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) Midsquare 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) 2N1 nodes
(d) N1 nodes (e) 2(N1) 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 outdegree and a positive indegree is called
(a) Source node (b) Sink node (c) Sibling node
(d) Null node (e) Innode.

28.

The time
complexity of the normal quick sort, randomized quick sort algorithms in the
worst case is
(a) O(n^{2}), O(n log n) (b) O(n^{2}), O(n^{2})
(c) O(n log n), O(n^{2}) (d) O(n log n), O(n log n)
(e) O(n log n), O(n^{2} 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) N^{2}
times
(d) N1 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
2n1 nodes, then there would be n leaves exactly.

24.

Answer : (d)
Reason: This is 2^{5} – 1. (2^{level}
– 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 i^{th}
smallest element with the i^{th} position. And we do this for i=1 to
n1 times.

30.

Answer : (c)
Reason: As Merge sort is the only one from the given
sorting techniques which is used for the external sorting.

Thank You so much,it was very helpful god bless you!
ReplyDeleteRespected sir,
ReplyDeleteHere Question number 27th and its answers are bit confusing . please check once sir
Regards
sri