数据结构与算法分析 复习试卷A1

川大复习资料

四川大学期末考试试题（闭卷）

（2009~2010学年第1学期）

课程号： 311036030课程名称： 数据结构与算法分析（A卷） 任课教师： 孙界平，张卫华 适用专业年级： 软件工程 2008级 学号： 姓名：

2. 请将答案全部填写在本试题纸上；

3. 考试结束，请将试题纸、添卷纸和草稿纸一并交给监考老师。

评阅教师

得分

一、单项选择题（本大题共20小题，每小题2分，共40分）提示：在每小题列

出的备选项中只有一个是符合题目要求的，请将其代码写到答题纸上。错选、多选或未选均无分。

1. An algorithm must be or do all of the following EXCEPT:

a) correct

b) composed of concrete steps *c) ambiguous d) composed of a finite number of steps e) terminate

2. For set P, the notation |P| indicates

*a) The number of elements in P. b) The inverse of P. c) The powerset of P. d) None of the above.

3. Pick the growth rate that corresponds to the most efficient algorithm when n = 4.

a) 5n

b) 20 log n c) 2n^2 *d) 2^n

4. When the upper and lower bounds for an algorithm are the same, we use:

a) big-Oh notation. b) big-Omega notation.

川大复习资料

*c) Theta notation. d) asymptotic analysis. e) Average case analysis. f) Worst case analysis.

5. As compared to the linked list implementation for lists, the array-based list implementation requires:

a) More space b) Less space

*c) More or less space depending on how many elements are in the list.

6. When comparing the doubly and singly linked list implementations, we find that the doubly linked list implementation

*a) Saves time on some operations at the expense of additional space. b) Saves neither time nor space, but is easier to implement.

c) Saves neither time nor space, and is also harder to implement.

7. The correct traversal to use on a BST to visit the nodes in sorted order is:

a) Preorder traversal. *b) Inorder traversal. c) Postorder traversal.

8. When every node of a full binary tree stores a 4-byte data field, two 4-byte child pointers, and a 4-byte parent pointer, the overhead fraction is approximately:

a) one quarter. b) one third. c) one half. d) two thirds.

*e) three quarters. f) none of the above.

9. If a node is at position r in the array implementation for a complete binary tree, then its right child is at:

a) (r - 1)/2 if r > 0

b) 2r + 1 if (2r + 1) < n *c) 2r + 2 if (2r + 2) < n d) r - 1 if r is even e) r + 1 if r is odd.

10. The Huffman coding tree works best when the frequencies for letters are

a) Roughly the same for all letters.

*b) Skewed so that there is a great difference in relative frequencies for various letters.

11. A topological sort requires all of the following except:

a) The graph be directed.

b) The graph contain no cycles.

*c) The graph contain weights on the edges.

12. When sorting n records, Mergesort has worst-case cost:

a) O(log n). b) O(n).

*c) O(n log n).

川大复习资料

d) O(n^2) e) O(n!)

f) None of the above.

13. As compared to the time required to access one unit of data from main memory, accessing one unit of data from disk is:

a) 10 times faster. b) 1000 times faster. c) 1,000,000 time faster. d) 10 times slower. e) 1000 times slower.

*f) 1,000,000 times slower.

14. The basic unit of I/O when accessing a disk drive is:

a) A byte. *b) A sector. c) A cluster. d) A track. e) An extent.

15. The most time-consuming part of a random access to disk is usually:

*a) The seek.

b) The rotational delay.

c) The time for the data to move under the I/O head.

16. Which is generally more expensive?

a) A successful search. *b) An unsuccessful search.

17. The 80/20 rule indicates that:

a) 80% of searches in typical databases are successful and 20% are not. *b) 80% of the searches in typical databases are to 20% of the records. c) 80% of records in typical databases are of value, 20% are not.

18. Hashing is most appropriate for:

a) In-memory applications. b) Disk-based applications.

*c) Either in-memory or disk-based applications.

19. The primary key is:

*a) A unique identifier for a record.

b) The main search key used by users of the database. c) The first key in the index.

20. Depth-first search is best implemented using:

*a) A stack or recursion. b) A queue. c) A tree.

川大复习资料

二、判断题（本大题共8小题，每小题1分，共8分）提示：正确答T，错误答F，

评阅教师

得分

将其结果写到答题纸上。

T 1. There is TWO queues needed to implement the priority queue. One queue is used for actual storing of data and another for storing priorities.

T 2. A binary tree is a tree in which each node have 2 child except leaf node. F 3. When sorting n records, Quicksort has worst-case cost O(n log n). T 4. Depth-first search is best implemented using stack or recursion. T 5. We say two vertices are connected if there is a path connect them.

F 6. Consider a node in an AVL tree, the height of left sub-tree minus height of right sub-tree can only be -1 or 1. T 7. Build a hash table of set {23,44,36,48,52,73,64,58}, h(K)=K%13, then the address of element 64 is 12 F 8. The Huffman coding tree works best when the frequencies for letters are roughly the same for all letters.

评阅教师

得分

三、问答题（本大题共6小题，每小题7分，共42分）。

1. Determine (in a "Big-O" sense) the order of the following method as a function of the parameter n.

A) x=0;

for(i=1;i<n;i++) for(j=1;j<=n-i;j++) x++; B) int i,j,k;

for(i=0;i<n;i++)

for(j=0;j<=n;j++) {

c[i][j]=0;

for(k=0;k<n;k++) c[ …… 此处隐藏：4202字，全部文档内容请下载后查看。喜欢就下载吧 ……