Algorithms and Data Structures (INF1, Autumn'06)
Answers for Exam Questions from 30.1.2007
Question 1
- a) False, True, True
- b) No, Yes
- c) A, B, D, G, E, C, F, H
- d) n2
- e) 3, 4, 2
- f) root 7 with left child 2 and right 8; right child of 2 is 4;
left child of 4 is 3 and right child of 4 is 5
- g) first column: 0, 4, 9, inf; second column: 0, 4, 9, 4;
third column: 0, 3, 9, 4
Question 2 (sketch)
- a) easy
- b) yes, easy
- c) easy, O(1)
- c) (sketch): create a new temporary stack s'; as long as the stack
s is nonempty, use pop to move the entry to the temporary
stack and at the same time add one to a variable storing
the current number of entries; after the stack is emptied,
restore its content (e.g. by a while loop) from s'.
Complexity is O(n) where n is
the size of the stack s
Question 3 (sketch)
- a) A pedigree for P can be formalized by a binary tree;
people are nodes with a field first_name; a mother of
a person is its left child (for example), a father is
its right child; P is a root
- b) easy
- c) 4 generation = 15 people; n generation = 2n -1
- d) use some tree traversal (e.g. inorder) and for every
node x where x.first_name="Kim" add one to some global variable
- e) In this case the pedigree is not necessarily a tree, hence
directed graph can be used to model this situation. Finding
whether pedigree is healthy can be done by using e.g. dfs
and making sure that we never discover an already visited node;
counting can be done again e.g. using dfs.