Question 1 |

Consider the queues Q1 containing four elements and Q2 containing none (shown
as the Initial State in the figure). The only operations allowed on these two queues are Enqueue(Q,element) and Dequeue(Q). The minimum number of Enqueue operations on Q1 required to place the elements of Q1 in Q2 in reverse
order (shown as the Final State in the figure) without using any additional storage is

4 | |

2 | |

0 | |

1 |

Question 1 Explanation:

Question 2 |

Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index _______.

510 | |

999 | |

509 | |

501 |

Question 2 Explanation:

Question 3 |

Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h_1 and h_2. Further suppose our hashing scheme uses h_1 for the odd keys
and h_2 for the even keys. What is the expected number of keys in a slot?

\frac{m}{n} | |

\frac{n}{m} | |

\frac{2n}{m} | |

\frac{n}{2m} |

Question 3 Explanation:

Question 4 |

Consider the problem of reversing a singly linked list. To take an example, given the linked list below,

the reversed linked list should look like

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?

the reversed linked list should look like

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?

The best algorithm for the problem takes \theta(n) time in the worst case. | |

The best algorithm for the problem takes \theta(n \log n) time in the worst case. | |

The best algorithm for the problem takes \theta(n^2) time in the worst case. | |

It is not possible to reverse a singly linked list in O(1) space. |

Question 4 Explanation:

Question 5 |

Consider the following ANSI C program:

```
#include < stdio.h >
#include < stdlib.h >
struct Node{
int value;
struct Node *next;};
int main( ) {
struct Node *boxE, *head, *boxN; int index=0;
boxE=head= (struct Node *) malloc(sizeof(struct Node));
head -> value = index;
for (index =1; index < = 3; index++){
boxN = (struct Node *) malloc (sizeof(struct Node));
boxE -> next = boxN;
boxN -> value = index;
boxE = boxN; }
for (index=0; index < = 3; index++) {
printf("Value at index %d is %d\n", index, head -> value);
head = head -> next;
printf("Value at index %d is %d\n", index+1, head -> value); } }
```

Which one of the following statements below is correct about the program?Upon execution, the program creates a linked-list of five nodes | |

Upon execution, the program goes into an infinite loop | |

It has a missing returnreturn which will be reported as an error by the compiler | |

It dereferences an uninitialized pointer that may result in a run-time error |

Question 5 Explanation:

Question 6 |

Consider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let B denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root.

The value of |A-B| is _____________

The value of |A-B| is _____________

3 | |

4 | |

1 | |

2 |

Question 6 Explanation:

Question 7 |

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?

\Theta (\sqrt{n}) | |

\Theta ( \log _2 (n)) | |

\Theta ( n^2) | |

\Theta ( n) |

Question 7 Explanation:

Question 8 |

Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H?

\Theta (1) | |

\Theta (\log n) | |

\Theta ( n) | |

\Theta (n \log n) |

Question 8 Explanation:

Question 9 |

Consider a dynamic hashing approach for 4-bit integer keys:

1. There is a main hash table of size 4.

2. The 2 least significant bits of a key is used to index into the main hash table.

3. Initially, the main hash table entries are empty.

4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table. entry is organized as a binary tree that grows on demand.

5. First, the 3rd least significant bit is used to divide the keys into left and right subtrees.

6. To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the 4th least significant bit.

7. A split is done only if it is needed, i.e., only when there is a collision.

Consider the following state of the hash table.

Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?

1. There is a main hash table of size 4.

2. The 2 least significant bits of a key is used to index into the main hash table.

3. Initially, the main hash table entries are empty.

4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table. entry is organized as a binary tree that grows on demand.

5. First, the 3rd least significant bit is used to divide the keys into left and right subtrees.

6. To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the 4th least significant bit.

7. A split is done only if it is needed, i.e., only when there is a collision.

Consider the following state of the hash table.

Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?

5,9,4,13,10,7 | |

9,5,10,6,7,1 | |

10,9,6,7,5,13 | |

9,5,13,6,10,14 |

Question 9 Explanation:

Question 10 |

Consider the following sequence of operations on an empty stack.

push(54); push(52); pop(); push(55); push(62); 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 ___________.

push(54); push(52); pop(); push(55); push(62); 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 ___________.

94 | |

83 | |

79 | |

86 |

Question 10 Explanation:

There are 10 questions to complete.