Welcome to Data Structure Quiz, Advanced Level !!

Question 1. A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below:
    10, 8, 5, 3, 2
Two new elements "1" and "7" are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

10, 8, 7, 5, 3, 2, 1

10, 8, 7, 2, 3, 1, 5

10, 8, 7, 1, 2, 3, 5

10, 8, 7, 3, 2, 1, 5

Question 2. 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 3. 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 4. Consider the following functions:
f(n) = 2^n
g(n) = n!
h(n) = n^logn
Which of the following statements about the asymptotic behavior of f(n), g(n), and h(n) is true?

f(n) = O(g(n)); g(n) = O(h(n))

f(n) = Omega(g(n)); g(n) = O(h(n))

g(n) = O(f(n)); h(n) = O(f(n))

h(n) = O(f(n)); g(n) = Omega(f(n))

Question 5. Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that '_' denotes an empty location in the table.

8, _, _, _, _, _, 10

1, 8, 10, _, _, _, 3

1, _, _, _, _, _,3

1, 10, 8, _, _, _, 3

Question 6. A set X can be represented by an array x[n] as follows:
array pic
Consider the following algorithm in which x,y and z are Boolean arrays of size n:
algorithm zzz(x[] , y[], z []) 
{ 
    int i; 
    for (i=O; i<n;   ++i) 
    z[i] = (x[i] ^ ~y[i]) U (~x[i] ^ y[i]) 
}

The set Z computed by the algorithm is:

(X Intersection Y)

(X Union Y)

(X-Y) Intersection (Y-X)

(X-Y) Union (Y-X)

Question 7. Consider the following recurrence:
recurrence
Which one of the following is true?

T(n) = Theta(loglogn)

T(n) = Theta(logn)

T(n) = Theta(sqrt(n))

T(n) = Theta(n)

Question 8. 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 9. In the following C function, let n >= m.
 
int gcd(n,m) 
{ 
      if (n%m ==0) return m;  
      n = n%m; 
      return gcd(m,n); 
} 

How many recursive calls are made by this function?

Theta(logn)

Omega(n)

Theta(loglogn)

Theta(sqrt(n))

Question 10. A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl < top 2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for "stack full" is

(top1 = MAXSIZE/2) and (top2 = MAXSIZE/2 + 1)

top1 + top2 = MAXSIZE

(top1= MAXSIZE/2) or (top2 = MAXSIZE)

top1= top2 -1