Name_________________
                         CIS 350 Exam 2
                           Winter '97
(3 points)
 
 1. How does the organization of a B-tree differ from the
   organization of a binary tree?

 
 
 
 
 
 
 



 
 2. Write type declarations for a data structure which might be 
    used to implement a priority queue.

 
 
 
 
 
 




 
 3. Compare the relative efficiencies of the Prim's algorithm 
    and the depth-first search algorithm as a means of finding
    a spanning tree.











 4. What is the principle difference between Floyd's algorithm 
    and Dijkstra's algorithm?


 

 
 
                                            Name_________________

 5. Given the following heap, cut 17 out of the heap and 
  readjust the heap nodes so that FindMax will a O(1) 
  operation.

                17 
             /      \
          10         12
         /  \       /  \
        8    6    11    5 
       / \  
      7   4  



 6. Draw the binary search tree after deleting the node 
    containing E.


                     J
                /         \
              E             Q
           /     \        /   \
         D        G      M     W
       /        /   \
      A        F     H



 7. Which node becomes the pivot node for an AVL rotation 
     following the addition of F to the tree below?  Why?


           A
        /     \
       B       C 
             /   \
            D     E
          /
         F



8. 	Assuming the key values T and W are inserted (in that
   order) into the B-tree below, draw the new B-tree which
   results.

                      M-Q
               /       |       \
               E-K       O         V 
             /  |  \    / \      /   \
            A   I   L  N   P  R-S     Z


                                            Name_________________
(4 points)

 9. Indicate the order in which Kruskal's algorithm would include 
    edges in constructing a minimum spanning tree for this graph. 
                  1
      B       E ----- G
      | \  7  |       |
     5|   \   | 4     |6
      |     \ |       |
      C ----- F ----- H
          2       3








 
10. Construct the binary expression tree from the traversals 
    shown below.
 
      Inorder:  4 + 3 + 2 * 1

      Preorder: + 4 * + 3 2 1












 
11. 	Use the digraph adjacency matrix below and topologically 
sort 
    vertices 1 to 5.

        | 1  2  3  4  5
      -----------------
      1 | 0  0  1  0  0
      2 | 0  0  1  1  0
      3 | 0  0  0  0  1
      4 | 0  0  0  0  1 
      5 | 0  0  0  0  0
 

 
 

                                            Name_________________
(6 points)
 
12. 	Write a function, which receives as an input argument the
    root to a binary tree and returns a count of the number of
    leaf nodes in the binary tree. Include any type definitions 
    used in your solution.