Data Structure Final (20070625)

(15%)

(3%) If a graph has 6 vertices, with the following degrees: 1, 1, 2, 2,
3, 5. How many edges does this graph have?
Answer:
(1+1+2+2+3+5)/2=7. (See page 262, section 6.1.2 of the text.)

(3%) A graph G is represented by the following adjacency lists:

vertex 0 -> 1 -> 2

vertex 1 -> 0 -> 3 -> 4

vertex 2 -> 0 -> 5 -> 6

vertex 3 -> 1 -> 7

vertex 4 -> 1 -> 7

vertex 5 -> 2 -> 7

vertex 6 -> 2 -> 7

vertex 7 -> 3 -> 4 -> 5 -> 6

What is the sequence
of breadth first search starting from vertex 0?
Answer:
0 1 2 3 4 5 6 7 (See page 274, section 6.2.2 of the text.)

(3%) What is the sequence of depth first search of the graph G in the
previous sub-problem, starting from vertex 0?
Answer: 0
1 3 7 4 5 2 6 (See page 274, section 6.2.2 of the text.)

(3%) What is a "stable" sorting algorithm?
Answer:
A stable sorting algorithm will not chagne the relative order of already
sorted elements. In symbol, if ai = aj and i < j,
then si < sj after a stable sorting algorithm.

(3%) Given the weights of 1, 3, 4, 5, 7, 8, 12, construct a Huffman tree
with minimum weighted external path length.
Answer:

(6%) Answer the following short questions about insertion sort.

(2%) What is the average and worse case time complexity of insertion
sort of n numbers?
Answer: O(n2),
O(n2)

(2%) Given a random permutation of a sequence from 1 to 6, what is the
sequence that exhibits the worst case behaviour of insertion sort?
Answer: 6 5 4 3 2 1

(2%) Is insertion sort stable?
Answer: Yes.

(9%) Answer the following short questions about quick sort.

(2%) What is the average and worse case time complexity of quick sort of
n numbers?
Answer: O(n2), O(n*log(n))

sequence that exhibits the worst case behaviour of quick sort?
Answer: 1 2 3 4 5 6

(3%) How do you avoid the worse case behavior of quick sort?
Answer: Use the technique of "median of three" in page 332, section 7.4 of the
text. Or you can do a random permutation before quick sort.

(2%) Is quick sort stable?
Answer: No.

(10%) Suppose that we are using 10 queues as the bins for LSD radix 10
sort. Show the contents of these queues after each of the three passes of LSD
radix sort when the input sequence is [179, 208, 306, 93, 859, 984, 55, 9,
271, 33].
Answer: See pages 356, 357, 358, Figure 7.16 of section 7.8 of the
textbook.

(10%) Consider the following undirected graph:

(5%) Find a minimum-cost spanning tree by Kruskal's algorithm. (Please
give partial results at the end of each iteration.)
Answer: (Click to
see the answer.)

(5%) Repeat (a) using Prim's algorithm.
Answer: (Click to see the
answer.)

(10%)

(5%) Please describe Dijkstra's algorithm for the single-source
all-destination shortest path problem. (Please clearly define your
notation.)
Answer: (My description is a bit formal. You
can use your own way to explain this algorithm.)
Let V denotes the set of
all vertices. Let S denote the set of vertices, including the starting
vertex a, whose shortest paths have been found. The distance between
vertices x and y is denoted by w(x, y). The shortest distance from a to x is
denoted by s(a, x).

Initially, set S={a}. For every vertex t in V-S, let s(t)=w(a, t).

Select a vertex t in V-S such that t = argy minx in S,
y in V-S {s(x)+w(x, y)}

Include t in S. Repeat step 2 and 3 until the end vertex is included
in S.

(5%) Please use the algorithm on the following graph to find the
shortest paths from the source node a to all the other nodes. (Please show
the partial result at each iteration.)
Answer: (You can also use other methods to demonstrate the
operation of this algorithm.)

Iteration

S

Seleted vertex

Shortest distance
a b c d e f

1

{a}

b

0 1 4 ∞ ∞ ∞

2

{a, b}

c

0 1 3 ∞ ∞ ∞

3

{a, b, c}

e

0 1 3 ∞ 4 ∞

4

{a, b, c, e}

d

0 1 3 7 4 ∞

5

{a, b, c, e d}

f

0 1 3 7 4 9

(10%) Consider the following AOE network:

(3%) Obtain the earliest and latest times for each vertex using the
backward-forward approach.
Answer: (Earliest time in blue, latest time
in red)

(3%) Obtain the early and late starting times for each activity.

Answer:

Activity

Early starting time

Late starting time

Critical activity

a0

0

9-5=4

No

a1

0

6-6=0

Yes

a2

5

12-3=9

No

a3

6

12-6=6

Yes

a4

6

15-3=12

No

a5

12

15-3=12

Yes

a6

12

19-4=15

No

a7

12

16-4=12

Yes

a8

15

16-1=15

Yes

a9

15

19-4=15

Yes

a10

16

21-5=16

Yes

a11

19

21-2=19

Yes

a12

16

23-4=19

No

a13

21

23-2=21

No

(2%) List all the critical paths.
Answer:

a1, a3, a7, a10,
a13

a1, a3, a5, a8,
a10, a13

a1, a3, a7, a9,
a11, a13

(2%) Can you reduce the project length by speeding up activity
a10 alone? Why or why not?
Answer: No, you
cannot reduce the project length by speeding up a10 alone.
Besides speeding up a10, you also need to speed up a9
or a11 since they are parallel in two critical paths.

(10%)

(6%) Explain the operations of any 3 uniform hash functions that have
been described in the textbook.

(1%) What is "collision" in accessing a hash table?

(3%) What is "overflow" in accessing a hash table? Describe 3 strategies
in handling overflow?

(10%) Consider the following min-max heap:

(2%) Plot the min-max heap after inserting 5 into the original heap.

Answer:

(2%) Plot the min-max heap after inserting 75 into the original heap.

Answer:

(3%) Plot the min-max heap after deleting min from the original heap.

Answer:

(3%) Plot the min-max heap after deleting max from the original heap.

Answer:

Please
indicate the modified vertieces using double circles when drawing the final
heaps.

(10%) Draw the deaps after the operations indicated next:

(2%)
Answer:

(2%)
Answer:

(3%)
Answer:

(3%)
Answer: