The University of Manitoba December 9, 2006 FINAL EXAMINATION PAPER NUMBER: 133 PAGE NUMBER: 1 OF 14 DEPARTMENT AND COURSE: COMP 2140 TIME: 3 hours EXAMINATION: Data Structures and Algorithms EXAMINER: Anderson & Cameron Instructions ! Aids (calculators, books, computing devices, MP3 Players, mobile telephones, other extraneous material) are not permitted. ! Answer all questions in the spaces provided on this examination paper. All pages of the examination must be handed in. ! Programming questions do not require comments unless you feel something needs to be explained that is not obvious from your code. Other programming standards used in class must be followed. ! There is a total of X marks in the examination. NAME: STUDENT NUMBER: Instructor: Section A – Short Answer 1) (2 marks each) For each of the following pairs of terms, what is the difference between the two terms? a) Open hashing and closed hashing. b) A heap ordered tree and a binary search tree. 2) (X marks) If you were using a String as a key for a hash function, why would you want to use polynomial accumulation for hashing, as opposed to simple summation of ordinal values? 3) (X marks) Why is a dummy header node useful in a linked list? The University of Manitoba December 9, 2006 FINAL EXAMINATION PAPER NUMBER: 133 PAGE NUMBER: 2 OF 14 DEPARTMENT AND COURSE: COMP 2140 TIME: 3 hours EXAMINATION: Data Structures and Algorithms EXAMINER: Anderson & Cameron 4) a) (X marks) Draw the correct expression tree for the following expression, assuming normal precedence of arithmetic operations: (12*4-6)+ 3 / (1+6) b) (X marks) What would the output be if we printed the nodes in this tree from part a) above using a postorder traversal? c) (X marks) What would the output be if we printed the nodes in this tree from part a) above using a preorder traversal? 5) Draw a sibling-and-child pointer representation of the following multi-way (general) tree. The root has three children, 2, 5, and 9. 2 has 2 children, 4 and 6. 5 has no children. 9 has 3 children, 0, 8, and 4. The University of Manitoba December 9, 2006 FINAL EXAMINATION PAPER NUMBER: 133 PAGE NUMBER: 5 OF 14 DEPARTMENT AND COURSE: COMP 2140 TIME: 3 hours EXAMINATION: Data Structures and Algorithms EXAMINER: Anderson & Cameron 3 a) (1 mark) Assume you are using a 2-3 tree with values stored only in the leaves as we did in class. Given the leaves and branches are as follows, draw the interior nodes and fill in the appropriate keys in this tree: b) (6 marks) Now Illustrate, step by step, what happens when 14 is deleted from this tree. c) (1 mark) Assume you have a 2-3 tree, with leaves and branches as follows. Draw the interior nodes and fill in appropriate key values: d) (6 marks) Illustrate, step by step, what happens when 8 is inserted in this tree. 6 9 7 3 1 12 14 12 14 3 1 The University of Manitoba December 9, 2006 FINAL EXAMINATION PAPER NUMBER: 133 PAGE NUMBER: 6 OF 14 DEPARTMENT AND COURSE: COMP 2140 TIME: 3 hours EXAMINATION: Data Structures and Algorithms EXAMINER: Anderson & Cameron Part C – Programming. All programming must be done in Java, and all data structures used must be your own. Remember that you need not write comments unless you feel they are necessary, but all other programming standards for this course should be adhered to. 1) (X marks) Write appropriate data types (i.e. a class header and data members) and an enter(int) method, for an array-based implementation of a standard FIFO queue of integers. Your insert routine should check if the queue is full and print an error message if so, and should be efficient (i.e. no shuffling data!) The University of Manitoba December 9, 2006 FINAL EXAMINATION PAPER NUMBER: 133 PAGE NUMBER: 7 OF 14 DEPARTMENT AND COURSE: COMP 2140 TIME: 3 hours EXAMINATION: Data Structures and Algorithms EXAMINER: Anderson & Cameron 2) Suppose we have a class List defining l, an array of strings and size, an integer recording the current length of that list. Write a sort() method for class List that will use the quicksort algorithm to order the elements in the list into descending order. The University of Manitoba December 9, 2006 FINAL EXAMINATION PAPER NUMBER: 133 PAGE NUMBER: 8 OF 14 DEPARTMENT AND COURSE: COMP 2140 TIME: 3 hours EXAMINATION: Data Structures and Algorithms EXAMINER: Anderson & Cameron 3) Suppose we have a directed graph stored using an adjacency list mechanism. This can be done in a similar fashion to your last Lab, by defining an unordered linked list of Edges: public class Edge { private int toVertex; // The edge is TO vertex "toVertex". private Edge next; // The next edge in the linked list for vertex i. public int getToVertex() {return toVertex;} public Edge getNext() {return next;}} } // end class Edge Class Graph stores a graph using an array of Edges. Element i in this array represents the linked list of edges connecting vertex i to its adjacent vertices. If there is an edge from vertex i to vertex j, then the linked list for vertex i contain an Edge object representing the edge to vertex j. containing vertex j. The linked lists are unordered, ordinary linked lists with no dummy nodes. Class Graph has ONLY the following data members: Class Graph { private Edge[] adjacent; //Adjacency list private int numVertices //# of vertices in the graph private boolean[] visited; //true in position i means vertex I has been visited Assume you have a constructor that will read in a graph and set these data members appropriately (including initializing the visited array to all false values). You wish to perform a Recursive Depth First Traversal on an instance of this graph. You will need two methods in class Graph to do this (fill in the skeletons below): private int getNextUnvisited(int i) { //return the next unvisited vertex connected to vertex i } public void dfTrav(int i) { //df traversal starting at a given vertex } The University of Manitoba December 9, 2006 FINAL EXAMINATION PAPER NUMBER: 133 PAGE NUMBER: 9 OF 14 DEPARTMENT AND COURSE: COMP 2140 TIME: 3 hours EXAMINATION: Data Structures and Algorithms EXAMINER: Anderson & Cameron 4) Assuming we have a BinaryTree class, where each BinaryTree has a private data member root which is a pointer to a TreeNode, along with a getRoot() method that serves as an accessor for the root, and TreeNodes are defined as follows: public class TreeNode { private int data; private TreeNode leftChild; private TreeNode rightChild; public TreeNode getLeft() {…} public TreeNode getRight() {…} public int getData() {…} } Write the following recursive static method for class BinaryTree (this method may be split into a method in BinaryTree and another in TreeNode, or done all in one place as is laid out here): public static boolean deepCompare(BinaryTree t1, BinaryTree t2) { //returns true if a deep comparison of the two binary trees returns true – remember that a //deep comparison ensures that the structure of the two tree and the values in each node are //identical from root to leaves The University of Manitoba December 9, 2006 FINAL EXAMINATION PAPER NUMBER: 133 PAGE NUMBER: 10 OF 14 DEPARTMENT AND COURSE: COMP 2140 TIME: 3 hours EXAMINATION: Data Structures and Algorithms EXAMINER: Anderson & Cameron 5) Assume you are implementing a Heap in order to support a priority queue. You are given the following definitions: public Class Heap { private static final int MAXSIZE=1000; //maximum number of values in any heap private int[] data; private int lastValidSlot; Write an appropriate constructor and a void insert(int) routine for this heap. Your insert should simply print an error message if the heap is full. The University of Manitoba December 9, 2006 FINAL EXAMINATION PAPER NUMBER: 133 PAGE NUMBER: 11 OF 14 DEPARTMENT AND COURSE: COMP 2140 TIME: 3 hours EXAMINATION: Data Structures and Algorithms EXAMINER: Anderson & Cameron 6) You are implementing an ordered linked list of integers with dummy header and trailer nodes and forward and back links (i.e. a doubly linked list). The list is not circular. Write an appropriate class definition for such a list (including its nodes, which may be an internal class if you wish), and then write appropriate routines to a) construct a new list and b) perform a delete from the list, given an integer to be deleted. If the value to be deleted is not actually in the list, your delete routine should do nothing. The End – Have a Great Holiday!
欢迎咨询51作业君
