Data structure Quiz - Solved

1. Which among the following is not a property of the binary tree
   1. There is a specially designated node called the root
   2. The rest of the nodes could be partitioned into t-disjoint sets (t>=0)
   3. Any node should be reachable form anywhere in the tree
   4. At most one cycle could be present in the
2. The maximum no of nodes in a binary tree of depth k is

a. 2^k-1 b. 2^(k+1) c. 2^k -1 d. 2^{(k+1) – 1}

 

 

 

1. A binary tree with k node ( k>1) has ……..Null pointers

1. An inorder and postorder traversal of a binary tree was claimed to yield the

Following sequence

Inorder: HAT GLOVE SOCKS SCARF GLASSES

Postorder: GLOVE SCARF HAT GLASSES SOCKS

a. HAT is the root of the binary tree

b. SOCKS is the root of the binary tree

c. The tree is skewed binary tree

d. The traversals are incorrect

 

1. For a non-empty binary tree T, if n0 is no of nodes with degree 0 and n2 is no of nodes with degree ,then

a. n0 =n2 b. n0=n2+1 c. n0+1=n2 d.n0<n2

 

1. Run time of the Kruskal algotithm is

a. O(ElogE) b. O(VlogE) c. O(ElogV) d.O(V+E)

 

1. Data structure used by Prim’s method is

a. Linked list b. Stack c. Priority Queue d. None

 

1. No of entries in the adjacency matrix of an undirected graph is

a. │E│ b.2│E│ c. │V│+│E│ d. none of these

 

1. No of edges in a n-vertex complete graph is given by

a. n² b. n(n -1)/2 c. n d. n-1

1. Pick the odd one put

a. Dijikstra’s algo b. Prim’s Algo c. Huffman code d. Inorder traversal of tree

1. Threaded representation without the header node has…….Null pointers

a. 2 b. 4 c.0 d. none of these

1. Implicit binary tree representation suits

a. strictly binary tree b. 2- Tree c. extended tree d. almost complete binary tree

1. A node with degree 0 in a graph is called ……………node

1. A graph has edges e1=(u,u), e2=(u,v), e3=(u,v) . This graph can be named as

…………………… graph.

1. In order traversal on a binary search tree yields keys in …………order.

 

1. Tree based sorting technique has the complexity

a. O(n²) b. O(n) c. O(nlogn) d. none of these

 

17. Which of the following pair of traversals yields the unique binary tree

a. Inorder & Postorder

b. Inorder & Preorder

c. Preorder and Postorder

 

18. A connected graph G=(V,E) without any cycle contains………edges.

 

19. The search complexity of a B-Tree of order m with n keys is

a. log_m n b.log_n m c. log₂ m d. log₂ n

 

20.A graph G=(V,E) has a spanning tree T=(V,E) with │E │ = ? …………..

 

 

ANSWERS

1. D
2. B
3. K+1
4. B
5. B
6. A
7. C
8. B
9. B
10. D
11. A
12. D
13. ISOLATED
14. MULTIGRAPH
15. ASCENDING
16. C
17. B
18. |V-1|
19. A
20. |V-1|

 

 

SHARE THIS