( 密 封 线 内 不 答 题 ) ………………………………………密………………………………………………封………………………………………线…………………………………… 学院 专业 座位号 诚信应考,考试作弊将带来严重后果！ 华南理工大学期末考试 《 Data Structure 》试卷 A 注意事项：1. 考前请将密封线内填写清楚； 2. 所有答案请答在答题纸上； 3．考试形式：闭卷； 4. 本试卷共十大题，满分100分，考试时间120分钟。 题 号 一 二 三 四 五 六 七 八 九 十 总分 得 分 评卷人 1. Select the correct choice. (20 scores, each 2 scores) (1) Pick the growth rate that corresponds to the most inefficient algorithm as n gets large: ( C ) (A) 2n3 (B) 2n2logn (C) n! (D) 2n (2) An algorithm must be or do all of the following EXCEPT: ( B ) (A) Partially correct (B) Ambiguous (C) Can stop (D) Concrete steps (3) If a data element requires 6 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) 3/4 (C) 4/7 (D) 2/3 (4) Which statement is not correct among the following four: ( C ) (A) The Quick-sort is an unstable sorting algorithm. (B) The number of empty sub-trees in a non-empty full binary tree is one more than the number of nodes in the tree. (C) The best case for my algorithm is n becoming larger and larger because that is the most quickly. (D) A cluster is the smallest unit of allocation for a file, so all files occupy a multiple of the cluster size. (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 must be full binary tree. (6) The golden rule of a disk-based program design is to: ( B ) (A) Improve the basic I/O operations. (B) Minimize the number of disk 《 Data Structure 》A试卷 第 1 页 共 5 页 _____________ ________ 姓名 学号 accesses.
(C) Eliminate the recursive calls. (D) Reduce main memory use.
(7) Given an array as A[m] [n]. Supposed that A [0] [0] is located at 644(10) and A [2] [2] is stored at 676(10), and every element occupies one space. “(10)” means that the number is presented in decimals. Then the element A [1] [1](10) is at position: ( D )
(A) 692 (B) 695 (C) 650 (D) 660
(8) If there is 1MB working memory, 4KB blocks, and 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, 256MB (D) 1MB, 256MB (9) In the following sorting algorithms, which is the best one to find the first 10 biggest elements in the 1000 unsorted elements? ( B ) (A) Quick-sort (B) Heap sort
(C ) Insertion sort (D) Replacement selection
(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) F G D E A B C H (B)E G F D A B C H (C) A B F D G E C H (D) E G F A C B D H
2. Fill the blank with correct C++ codes: (16 scores)
(1) Given an array storing integers ordered by distinct value without duplicate, modify the binary
search routines to return the position of the integer with the greatest value less than K when K itself does not appear in the array. Return ERROR if the lest value in the array is greater than K: (10 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）// the lest value in the array is greater than K with l updated
return l ; // when K itself does not appear in the array
else return ERROR; // the integer with the lest value greater than K }
《 Data Structure 》A试卷 第 2 页 共 5 页
(2) The number of nodes in a complete binary tree as big as possible with height h is 2h-1(suppose 1-node tree’s height is 1) (3 scores)
(3) The number of different shapes of binary trees with 6 nodes is _132. (3 scores)
3. A certain binary tree has the post-order enumeration as EDCBIHJGFA and the in-order enumeration as EBDCAFIHGJ. Try to draw the binary tree and give the postorder enumeration. (The process of your solution is required!!!) (6 scores) A A A A
B F B F B F EBDC FIHGJ
E IHGJ E C G E C G DC
J IH J H D D preorder enumeration: ABECDFGHIJ
I
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<5; i++) for (j=0; j sum++; solution : Θ___(n)_______ (2) sum = 0; for(i=1;i<=n;i++) for(j=n;j>=i;j--) sum++; solution : Θ__(n2)________ (3) sum=0; if (EVEN(n)) for (i=0; i sum=sum+n; solution : Θ___(n)_____ 5. Show the min-heap that results from running buildheap on the following values stored in an array: 4, 2, 5, 8, 3, 6, 10, 14. (6 scores) 2 4 4 2 2 2 2 4 4 5 4 5 4 5 8 8 3 2 2 2 2 3 5 3 5 3 5 3 5 8 4 8 》A试卷页 共页 10 6 4 《 Data Structure 8 4 6 10 第 3 8 4 5 6 14