软件学院数据结构与算法分析期末试题(2006级B).docVIP

课程名称：数据结构与算法分析 任课教师： 学号： 姓名： 本题 NUMPAGES 10页，本页为第 PAGE 10页 教务处试题编号： 注：试题字迹务必清晰，书写工整。 本题 NUMPAGES 5页，本页为第 PAGE 1页 教务处试题编号： 四川大学期末考试试题 （2007-2008学年第1学期） 课程号： 课程名称： 数据结构与算法分析（B卷） 任课教师： 适用专业年级： 06级软件工程 学号： 姓名： 考试须知 四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。 四川大学各级各类考试的监考人员，必须严格执行《四川大学考试工作管理办法》、《四川大学考场规则》和《四川大学监考人员职责》。有违反学校有关规定的，严格按照《四川大学教学事故认定及处理办法》进行处理。 题 号 1 2 3 4 5 6 7 卷面成绩 得 分 20 10 10 15 15 15 15 阅卷教师 阅卷时间 1. Single-Choice questions（each question 2 scores, total 20 scores） （1）The primary purpose of most computer programs is a) to perform a mathematical calculation. b) to store and retrieve information. c) to sort a collection of records. d) all of the above. （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）Pick the growth rate that corresponds to the most efficientalgorithm as n gets large: a) 5n b) 20 log n c) 2n^2 d) 2^n （4）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. （5）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. （6）When sorting n records, Insertion sort has best-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. （7）For a list of length n, the linked-list implementations prev function requires worst-case time: a) O(1). b) O(log n). c) O(n). d) O(n^2). （8）The easiest way to represent a general tree is to: a) convert to a list. b) convert to a binary tree. c) convert to a graph.