華南理工大學(xué)數(shù)據(jù)結(jié)構(gòu).doc

_ _ 誠(chéng)信應(yīng)考,考試作弊將帶來嚴(yán)重后果！ 華南理工大學(xué)期末考試 Data Structure A試卷注意事項(xiàng)：1. 考前請(qǐng)將密封線內(nèi)填寫清楚； 2. 所有答案請(qǐng)直接答在試卷上； 3考試形式：閉卷； 4. 本試卷共十大題，滿分100分，考試時(shí)間120分鐘。題 號(hào)一二三四五六七八九十總分得 分評(píng)卷人1. Select the correct choice. (20 scores, each 2 scores)(1) An algorithm must be or do all of the following EXCEPT: ( D )(A) Correct正確的 (B) Finite有限的 (C) Terminate終止的 (D) Ambiguous模糊(2) Pick the growth rate增長(zhǎng)率 that corresponds to the most efficient有效率的 algorithm as n gets large: ( C )(A) n! (B) 2n (C) 10nlog n (D) 2n2(3) If a data element requires 6 bytes and a pointer requires 4 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) 2/3 (B) 3/5 (C) 3/4 (D) 1/2(4) Which statement is not correct among the following four下面那個(gè)描述是不正確的: ( A )(A) The worst case for my algorithm is n becoming larger and larger because that is the slowest.(B) A cluster簇 is the smallest unit of allocation分配 for a file, so all files occupy占據(jù) a multiple倍數(shù) of the cluster size.(C) The selection sort is an unstable不穩(wěn)定的 sorting algorithm.(D) The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.(5) Which of the following is a true statement: ( C )(A) In a BST, the left child of any node is less than the right child, and in a heap, the left child of any node is less than the right child.(B) In a BST, the left child of any node could be less or greater than the right child, but in a heap, the left child of any node must be less than the right child. (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) In both a BST and a heap, the left child of any node could be either less than or greater than the right child.(6) The most effective way to reduce the time required by a disk-based program is to: ( B ) (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 (46, 79, 56, 38, 40, 84) is ( )?(A) 79, 46, 56, 38, 40, 84 (B) 84, 79, 56, 46, 40, 38(C) 84, 79, 46, 38, 40, 56 (D) 84, 56, 79, 40, 46, 38(8) If there is 0.5MB working memory, 4KB 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 ( A )?(A) 1MB, 128MB (B) 1MB, 64MB(C) 2MB, 64 MB (D) 0.5 MB, 128MB(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: E D F G B G F A F E G B, if the list is organized by the move-to-front heuristic, then the final list will be ( B ).(A) B G E F D A C H (B) B G E F A D C H(C) A B F D G E C H (D) F D G E A B C H2. Fill the blank with correct C+ codes: (13 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: (10 scores)/ Return position of greatest element = Kint 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 arrayi) _ l=i _ / In right half / Search value not in array _ return l _; / l at first value less than K / l=-1, no value less than K(2) A full 5-ary tree with 100 internal vertices has _501_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)EBCDFHIGJAABEFCDHIGJABEFCDGJHIABEFCDGJHIPostorder enumeration: EDCBIHJGFA4. Determine for the following code fragments in the average case. Assume that all variables are of t