软件 数据结构 中期考试091109（含部分答案）

四川大学期中考试试题（闭卷） （2009~2010学年第1学期）

课程号： 311036030 课程名称： 数据结构与算法分析 任课教师： 孙界平、张卫华

适用专业年级： 软件工程 2008级 学号：

姓名：

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

2. 考试结束，请将试卷和答题纸一并交给监考老师。

评阅教师

得分

一、单项选择题（本大题共40小题，每小题1分，共40分）提示：在每小题列出的备选项中只有一个是符合题目要求的，请将其代码填写在下表中。错选、多选或未选均无分

21 26 31 36 22 27 32 37 23 28 33 38 24 29 34 39 25 30 35 40 本题16页，本页为第1

系所审核：

学院审核：

教务处试题编号：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 注：试题字迹务必清晰，书写工整。

页

出题：

编辑：

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

1. A solution is efficient if

a) it solves a problem within the require resource constraints. b) it solves a problem within human reaction time. c) it solves a problem faster than other known solutions. d) a and b. *e) a and c. f) b and c.

2. Assume that P contains n elements. The number of sets in the powerset of P is a) n b) n^2 *c) 2^n d) 2^n - 1 e) 2^n + 1

3. R is an equivalence relation on set S if it is ( ) *a) reflexive, symmetric, transitive. b) reflexive, antisymmetric, transitive. c) symmetric, transitive. d) antisymmetric, transitive. e) irreflexive, symmetric, transitive. f) irreflexive, antisymmetric, transitive.

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

页

教务处试题编号：

本题16页，本页为第2

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

4. Mathematical induction is most like ( ) a) iteration. *b) recursion. c) branching. d) divide and conquer.

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

6. Asymptotic analysis refers to: ( )

a) The cost of an algorithm in its best, worst, or average case.

*b) The growth in cost of an algorithm as the input size grows towards infinity.

c) The size of a data structure.

d) The cost of an algorithm for small input sizes

7. For an air traffic control system, the most important metric is: ( ) a) The best-case upper bound. b) The average-case upper bound.

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

页

教务处试题编号：

本题16页，本页为第3

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

*c) The worst-case upper bound. d) The best-case lower bound. e) The average-case lower bound. f) The worst-case lower bound.

8. The best case for an algorithm refers to: ( ) a) The smallest possible input size.

*b) The specific input instance of a given size that gives the lowest cost. c) The largest possible input size that meets the required growth rate. d) The specific input instance of a given size that gives the greatest cost.

9. Here is a series of C++ statements using the list ADT in the book. ( )

L1.append(10); L1.append(20); L1.append(15);

If these statements are applied to an empty list, the result will look like:

a) < 10 20 15 > *b) < | 10 20 15 > c) < 10 20 15 | > d) < 15 20 10 > e) < | 15 20 10 >

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

页

教务处试题编号：

本题16页，本页为第4