四川大学期末考试试题
（2014-2015学年第1学期）
课程号： 课程名称： 数据结构与算法分析（B卷） 适用专业年级： 学号：
姓名：
任课教师：
考试须知 四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。 四川大学各级各类考试的监考人员，必须严格执行《四川大学考试工作管理办法》、《四川大学考场规则》和《四川大学监考人员职责》。有违反学校有关规定的，严格按照《四川大学教学事故认定及处理办法》进行处理。 题 号 得 分 阅卷教师 阅卷时间 1 20 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 卷面成绩 一、单项选择题（每小题 2 分，共20分） 1．在数据类型中，值不可分解的类型为（ ）。
A）原子类型 B）结构类型 C）固定聚合类型 D）可变聚合类型（ ）。
2．如某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，则（ ）存储方式最节省运行时间。
A）单链表 B）带头结点的单链表 C）单循环链表 D）带头结点的双循环链表
3．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，这样主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（ ）结构。
A）栈 B）队列 C）数组 D）线性表 4．串的长度是（ ）。
A）串中不同字母的个数 B）串中不同字符的个数 C）串中所含数字的个数 D）串中所有字符的个数 5．一棵深度为5的满二叉树的结点数为（ ）。
A）16 B）15 C）32 D）31
6．采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的（ ）。
A）先序遍历 B）中序遍历 C）后序遍历 D）层次遍历 7．某二叉树的先序遍历序列与后序遍历序列相反，则此二叉树一定为（ ）。
A）高度等于其结点数 B）空或只有一个结点 C）任一点无左孩子 D）任一结点无右孩子 8．堆排序的时间复杂度是（ ）。
A）O(1) B）O(n) C）O(n2) D）O(nlogn) 9．每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（ ）。
A）冒泡排序 B）简单选择排序 C）希尔排序 D）直接插入排序
10．若需在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
A）快速排序 B）堆排序 C）归并排序 D）直接插入排序 二、（本题10分）
有二叉树中序序列为：ABCEFGHD；后序序列为：ABFHGEDC；请画出此二叉树。 三、（本题10分） 注：试题字迹务必清晰，书写工整。 本题2页，本页为第1页
教务处试题编号：
课程名称：数据结构与算法分析 任课教师： 学号： 姓名： 已知序列7，31，13，11，20，35，25，8，4，11，24，40，27，请画出此序列列的排序二叉树，分别给出下列操作后的二叉树：
（1）插入数据9； （2）删除结点17； （3）再删除结点13。
四、（本题10分）
如图所示，用Prim算法从结点1出发构造出一棵最小生成树，要求图示出每一步的变化情况。
五、（本题10分）
已知哈希表地址空间为0..8，哈希函数为H(key)=key % 7，采用线性探测再散列处理冲突，将数据序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。 六、（本题10分）
具有n个叶结点的哈夫曼树共有多少个结点？并说明原因。 七、（本题10分）
给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18)。写出用下列算法从小到大排序时第一趟结束时的序列。 （1）希尔排序（第一趟排序的增量为6） （2）快速排序（选第一个记录为枢轴） 八、（本题10分）
已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，…，Nm个度为m的结点。试问该树中有多少个叶子结点？
九、（本题10分）
假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按如下图所示的树状显示二叉树。
本题2页，本页为第2页 教务处试题编号：