1、封 密題答不內(nèi)線封密1號位座業(yè)專院學 號學名姓誠信應考，考試作弊將帶來嚴重后果!華南理工大學期末考試« Data Structure » 試卷 B注意事項：1.考前請將密封線內(nèi)填寫清楚；2.所有答案請答在答題紙上；3.考試形式：閉卷；4.本試卷共十大題，滿分 100分，考試時間120分鐘。題號一二三四五六七八九十總分得分評卷人1. Selectthe correct choice. (30 scores, each 2 scores)(1) If a data element requires 4 bytes and a pointer requires 2 bytes,t

2、hen a linked list representation will be more space efficientthan a standard array representation when the fraction of non-zeroelements is less than about: ( A )(A) 2/3(B) 3/4(C) 1/3(D) 1/2(2) Assume array A contains a random permutation of the values from 0 ton - 1, the time cost of the following c

3、ode fragment is: ( B )sum = 0;for (i=0; i<n; i+)for (j=0; Aj!=i; j+) sum+;(A)后(n)(B) 0(n2)(C) G (nlogn)(D) O(logn)(3) Which statement isnot correct among the following four: ( D )(A) 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

4、be less than orgreater than the right child.(B) The number of empty subtrees in a non-empty binary tree is one more than the number of nodes in the tree.(C) A general tree can be transferred to a binary tree with the root having only left child.(D) A heap must be a full binary tree.(4) An algorithm

5、must be or do all of the following EXCEPT: ( B )(A) Correct (B) Ambiguous (C) Concrete step (D) terminable(5) In the following sorting algorithms, which is the best one to find the first 10 biggest elements in the 1000 unsorted elements?( C )(A) Insert sort.(B) Quicksort.(C) Heap sort.(D) Shell sort

6、.(6) Which of the following is the max-heap constructed by a sequence of key (48, 76,54, 32, 40, 85) ?( B )(A)76,85, 54, 32, 48, 40(B) 85, 76, 54, 32, 40, 48(C) 85, 54, 76, 48, 32, 40(D) 85, 76, 54, 32, 40, 48 If there is 1MB working memory, 4KB each block, and yield 256 blocks for working memory. B

7、y the multi-way merge in external sorting, the average run size and the sorted size in one pass of multi-way merge on averagerespectively are :( C )(A)1MB, 256 MB(B) 1MB, 512 MB(C) 2MB, 512 MB(D) 2MB, 1024MB(8) The golden ruleof a disk-basedprogram design is to: ( A )(A) Minimize the number of disk

8、accesses. (B) Eliminate the recursive calls. (C)Improve the basic operations.(D) Reduce main memory use.(9) The time cost of Quicksort in the worst case is ( D ).2(A) O(n) (B) O(log2 n)(C) O(n 10g2 n) (D) O(n )(10) The function of replacement selection sort is ( B ).(A) Select the maximal element. (

9、B) Generate the initial sorted merge files. (C) Merge the sorted file.(D) Replace some record.(11) Tree indexing methods are meant to overcome what deficiency inhashing?( D )(A) Inability to handle range queries.(B) Inability to handle largestkey valuequeries.(C) Inability to handle queries in key o

10、rder(D) All above.(12) Which statement is not correct among the following four: ( 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 a multiple of the cluster size.(C) The

11、 selection sort is an unstable sorting algorithm.(D) The number of leaves in a non-empty full binary tree is one more than the number of internal node.(13) 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

12、 applying the following access pattern: F D F G G F A D F G, if the list is organized by frequency count (count will store the records in the order of frequency that has actually occurred so far), then the final list will be ( A ).(A) A B F G D C E H(B) E G F D A B C H(C) A G F D B C E H(D) F E G D

13、A B C H(14) In the hash function, collision refers to ( B ).(A) Two elements have the same sequence number.(B) Different keys are mapped to the same address of hash table.(C) Two records have the same key.(D) Data elements are too much.(15) For the following graph, one of results ofDepth-first trave

14、rsal is: ( C )& hA. acbdieghf B. abighfcde C. abdeigchf D. abcdefghi2. Arrange the following expressions by growth rate from slowest to fastest. (4 scores)3n2 log3n n! 10n 2n 20 log2n8n2/3Answer: 20< 10g3n< log2n<8n2/3< 10n< 3n2<2n< n!3. Draw the general tree represented by

15、the following sequential representationfor general trees: RAC)M)PL)V)NW)J)(6 scores)Answer:RANCMPW JL V4. Please apply Quicksort Algorithm to sort the array in ascending order: 265, 301,751, 129, 937, 863, 742, 694, 076, 438. Note that the pivot value is selected based on the following function, Par

