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

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

（2009~2010学年第1学期）

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

考试须知 四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。 四川大学各级各类考试的监考人员，必须严格执行《四川大学考试工作管理办法》、《四川大学考场规则》和《四川大学监考人员职责》。有违反学校有关规定的，严格按照《四川大学教学事故认定及处理办法》进行处理。 题 号 一(40%) 得 分 阅卷时间 二(8%) 三(42%) 四(10%) 卷面成绩 注意事项：1. 请务必将本人所在学院、姓名、学号、任课教师姓名等信息准确填写在试题纸和添卷纸上；

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

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

???????????????????????????????????????????????

评阅教师

得分

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

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

1. A sequence has the following properties:

*a) May have duplicates, element have a position.

b) May have duplicates, elements do not have a position. c) May not have duplicates, elements have a position.

d) May not have duplicates, elements do not have a position.

2. Pick the growth rate that corresponds to the most efficient algorithm as n gets large:

a) 5n

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

3 When we describe the lower bound for a problem we use:

a) The upper bound for the best algorithm we know. b) the lower bound for the best algorithm we know.

c) The smallest upper bound that we can prove for the best algorithm that could possibly exist. *d) The greatest lower bound that we can prove for the best algorithm that could possibly exist.

4. If an algorithm is Theta(f(n)) in the average case, then it is:

a) Omega(f(n)) in the best case. *b) Omega(f(n)) in the worst case.

注：字迹务必清晰，书写工整。

出题:

编辑:

系所审核:

学院审核:

本题共6页，本页为第1页 教务处试题编号：

课程名称： 任课教师： 学号： 姓名：

c) O(f(n)) in the worst case.

5 When we say that a list implementation enforces homogeneity, we mean that:

a) All list elements have the same size. *b) All list elements have the same type. c) All list elements appear in sort order.

6. The height of a binary tree is:

a) The height of the deepest node. b) The depth of the deepest node.

*c) One more than the depth of the deepest node.

7. A full binary tree is one in which:

*a) Every internal node has two non-empty children.

b) all of the levels, except possibly the bottom level, are filled.

8. If a node is at position r in the array implementation for a complete binary tree, then its parent 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.

9. When implementing heaps and BSTs, which is the best answer?

a) The time to build a BST of n nodes is O(n log n), and the time to build a heap of n nodes is O(n log n). b) The time to build a BST of n nodes is O(n), and the time to build a heap of n nodes is O(n log n). *c) The time to build a BST of n nodes is O(n log n), and the time to build a heap of n nodes is O(n). d) The time to build a BST of n nodes is O(n), and the time to build a heap of n nodes is O(n).

10. We use the parent pointer representation for general trees to solve which problem?

a) Shortest paths

b) General tree traversal *c) Equivalence classes d) Exact-match query

11. Which sorting algorithm does not have any practical use?

a) Insertion sort. *b) Bubble sort. c) Quicksort. d) Radix Sort. e) a and b.

12. When sorting n records, Quicksort has average-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.

注：字迹务必清晰，书写工整。

本题共6页，本页为第2页 教务处试题编号：

课程名称： 任课教师： 学号： 姓名：

13. In the worst case, the very best that a sorting algorithm can do when sorting n records is:

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

*c) O(n log n). d) O(n^2) e) O(n!)

f) None of the above.

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. In external sorting, a run is:

*a) A sorted sub-section for a list of records. b) One pass through a file being sorted. c) The external sorting process itself.

16. Self-organizing lists attempt to keep the list sorted by:

a) value

*b) frequency of record access c) size of record

17. A good hash function will:

a) Use the high-order bits of the key value. b) Use the middle bits of the key value. c) Use the low-order bits of the key value. *d) Make use of all bits in the key value.

18. Indexing is:

a) Random access to an array.

*b) The process of associating a key with the location of a corresponding data record. c) Using a hash table.

19. Tree indexing methods are meant to overcome what deficiency in hashing?

*a) Inability to handle range queries. b) Inability to handle updates.

c) Inability to handle large data sets.

20. 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.

注：字迹务必清晰，书写工整。

