CS 127, Midterm 2
Ondich
Due Monday, June 2, 1997
You may use your textbook, a computer, your brain, and,
if available, divine guidance. Don't discuss this test with
anyone other than Jeff Ondich.
- (8 points) Suppose you want to build a hash table of
items whose keys are strings of letters. Let the slots be
numbered 0 through 6, and let the hash function consist of
taking the sum of the letters mod 7. For example, "dog"
hashes to (4 + 15 + 7) mod 7, that is, 5. Suppose your
table contains the items "dog",
"bug", "ant", "bee", and "gnu".
- If you use linear
probing to resolve collisions,
what does the table look like? How many key comparisons
will the longest possible failed search require?
- If you use chaining to resolve collisions,
what does the table look like? How many key comparisons
will the longest possible failed search require?
- (6 points) Start with an empty max-heap
and add the items D, Q, M, P, T, B, L, and R to the heap
in that order, one at a time.
What does the final heap look like? Now delete the maximum
item twice (after which the T and the R will be gone). What
does the resulting heap look like?
- (6 points) Do parts (c), (e) and (f) of Problem E3 on page 410 of Kruse.
- (6 points) Start with an empty AVL tree and add the items
A, H, M, J, K, Q, F, D, G, I to it, in that order. What does the
resulting tree look like?
- (8 points) Suppose you have a graph with 8 vertices, labelled
1 through 8, and edges (1,2), (1,5), (5,6), (6,7), (7,8),
(5,8), (2,3), (2,7), and (4,7).
- Draw the graph.
- List the vertices in the order in which they're visited by
a depth-first search starting at vertex 1, assuming you move towards
the smallest numbered vertex if you have a choice.
- Draw the spanning tree generated by this depth-first search.
- List the vertices and draw the spanning tree for a
breadth-first search starting at vertex 1, assuming again that
you move towards
the smallest numbered vertex if you have a choice.
- (3 points) I've been trying for several years to come up
with new names for the Macintoshes in CMC 301. They have been
named after McDonald's "food" items since we moved into the
building. Please suggest a better theme for the machine names.
- (9 points) Don, Edsger, and Grace are planning to
implement a hash table that will have 2048 slots. They
have agreed to resolve collisions with chaining. The items
the hash table will contain will be English words. They
are arguing over what hash function to use.
Criticize (positively or negatively) each of these proposals.
- Don advocates adding the letter numbers of the letters
in the word together (e.g. ada-> 1 + 4 + 1).
- Edsger wants to use a 64x64 2-dimensional array of slots, and
take the ASCII values of the first two letters of the word,
mod 64, as the indices of the slot into which the word will go.
- Grace wants to consider the character string as a string
of bits, break the bit string into 12-bit chunks, and
XOR these chunks together to get the hash value.
- (6 points) If you have an N-node binary tree, and you
call Inorder() (see page 393 of Kruse) on the
tree's root, how many times does Inorder() get called?
- (12 points) For each of the following scenarios, tell me
what data structure I should use, and defend your choice. If
implementation details matter (such as whether you'll use an
array or a linked structure), include them in your discussion.
- I want to have a database into which I can quickly insert
items, from which I can quickly delete items, and which I can
access efficiently in sorted order. I must also be able to
search for an item in this database, and it is essential that
my worst-case search time be fast (linear search is not acceptable).
- Memory is very tight, so I don't want to waste any.
I want to maintain a
database of items that will never change, and I know exactly
how many items there are. I will be searching
for items in the database often.
- I want to maintain a database. Additions, deletions,
and especially searches have to be very fast. I have lots
of memory available.