COMP1927 15s2 Theory Answers

q4.txt

COMP1927 15s2 Exam Question 4 (Fury of Dracula)

A.
Dracula's Castle

B.
City move (Unknown City)

C.
They lose all their lifepoints

D.
Lisbon Rests
Madrid Rail
Madrid Road
Cadiz Road
Atlantic Ocean Sea
Santander Road
Santander Rail
Saragossa Rail
Alicante Rail

E.
Saragossa
Alicante

q5.txt

COMP1927 15s2 Exam Question 5 (Binary Search Trees)

A.
7
right and equal comparisons are 2, left are 1

B.
2, 42

C.
10, 33
10, 99

D.
4 comparisons, anything less than 4

E.
41
Right then max left or
Left then max right
41 is less disruptive

F.
    20
  /    \
09      42

q6.txt

COMP1927 15s2 Exam Question 6 (Weighted DiGraphs)

A.
ABGMNPQV

B.
VQKJHGFA

C.
R

q7.txt

COMP1927 15s2 Exam Question 7 (Mergesort)

A.
o s r t i n g i a s e w o s e m 
o r s t g i i n a e s w e m o s 
g i i n o r s t a e e m o s s w 
a e e g i i m n o o r s s s t w 

B.
When the input is not a power of 2, the partition size may over extend 
the end of the array, and thus a min on hi is needed

q8.txt

COMP1927 15s2 Exam Question 8 (Hash Table)

A.
average chain length is N/11 
100/11 = 9.09

B.
4

C.
9

D.
10+ceil(N/10)

E.
1

F.
for (i = 0; i<100; i++){
    insert i*11
}

q9.txt

COMP1927 15s2 Exam Question 9 (Bonus Question)

A.
Larry Page
Sergey Brin

B.
Stanford University