DS CCW

What is the output of the following function in which start is pointing to the first node of the following linked list 1->2->3->4->5->6?

void fun(struct node* start)

{

if(start == NULL)

return;

printf("%d ", start->data);

if(start->next != NULL )

fun(start->next->next);

printf("%d ", start->data);

}

• 1 3 5

• 1 2 3 4

• 1 3 4 6

• 2 4 6

Assume that the operators +,-,× are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^,x,+,-. The postfix expression corresponding to the infix expression a+b×c-d^e^f is

• abc×+def^^-

• abc×+de^f^-

• ab+c×d-e^f^

• -+a×bc^^def

What does the following function do for a given binary tree?

int fun(struct node *root)

{

if (root == NULL)

return 0;

if (root->left == NULL && root->right == NULL)

return 0;

return 1 + fun(root->left) + fun(root->right);

}

• Counts leaf nodes

• Counts internal nodes

• Returns height where height is defined as number of edges on the path from root to deepest node

• Return diameter where diameter is number of edges on the longest path between any two nodes.

Following is an incorrect pseudocode for the algorithm which is supposed to determine whether a sequence of parentheses is balanced.

declare a character stack

while ( more input is available)

{

read a character

if ( the character is a '(' )

push it on the stack

else if ( the character is a ')' and the stack is not empty )

pop a character off the stack

else

print "unbalanced" and exit

}

print "balanced"

Which of these unbalanced sequences does the above code think is balanced?

• ((())

• ())((

• (()()))

• (()))()

Suppose a circular queue of capacity (n–1) elements is implemented with an array of n elements. Assume that the insertion and deletion operation are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR=FRONT=0. The conditions to detect queue full and queue empty are

• Full:(REAR+1)modn==FRONT,empty:REAR==FRONT

• Full:(REAR+1)modn==FRONT,empty:(FRONT+1)modn==REAR

• Full:REAR==FRONT,empty:(REAR+1)modn==FRONT

• Full:(FRONT+1)modn==REAR,empty:REAR==FRONT

How many distinct binary search trees can be constructed out of 4 distinct keys?

• 5

• 14

• 24

• 35

A Binary Search Tree is generated by inserting in order of the following integers. 50,15,62,5,20,58,91,3,8,37,60,24 The number of nodes in the left and right subtree of the root respectively is:

• (4,7)

• (7,4)

• (8,3)

• (3,8)

The preorder traversal sequence of a binary search tree is 30,20,10,15,25,23,39,35,42. Which one of the following is the postorder traversal sequence of the same tree?

• 10,20,15,23,25,35,42,39,30

• 15,10,25,23,20,42,35,39,30

• 15,20,10,23,25,42,35,39,30

• 15,10,23,25,20,35,42,39,30

Consider a hash function that distributes keys uniformly. The hashtable size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5.

• 5

• 6

• 7

• 10

Consider the following sequence of nodes for the undirected graph given below.

A Depth First Search started at node a. The nodes are listed in the order they are first visited. Which all of the above are possible outputs?

1. 1. a b e f d g c

2. 2. a b e f c g d

3. 3. a d g e b c f

4. 4. a d b c g e f

• 1 & 3

• 2 & 3

• 2, 3 & 4

• 1, 2 & 3