装订线—————————————————————————————————————————————————————————— 2008－2009学年第二学期
计算机科学学院《数据结构》期末考试试卷（A卷）
答案与评分标准
年级：07级 专业： 班级： 学号： 姓名： 题号 得分 一 二 三 四 五 六 总分 签名 注：1、共100分，考试时间120分钟。
2、此试卷适用于计算机科学与技术本科、信息管理与信息系统专业。
一 得 分 阅卷教师 一、填空题（本题共10小题，每个空2分，共20分）
1．数据是对客观事物的符号的表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的（ 符号的总称 ）。
2．抽象数据类型是指一个（ 数学模型 ）以及定义在该模型上的一组操作。
3. 在顺序表中插入或删除一个元素，需要平均移动（ 表中一半 ）元素，具体移动的元素个数与（ 表长和该元素在表中的位置 ）有关。
4. 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（ 108 ）。
5．循环队列的引入是为了克服（ 假溢出 ）。 6．head(tail(head(((a，b)，(c，d)))))= b 。
7．已知一棵完全二叉树共有768个结点，则该树中有（ 384 ）个叶子结点。 8．某二叉树的先序遍历序列是8，5，1，3，2，4，6，7，10，9，11 ，中序遍历序列是1，2，3，4，5，6，7，8，9，10，11，则其后序遍历序列是（2，4，3，1，7，6，5，9，11，10，8）。
9．有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的（ 出度 ）。
2
10．对n个待排序记录序列进行快速排序，其最坏时间复杂度为（ O（n） ）。
二 得 分 阅卷教师 二、选择题（本题共5小题，每个空2分，共10分）
1．算法是指 （ A ）
A．对特定问题求解步骤的一种描述，是指令的有限序列
B．计算机程序 C．解决问题的计算方法 D．数据处理
《数据结构与算法》期末考试试卷（A卷）第 1 页 共 5 页
2．若某线性表中最常用的操作是取第i个元素和查找第i个元素的前驱，则采用（ A ）存储方法最节省时间。
A．顺序表 B．单链表 C．双链表 D．单循环链表
3．设计一个判别表达式中左右括号是否配对的算法，采用（ B ）数据结构最佳。 A．队列 B．栈 C．链表 D．树
4．若一棵二叉树有10个叶子结点，则该二叉树中度为2的结点个数是 （ D ）
A．11 B．10 C．不确定 D．9
5．二叉排序树中，最小值的结点的 （ B ）
A．右指针一定为空 B．左指针一定为空
C．左、右指针均一定为空 D．左、右指针均不为为空
三 得 分 阅卷教师 三、名词解释(本题共3小题，每小题2分，共6分)
数据类型——一个值得集合和定义在这个值上的一组操作的总称；
数据结构——相互之间存在一种或多种特定关系的数据元素的集合。
栈——限定仅在表尾进行插入或删除操作的线性表。
四 得 分 阅卷教师 四、简答题与应用题(本题共7小题，每小题7分，共49分) 1、在什么情况下用顺序表