2016数据结构试卷B及答案-副本-副本

《2016数据结构试卷B及答案-副本-副本》由会员分享，可在线阅读，更多相关《2016数据结构试卷B及答案-副本-副本（10页珍藏版）》请在文档大全上搜索。

1、封 密题答不内线封密1号位座业专院学 号学名姓诚信应考，考试作弊将带来严重后果!华南理工大学期末考试« 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,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