本题共6页，本页为第3页 教务处试题编号：

课程名称： 任课教师： 学号： 姓名：

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

评阅教师

得分

将其结果写到答题纸上。

F 1. Queue is the data structures used to perform recursion.

T 2. A binary tree is a tree in which each node have 2 child except leaf node. F 3. A topological sort requires The graph contain cycles.

T 4. We say two vertices are adjacent only when there is an edge connect them. 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. F 7. The C++ programmer's view of a disk file is most like a graph.

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 \

A) x=0;

for(i=1;i

B) fact(n) {

if(n<=1)

return (1); else return (n*fact(n-1)); }

A) O(n2) B) O(n)

2. Suppose a binary-tree, the pre-order sequence of this binary-tree is EBADCFHGIKJ, and the in-order sequence of it is ABCDEFGHIJK, please write down the post-order sequence of this binary-tree.

ACDBGJKIHFE

3. Build the Huffman coding tree for the following set of weights (5，9，11，2，7，16)

答案

注：字迹务必清晰，书写工整。

本题共6页，本页为第4页 教务处试题编号：

课程名称： 任课教师： 学号： 姓名：

50 20 9

11 7 2

30 14 7 5 16

4. Write down the DFS and BFS sequence of graph below: (Attention: while traversing, choose vertex from numeric sequence when more than one vertex can be chosen)

0 3 6 1 4 7

2 5 8

深度优先搜索序列：0,4,7,5,8,3,6,1,2 广度优先搜索序列：0,4,3,1,7,5,6,2,8

5. Give out the topologic sort result of the graph below, using BFS. (Attention! while traversing, choose vertex from numeric sequence when more than one vertex can be chosen)

答案： C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7

6 What are the minimum and maximum number of elements in a heap of height h?

答案：The minimum number of elements is contained in the heap with a single node at depth h ? 1, for a total of 2h?1 nodes.

The maximum number of elements is contained in the heap that has completely filled up level h ? 1, for a total of 2h ? 1 nodes.

注：字迹务必清晰，书写工整。

本题共6页，本页为第5页 教务处试题编号：

课程名称： 任课教师： 学号： 姓名：

评阅教师 得分

四、编程、设计及分析题（本大题共2小题，共12分）。提示：题目给出了一个程

序设计要求，请按照要求写出源程序代码，如果源程序代码中出现语法错误或逻辑错误，则酌情扣分。

A palindrome is a string that read the same forwards as backwards. Using only a fixed number of stacks of int and char variables, write an algorithm to determine if a string is a palindrome. Assume that the string is read from standard input one character at a time. The algorithm should output true or false as appropriate.

答案

bool palin() {

Stack S; Queue Q;

while ((c = getc()) != ENDOFSTRING) {

S.push(c); Q.enqueue(c); }

while (!S.isEmpty()) {

if (S.top() != Q.front())

return FALSE; char dum = S.pop(); dum = Q.dequeue(); }

return TRUE; }

注：字迹务必清晰，书写工整。

本题共6页，本页为第6页 教务处试题编号：

课程名称： 任课教师： 学号： 姓名：

评阅教师 得分

四、编程、设计及分析题（本大题共2小题，共12分）。提示：题目给出了一个程

序设计要求，请按照要求写出源程序代码，如果源程序代码中出现语法错误或逻辑错误，则酌情扣分。

A palindrome is a string that read the same forwards as backwards. Using only a fixed number of stacks of int and char variables, write an algorithm to determine if a string is a palindrome. Assume that the string is read from standard input one character at a time. The algorithm should output true or false as appropriate.

答案

bool palin() {

Stack S; Queue Q;

while ((c = getc()) != ENDOFSTRING) {

S.push(c); Q.enqueue(c); }

while (!S.isEmpty()) {

if (S.top() != Q.front())

return FALSE; char dum = S.pop(); dum = Q.dequeue(); }

return TRUE; }

注：字迹务必清晰，书写工整。

本题共6页，本页为第6页 教务处试题编号：

本文来源：https://www.bwwdw.com/article/u2dr.html