15s2

COMP1927 15s2 Exam Question 6 (Weighted DiGraphs)

A. 2.5 (A B G M N P Q V) (checked 1)


B. 3.1 (V Q K J H G F A) (checked 1)


C. R is not visitable from any other node

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 w s 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. Dictates the end of each partition when merging from the bottom up. i + 2*m - 1 can overflow on the last outer loop pass when log_2(n) is not a whole number, so we take min with hi, the max array index

COMP1927 15s2 Exam Question 8 (Hash Table)

A. avg length = 100/11 = 9 (approx)


B. 4 (including 42)


C. 9


D. ceil(N/11) where N is the total number of items inserted

E. 0 (ie an empty list, no items to compare)

Confusing question, but if the N items are the same sequence as D, then floor(N/11)

F. for (int i = 0; i < 100*11; i *= 11) {
		insert(h(i), table);
	}