Exam 2 Flashcards
Consider an abstraction supporting the operations “allocate”, “allocateAny”, and “freeup” in constant time. How does the “allocateAny” operation detect that all items have already been allocated?
The header points at itself
Which of the following may be performed in O(1) worst-case time?
LogicalPredecessor(L, x) on a sorted, doubly linked list
Which binary tree traversal corresponds to the following recursive code?
void traverse(noderef x) {
if (x==null) return;
traverse(x.left);
traverse(x.right);
// process x here }
Postorder
Suppose that only numbers in 1 . . . 100 appear as keys in a binary search tree. While searching for 50, which of the following sequences of keys could not be examined?
10, 40, 70, 30, 50
Which phase of counting sort uses this code?
Slot[0]=0;
for (i=1; i<kl i++)
slot[i]=slot[i-1]+count[i-1];
Third
In a binary search tree, which element does not have a predecessor?
The minimum
Suppose the tree below is a binary search tree whose keys and subtree sizes are NOT SHOWN. Which node will contain the key with rank 10?
C
Why is it common for a circular queue implementation to waste one table element?
To avoid confusing an empty queue with a full queue
Which of the following will NOT BE TRUE regarding the decision tree for QUICKSORT for sorting n input values?
Every path from the root to a leaf will have O(n logn) decisions.
The worst-case number of comparisons for finding the kth largest of n keys using PARTITION is in which asymptotic set?
O(n^2)
If POP is implemented as return stack[–SP], then PUSH of element X is implemented as:
stack[SP++] = X
Which of the following is a longest common subsequence for 0 1 2 0 1 2 and 0 0 1 2 1 2?
0 1 2 1 2
Suppose a value k appears for p entries in the cost function table (C) for an instance of the longest monotonically increasing subsequence problem. Going left-to-right across the corresponding input sequence values (y1), which statement is true?
(Stated formally: For i1 < i2 < . . . < ip, suppose Ci1 = Ci2 = . . . = Cip = k. Which statement is true regarding yi1, yi2, . . ., yip?)
They are strictly decreasing
Based on dictionary search performance alone, the best justification for ordering a linked list is:
Many more misses than hits are expected.
The maximum number of rotations while inserting a key into a red-black tree is:
2
Suppose the tree below is a binary search tree whose keys and subtree sizes are NOT SHOWN. Which node will contain the key with rank 6?
I
For which of the following sorts does the decision tree model not apply?
LSD Radix Sort
In the example of recycling the elements of a list in O(1) time, which situation holds?
The list to be recycled is circular, the garbage list is not
Given a pointer to a node, the worst-case time to delete the node from a singly-linked list with n nodes in ascending order is:
O(n)
Which of the following binary trees has exactly one legal coloring as a red-black tree?
B
What does counting sort count?
The number of occurences for each possible key value
The subset sum problem takes n input values and attempts to find a combination of those values whose sum is m. The worst-case time to extract the solution from the dynamic programming table is:
O(n)
