\documentstyle[11pt,cprog]{article}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}
\setlength{\topmargin}{-0.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{0.0in}
\begin{document}
\title{Exam questions\\}
\author
{Mark Allen Weiss\\
School of Computer Science\\
Florida International University\\
University Park\\
Miami, FL 33199}
\date{}
\maketitle
\begin{center}
{\large\bf Abstract}
\end{center}
{\small
This report contains a collection of multiple-choice
questions, organized by book chapter
that can be used for examinations.\footnote{
Many of these questions appear in different form
in the {\em Instructor's Resource Manual} for
{\em Algorithms, Data Structures, and Problem Solving with C++},
published by Addison-Wesley, 1996.}
Answers are provided at the end.
This report was typeset in \LaTeX. Original source
is available.}
\section*{Chapter 1}
\begin{enumerate}
\item What is the approximate value of log 1,000,000?
\begin{enumerate}
\item 10
\item 20
\item 50
\item 1000
\item none of the above
\end{enumerate}
\item If $\log n$ equals 100, what is the value of $\log (2n)$?
\begin{enumerate}
\item 101
\item 200
\item 1000
\item 10000
\item none of the above
\end{enumerate}
\item When performing a proof by induction, which is the case that is trivially true?
\begin{enumerate}
\item the basis
\item the inductive hypothesis
\item the lemma
\item the theorem
\item none of the above
\end{enumerate}
\item The following routine violates which rule(s) of recursion?
\begin{tt}\begin{verbatim}
function Recurse( N : Integer ) return Integer is
begin
if N = 0 then
return 0;
else
return N + Recurse( N / 2 ) + Recurse( N / 2 + 1 );
end if;
end Recurse;
\end{verbatim}\end{tt}
\begin{enumerate}
\item No base case
\item Fails to make progress
\item Performs redundant work
\item Two of the above
\item All of (a), (b), and (c)
\end{enumerate}
\item Which of the following is the most likely result of failing to make progress towards a base case in a recursive call?
\begin{enumerate}
\item compiler enters into an infinite loop
\item error at compilation time
\item exception is raised at run time
\item recursive routine enters an infinite loop when it runs
\item recursive routine terminates with bad value but no other error
\end{enumerate}
Answers: 1-B, 2-A, 3-A, 4-D, 5-C.
\end{enumerate}
\section*{Chapter 2}
\begin{enumerate}
\item Which of the following functions grows fastest?
\begin{enumerate}
\item $n \log n$
\item $2 ^ n$
\item $\log n$
\item $n^2$
\item $n^{20}$
\end{enumerate}
\item Which of the following functions grows fastest?
\begin{enumerate}
\item $n + \log n$
\item $n \log n$
\item $n - \log n$
\item $n$
\item There is a tie among two or more functions for fastest growth rate
\end{enumerate}
\begin{em}
The next three questions apply to the following code fragment:
\end{em}
\begin{tt}\begin{verbatim}
1 for i in 1..N loop
2 for j in 1..i loop
3 for k in i..j loop
4 Sum := Sum + 1;
5 end loop;
6 end loop;
7 end loop;
8 for p in 1..N*N loop
9 for q in 1..p loop
10 Sum := Sum - 1;
11 end loop;
12 end loop;
\end{verbatim}\end{tt}
\item How many times is statement 4 executed?
\begin{enumerate}
\item $O( N )$
\item $O( N^2 )$
\item $O( N^3) $
\item $O( N^4 )$
\item none of the above
\end{enumerate}
\item How many times is statement 10 executed?
\begin{enumerate}
\item $O( N )$
\item $O( N^2 )$
\item $O( N^3) $
\item $O( N^4 )$
\item none of the above
\end{enumerate}
\item What is the running time of the fragment?
\begin{enumerate}
\item $O( N^4 )$
\item $O( N^5 )$
\item $O( N^6) $
\item $O( N^7 )$
\item none of the above
\end{enumerate}
\item Suppose $T_1(n) = O( F(n) )$ and $T_2(n) = O(F(n) )$. Which of the following are true?
\begin{enumerate}
\item $T_1(n) + T_2(n) = O(F(n))$
\item $T_1(n) * T_2(n) = O(F(n))$
\item ${T_1(n)} / {T_2(n)} = O(1)$
\item $T_1(n) = O(T_2(n))$
\item none of the above
\end{enumerate}
\item Programs $A$ and $B$ are analyzed and found to have worst-case running times no greater than $150n \log n$ and $n^2$, respectively. Which of the following statements does the analysis imply?
\begin{enumerate}
\item Program $A$ will run faster on average for sufficiently large $n$.
\item Program $B$ will run faster on average for small n.
\item Program $A$ is probably simpler to code than program $B$.
\item There exists some input for which program $B$ takes longer than program $A$.
\item none of the above
\end{enumerate}
\item An algorithm takes 10 seconds for an input size of 50. If the algorithm is quadratic, approximately how long does it take to solve a problem of size 100?
\begin{enumerate}
\item 10 seconds
\item 20 seconds
\item 40 seconds
\item 100 seconds
\item none of the above
\end{enumerate}
\item An algorithm takes 30 seconds for an input of size 1000. If the algorithm is quadratic, how large a problem can be solved in two minutes?
\begin{enumerate}
\item 2000
\item 4000
\item 6000
\item 60000
\item none of the above
\end{enumerate}
\item An algorithm takes 6 seconds to solve a problem of size 100 and ten minutes to solve a problem of size 1000. What is the likely running time of the algorithm?
\begin{enumerate}
\item constant
\item linear
\item quadratic
\item cubic
\item none of the above
\end{enumerate}
\item Which of (a) to (d) is false about the binary search?
\begin{enumerate}
\item the input array must be sorted
\item successful searches take logarithmic time on average
\item unsuccessful searches take logarithmic time on average
\item the worst case for any search is logarithmic
\item all of the above are true
\end{enumerate}
\item Which of the following can be done in $O( \log n )$ arithmetic operations?
\begin{enumerate}
\item Raising a number to the $n$th power
\item Computing the greatest common divisor of some integer and $n$
\item Adding two $n$-digit numbers
\item Two of the above
\item All of (a), (b), and (c)
\end{enumerate}
\item A recursive algorithm works by solving two half-sized problems recursively, with an additional linear-time overhead. The total running time is most accurately given by
\begin{enumerate}
\item $O( \log n )$
\item $O( n )$
\item $O( n \log n )$
\item $O( n ^ 2 )$
\item none of the above
\end{enumerate}
\item The solution to $T(n) = T( \lfloor 3n/4 \rfloor ) + 10 $ with $T(0)=0$ is most accurately given by
\begin{enumerate}
\item $O( \log n )$
\item $O( n )$
\item $O( n \log n )$
\item $O( n ^ 2 )$
\item none of the above
\end{enumerate}
\item Approximately how many random numbers are using in the permutation generation algorithm in Exercise 2.7.c?
\begin{enumerate}
\item 1
\item $\log n$
\item $n$
\item $n \log n$
\item none of the above
\end{enumerate}
\item What is the running time of the following routine?
\begin{tt}\begin{verbatim}
// Check if N is prime
function Is_Prime( N : Integer ) return Boolean is
I : Integer := 3;
begin
if N = 2 or else N = 3 then
return TRUE;
end if;
if N MOD 2 = 0 then
return FALSE;
end if;
while i * i <= N loop
if N MOD i = 0 then
return FALSE;
else
I := I + 2;
end if;
end loop;
return TRUE;
end Is_Prime;
\end{verbatim}\end{tt}
\begin{enumerate}
\item constant time
\item $O ( \log N )$
\item $O( N )$
\item $O( \sqrt{ N } )$
\item none of the above
\end{enumerate}
\end{enumerate}
Answers: 1-B, 2-B, 3-C, 4-D, 5-A, 6-A, 7-E, 8-C, 9-A, 10-C,
11-E, 12-D, 13-C, 14-A, 15-C, 16-D.
\section*{Chapter 3}
\begin{enumerate}
\item Which of the following operations is not efficiently supported by a singly-linked list?
\begin{enumerate}
\item accessing the element in the current position
\item insertion after the current position
\item insertion before the current position
\item moving to the position immediately following the current position
\item all of the above are efficiently supported
\end{enumerate}
\item Which statement, placed in the list package implementation, inserts an item {\tt X} after position {\tt Current}?
\begin{enumerate}
\item {\tt Current := new Node'( X, Current );}
\item {\tt Current := new Node'( X, Current.Next );}
\item {\tt Current.Next := new Node'( X, Current );}
\item {\tt Current.Next := new Node'( X, Current.Next );}
\item none of the above
\end{enumerate}
\item The header node of a linked list
\begin{enumerate}
\item simplifies deletion
\item simplifies insertion
\item uses only constant extra space
\item two of the above
\item all three of (a), (b), and (c)
\end{enumerate}
\item If a header node is used, which of the following indicates a list {\tt L} with one item?
\begin{enumerate}
\item {\tt L.Header.Next = null}
\item {\tt L.Header.Next /= null }
\item {\tt L.Header.Next /= null and then L.Header.Next.Next /= null }
\item {\tt L.Header.Next /= null and then L.Header.Next.Next = null }
\item none of the above
\end{enumerate}
\item Insertion of a node into a doubly linked list requires how many changes to various {\tt Next} and {\tt Prev} pointers?
\begin{enumerate}
\item no changes
\item 1 {\tt Next}, 1 {\tt Prev}
\item 2 {\tt Next}, 2 {\tt Prev}
\item 3 {\tt Next}, 3 {\tt Prev}
\item none of the above
\end{enumerate}
\item What operation is supported in constant time by the doubly linked list, but not by the singly linked list?
\begin{enumerate}
\item {\tt Advance}
\item {\tt Backup}
\item {\tt First}
\item {\tt Retrieve}
\item all of the above are always constant time
\end{enumerate}
\item The UNIX editor {\em vi} allows searching in both directions, with wraparound if necessary. If the sequence of lines is stored as a linked list, which of the following is most reasonable?
\begin{enumerate}
\item singly linked list
\item doubly linked list
\item circular singly linked list
\item circular doubly linked list
\item none of the above
\end{enumerate}
\item What happens when wraparound is implemented for a queue?
\begin{enumerate}
\item If {\tt Front} advances past the last array position, it is reset to the first array position.
\item If {\tt Rear} advances past the last array position, it is reset to the first array position.
\item Both (a) and (b)
\item Neither (a) nor (b)
\end{enumerate}
\item Using the text implementation, if {\tt Front} and {\tt Rear} have identical values, what is the size of the queue?
\begin{enumerate}
\item 0
\item 1
\item 2
\item the answer cannot be determined
\item none of the above
\end{enumerate}
\item For the linked list implementation of the stack, where are the pushes and pops performed?
\begin{enumerate}
\item Push in front of the first element, pop the first element
\item Push after the last element, pop the last element
\item Push after the last element, pop the first element
\item Push in front of the first element, pop the last element
\item Push after the first element, pop the first element
\end{enumerate}
\item For the linked list implementation of the queue, where are the enqueue and dequeues performed?
\begin{enumerate}
\item Enqueue in front of the first element, dequeue the first element
\item Enqueue after the last element, dequeue the last element
\item Enqueue after the last element, dequeue the first element
\item Enqueue in front of the first element, dequeue the last element
\item Enqueue after the first element, dequeue the first element
\end{enumerate}
\item For the linked list implementation, if the stack is not empty, which of the following statements in a main procedure can be used to access the top element in the stack {\tt S}?
\begin{enumerate}
\item {\tt S.Element}
\item {\tt S.TopOfStack}
\item {\tt S.TopOfStack.Element}
\item {\tt TopOfStack.Element}
\item none of the above
\end{enumerate}
\end{enumerate}
Answers: 1-C, 2-D, 3-E, 4-D, 5-C, 6-B, 7-D, 8-C, 9-B, 10-A, 11-C, 12-E.
\section*{Chapter 4}
\begin{enumerate}
\item Which of the following traversals requires more than linear time in the worst case?
\begin{enumerate}
\item inorder
\item level order
\item postorder
\item preorder
\item all of these traversals are linear time
\end{enumerate}
\item In which of the following traversals is the node processed before the recursive calls to the children complete?
\begin{enumerate}
\item inorder
\item level order
\item postorder
\item preorder
\item none of the above
\end{enumerate}
\item What is the maximum number of nodes in a binary tree with $L$ leaves?
\begin{enumerate}
\item $2L$
\item $2^L$
\item $2^{L+1}$
\item there is no maximum
\item none of the above
\end{enumerate}
\item Which of the following is true about the height of a node?
\begin{enumerate}
\item The height of a node is one less than the height of its parent
\item The height of an empty tree is 0
\item The height of a leaf is 0
\item The height of a tree can be larger than its depth
\item all of the above are false
\end{enumerate}
\item The first child / next sibling implementation
\begin{enumerate}
\item allows easy access to the parent
\item is appropriate for binary trees
\item uses $C$ pointers per node, where $C$ is the number of children
\item all of the above
\item none of (a), (b), and (c)
\end{enumerate}
\item Which traversal computes the total size of each directory in the UNIX file system?
\begin{enumerate}
\item inorder
\item level order
\item postorder
\item preorder
\item two or more of the above traversals could be used
\end{enumerate}
\item Let {\tt C(X)} be the number of leaves in a binary tree rooted at {\tt T}. Assume that {\tt IsLeaf(T)} returns 1 if {\tt T} is a leaf. Which of the following observations leads to a recursive implementation?
\begin{enumerate}
\item {\tt C(T):=C(T.Left)+C(T.Right) }
\item {\tt C(T):=C(T.Left)+C(T.Right)+1 }
\item {\tt C(T):=C(T.Left)+C(T.Right)+IsLeaf(T) }
\item {\tt C(T):=C(T.Left)+C(T.Right)+IsLeaf(T)+1 }
\item none of the above
\end{enumerate}
\item Which traversal does not use a stack?
\begin{enumerate}
\item inorder
\item level order
\item postorder
\item preorder
\item all of these traversals uses a stack
\end{enumerate}
\item How many $n$ node binary trees with items 1, 2, ..., $n$ have identical postorder and inorder traversals?
\begin{enumerate}
\item 0
\item 1
\item $n$
\item $n!$
\item none of the above
\end{enumerate}
\begin{em}
The next three questions relate to the binary tree with root $A$.
The root has left child $B$ and right child $C$.
$B$ has left child $D$ and right child $E$.
There are no other nodes in the tree.
\end{em}
\item Which of the following traversals yields ABCDE?
\begin{enumerate}
\item inorder
\item level order
\item postorder
\item preorder
\item two of the above
\end{enumerate}
\item Which of the following is an inorder traversal of the tree?
\begin{enumerate}
\item ABCDE
\item ABDEC
\item DBEAC
\item DEBAC
\item none of the above
\end{enumerate}
\item The height of the tree is
\begin{enumerate}
\item 0
\item 1
\item 2
\item 3
\item none of the above
\end{enumerate}
\item Approximately what is the maximum height of a binary search tree of $n$ nodes?
\begin{enumerate}
\item $\log n$
\item $1.38 \log n$
\item $1.44 \log n$
\item $2 \log n$
\item none of the above
\end{enumerate}
\item The following items are inserted into a binary search tree: 8, 3, 4, 9, 5, 6, 2, 1, 7. Which item is placed at a root?
\begin{enumerate}
\item 1
\item 4
\item 8
\item 9
\item none of the above
\end{enumerate}
\item The following items are inserted into a binary search tree: 3, 6, 5, 2, 4, 7, 1. Which node is the deepest?
\begin{enumerate}
\item 1
\item 3
\item 4
\item 7
\item none of the above
\end{enumerate}
\item Which of the following statements is true about deleting the root of a binary search tree?
\begin{enumerate}
\item the root pointer always changes
\item the root pointer changes if it does not have two children
\item if the root has two children, its item is replaced by the largest element in the right subtree
\item all of the above
\item none of (a), (b), and (c)
\end{enumerate}
\item For an insertion of a single item into an $n$-item AVL tree, the maximum number of rotations (double rotations count as one rotation) is
\begin{enumerate}
\item 1
\item 2
\item approximately $\log n$
\item approximately $1.44 \log n$
\item none of the above
\end{enumerate}
\item The following items are inserted into an AVL tree: 1, 2, 3, 8, 6. How many rotations are performed?
\begin{enumerate}
\item no rotations
\item 1 single rotation only
\item 1 double rotation only
\item 1 single rotation and 1 double rotation
\item none of the above
\end{enumerate}
\item Items 7, 3, 11, 9, and 13 are inserted into an AVL tree. What happens when 12 is inserted?
\begin{enumerate}
\item no rotation is needed
\item a single rotation between some node and its left child is performed
\item a single rotation between some node and its right child is performed
\item a double rotation with a node, its left child, and a third node is performed
\item a double rotation with a node, its right child, and a third node is performed
\end{enumerate}
\item Which of the following data structures has the strongest height guarantee?
\begin{enumerate}
\item AVL tree
\item B-tree of order 3
\item B-tree of order 5
\item splay tree
\item 2-3 tree
\end{enumerate}
\item Suppose a disk block stores 4096 bytes and the basic key size is 96 bytes. Assuming that pointers cost 4 bytes, what is the correct choice of $M$ for a B-tree?
\begin{enumerate}
\item 41
\item 42
\item 43
\item 96
\item none of the above
\end{enumerate}
\item In addition to the data and left and right pointers, for {\bf any} implementation, what must be stored in each node of a splay tree?
\begin{enumerate}
\item the node's height
\item the node's level
\item the node's parent
\item the node's rank
\item none of the above
\end{enumerate}
\item What is amortized cost of an operation using rotate-to-root?
\begin{enumerate}
\item $O(1)$
\item $O( \log n )$
\item $O( n )$
\item $O( n \log n )$
\item none of the above
\end{enumerate}
\item An access of a splay tree of $n$ nodes results in a completely identical tree. For how many different nodes would this be possible?
\begin{enumerate}
\item 0
\item 1
\item 2
\item $n - 1$
\item none of the above
\end{enumerate}
\item What is the worst-case height of a splay tree?
\begin{enumerate}
\item $\log n$
\item $1.38 \log n$
\item $2 \log n$
\item $n - 1$
\item $n$
\end{enumerate}
\item Which of the statements (a) to (d) about splay trees is false?
\begin{enumerate}
\item a single access operation could examine every node in the tree
\item any $n$ consecutive operations from an initially empty splay tree must take at most $O( n \log n )$ time
\item inserting the items 1, 2, ..., $n$ into an initially empty splay tree takes $O( n) $ total time.
\item the most recently accessed item is at the root
\item none of (a) to (d) is false
\end{enumerate}
\item Which of the following splay tree rotations in effect distinguishes it from rotate-to-root?
\begin{enumerate}
\item zig only
\item zig-zag only
\item zig-zig only
\item zig-zig and zig-zag only
\item all of the above
\end{enumerate}
\item What item is at the root after the following sequence of insertions into an empty splay tree: 1, 11, 3, 10, 8, 4, 6, 5, 7, 9, 2?
\begin{enumerate}
\item 1
\item 2
\item 4
\item 8
\item none of the above
\end{enumerate}
\item How is deletion performed in a splay tree?
\begin{enumerate}
\item If the node is found, it is replaced with the smallest node in its right subtree, which itself is recursively deleted.
\item It the node is found, it is replaced with the largest node in its left subtree, which itself is recursively deleted.
\item A single splay is performed which places the deleted node in a leaf; that node is then easily removed
\item A single splay is performed which places the deleted node at the root; it is deleted and the two subtrees are reattached by using a second splay
\item none of the above
\end{enumerate}
\item In a splay tree, how is the rank of a node stored?
\begin{enumerate}
\item an extra array stores the information
\item a linked list stores the information
\item directly, in each node
\item indirectly, by storing the size in each node
\item the rank is not stored at all
\end{enumerate}
\item Which of the following alternatives preserves the logarithmic amortized time bound for the splay tree?
\begin{enumerate}
\item do not splay on unsuccessful searches
\item do not splay if an access path has fewer than $\log n$ nodes
\item replace the zig-zig with two single bottom-up rotations
\item splay on every other access
\item none of the above
\end{enumerate}
\end{enumerate}
Answers: 1-E, 2-D, 3-D, 4-C, 5-E, 6-C, 7-C, 8-B, 9-B, 10-B, 11-C, 12-C,
13-E, 14-C, 15-C, 16-B, 17-A, 18-D, 19-C, 20-C, 21-A, 22-E, 23-C, 24-B,
25-D, 26-E, 27-C, 28-B, 29-D, 30-E, 31-B.
\section*{Chapter 5}
\begin{enumerate}
\item Which of the following data structures requires more than constant average time for insertions?
\begin{enumerate}
\item hash table
\item queue
\item search tree
\item stack
\item all of the above have constant time insertion algorithms
\end{enumerate}
\item What is the range of values computed by the hash function $Hash( X ) = X \bmod 100$?
\begin{enumerate}
\item 0 to 99
\item 0 to 100
\item 1 to 99
\item 1 to 100
\item none of the above
\end{enumerate}
\item Which of (a) to (d) is false: The size of a hash table
\begin{enumerate}
\item should be a power of 2 for quadratic probing
\item should be a prime number for linear probing
\item should be about $2n$ for quadratic probing
\item should be about $n$ for separate chaining
\item two or more of the above are false
\end{enumerate}
\item How are elements deleted in linear probing?
\begin{enumerate}
\item deletion is not allowed
\item they are changed to zero
\item they are marked deleted
\item unchecked deallocation
\item none of the above
\end{enumerate}
\item Suppose we are implementing quadratic probing with a hash function $Hash( X ) = X \bmod 100$. If an element with key 4594 is inserted and the first three locations attempted are already occupied, then the next cell that will be tried is
\begin{enumerate}
\item 2
\item 3
\item 9
\item 97
\item none of the above
\end{enumerate}
\item In a separate chaining hash table with load factor $\lambda = 0.8$, what is the average length of a list?
\begin{enumerate}
\item 0.8
\item 1.0
\item 1.25
\item there is not enough information
\item there is enough information, but none of the above are correct
\end{enumerate}
\item Which of the following costs are equal in a probing hash table?
\begin{enumerate}
\item insertion and successful search
\item insertion and unsuccessful search
\item successful search and unsuccessful search
\item insertion, successful search, and unsuccessful search
\item none of the above
\end{enumerate}
\item Which of the following statements about quadratic probing is true (expensive does not include trivial operations such as multiplication or division by powers of 2; computation of the hash function is not included in the cost)?
\begin{enumerate}
\item an expensive division must be performed
\item an expensive mod operator must be performed
\item an expensive multiplication must be performed
\item all of the above
\item none of (a), (b), and (c)
\end{enumerate}
\item Linked lists are used in
\begin{enumerate}
\item double hashing
\item linear probing
\item quadratic probing
\item separate chaining
\item all of the above
\end{enumerate}
\item {\em Primary clustering} occurs in
\begin{enumerate}
\item linear probing
\item quadratic probing
\item separate chaining
\item all of the above
\item none of (a), (b), and (c)
\end{enumerate}
\item {\em Rehashing} can be used in
\begin{enumerate}
\item linear probing
\item quadratic probing
\item separate chaining
\item all of the above
\item none of (a), (b), and (c)
\end{enumerate}
\end{enumerate}
Answers: 1-C, 2-A, 3-A, 4-C, 5-B, 6-A, 7-B, 8-E, 9-D, 10-A, 11-D.
\section*{Chapter 6}
\begin{enumerate}
\item Every node in a (min) binary heap
\begin{enumerate}
\item has two children
\item is no larger than its children
\item is no smaller than its children
\item has a smaller left child than right child
\item two or more of the above
\end{enumerate}
\item If an element in a binary heap is stored in position $i$ and the root is at position 1, then where is the parent stored?
\begin{enumerate}
\item $\lfloor i/ 2 \rfloor$
\item $\lceil i / 2 \rceil$
\item $ 1 + \lfloor i/2 \rfloor $
\item $2i$
\item $2i + 1$
\end{enumerate}
\item The running time of {\tt Build\_Heap} is
\begin{enumerate}
\item $O( n )$ worst case and $O ( n )$ average case
\item $O( n )$ worst case and $O( \log n )$ average case
\item $O( n ) $ worst case and $O( n \log n )$ average case
\item $O( n \log n )$ worst case and $O( n )$ average case
\item $O( n \log n )$ worst case and $O( n \log n )$ average case
\end{enumerate}
\item $n$ elements are inserted one by one into an initially empty binary heap. The total running time is
\begin{enumerate}
\item $O( n )$ worst case and $O ( n )$ average case
\item $O( n )$ worst case and $O( \log n )$ average case
\item $O( n ) $ worst case and $O( n \log n )$ average case
\item $O( n \log n )$ worst case and $O( n )$ average case
\item $O( n \log n )$ worst case and $O( n \log n )$ average case
\end{enumerate}
\item Which operation is not supported in constant time by a double-ended queue (deque)?
\begin{enumerate}
\item Insertion as the front or rear item
\item Access of the front or rear item
\item Deletion of the front or rear item
\item Access and deletion of the minimum item
\item all of the above are supported
\end{enumerate}
\item Which operation is not efficiently supported by priority queues?
\begin{enumerate}
\item {\tt Delete\_Min}
\item {\tt Find}
\item {\tt Find\_Min}
\item {\tt Insert}
\item All of the above are efficiently supported
\end{enumerate}
\item Which data structure is used to check for balanced parentheses?
\begin{enumerate}
\item binary search tree
\item hash table
\item priority queue
\item queue
\item stack
\end{enumerate}
\item Jobs sent to a printer are generally placed on a
\begin{enumerate}
\item binary search tree
\item hash table
\item priority queue
\item queue
\item stack
\end{enumerate}
\item Which data structure is generally used to implement a symbol table?
\begin{enumerate}
\item binary search tree
\item hash table
\item priority queue
\item queue
\item stack
\end{enumerate}
\item Which data structure maintains the event set in an event-driven (discrete-event) simulation?
\begin{enumerate}
\item binary search tree
\item hash table
\item priority queue
\item queue
\item stack
\end{enumerate}
\item Which of the following could be used as an efficient priority queue?
\begin{enumerate}
\item binary search tree
\item hash table
\item linked list
\item queue
\item stack
\end{enumerate}
\item Which of the following does the binary heap implement?
\begin{enumerate}
\item binary search tree
\item hash table
\item priority queue
\item queue
\item stack
\end{enumerate}
\item 6, 8, 4, 3, and 1 are inserted into a data structure in that order. An item is deleted using only a basic data structure operation. If the deleted item is a 1, the data structure cannot be a
\begin{enumerate}
\item hash table
\item priority queue
\item queue
\item search tree
\item stack
\end{enumerate}
\item Which data structure is used by the compiler to implement recursion?
\begin{enumerate}
\item hash table
\item priority queue
\item queue
\item search tree
\item stack
\end{enumerate}
\item Which of the following data structures uses a sentinel?
\begin{enumerate}
\item binary heap
\item hash table
\item queue
\item stack
\item none of the above use sentinels
\end{enumerate}
\item A node with key 8 has a left child with key 10. Which of the following objects could this node be found in?
\begin{enumerate}
\item binary search tree
\item max heap
\item min heap
\item two of the above
\item none of (a), (b), and (c)
\end{enumerate}
\item {\em Percolate up} and {\em down} are used for
\begin{enumerate}
\item AVL trees
\item B-trees
\item circular queue
\item binary heaps
\item none of the above
\end{enumerate}
\item Which of the following is true about the skew heap?
\begin{enumerate}
\item it is balanced
\item each node stores nothing besides an item and two pointers
\item the right path contains at most a logarithmic number of nodes
\item two of the above
\item all of (a), (b), and (c)
\end{enumerate}
\item Which of the four operations below can be used to implement the other three for the skew heap?
\begin{enumerate}
\item {\tt Decrease\_Key}
\item {\tt Delete\_Min}
\item {\tt Insert}
\item {\tt Merge}
\item none of the above
\end{enumerate}
\item Which of the following is not a binary tree?
\begin{enumerate}
\item binary heap
\item binomial queue
\item skew heap
\item splay tree
\item all of the above are binary trees
\end{enumerate}
\end{enumerate}
Answers: 1-B, 2-A, 3-A, 4-D, 5-D, 6-B, 7-E, 8-D, 9-B, 10-C, 11-A, 12-C,
13-C, 14-E, 15-A, 16-C, 17-D, 18-B, 19-D, 20-B.
\section*{Chapter 7}
\begin{enumerate}
\item What is the basic algorithm used for external sorting?
\begin{enumerate}
\item finding the median
\item merging
\item selection
\item all of the above
\item none of (a), (b), and (c)
\end{enumerate}
\item Which of the following data structures does not yield an efficient comparison-based sort?
\begin{enumerate}
\item AVL tree
\item hash table
\item priority queue
\item all can be used for efficient sorting
\item none can be used for efficient sorting
\end{enumerate}
\item Which of the following algorithms requires the most extra space, on average, when implemented as in the text?
\begin{enumerate}
\item heapsort
\item insertion sort
\item mergesort
\item quicksort
\item shellsort
\end{enumerate}
\item Which of the following is the strongest lower bound for sorting when ordering information is obtained only by {\em adjacent comparisons}?
\begin{enumerate}
\item $O( n \log n )$
\item $O( n ^ 2 ) $
\item $\Omega( n \log n )$
\item $\Omega( n ^ 2 )$
\item none of the above is a valid lower bound for this problem
\end{enumerate}
\item Which of the following algorithms runs in quadratic average time?
\begin{enumerate}
\item heapsort
\item insertion sort
\item mergesort
\item quicksort
\item shellsort
\end{enumerate}
\item Which of the following algorithms runs in $O( n \log n )$ average time but quadratic worst-case time?
\begin{enumerate}
\item heapsort
\item insertion sort
\item mergesort
\item quicksort
\item shellsort
\end{enumerate}
\item Which of the following algorithms, implemented as in the text, runs in $O( n )$ time when presented with an array of $n$ identical elements?
\begin{enumerate}
\item heapsort
\item insertion sort
\item mergesort
\item quicksort
\item shellsort
\end{enumerate}
\item Which of the following algorithms has the largest big-Oh differential between average-case and worst-case performance?
\begin{enumerate}
\item heapsort
\item insertion sort
\item mergesort
\item quicksort
\item quickselect
\end{enumerate}
\item How much extra space is used by heapsort?
\begin{enumerate}
\item $O( 1 )$
\item $O( \log n )$
\item $O( n )$
\item $O( n ^ 2 )$
\item none of the above
\end{enumerate}
\item Which sorting algorithm has the same average and worst-case time bounds (in Big-Oh) as heapsort?
\begin{enumerate}
\item insertion sort
\item mergesort
\item quicksort
\item shellsort
\item none of the above
\end{enumerate}
\item For quicksort, what do {\tt I} and {\tt J} do when they see keys equal to the pivot?
\begin{enumerate}
\item {\tt I} stops, {\tt J} stops
\item {\tt I} stops, {\tt J} goes
\item {\tt I} goes, {\tt J} stops
\item {\tt I} goes, {\tt J} goes
\item {\tt I} and {\tt J} alternate between stopping and going
\end{enumerate}
\item In median-of-three partitioning, where is the pivot placed before partitioning begins?
\begin{enumerate}
\item at the start of the array
\item at the middle of the array
\item at the end of the array
\item in a temporary variable
\item none of the above
\end{enumerate}
\item Which of the following statements about sorting five elements is the strongest statement that is directly implied by the information theoretic lower bound?
\begin{enumerate}
\item 6 comparisons are sufficient
\item 6 comparisons are necessary and sufficient
\item 7 comparisons are necessary
\item 7 comparisons are sufficient
\item 7 comparisons are necessary and sufficient
\end{enumerate}
\item {\em Replacement selection} is
\begin{enumerate}
\item arranging the initial runs on the tape in an optimal way
\item constructing the runs so they have expected length $2M$
\item using $K$-way merging instead of 2-way merging
\item using $K + 1$ tapes instead of $K$ tapes
\item none of the above
\end{enumerate}
\end{enumerate}
Answers: 1-B, 2-B, 3-C, 4-D, 5-B, 6-D, 7-B, 8-E, 9-A, 10-B, 11-A, 12-E,
13-C, 14-B.
\section*{Chapter 8}
\begin{enumerate}
\item Which of the following trees can have height that is not logarithmic?
\begin{enumerate}
\item AVL tree
\item binary heap
\item B-tree of order 4
\item union/find tree, with union-by-height
\item all of the above trees must have logarithmic depth
\end{enumerate}
\item Which of the following properties is not required for an equivalence relation?
\begin{enumerate}
\item reflexive
\item symmetric
\item transitive
\item all of these properties are required
\item none of these properties is required
\end{enumerate}
\item Which of the following is an equivalence relationship?
\begin{enumerate}
\item $a$ R $b$ if there is a path from $a$ to $b$ in a directed graph $G$
\item $a$ R $b$ if $a$ and $b$ are two people who know each other
\item $a$ R $b$ if $a$ and $b$ end in the same two digits
\item all of the above
\item none of (a), (b), (c)
\end{enumerate}
\item Which of the following, when performed by itself, is sufficient to ensure a bound of $O( m \log n )$ for $m$ operations?
\begin{enumerate}
\item path compression
\item union by height
\item union by size
\item all of the above
\item none of (a), (b), and (c)
\end{enumerate}
\item {\em Path compression} is
\begin{enumerate}
\item performed during {\tt Union}s to make {\tt Union}s faster
\item performed during {\tt Union}s to make {\tt Find}s faster
\item performed during {\tt Find}s to make {\tt Find}s faster
\item performed during {\tt Find}s to make {\tt Union}s faster
\item performed during {\tt Find}s to make both {\tt Find}s and {\tt Union}s faster
\end{enumerate}
\item What is the value of ${\log} ^ * 65536$?
\begin{enumerate}
\item 1
\item 4
\item 16
\item 32
\item none of the above
\end{enumerate}
\end{enumerate}
Answers: 1-E, 2-D, 3-C, 4-D, 5-C, 6-B.
\section*{Chapter 9}
\begin{enumerate}
\item Which of the following is a synonym for an edge?
\begin{enumerate}
\item arc
\item node
\item path
\item vertex
\item none of the above
\end{enumerate}
\item Which of the following problems is not known to be solvable in linear time?
\begin{enumerate}
\item topological sort
\item unweighted shortest path in general graphs
\item weighted shortest path in acyclic graphs
\item weighted shortest path in cyclic graphs
\item all are solvable in linear time
\end{enumerate}
\item Which of the following does not use a queue?
\begin{enumerate}
\item negative weighted shortest path algorithm
\item positive weighted shortest path algorithm
\item topological sort
\item unweighted shortest path algorithm
\item all of the above use a queue
\end{enumerate}
\item Which of the following algorithms solves the unweighted single source shortest path problem?
\begin{enumerate}
\item breadth first search
\item depth first search
\item Dijkstra's algorithm
\item Kruskal's algorithm
\item Prim's algorithm
\end{enumerate}
\item Which of the following algorithms solves the positive weighted single source shortest path problem?
\begin{enumerate}
\item breadth first search
\item depth first search
\item Dijkstra's algorithm
\item Kruskal's algorithm
\item Prim's algorithm
\end{enumerate}
\item In a graph with $v$ vertices and $e$ edges, which of the following maximum sizes is not correct for an unweighted shortest path computation?
\begin{enumerate}
\item $v$ for the number of adjacency lists
\item $e$ for the total size of all adjacency lists
\item $e$ for the size of the hash table that maps names to internal numbers
\item $v$ for the size of the queue
\item all of the above are correct
\end{enumerate}
\item In a connected graph with no loops or multiple edges, which of the following inequalities is not correct? ($v$ is the number of vertices, $e$ is the number of edges)
\begin{enumerate}
\item $e \le v^2$
\item $e \ge v - 1$
\item $v \le e^2 + 1 $
\item $v \ge e / 2 $
\item all of the above are correct
\end{enumerate}
\item If the shortest path algorithm is run and a vertex is not reachable from the starting point, what happens?
\begin{enumerate}
\item a distance of infinity is reported
\item a distance of -1 is reported
\item a distance of zero is reported
\item the algorithm enters an infinite loop
\item the algorithm's results are undefined
\end{enumerate}
\item For the weighted shortest path problem, let $d_v$ be the cost of reaching the current vertex $v$, let $w$ be adjacent to $v$ and assume the edge cost is $c_{v,w}$. Suppose that $d_w$ was the cost of reaching $w$ prior to examining $v$. (Ties are broken in favor of the first path seen). Then under what circumstances is $w$'s distance lowered?
\begin{enumerate}
\item $d_w > d_v$
\item $d_w > d_v + 1$
\item $d_w > d_v + c_{v,w} $
\item $d_v > d_w + c_{v,w} $
\item none of the above
\end{enumerate}
\item Which of the following statements is true?
\begin{enumerate}
\item A topological ordering exists in every directed graph
\item Every acyclic graph has at least one topological ordering
\item Every acyclic graph has exactly one topological ordering
\item Every acyclic graph has at most one topological ordering
\item none of the above
\end{enumerate}
\begin{em}
The next four questions refer to the following directed graph:
$V = \{ V_0, V_1, V_2, V_3,$ $ V_4, V_5, V_6 \}$.
There are the following twelve edges, with edge costs listed
as the third item in the triplet:
$E = \{ ( V_0, V_2, 4 ), $ $( V_1, V_0, 2 ),$ $ ( V_1, V_3, 3 ),$
$( V_3, V_0, 1 ),$ $ ( V_3, V_2, 2 ),$ $ ( V_3, V_5, 8 ),$ $ ( V_3, V_6, 4 ),$
$( V_4, V_1, 10 ),$ $ ( V_4, V_3, 2 ),$ $ ( V_4, V_6, 7 ),$
$( V_5, V_2, 2 ),$ $ ( V_6, V_5, 1 ) \}$.
\end{em}
\item The shortest weighted path from $V_4$ to $V_5$ has weight
\begin{enumerate}
\item 2
\item 4
\item 7
\item 8
\item none of the above
\end{enumerate}
\item If the start vertex is $V_4$, then using the standard weighted shortest path algorithm, which is the last vertex to be declared known?
\begin{enumerate}
\item $V_0$
\item $V_1$
\item $V_2$
\item $V_4$
\item none of the above
\end{enumerate}
\item If the start vertex is $V_4$, then using the acyclic weighted shortest path algorithm, which is the last vertex to be declared known?
\begin{enumerate}
\item $V_0$
\item $V_1$
\item $V_2$
\item the graph is not acyclic, so the acyclic algorithm should not be used
\item none of the above
\end{enumerate}
\item If the above graph were undirected, then what would be the cost of its minimum spanning tree?
\begin{enumerate}
\item 1
\item 10
\item 11
\item 12
\item none of the above
\end{enumerate}
\item Which algorithm is used to compute minimum spanning trees?
\begin{enumerate}
\item breadth first search
\item depth first search
\item Dijkstra's
\item Kruskal's
\item none of the above
\end{enumerate}
\end{enumerate}
Answers: 1-A, 2-D, 3-B, 4-A, 5-C, 6-C, 7-D, 8-A, 9-C, 10-B, 11-C, 12-B,
13-C, 14-B, 15-D.
\section*{Chapter 10}
\begin{enumerate}
\item Which of the following strategies do not directly invoke recursion?
\begin{enumerate}
\item backtracking
\item divide and conquer
\item dynamic programming
\item two of the above do not directly invoke recursion
\item none of (a), (b), and (c) directly invoke recursion
\end{enumerate}
\item 10000 random integers are generated randomly with a uniform distribution over the range 1 to 10000 inclusive. Which of the following would indicate a poor generator?
\begin{enumerate}
\item the average of the numbers is about 4999
\item each number appears exactly once
\item no four consecutive numbers are all even
\item two of the above
\item all of (a), (b), and (c)
\end{enumerate}
\item The {\em seed} of a linear congruential generator is
\begin{enumerate}
\item always zero
\item occasionally zero, depending on other random events
\item the initial value
\item the multiplier
\item the period of the generator
\end{enumerate}
\item Which of the following is a bad case for randomized quickselect?
\begin{enumerate}
\item any input with $K = 1$
\item reverse ordered input
\item sorted input
\item there are no bad inputs
\item none of the above
\end{enumerate}
\item If the randomized primality testing algorithm (with one iteration) declares that $P$ is prime and $C$ composite, then which of the following is most accurate?
\begin{enumerate}
\item There is at most a 25 percent chance that $P$ has been declared prime falsely and there is at most a 25 percent chance that $C$ has been declared composite falsely
\item $P$ is prime with 100 percent certainty but there is at most a 25 percent chance that $C$ has been declared composite falsely
\item There is at most a 25 percent chance that $P$ has been declared prime falsely, but $C$ is composite with at least 100 percent certainty
\item $P$ is prime with 100 percent certainty and $C$ is composite with 100 percent certainty
\item All of the above statements are factually incorrect
\end{enumerate}
\end{enumerate}
Answers: 1-C, 2-D, 3-C, 4-D, 5-C.
\end{document}