姓名 学号 学院 专业 座位号
( 密封线内不答题 )
……………………………………………………密………………………………………………封………………………………………线……………………………………线………………………………………
_____________ ________
…
诚信应考,考试作弊将带来严重后果！华南理工大学期末考试
《 Data Structure 》试卷 B
注意事项：1. 考前请将密封线内填写清楚；
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,then 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 code fragment is: ( B )
sum = 0;
for (i=0; i<n; i++)
for (j=0; A[j]!=i; j++)
sum++;
(A) (B) (C) (D)
(3) Which statement is not 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 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 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) 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
(7) If there is 1MB working memory, 4KB each block, and yield 256 blocks for working mem
ory. By 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 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 ).
(A) O(n) (B) O(log2 n) (C) O(n log2 n) (D) O(n2)
(10) The function of replacement selection sort is ( B ).
(A) Select the maximal element. (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 order
(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 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 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 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.
sortedlist (C) Two records have the same key.(D) Data elements are too much.
发表评论