Data Structure and Algorithm Analysis Set 3

Data Structure and Algorithm Analysis

Questions 21 to 30

21.	What do you call the selected keys in the quick sort method? (a)  Outer key (b)  Inner Key       (c)  Partition key (d)  Pivot key (e)  Recombine key.
22.	Primary clustering occurs in (a)  Linear probing         (b)  Quadratic probing (c)  Mid-square method  (d)  Order probing                                    (e)  Chaining.
23.	How many nodes do a full binary tree with ‘N’ leaves contain? (a)  2N nodes        (b)  N nodes (c)  2N-1 nodes (d)  N-1 nodes       (e)  2(N-1) nodes.
24.	How many nodes does a complete binary tree of level 5 have? (a)  16     (b)  15     (c)  32           (d)  31   (e)  64.
25.	How do you determine the cost of a spanning tree? (a)   By the sum of the costs of the edges of the tree (b)   By the sum of the costs of the edges and vertices of the tree (c)   By the sum of the costs of the vertices of the tree (d)   By the sum of the costs of the edges of the graph (e)   By the sum of the costs of the edges and vertices of the graph.
26.	What would be the depth of tree whose level is 9? (a)  10     (b)  8      (c)  9            (d)  11   (e)  7.
27.	A node of a directed graph G having no out-degree and a positive in-degree is called (a)  Source node    (b)  Sink node           (c)  Sibling node (d)  Null node (e)  In-node.
28.	The time complexity of the normal quick sort, randomized quick sort algorithms in the worst case is (a)  O(n2), O(n log n)                  (b)  O(n2), O(n2) (c)  O(n log n), O(n2)                  (d)  O(n log n), O(n log n) (e)  O(n log n), O(n2 log n).
29.	Let there be an array of length ‘N’, and the selection sort algorithm is used to sort it, how many times a swap function is called to complete the execution? (a)  N log N times          (b)  log N times (c)  N2 times (d)  N-1 times        (e)  N times.
30.	The Sorting method which is used for external sort is (a)  Bubble sort     (b)  Quick sort                       (c)  Merge sort (d)  Radix sort       (e)  Selection sort.

Answers

21.	Answer : (d) Reason:  As in quick sort the division is made at an element which is pivotal element.
22.	Answer : (a) Reason:  As there is no chance for the other probing techniques to have primary clustering.
23.	Answer : (c) Reason:  According to full binary tree, if there are 2n-1 nodes, then there would be n leaves exactly.
24.	Answer : (d) Reason:  This is 25 – 1. (2level – 1)
25.	Answer : (a) Reason:  As the other options are wrong, and the cost of a spanning tree is the cost of edges of the tree only.
26.	Answer : (c) Reason:  As both the depth and level are same.
27.	Answer : (a) Reason:  Because the source vertex is a vertex which contains only leaving edges, but no any incoming edge.
28.	Answer : (b) Reason:  Because, there is no difference between normal quick sort and randomized quick sort algorithms for their efficiency, except the picking of a pivotal element.
29.	Answer : (d) Reason:  Because, every time we swap the ith smallest element with the ith position. And we do this for i=1 to n-1 times.
30.	Answer : (c) Reason:  As Merge sort is the only one from the given sorting techniques which is used for the external sorting.

<< Prev  Set 1  Set 2  Set 3  Set 4  Set 5  Set 6  Set 7  Set 8  Set 9  Set 10  Set 11  Set 12  Set 13  Set 14  Set 15  Set 16  Set 17  Set 18  Set 19  Set 20  Set 21  Set 22  Set 23  Set 24  Set 25  Set 26  Set 27  Set 28  Set 29  Set 30  Next >>