Data Structure
Trees
Q.

After applying the below operations on a input sequence, what happens?

i. construct a cartesian tree for input sequence

ii. put the root element of above tree in a priority queue

iii. if( priority queue is not empty) then

.search and delete minimum value in priority queue

.add that to output

.add cartesian tree children of above node to priority queue
A.  constructs a cartesian tree B.  sorts the input sequence C.  does nothing D.  produces some random output
Similar Questions
1. 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 thecosts of the edges and vertices of the graph.
2. In an arbitrary tree ( not a search tree) of order M. Its size is N, and its height is K. The computation time needed to find a data item on T is
A.  O(K*K) B.  O(M*M) C.  O(N) D.  O(K)
3. What would be the cost value for any answering node of a sub tree with root ‘r’ using branch-bound algorithm?
A.  Maximum B.  Minimum C.  Optimal D.  Average
4. How many nodes are there in a full state space tree with n = 6?
A.  65 B.  64 C.  63 D.  32
5. How many minimum number of spanning trees, one can have from a given connected graph with N nodes is having different weights for the edges.
A.  N-1 B.  One C.  1/(N+1) 2NCN D.  2NCN
6.

The following formula is of :

left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)
A.  Bianry Tree B.  Complete Binary Tree C.  Binary Search Tree D.  All of the above
7. Binary search tree has best case run-time complexity of Ο(log n). What could the worst case?
A.  Ο(n) B.  Ο(n2) C.  Ο(n3) D.  None of the above
8. In order traversal of binary search tree will produce −
A.  unsorted list B.  reverse of input C.  sorted list D.  none of the above
9. In binary heap, whenever the root is removed then the rightmost element of last level is replaced by the root. Why?
A.  It is the easiest possible way. B.  To make sure that it is still complete binary tree. C.  Because left and right subtree might be missing. D.  None of the above.
10. If we choose Prim's Algorithm for uniquely weighted spanning tree instead of Kruskal's Algorithm, then
A.  we'll get a different spanning tree. B.  we'll get the same spanning tree. C.  spanning will have less edges. D.  spanning will not cover all vertices.
DATA STRUCTURE TOPICS