Exercise 2 Theory: Trees

Exercise 1:

a) Breadth-first-search on a tree is implemented easiest with recursion?
1) Yes
2) No

b) Depth-first-search on a tree is implemented easiest with recursion?
1) Yes
2) No

c) A tree is an undirected connected acyclic graph?
1) Yes
2) No

d) How many edges are there in a binary tree with n nodes?
1) n
2) n + 1
3) 2
4) n - 1

e) Suppose G is an undirected connected acyclic graph and we add an extra edge. Which of the following statements is correct?
1) G is still an undirected connected acyclic graph.
2) G is now an undirected connected cyclic graph.
3) G is now a tree.
4) None of the statements above are correct

Exercise 2:

The image presented at the task-site, shows a binary search-tree.
Below we present four (4) different ways to traverse the tree.

1 - 1, 2, 5, 4, 3, 7, 9, 8, 6, 12, 11, 14, 17, 16, 15, 18, 13, 10
2 - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18
3 - 1, 2, 4, 5, 3, 6, 7, 8, 9, 10, 12, 11, 13, 14, 16, 17, 15, 18
4 - 10, 6, 3, 2, 1, 4, 5, 8, 7, 9, 13, 11, 12, 18, 15, 14, 16, 17

a) Which answer represents a postorder traversal?
1) 1
2) 2
3) 3
4) 4
   
b) Which answer represents a preorder traversal?
1) 1
2) 2
3) 3
4) 4
   
c) Which answer represents an inorder traversal?
1) 1
2) 2
3) 3
4) 4
   
Exercise 3:

Answer the following questions with the asymptotic notation which gives the most information.
For example most algorithms have a running-time that is O(n^n) (n to the power of n), since this is a very high upper limit, while Theta(f(n))
gives both an upper and lower limit and therefore gives much more information about the running-time.

a) What is the search time in a perfectly balanced binary search tree?
1) O(log n)
2) O(n)
3) O(nlog n)
   
b) What is the search time if the search tree is a linear chain of n nodes?
1) O(log n)
2) O(n)
3) O(nlog n)
   
c) You are given a big perfectly balanced binary tree and you are looking for a specific node. You know that 
   it's in a leef node, but you know nothing about the search key. On average, will a BFS- (Breadth-first-search) 
   or DFS-search (Depth-first-search) use the least time to traverse the tree until one finds the specific node?
1) BFS will use the least time
2) DFS wull use the least time
3) DFS and BFS will use the same amount of time
4) It's impossible to predict which one that will be the fastest

Exercise 4:

a) What kind of edges (classifications) is it possible to get when you run a DFS (Depth-first-search) on a directed acyclic graph?
1) Forward edges
2) Cross edges
3) Tree edges
   
b) What kind of edges (classifications) is it possible to get when you run a DFS (Depth-first-search) on an undirected graph?
1) Tree edges and back edges
2) Tree edges and forward edges
3) Back edges, tree edges and forward edges
   
c) The image above shows a directed graph. We run a DFS (Depth-first-search) on the graph, starting in node one (1) and choosing
   nodes in ascending order. (Remember to follow the directions of the arrows.)
   
   How many forward edges and back edges do we get during the DFS-run?
1) 2 forward edges and 4 back edges
2) 1 forward edge and 3 back edges
3) 3 forward edges and 4 back edges
   
   
d) Which edge is a cross edge?
1) (1,4)
2) (7,6)
3) (6,5)
   
e) We run DFS one more time, but now we start in node one (1), and choose the nodes in descending order.
   What kind of edge is (1,4) now?
1) Tree edge
2) Forward edge
3) Cross edge