Your Answer : (Not Answered)

Correct Answer : D

The odd one is Tower of Hanoi.

A priority queue, a circular queue and a deque (double-ended queue) are all queue data structures: variations on storing elements and removing them in a defined order from the ends or by priority.

The Tower of Hanoi is a problem, a puzzle of moving discs between pegs, usually solved by recursion and often used to illustrate stacks and recursion. It is not a kind of queue, so it does not belong with the other three.

Your Answer : (Not Answered)

Correct Answer : B

A circular linked list is used in allocating CPU to resources (processes), as in round-robin scheduling.

In round-robin scheduling the ready processes are kept in a circular list. The scheduler gives the CPU to one process for a time slice and then simply moves to the next node; after the last process it comes back to the first without any special case, which is exactly what a circular list provides.

Undo operations, recursive function calls and expression evaluation are all classic uses of a stack, since each needs last-in, first-out order, not a circular list.

Your Answer : (Not Answered)

Correct Answer : C

The prefix form is * - A / B C - / A K L.

Convert each part, giving / priority over -:

• A - B / C: B / C becomes / B C, so the whole is - A / B C.
• A / K - L: A / K becomes / A K, so the whole is - / A K L.

The two bracketed parts are multiplied, so * goes in front: * - A / B C - / A K L.

The option A B C A K L * - / - / is a postfix-style string with the operators gathered at the end, and the other two options place the operators in an order that does not reproduce the expression when read back.

Your Answer : (Not Answered)

Correct Answer : C

The stack holds at most 3 parentheses.

The algorithm pushes each '(' and pops one for each ')'. The maximum stack size is the deepest nesting. For ( ( ) ( ( ) ) ( ( ) ) ): the outer '(' gives depth 1, the next pairs reach depth 2, and the inner '(' of each '( ( ) )' group reaches depth 3. The stack never holds more than three at once.

12 is the total number of characters, and 6 the number of '(' symbols, neither of which is ever on the stack at the same time. 4 would need one more level of nesting.

Your Answer : (Not Answered)

Correct Answer : A

Bubble sort is O(n) in the best case and O(\(n^{2}\)) in the worst case.

Bubble sort with the usual 'swapped' flag stops as soon as a pass makes no swaps. On an already sorted array the first pass of n-1 comparisons makes no swaps, so the best case is O(n). On a reverse-sorted array every pass swaps, and about n(n-1)/2 comparisons and swaps are needed, so the worst case is O(\(n^{2}\)).

O(n log n) is the complexity of merge sort and of heap sort, not of bubble sort, which rules out options B, C and D.

Your Answer : (Not Answered)

Correct Answer : D

This data structure is a deque.

A deque (double-ended queue) allows insertion and deletion at both the front and the rear, but not in the middle. It generalises both the stack and the queue.

A stack allows insertion and removal at one end only (last in, first out). A queue inserts at the rear and removes from the front (first in, first out), so each end supports only one operation. A linked list allows insertion and deletion anywhere, including the middle.

Your Answer : (Not Answered)

Correct Answer : C

The New-order traversal is - + 1 * 7 6 ^ 2 - 5 * 4 3.

Build the tree from the postfix expression 3 4 * 5 - 2 ^ 6 7 * 1 + -: it is ((3 * 4) - 5) ^ 2 - ((6 * 7) + 1). The root is the last operator, -, with left subtree ((3*4)-5) ^ 2 and right subtree (6*7)+1.

New-order visits root, then right subtree, then left subtree, recursively:

• Root: -
• Right subtree (6*7)+1: +, then its right child 1, then its left subtree * 7 6 (root, right, left).
• Left subtree: ^, then its right child 2, then its left subtree -, 5, then * 4 3.

This gives - + 1 * 7 6 ^ 2 - 5 * 4 3. New-order is exactly the reverse of postfix order, which is a quick check: reverse 3 4 * 5 - 2 ^ 6 7 * 1 + - and you get the same string. The option with * 6 7 and * 3 4 visits the left child before the right in the inner subtrees, and the other two options start with the wrong node.

Your Answer : (Not Answered)

Correct Answer : C

Floyd-Warshall is based on the Dynamic Programming paradigm.

It computes \(d_{k}(i, j)\), the shortest path from \(i\) to \(j\) using only the first \(k\) vertices as intermediates, from the previous table:

\[ \begin{aligned} d_{k}(i,j) = \min(&d_{k-1}(i,j), \\ &d_{k-1}(i,k) + d_{k-1}(k,j)) \end{aligned} \]

This builds the solution from overlapping subproblems stored in a table, the defining feature of dynamic programming, and runs in \(O(n^{3})\).

