Data Structures and Algorithms Quiz Part2

Construct a binary search tree by inserting 8, 6, 12, 3, 10, 9 one after another. To make the resulting tree as AVL tree which of the following is required?

• One right rotation only

• One left rotation followed by two right rotations

• One left rotation and one right rotation

• The resulting tree itself is AVL

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

• 9, _, 1, 6, _, _, 4

• 1, _, 6, 9, _, _, 4

• 4, _, 9, 6, _, _, 1

• 1, _, 9, 6, _, _, 4

Consider the following C program where TreeNode represents a node in a binary tree

struct TreeNode

{ struct TreeNode *leftChild;

struct TreeNode *rightChild;

int element; };

int CountNodes(struct TreeNode *t)

{ if((t==NULL)||((t->leftChild==NULL) && (t->rightChild==NULL)))

return 0;

else

{ return 1+CountNodes(t->leftChild)+CountNodes(t->rightChild) } }

The value returned by CountNodes when a pointer to the root of a binary tree is passed as its argument is

• number of nodes

• number of leaf nodes

• number of non leaf nodes

• number of leaf nodes-number of non leaf nodes

How many distinct binary search trees can be created out of 6 distinct keys?

• 7

• 36

• 140

• 132

Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this: 2 5 1 7 9 12 11 10 Which statement is correct?

• The pivot could be either the 7 or the 9.

• The pivot could be the 7, but it is not the 9

• The pivot is not the 7, but it could be the 9

• Neither the 7 nor the 9 is the pivot.

In a complete k-ary tree, every internal node has exactly k children or no child. The number of leaves in such a tree with n internal nodes is:

• nk

• (n - 1) k+ 1

• n( k - 1) + 1

• n(k - 1)

If a node in a Binary search tree has two children, then its inorder predecessor has .........

• No child

• No left child

• No right child

• Two children

Using Bubble sort, the number of interchanges required to sort 5, 1, 6, 2 and 4 in ascending order is...........

• 7

• 5

• 8

• 6

State True or False

Binary search is used for searching in a sorted array

The time complexity of binary search is O(log n)

• True, True

• False, True

• True, false

• False,False

The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is

• 1

• 2

• 3

• 4