厦门大学《 数据结构 》课程试卷 信息科学与技术学院计算机科学系2004年级＿＿＿专业
主考教师：陈怡疆、庄朝晖、郑旭玲 试卷类型：（A卷） 一、 （本题15分）试设计一个结点数据类型为整型的带表头结点的有序单链表，然后设
计一个算法，该算法将这个有序单链表划分成两个单链表，使得第一个单链表中包含原单链表中所有数值为奇数的结点，第二个单链表中包含原单链表中所有数值为偶数的结点，且两个单链表中结点的相对排列顺序与原单链表中相同。注意：要求使用原单链表的空间，表头结点可以另辟空间。 二、
（本题20分）试设计一个递归算法，判断二叉树T是否是满二叉树，假设T是以二
叉链表存储。
typedef struct BiTNode{
TElemType data;
Struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree; 三、
（本题15分）给定下面的带权无向图G：
1） 从顶点0出发，请写出深度优先遍历序列和广度优先遍历序列，当有多种选择时，编号小的结点优先。
2） 分别使用普里姆算法和克鲁斯卡尔算法求出下图的最小生成树，仅需画出最小生成树的成长过程即可。
0 4 1 1 6 4 7 5
5 3 2 6 6 2 5 3 四、
（本题15分）设有一个关键字序列{11,73,51,31,63,37,46,2,7}，
1
1） 从空树开始构造排序二叉树，画出得到的排序二叉树；分别计算该排序二叉树在等概率下查找成功的平均查找长度和查找失败的平均查找长度；
2） 从空树开始构造平衡二叉树，画出每加入一个新结点时二叉树的形态；若发生不平衡，请画出调整平衡后的结果；分别计算该平衡二叉树在等概率下查找成功的平均查找长度和查找失败的平均查找长度。 五、
（本题10分）已知待散列存储的关键字序列为（4,15,38,49,33,60,27,71），哈希函
数为H(key)=key MOD 11，哈希表HT的长度为11，采用二次探测再散列法解决冲突。试构造此哈希表，并求出在等概率情况下查找成功的平均查找长度。 六、
（本题15分）试设计算法在O(n)时间内将数组A[1..n]划分为左右两个部分，使得
左边的所有元素为奇数，右边的所有元素均为偶数，要求所使用的辅助存储空间大小为O(1)。 七、
（本题10分）若待排序记录的关键字集合是{30,90,27,4,48,15,9,13,18}，欲将其
按关键字非递减排序：
1） 若采用快速排序（选取待排序列中的第一个记录作为枢轴），请给出第一趟和第二趟排序的结果；
2） 若采用堆排序，请画出初始建立的“大顶堆”；
3） 当给定的待排序记录的关键字基本有序时，应采用堆排序还是快速排序？为什么？ 八、
（本题不记分）请谈谈学习《数据结构》课程的心得体会，或对该课程的教学提出意
见和建议。
2