CS 127
Midterm 2
Ondich
Due ON PAPER 11:10 AM Monday, March 5, 2001
For this exam, you may use your textbook and a language
reference, my sample code, your own programs and notes, and divine
guidance should any be available to you.
You may not use other books, web pages, or code.
If you get stuck, talk to
me, but please don't talk to anyone else (not even
Jeremy Carr or the lab assistants) about the exam.
You may discuss syntax and system problems with
Jeremy or the lab assistants, but you must tell them that you are
working on an exam.
- (12 points) For each of the following scenarios, recommend a
data structure. Briefly justify your recommendation.
- You have a database of a few million items, and it's
mostly static. That is, you are seldom going
to add items to or delete items from the database.
Each item in the database has a single search key, and
you plan to do lots of searches.
Memory is extremely limited.
- You have a database of a few hundred items, each of which
has a single search key. You plan to do lots of adding and
deleting, and millions of searches. It is essential that
you keep search times as short as possible. You can have
as much memory as you want.
- You are going to do a word-frequency program as in
your homework that was due 2/19, and run it on the text version
of the English translation of the Koran (1.7MB). Unfortunately,
you don't seem to be able to find your old code, and you have
to get this program running in 45 minutes or you'll miss your bus home.
You can let the program run overnight.
- (12 points) Suppose you have a file consisting of a list
of names and their test scores, like so:
Norman 92
Felicity 84
Quentin 9
Alice 92
etc.
You may assume that no two lines have the same name, but that
scores may be duplicated.
- Write a program using the standard template library
map template to read this file and print out
a list of names and scores in alphabetical order by
name.
- Describe a data structure that will enable you to
search the name/score pairs by name in O(log N) time,
search the name/score pairs by score in O(log N) time,
print the pairs in alphabetical order in O(N) time,
and print the pairs in numerical order in O(N) time.
YOU NEED NOT IMPLEMENT THIS DATA STRUCTURE.
- (8 points) Consider the following AVL tree, called T1,
whose nodes contain letters of the alphabet:
Q
J U
D L S V
C H - M - T - X
A - E I - - - - - - - - - - - -
(In this representation of a tree, I have written each row of the tree
from left to right, with a "-" wherever there is no node. So Q is the
root, the children of U are S and V, and V has a right child X but
no left child.)
- Draw the AVL tree T2 that results when you add G to T1.
- Draw the AVL tree T3 that results when you add Z to T2.
- (6 points) Start with the tree T1 from the previous problem, but
this time treat it as an ordinary binary search tree (not an AVL tree).
Show the tree that results when you delete the root from T1 using the
algorithm in section 4.3.4 of your textbook.
- (4 points) What is the largest number of edges in a graph with
N nodes, given that at most one edge can connect any pair of nodes, and
that no edge can connect a node to itself?
- (12 points) Consider a graph G with 9 nodes numbered 0 through 8,
whose edge set is {(0,8), (0,1), (0,2), (1,3), (2,3), (2,4), (6,8),
(5,6), (5,7), (3,7)}.
- Draw the graph.
- Using the breadth-first search
algorithm I handed out in class, list the nodes in the order in which
they will be visited in a search starting at node 0. Draw the
resulting spanning tree.
- Using the depth-first search
algorithm I handed out in class, list the nodes in the order in which
they will be visited in a search starting at node 0. Draw the
resulting spanning tree.
- Suppose the edge weight on each edge is the sum of the numbers
of the nodes it connects. Using Dijkstra's algorithm as described
in section 9.3.2 of your textbook, starting with node 0, list the
nodes in the order in which they become "known." Draw the shortest
paths to 0 spanning tree.
- (2 points) Please recommend a book for me to read.
- (6 points) Consider the max heap H1:
9
4 7
3 0 6 5
2 - - - - - - -
- Draw the heap H2 that results when you add 8 to H1.
- Draw the heap that results when you remove the largest
item from H2.
- (6 points) What is the worst-case complexity (in big-oh notation)
of:
- adding an item to an N-item max heap?
- deleting the largest item from an N-item max heap?
- searching for an item in an N-item max heap?