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?
(aOuter 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.




2 comments :

  1. Thank You so much,it was very helpful god bless you!

    ReplyDelete
  2. Respected sir,
    Here Question number 27th and its answers are bit confusing . please check once sir
    Regards
    sri

    ReplyDelete