[modified] Exam-2

Question 1

For which of the following sorts does the decision tree model not apply?
a) insertion
b) LSD radix sort
c) merge-sort
d) quicksort

Answer 1

b) LSD radix sort

Question 2

In the example of recycling the elements of a list in O(1) time, which situation holds?
a) both lists are circular
b) both lists are not circular
c) the list to be recycled is circular, the garbage list is not
d) the garbage list is circular, the list to be recycled is not

Answer 2

c) the list to be recycled is circular, the garbage list is not

Question 3

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:

Answer 3

Θ(n)

Question 4

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?

Answer 4

10, 40, 70, 30, 50

Question 5

What does counting sort count?

Answer 5

the number of occurences for each possible key value

Question 6

The subset sum problem takes n input values and attempts to find a combination of those values whose sum in m. The worst-case time to extract the solution from the dynamic programming table is:

Answer 6

O(n)

Question 7

Which of the following will not be true regarding the decision tree for HEAP-SORT for sorting n input values?
a) every path from the root to a leaf will have O(n log n) decisions
b) the height of the tree is Ω(n log n)
c) there will be a path from the root to a leaf with Ω(n^2) decisions
d) there will be n! leaves

Answer 7

c) there will be a path from the root to a leaf with Ω(n^2) decisions.

Question 8

Suppose a node x in an unbalanced binary search tree has two children, each storing one key. What is the first step to delete x?

Answer 8

find the successor of x

Question 9

If POP is implemented as return stack[SP–], then PUSH of element X is implemented as:

Answer 9

stack[++SP] = X

Question 10

Suppose a (singly) linked list is used to implement a queue. Which of the following is true?
a) like a circular queue, the maximum number of items is determined at initialization
b) the head points to the first element and the tail points to the last element
c) the tail points to the first element and the head points to the last element
d) one node is always wasted

Answer 10

b) the head points to the first element and the tail points to the last element

Question 11

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 }

Answer 11

postorder

Question 12

The purpose of the binary searches used when solving the longest (monotone) increasing subsequence (LIS) problem is:

Answer 12

to determine the longest possible increasing subsequence terminated by a particular input value

Question 13

In a binary search tree, which element does not have a successor?

Answer 13

the maximum

Question 14

The most accurate description of the time to perform a deletion in an unbalanced binary search tree with n keys and height h is:

Answer 14

Θ(h)

Question 15

The time to fill in the dynamic programming matrix when computing the LCS for sequences of lengths m and n is:

Answer 15

O(n)

Question 16

Given a pointer to a node, the worst-case time to delete the node from a doubly-linked list with n nodes in ascending order is:

Answer 16

Θ(1)

Question 17

Suppose that only numbers 1 … 1000 appear as keys in a binary search tree. While searching for 500, which of the following sequences of keys could not be examing?

Answer 17

100, 1000, 200, 800, 300, 900, 500

Question 18

In the example of recycling the elements of a list in O(1) time, which element becomes the first element of the garbage list?

Answer 18

the second element of the circular list

Question 19

Suppose a binary search tree includes each subtree’s size at the subtree’s root. How should the rank for the key stored at the tree’s root be computed?

Answer 19

Add 1 to the subtree size for the subtree to the left of the root

Question 20

Which of the following may be performed in O(1) worst-case time?
a) Search(L, k) on a sorted, singly linked list
b) Search(L, k) on an unsorted, singly linked list
c) LogicalPredecessor(L, x) on a sorted, singly linked list
d) LogicalPredecessor(L, x) on a sorted, doubly linked list

Answer 20

d) LogicalPredecessor(L, x) on a sorted, doubly linked list

Question 21

If POP is implemented as return stack[–SP], then the test for an empty stack is implemented as:

Answer 21

return SP==0

Question 22

The worst-case number of comparisons for finding the kth largest of n keys using PARTITION is in which asymptotic set?

Answer 22

Θ(n^2)

Question 23

Given a pointer to a node, the worst-case time to insert the node into an unsorted, doubly-linked list with n nodes is:

Answer 23

Θ(1)

Question 24

Which binary tree traversal corresponds to the following recursive code?
void traverse(noderef x) {
if (x==null) return;
// process x
traverse(x.left);
traverse(x.right); }

Answer 24

preorder

Question 25

What is the worst-case time to perform MINIMUM(L) for a sorted, doubly-linked list with n nodes?

Answer 25

Θ(1)

Question 26

Free-Response

The asymptotic number of nodes in the decision tree for any key-comparison sorting algorithm for an input sequence with n unique values is:

Answer 26

Θ(2^n)

Question 27

Long Answer

Describe the four phases of counting sort and give the asymptotic complexity for each phase.

Answer 27

1. Clear the count table - one counter for each value in range (i < k) and repeat count[i]=0 [takes Θ(k) time]
2. Pass through input table - add to appropriate counter for each key (i < n) and repeat count[inp[i]]++ [takes Θ(n) time]
3. Determine first slot that will receive a record for each range value. Initialize slot[0]=0 and loop (i < k) and repeat slot[i]=slot[i-1]+count[i-1] [takes Θ(k) time]
4. Copy each record to output, increment index in table from 3rd step (i < n) and repeat out[slot[inp[i]]++]=inp[i] [takes Θ(n) time]

Question 28

Which phase of counting sort uses this code?
slot[0]=0;
for (i=1; i<k; i++)
slot[i]=slot[i-1]+count[i-1];

Answer 28

third

Question 29

In a binary search tree, which element does not have a predecessor?

Answer 29

the minimum

Question 30

Why is it common for a circular queue implementation to waste one table element?

Answer 30

to avoid confusing an empty queue with a full queue

Question 31

Which of the following will not be true regarding the decision tree for QUICKSORT for sorting n input values?
a) there will be n! leaves
b) every path from the root to a leaf will have O(n log n) decisions
c) there will be a path from the root to a leaf with Ω(n^2) decisions
d) the height of the tree is Ω(n log n)

Answer 31

b) every path from the root to a leaf will have O(n log n) decisions

Question 32

If POP is implemented as return stack[–SP], then PUSH of element X is implemented as:

Answer 32

stack[SP++] = X

Question 33

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 (yi), which statement is true?

(Stated formally: For i1 < i2 < … < ip, suppose Ci1 = Ci2 = … = Cip = k. Which statement is true regarding yi1, yi2, …, yip?)

Answer 33

they are strictly decreasing

Question 34

Based on dictionary search performance alone, the best justification for ordering a linked list is:

Answer 34

many more misses than hits are expected

Question 35

Which phase of counting sort actually “counts”?

Answer 35

second

Question 36

The expected number of comparisons for finding the kth largest of n keys using PARTITION is in which asymptotic set?

Answer 36

Θ(n)

Question 37

Memoization is associated with which technique?

Answer 37

top-down dynamic programming

Question 38

Circular linked lists are occasionally useful because

Answer 38

some operations may be done in constant time

Question 39

Given a pointer to a node, the worst-case time to delete the node from an unsorted, doubly-linked list with n nodes is:

Answer 39

Θ(1)

Question 40

Which phase of counting sort clears the count table?

Answer 40

first

Question 41

How will a circular queue implementation test for an empty queue?

Answer 41

return tail==head

Question 42

Assuming the input has been sorted, Huffman coding may use:

Answer 42

queues

Question 43

What is minimized in the dynamic programming solution to the subset sum problem?

Answer 43

the index stored for each C(i)