Welcome to Data Structure Quiz, Randomly Selected !!

Question 1. Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always true?

LASTIN = LASTPOST

LASTIN = LASTPRE

LASTPRE = LASTPOST

none of the above

Question 2. An undirected graph G has n nodes. Its adjacency matrix is given by an n * n square matrix whose (i) diagonal elements are 0's and (ii) non-diagonal elements are 1's. which one of the following is TRUE?

Graph G has no minimum spanning tree (MST)

Graph G has a unique MST of cost n-1

Graph G has multiple distinct MSTs, each of cost n-1

Graph G has multiple spanning trees of different costs

Question 3. The maximum number of binary trees that can be formed with three unlabeled nodes is:

1

5

4

3

Question 4. A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.
hash_table
Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

46, 42, 34, 52, 23, 33

34, 42, 23, 52, 33, 46

46, 34, 42, 23, 52, 33

42, 46, 33, 23, 34, 52

Question 5. Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely
i) preorder and postorder
ii) inorder and postorder
iii) preorder and inorder
iv) level order and postorder

(i) only

(ii), (iii)

(iii) only

(iv) only

Question 6. An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?

At least 2n - c comparisons, for some constant c, are needed.

At most 1.5n - 2 comparisons are needed.

At least nLog2n comparisons are needed.

none of the above

Question 7. How many undirected graphs (not necessarily connected) can be constructed out of a given set V= {V 1, V 2, ... V n} of n vertices

n(n-l)/2

2^n

n!

2^(n(n-1)/2)

Question 8. Which of the following sorting algorithms has the lowest worst-case complexity?

Merge sort

Bubble sort

Quick sort

Selection sort

Question 9. An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 , .. vn. Two nodes vi , vj are connected if and only if 0 < |i - j| <= 2. Each edge (vi, vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below
Graph
What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?

1/12(11n^2 - 5n)

n^2 - n + 1

6n - 11

2n + 1

Question 10. The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

n

n^2

nlogn

n(log^2)n