CS-242 - DATA STRUCTURES II - TEST #1 - Sept. 30, 2005
PLEDGE: I have not violated the Honor Code in completing this test. ________________________________
READ THESE NOTES
Sign the pledge above and initial each sheet. Show all of your work.
You may omit any ONE question but you must indicate which one you want omitted by writing OMIT next to it and circling the question number.
Do not spend an excessive amount of time on any one question. All questions count the same.
If you have trouble with a question, skip it and come back to it later.
You may explain your answers if you choose to.

1. During the process of using the DSW algorithm to balance a binary search tree a backbone is created. If the backbone contains the following data (2, 3, 5, 7, 11, 13, 17, 19) draw the binary search trees generated by successive left rotates.
   
   
   
   
   
   
   
   
   
   
   
   
2. A particular binary search tree holds 2001 nodes, numbered 0 to 2000. If the tree is perfectly balanced top-to-bottom and left-to-right what is the index of the root node? __________
   
   
3. An AVL tree contains 5000 nodes. What is the maximum number of levels it can contain? _________
   
   
4. AVL trees require that the difference in the number of levels in the right subtree and the left subtree of any node differ by no more than one. This difference is called the balance factor of the node. If a node is deleted using the standard binary search tree deletion algorithm what is the largest balance factor that can result from the deletion _________
   
   
5. Let H be a heap with N elements using the standard array implementation.
   A) What is the index of the parent of the node with index i in H? ________
   
   B) What are the indices of the children of node N in H? left ________ right _______
   
   
6. How may one determine if a node with index x in H is a leaf?
   
   
   
   
   
7. An array, A, contains the following data (9, 22, 17, 6, 30, 40, 25, 2, 50, 25, 35). Draw the exact heap that results from using Floyd's algorithm to build a heap on the data set given above.
   
   
   
   
   
   
   
   
   
8. Draw the B-tree that would result from adding the value 29 to the B-tree in figure 7.7(d) on page 308 in the text.
   
   
   
   
   
   
   
   
   
   
9. Draw the B-tree that would result from deleting the value 24 from the B-tree in figure 7.8(f) on page 309 in the text.
   
   
   
   
   
   
   
   
   
   
10. A B-tree contains N data items and has a branching factor of 100.
    A. If each node is nearly filled, what is the maximum number of nodes which must be accessed to find a particular key in the tree? ________
    HINT: Try solving the problem using N = 1 million
    
    B. If each node contains the minimum number of data items, what is the maximum number of nodes which must be accessed to find a particular key in the tree? ________
    
    
11. There are at least 2 reasons why B^* trees normally have more keys per node than B-trees. Give and explain those reasons.
    
    
    
    
    
    
    
    
    
12. Give pseudocode to write all of the keys in a B+ tree in order to an array, A.
    
    
    
    
    
    
    
    
    
    
    
13. Explain why a simple prefix B+ tree is an improvement over an ordinary B+ tree.
    
    
    
    
    
    
    
14. An aircraft explodes in midflight and scatters debris over an area 1000 meters wide by 1000 meters long. Workers with highly accurate GPS units map the debris field and record the x and y coordinates and a description of each piece of debris (0<=x,y<=1000).
    A) What data structure that we have studied is most appropriate for storing this data? _____________________
    
    B) Draw the tree-structure generated by inserting the following coordinates in the order given.
    (400, 300), (20, 50), (700, 200), (700,400), (250, 450), (220, 180), (100, 150)
    
    
    
    
    
    
    
    
    
15. Write C++ or good pseudocode to determine if a rectangle defined by (xmin, xmax, ymin, ymax) is inside a node defined by (xlo, xhi, ylo, yhi, ID, dataPointer) in an R-Tree. You may assume that both the rectangle and the R-Tree nodes are objects with the attribute names given above.
    
    
    
    
    
    
    
    
16. Upper-case English words are stored in a trie named Ti. Each node in Ti contains several cells and each cell contains a 4 byte pointer to a sub-trie. There are several ways to implement trie nodes. For each node implementation given below determine the best and worst case space requirements for the node.
    A) fixed-size (static) array of 26 cells.
    
    
    
    B) linked list of cells; each representing a letter contained in the root of its corresponding sub-trie.
    
    
    
    C) a dynamically allocated array of just enough cells to hold the required letters
    
    
    
    

---

Top of this page         Home page