数据结构2014(全英文) 四川大学期末考试试题.docx

四川大学期末考试试题（闭卷）A（2013 ——2014 学年第 2 学期）课程号： 课序号： 1 课程名称：数据结构(in English ) 任课教师： 成绩：适用专业年级：13电子商务 学生人数：159 印题份数：160 学号： 姓名：考 试 须 知四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。四川大学各级各类考试的监考人员，必须严格执行《四川大学考试工作管理办法》.《四川大学考场规则》和《四川大学监考人员职责》。有违反学校有关规定的，严格按照《四川大学教学事故认定及处理办法》进行处理。Part I. Brief Description Questions（5*6=30）What does LIFO mean?List the differences between ordinary queue and circular queue.List the advantages of linked lists over arrays.What is abinary tree?Define a full binary tree.Part II. Multiple Choice Questions（10*3=30）Doubly linked lists have ( ) number of pointer fields.a)3 b)2 c) 1 Pre-order traversal means ( ).a)TlRTr b) RTlTr 2 c) TlTrR The memory space allocated for the elements of the linked list ( ) at any time.a)can be extended b) can not be extended A queue is called ( ).a)FIFO b)LIFO c)none of these The elements in the queue are processed in ( ).a)the same order b)the reverse order c)different orders d)none of these In the linked lists ( ) is involved with insertions into and deletions from the middle of the list.a)Data movement b)No Data movement The operation for adding an entry to a stack is traditionally called ( )a) add b)append c) insert d) pushThe operation for removing an entry from a stack is traditionally called ( )a) delete b)PEEK c) POP d) remove注：1试题字迹务必清晰，书写工整。 本题 2 页，本页为第 1 页 2 题间不留空，一般应题卷分开 教务处试题编号： 学号： 姓名In a binary tree, a node can have ( ) children.a) 1 b)2 c) more than 2 d) either a) or b)The maximum number of nodes possible in a binary tree of height h is ( )a)2h+1 b)2+6h c) 2h-1Part III. Algorithm application Questions（2*10=20）Give the pre_order and post_order traversal sequences of thefollowing binary tree.There are eight kinds of characters, they are { A,B,C,D,E,F,G,H }，the corresponding probab