### SET 2

Question 1

**Consider rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of sub trees having exactly 4 nodes is O(n**^{a} log n ^{b}). Then the value of a + 10b is_______

Answer Discuss it!

.

Correct answer is :1

Solution :

int print_subtrees_size_4(node *n)

{

int size=0;

if(node==null)

return 0;

size=print_subtrees_size_4(node->left)+print_subtrees_size_4(node->right)+1;

if(size==4)

printf("this is a subtree of size 4");

return size;

}

The above function on taking input the root of a binary tree prints all the subtrees of size 4 in O(n) time

Question 2

**A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:**

A : 10, 8, 7, 3, 2, 1, 5

B : 10, 8, 7, 2, 3, 1, 5

C : 10, 8, 7, 1, 2, 3, 5

D : 10, 8, 7, 5, 3, 2, 1

Answer Discuss it!

.

Correct answer is :A

Question 3

**Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.**

Answer Discuss it!

.

Correct answer is :358

Solution :

The implementation of optimal algorithm for merging sequences is as follows. In it total number of comparisons is (44-1)+(94-1)+(65-1)+(159-1) = 358

Question 4

**Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___.**

Answer Discuss it!

.

Correct answer is :6

Question 5

**Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?**

A : A queue cannot be implemented using this stack.

B : A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of

C : A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a

D : A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.

Answer Discuss it!

.

Correct answer is :C

Solution :

Option (a) is false because queue can be implemented by using the modified stack as by reversing the stack. LIFO will become FIFO. Implementation of ENQUEUE & DEQUEUE takes four sequence of instructions as follows:

1 .ENQUEUE : Reverse , Push , Reverse and DEQUEUE : Pop.

2.Enqueue: Push and Dequeue: Reverse, POP, Reverse

Question 6

**Consider the following rooted tree with the vertex labelled P as the root**

The order in which the nodes are visited during an in-order traversal of the tree is

A : SQPTRWUV

B : SQPTUWRV

C : SQPTWUVR

D : SQPTRUWV

Answer Discuss it!

.

Correct answer is :A

Solution :

The In order Traversal of Ternary Tree is done as follows:

Left -> Root ->Middle -> Right

So the nodes are visited in SQPTRWUV order.

Question 7

**Consider the pseudocode given below. The function Dosomething () takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.**

typedef struct treeNode* treeptr;
struct treeNode
{
treeptr leftMostChild, rightSibling;
};
int DoSomething (treeptr tree)
{
int value=0;
if (tree != NULL)
{
if (tree->leftMostChild == NULL)
value = 1;
else
value = DoSomething(tree->leftMostChild);
value = value + DoSomething(tree->rightSibling);
}
return(value);
}

A : number of internal nodes in the tree.

B : height of the tree.

C : number of nodes without a right sibling in the tree.

D : number of leaf nodes in the tree.

Answer Discuss it!

.

Correct answer is :D

Solution :

The key to solving such questions is to understand or detect where/by what condition the value (or the counter) is getting incremented each time.

Here, that condition is if (tree->leftMostchild == Null)

Which means if there is no left most child of the tree (or the sub-tree or the current nodeas called in recursion)

Which means there is no child to that particular node (since if there is no left most child, there is no child at all).

Which means the node under consideration is a leaf node

Question 1

^{a}log n

^{b}). Then the value of a + 10b is_______

.

Correct answer is :1

Solution :

int print_subtrees_size_4(node *n)

{

int size=0;

if(node==null)

return 0;

size=print_subtrees_size_4(node->left)+print_subtrees_size_4(node->right)+1;

if(size==4)

printf("this is a subtree of size 4");

return size;

}

The above function on taking input the root of a binary tree prints all the subtrees of size 4 in O(n) time

Question 2

.

Correct answer is :A

Question 3

.

Correct answer is :358

Solution :

The implementation of optimal algorithm for merging sequences is as follows. In it total number of comparisons is (44-1)+(94-1)+(65-1)+(159-1) = 358

Question 4

.

Correct answer is :6

Question 5

.

Correct answer is :C

Solution :

Option (a) is false because queue can be implemented by using the modified stack as by reversing the stack. LIFO will become FIFO. Implementation of ENQUEUE & DEQUEUE takes four sequence of instructions as follows:

1 .ENQUEUE : Reverse , Push , Reverse and DEQUEUE : Pop.

2.Enqueue: Push and Dequeue: Reverse, POP, Reverse

Question 6

The order in which the nodes are visited during an in-order traversal of the tree is

.

Correct answer is :A

Solution :

The In order Traversal of Ternary Tree is done as follows:

Left -> Root ->Middle -> Right

So the nodes are visited in SQPTRWUV order.

Question 7

typedef struct treeNode* treeptr; struct treeNode { treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr tree) { int value=0; if (tree != NULL) { if (tree->leftMostChild == NULL) value = 1; else value = DoSomething(tree->leftMostChild); value = value + DoSomething(tree->rightSibling); } return(value); }

.

Correct answer is :D

Solution :

The key to solving such questions is to understand or detect where/by what condition the value (or the counter) is getting incremented each time.

Here, that condition is if (tree->leftMostchild == Null)

Which means if there is no left most child of the tree (or the sub-tree or the current nodeas called in recursion)

Which means there is no child to that particular node (since if there is no left most child, there is no child at all).

Which means the node under consideration is a leaf node