16、ameters i andj define the start and end indices of the ArrayA, respectively. (10 scores)template <typename E>inline int findpivot(E A, int i, int j) return Ai; Answer:Initial : 265 301 751 129 937 863 742 694 076 438 1st pass 076 129 265 751 937 863 742 694 301 438 2nd pass 076 129 265 438 301

17、 694 742 751 863 937 3rd pass 076 129 265 301 438 694 742 751 863 937 4th pass 076 129 265 301 438 694 742 751 863 937 5th pass 076 129 265 301 438 694 742 751 863 9375. Please draw pictures to show the heaps that results from (6 scores)1) add 38 to the following heap；2) then delete 42 from the resu

18、lt heap of 1)252215161218Answer:6. Please give the Huffman codes for the letters of the following table, draw pictures to show how to obtain the Huffman tree step by step, and compute the expected bit-length per letter. What' the advantage of Huffman code scheme. (8 scores)LetterabcdefghFrequenc

19、y55134117670111722Answer:2) expected bit-length(6 +11)x5 +17x4 + (34+17 + 22)x3+(70+55)x2-7 222 2.83) advantageHuffman code scheme saves text length in most cases.7. Given a hash table of size 11, assume that . ，andH = j ：。二 |一 | are two hash functions, where H1 is used to get homeposition and H2is

20、used to resolve collision for method double hashing. Please insert keys 9, 17, 63, 55, 22, 27, 88, 41 into the hash table in order. (10 scores)Answer:H1(9)=8, H1(17)=2, H1(63)=6, H1(55)=1, no conflictWhen H1(22)=1, H2(22)=7 (1+2*7) %11=4, so 22 enters the 4 slot (pass by 1,8);H1(27)=0 so 27 enters t

21、he 0 slot;H1(88)=1, H2(88)=5 (1+3*5)%11= 5 so 88 enters 5 (pass by 1,6, 0 );H1(41)=6, H2(41)=4(6+1*4)%11= 10 so 41 enters 10(pass by 6)2755172288639410123456789108. Please insert 18 58,8 into the following 2-3 tree. Inserting a key, draw a picture for the resulted 2-3 tree. Thus you should draw 3 pi

22、ctures. (10 scores)Answer:1)3)309. Complete the insert, remove functions of the Link-based List class. (6 scores) template <class Elem> class LList:public List<Elem> private:Link<Elem>* head;/Point to list headerLink<Elem>* tail;/Pointer to last ElemLink<Elem>* fence;/L

23、ast element on leftint leftcnt; /Size of leftint rightcnt; /Size of rightpublic:bool LList<Elem>:insert(const Elem& item) template <class Elem> bool LList<Elem>二remove(Elem& it) Solution:/ Insert at front of right partitiontemplate <class Elem>bool LList<Elem>:i

24、nsert(const Elem& item) fence->next = new Link<Elem>(item, fence->next);if (tail = fence) tail = fence->next; rightcnt+;return true;/ Remove and return first Elem in right/ partitiontemplate <class Elem> bool LList<Elem>:remove(Elem& it) if (fence->next = NULL)

25、return false;it = fence->next->element; /Remember val/ Remember link nodeLink<Elem>* ltemp = fence->next;fence->next = ltemp->next; / Removeif (tail = ltemp) / Reset tailtail = fence;delete ltemp; / Reclaim spacerightcnt-;return true;10. Assume a disk drive is configured as foll

26、ows. The total storage is approximately 1.5G divided among 15 surfaces. Each surface has 512 tracks; there are 256 sectors/track, 1024 byte/sector, and 32 sectors/cluster. The disk turns at 7200rmp (8.33 ms/r). The track-to-track seek time is 3 ms, and the average seek time is 10 ms. Now how long do

27、es it take to read all of the data in a 960 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)Solution:The first question is how many clusters the file requires?A cluster holds 32*1K = 32K. Thus, the file requires 960K/32K=30 clustersThe time to read a clusteris seek time to the clust