-《数据结构与算法》试卷.doc

1、四川大学期末考试试题（闭卷）（20092010学年第2 学期）课程号：311036030课程名称：数据结构与算法（ C 卷）任课教师： 孙界平 杨秋辉 张卫华适用专业年级：软件工程2009级学号：姓名：考试须知四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行四川大学考试工作管理办法和四川大学考场规则。有考试违纪作弊行为的，一律按照四川大学学生考试违纪作弊处罚条例进行处理。四川大学各级各类考试的监考人员，必须严格执行四川大学考试工作管理办法、四川大学考场规则和四川大学监考人员职责。有违反学校有关规定的，严格按照四川大学教学事故认定及处理办法进行处理。题号一(30% )二(10%

2、 )三(15% )四(20% )五(25% )卷面成绩得分阅卷时间注意事项： 1. 请务必将本人所在学院、姓名、学号、任课教师姓名等信息准确填写在试题纸和添卷纸上；2. 请将答案全部填写在本试题纸上；3. 考试结束，请将试题纸、添卷纸和草稿纸一并交给监考老师。评阅教师得分一、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分）提示：在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在答题纸上。错选、多选或未选均无分。1. An array is ()(A) A contiguous block of memory locations where each memor

3、y location stores a fixed-length data item.(B) An ADT composed of a homogeneous collection of data items, each data item identified by a particular number.(C) a set of integer values.(D) a and b.2. Pick the growth rate that corresponds to the most efficient algorithm as n gets large: ()(A) 5n(B) 20

4、log n(C) 2n2(D) 2n3. When the upper and lower bounds for an algorithm are the same, we use: ()(A) big-Oh notation.(B) big-Omega notation.注：字迹务必清晰，书写工整。本题共 6 页，本页为第1 页出题 : 张卫华编辑 :系所审核 :学院审核 :教务处试题编号：(C) Theta notation.(D) asymptotic analysis.4. When comparing the doubly and singly linked list impleme

5、ntations, we find that the doubly linkedlist 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.(D) Saves time and space together.5. Huffm

6、an coding provides the optimal coding when: ()(A) The messages are in English.(B) The messages are binary numbers.(C) The frequency of occurrence for a letter is independent of its context within the message.(D) Never.6. The primary access function used to navigate the general tree when performing U

7、NION/FIND is: ( )(A) leftmost child(B) right child(C) right sibling(D) parent7. When sorting n records, Insertion sort has best-case cost: ()(A) O(log n).(B) O(n).(C) O(n log n).(D) O(n2)8. When sorting n records, Selection sort will perform how many swaps in the worst case? ()(A) O(log n).(B) O(n).

8、(C) O(n log n).(D) O(n2)9. The basic unit for disk allocation under DOS or Windows is: ()(A) A byte.(B) A sector.(C) A cluster.(D) A track.10. When properly implemented, which search method is generally the most efficient forexact-match queries? ()(A) Binary search.(B) Dictionary search.(C) Search i

9、n self-organizing lists(D) Hashing11. 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.12. Indexing is: ()(A) Random access to an array.(B) The proc

10、ess of associating a key with the location of a corresponding data record.(C) Using a hash table.(D) None of the above.13. A 2-3 tree is a specific variant of a: ()(A) Splay tree.(B) B-tree.(C) BST.(D) Trie.14. The single-source shortest path problem can be used to: ()(A) Sort all of the graph verti

11、ces by value.(B) Sort all of the graph vertices so that each vertex is listed prior to any others that depend on it.(C) Sort all of the graph vertices by distance from the source vertex.(D) None of the above.15. A topological sort requires all of the following except: ()(A) The graph be directed.(B)

12、 The graph contain no cycles.(C) The graph contain weights on the edges.(D) None of the above.评阅教师得分二、判断题（本大题共 5 小题，每小题 2 分，共 10 分）提示：正确打 T，错误打 F，将其结果填写在答题纸上。1. Given two hash function h 1 and h2 and key k1, If h 1 (k1) = h2 (k1), then we say that h1 and h2 have a collision. ( )2. The number of leav

13、es in a non-empty full binary tree is one more than the number of internal nodes. ( )3. A serious disadvantage for Mergesort is that it requires twice the amount of space of sorting data. ( )4. For given set of elements, the shape of the corresponding BST is unique, and it is independentof the order

14、 in which elements are inserted. ()5. Linked lists are better than array-based lists when implementing lists whose number of elements varies widely or is unknown. ( )评阅教师得分三、名词解释题（本大题共 3 小题，每小题 5 分，共 15 分）。提示：解释每小题所给名词的含义，若解释正确则给分，若解释错误则无分，若解释不准确或不全面，则酌情扣分。1. Full Binary Tree2. Data structure3. inte

15、rleave factor评阅教师得分四、应用题（本大题共 4小题，每小题 5 分，共 20 分）。提示：请给出准确答案，如果有中间步骤，答案错误的情况下有步骤分。1. AVL tree of input sequence 16, 3, 7, 11, 9, 26, 18, 14, 152. Draw the binary tree represented byAB/DCEG/FHI3. Proof: To any binary tree, if it has n0 leaf node, n2 internal node of degree=2, n0=n2+14. Insert 14, 19,

16、 22, 23 to B+ tree in sequence评阅教师得分五、编程题（本大题共 2 小题，共 25 分）。提示：每小题给出了一个程序设计要求，请按照要求写出源程序代码，如果源程序代码中出现语法错误或逻辑错误，则酌情扣分。1. Write a function to calculate the depth of a binary tree(共 10 分)2. Write a recursive function named printRange that, given the pointer to the root to a BST, a low key value, and a high key value, prints in sorted order all records whose key values fall between the two given keys. Function printRange should visit as few nodes in the BST as possible. (共 15 分)善良是女人最好的修