McqMate
410+ Design and Analysis of Algorithms Solved MCQs
70
55.1k
| 101. |
Quick sort uses join operation rather than merge operation. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: quick sort uses join operation since join is a faster operation than merge. | |
| 102. |
How many sub arrays does the quick sort algorithm divide the entire array into? |
| A. | one |
| B. | two |
| C. | three |
| D. | four |
| Answer» B. two | |
| Explanation: the entire array is divided into two partitions, 1st sub array containing elements less than the pivot element and 2nd sub array containing elements greater than the pivot element. | |
| 103. |
Which is the worst method of choosing a pivot element? |
| A. | first element as pivot |
| B. | last element as pivot |
| C. | median-of-three partitioning |
| D. | random element as pivot |
| Answer» A. first element as pivot | |
| Explanation: choosing the first element as pivot is the worst method because if the input is pre-sorted or in reverse order, then the pivot provides a poor partition. | |
| 104. |
The shortest distance between a line and a point is achieved when? |
| A. | a line is drawn at 90 degrees to the given line from the given point |
| B. | a line is drawn at 180 degrees to the given line from the given point |
| C. | a line is drawn at 60 degrees to the given line from the given point |
| D. | a line is drawn at 270 degrees to the given line from the given point |
| Answer» A. a line is drawn at 90 degrees to the given line from the given point | |
| Explanation: the shortest distance between a line and a point is achieved when a line is drawn at 90 degrees to the given line from the given point. | |
| 105. |
What is the shortest distance between the line given by -2x + 3y + 4 = 0 and the point (5,6)? |
| A. | 4.5 units |
| B. | 5.4 units |
| C. | 4.3 units |
| D. | 3.3 units |
| Answer» D. 3.3 units | |
| Explanation: the shortest distance between a line and a point is given by the formula (ax1+by1+c)/(√a2+b2). using this formula we get the answer 3.3 units. | |
| 106. |
What is the distance between the lines 3x- 4y+7=0 and 3x-4y+5=0? |
| A. | 1 unit |
| B. | 0.5 unit |
| C. | 0.8 unit |
| D. | 0.4 unit |
| Answer» D. 0.4 unit | |
| Explanation: as the given lines are parallel so the distance between them can be calculated by using the formula (c1- c2)/(√a2+b2). so we get the distance as 0.4 unit. | |
| 107. |
What will be the slope of the line given by ax + by + c = 0? |
| A. | -a/b |
| B. | -b/a |
| C. | -c/a |
| D. | a/c |
| Answer» A. -a/b | |
| Explanation: the slope of a line given by the equation ax + by + c=0 has the slope of -a/b. so two lines having the same ratio of the coefficient of x and y will be parallel to each other. | |
| 108. |
What will be the slope of the line given by 10x + 5y + 8=0? |
| A. | -5 |
| B. | -2 |
| C. | -1.25 |
| D. | 5 |
| Answer» B. -2 | |
| Explanation: the slope of a line given by the equation ax + by + c=0 has the slope of -a/b. so the slope of the given line will be -2. | |
| 109. |
Which of the following areas do closest pair problem arise? |
| A. | computational geometry |
| B. | graph colouring problems |
| C. | numerical problems |
| D. | string matching |
| Answer» A. computational geometry | |
| Explanation: closest pair problem arises in two most important areas- computational geometry and operational research. | |
| 110. |
What is the runtime efficiency of using brute force technique for the closest pair problem? |
| A. | o(n) |
| B. | o(n log n) |
| C. | o(n2) |
| D. | o(n3 log n) |
| Answer» C. o(n2) | |
| Explanation: the efficiency of closest pair algorithm by brute force technique is mathematically found to be o(n2). | |
| 111. |
The most important condition for which closest pair is calculated for the points (pi, pj) is? |
| A. | i>j |
| B. | i!=j |
| C. | i=j |
| D. | i<j |
| Answer» D. i<j | |
| Explanation: to avoid computing the distance between the same pair of points twice, we consider only the pair of points (pi, pj) for which i<j. | |
| 112. |
What is the basic operation of closest pair algorithm using brute force technique? |
| A. | euclidean distance |
| B. | radius |
| C. | area |
| D. | manhattan distance |
| Answer» A. euclidean distance | |
| Explanation: the basic operation of closest | |
| 113. |
Which of the following is similar to Euclidean distance? |
| A. | manhattan distance |
| B. | pythagoras metric |
| C. | chebyshev distance |
| D. | heuristic distance |
| Answer» B. pythagoras metric | |
| Explanation: in older times, euclidean distance metric is also called a pythagoras metric which is the length of the line segment connecting two points. | |
| 114. |
Which of the following strategies does the following diagram depict? |
| A. | divide and conquer strategy |
| B. | brute force |
| C. | exhaustive search |
| D. | backtracking |
| Answer» B. brute force | |
| Explanation: brute force is a straight forward approach to solve critical problems. here, we use brute force technique to find the closest distance between p1 and p2. | |
| 115. |
Manhattan distance is an alternative way to define a distance between two points. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: manhattan distance is an alternative way to calculate distance. it is the distance between two points measured along axes at right angles. | |
| 116. |
What is the optimal time required for solving the closest pair problem using divide and conquer approach? |
| A. | o(n) |
| B. | o(log n) |
| C. | o(n log n) |
| D. | o(n2) |
| Answer» C. o(n log n) | |
| Explanation: the optimal time for solving using a divide and conquer approach is mathematically found to be o(n log n). | |
| 117. |
In divide and conquer, the time is taken for merging the subproblems is? |
| A. | o(n) |
| B. | o(n log n) |
| C. | o(n2) |
| D. | o(log n) |
| Answer» B. o(n log n) | |
| Explanation: the time taken for merging the smaller subproblems in a divide and conquer approach is mathematically found to be o(n log n). | |
| 118. |
The optimal time obtained through divide and conquer approach using merge sort is the best case efficiency. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: the optimal time obtained through divide and conquer approach is the best class efficiency and it is given by Ω(n log n). | |
| 119. |
Which of the following strategies does the following diagram depict? |
| A. | brute force |
| B. | divide and conquer |
| C. | exhaustive search |
| D. | branch and bound |
| Answer» B. divide and conquer | |
| Explanation: the above diagram depicts the implementation of divide and conquer. the problem is divided into sub problems and are separated by a line. | |
| 120. |
Which of the points are closer to each other? |
| A. | p1 and p11 |
| B. | p3 and p8 |
| C. | p2 and p3 |
| D. | p9 and p10 |
| Answer» C. p2 and p3 | |
| Explanation: from symmetry, we determine that the closest pair is p2 and p3. but the exact calculations have to be done using euclid’s algorithm. | |
| 121. |
Cross product is a mathematical operation performed between |
| A. | 2 scalar numbers |
| B. | a scalar and a vector |
| C. | 2 vectors |
| D. | any 2 numbers |
| Answer» C. 2 vectors | |
| Explanation: cross product is a mathematical operation that is performed on 2 vectors in a 3d plane. it has many applications in computer programming and physics. | |
| 122. |
Cross product is also known as? |
| A. | scalar product |
| B. | vector product |
| C. | dot product |
| D. | multiplication |
| Answer» B. vector product | |
| Explanation: cross product is also known as a vector product. it is a mathematical operation that is performed on 2 vectors in 3d plane. | |
| 123. |
The concept of cross product is applied in the field of computer graphics. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: the concept of cross product find its application in the field of computer graphics. it can be used to find the winding of polygon about a point. | |
| 124. |
Which of the following equals the a x b ( a and b are two vectors)? |
| A. | – (a x b) |
| B. | a.b |
| C. | b x a |
| D. | – (b x a) |
| Answer» D. – (b x a) | |
| Explanation: the vector product a x b is equal to – (b x a). the minus sign shows that these vectors have opposite directions. | |
| 125. |
Cross product of two vectors can be used to find? |
| A. | area of rectangle |
| B. | area of square |
| C. | area of parallelogram |
| D. | perimeter of rectangle |
| Answer» C. area of parallelogram | |
| Explanation: cross product of two vectors can be used to find the area of parallelogram. for this, we need to consider the vectors as the adjacent sides of the parallelogram. | |
| 126. |
What will be the cross product of the vectors 2i + 3j + k and 3i + 2j + k? |
| A. | i + 2j + k |
| B. | 2i + 3j + k |
| C. | i + j – 5k |
| D. | 2i – j – 5k |
| Answer» C. i + j – 5k | |
| Explanation: we can find the cross product of the given vectors by solving the determinant. | |
| 127. |
What will be the cross product of the vectors 2i + 3j + k and 6i + 9j + 3k? |
| A. | i + 2j + k |
| B. | i – j – 5k |
| C. | 0 |
| D. | 2i – j – 5k |
| Answer» C. 0 | |
| Explanation: the given vectors are parallel to each other. the cross product of parallel vectors is 0 because sin(0) is 0. | |
| 128. |
Which of the following operation will give a vector that is perpendicular to both vectors a and b? |
| A. | a x b |
| B. | a.b |
| C. | b x a |
| D. | both a x b and b x a |
| Answer» D. both a x b and b x a | |
| Explanation: the resultant vector from the cross product of two vectors is perpendicular to the plane containing both vectors. so both a x b and b x a will give a vector that is perpendicular to both vectors a and b. | |
| 129. |
is a method of constructing a smallest polygon out of n given points. |
| A. | closest pair problem |
| B. | quick hull problem |
| C. | path compression |
| D. | union-by-rank |
| Answer» B. quick hull problem | |
| Explanation: quick hull is a method of | |
| 130. |
What is the other name for quick hull problem? |
| A. | convex hull |
| B. | concave hull |
| C. | closest pair |
| D. | path compression |
| Answer» A. convex hull | |
| Explanation: the other name for quick hull problem is convex hull problem whereas the closest pair problem is the problem of finding the closest distance between two points. | |
| 131. |
How many approaches can be applied to solve quick hull problem? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» B. 2 | |
| Explanation: most commonly, two approaches are adopted to solve quick hull problem- brute force approach and divide and conquer approach. | |
| 132. |
What is the average case complexity of a quick hull algorithm? |
| A. | o(n) |
| B. | o(n log n) |
| C. | o(n2) |
| D. | o(log n) |
| Answer» B. o(n log n) | |
| Explanation: the average case complexity of quickhull algorithm using divide and conquer approach is mathematically found to be o(n log n). | |
| 133. |
What is the worst case complexity of quick hull? |
| A. | o(n) |
| B. | o(n log n) |
| C. | o(n2) |
| D. | o(log n) |
| Answer» C. o(n2) | |
| Explanation: the worst case complexity of quickhull algorithm using divide and conquer approach is mathematically found to be o(n2). | |
| 134. |
What does the following diagram depict? |
| A. | closest pair |
| B. | convex hull |
| C. | concave hull |
| D. | path compression |
| Answer» B. convex hull | |
| Explanation: the above diagram is a depiction of convex hull, also known as quick hull, since it encloses n points into a convex polygon. | |
| 135. |
Which of the following statement is not related to quickhull algorithm? |
| A. | finding points with minimum and maximum coordinates |
| B. | dividing the subset of points by a line |
| C. | eliminating points within a formed triangle |
| D. | finding the shortest distance between two points |
| Answer» D. finding the shortest distance between two points | |
| Explanation: finding the shortest distance between two points belongs to closest pair algorithm while the rest is quickhull. | |
| 136. |
The quick hull algorithm runs faster if the input uses non- extreme points. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: it is proved that the quick hull algorithm runs faster if the input uses non- | |
| 137. |
To which type of problems does quick hull belong to? |
| A. | numerical problems |
| B. | computational geometry |
| C. | graph problems |
| D. | string problems |
| Answer» B. computational geometry | |
| Explanation: quick hull problem and closest pair algorithms are some of the examples of computational problems. | |
| 138. |
Which of the following algorithms is similar to a quickhull algorithm? |
| A. | merge sort |
| B. | shell sort |
| C. | selection sort |
| D. | quick sort |
| Answer» D. quick sort | |
| Explanation: quickhull algorithm is similar to a quick sort algorithm with respect to the run time average case and worst case efficiencies. | |
| 139. |
Who formulated quick hull algorithm? |
| A. | eddy |
| B. | andrew |
| C. | chan |
| D. | graham |
| Answer» A. eddy | |
| Explanation: eddy formulated quick hull algorithm. graham invented graham scan. andrew formulated andrew’s algorithm and chan invented chan’s algorithm. | |
| 140. |
The time is taken to find the ‘n’ points that lie in a convex quadrilateral is? |
| A. | o(n) |
| B. | o(n log n) |
| C. | o(n2) |
| D. | o(log n) |
| Answer» A. o(n) | |
| Explanation: the time taken to find the ‘n’ points that lie in a convex quadrilateral is mathematically found to be o(n). | |
| 141. |
Chan’s algorithm is used for computing |
| A. | closest distance between two points |
| B. | convex hull |
| C. | area of a polygon |
| D. | shortest path between two points |
| Answer» B. convex hull | |
| Explanation: chan’s algorithm is an output- sensitive algorithm used to compute the convex hull set of n points in a 2d or 3d space. closest pair algorithm is used to compute the closest distance between two points. | |
| 142. |
What is the running time of Chan’s algorithm? |
| A. | o(log n) |
| B. | o(n log n) |
| C. | o(n log h) |
| D. | o(log h) |
| Answer» C. o(n log h) | |
| Explanation: the running time of chan’s algorithm is calculated to be o(n log h) where h is the number of vertices of the convex hull. | |
| 143. |
Who formulated Chan’s algorithm? |
| A. | timothy |
| B. | kirkpatrick |
| C. | frank nielsen |
| D. | seidel |
| Answer» A. timothy | |
| Explanation: chan’s algorithm was formulated by timothy chan. kirkpatrick and seidel formulated the kirkpatrick-seidel algorithm. frank nielsen developed a paradigm relating to chan’s algorithm. | |
| 144. |
The running time of Chan’s algorithm is obtained from combining two algorithms. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: the o(n log h) running time of chan’s algorithm is obtained by combining the running time of graham’s scan [o(n log n)] and jarvis match [o(nh)]. | |
| 145. |
Which of the following is called the “ultimate planar convex hull algorithm”? |
| A. | chan’s algorithm |
| B. | kirkpatrick-seidel algorithm |
| C. | gift wrapping algorithm |
| D. | jarvis algorithm |
| Answer» B. kirkpatrick-seidel algorithm | |
| Explanation: kirkpatrick-seidel algorithm is called as the ultimate planar convex hull algorithm. its running time is the same as that of chan’s algorithm (i.e.) o(n log h). | |
| 146. |
Which of the following algorithms is the simplest? |
| A. | chan’s algorithm |
| B. | kirkpatrick-seidel algorithm |
| C. | gift wrapping algorithm |
| D. | jarvis algorithm |
| Answer» A. chan’s algorithm | |
| Explanation: chan’s algorithm is very practical for moderate sized problems whereas kirkpatrick-seidel algorithm is not. although, they both have the same running time. gift wrapping algorithm is a non-output sensitive algorithm and has a longer running time. | |
| 147. |
What is the running time of Hershberger algorithm? |
| A. | o(log n) |
| B. | o(n log n) |
| C. | o(n log h) |
| D. | o(log h) |
| Answer» B. o(n log n) | |
| Explanation: hershberger’s algorithm is an output sensitive algorithm whose running | |
| 148. |
Which of the following statements is not a part of Chan’s algorithm? |
| A. | eliminate points not in the hull |
| B. | recompute convex hull from scratch |
| C. | merge previously calculated convex hull |
| D. | reuse convex hull from the previous iteration |
| Answer» B. recompute convex hull from scratch | |
| Explanation: chan’s algorithm implies that the convex hulls of larger points can be arrived at by merging previously calculated convex hulls. it makes the algorithm simpler instead of recomputing every time from scratch. | |
| 149. |
Which of the following factors account more to the cost of Chan’s algorithm? |
| A. | computing a single convex hull |
| B. | locating points that constitute a hull |
| C. | computing convex hull in groups |
| D. | merging convex hulls |
| Answer» C. computing convex hull in groups | |
| Explanation: the majority of the cost of the algorithm lies in the pre-processing (i.e.) computing convex hull in groups. to reduce cost, we reuse convex hulls from previous iterations. | |
| 150. |
Chan’s algorithm can be used to compute the lower envelope of a trapezoid. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: an extension of chan’s algorithm can be used for proving solutions to complex problems like computing the lower envelope l(s) where s is a set of ‘n’ line segments in a trapezoid. | |
| 151. |
Which of the following is false in the case of a spanning tree of a graph G? |
| A. | it is tree that spans g |
| B. | it is a subgraph of the g |
| C. | it includes every vertex of the g |
| D. | it can be either cyclic or acyclic |
| Answer» D. it can be either cyclic or acyclic | |
| Explanation: a graph can have many spanning trees. each spanning tree of a graph g is a subgraph of the graph g, and spanning trees include every vertex of the gram. | |
| 152. |
Every graph has only one minimum spanning tree. |
| A. | true |
| B. | false |
| Answer» B. false | |
| Explanation: minimum spanning tree is a spanning tree with the lowest cost among all the spacing trees. sum of all of the edges in the spanning tree is the cost of the spanning tree. there can be many minimum spanning trees for a given graph. | |
| 153. |
Consider a complete graph G with 4 vertices. The graph G has spanning trees. |
| A. | 15 |
| B. | 8 |
| C. | 16 |
| D. | 13 |
| Answer» C. 16 | |
| Explanation: a graph can have many spanning trees. and a complete graph with n vertices has n(n-2) spanning trees. so, the complete graph with 4 vertices has 4(4-2) = 16 spanning trees. | |
| 154. |
The travelling salesman problem can be solved using |
| A. | a spanning tree |
| B. | a minimum spanning tree |
| C. | bellman – ford algorithm |
| D. | dfs traversal |
| Answer» B. a minimum spanning tree | |
| Explanation: in the travelling salesman problem we have to find the shortest possible route that visits every city exactly once and returns to the starting point for the given a set of cities. so, travelling salesman problem can be solved by contracting the minimum spanning tree. | |
| 155. |
Consider the graph M with 3 vertices. Its adjacency matrix is shown below. Which of the following is true?
|
| A. | graph m has no minimum spanning tree |
| B. | graph m has a unique minimum spanning trees of cost 2 |
| C. | graph m has 3 distinct minimum spanning trees, each of cost 2 |
| D. | graph m has 3 spanning trees of different costs |
| Answer» C. graph m has 3 distinct minimum spanning trees, each of cost 2 | |
| Explanation: here all non-diagonal elements in the adjacency matrix are 1. so, every vertex is connected every other vertex of the graph. and, so graph m has 3 distinct minimum spanning trees. | |
| 156. |
Consider a undirected graph G with vertices { A, B, C, D, E}. In graph G, every edge has distinct weight. Edge CD is edge with minimum weight and edge AB is edge with maximum weight. Then, which of the following is false? |
| A. | every minimum spanning tree of g must contain cd |
| B. | if ab is in a minimum spanning tree, then its removal must disconnect g |
| C. | no minimum spanning tree contains ab |
| D. | g has a unique minimum spanning tree |
| Answer» C. no minimum spanning tree contains ab | |
| Explanation: every mst will contain cd as it is smallest edge. so, every minimum spanning tree of g must contain cd is true. and g has a unique minimum spanning tree is also true because the graph has edges with distinct weights. so, no minimum spanning tree contains ab is false. | |
| 157. |
If all the weights of the graph are positive, then the minimum spanning tree of the graph is a minimum cost subgraph. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: a subgraph is a graph formed from a subset of the vertices and edges of the original graph. and the subset of vertices includes all endpoints of the subset of the edges. so, we can say mst of a graph is a subgraph when all weights in the original graph are positive. | |
| 158. |
Which of the following is not the algorithm to find the minimum spanning tree of the given graph? |
| A. | boruvka’s algorithm |
| B. | prim’s algorithm |
| C. | kruskal’s algorithm |
| D. | bellman–ford algorithm |
| Answer» D. bellman–ford algorithm | |
| Explanation: the boruvka’s algorithm, prim’s algorithm and kruskal’s algorithm are the algorithms that can be used to find the minimum spanning tree of the given graph. the bellman-ford algorithm is used to find the shortest path from the single source to all other vertices. | |
| 159. |
Which of the following is false? |
| A. | the spanning trees do not have any cycles |
| B. | mst have n – 1 edges if the graph has n edges |
| C. | edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the msts of the graph |
| D. | removing one edge from the spanning tree will not make the graph disconnected |
| Answer» D. removing one edge from the spanning tree will not make the graph disconnected | |
| Explanation: every spanning tree has n – 1 edges if the graph has n edges and has no cycles. the mst follows the cut property, edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the msts of the graph. | |
| 160. |
Kruskal’s algorithm is used to |
| A. | find minimum spanning tree |
| B. | find single source shortest path |
| C. | find all pair shortest path algorithm |
| D. | traverse the graph |
| Answer» A. find minimum spanning tree | |
| Explanation: the kruskal’s algorithm is used to find the minimum spanning tree of the connected graph. it construct the mst by finding the edge having the least possible weight that connects two trees in the forest. | |
| 161. |
Kruskal’s algorithm is a |
| A. | divide and conquer algorithm |
| B. | dynamic programming algorithm |
| C. | greedy algorithm |
| D. | approximation algorithm |
| Answer» C. greedy algorithm | |
| Explanation: kruskal’s algorithm uses a greedy algorithm approach to find the mst of the connected weighted graph. in the greedy method, we attempt to find an optimal solution in stages. | |
| 162. |
What is the time complexity of Kruskal’s algorithm? |
| A. | o(log v) |
| B. | o(e log v) |
| C. | o(e2) |
| D. | o(v log e) |
| Answer» B. o(e log v) | |
| Explanation: kruskal’s algorithm involves sorting of the edges, which takes o(e loge) time, where e is a number of edges in graph and v is the number of vertices. after sorting, all edges are iterated and union-find algorithm is applied. union-find algorithm requires o(logv) time. so, overall kruskal’s algorithm requires o(e log v) time. | |
| 163. |
Consider the following graph. Using Kruskal’s algorithm, which edge will be selected first? |
| A. | gf |
| B. | de |
| C. | be |
| D. | bg |
| Answer» C. be | |
| Explanation: in krsuskal’s algorithm the edges are selected and added to the spanning tree in increasing order of their weights. | |
| 164. |
Which of the following edges form minimum spanning tree on the graph using kruskals algorithm? |
| A. | (b-e)(g-e)(e-f)(d-f) |
| B. | (b-e)(g-e)(e-f)(b-g)(d-f) |
| C. | (b-e)(g-e)(e-f)(d-e) |
| D. | (b-e)(g-e)(e-f)(d-f)(d-g) |
| Answer» A. (b-e)(g-e)(e-f)(d-f) | |
| Explanation: using krushkal’s algorithm on the given graph, the generated minimum spanning tree is shown below. | |
| 165. |
Which of the following is false about the Kruskal’s algorithm? |
| A. | it is a greedy algorithm |
| B. | it constructs mst by selecting edges in increasing order of their weights |
| C. | it can accept cycles in the mst |
| D. | it uses union-find data structure |
| Answer» C. it can accept cycles in the mst | |
| Explanation: kruskal’s algorithm is a greedy algorithm to construct the mst of the given graph. it constructs the mst by selecting edges in increasing order of their weights and rejects an edge if it may form the cycle. so, using kruskal’s algorithm is never formed. | |
| 166. |
Kruskal’s algorithm is best suited for the dense graphs than the prim’s algorithm. |
| A. | true |
| B. | false |
| Answer» B. false | |
| Explanation: prim’s algorithm outperforms the kruskal’s algorithm in case of the dense graphs. it is significantly faster if graph has more edges than the kruskal’s algorithm. | |
| 167. |
Kruskal’s algorithm can efficiently implemented using the disjoint-set data structure. |
| A. | s1 is true but s2 is false |
| B. | both s1 and s2 are false |
| C. | both s1 and s2 are true |
| D. | s2 is true but s1 is false |
| Answer» D. s2 is true but s1 is false | |
| Explanation: in kruskal’s algorithm, the disjoint-set data structure efficiently identifies the components containing a vertex and adds the new edges. and kruskal’s algorithm always finds the mst for the connected graph. | |
| 168. |
Which of the following is true? |
| A. | prim’s algorithm initialises with a vertex |
| B. | prim’s algorithm initialises with a edge |
| C. | prim’s algorithm initialises with a vertex which has smallest edge |
| D. | prim’s algorithm initialises with a forest |
| Answer» A. prim’s algorithm initialises with a vertex | |
| Explanation: steps in prim’s algorithm: (i) select any vertex of given graph and add it to mst (ii) add the edge of minimum weight from a vertex not in mst to the vertex in mst; (iii) it mst is complete the stop, otherwise go to step (ii). | |
| 169. |
Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used? |
| A. | o(log v) |
| B. | o(v2) |
| C. | o(e2) |
| D. | o(v log e) |
| Answer» B. o(v2) | |
| Explanation: use of adjacency matrix provides the simple implementation of the prim’s algorithm. in prim’s algorithm, we need to search for the edge with a minimum for that vertex. so, worst case time complexity will be o(v2), where v is the number of vertices. | |
| 170. |
Prim’s algorithm is a |
| A. | divide and conquer algorithm |
| B. | greedy algorithm |
| C. | dynamic programming |
| D. | approximation algorithm |
| Answer» B. greedy algorithm | |
| Explanation: prim’s algorithm uses a greedy algorithm approach to find the mst of the connected weighted graph. in greedy method, we attempt to find an optimal solution in stages. | |
| 171. |
Prim’s algorithm resembles Dijkstra’s algorithm. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: in prim’s algorithm, the mst is constructed starting from a single vertex and adding in new edges to the mst that link the partial tree to a new vertex outside of the mst. and dijkstra’s algorithm also rely on the similar approach of finding the next closest vertex. so, prim’s algorithm | |
| 172. |
Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: prim’s algorithm and kruskal’s algorithm perform equally in case of the sparse graphs. but kruskal’s algorithm is simpler and easy to work with. so, it is best suited for sparse graphs. | |
| 173. |
Prim’s algorithm can be efficiently implemented using for graphs with greater density. |
| A. | d-ary heap |
| B. | linear search |
| C. | fibonacci heap |
| D. | binary search |
| Answer» A. d-ary heap | |
| Explanation: in prim’s algorithm, we add the minimum weight edge for the chosen vertex which requires searching on the array of weights. this searching can be efficiently implemented using binary heap for dense graphs. and for graphs with greater density, prim’s algorithm can be made to run in linear time using d-ary heap(generalization of binary heap). | |
| 174. |
Which of the following is false about Prim’s algorithm? |
| A. | it is a greedy algorithm |
| B. | it constructs mst by selecting edges in increasing order of their weights |
| C. | it never accepts cycles in the mst |
| D. | it can be implemented using the fibonacci heap |
| Answer» B. it constructs mst by selecting edges in increasing order of their weights | |
| Explanation: prim’s algorithm can be implemented using fibonacci heap and it never accepts cycles. and prim’s algorithm follows greedy approach. prim’s algorithms | |
| 175. |
Which of the following is the most commonly used data structure for implementing Dijkstra’s Algorithm? |
| A. | max priority queue |
| B. | stack |
| C. | circular queue |
| D. | min priority queue |
| Answer» D. min priority queue | |
| Explanation: minimum priority queue is the most commonly used data structure for implementing dijkstra’s algorithm because the required operations to be performed in dijkstra’s algorithm match with specialty of a minimum priority queue. | |
| 176. |
How many priority queue operations are involved in Dijkstra’s Algorithm? |
| A. | 1 |
| B. | 3 |
| C. | 2 |
| D. | 4 |
| Answer» B. 3 | |
| Explanation: the number of priority queue operations involved is 3. they are insert, extract-min and decrease key. | |
| 177. |
How many times the insert and extract min operations are invoked per vertex? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 0 |
| Answer» A. 1 | |
| Explanation: insert and extract min operations are invoked only once per vertex because each vertex is added only once to the set and each edge in the adjacency list is examined only once during the course of algorithm. | |
| 178. |
The maximum number of times the decrease key operation performed in Dijkstra’s algorithm will be equal to |
| A. | total number of vertices |
| B. | total number of edges |
| C. | number of vertices – 1 |
| D. | number of edges – 1 |
| Answer» B. total number of edges | |
| Explanation: if the total number of edges in all adjacency list is e, then there will be a total of e number of iterations, hence there will be a total of at most e decrease key operations. | |
| 179. |
What is running time of Dijkstra’s algorithm using Binary min- heap method? |
| A. | o(v) |
| B. | o(vlogv) |
| C. | o(e) |
| D. | o(elogv) |
| Answer» D. o(elogv) | |
| Explanation: time required to build a binary min heap is o(v). each decrease key operation takes o(logv) and there are still at most e such operations. hence total running time is o(elogv). | |
| 180. |
The running time of Bellmann Ford algorithm is lower than that of Dijkstra’s Algorithm. |
| A. | true |
| B. | false |
| Answer» B. false | |
| Explanation: the number of iterations involved in bellmann ford algorithm is more than that of dijkstra’s algorithm. | |
| 181. |
Dijkstra’s Algorithm run on a weighted, directed graph G={V,E} with non-negative weight function w and source s, terminates with d[u]=delta(s,u) for all vertices u in V. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: the equality d[u]=delta(s,u) holds good when vertex u is added to set s and this equality is maintained thereafter by the upper bound property. | |
| 182. |
Dijkstra’s Algorithm is the prime example for |
| A. | greedy algorithm |
| B. | branch and bound |
| C. | back tracking |
| D. | dynamic programming |
| Answer» A. greedy algorithm | |
| Explanation: dijkstra’s algorithm is the prime example for greedy algorithms because greedy algorithms generally solve a problem in stages by doing what appears to be the best thing at each stage. | |
| 183. |
Bellmann ford algorithm provides solution for problems. |
| A. | all pair shortest path |
| B. | sorting |
| C. | network flow |
| D. | single source shortest path |
| Answer» D. single source shortest path | |
| Explanation: bellmann ford algorithm is used for finding solutions for single source shortest path problems. if the graph has no negative cycles that are reachable from the source then the algorithm produces the shortest paths and their weights. | |
| 184. |
Bellmann Ford algorithm is used to indicate whether the graph has negative weight cycles or not. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: bellmann ford algorithm returns true if the graph does not have any negative weight cycles and returns false when the graph has negative weight cycles. | |
| 185. |
How many solution/solutions are available for a graph having negative weight cycle? |
| A. | one solution |
| B. | two solutions |
| C. | no solution |
| D. | infinite solutions |
| Answer» C. no solution | |
| Explanation: if the graph has any negative weight cycle then the algorithm indicates that no solution exists for that graph. | |
| 186. |
What is the running time of Bellmann Ford Algorithm? |
| A. | o(v) |
| B. | o(v2) |
| C. | o(elogv) |
| D. | o(ve) |
| Answer» D. o(ve) | |
| Explanation: bellmann ford algorithm runs in time o(ve), since the initialization takes o(v) for each of v-1 passes and the for loop in the algorithm takes o(e) time. hence the total time taken by the algorithm is o(ve). | |
| 187. |
How many times the for loop in the Bellmann Ford Algorithm gets executed? |
| A. | v times |
| B. | v-1 |
| C. | e |
| D. | e-1 |
| Answer» B. v-1 | |
| Explanation: the for loop in the bellmann ford algorithm gets executed for v-1 times. after making v-1 passes, the algorithm checks for a negative weight cycle and returns appropriate boolean value. | |
| 188. |
Dijikstra’s Algorithm is more efficient than Bellmann Ford Algorithm. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: the running time of bellmann ford algorithm is o(ve) whereas dijikstra’s algorithm has running time of only o(v2). | |
| 189. |
What is the basic principle behind Bellmann Ford Algorithm? |
| A. | interpolation |
| B. | extrapolation |
| C. | regression |
| D. | relaxation |
| Answer» D. relaxation | |
| Explanation: relaxation methods which are also called as iterative methods in which an approximation to the correct distance is replaced progressively by more accurate values till an optimum solution is found. | |
| 190. |
Bellmann Ford Algorithm can be applied for |
| A. | undirected and weighted graphs |
| B. | undirected and unweighted graphs |
| C. | directed and weighted graphs |
| D. | all directed graphs |
| Answer» C. directed and weighted graphs | |
| Explanation: bellmann ford algorithm can be applied for all directed and weighted graphs. the weight function in the graph may either be positive or negative. | |
| 191. |
Bellmann Ford algorithm was first proposed by |
| A. | richard bellmann |
| B. | alfonso shimbe |
| C. | lester ford jr |
| D. | edward f. moore |
| Answer» B. alfonso shimbe | |
| Explanation: alfonso shimbe proposed bellmann ford algorithm in the year 1955. later it was published by richard bellmann in 1957 and lester ford jr in the year 1956. hence it is called bellmann ford algorithm. | |
| 192. |
Bellmann Ford Algorithm is an example for |
| A. | dynamic programming |
| B. | greedy algorithms |
| C. | linear programming |
| D. | branch and bound |
| Answer» A. dynamic programming | |
| Explanation: in bellmann ford algorithm the shortest paths are calculated in bottom up manner which is similar to other dynamic programming problems. | |
| 193. |
A graph is said to have a negative weight cycle when? |
| A. | the graph has 1 negative weighted edge |
| B. | the graph has a cycle |
| C. | the total weight of the graph is negative |
| D. | the graph has 1 or more negative weighted edges |
| Answer» C. the total weight of the graph is negative | |
| Explanation: when the total weight of the graph sums up to a negative number then the graph is said to have a negative weight cycle. bellmann ford algorithm provides no solution for such graphs. | |
| 194. |
Floyd Warshall’s Algorithm is used for solving |
| A. | all pair shortest path problems |
| B. | single source shortest path problems |
| C. | network flow problems |
| D. | sorting problems |
| Answer» A. all pair shortest path problems | |
| Explanation: floyd warshall’s algorithm is used for solving all pair shortest path problems. it means the algorithm is used for finding the shortest paths between all pairs of vertices in a graph. | |
| 195. |
Floyd Warshall’s Algorithm can be applied on |
| A. | undirected and unweighted graphs |
| B. | undirected graphs |
| C. | directed graphs |
| D. | acyclic graphs |
| Answer» C. directed graphs | |
| Explanation: floyd warshall algorithm can be applied in directed graphs. from a given directed graph, an adjacency matrix is framed and then all pair shortest path is computed by the floyd warshall algorithm. | |
| 196. |
What is the running time of the Floyd Warshall Algorithm? |
| A. | big-oh(v) |
| B. | theta(v2) |
| C. | big-oh(ve) |
| D. | theta(v3) |
| Answer» D. theta(v3) | |
| Explanation: the running time of the floyd warshall algorithm is determined by the triply nested for loops. since each execution of the for loop takes o(1) time, the algorithm runs in time theta(v3). | |
| 197. |
What approach is being followed in Floyd Warshall Algorithm? |
| A. | greedy technique |
| B. | dynamic programming |
| C. | linear programming |
| D. | backtracking |
| Answer» B. dynamic programming | |
| Explanation: floyd warshall algorithm follows dynamic programming approach because the all pair shortest paths are computed in bottom up manner. | |
| 198. |
Floyd Warshall Algorithm can be used for finding |
| A. | single source shortest path |
| B. | topological sort |
| C. | minimum spanning tree |
| D. | transitive closure |
| Answer» D. transitive closure | |
| Explanation: one of the ways to compute the transitive closure of a graph in theta(n3) time is to assign a weight of 1 to each edge of e and then run the floyd warshall algorithm. | |
| 199. |
What procedure is being followed in Floyd Warshall Algorithm? |
| A. | top down |
| B. | bottom up |
| C. | big bang |
| D. | sandwich |
| Answer» B. bottom up | |
| Explanation: bottom up procedure is being used to compute the values of the matrix elements dij(k). the input is an n x n matrix. | |
| 200. |
Floyd- Warshall algorithm was proposed by |
| A. | robert floyd and stephen warshall |
| B. | stephen floyd and robert warshall |
| C. | bernad floyd and robert warshall |
| D. | robert floyd and bernad warshall |
| Answer» A. robert floyd and stephen warshall | |
| Explanation: floyd- warshall algorithm was proposed by robert floyd in the year 1962. | |
Done Reading?
Tags
- Question and answers in Design and Analysis of Algorithms,
- Design and Analysis of Algorithms multiple choice questions and answers,
- Design and Analysis of Algorithms Important MCQs,
- Solved MCQs for Design and Analysis of Algorithms,
- Design and Analysis of Algorithms MCQs with answers PDF download