dsa-11.7.24 an

1.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.

• 1. 8, , , , , _, 10

• 2. 1, 8, 10, , , _, 3

• 1. 1, , , , , _,3

• 1. 1, 10, 8, , , _, 3

2.What maximum difference in heights between the leafs of a AVL tree is possible?

• 1. log(n) where n is the number of nodes

• 1. n where n is the number of nodes

• 1. 0 or 1

• 1. Atmost 1

3.We are given a set of n distinct elements and an unlabelled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

• 1. 0

• 1. 1

• 1. n!

• 1. 1/n+1

4.If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m,

where n ≤ m, the expected number of collisions involving a particular key x is less than _______.

• 1. 1

• 1. 1/n

• 1. 1/m

• 1. n/m

5.Consider the below left-left rotation pseudo code where the node contains value pointers to left, right child nodes and a height value and Height() function returns height value stored at a particular node.

avltree leftrotation(avltreenode z): avltreenode w =x-left x-left=w-right w-right=x x-height=max(Height(x-left),Height(x-right))+1 w-height=max(missing)+1 return w

What is missing?

• 1. Height(w-left), x-height

• 1. Height(w-right), x-height

• 1. Height(w-left), x

• 1. Height(w-left)

6.We are given a set of n distinct elements and an unlabelled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

• 1. 0

• 1. 1

• 1. n!

• 1. (1/(n+1)).2nCn

7.What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.

• 1. 2

• 1. 3

• 1. 4

• 5

8.What output does the below pseudo code produces?

1. Tree_node function(Tree_node x)  

2. {  

3. Tree_node y = x.left;  

4. x.left = y.right;  

5. y.right = x;  

6. return y;  

7. }  

• 1. right rotation of subtree

• 1. left rotation of subtree

• 1. zig-zag operation

• 1. zig-zig operation

9.What does the following piece of code do?

1. public void func(Tree root)  

2. {  

3. func(root.left());  

4. func(root.right());  

5. System.out.println(root.data());  

6. }  

• 1. Preorder traversal

• 1. Inorder traversal

• 1. Postorder traversal

• 1. Level order traversal

10.Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

• 1. h(i)=i*i mod 10

• 1. h(i)=i*i*i mod 10

• 1. h(i)=(11∗i*i) mod 10

• 1. h(i)=(12∗i) mod 10