CSCI 203 Data Structures Fall 2012 Exam #2
Instructions: The usual…this test is closed book, closed notes, closed
computer/phone, closed neighbor, but hopefully open mind. Write your answers in the space
provided. If you need more space, move
to the back of one of the pages and indicate where I can find your answer. Write legibly—if I can’t read it, it’s
wrong. Read through the entire test
before answering any questions in order to find the easy questions and answer
them first to maximize your score. Each
question is worth 5 points. Good luck
and have fun!
I.
TREES
A.
We can store binary trees in arrays. Draw the binary tree represented by the array
shown below.
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
index |
|
d |
r |
w |
g |
- |
m |
k |
a |
e |
- |
- |
- |
s |
y |
s |
- |
- |
b |
v |
- |
- |
- |
- |
- |
- |
j |
p |
- |
C |
z |
- |
B.
What are the three types of nodes that make
up a tree?
C.
What is the difference between a complete
and a full binary tree?
D.
The following binary tree is being used to
store a general tree. Draw the general
tree it stores.
E.
If we start counting levels with 0, how
many nodes are on level 7?
F.
How many nodes are in a full binary tree
with 7 levels?
G.
The following numbers are inserted into a
binary search tree in the order given.
Draw the resulting binary search tree.
10, 15, 13,
14, 20, 1, 4, 6, 2, 5, 8
H.
Convert the following tree into a heap.
I.
For the graph in question H, list the order
the nodes are processed for a postorder traversal.
J.
For the graph in question H, list the order
the nodes are processed for a level order traversal.
II.
GRAPHS
K.
How many edges are there in a minimal
spanning tree for a connected graph with n nodes?
L.
What properties must a graph have for
Dijkstra’s shortest path all points algorithm to work?
M.
For the graph above, find a minimal
spanning tree.
N.
For the graph above, find the shortest path
all points using Dijkstra’s algorithm.
III.
SORTING
O.
Name two sorts that have computational
complexity O(n2).
P.
Name two sorts that have computational
complexity O(n log(n)).
Q.
What is the term for a sort that preserves
the initial order of two items of equal value?
(In other words, if there are two 10’s in the list, after the list is
sorted, the 10 that came first in the unsorted list comes first in the sorted
list.)
R.
Given the array of numbers shown below,
show the results of each pass of the insertion sort in the following rows.
|
Original array |
1 |
8 |
5 |
7 |
12 |
3 |
9 |
|
Pass 1 |
|
|
|
|
|
|
|
|
Pass 2 |
|
|
|
|
|
|
|
|
Pass 3 |
|
|
|
|
|
|
|
|
Pass 4 |
|
|
|
|
|
|
|
|
Pass 5 |
|
|
|
|
|
|
|
|
Pass 6 |
|
|
|
|
|
|
|
|
Pass 7 |
|
|
|
|
|
|
|
S.
Briefly describe the Shell sort algorithm.
T.
If you have a collection of student records
that you want to be sorted by classification (freshman, sophomore, etc), and
within classification, by last name, and then within last name by first name,
in what order do you sort the three fields (classification, last name, first
name)?