( 密 封 线 内 不 答 题 ) ………………………………………密………………………………………………封………………………………………线…………………………………… 学院 专业 座位号 诚信应考,考试作弊将带来严重后果！ 华南理工大学期末考试 《 Data Structure 》A试卷 注意事项：1. 考前请将密封线内填写清楚； 2. 所有答案请直接答在试卷上； 3．考试形式：闭卷； 4. 本试卷共十大题，满分100分，考试时间120分钟。 题 号 一 二 三 四 五 六 七 八 九 十 总分 得 分 评卷人 1. Select the correct choice. (20 scores, each 2 scores) (1) An algorithm must be or do all of the following EXCEPT: ( C ) (A) Correct (B) Finite (C) Ambiguous (D) Concrete steps (2) Pick the growth rate that corresponds to the most efficient algorithm as n gets large: ( D ) (A) 2n3 (B) 2n (C) n! (D) 20n2logn (3) If a data element requires 8 bytes and a pointer requires 2 bytes, then a linked list representation will be more space efficient than a standard array representation when the fraction of non-null elements is less than about: ( B ) (A) 1/4 (B) 4/5 (C) 3/5 (D) 3/4 (4) Which statement is not correct among the following four: ( B ) (A) The Heap sort is an unstable sorting algorithm. (B) A cluster is the smallest unit of allocation for a file, so all files occupy a multiple of the cluster size. (C) The worst case for my algorithm is n becoming larger and larger because that is the slowest. (D) The number of empty subtrees in a non-empty binary tree is one more than the number of nodes in the tree. (5) Which of the following is a true statement: ( C ) (A) A general tree can be transferred to a binary tree with the root having both left child and right child. (B) In a BST, the node can be enumerated sorted by a preorder traversal to the BST. (C) In a BST, the left child of any node is less than the right child, but in a heap, the left child of any node could be less than or greater than the right child. (D) A heap has the shape like full binary tree. (6) The most effective way to reduce the time required by a disk-based program is to: ( B ) 《 Data Structure 》A试卷 第 1 页 共 6 页 _____________ ________ 姓名 学号 (A) Improve the basic operations. (B) Minimize the number of disk accesses. (C) Eliminate the recursive calls. (D) Reduce main memory use.
(7) The max-heap constructed by a sequence of key (54, 32, 45, 63, 76, 84) is ( D )?
(A) 84, 63, 54, 76, 32, 45 (B) 84, 76, 45, 63, 54, 32 (C) 84, 63, 76, 32, 45, 54 (D) 84, 76, 54, 63, 32, 45 (8) If there is 1MB working memory, 8KB blocks, yield 128 blocks for working memory. By the multi-way merge in external sorting, the average run size and the sorted size in one pass of multi-way merge on average are separately ( C )? (A) 1MB, 128 MB (B) 2MB, 512MB (C) 2MB, 256 MB (D) 1MB, 256MB (9) Tree indexing methods are meant to overcome what deficiency in hashing? ( D )
(A) Inability to handle range queries. (B) Inability to maximum queries (C) Inability to handle queries in key order (D) All of above.
(10) Assume that we have eight records, with key values A to H, and that they are initially placed in alphabetical order. Now, consider the result of applying the following access pattern: F D F G E G F A D F G E, if the list is organized by the move-to-front heuristic, then the final list will be ( B ).
(A) E G F D A C H B (B) E G F D A B C H (C) F D G A E C B H (D) F D G E A B C H 2. Fill the blank with correct C++ codes: (15 scores)
(1) Given an array storing integers ordered by value, modify the binary search routines to return the position of the first integer with the greatest value less than K when K itself does not appear in the array. Return ERROR if the least value in the array is greater than K: (12 scores) // Return position of greatest element <= K int newbinary(int array[], int n, int K) { int l = -1;
int r = n; // l and r beyond array bounds while (l+1 != r) { // Stop when l and r meet
___ int i=（l+r）/2_____; // Look at middle of subarray if (K < array[i]) __ r=i ___; // In left half if (K == array[i]) __ return i ___; // Found it if (K > array[i]) ___ l=i ___ // In right half }
// K is not in array or the greatest value is less than K if K> array[0] （or l !=-1）
then return l ; // the first integer with the greatest value less than
// K when K itself does not appear in the array
else return ERROR; // the least value in the array is greater than K
《 Data Structure 》A试卷 第 2 页 共 6 页
}
(2) A full 6-ary tree with 100 internal vertices has ___601___vertices. ( 3 scores)
3. A certain binary tree has the preorder enumeration as ABECDFGHIJ and the inorder enumeration as EBCDAFHIGJ. Try to draw the binary tree and give the postorder enumeration. (The process of your solution is required!!!) (8 scores) A A A A B F B F B F EBCD FHIGJ E HIGJ E C G E C G CD
D HI J D H J
I
Postorder enumeration: EDCBIHJGFA
4. Determine Θ for the following code fragments in the average case. Assume that all variables are of type int. (6 scores) (1) sum=0;
for (i=0; i<3; i++) for (j=0; j sum++; solution : Θ___(n)_______ (2) sum = 0; for(i=1;i<=n;i++) for(j=1;j<=i;j++) sum++; solution : Θ__(n2)________ (3) sum=0; if (EVEN(n)) for (i=0; i sum=sum+n; solution : Θ___(n)_____ 5. Trace by hand the execution of Quicksort algorithm on the array: int a[] = {265 301 751 129 937 863 742 694 76 438} The pivot is 265 in the first pass, the second is 76 and 751, the third is 438 and 863, the four is 694, and so on till the algorithm is finished. (9 scores) initial: 265 301 751 129 937 863 742 694 76 438 《 Data Structure 》A试卷 第 3 页 共 6 页 pass 1: [76 129] 265 [751 937 863 742 694 301 438] pass 2: 76 [129] 265 [438 301 694 742] 751 [863 937] pass 3: 76 129 265 [301] 438 [694 742] 751 863 [937] pass 4: 76 129 265 301 438 694 [742] 751 863 937 pass 5: 76 129 265 301 438 694 742 751 863 937 final sorted array: 76 129 265 301 438 694 742 751 863 937 6. Build the Huffman coding tree and determine the codes for the following set of letters and weights: A B C D E F G H 5 25 3 6 10 11 36 4 Draw the Huffman coding tree and give the Huffman code for each letters. What is the expected length in bits of a message containing n characters for this frequency distribution? (The process of your solution is required!!!) (9 scores) Huffman code A 0 0 0 0 3 7 17 39 100 1 0 61 1 22 1 36 1 10 25 0 0 5 11 1 11 B G 1 4 E 1 6 F C H A D B C D E F G H 0100 10 0000 0101 001 011 11 0001 Total length: 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 + 3 * 11 + 2 * 36 + 4 * 4 = 257 Expected length: 257/100=2.57 7. Assume a disk drive is configured as follows. The total storage is approximately 675M divided among 15 surfaces. Each surface has 612 tracks; there are 144 sectors/track, 512 byte/sector, and 16 sectors/cluster. The interleaving factor is five. The disk turns at 7200rmp (8.33 ms/r). The track-to-track seek time is 20 ms, and the average seek time is 80 ms. Now how long does it take to read all of the data in a 320 KB file on the disk? Assume that the file’s clusters are spread randomly across the disk. A seek must be performed each time the I/O reader moves to a new track. Show your calculations. (The process of your solution is required!!!) (8 scores) Answer： The first question is how many clusters the file requires? 《 Data Structure 》A试卷 第 4 页 共 6 页 A cluster holds 16*0.5K = 8K. Thus, the file requires 320/8=40 clusters. The time to read a cluster is seek time to the cluster+ latency time + (interleaf factor × rotation time). Average seek time is defined to be 80 ms. Latency time is 0.5 * 8.33 ms(60/7200≈8.33ms), and cluster rotation time is 5 * (16/144)*8.33. Seek time for the total file read time is 40* (80 + 0.5 * 8.33+ 5 * (16/144)*8.33 ) ≈ 3551.85 ms Or 3551.51 when (60/7200≈8.3ms) 8. Using closed hashing, with double hashing to resolve collisions, insert the following keys into a hash table of eleven slots (the slots are numbered 0 through 10). The hash functions to be used are H1 and H2, defined below. You should show the hash table after all eight keys have been inserted. Be sure to indicate how you are using H1 and H2 to do the hashing. ( The process of your solution is required!!!) H1(k) = 3k mod 11 H2(k) = 7k mod 10+1 Keys: 22, 41, 53, 46, 30, 13, 1, 67. (8 scores) Answer: H1(22)=0, H1(41)=2, H1(53)=5, H1(46)=6, no conflict When H1(30)=2, H2(30)=1 （2+1*1）=3，so 30 enters the 3rd slot; H1(13)=6, H2(13)=2 (6+1*2)=8, so 13 enters the 8th slot; H1(1)=3, H2(1)=8 (3+5*8)= 10 so 1 enters 10 (pass by 0, 8, 5, 2 ); H1(67)=3, H2(67)=10 (3+2*10)= 1 so 67 enters 1(pass by 2) 9. You are given a series of records whose keys are integers. The records arrive in the following order: C, S, D, T, A, M, P, I, B, W, N, G, U, R. Show the 2-3 tree that results from inserting these records. （the process of your solution is required!!!） (7 scores) MS BD P U A C GI N R T W 10. 1) Use Dijkstra’s Algorithm to find the shortest paths from C to all other vertices. (4 scores) 2) Use Kruskal’s algorithm to find the minimum-cost spanning tree. (3 scores) 3) Show the DFS tree for the following graph, starting at Vertex A. (3 scores) A 4 9 2 6 B 1 《 Data Structure 》A试卷 第 5 页 共 6 页 C 5 7 D 8 6 E 3 F G 1) C to A: 4 (C,A); CF: 5(C,F); CD: 6(C,A,D); CB: 12(C,A,D,B); CG:11 (C,F,G); CE: 13(C,A,D,B,E) 2) A B 4 2 1 C 5 D E F 6 G 3 OR B 4 A 2 6 1 D C 5 E F G 3 3) A---->B---->D--->F---->C G E 《 Data Structure 》A试卷 第 6 页 共 6 页 1) C to A: 4 (C,A); CF: 5(C,F); CD: 6(C,A,D); CB: 12(C,A,D,B); CG:11 (C,F,G); CE: 13(C,A,D,B,E) 2) A B 4 2 1 C 5 D E F 6 G 3 OR B 4 A 2 6 1 D C 5 E F G 3 3) A---->B---->D--->F---->C G E 《 Data Structure 》A试卷 第 6 页 共 6 页
