Block 7: Trees and graphs

Home > Preview

The flashcards below were created by user ccc on FreezingBlue Flashcards.


  1. Draw a complete binary search tree containing 1,2,3,4,5 and 6.
    Image Upload
  2. Here is an adjacency matrix for a weighted directed graph. Cells contain weights
    of edges, empty cells mean there is no edge. Complete the drawing of the graph to
    the right by adding directed edges and weights.
    Image Upload
    Image Upload
  3. In the same graph as B), one path from A to E is A→C→E, with a combined
    weight of 9.
    Write three other paths from A to E, and the combined weight of each.
    • A → D → E (11)
    • A → B → C → E (9)
    • A → C → D → E (15)
  4. If a multigraph has E edges, what is the maximal/minimal number of nodes it may have? Answer in O notation. Assume the graph is undirected and connected (no unreachable nodes).
    Maximal N = E+1 , O(E)

    Minimal N = 1, O(E)
  5. Given this weighted directed graph, we use Dijkstras Algorithm (3 points)
    to find the shortest path from A to all other (reachable) nodes. Write the nodes it
    reaches and the length of the shortest path it finds for each. Write them in the
    order that the algorithm would find them.
    Image Upload
    • B 2
    • D 3
    • C 4
    • F 5
  6. List the Nodes of the same graph in breadth
    first order starting from E. (2 points)
    Image Upload
    E,D,C,F,B
  7. ) In an adjacency matrix for the same graph, where each cell has either a weight
    or -1 if there is no edge, how many cells would have -1 in them? Also write a
    formula for calculating this number for any graph, in terms of number of nodes N
    and number of edges E.

    Image Upload
    • 6 * 6 - 9 = 27
    • N^2 - E
  8. If a binary tree has N nodes, what is the maximal/minimal height the tree may
    have (you may answer in O notation)
    Maximal H = N-1 , O(N) 

    Minimal H = O( log(N) )
  9. If a graph has E edges, what is the maximal/minimal number of nodes it may
    have? Answer in O notation. Assume the graph is undirected, connected (no
    unreachable nodes) and not a multigraph.
    Maximal N = O(E) 

    Minimal N = O( sqrt(E) ) [E=n^2]
  10. A directed weighted graph is represented as an adjacency matrix g, such that g[i][j]
    is a boolean that is true if and only if there is an edge from node i to node j.
    A) Write the body of the method:
    public static int highestDegree(boolean[][] g)
    That computes the highest number of outgoing edges of any node.
    • int size = g.length;
    • int top = 0;

    • for (int i = 0;i<size;i++) {
    • int deg = 0;
    • for (int j = 0;j<size;j++) {
    • if (g[i][j]) deg++;

    • if (deg>top) top=deg;
    • }
    • return top;
  11. If the graph g has N nodes and E edges, how many cells in g contains false?
    N^2 - E
  12. Define a binary search tree (compared to trees in general).
    • Binary tree, each non-leaf node has two children.
    • The element in each node must be greater than or equal to all elements in
    • the left child, and lesser than all elements in the right child
  13. If a binary tree has N nodes, what is the maximal/minimal height the tree may
    have (you may answer in O notation)
    Maximal H = N-1 , O(N)

    Minimal H = O( log(N) )

Card Set Information

Author:
ccc
ID:
329518
Filename:
Block 7: Trees and graphs
Updated:
2017-03-14 16:23:56
Tags:
Block Trees graphs
Folders:

Description:
Block 7: Trees and graphs
Show Answers:

Home > Flashcards > Print Preview