1
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 follow...
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. Assumin...
3
Consider the queues $Q_{1}$ containing four elements and $Q_{2}$ containing none (shown as the $\textsf{Initial State}$ in the figure). The only operations allowed on the...
4
​​​​​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...
5
Consider a complete binary tree with $7$ nodes. Let $A$ denote the set of first $3$ elements obtained by performing Breadth-First Search $\text{(BFS)}$ starting from the ...
6
​​​​​Let $P$ be an array containing $n$ integers. Let $t$ be the lowest upper bound on the number of comparisons of the array elements, required to find the min...
7
A binary search tree $T$ contains $n$ distinct elements. What is the time complexity of picking an element in $T$ that is smaller than the maximum element in $T$? $\Theta... 3 answers 8 Consider the following sequence of operations on an empty stack.$$\textsf{push}(54);\textsf{push}(52);\textsf{pop}();\textsf{push}(55);\textsf{push}(62);\textsf{s}=\texts... 2 answers 9 An$articulationpoint$in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected component... 4 answers 10 The preorder traversal of a binary search tree is$15, 10, 12, 11, 20, 18, 16, 19$. Which one of the following is the postorder traversal of the tree?$10,11,12,15,16,18,...
11
What is the worst case time complexity of inserting $n^{2}$ elements into an AVL-tree with $n$ elements initially? $\Theta (n^{4})$ $\Theta (n^{2})$ $\Theta (n^{2}\log n)... 9 answers 12 What is the worst case time complexity of inserting$n$elements into an empty linked list, if the linked list needs to be maintained in sorted order?$\Theta(n)\Theta...
13
In a balanced binary search tree with $n$ elements, what is the worst case time complexity of reporting all elements in range $[a,b]$? Assume that the number of reported ...
14
Consider the array representation of a binary min-heap containing $1023$ elements. The minimum number of comparisons required to find the maximum in the heap is _________...
15
Consider the following statements: The smallest element in a max-heap is always at a leaf node The second largest element in a max-heap is always a child of a root node A...
16
Let $T$ be a full binary tree with $8$ leaves. (A full binary tree has every level full.) Suppose two leaves $a$ and $b$ of $T$ are chosen uniformly and independently at ...
The number of possible min-heaps containing each value from $\{1,2,3,4,5,6,7\}$ exactly once is _______
The postorder traversal of a binary tree is $\text{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 t...
A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let $n$ denote the number of node...