101.  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 
a.  (i) only 
b.  (ii), (iii) 
c.  (iii) only 
d.  (iv) only 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).(ii), (iii)

102.  A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time? 
a.  rear node 
b.  front node 
c.  not possible with a single pointer 
d.  node next to front 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).rear node

103.  The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a Max Heap. The resultant Max Heap is. 
a.  a 
b.  b 
c.  c 
d.  d 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).a

104.  Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each array can be stored either in rowmajor or columnmajor order in contiguous memory locations. The time complexity of an algorithm to compute M1 × M2 will be 
a.  best if A is in rowmajor, and B is in column major order 
b.  best if both are in rowmajor order 
c.  best if both are in columnmajor order 
d.  independent of the storage scheme 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).independent of the storage scheme

105.  Consider the following C program
main() { int x, y, m, n; scanf ("%d %d", &x, &y); /* Assume x > 0 and y > 0 */ m = x; n = y; while (m! = n) { if (m > n) m = m  n; else n = n  m; } print f ("% d", n); } The program computes 
a.  x ÷ y using repeated subtraction 
b.  x mod y using repeated subtraction 
c.  the greatest common divisor of x and y 
d.  the least common multiple of x and y 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).the greatest common divisor of x and y

106.  What does the following algorithm approximate?
x = m; y = 1; while (x  y > e) { x = (x + y)/2; y = m/x; } print(x); (Assume m > 1, e > 0). 
a.  log m 
b.  m^2 
c.  m^1/2 
d.  m^1/3 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).m^1/2

107.  Consider the following C program segment
struct CellNode { struct CelINode *leftchild; int element; struct CelINode *rightChild; } int Dosomething(struct CelINode *ptr) { int value = 0; if (ptr != NULL) { if (ptr>leftChild != NULL) value = 1 + DoSomething(ptr>leftChild); if (ptr>rightChild != NULL) value = max(value, 1 + DoSomething(ptr>rightChild)); } return (value); } The value returned by the function DoSomething when a pointer to the root of a nonempty tree is passed as argument is 
a.  The number of leaf nodes in the tree 
b.  The number of nodes in the tree 
c.  The number of internal nodes in the tree 
d.  The height of the tree 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).The height of the tree

108.  Suppose we run Dijkstra’s single source shortestpath algorithm on the following edge weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized? 
a.  P, Q, R, S, T, U 
b.  P, Q, R, U, S, T 
c.  P, Q, R, U, T, S 
d.  P, Q, T, R, U, S 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).P, Q, R, U, S, T

109.  The order of an internal node in a B+ tree index is the maximum number of children it can have. Suppose that a child pointer takes 6 bytes, the search field value takes 14 bytes, and the block size is 512 bytes. What is the order of the internal node? 
a.  24 
b.  25 
c.  26 
d.  27 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).26

110.  Let A[1, ..., n] be an array storing a bit (1 or 0) at each location, and f(m) is a unction whose time complexity is θ(m). Consider the following program fragment written in a C like language:
counter = 0; for (i = 1; i < = n; i++) { if (A[i] == 1) counter++; else { f(counter); counter = 0; } } The complexity of this program fragment is 
a.  Ω(n^2) 
b.  Ω(nlog n) and O(n^2) 
c.  θ(n) 
d.  O(n) 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).θ(n)
