DSA Quiz 2 Set 1

Consider the following sequence of operations on an empty stack.

push(54); push(52); pop(); push(55); push(70); s=pop(). Consider the following sequence of operations on an empty queue. enqueue(21); enqueue(24);dequeue(); enqueue(28); enqueue(32); q=dequeue(). The value of s + q is

• 86

• 68

• 24

• 94

Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute M1 × M2 will be

• best if A is in row-major, and B is in column-major order.

• best if both are in row-major order.

• independent of the storage scheme.

• best if both are in column-major order

Predict the output of the following C code.

int main(){

char c = 011;

printf("%d",c);

return 0;

}

• 11

• 10

• 9

• None of the other.

In how many ways you can insert 1,2,3,4,5,6,7,8 in an empty binary search tree, such that the resulting tree has height 7? (height of the tree with a single node is 0.)

• 2

• 4

• 64

• None of the other.

In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The number of leaf nodes in the binary tree is –

• 10

• 11

• 12

• 15

Which of the following best fits for forward and back buttons in web browsers?

• Stack

• Queue

• Binary Search Tree

• None of these

For a binary tree with breadth first and preorder traversals ’a, b, e, c, d, f, g, h’ and ‘a, b, c, d, e, f, h,g’ respectively, the postorder traversal would be:

• c d b h f g e a

• c b d a h f g e

• c d b h a f e g

• c d b h f g a e

The inorder and postorder traversal of a binary tree are ’d b e a f c g’ and ’d e b f g c a’, respectively.

(a) Is the binary tree a complete binary tree?

(b) Identify the root node.

(c) What is the preorder traversal of the binary tree?

• (a) No

  (b) a

  (c) Preorder : a b c d e f g

• (a) Yes

  (b) a

  (c) Preorder : a b d e c f g

• (a) Yes

  (b) d

  (c) Preorder : a b d e c f g

• (a) Yes

  (b) d

  (c) Preorder : a b d e c g f

Consider a hash table of size 8, starting with the index = 0, and a hash function: (4x+4) Assuming the hash table is initially empty, what would be the order of the contents of this table when the sequence: 1, 4, 5, 9, 10, 8 is inserted using closed hashing?

Note : Closed hashing is nothing but open addressing and here it is used with linear probing.

• 1, 5, 9,_ , 4, 10, 8,_ ,_

• 8, 1, 10, _, 4, 5, _,_, 9

• 1, 9, _, 5, 4, 10, 8, _,_,

• None of the above.

Consider a circular array based queue ’Q’ that is capable of holding 12 elements. What would the element at index 3 be after execution of the following code snippet on the array? Assume Q is initially empty and its indices run from 0 to 11.

for(i=1; i != 10; i++)

q.enqueue(i);

for(i=1; i != 6; i++)

q.dequeue();

q.enqueue(q.dequeue());

• 6

• 5

• 4

• 3