It is not greedy: Dijkstra’s algorithm is the greedy shortest-path method, fixing one vertex at a time. It is not divide-and-conquer, which splits a problem into independent subproblems; the subproblems here overlap and are reused.

Your Answer : (Not Answered)

Correct Answer : C

The best strategy is the universal hashing method.

Any single fixed hash function can be defeated: an adversary who knows it can choose k keys that all hash to the same slot, giving \(\Theta(k)\) time per lookup. Universal hashing chooses the hash function at random, at run time, from a family in which any two distinct keys collide with probability at most 1/m. Since the adversary picks keys without knowing which function was drawn, the expected number of collisions for any key is at most about k/m, whatever keys were chosen.

The division method and the multiplication method are both fixed, deterministic functions, so each can be attacked as above. Switching between them on whether k is prime is still deterministic, and the adversary controls the keys anyway.

Your Answer : (Not Answered)

Correct Answer : A

Only statement I must be true.

In a depth first search of an undirected graph, when an edge (u, v) is examined from u, either v is unvisited, making (u, v) a tree edge, or v was visited and is still active, making it an ancestor. So every non-tree edge joins a vertex to one of its ancestors, and there are no cross edges with respect to the DFS tree.

Statement II fails. In a BFS tree the depths of the two ends of an edge differ by at most 1, but they can be equal. In a triangle with BFS from one vertex, the other two vertices are both at depth 1 and are joined by an edge, so \(|i - j| = 0\).

That rules out 'II only' and 'Both I and II', and statement I being true rules out 'Neither I nor II'.

Your Answer : (Not Answered)

Correct Answer : A

The fastest algorithm runs in Θ(m + n).

In a directed acyclic graph, single-source shortest paths need no priority queue. Sort the vertices topologically (O(m + n) with depth-first search), then relax the outgoing edges of each vertex in that order. When a vertex is processed, every path into it has already been considered, because all its predecessors come earlier in the order. Each edge is relaxed once, so the total is Θ(m + n), and this works with negative edge weights too.

Θ(m + n log n) is Dijkstra's algorithm with a Fibonacci heap, which ignores the acyclic structure and fails with negative weights. Θ(nm) is Bellman-Ford, for general graphs with negative edges. Θ(n³) is Floyd-Warshall, which computes all pairs.

Your Answer : (Not Answered)

Correct Answer : A

The fastest algorithm takes Θ(n) in the worst case.

Write d_i = A[i+1] - A[i] for i = 1, ..., n - 1. The condition says d_i > d_j whenever i > j: the sequence of differences is strictly increasing. Strict increase of a whole sequence is equivalent to strict increase between each pair of neighbours, d_i+1 > d_i, because the relation > is transitive. So one pass computing the n - 1 differences and comparing neighbours suffices: O(n).

No algorithm can do better, since changing any single element of A can break the condition, so every element must be read: Ω(n). Checking all pairs (i, j) would take Θ(n²), and Θ(log n) is impossible for the same reason.

Your Answer : (Not Answered)

Correct Answer : C

The loop invariant is \(X^{Y} = \mathrm{res} * a^{b}\).

Check that it holds at the start and is preserved by each branch:

• Initially \(\mathrm{res} = 1\), \(a = X\), \(b = Y\), so \(\mathrm{res} \cdot a^{b} = X^{Y}\).
• If \(b\) is even, \(a\) becomes \(a^{2}\) and \(b\) becomes \(b/2\): \((a^{2})^{b/2} = a^{b}\), unchanged.
• If \(b\) is odd, \(\mathrm{res}\) becomes \(\mathrm{res} \cdot a\) and \(b\) becomes \(b - 1\): \(\mathrm{res} \cdot a \cdot a^{b-1} = \mathrm{res} \cdot a^{b}\), unchanged.

When the loop ends, \(b = 0\), so \(X^{Y} = \mathrm{res}\), which is what the function returns.

\(X^{Y} = a^{b}\) fails after the first odd step, when part of the power has moved into \(\mathrm{res}\). \(X^{Y} = (\mathrm{res} * a)^{b}\) raises \(\mathrm{res}\) to the power \(b\) as well, and \((\mathrm{res} * a)^{Y} = (\mathrm{res} * X)^{b}\) holds at the start but fails after the first even step, when \(a\) becomes \(X^{2}\) while \(b\) halves.

Your Answer : (Not Answered)

Correct Answer : B

Both Extract-Max(A) and Insert(A,key) run in \(O(\log(n))\).

Extract-Max reads the maximum at the root in constant time, but it must also delete it: the last element is moved to the root and sifted down, swapping with the larger child until the heap property holds again. That can take one swap per level, and a heap of n elements has about \(\log_{2} n\) levels.

