Question 1 |
Consider a sequence a of elements a_0 = 1, a_1 = 5, a_2 = 7, a_3 = 8, a_4 = 9, \; and \;
a_5 = 2. The following operations are performed on a stack S and a queue Q, both
of which are initially empty.
I: push the elements of a from a_0 to a_5 in that order into S.
II: enqueue the elements of a from a_0 to a_5 in that order into Q.
III: pop an element from S.
IV: dequeue an element from Q.
V: pop an element from S.
VI: dequeue an element from Q.
VII: dequeue an element from Q and push the same element into S.
VIII: Repeat operation VII three times.
IX: pop an element from S.
X: pop an element from S.
The top element of S after executing the above operations is ___.
I: push the elements of a from a_0 to a_5 in that order into S.
II: enqueue the elements of a from a_0 to a_5 in that order into Q.
III: pop an element from S.
IV: dequeue an element from Q.
V: pop an element from S.
VI: dequeue an element from Q.
VII: dequeue an element from Q and push the same element into S.
VIII: Repeat operation VII three times.
IX: pop an element from S.
X: pop an element from S.
The top element of S after executing the above operations is ___.
7 | |
8 | |
9 | |
2 |
Question 1 Explanation:
Question 2 |
Consider the C function foo and the binary tree shown.

When foo is called with a pointer to the root node of the given binary tree, what will it print?
typedef struct node {
int val;
struct node *left, *right;
} node;
int foo(node *p) {
int retval;
if (p == NULL)
return 0;
else {
retval = p->val + foo(p->left) + foo(p->right);
printf("%d ", retval);
return retval;
}
}

When foo is called with a pointer to the root node of the given binary tree, what will it print?
3 8 5 13 11 10 | |
3 5 8 10 11 13 | |
3 8 16 13 24 50 | |
3 16 8 50 24 13 |
Question 2 Explanation:
Question 3 |
Let A be a priority queue for maintaining a set of elements. Suppose A is
implemented using a max-heap data structure. The operation Extract-Max(A)
extracts and deletes the maximum element from A. The operation Insert(A,key)
inserts a new element key in A. The properties of a max-heap are preserved at the
end of each of these operations.
When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?
When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?
Both Extract-Max(A) and Insert(A,key) run in O(1). | |
Both Extract-Max(A) and Insert(A,key) run in O(log(n)). | |
Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(n). | |
Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(log(n)). |
Question 3 Explanation:
Question 4 |
An algorithm has to store several keys generated by an adversary in a hash
table. The adversary is malicious who tries to maximize the number of collisions.
Let k be the number of keys, m be the number of slots in the hash table, and k \gt m.
Which one of the following is the best hashing strategy to counteract the adversary?
Which one of the following is the best hashing strategy to counteract the adversary?
Division method, i.e., use the hash function h(k) = k\; mod \; m | |
Multiplication method, i.e., use the hash function h(k) = \left \lfloor m(kA -\left \lfloor kA \right \rfloor ) \right \rfloor, where
A is a carefully chosen constant. | |
Universal hashing method. | |
If k is a prime number, use Division method. Otherwise, use Multiplication method |
Question 4 Explanation:
Question 5 |
Let SLLdel be a function that deletes a node in a singly-linked list given a pointer
to the node and a pointer to the head of the list. Similarly, let DLLdel be another
function that deletes a node in a doubly-linked list given a pointer to the node and
a pointer to the head of the list.
Let n denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?
Let n denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?
SLLdel is O(1) and DLLdel is O(n) | |
Both SLLdel and DLLdel are O(log(n)) | |
Both SLLdel and DLLdel are O(1) | |
SLLdel is O(n) and DLLdel is O(1) |
Question 5 Explanation:
There are 5 questions to complete.