Erik's answers to the 331 Review questions

27.

Given the graph below, perform a breadth-first spanning tree starting at vertex 1.

The answer is: 1, 0, 3, 2, 4, 5

28. 29. 30.

What is the degree of vertex 2 in the graph above?
Who are the neighbors of vertex 2?
Are vertices 2 and 4 adjacent?

vertex 2 has degree 2 (that's how many neighbors it has)
2's neighbors are 0 and 5
No

31.

Give the adjacency matrix repesentation

x  1  1  0  1  0
1  x  0  1  0  0
1  0  x  0  0  1
0  1  0  x  1  1
1  0  0  1  x  1
0  0  1  1  1  x

x = don't care, 1 = connected, 0 = not connected

32.

Give the adjancency list representation

0: 1, 2, 4
1: 0, 3
2: 0, 5
3: 1, 4, 5
4: 0, 3, 5
5: 2, 3, 4

33.

How much time does it take to check if the edge (u,v) is in the graph if you use a matrix? adjacency list?
Matrix: O(1), just lookup edges[u][v]
List: O(n), have to search for v in list[u]

34.

What's another name for a connected, acyclic graph?
A Tree

35.

How many edges does a connected, acyclic graph have if there's n vertices?
(n-1) edges for n vertices.

36.

What is the largest number of edges a directed graph can have if it has n vertices, no self-loops, and no duplicate edges?
In a nutshell, and node can be connected to any other, so we'd have n² edges. But we're not allowed self-loops, so in total, we have n² - n = n(n-1) edges in total.

37.

Describe Kruskal's Algorithm.
See minimum spanning trees.

38.

Describe Prims's Algorithm.
See minimum spanning trees.

39.

Which is easier to hand trace, Kruskal or Prim's? While this may be a matter of opinion, Kruskal's is much easier to hand trace, since most of it can be done by inspection.

40.

Which algorithm builds a tree while having the graph connected at all times?
Prim's algorithm does, since the condition for new edges is that u is in TV and v isn't, so any newly added always have one node attached to T.

41.

What's the difference between a binary tree and a binary search tree?

42.

What is an AVL tree?
Its a special binary tree that gets balanced (if necessary) by different rotations, each time a new node is added. The tree is always near-perfect (the heights of the left and right subtrees are always withing +/- 1 of each other). See pp 555-562 for a full discussion.

43.

What is a complete binary tree?
A binary tree with n nodes and depth k is complete iff its nodes correspond to the nodes numbered 1 to n in a full binary tree of depth k. ie, the tree looks like this:

        1
    2       3
  4   5   6   7

44.

What is a full binary tree?
A full binary tree of depth k is a binary tree with 2^k-1 nodes.

45.

What is a good representation of a full/complete binary tree?
Use an array of length 2^k to represent a full/complete binary tree.

46.

For the representation in 45. how do you find the left child of a node i? How about the right child?
Left child = 2* i, right child = 2 * i + 1. If i = 1, the node is the root.

47.

Give some pseudo-code to print out the nodes of a tree in decreasing order.

Print( Node n ) {
  if( n.left ) Print( n.left );
  print n.value;
  if( n.right ) Print( n.right );
}

page 2 | page 4