Insert places the new key in the next free leaf and sifts it up towards the root, again at most one swap per level, \(O(\log(n))\).

The options with Extract-Max in \(O(1)\) confuse finding the maximum with extracting it while keeping a valid heap. Insert is never \(O(n)\) in a binary heap, and neither operation is \(O(1)\) in the worst case.

Your Answer : (Not Answered)

Correct Answer : B

The max-heap is 23, 17, 14, 7, 13, 10, 1, 5, 6, 12.

In an array heap the children of \(A[i]\) are \(A[2i]\) and \(A[2i+1]\), and every parent must be at least as large as its children. For this sequence:

• A[1] = 23: children 17 and 14
• A[2] = 17: children 7 and 13
• A[3] = 14: children 10 and 1
• A[4] = 7: children 5 and 6
• A[5] = 13: child 12

Every check passes. The others each break the rule once: in the first sequence A[3] = 10 has the child A[6] = 14; in the third A[5] = 13 has the child A[10] = 15; and in the fourth A[4] = 1 has the children 12 and 7.

Your Answer : (Not Answered)

Correct Answer : D

The first three elements are 131, 111, 90.

Heapify here builds a max-heap bottom-up, sifting down from the last internal node (index 4, value 111) to the root:

• 111 already exceeds its child 93.
• 11 swaps with its larger child 131.
• 90 stays above 75 and 33.
• 101 swaps with 131, then stays above 11 and 44.
• 82 swaps with 131, then with 111, then with 93.

The result is [131, 111, 90, 101, 93, 75, 33, 11, 44, 82]. The root must be the maximum, 131, which rules out the options starting with 82. Option C puts 11 at index 1, above larger elements such as 101, which a max-heap forbids.

Your Answer : (Not Answered)

Correct Answer : D

SLLdel is \(O(n)\) and DLLdel is \(O(1)\).

To unlink a node from a singly-linked list, the previous node's next pointer must be changed, and a singly-linked node has no pointer back to its predecessor. SLLdel must therefore walk from the head to find it, which takes up to n steps when the node is near the end. (Copying the next node's data into the node does not help in the worst case, because it fails for the last node.)

In a doubly-linked list the node carries a prev pointer, so DLLdel can reset the predecessor's next pointer and the successor's prev pointer directly, a constant number of steps.

So 'SLLdel O(1), DLLdel O(n)' is backwards, 'both O(1)' ignores the search, and no list operation here is logarithmic, which rules out \(O(\log(n))\).

Your Answer : (Not Answered)

Correct Answer : C

The total time is \(O(N^{2})\).

Cost each batch on a sorted doubly linked list:

• \(\Theta(N)\) deletes: with a pointer to the node, each is \(O(1)\), so \(O(N)\) in all.
• \(O(\log N)\) inserts: finding the position in a sorted list takes \(O(N)\) each, so \(O(N\log N)\).
• \(O(\log N)\) finds: a linear search each, \(O(N\log N)\).
• \(\Theta(N)\) decrease-keys: the node is reached by pointer, but its new smaller key may belong much further forward, and moving it there takes \(O(N)\) each, so \(O(N^{2})\).

The decrease-keys dominate, giving \(O(N^{2})\). \(O(N)\) ignores the cost of repositioning, \(O(\log^{2}N)\) assumes logarithmic operations a linked list cannot provide, and \(\Theta(N^{2}\log N)\) overstates the bound.

Your Answer : (Not Answered)

Correct Answer : B

The correct replacements are E1: head->next == NULL and E2: 1 + getListSize(head->next).

The list is non-empty, so the base case is the last node: when head->next is NULL, the list from here has exactly 1 node. Otherwise the size is this node plus the size of the rest of the list, 1 + getListSize(head->next).

Calling getListSize(head) again, as in two of the options, recurses on the same node forever. Testing head == NULL with head->next in the recursion reaches the NULL after the last node and returns 1 there, so it counts one node too many.

Your Answer : (Not Answered)

Correct Answer : D

The missing condition is b != a.

The function keeps two candidate positions, a from the left and b from the right. At each step it discards the smaller of p[a] and p[b] by moving that index inward, since the smaller one cannot be the maximum. The maximum is always kept between a and b inclusive. The loop must stop when only one candidate remains, that is when a and b meet, and then p[a] is the maximum. So it should run while b != a.

a != n would let a run past b and off the end of the array. b != 0 ignores a and can move b below a. b \(\gt\) (a + 1) stops with two candidates left and returns p[a] without comparing it with p[b], which fails when p[b] is larger, for example for the array {1, 2}.