ࡱ> ` Objbj 4DF7TTTT$ $ $ 8 88 2|Xnnn+++#%%%%%%$h>I$ ӲX+ITTnne!^ F Txn$ n# # X$ Snp F[U/t0C(SS$ g+"M ey+++IIj+++8 8 8 Dc|pD8 8 8 |p8 8 8 TTTTTT  Points off 1 2 3 4 Total off Net Score  CS 307 Final Fall 2005 Name__________________________________________ UTEID login name _______________________________ TAs Name ___________________________ Instructions: Please turn off your cell phones. There are 4 questions on this test. You have 3 hours to complete the test. You may not use a calculator on the test. When code is required, write Java code. Ensure your answers are legible. You may add helper methods if you wish when answering coding questions. When answering coding questions assume the preconditions of the methods are met 1. (2 points each, 40 points total) Short answer. Place you answers on the attached answer sheet. If the code contains a syntax error or other compile error, answer Compiler error. If the code would result in a runtime error or exception answer Runtime error. If the code results in an infinite loop answer Infinite loop. Recall that when asked for Big O your answer should be the most precise Big O function. For example Selection Sort has an average case Big O of O(N^2), but per the formal definition of Big O it is correct to say Selection Sort also has a Big O of O(N^3). Give the most precise Big O function. (Closest without going under.) A. The following numbers are inserted, one at a time, in the order shown into a binary search tree with no checks to ensure or maintain balance. (i.e. the traditional nave insertion algorithm.) The tree is initially empty. Draw the resulting tree. 72, 33, 9, 12, 38, 101 For parts B - F consider the following binary tree. For each question assume when a node is processed the value in the node is printed out by the statement: System.out.print( currentNode.getData() + " " );         B. What is the output of a preorder traversal of the above tree? C. What is the output of an inorder traversal of the above tree? D. What is the output of a postorder traversal of the above tree? E. What is the output of a level order traversal of the above tree? F. Is the binary tree shown above a binary search tree? G. If 1000 elements are inserted into a Binary Search Tree using the nave insertion algorithm, what is the expected (average case) height of the resulting tree? (The height of a tree is the number of links from the root to the deepest leaf. The height of the tree on this page is 3.) Recall the following methods from the ArrayList class: booleanadd(Object x) Add x to the end of list. returns true.Objectset(int index, Object x) Replaces the element at the specified position in this list with the specified element.voidadd(int index, Object x) Inserts x at position index, sliding elements at position index and higher to the right (adds 1 to their indices) and adjusts sizeObjectremove(int index) Removes element from position index, sliding elements at position index + 1 and higher to the left (subtracts 1 from their indices) and adjusts size returns the element formerly at the specified positionObjectget(int index) return the element at the given index H. What is the output of the following code? ArrayList li = new ArrayList(); for(int i = 0; i < 5; i++) li.add(0, i); for(int i = 0; i < li.size(); i++) System.out.print( li.get(i) + ); I. What is the output of the following code? ArrayList li = new ArrayList(); String[] letters = {A, C, B, M, S, E, F}; for(int i = 0; i < letters.length; i++) li.add( letters[i] ); for(int i = 0; i < li.size(); i++) li.remove( i ); for(int i = 0; i < li.size(); i++) System.out.print( li.get(i) + ); J. What is the output of the following code? Stack s = new Stack(); for(int i = 5; i < 12; i++) s.push(i); int limit = 5; while( limit > 1 ) { s.pop(); limit--; } for(int i = 0; i < 3; i++) { System.out.print( s.top() + ); s.pop(); } K. Draw the contents of the Queue q2 after the following code has completed. Clearly label the front and back elements of the queue. Queue q1 = new Queue (); for(int i = 7; i >= 3; i--) { q1.enqueue(i); q1.enqueue(i); } Queue q2 = new Queue (); int temp; while( !q1.isEmpty() ) { temp = q1.front(); if( temp % 2 == 0 ) q2.enqueue( q1.dequeue() ); else q1.dequeue(); if( !q1.isEmpty() ) q2.enqueue( q1.dequeue() ); } L. What is the output of the following code? Stack s1 = new Stack(); Queue q = new Queue(); for(int i = 0; i < 4; i++) { s1.push(i); q.enqueue(i); } Stack s2 = new Stack(); while( !s1.isEmpty() ) { s2.push( q.dequeue() ); s2.push( s1.pop() ); } while( !s2.isEmpty() ) System.out.print( s2.pop() + ); M. Briefly explain why a Stack class should not extend a pre existing List class. N. In Java there are two ways of creating generic data structures. The first method involves storing variables of type Object and relying on the fact that all objects are descendants of the Object class. The second method relies on parameterized data types, declaring the data type a particular data structure will hold when it is declared. For example the declaration Stack s1 = new Stack(); declares a Stack that holds Integer objects only. Briefly explain biggest reason the second method, (generic data structures based on parameterized types), is better than the first method (storing variables of type Object and relying on inheritance and polymorphism). O. What is the average case Big O for inserting 1 item into a binary search tree using the traditional nave algorithm? There are initially N items in the tree. P. What is the average case Big O for inserting N items into a binary search tree using the traditional nave algorithm? The tree is initially empty. Q. What is the worst case Big O for inserting N items into a binary search tree using the red black tree algorithm? The tree is initially empty. R. Briefly explain why it is good practice to have an Iterator for a Linked List class. S. In general what determines the length of the code for a particular character or symbol in a Huffman encoding scheme? T. On the last assignment you were to conduct an experiment that involved adding integers in ascending order to a binary search tree. If the binary search tree class uses the traditional nave algorithm for adding and the add method is written recursively a stack overflow error occurred. Briefly explain why this happens. 2. (Binary Search Trees, 20 points) Complete a method for a Binary Search Tree class that returns the kth smallest item. If k is equal to 1, the smallest value in the Binary Search Tree is returned. If k is equal to 2, the second smallest value in the Binary Search Tree is returned. And so forth. Important. The space requirement for your method must be no worse than O(h) where h is the height of the tree. If there are N elements in the tree and your method requires O(N) space, you will lose significant points on this question. Hint: You can use an array of ints of length 1 to track how many nodes you have visited. As an example, consider the following Binary Search Tree:  If the Binary Search Tree object, t refers to the above tree the following would be the result to various calls to getKth. t.getKth(1) would return 30. t.getKth(2) would return 40. t.getKth(3) would return 45. t.getKth(9) would return 300. Here is the BinarySearchTree class: public class BinarySearchTree { private TreeNode myRoot; private int mySize; // returns the number of items in this Binary Search Tree public int size() // to be completed by the student /* find the kth smallest item in the tree. pre: 0 < k <= size() post: return the kth smallest item */ public Comparable getKth(int k) // other methods not shown } Here is the TreeNode class: public class TreeNode { public TreeNode() public TreeNode(Object initValue) public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight) public Object getValue() public TreeNode getLeft() public TreeNode getRight() public void setValue(Object theNewValue) public void setLeft(TreeNode theNewLeft) public void setRight(TreeNode theNewRight) } Imporant: Briefly explain you algorithm. (3 points) Complete the getKth method on the next page. You can add a helper method if you wish. /* find the kth smallest item in the tree. pre: 0 < k <= size() post: return the kth smallest item */ public Comparable getKth(int k) { 3. ( Working with Data Structures, 20 points) A graph consists of a set of vertices and a set of edges that connect the vertices. Vertices are analogous to the nodes of a linked list or a binary tree and edges are analogous to the links between nodes of a linked list or binary tree. In an undirected graph if an link exists between two nodes movement is allowed back and forth, from one node to another, in either direction. This question involves undirected graphs. Here is an example of a graph. In the example each node is numbered 0 to N-1 where N is the number of nodes in the graph. Nodes are specified by an integer.  SHAPE \* MERGEFORMAT  One method for representing a graph is with an adjacency matrix. The adjacency matrix is a square 2D matrix of booleans. Each row represents a node. Elements in the row are true if a link exists between the node specified by the row and the node specified by the column. Elements are false if no direct link exists between the nodes represented by the row and the column. For example, the adjacency matrix for the graph shown above would be: node0123456780falsetruefalsefalsefalsefalsefalsefalsefalse1truefalsefalsetruefalsetruefalsefalsefalse2falsefalsefalsetruefalsefalsefalsefalsefalse3falsetruetruefalsefalsefalsetruefalsefalse4falsefalsefalsefalsefalsetruetruefalsefalse5falsetruefalsefalsetruefalsetruetruetrue6falsefalsefalsetruetruetruefalsefalsefalse7falsefalsefalsefalsefalsetruefalsefalsefalse8falsefalsefalsefalsefalsetruefalsefalsefalse Complete the following method that is a member of the Graph class: /* determine the nodes that are within numLinks or fewer links of the specified node. pre: 0 <= nodeNumber < size(),numLinks > 0 post: return an ArrayList of Integers that are within numLink links of nodeNumber. There are no duplicates in the returned ArrayList. */ public ArrayList getNodes(int nodeNumber, int numLinks) Here are some examples of results to calls to getNodes given the example graph shown on the previous page: Value of nodeNumber Value of numLinksValues in the returned ArrayList. The values in the ArrayList do not need to be in sorted order.011021, 3, 5110, 3, 5120, 2, 3, 4, 5, 6, 7, 8130, 2, 3, 4, 5, 6, 7, 8213221, 3, 6230, 1, 3, 4, 5, 6240, 1, 3, 4, 5, 6, 7, 8613, 4, 5 nodeNumber is not included in the returned ArrayList, unless the node is self looping. A self looping node has a link that goes to itself. In the example shown none of the nodes are self looping. Here is the Graph class. public class Graph { private boolean[][] myAdjacencyMatrix; // myAdjacencyMatrix is a square matrix. // myAdjacencyMatrix.length is always equal to the number // of nodes in the graph. In other words, the number of rows // and the number of columns in the matrix are always equal // to size() // return the number of nodes in this Graph public int size() // students are to complete this method /* determine the nodes that are within numLinks or fewer links of the specified node. pre: 0 <= nodeNumber < size(),numLinks > 0 post: return an ArrayList of Integers that are within numLink links of nodeNumber. There are no duplicates in the returned ArrayList. */ public ArrayList getNodes(int nodeNumber, int numLinks) } Here is a summary of methods from the ArrayList class. boolean HYPERLINK "http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html" \l "add(E)" add(AnyType o) Appends the specified element to the end of this list.void HYPERLINK "http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html" \l "add(int, E)" add(intindex, AnyTypeelement) Inserts the specified element at the specified position in this list.void HYPERLINK "http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html" \l "clear()" clear() Removes all of the elements from this list.boolean HYPERLINK "http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html" \l "contains(java.lang.Object)" contains(AnyTypeelem) Returns true if this list contains the specified element.void HYPERLINK "http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html" \l "ensureCapacity(int)" ensureCapacity(intminCapacity) Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.AnyType HYPERLINK "http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html" \l "get(int)" get(intindex) Returns the element at the specified position in this list.int HYPERLINK "http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html" \l "indexOf(java.lang.Object)" indexOf(AnyTypeelem) Searches for the first occurrence of the given argument, testing for equality using the equals method.boolean HYPERLINK "http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html" \l "isEmpty()" isEmpty() Tests if this list has no elements.AnyType HYPERLINK "http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html" \l "remove(int)" remove(intindex) Removes the element at the specified position in this list.AnyType HYPERLINK "http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html" \l "set(int, E)" set(intindex, AnyTypeelement) Replaces the element at the specified position in this list with the specified element.int HYPERLINK "http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html" \l "size()" size() Returns the number of elements in this list. Complete the method getNodes on the next page. Important: Briefly explain you algorithm. (3 points) /* determine the nodes that are within numLinks or fewer links of the specified node. pre: 0 <= nodeNumber < size(),numLinks > 0 post: return an ArrayList of Integers that are within numLinks links of nodeNumber. There are no duplicates in the returned ArrayList. */ public ArrayList getNodes(int nodeNumber, int numLinks) Scratch Paper Scratch Paper 4. (Implementing Data Structures, 20 Points) Implement the enqueue method for a priority queue. A priority queue is like a regular queue except that each element that is enqueued is also given a priority. When added an item moves in front of all items that have a lower priority than it. In this priority queue class priorities are stated with ints. 1 is the highest priority. The maximum positive integer is the lowest priority. This priority queue class uses a native array of PriPair objects as its internal storage container. A PriPair object holds a single Object, the data, and a single int, the priority of that data. The front of the queue is always at index 0 in the array. The array may have extra capacity in it. Here is an example of what the priority queue may look like at a give instance in time: array index: 0 1 2 3 4 5 6 Apple priority: 2Grape priority: 4Apricot priority: 12Quince priority: 14Banana priority: 14nullnullFront of Back of Queue Queue If the value Berry were enqueued with a priority of 14 the queue would now look like this: array index: 0 1 2 3 4 5 6 Apple priority: 2Grape priority: 4Apricot priority: 12Quince priority: 14Banana priority: 14Berry priority: 14nullFront of Back of Queue Queue If the value Orange were enqueued with a priority of 1 the queue would now look like this: array index: 0 1 2 3 4 5 6 Orange priority: 1Apple priority: 2Grape priority: 4Apricot priority: 12Quince priority: 14Banana priority: 14Berry priority: 14Front of Back of Queue Queue Here is the PriPair class. public class PriPair { public PriPair(int priority, Object data) public int getPriority() public Object getData() // implementation and other methods not shown } Here is the PriorityQueue class public class PriorityQueue { private PriPair[] myCon; private int myBack; // myBack holds the index of the current last element in the // queue // resizes the internal storage container, doubling the size. private void resize() // students are to complete this method /* enqueue data into the proper spot in this priority queue pre: priority > 0 post: data enqueued to the proper spot in this priority queue based on priority */ public void enqueue(Object data, int priority) { Scratch Paper Scratch Paper Scratch Paper Scratch Paper Scratch Paper Name:_______________________________ TAs name: ___________________________ Answer sheet for question 1, short answer questions A. B. C. D. E. F. G. H. I. J. K. L. M. N. O. P. Q. R. S. T.     CS 307 Final Fall 2005  PAGE 16 77 9 17 13 37 root of tree 97 75 75 70 8 7 6 5 300 200 100 30 45 40 50 4 3 2 1 0 150 85 GIkstW X 6 3M !"#$%&39:=?AEGHIJKLMwh@h~7hqjhqCJUmHnHujhqUmHnHujh9/CJUmHnHujhJCJUmHnHuhJOJQJ^JhJ5>*\h9/h8s hJCJ h3hJ4klmnopqrs$If DN{NOstkd$$IfTlִHT  tt``````06    4 laT  + M r  W ` 6 7 8 23NO^ 0^`0 & Fgd9/gd9/ & FOPQ!#$&456789;<=@AFGLNOPQ  !^ 0^`0_`a1 $IfgdJ $$Ifa$gdJ 0^`0+/239:=QRT $%OQWX^hikl򘇘why5CJaJh"CJaJ hy5h"CJOJQJ^JaJhy5h"CJaJhy50J5CJ\hy50JCJhy5h@CJaJh"h0J5CJ\h0JCJh@h@CJOJQJ^Jh@0J5CJ\ h@CJh@0JCJ+12:g[M $7$8$H$Ifgdy5 $$Ifa$gdJkd$$If-0%q 0634-abpPeYH:  !$IfgdJ0$If^`0gdJ $$Ifa$gdJkd$$If-(0%q 0634-abpPQX7eYK $7$8$H$Ifgdy5 $$Ifa$gdJkd$$If-0%q 0634-abpl678?BMOtuvxCFGrøòxxtgxxhy5hy5OJQJ^Jh0h0OJQJ^Jhy5OJQJ^JhR+OJQJ^Jhy5hqh"h"0JCJ\h"CJaJ h"CJh"0J5CJ\h"0JCJ h@CJhy5h@CJaJhy5CJaJ hy5hy5CJOJQJ^JaJhy5hy5CJaJ&78?ug[M $7$8$H$Ifgdy5 $$Ifa$gdJkd$$If-0%q 0634-abpuvwxg]]]]]]]]] 0^`0kdv$$If-0%q 0634-abp ABCqr  .?@c 0^`0gdR+ 0^`0+12;=>JKTYtuyz¸細vhhJOJQJ^JhfihROJQJ^Jh["OJQJ^J h["h["hJOJQJ^JhhJhRhfiOJQJ^JhR+OJQJ^JhOJQJ^JhfihfiOJQJ^JhR+hK;|h0hy5hy5h0OJQJ^J."6BMPQm*+Xu7> ! 0^`0>Oe0?ORS~  ^`  !gd !Tde}    %7?r  #$Q+HвпЎЊhhQh3hOJQJ^Jh3h3OJQJ^JhOJQJ^JhhOJQJ^Jh3h3hOJQJ^JhhhJOJQJ^JhhOJQJ^JhOJQJ^JhJh3   _`a IJK7 8 9 !gd !0^`06 7 < !!!""""("N"q"&#'#1#6#;##$$$k$l$m$$$$$$$$T%_%q%z%ygg#hBfhBfOJQJ^JmHnHuhBfCJmHnHujhBfCJUmHnHuhCJmHnHuhhJmHnHuhBfmHnHuhhmHnHu h Mh M h3h3 h35h5h5hBf>* hBf5hBfh MhJh h3hQh-&!!&#'#$$l$m$$$$$$$$$$$$$$$$$$$$$$  !gd M !$$$$S%T%q%%%%%%%&)&>&?&z&&&&&'D'E'a'c'd''  !gdBf !z%{%|%%%%%%%%%%%%%%& &*&1&'D'a'c'd'p't'պդ~kkXIhrOJQJ^JmHnHu%h5CJOJQJ^JaJmHnHu%hBfCJOJQJ^JaJmHnHu%h3CJOJQJ^JaJmHnHu%hrCJOJQJ^JaJmHnHu+hBfhBfCJOJQJ^JaJmHnHu#h5hBfOJQJ^JmHnHuh5mHnHuhBfmHnHu#hBfhBfOJQJ^JmHnHuhBfOJQJ^JmHnHut'x'''''''''''' (((+(G(J(L(e(f(h(j(((((((((((())))R)ů~sjh3mHnHuh35mHnHuhBfCJmHnHu%h3CJOJQJ^JaJmHnHu%hrCJOJQJ^JaJmHnHu+hrhrCJOJQJ^JaJmHnHuhBfmHnHu+hBfh5CJOJQJ^JaJmHnHuh5mHnHu#h5h5OJQJ^JmHnHu'''''' (*(+(H(f(((()))G)H)I)J)K)L)M)N)O)P)Q)R)  !Rgdrgdr !R)_)e)f)~)))))9*:*;*<*=*B*N*i*k*Y+Z+x+|+++++,3,A,,,,ңvmvmdmdmm`\XT\h%h[hJhzh[mHnHuhzmHnHuhJmHnHuhnmHnHuh{[mHnHu#hnh3OJQJ^JmHnHuh3OJQJ^JmHnHuhnhBfmHnHuhBfCJmHnHuh8mHnHuhnOJQJ^JmHnHu#hnhnOJQJ^JmHnHuhnhnmHnHuR))))*:*<*Z+[+,,,,,,,...........  !$IfgdG  !gdn !,,,,,,,,,,,,,-----D.P........//I/J/////// 0!0X0Y000000000Źű|h%h%OJQJ^J h%h8h1I h%h% hJhJh[h1Ih[CJaJhnCJaJhJhJ6h8hJ!jWhJhJOJQJU^JjhJUmHnHujhJOJQJU^JhJOJQJ^J0...................../ /////Ff, Ffc Ff  !$IfgdG/ /&/+/1/7/=/C/I/J/L/R/W/\/b/h/n/s/y/////////FfFf  !$IfgdG/////////////////////0 0000 0FfPFf  !$IfgdG 0!0#0)0/050;0A0F0L0R0X0Y0[0a0g0m0s0y0~0000000 !FfFf  !$IfgdGFf00101\11,2-22222$3  !$If ! 00111.1/1N1[12*2-2223334(444466I6L6777777777777ؼ{wswsms h4_0Jh4_h_4Nh_4NOJQJ^Jh%hOJQJ^Jh8OJQJ^JhOJQJ^JhhOJQJ^Jh hn6hnhOJQJ^J hnh1I hnhnhnOJQJ^Jh/OJQJ^Jh1IOJQJ^Jh%OJQJ^J%$3%3'3)3+3qfff  !$Ifkd!$$IflF f _ t06    44 la+3,3.30383qfff  !$Ifkd4"$$IflF f _ t06    44 la8393;3=3E3qfff  !$Ifkd"$$IflF f _ t06    44 laE3F3H3J3a3qfff  !$Ifkd"$$IflF f _ t06    44 laa3b3d3f3}3qfff  !$Ifkdc#$$IflF f _ t06    44 la}3~3333qfff  !$Ifkd#$$IflF f _ t06    44 la33333qfff  !$Ifkd-$$$IflF f _ t06    44 la33333qfff  !$Ifkd$$$IflF f _ t06    44 la33333qccc  !$IfgdGkd$$$IflF f _ t06    44 la33333qccc  !$IfgdGkd\%$$IflF f _ t06    44 la333444445555 6qkkkkkkkkkkk !kd%$$IflF f _ t06    44 la 66H666777777778$If $$Ifa$  !gd ! 77N8O8R8S8T8[8^8888889 9 9 99 9)9{9|999999999: :(:):*:::::::::::::::e;f;t;u;;;;:<;<<<C<D<E<<<<ƾжƾƾЫƥƾƥƾж h4_0JhcLhcL0JPJhcL0JPJh4_CJaJh4_ hcL0J h4_0J$h4_0J5CJOJQJ\^JaJh4_0J5\jh4_0J5U\A888{9g^X$If $$Ifa$kd&&$$If-0u%g 0634-abp{9|99:g^X$If $$Ifa$kd '$$If-0u%g 0634-abp: :)::g^X$If $$Ifa$kd'$$If-0u%g 0634-abp::::<g^X$If $$Ifa$kd($$If-0u%g 0634-abp:<;<D<<g^X$If $$Ifa$kd)$$If-0u%g 0634-abp<<<<<<<=m=n=u=v=w=~======>>>_>`>g>h>j>>>>>>?? ? ??^?_?`?g?h?i????????M@N@R@S@T@@@@@@@@hcL0JPJ hcL0J h4_0JhcLhcL0JPJ$h4_0J5CJOJQJ\^JaJh4_0J5\h4_CJaJh4_ h4_0Jjh4_0J5U\=<<<=g^X$If $$Ifa$kd*$$If-0u%g 0634-abp==>>g^X$If $$Ifa$kd+$$If-0u%g 0634-abp>>>^?g^X$If $$Ifa$kdw,$$If-0u%g 0634-abp^?_?h?M@g^X$If $$Ifa$kd^-$$If-0u%g 0634-abpM@N@S@@g^X$If $$Ifa$kdE.$$If-0u%g 0634-abp@@@ AVAWAXAYAZA[A\AgaaXXXXXXX  !gd?  !kd,/$$If-0u%g 0634-abp @@A AA!A+A,AZA[A\A_ABBBBBBBB2CCCCCCCDDDDDDDDDEոŤŤyohydh C hGhGhGOJQJ^Jh =h2MOJQJ^JhJhGh2Mhy hyhy hyhJh8OJQJ^Jh{[OJQJ^Jh%h? OJQJ^J h8h8h8mHnHuh8 h85h? h? h? OJQJ^J h? h? h? OJQJ^J$\AAABBDDEEFFFAFUFiFFFFFF$ !$Ifa$gd2M !  !gd? E E~EEFF)F,F0F4F5F?F@FAFIFRFTFUFhFiFjFqF|FFFFFFFFFFFFFFFFFFFFFGG@GMGaGgGjGnGsGyG{GGGGGGGGGG᫞h2MhGOJQJ^JhGOJQJ^J hyh2M h2Mh2M h2MhGh2Mh2MOJQJ^Jh2MOJQJ^JhOJQJ^JhGh2MhGh2MOJQJ^J>FFFF("" !kd0$$Ifl֞3 e t0644 laFF?G@GMGGGGGGGH H$ !$Ifa$gdG  !gdG ! GGGGGGGGGGGGHH H H^HHHHHHHHHHIIIIIIII"I+I-I.IAICIJIUIXIYIbIkInIoIxIIIIIIIIJ&J-J6JJJJJJJȻȻh_h =OJQJ^Jh =hJh =h COJQJ^Jh Chh2MhGOJQJ^JhGOJQJ^JhOJQJ^Jh2MhG h2MhGA H H8H(  !gdGkd0$$Ifl֞3 .| t0644 la8H_H`HHHHII.IBIYIoIII$ !$Ifa$gdG  !gdG ! IIIJ%  !gdGkd1$$Ifl֞3q ! t0644 laJJ5J6JKJyJJJJKK6KKKKKKKKKLQLeLLLLLLLM !JKJKKKKKLLLLM?MMMMNNDNENGNHNJNKNMNNNPNkNmNnNtNuNwNxNzN{NNNNNNNNNNNNNķ|vvvvvv hGCJ h0JmHnHu hG0JjhG0JUhGh3hBjhBUh-h|.hJh =h_OJQJ^Jh_OJQJ^Jh =hOJQJ^JhOJQJ^Jh =OJQJ^Jh =h =OJQJ^Jh =.MM!M?MeMfMMMMMMMMMMMMMMMMMMMMMM  !gd- !  !gd|.MMMMMMMMMMMMMMMMMMMMMMMMMNNNN  !gd-NNNN N N NNNNNNNNNNNNNN!N"N#N$N'N(N)N*N-N  !gd--N.N/N0N3N4N5N6N7N8N9NN?N@NCNDNFNGNINJNLNMNONPNyNzN{N  !gd-{NNNNNNNNNNNNNNNNNNNNNNNNNNNN 7$8$H$gdJgd9/gd NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNOOOOh-hJ#hGB*CJ$OJQJ^JaJ$phhG hGCJ (NNNNNNNNNNNNNNNNNNNNNNNNNNNgdgdgd 7$8$H$gdJNNNNNNNOOOO  !gd-gd9/gd 7$8$H$gdJ 21h:p-/ =!"#$% $$If!vh55`5`5`5`5`55`#v#v`#v#v`:V l0655`55`4aT$$If!vh55"#v#v":V - 0655q/ 34-p$$If!vh55"#v#v":V -( 0655q/ 34-p$$If!vh55"#v#v":V - 0655q/ 34-p$$If!vh55"#v#v":V - 0655q/ 34-p$$If!vh55"#v#v":V - 0655q/ 34-pDd D  3 @@"?$$If!v h5]5R5R5R5R5R5R5R5 R5 R#v]#v R:Vl t65 / /  "kd$$Ifl C9 / t06((((44 la$$If!v h5]5R5R5R5R5R5R5R5 R5 R#v]#v R:Vl t65 / "kd$$Ifl C9 / t06((((44 la$$If!v h5]5R5R5R5R5R5R5R5 R5 R#v]#v R:Vl t65 / "kd $$Ifl C9 / t06((((44 la$$If!v h5]5R5R5R5R5R5R5R5 R5 R#v]#v R:Vl t65 / "kdP$$Ifl C9 / t06((((44 la$$If!v h5]5R5R5R5R5R5R5R5 R5 R#v]#v R:Vl t65 / "kd$$Ifl C9 / t06((((44 la$$If!v h5]5R5R5R5R5R5R5R5 R5 R#v]#v R:Vl t65 / "kd$$Ifl C9 / t06((((44 la$$If!v h5]5R5R5R5R5R5R5R5 R5 R#v]#v R:Vl t65 / "kd$$Ifl C9 / t06((((44 la$$If!v h5]5R5R5R5R5R5R5R5 R5 R#v]#v R:Vl t65 / "kdt$$Ifl C9 / t06((((44 la$$If!v h5]5R5R5R5R5R5R5R5 R5 R#v]#v R:Vl t65 / "kd=$$Ifl C9 / t06((((44 la$$If!v h5]5R5R5R5R5R5R5R5 R5 R#v]#v R:Vl t65 / "kd$$Ifl C9 / t06((((44 lac$$If!vh5y5Y5#vy#vY#v:Vl t65c$$If!vh5y5Y5#vy#vY#v:Vl t65c$$If!vh5y5Y5#vy#vY#v:Vl t65c$$If!vh5y5Y5#vy#vY#v:Vl t65c$$If!vh5y5Y5#vy#vY#v:Vl t65c$$If!vh5y5Y5#vy#vY#v:Vl t65c$$If!vh5y5Y5#vy#vY#v:Vl t65c$$If!vh5y5Y5#vy#vY#v:Vl t65c$$If!vh5y5Y5#vy#vY#v:Vl t65c$$If!vh5y5Y5#vy#vY#v:Vl t65c$$If!vh5y5Y5#vy#vY#v:Vl t65$$If!vh55w!#v#vw!:V - 06,5g5/ 34-p$$If!vh55w!#v#vw!:V - 06,5g5/ 34-p$$If!vh55w!#v#vw!:V - 06,5g5/ 34-p$$If!vh55w!#v#vw!:V - 06,5g5/ 34-p$$If!vh55w!#v#vw!:V - 06,5g5/ 34-p$$If!vh55w!#v#vw!:V - 06,5g5/ 34-p$$If!vh55w!#v#vw!:V - 06,5g5/ 34-p$$If!vh55w!#v#vw!:V - 06,5g5/ 34-p$$If!vh55w!#v#vw!:V - 06,5g5/ 34-p$$If!vh55w!#v#vw!:V - 06,5g5/ 34-p$$If!vh55w!#v#vw!:V - 06,5g5/ 34-p$$If!vh555555N5N#v#v#vN:Vl t6,5$$If!vh5555555N#v#v#vN:Vl t6,5$$If!vh5555555#v#v:Vl t6,5@@@ NormalCJ_HaJmH sH tH 8@8 Heading 1$@&CJ N@2N Heading 3dd@&[$\$5CJ\aJDA@D Default Paragraph FontVi@V  Table Normal :V 44 la (k@(No List 4@4 Header  !4 @4 Footer  !.)@. Page Number0>@"0 Title$a$CJ$PC@2P Body Text Indent ^ OJQJ^J*W@A* Strong5\4B@R4 Body Text5\6U@a6 Hyperlink >*B*phFV@qF FollowedHyperlink >*B* phBb@B HTML CodeCJOJPJQJ^JaJe@ HTML Preformatted7 2( Px 4 #\'*.25@9CJOJPJQJ^JaJNg@N HTML TypewriterCJOJPJQJ^JaJB^@B Normal (Web)dd[$\$PR@P Body Text Indent 20^`0j@j J Table Grid7:V0 (,17;<?BEHMRSZ`eimnorux{~G#"! $)  (,17;<?BEHMRSZ`eimnorux{~   Gklmnopqrst+MrW `67823NOPQ!#$&456789;<=@AFGLNOPQ_`a 1 2 : P Q X 7 8 ? u v w x  A B C q r  .?@c"6BMPQm*+Xu7>Oe0?ORS~   _`a IJK789&'lmSTq)>?zDEacd * + H f !!!G!H!I!J!K!L!M!N!O!P!Q!R!!!!":"<"Z#[#$$$$$$$&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&' ''''' '&'+'1'7'='C'I'J'L'R'W'\'b'h'n's'y'''''''''''''''''''''''''''''( (((( (!(#()(/(5(;(A(F(L(R(X(Y([(a(g(m(s(y(~(((((((()0)\)),*-*****$+%+'+)+++,+.+0+8+9+;+=+E+F+H+J+a+b+d+f+}+~++++++++++++++++++++++,,,,,---- ..H...////////000{1|112 2)2222:4;4D4444556666^7_7h7M8N8S8888 9V9W9X9Y9Z9[9\999::<<==>>>A>U>i>>>>>>>>>>??@?M???????@ @ @8@_@`@@@@AA.ABAYAoAAAAABB5B6BKByBBBBCC6CKCCCCCCCDQDeDDDDDDDEE!E?EeEfEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEFFFFFFF F F FFFFFFFFFFFFFF!F"F#F$F'F(F)F*F-F.F/F0F3F4F5F6F7F8F9FF?F@FCFDFFFGFIFJFLFMFOFPFyFzF{FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFGGG000 0 0 0 0 0 0 0@0@0@0@0@0 0 0 0 0 0 0 0 0@0@0 0 0 0@00@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@00@0@0@0@0@0@0@0 @0 @0 @0 @0 @0 @0 @0@0 @0 @0 @0 @0 0 0 0 0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@00@0@0@00@0@0@00@0@00@0@00@0@0@00@0@0@0@0@0@0000@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@00@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@00@0@0@0@0@0@0@0@0@00000000000000@0@0@000@0@00@0@0@0@0@0@00@0@0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @000@0@0@0@00@0@0@0@0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0@0@00@0@0@0@0@0@0@0@00@0@0@0@0@0000@0@0 @0 @0 @0@0@0 @0 @0 @0 @0 @0 @0 @0@0@0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0 @0@000000000@0@0@00@00@0@0@0@00@0 @0 @0 @0 @0 @0 @0 @0 @0@0@0@0@0@00@0 @0 @0 @0 @0 @0 @0 @0 @0@0@0@0@0@00@0 @0 @0 @0 @0 @0 @0 @0 @0@0@0@0@0@0@0@0@00@0@0@0000@0@0@0@0@0@0@0@0@0@0@0@0@0@00000@0@0@000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000@0y00@0y00@0y00@0y00@0@0y00d000000000000000000000000000000000000000000000i0i0i00i00i00i00i00i00i00iy0=0?_`a 1 2 : P Q X 7 8 ? u v ?@c*+Xu7>Oe0?ORS aIJKSTqzacd !!!!!"<"&&&&''I'J'y''''''''''''' (!(X(Y(y(~(((((+++++++++++++++++,,,,,../////000{1|112 2)2222:4;4D4444556666^7_7h7M8N8S8888 999::=>>>A>U>i>>>>>>>M???????@ @8@@AA.ABAYAoAAAAAB{FFFFFFFFFG{00P>{00{00@0{00{00{00{00y00 @t0uz y0 0 y00 @0{00=@1{00y00 @0y00{00y00 y00={00{00{00{00 ={00{00{00{00{00{00{00{00{00{00{00{00={00{00{00{00{0%0&({n{0%0{0%0{0(0)|{n{0(0{0(0{00{00{00{00{0/00ę@{0/0{0/0@0{03044@{030{030@0y00y00y00y00y00y00{0=0>@{0=0{0=0s0@0{0A0@0{00s0D0E@s0D0s0D0{00@0@0@0@0h{0L0M@{0L0{0L0@40?P{00{00{00s0D0s0D0{00{00 {00  {00 a{0V0 {00 a{0V0 {00 a{0V0 {0V0Wa{0V0 {00 {0V0 {0V0 {0V0 {0V0 {0V0 {0V0 {0V0Wa{00{00a@0 {00a@0 {00a@0 {00{00{00 p0 {00 V@W0S8 {0u0v@0{0w0x{0w0{0y0 z{0y0{0w0{0w0{0}0{0}0{0}0{0w0{0w0{0w0{0u0@0{00l{00{00@0{00{00{00{00{00{00{00+Ty00-y00, y00y00 y00* y00A0y00 y00@0----y00 y0 0 {4y00 y00y00\y00 y00@0y00 y00@0*y00 y00@0xipy00 y00 @0 4y00 y00 @0`"##Py00 y0 0 0y00y00{00y00y00y00{00y00y00y00{00@0 y00 y00 y00 @0 {00 {00@0{00{00@0 y00 y00 y00 @0 {00 {00{00{00{00@0 @0 {00 {00 y00 @0 {00 y00 {00{000|X @0@0@0@0@0@0@0@00|X  6669lz%t'R),07<@EGJNO(/37:<?@BDJW]dfintsO1P7u> !$'R).// 00$3+383E3a3}333333 68{9:::<<=>^?M@@\AFF H8HIJMMN-N{NNNO)+,-.01245689;=>ACEFGHIKLMNOPQRSTUVXYZ[\^_`abceghjklmopqrsuvO*$$$/N0R001 1111)2222e3t3D4444m5u56_6g667 7h777S888G_XXXXXXXXXXX)039!T8@!] (    V ] 3  s"*?5`  c $X99? V ]F`  #  _ b2  C "`l  c $  F`  # .Qb2  C "`l  c $  F`  # U w7b2  C "`l  c $  F`  # .b2  C "`l  c $  F`  # a!kb2  C "`l  c $  F`  # Ab2  C "`l  c $  F`  # n.]b2  C "`l  c $  F`  # A]b2  C "`l  c $  F`  # -7b2  C "`l  c $    TB  C D ^.^TB  C D;;TB  C D*.TB  C DTB  C DakTB  C DaaTB  C DTB B C DTB B C D.7P  BC(DE@F @<x@  80PxP(p @      V N   3   (2   (2    (2   (2  (2   (2  NB @ S D NB  S D NB  S D T  C  T  C  T ! C ! T " C " T # C # T $ C $ (2 ' NB (@ S DT ) C  )  NB @ S DNB  S D(2  T  C    NB  S DNB @ S D(2  T  C ! !(2  4(2  3(2  2(2  1(2  0(2  #NB @ S D/NB  S D.NB  S D-T  C , T  C + T  C * T  C " T  C  T  C ) NB @ S D$NB  S D((2  !NB  S D NB @ S D'(2  &T  C  %  (2  T  C    NB @ S DT  C  B S  ?!$&'()*+,-./0129=>ABCDGHIJL$G d5t ,t'P  t) 4 t(4 t$Q ! t#4ete@ t-ItQ tet@ I,t @ 5t !! t 45t tT Dt!d ytT yt\@tTt p( t"<@ tL}tmt`t<d t$`t! %Rt$  t t*  t%Dt j g"Yt!Z%t) w t8 S t t%tG%t! MWtI  { tM t) apt% t tAM tuU%t tM] t h  tq}tq t9ut(p t !f!"f#??G??G9*urn:schemas-microsoft-com:office:smarttagsState9*urn:schemas-microsoft-com:office:smarttagsplace PM  > A _ b C F       , . 4 5 6 r { | ~ %)*/8:;DGHIOPSZ^_dtv|}~  9>VYZ[abhip]`abhipq$%+,;<AJKL`c15@%H%();)E)O)W)m)v)))))))))* ******!*"***[*c*********+++,,,,,,--4-..p.x....... ///&/U/^/l/u///////////////T0[0111 1!2(22222f3t3v3y3z3333<4C44444n5u5w5~55556`6g666 77`7g77777O8R89 999999999:#:-:7:f:o:{:::::::::::: ;;|;;*<.<<<<<%=(=>?{@@AA&B-BCBJBTB[B\B_BBBBBBBBB CC%C,C/C4C?CBCCCICOCUCDDrDzDDDDDDFDFFFFFGFGFIFJFLFMFOFPFzF{FG55: # * : >  - /9@Ddu #)9?DKRVpSUY]x&9=ALQThs  3;AKy{8F &'1np))1)4)])a)))**++U,[,,,-- ...... //////O0R0 1 11122f3t344n5u5`6g67 777889999:#:::::>>@?E?@@AA6BCCCSDVDgDkDDDDDDEFEDFDFFFFFGFGFIFJFLFMFOFPFzF{FFFG3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333T O 8 v +H++Y9Z9::;;;;;;<<>>)>,>0>4>5>6>?>?>a?a?g?j?n?s?y?{?@@@@@@@@AAAABBJCCE?EEEFFFFFF=F=FBFBFCFDFDFFFFFGFGFIFJFLFMFOFPFjFkFmFxF{F{F~FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGAADFDFFFFFGFGFIFJFLFMFOFPFzF{FG ^aռmV$&z"&Ϣ'E:y[2fo~|h^`.h^`.hpLp^p`L.h@ @ ^@ `.h^`.hL^`L.h^`.h^`.hPLP^P`L.h^`.h^`.hpLp^p`L.h@ @ ^@ `.h^`.hL^`L.h^`.h^`.hPLP^P`L.^`CJOJQJo(^`CJOJQJo(opp^p`CJOJQJo(@ @ ^@ `CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(^`CJOJQJo(PP^P`CJOJQJo(h^`.h^`.hpLp^p`L.h@ @ ^@ `.h^`.hL^`L.h^`.h^`.hPLP^P`L.h^`.h^`OJQJo(hHhpLp^p`L.h@ @ ^@ `.h^`.hL^`L.h^`.h^`.hPLP^P`L.h^`.h^`.hpLp^p`L.h@ @ ^@ `.h^`.hL^`L.h^`.h^`.hPLP^P`L.h^`.h^`.hpLp^p`L.h@ @ ^@ `.h^`.hL^`L.h^`.h^`.hPLP^P`L.~&y[m ^a"&E%                  Xt+u"$:ܦ)&Ѣut'                                    ;"e@?-cL oA 2MAJ/R+|.58Q8 = C@H1IJ M_4NQ5V` Z8s"tK;|_ qfiGBfG9-@[s%nn["9/B5-3yy5"RG~7r? {[4_z0klmnopqrst 1 2 : P Q X 7 8 ? u v &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&' ''''' '&'+'1'7'='C'I'J'L'R'W'\'b'h'n's'y'''''''''''''''''''''''''''''( (((( (!(#()(/(5(;(A(F(L(R(X(Y([(a(g(m(s(y(~(((((***$+%+'+)+++,+.+0+8+9+;+=+E+F+H+J+a+b+d+f+}+~+++++++++++++++++++++//000{1|112 2)2222:4;4D4444556666^7_7h7M8N8S888A>U>i>>>>>>>??????@ @ @AA.ABAYAoAAAAG@ AAyAA@{GP@UnknownGz Times New Roman5Symbol3& z Arial?5 z Courier New;Wingdings"1hrfK*| ;#| ;#!4d!F!F 2QHX?@H2CS 307  Midterm 1  Fall 2001 Mike Scottscottm(       Oh+'0 $0 P \ h t CS 307 Midterm 1 Fall 2001 Mike Scott Normal.dotscottm42Microsoft Office Word@78@jX1@S@|4*[| ;՜.+,D՜.+,P  hp  U of T#!F CS 307 Midterm 1 Fall 2001 Title<  8@ _PID_HLINKSABo:!Ahttp://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.htmlsize()tuAhttp://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html set(int, E)amAhttp://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html remove(int)K]Ahttp://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html isEmpty() Ahttp://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.htmlindexOf(java.lang.Object)@Ahttp://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html get(int)hlAhttp://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.htmlensureCapacity(int);e Ahttp://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.htmlcontains(java.lang.Object):: Ahttp://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.htmlclear()vtAhttp://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html add(int, E).zAhttp://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.htmladd(E)  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwyz{|}~     Root Entry F@F[Data x11TableWordDocument4SummaryInformation(DocumentSummaryInformation8CompObjq  FMicrosoft Office Word Document MSWordDocWord.Document.89q