2018年华中科技大学887数据结构与算法分析
复习八套卷 一（
版）
一．名词解释（25分，1个5分）
1.1抽象数据类型 1.2有序树和无序树 1.3二叉排序树 1.4深度优先搜索 1.5算法的稳定性
二．选择题（25分，1个5分）
2.1 下列算法的时间复杂度为（ ）
void fun (int n){
int i=0;
while(i*i*i<=n) i++; }
A. O(n) B. O(nlogn) C.
D.
2.2．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ） A．O（i） B．O（1） C．O（n） D．O（i-1）
2.3下面哪一方法可以判断出一个有向图是否有环（回路） （ ）
A．深度优先遍历 B. 求两个结点之间的路径 C. 求最短路径 D. 求关键路径
2.4一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2
2.5一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ） A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG
三．简答题（60分）
3.1一颗二叉树的先序，中序，后序如下所示，填空，并画出该树。（12分） 先序序列 ：_ _ C D E _ G H I _ K 中序序列 ：C B _ _ F A _ J K I G 后序序列 ：_ E F D B _ J I H _ A
3.2一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。 求该青蛙跳上一个n 级的台阶总共有多少种跳法。（12分）
3.3 根据下图回答下列问题
(1)从顶点A出发，求它的深度优先生成树。（4分） (2)从顶点E出发，求它的广度优先生成树。（4分） (3)根据普利姆(Prim) 算法，写出具体的过程。（4分）
3.4待排序的关键码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。 (1) 快速排序。（6分） (2) 二路归并排序。（6分）
3.5假设哈希表的地址范围是0-8，哈希函数为：H(K)=（K +1）MOD9 K为关键字，用线性表探测再散列法处理冲突，输入关键字序列｛13，32，17，31，30，36，63｝ 回答下列问题：
（1）画出构造的哈希表。（6分）
（2）计算成功查找长度以及失败查找长度。（6分）
四．算法设计（40分）（编码困难可以写伪代码，会适当扣分）
4.1已知两个链表A和B分别表示两个集合，其元素递增排列。编写函数，求A与B的交集，并存放于A链表中，并分析所用的时间复杂度（20分）
4.2试写出算法，求任意二叉树中第一条最长的路径长度（多条相等只输出一条），并输出此路径上各结点的值。（20分） typedef struct BiTree {
int data；
struct BiTree *Rc； struct BiTree *Lc； } * BiTree；
2018年华中科技大学887数据结构与算法分析
复习八套卷 一（
版）答案
一．名词解释（25分，1个5分）
1.1抽象数据类型
答：ADT，指一个数学模型以及定义在该模型上的一组操作。通常用数据对象、数据关系、基本操作集这样的三元组来表示。有数据抽象和数据封装两个重要特性。 1.2有序树和无序树
答：树中结点的子树从左到右是有次序的，不能交换，叫做有序树。反之为无序树。 1.3二叉排序树 答：一棵二叉树或是空二叉树或是具有以下性质的二叉树：左子树上所有关键字均小于根结点的关键字，右子树所有结点关键字大于根结点的关键字。左子树和右子树又各是一棵二叉排序树。
1.4深度优先搜索
答：类似于树的先序遍历，假设从图中某顶点V出发，在访问了V之后一次从V的未被访问的邻接点出发做深度优先遍历，知道图中所有和v有路径相同的顶点都被访问到。若图中还有顶点未访问，则另选图中一个未曾被方位的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问。 1.5算法的稳定性
答：假设Ri=Rj，且在排序之前Ri领先于Rj，若在排序后的序列中Ri仍然领先于Rj，则称所用的排序算法是稳定的，反之则称所用的算法是不稳定的。
二．选择题（25分，1个5分）
2.1 下列算法的时间复杂度为（C）
void fun (int n){ int i=0;
while(i*i*i<=n) i++; }
A. O(n) B. O(nlogn) C.
D.
算法的基本运算是i++，设其执行时间为T(n)，则有，T(6)*T(n)*T(n)<=n，即T(n)3<=n。故
有，。
2.2．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C ） A．O（i） B．O（1） C．O（n） D．O（i-1）
2.3下面哪一方法可以判断出一个有向图是否有环（回路） （A）
A．深度优先遍历 B. 求两个结点之间的路径 C. 求最短路径 D. 求关键路径
2.4一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2
2.5一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ B ） A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG
八．简答题（60分）
3.1一颗二叉树的先序，中序，后序如下所示，填空，并画出该树。（10分） 先序序列 ：A B C D E F G H I J K 中序序列 ：C B E D F A H J K I G 后序序列 ：C E F D B K J I H G A
3.2一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。 求该青蛙跳上一个n 级的台阶总共有多少种跳法。（12分）
递归解法。
3.3 根据下图回答下列问题（12分）
(1)从顶点A出发，求它的深度优先生成树
(2)从顶点E出发，求它的广度优先生成树
（3）根据普利姆(Prim) 算法，写出具体的过程。
设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列 (1)ABGFDEC (2)EACFBDG (3)
A 2 A 2 2 A A 2 D D B D 3 1 3 3 D F F G G 1 F 3
2 A A 2 4 D 4 D C B B C 3 E 1 3 3 3 F F G 1 G 1
3.4待排序的关键码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。 (1) 快速排序 （6分） (2) 二路归并排序（6分） （1）快速排序
(2) 二路归并排序
3.5假设哈希表的地址范围是0-8，哈希函数为：H(K)=（K+1） MOD9 K为关键字，用线性表探测再散列法处理冲突，输入关键字序列｛13，32，17，31，30，36，63｝ 回答下列问题：
（1）画出构造的哈希表。（6分）
（2）计算成功查找长度以及失败查找长度。（6分） 地址 0 1 36 1 3 2 63 2 2 3 1 4 30 1 5 5 13 1 4 6 32 1 3 7 31 3 2 8 1 关键字 17 比较次 1 失败 4
成功 10/7 失败 25/9
九．算法设计（40分）（编码困难可以写伪代码，会适当扣分）
4.1已知两个链表A和B分别表示两个集合，其元素递增排列。编一函数，求A与B的交集，并存放于A链表中，并分析所用的时间复杂度（20分）
4.2试写出算法，求任意二叉树中第一条最长的路径长度（多条相等只输出一条），并输出此路径上各结点的值。（20分） typedef struct BiTree {
int data；
struct BiTree *Rc； struct BiTree *Lc； } * BiTree；
因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。
void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度
{BiTree p=bt,l[],s[]; //l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点
int i，top=0,tag[],longest=0; while(p || top>0)
{ while(p) {s[++top]=p；tag[top]=0; p=p->Lc;} //沿左分枝向下
if(tag[top]==1) //当前结点的右分枝已遍历
{if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时，才查看路径长度 if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;}
//保留当前最长路径到l栈，记住最高栈顶指针，退栈 }
else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下 }//while(p!=null||top>0) }//结束LongestPath
2018年华中科技大学887数据结构与算法分析
复习八套卷 二（
版）
一．名词解释（25分，1个5分）
1.1时间复杂度 1.2队列 1.3判定树 1.4 AOE网 1.5装填因子
二．选择题（25分，1个5分）
2.1 下列算法的时间复杂度为（ ）
int fun(int n,int b){ if (n<=l) return 1; return n*fun(n-1,b-1)+b; }
A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2)
2.2．数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。
A. 1175 B. 1180 C. 1205 D. 1210
2.3设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。
A． 6 B. 4 C. 3 D. 2
2.4 具有10个叶结点的二叉树中有（ ）个度为2的结点
A．8 B．9 C．10 D．ll
2.5在用邻接表表示图时，拓扑排序算法时间复杂度为( )。
A. O(n) B. O(n＋e) C. O(n*n) D. O(n*n*n)
三．简答题（60分）
3.1．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）(12分) D G A E J H I B C F K L M N O
P 3.2写出下图双链表中对换值为23和15的两个结点相互位置时修改指针的有关语句。
结点结构为：(llink,data,rlink) (12分)
p
10231530
3.3已知无向图如下所示：(12分)
（1）．给出从V1开始的广度优先搜索序列；（2）．画出它的邻接表； （3）．画出从V1开始深度优先搜索生成树。
3.4对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：（12分）
（1） 当n=7时，在最好情况下需进行多少次比较？请说明理由。 （2） 当n=7时，给出一个最好情况的初始排序的实例。
（3） 当n=7时，在最坏情况下需进行多少次比较？请说明理由。 （4） 当n=7时，给出一个最坏情况的初始排序的实例。
3.5给定集合{15,3,14,2,6,9,16,17}（12分）
(1)（3分）构造相应的huffman树： (2) (3分)计算它的带权路径长度： (3)（3分)写出它的huffman编码：
(4)（3分)huffman编码常用来译码，请用语言叙述写出其译码的过程。
四．算法设计（40分）（编码困难可以写伪代码，会适当扣分）
4.1冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。（20分）
4.2试给出二叉树的自下而上、自右而左的层次遍历算法。（20分）
2018年华中科技大学887数据结构与算法分析
复习八套卷 二（
版）答案
一．名词解释（25分，1个5分）
1.1时间复杂度
答：一般情况下，算法中基本操作的重复次数是问题规模n的某个函数f（n），算法的时间度量记作T（n）=O（f（n）），表示随着问题规模n的增大，算法执行时间增长率和f（n）的增长率相同，称为时间复杂度。 1.2队列
答：一种先进先出的线性表，只允许在表的一段插入元素，另一端删除元素，在队列中允许插入的一端为队尾，允许删除的一端为队头。 1.3判定树
答：树中每个结点表示表中的一个记录，结点里的值为该记录在表中的位置，通常称这个查找过程的二叉树为判定树。 1.4 AOE网
答：在带权有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销（如时间），则称这个网络为AOE网。 1.5装填因子 答：哈希表中填入的记录数和哈希表的长度之商，哈希表的平均查找长度是装填因子的函数，不是规模的函数。（散列表的查找效率取决于三个因素：散列函数/处理冲突的方法和装填因子）
二．选择题（25分，1个5分）
2.1 下列算法的时间复杂度为（B）
int fun(int n,int b){ if (n<=l) return 1; return n*fun(n-1,b-1)+b; }
A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2)
2.2．数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( A )。
A. 1175 B. 1180 C. 1205 D. 1210
2.3设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( C )。
A． 6 B. 4 C. 3 D. 2
2.4 具有10个叶结点的二叉树中有（B ）个度为2的结点
A．8 B．9 C．10 D．ll
2.5在用邻接表表示图时，拓扑排序算法时间复杂度为( B )。
A. O(n) B. O(n＋e) C. O(n*n) D. O(n*n*n)
三．简答题（60分）
3.1．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果） D G A J H I E B C K N O L M F P A
答案： B D
E G C
H F I KO J L M P N O
3.2写出下图双链表中对换值为23和15的两个结点相互位置时修改指针的有关语句。
结点结构为：(llink,data,rlink)
p
10231530
设 q=p->llink; 则
q->rlink=p->rlink; p->rlink->llink=q;
p->llink=q->llink; q->llink->rlink=p; p->rlink=q; q->llink=p
3.3已知无向图如下所示：(12分)
（1）．给出从V1开始的广度优先搜索序列；（2）．画出它的邻接表； （3）．画出从V1开始深度优先搜索生成树。
（1） 广度优先搜索序列：V1V2V3V4V5V6V7V8 （2） 略
（3） 深度优先搜索序列：V1V2V4V8V5V3V6V7
3.4对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：（12分）
（1） 当n=7时，在最好情况下需进行多少次比较？请说明理由。 （2） 当n=7时，给出一个最好情况的初始排序的实例。
（3） 当n=7时，在最坏情况下需进行多少次比较？请说明理由。 （4） 当n=7时，给出一个最坏情况的初始排序的实例。
k
(1) 在最好情况下，假设每次划分能得到两个长度相等的子序列，序列的长度n=2-1，那么第一遍划分得到两个长度均为?n/2?的子序列，第二遍划分得到4个长度均为?n/4?的子序列，以此类推，总共进行k=log2(n+1)遍划分，各子序列的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一遍需比较6次，第二遍分别对两个子序列（长度均为3，k=2）进行排序，各需2次，共10次即可。
(2) 在最好情况下快速排序的原始序列实例：4,1,3,2,6,5,7。 (3) 在最坏情况下，若每次用来划分的记录的关键字具有最大值(或最小值)，那么只能得到左(或右)子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递增次序排列时，快速排序的效率与冒泡排序相同，其时间复杂度为2
O(n)。所以当n=7时，最坏情况下的比较次数为21次。
(4) 在最坏情况下快速排序的初始序列实例： 7,6,5,4,3,2,1，要求按递增排序。
3.5给定集合{15,3,14,2,6,9,16,17}
(1)（3分）构造相应的huffman树： (2) (3分)计算它的带权路径长度： (3)（3分)写出它的huffman编码：
(4)（3分)huffman编码常用来译码，请用语言叙述写出其译码的过程。 (1)略
(2）wpl=(2+3)*5+6*4+(9+14+15)*3+(16+17)*2=229
(3) 编码为：15:111, 3:10101, 14:110, 2:10100, 6:1011, 9:100, 16:00, 17:01 (4) 常用哈夫曼树为通讯用的字符编码，本题中集合的数值解释为字符发生的频率（次数）。由哈夫曼树构造出哈夫曼编码。译码时，进行编码的“匹配”，即从左往右扫描对方发来的“编码串”，用字符编码去匹配，得到原来的元素（本题中的数）。
四．算法设计（40分）（编码困难可以写伪代码，会适当扣分）
4.1冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。（20分）
void BubbleSort2(int a[],int n) //相邻两趟向相反方向起泡的冒泡排序算法
{ change=1;low=0;high=n-1; //冒泡的上下界
while(low { change=0; //设不发生交换 for(i=low;i if(a[i]>a[i+1]){a[i]<-->a[i+1];change=1;} //有交换，修改标志change high--; //修改上界 for(i=high;i>low;i--) //从下向上起泡 if(a[i] }//BubbleSort2 [算法讨论]题目中“向上移”理解为向序列的右端，而“向下移”按向序列的左端来处理。 4.2试给出二叉树的自下而上、自右而左的层次遍历算法。（20分） [题目分析] 借助队列和栈，最后弹出栈中元素实现对二叉树按自下至上，自右至左的层次遍历 void InvertLevel(biTree bt) // 对二叉树按自下至上，自右至左的进行层次遍历 {if(bt!=null) {StackInit(s); //栈初始化，栈中存放二叉树结点的指针 QueueInit(Q); //队列初始化。队列中存放二叉树结点的指针 QueueIn(Q,bt); while(!QueueEmpty(Q)) //从上而下层次遍历 {p=QueueOut(Q); push(s,p); //出队, 入栈 if(p->lchild) QueueIn(Q,p->lchild); //若左子女不空，则入队列 if(p->rchild) QueueIn(Q,p->rchild);} //若右子女不空,则入队列 while(!StackEmpty(s)) {p=pop(s); printf(p->data);} //自下而上,从右到左的层次遍历 }//if(bt!=null) } //结束InvertLevel 2018年华中科技大学887数据结构与算法分析 复习八套卷 三（ 版） 一．名词解释（25分，1个5分） 1.1数据结构 1.2满二叉树 1.3最小生成树 1.4线性表 1.5关键字 二．选择题（25分，1个5分） 2.1 下列算法的时间复杂度为( ) for(i=2;i<=n;++i) for(j=2;j<=i-1;++j) {++x; a[i,j]=x; } A. O(n) B. O(3n) C. O(n-3n+2) D. O(n) 2.2．链表不具有的特点是（ ） A．插入、删除不需要移动元素 B．所需空间与线性长度成正比 C．不必事先估计存储空间 D．可随机访问任一元素 2.3 (1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义； 3 (2). 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n ) ；（图用邻接矩阵表示） (3). Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。 上面不正确的是（ ）。 A．(1),(2),(3) B．(1) C．(1),(3) D．(2),(3) 2.4在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个 A．4 B．5 C．6 D．7 2.5表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ ）。其中^为乘幂 。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- 2 2 C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 三.简答题（60分） 3.1设一棵二叉树的先序、中序遍历序列分别为 先。序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （12分） （1）画出这棵二叉树。 （2）画出这棵二叉树的后序线索树。 （3）将这棵二叉树转换成对应的树（或森林）。 3.2有线性表(a1,a2,…,an),采用单链表存储，头指针为H，每个结点中存放线性表中一个元素，现查找某个元素值等于X的结点。分别写出下面三种情况的查找语句。要求时间尽量少。（12分） （1）线性表中元素无序。 （2）线性表中元素按递增有序。 （3）线性表中元素按递减有序。 3.3已知一个无向图如下图所示，要求分别用Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。（12分） 3.4已知一组关键字序列为（25，51，8，22，26，67，11，16，54，41），其散列地址空间为[0,…,12]，若Hash函数定义为：H(key) = key MOD 13，采用线性探测法处理冲突，请画出它们对应的哈希表。 （12分） 3.5给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列； （12分） (1) 希尔排序（第一趟排序的增量为5） (2) 快速排序（选第一个记录为枢轴（分隔）） (3) 链式基数排序（基数为10） 四 算法设计（40分）（编码困难可以写伪代码，会适当扣分） 4.1设有一元素为整数的线性表L=(a1,a2,a3,…,an),存放在一维数组A[N]中,设计一个算法,以表中an作为参考元素,将该表分为左、右两部分,其中左半部分每个元素小于等于an,右半部分每个元素都大于an, an位于分界位置上(要求结果仍存放在A[N]中),要求时间复杂度为O(n)（20分） 4.2设计算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数目。（20分） typedef struct BiTree { int data； struct BiTree *Rchild； struct BiTree *Lchild； } * BiTree； 2018年华中科技大学887数据结构与算法分析 复习八套卷 三（ 版）答案 一．名词解释（25分，1个5分） 1.1数据结构 答：1.一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。2.相互之间存在一种或多种特定关系的数据元素的集合。包括（逻辑结构、存储结构和数据的运算）。 1.2满二叉树 答：一棵高度为h，并且含有2^h -1个结点的二叉树称为满二叉树。即每层都有最多的结点，叶子集中在二叉树的最下一层且除叶子之外的每个结点度为2. 1.3最小生成树 答：一个带权连通无向图的生成树中边的权值之和最小的那个叫做此图的最小生成树。 1.4线性表 答：具有相同数据类型的n（n>=0）个数据元素的有限序列。 线性表的顺序存储又称顺序表；链式存储又称单链表。 1.5关键字 答：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。 二．选择题（25分，1个5分） 2.1 下列算法的时间复杂度为(D) for(i=2;i<=n;++i) for(j=2;j<=i-1;++j) {++x; a[i,j]=x; } A. O(n) B. O(3n) C. O(n-3n+2) D. O(n) 2.2．链表不具有的特点是（D ） A．插入、删除不需要移动元素 B．所需空间与线性长度成正比 C．不必事先估计存储空间 D．可随机访问任一元素 2.3 (1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义； 3 (2). 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n ) ；（图用 2 2 邻接矩阵表示） (3). Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。 上面不正确的是（ C ）。 A．(1),(2),(3) B．(1) C．(1),(3) D．(2),(3) ? (1)错。Dijkstra不能为负权，因为算法中使用了优先队列和BFS思想，若有负权，则先出队列的可能并不是全局路径最短的，因为后面可能还有负值更大（即更短的路径），比如求(a, c)路径，有路径a -> b (-10)-> c(-10)，则为-20时，c出队列，而有另外路径a -> d(1) -> c(100)，d的权为1因此出不了队列，后面(d,c)为-100的权就无法在c出队列之前更新c了，因此造成最短路径为(a,b,c)，实际上最短路径为(a,d,c)。 (2)对。Dijkstra算法采用数组结构时（即邻接矩阵），O(n2)，则求每对顶点之间最短路径再加一层循环，循环数n，因此为O(n3)；但是要注意Dijkstra算法采用二叉堆且满足源点可达任意顶点时时，为O(ElgV) (3)错。Floyd-Warshall算法是动态规划算法，核心思想是从至多包含一条边的路径矩阵发散到至多包含(n-1)边的路径矩阵，该算法不要求图中无负权回路。 2.4在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ C ）个 A．4 B．5 C．6 D．7 2.5表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ D ）。其中^为乘幂 。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 三.简答题（60分） 3.1设一棵二叉树的先序、中序遍历序列分别为 先。序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C（12分） （1）画出这棵二叉树。 （2）画出这棵二叉树的后序线索树。 （3）将这棵二叉树转换成对应的树（或森林）。 3.2有线性表(a1,a2,…,an),采用单链表存储，头指针为H，每个结点中存放线性表中一个元素，现查找某个元素值等于X的结点。分别写出下面三种情况的查找语句。要求时间尽量少。（12分） （1）线性表中元素无序。 （2）线性表中元素按递增有序。 （3）线性表中元素按递减有序。 设单链表带头结点，工作指针p初始化为p=H->next; (1) while(p!=null && p->data!=X) p=p->next; if(p= =null) return(null);∥查找失败 else return(p);∥查找成功 (2) while(p!=null && p->data if(p==null || p->data>X) return(null);∥查找失败 else return(p); (3) while(p!=null && p->data>X) p=p->next; if(p==null || p->data 3.3已知一个无向图如下图所示，要求分别用Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。（12分） Kruskal （下图也可选(2,4)代替(3,4),(5,6)代替(1,5)） 2 3 1 9 1 5 10 6 6 3 4 5 2 6 11 3.4已知一组关键字序列为（25，51，8，22，26，67，11，16，54，41），其散列地址空间 为[0,…,12]，若Hash函数定义为：H(key) = key MOD 13，采用线性探测法处理冲突，请画出它们对应的哈希表 （12分） 地址空间 序列 0 51 1 26 2 67 3 16 4 54 5 41 6 7 8 8 9 22 10 11 11 12 25 3.5给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列； （12分） (1) 希尔排序（第一趟排序的增量为5） (2) 快速排序（选第一个记录为枢轴（分隔）） (3) 链式基数排序（基数为10） (1)一趟希尔排序: 12,2,10,20,6,18,4,16,30,8,28 （ D=5） (2)一趟快速排序：6,2,10,4,8,12,28,30,20,16,18 (3)链式基数排序LSD [0][1][2][3][4][5][6][7][8][9] ↓ ↓ ↓ ↓ ↓ 分配 30 12 4 16 8 ↓ ↓ ↓ ↓ 10 2 6 28 ↓ ↓ 20 18 收集：→30→10→20→12→2→4→16→6→8→28→18 四 算法设计（40分）（编码困难可以写伪代码，会适当扣分） 4.1设有一元素为整数的线性表L=(a1,a2,a3,…,an),存放在一维数组A[N]中,设计一个算法,以表中an作为参考元素,将该表分为左、右两部分,其中左半部分每个元素小于等于an,右半部分每个元素都大于an, an位于分界位置上(要求结果仍存放在A[N]中),要求时间复杂度为O(n)（20分） 片段： i=1;j=n; t=a[n]; ∥暂存参考元素。 while(i {while(i while(i if(i 4.2设计算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数目。（20分） typedef struct BiTree { int data； struct BiTree *rchild； struct BiTree *lchild； } * BiTree； void Count(BiTree bt,int *n0,*n) //统计二叉树bt上叶子结点数n0和非叶子结点数n {if(bt) {if (bt->lchild==null && bt->rchild==null) *n0++；//叶子结点 else *n++; //非叶结点 Count(bt->lchild,&n0,&n); Count(bt->rchild,&n0,&n); } }//结束 Count 2018年华中科技大学887数据结构与算法分析 复习八套卷 四（ 版） 一．名词解释（25分，1个5分） 1.1算法设计的要求 1.2哈夫曼树 1.3平衡因子 1.4简单图 1.5 AOV网 二．选择题（25分，1个5分） 2.1以下算法中加下划线语句的执行次数为（ ）。 int m=0, i, j; for(i=l;i<=n;i++) for(j=1;j<=2 * i;j++) m++; A. n(n+1) B. n C. n+1 D. n 2 2.2．线性表是具有n个（ ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 2.3无向图G=(V,E), 其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 2.4设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ） A．5 B．6 C．7 D．8 2.5有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 三.简答题（60分） 3.1已知一棵二叉树的先序 中序和后序序列如下，其中空缺了部分，请画出该二叉树。（12分） 先序：_ B C _ E F G _ I J K _ 中序：C B E D _ G A J _ H _ L 后序：_ E _ F D _ J _ L _ H A 3.2一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别（或阶)。 式中，n是问题的规模，为简单起见，设n是2的整数幂。（12分） 3.3请看下边的无向加权图。 （12分） （1）．写出它的邻接矩阵 （2）．按Prim算法求其最小生成树，并给出构造最小生成树过程中辅助数组的各分量值 辅助数组内各分量值： Y Closedge Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost 2 3 4 5 6 7 8 U V.-U 3.4有关键字集合：30,15,21,40,25,26,36,37。若装填因子a=0.8,采用线性探测法处理冲突。试设计一种较为合适的哈希函数，给出生成的哈希表。（12分） 3.5设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。（12分） (1) 用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。 (2) 用直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。 (3) 直接插入排序算法和直接选择排序算法的稳定性如何？ 四 算法设计（40分）（编码困难可以写伪代码，会适当扣分） 4.1试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。（void delete（Linklist &L） 4.2设计算法：求其指定的某一层k(k>1)上的叶子结点的个数。（20分） typedef struct BiTree { int data； struct BiTree *rchild； struct BiTree *lchild； } * BiTree； 20分） 2018年华中科技大学887数据结构与算法分析 复习八套卷 四（ 版）答案 一．名词解释（25分，1个5分） 1.1算法设计的要求 答：正确性、可读性、健壮性、效率与低存储量需求。 1.2哈夫曼树 答：在含有N个带权叶子结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树或最优二叉树。 1.3平衡因子 答：该结点的左子树深度减去它的右子树深度的绝对值。 1.4简单图 答：不存在重复边，不存在定点到自身的边称图G为简单图。与多重图相对 1.5 AOV网 答：用有向无环图表示一个工程，顶点表示活动，有向边 二．选择题（25分，1个5分） 2.1以下算法中加下划线语句的执行次数为（A）。 int m=0, i, j; for(i=l;i<=n;i++) for(j=1;j<=2 * i;j++) m++; A. n(n+1) B. n C. n+1 D. nm++语句的执行次数为 2 2.2．线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 2.3无向图G=(V,E), 其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ D ）。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 2.4设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子 数为（ D ） A．5 B．6 C．7 D．8 2.5有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 三.简答题（60分） 3.1已知一棵二叉树的先序 中序和后序序列如下，其中空缺了部分，请画出该二叉树。（12分） 先序：_ B C _ E F G _ I J K _ 中序：C B E D _ G A J _ H _ L 后序：_ E _ F D _ J _ L _ H A 3.2一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别（或阶)。 式中，n是问题的规模，为简单起见，设n是2的整数幂。（12分） 答：时间复杂度为O(nlog2n)。 设n=2k(k>=0)， 根据题目所给定义，有由此，可得一般递推公式进而，可得即 ，即为 ， ， 。 ， 3.3请看下边的无向加权图。 （12分） （1）．写出它的邻接矩阵 （2）．按Prim算法求其最小生成树，并给出构造最小生成树过程中辅助数组的各分量值 辅助数组内各分量值： Y Closedge Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost 2 3 4 5 6 7 8 U V.-U 3.4有关键字集合：30,15,21,40,25,26,36,37。若装填因子a=0.8,采用线性探测法处理冲突。试设计一种较为合适的哈希函数，给出生成的哈希表。（12分） 哈希函数为H(x)=x%9 3.5设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。（12分） (1) 用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。 (2) 用直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。 (3) 直接插入排序算法和直接选择排序算法的稳定性如何？ (1)直接插入排序 第一趟 (3)[8,3],2,5,9,1,6 第二趟 (2)[8,3,2],5,9,1,6 第三趟 (5)[8,5,3,2],9,1,6 第四趟 (9)[9,8,5,3,2],1,6 第五趟 (1)[9,8,5,3,2,1],6 第六趟 (6)[9,8,6,5,3,2,1] (2)直接选择排序（第六趟后仅剩一个元素，是最小的，直接选择排序结束） 第一趟 (9)[9],3,2,5,8,1,6 第二趟 (8)[9,8],2,5,3,1,6 第三趟 (6)[9,8,6],5,3,1,2 第四趟 (5)[9,8,6,5],3,1,2 第五趟 (3)[9,8,6,5,3],1,2 第六趟 (2)[9,8,6,5,3,2],1 (3)直接插入排序是稳定排序，直接选择排序是不稳定排序。 四 算法设计（40分）（编码困难可以写伪代码，会适当扣分） 4.1试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。（20分） void delete（Linklist &L） [题目分析] 本题要求在单链表中删除最小值结点。单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。 LinkedList Delete（LinkedList L） ∥L是带头结点的单链表，本算法删除其最小值结点。 {p=L->next； ∥p为工作指针。指向待处理的结点。假定链表非空。 pre=L； ∥pre指向最小值结点的前驱。 q=p； ∥q指向最小值结点，初始假定第一元素结点是最小值结点。 while（p->next!=null） {if（p->next->data pre->next=q->next；∥从链表上删除最小值结点 free（q）； ∥释放最小值结点空间 }∥结束算法delete。 4.2设计算法：求其指定的某一层k(k>1)上的叶子结点的个数。 （20分） typedef struct BiTree { int data； struct BiTree *rchild； struct BiTree *lchild； } * BiTree； [题目分析]对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。 int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数 {if(bt==null || k<1) return(0); BiTree p=bt,Q[]; //Q是队列，元素是二叉树结点指针,容量足够大 int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数 int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针，level 是二叉树的层数 while(front<=rear) {p=Q[++front]; if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点 if(p->lchild) Q[++rear]=p->lchild; //左子女入队 if(p->rchild) Q[++rear]=p->rchild; //右子女入队 if(front==last) {level++; //二叉树同层最右结点已处理,层数增1 last=rear; } //last移到指向下层最右一元素 if(level>k) return (leaf); //层数大于k 后退出运行 }//while }//结束LeafKLevel 2018年华中科技大学887数据结构与算法分析 复习八套卷 五（ 版） 一．名词解释（25分，1个5分） 1.1数据元素 1.2栈 1.3关键路径 1.4二叉排序树 1.5二次聚集 二．选择题（25分，1个5分） 2.1某算法的时间复杂度为O(n2)，表明该算法的（ ）。 A.问题规模是n2 B.执行时间等于n2 C.执行时间与n2成正比 D.问题规模与n2成正比 2.2．静态链表中指针表示的是（ ）. A． 内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址 2.3已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}， E={ A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7 2.4设有一表示算术表达式的二叉树（见下图）， / 它所表示的算术表达式是（ ） A. A*B+C/(D*E)+(F-G) + + B. (A*B+C)/(D*E)+(F-G) * - * C C. (A*B+C)/(D*E+（F-G）) A B D E F G D. A*B+C/D*E+F-G 2.5下列排序算法中，其中（ ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 三.简答题（60分） 3.1用一维数组存放的一棵完全二叉树如下图所示：（12分） A B C D E F G H I J K L 写出后序遍历该二叉树时访问结点的顺序 3.2分析以下各程序段，求出算法的时间复杂度。（1个3分 共12分） // 程序段① i=l;k=0; while(i 3.3已知某图的邻接表为 （1）．写出此邻接表对应的邻接矩阵；（2分） （2）．写出由v1开始的深度优先遍历的序列；（2分） （3）．写出由v1开始的深度优先的生成树；（3分） （4）．写出由v1开始的广度优先遍历的序列；（2分） （5）．写出由v1开始的广度优先的生成树；（3分） 234?v1 5?1v2 5?1v3 v416? v523? v64? 3.4使用散列函数hashf(x)=x mod 11,把一个整数值转换成散列表下标，现要把数据：1,13,12,34,38,33,27,22插入到散列表中。 （1）使用线性探查再散列法来构造散列表。（4分） （2）使用链地址法构造散列表。（4分） 针对这两种情况，确定其装填因子，查找成功所需的平均探查次数，以及查找不成功所需的平均探查次数。（4分） 3.5判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。（12分） （1）100，85，98，77，80，60，82，40，20，10，66 （2）100，98，85，82，80，77，66，60，40，20，10 （3）100，85，40，77，80，60，66，98，82，10，20 （4）10，20，40，60，66，77，80， 82，85，98，100 四 算法设计（40分）（编码困难可以写伪代码，会适当扣分） 4.1设有顺序放置的n个荷叶，每个荷叶上有一只青蛙，青蛙的颜色是红,绿,蓝之一。要求重新安排这些青蛙，使得所有红色青蛙在前，所有绿色青蛙居中，所有蓝色青蛙居后，重新安排时对每只青蛙的颜色只能看一次，并且只允许交换操作来调整青蛙的位置。 4.2设计算法：二叉树结点的平衡因子（bf）定义为该结点的左子树高度与右子树高度之差。 树的结构如下图所示 编写递归算法计算二叉树中各个结点的平衡因子。 （20分） typedef struct BiTree { int data； int bf； //平衡因子 struct BiTree *rchild； struct BiTree *lchild； } * BiTree； 2018年华中科技大学887数据结构与算法分析 复习八套卷 五（ 版）答案 一．名词解释（25分，1个5分） 1.1数据元素 答：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 1.2栈 答：限定在表尾进行插入或删除操作的线性表。操作端称为栈顶，后进先出 1.3关键路径 答：在AOE网中，路径长度最长的路径叫做关键路径，关键路径上的所有活动都是 1.4二叉排序树 答：一棵二叉树或是空二叉树或是具有以下性质的二叉树：左子树上所有关键字均小于根结点的关键字，右子树所有结点关键字大于根结点的关键字。左子树和右子树又各是一棵二叉排序树。 1.5二次聚集 答：指在处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后继哈希地址的现象。 二．选择题（25分，1个5分） 2.1某算法的时间复杂度为O(n2)，表明该算法的（ C ）。 A.问题规模是n2 B.执行时间等于n2 C.执行时间与n2成正比 D.问题规模与n2成正比 2.2．静态链表中指针表示的是（ C ）. A． 内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址 2.3已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}， E={ A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7 2.4设有一表示算术表达式的二叉树（见下图）， / 它所表示的算术表达式是（ C ） A. A*B+C/(D*E)+(F-G) + + B. (A*B+C)/(D*E)+(F-G) * C - * C. (A*B+C)/(D*E+（F-G）) A B D E F G D. A*B+C/D*E+F-G 2.5下列排序算法中，其中（ D ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 三.简答题（60分） 3.1用一维数组存放的一棵完全二叉树如下图所示：（12分） A B C D E F G H I J K L 写出后序遍历该二叉树时访问结点的顺序 答：HIDJKEBLFGCA 3.2分析以下各程序段，求出算法的时间复杂度。（1个3分 共12分） // 程序段① i=l;k=0; while(i ①基本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n)。 ②设循环体共执行T(n)次，每循环一次，循环变量y加1,最终T(n)=y。故(T(n))2<=n，解得 T(n)=O(n1/2)。 ③ x++是基本语句，。 ④a[i][j]=0是基本语句，内循环执行m次，外循环执行n次，共执行了 m*n次，所以 T(m, n)=O(m*n) 3.3已知某图的邻接表为 （1）．写出此邻接表对应的邻接矩阵；（2分） （2）．写出由v1开始的深度优先遍历的序列；（2分） （3）．写出由v1开始的深度优先的生成树；（3分） （4）．写出由v1开始的广度优先遍历的序列；（2分） （5）．写出由v1开始的广度优先的生成树；（3分） 234?v1 5?1 v25?1 v3v4v5v6124?63??（1）略 （2）V1V2V5V3V4V6 (3) V4 V6 V1 V2 V5 V3 (4) V1V2V3V4V5V6 (5) V1 V2 V3 V4 V6 V5 3.4使用散列函数hashf(x)=x mod 11,把一个整数值转换成散列表下标，现要把数据：1,13,12,34,38,33,27,22插入到散列表中。 （1）使用线性探查再散列法来构造散列表。（4分） （2）使用链地址法构造散列表。（4分） 针对这两种情况，确定其装填因子，查找成功所需的平均探查次数，以及查找不成功所需的平均探查次数。（4分） 由hashf(x)=x mod 11 可知，散列地址空间是0到10，由于有8个数据，装载因子取0.7。 （1） 散列地址 0 关键字 33 比较次数 1 1 1 1 2 13 1 3 12 3 4 34 4 5 38 1 6 27 2 7 22 8 8 9 10 ASLsucc=21/8 ASLunsucc=47/11 （2） ASLsucc=13/8 ASLunsucc=19/11 值得指出，对用拉链法求查找失败时的平均查找长度有两种观点。其一，认为比较到空指针算失败。以本题为例，哈希地址0、2、5、7、9和10均为比较1次失败，而哈希地址1和3比较2次失败，其余哈希地址均为比较3次失败，因此，查找失败时的平均查找长度为19/11，我们持这种观点。还有另一种理解，他们认为只有和关键字比较才计算比较次数，而和空指针比较不计算。照这种观点，本题的ASLunsucc=（1+1+2+2+2）/11=8/11 3.5判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。（12分） （1）100，85，98，77，80，60，82，40，20，10，66 （2）100，98，85，82，80，77，66，60，40，20，10 （3）100，85，40，77，80，60，66，98，82，10，20 （4）10，20，40，60，66，77，80， 82，85，98，100 答：(1)是大堆； (2)是大堆； (3)不是堆，调成大堆 100，98，66，85，80，60，40，77，82，10，20 （4）是小堆； 四 算法设计（40分）（编码困难可以写伪代码，会适当扣分） 4.1设有顺序放置的n个荷叶，每个荷叶上有一只青蛙，青蛙的颜色是红,绿,蓝之一。要求重新安排这些青蛙，使得所有红色青蛙在前，所有绿色青蛙居中，所有蓝色青蛙居后，重新安排时对每只青蛙的颜色只能看一次，并且只允许交换操作来调整青蛙的位置。 [题目分析]利用快速排序思想解决。由于要求“对每只青蛙的颜色只能看一次”，设3个指针i，j和k，分别指向红色、绿色青蛙的后一位置和待处理的当前元素。从k=n开始，从右向左搜索，若该元素是蓝色，则元素不动，指针左移（即k-1）；若当前元素是红色青蛙，分i>=j（这时尚没有绿色青蛙）和i 对当前元素是绿色青蛙的情况，也可类似处理。 为方便处理，将三种青蛙的颜色用整数1、2和3表示。 void QkSort(rectype r[],int n) // r为含有n个元素的线性表，元素是具有红、绿和蓝色的青蛙，用顺序存储结构存储， //本算法对其排序，使所有红色青蛙在前，绿色居中，蓝色在最后。 {int i=1,j=1,k=n,temp; while (k!=j) {while (r[k].key==3) k--;// 当前元素是蓝色青蛙，指针左移 if (r[k].key==1) // 当前元素是红色青蛙 if (i>=j){temp=r[k];r[k]=r[i];r[i]=temp; i++;} //左侧只有红色青蛙，交换r[k]和r[i] else {temp=r[j];r[j]=r[i];r[i]=temp; j++; //左侧已有红色和绿色青蛙，先交换绿色青蛙到位 temp=r[k];r[k]=r[i];r[i]=temp; i++; //绿色青蛙（i所指）和待定青蛙（j所指） } //再交换r[k]和r[i]，使红色青蛙入位。 if (r[k].key==2) if (i<=j) { temp=r[k];r[k]=r[j];r[j]=temp; j++;} // 左侧已有绿色青蛙，交换r[k]和r[j] else { temp=r[k];r[k]=r[i];r[i]=temp; j=i+1;} //i、j分别指向红、绿色青蛙的后一位置 }//while if (r[k]==2) j++; /* 处理最后一只青蛙 else if (r[k]==1) { temp=r[j];r[j]=r[i];r[i]=temp; i++; j++; } //最后红、绿、蓝色青蛙的个数分别为: i-1;j-i;n-j+1 }//结束QkSor算法 4.2设计算法：二叉树结点的平衡因子（bf）定义为该结点的左子树高度与右子树高度之差。 树的结构如下图所示 编写递归算法计算二叉树中各个结点的平衡因子。 （20分） typedef struct BiTree { int data； int bf； //平衡因子 struct BiTree *rchild； struct BiTree *lchild； } * BiTree； [题目分析] 由定义，结点的平衡因子bf等于结点的左子树高度与右子树高度之差，设计一遍历算法，在遍历结点时，求结点的左子树和右子树的高度，然后得到结点的平衡因子。 int Height(BiTree bt)//求二叉树bt的深度 {int hl,hr; if (bt==null) return(0); else {hl=Height(bt->lchild); hr=Height(bt->rchild); if(hl>hr) return (hl+1); else return(hr+1); } }// Height void Balance(BiTree bt) //计算二叉树bt各结点的平衡因子 {if (bt) {Balance(bt->lchild); //后序遍历左子树 Balance(bt->rchild); //后序遍历右子树 hl=Height(bt->lchild); hr=Height(bt->rchild);//求左右子树的高度 bt->bf=hl-hr; //结点的平衡因子bf } }//算法结束 2018年华中科技大学887数据结构与算法分析 复习八套卷 六（ 版） 一．名词解释（25分，1个5分） 1.1算法 1.2连通图 1.3森林 1.4堆排序 1.5静态查找表 二．选择题（25分，1个5分） 2.1 for(i=n-l;i>l;i--) for(j=1;j A[j]与 A[j+1]对换; 其中n为正整数，则最后一行的语句频度在最坏情况下是（ ）。 A. O(n) B. O(nlogn) C. O(n的3次方) D. O(n的2次方) 2.2．下面关于二分查找的叙述正确的是 ( ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序，而且只能从小到大排列 C. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储 2.3下列说法不正确的是（ ）。 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程 2.4在下述结论中，正确的是（ ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④ 2.5对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 ( )。 A. 选择 B. 冒泡 C. 快速 D. 插入 三.简答题（60分） 3.1设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若 T中有6个叶结点，试问：（12分） （1）T树的最大深度Kmax=?最小可能深度Kmin=? （2）T树中共有多少非叶结点？ (3) 若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。 3.2一个人带着青蛙去每个村庄卖，每经过一个村子卖去青蛙的一半又一只。这样他经 过了七个村子后还剩两只青蛙，问他出发时共赶多少只青蛙？经过每个村子卖出多少只青蛙？（12分）（用程序解答） 3.3对图示的AOE网络，计算各活动弧的e(ai)和l(ai)的函数值，各事件（顶点）的ve（Vj）和vl (Vj)的函数值，列出各条关键路径。（12分） A1B?6534C 11106F916H1221 17W72E8G13D 3.4对下面的关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8，采用线性探 测再散列方法解决冲突：（12分） （1）设计哈希函数； （2）画出哈希表； （3）计算查找成功和查找失败的平均查找长度； 3.5（1） 判定起泡排序的结束条件是什么？ （2） 请简单叙述希尔排序的基本思想。 （3） 将下列序列调整成堆（堆顶为最小值） 1 2 3 4 5 6 7 8 9 10 112 70 33 65 24 56 48 92 80 13 （4）在16个关键字中选出最小的关键字至少要多少次比较？再选出次小的关键字至少要多少次比较？请简要说明选择的方法和过程。 （12分） 四 算法设计（40分）（编码困难可以写伪代码，会适当扣分） 4.1编写一个算法来交换单链表中指针P所指结点与其后继结点，HEAD是该链表的头指针，P指向该链表中某一结点。（20分） 4.2设计算法： p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（root，p,q,r）,该算法找到p和q的最近共同祖先结点r。（20分） typedef struct BiTree { int data； struct BiTree *rchild； struct BiTree *lchild； } * BiTree； 2018年华中科技大学887数据结构与算法分析 复习八套卷 六（ 版）答案 一．名词解释（25分，1个5分） 1.1算法 答：对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。有5个重要特性（有穷性、确定性、可行性、输入、输出） 1.2连通图 答：若从顶点v到顶点w存在路径，则v和w是联通的。若图G中任意两个顶点都是联通的，则称图G为连通图 1.3森林 答：m（m>=0）棵互不相交的树的集合。 1.4堆排序 答：一种树形选择排序方法。在排序过程中把L[1...N]堪称一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲和孩子之间的关系，在当前无序区选择最大或最小的元素。 1.5静态查找表 答：如果一个查找表的操作仅涉及查询某个特定的数据元素是否在查找表中和检索满足条件的某个特定的数据元素的各种属性，则称为静态查找表。 二．选择题（25分，1个5分） 2.1 for(i=n-l;i>l;i--) for(j=1;j A[j]与 A[j+1]对换; 其中n为正整数，则最后一行的语句频度在最坏情况下是（D ）。 A. O(n) B. O(nlogn) C. O(n的3次方) D. O(n的2次方) 当所有相邻元素都为逆序时，则最后一行的语句每次都会执行。此时， 所以在最坏情况下的该语句频度是O(n2)。 2.2．下面关于二分查找的叙述正确的是 ( D ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序，而且只能从小到大排列 C. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储 2.3下列说法不正确的是（ C ）。 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程 2.4在下述结论中，正确的是（ D ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④ 2.5对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 ( A )。 A. 选择 B. 冒泡 C. 快速 D. 插入 三.简答题（60分） 3.1设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若 T中有6个叶结点，试问： （1）T树的最大深度Kmax=?最小可能深度Kmin=? （2）T树中共有多少非叶结点？ (3) 若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。 答：（1）T树的最大深度Kmax=6（除根外，每层均是两个结点） T树的最小深度Kmin=4（具有6个叶子的完全二叉树是其中的一种形态） （2）非叶子结点数是5。（n2=n0-1） （3）哈夫曼树见下图，其带权路径长度wpl=51 6 3 1 2 4 5 3.2一个人带着青蛙去每个村庄卖，每经过一个村子卖去青蛙的一半又一只。这样他经 过了七个村子后还剩两只青蛙，问他出发时共赶多少只青蛙？经过每个村子卖出多少只青蛙？（12分）（用程序解答） qingwa(int begin,int times) { if(times==7) return begin; return qingwa ((begin+1)*2,times+1); } 3.3对图示的AOE网络，计算各活动弧的e(ai)和l(ai)的函数值，各事件（顶点）的ve（Vj）和vl (Vj)的函数值，列出各条关键路径。（12分） A1B?6534C 11106F916H1221 17W72E8G13D B 6 C 3 D 4 7 E F G H W 24 13 39 22 52 31 13 39 22 52 a11 a12 a13 a14 a15 a16 a17 顶点 Ve(i) Vl(i) 活动 e(i) l(i) α A 0 0 1 29 24 3 aaaaaaaaaa11 2 3 4 5 6 7 8 9 0 0 0 0 0 1 6 6 3 3 4 210 3 22333 7 8 8 9 4 1 4 24 13 13 13 39 22 22 31 20 36 13 39 22 40 关键路径是： C F H G W ，长52。 ? 活动与顶点的对照表：a1<α,A> a2<α,B> a3<α,C> a4<α,D> a6 a8 a9 3.4对下面的关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8，采用线性探 测再散列方法解决冲突：（12分） （1）设计哈希函数； （2）画出哈希表； （3）计算查找成功和查找失败的平均查找长度； 答：由于装填因子为0.8，关键字有8个，所以表长为8/0.8=10。 （1）用除留余数法，哈希函数为H（key）=key % 7 （2） 散列地址 0 关键字 21 比较次数 1 1 15 1 2 30 1 3 36 3 4 25 1 5 40 1 6 26 2 7 37 6 8 9 （3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i（0≤i≤m-1）时的查找次数。本例中m=10。故查找失败时的平均查找长度为： ASLunsucc=（9+8+7+6+5+4+3+2+1+1）/10=4.6 ASLsucc =16/8=2 3.5（1） 判定起泡排序的结束条件是什么？ （2） 请简单叙述希尔排序的基本思想。 （3） 将下列序列调整成堆（堆顶为最小值） 1 2 3 4 5 6 7 8 9 10 112 70 33 65 24 56 48 92 80 13 （4）在16个关键字中选出最小的关键字至少要多少次比较？再选出次小的关键字至少要多少次比较？请简要说明选择的方法和过程。 （12分） 答：(1)当至多进行n-1趟起泡排序，或一趟起泡排序中未发生交换（即已有序）时，结束排序。 (2)希尔排序是对直接插入排序算法的改进，它从“记录个数少”和“基本有序”出发，将待排序的记录划分成几组（缩小增量分组），从而减少参与直接插入排序的数据量，当经过几次分组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序。 (3)13，24，33，65，70，56，48，92，80，112 (4)采用树型锦标赛排序选出最小关键字至少要15次比较。再选出次小关键字比较4次。（两两比较8次选出8个优胜，再两两比较4次选出4个优胜，半决赛两场，决赛一场，共比较了15次。将冠军的叶子结点改为最大值，均与兄弟比较，共4次选出亚军。） 四 算法设计（40分）（编码困难可以写伪代码，会适当扣分） 4.1编写一个算法来交换单链表中指针P所指结点与其后继结点，HEAD是该链表的头指针，P指向该链表中某一结点。（20分） [题目分析] 单链表中查找任何结点，都必须从头指针开始。本题要求将指针p所指结点与其后继结点交换，这不仅要求知道p结点，还应知道p的前驱结点。这样才能在p与其后继结点交换后，由原p结点的前驱来指向原p结点的后继结点。 另外，若无特别说明，为了处理的方便统一，单链表均设头结点，链表的指针就是头结点的指针。并且由于链表指针具有标记链表的作用，也常用指针名冠以链表名称。如“链表head”既指的是链表的名字是head，也指出链表的头指针是head。 LinkedList Exchange（LinkedList HEAD，p） ∥HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 {q=head->next； ∥q是工作指针，指向链表中当前待处理结点。 pre=head； ∥pre是前驱结点指针，指向q的前驱。 while（q!=null && q!=p）{pre=q；q=q->next；} ∥未找到p结点，后移指针。 if（p->next==null）printf（“p无后继结点\\n”）; ∥p是链表中最后一个结点，无后继。 else∥处理p和后继结点交换 {q=p->next； ∥暂存p的后继。 pre->next=q； ∥p前驱结点的后继指向p的后继。 p->next=q->next；∥p的后继指向原p后继的后继。 q->next=p ；∥原p后继的后继指针指向p。 } }∥算法结束。 4.2设计算法： p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（root，p,q,r）,该算法找到p和q的最近共同祖先结点r。（20分） typedef struct BiTree { int data； struct BiTree *rchild； struct BiTree *lchild； } * BiTree； [题目分析]后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。 typedef struct {BiTree t;int tag;//tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问 }stack; stack s[],s1[];//栈，容量够大 BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉树上结点p和q的最近的共同祖先结点r。 {top=0; bt=ROOT; while(bt!=null ||top>0) {while(bt!=null && bt!=p && bt!=q) //结点入栈 {s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下 if(bt==p) //不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点 {for(i=1;i<=top;i++) s1[i]=s[i]; top1=top; }//将栈s的元素转入辅助栈s1 保存 if(bt==q) //找到q 结点。 for(i=top;i>0;i--)//；将栈中元素的树结点到s1去匹配 {pp=s[i].t; for (j=top1;j>0;j--) if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”)；return (pp);} ｝ while(top!=0 && s[top].tag==1) top--; //退栈 if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ //沿右分枝向下遍历 }//结束while(bt!=null ||top>0) return(null);//ｑ、p无公共祖先 ｝//结束Ancestor 2018年华中科技大学887数据结构与算法分析 复习八套卷 七（ 版） 一．名词解释（25分，1个5分） 1.1数据的逻辑结构 1.2结点的层次 1.3最短路径 1.4希尔排序 1.5折半查找 二．选择题（25分，1个5分） 2.1设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。 x=2; while(x A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2) 2.2．以下数据结构中，（ ）是非线性数据结构 A．树 B．字符串 C．队 D．栈 2.3由3 个结点可以构造出多少种不同的二叉树？（ ） A．2 B．3 C．4 D．5 2.4设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) A．8 B．3 C．5 D．9 2.5用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（ ）。 A． 94,32,40,90,80,46,21,69 B． 32,40,21,46,69,94,90,80 C． 21,32,46,40,80,69,90,94 D． 90,69,80,46,21,32,94,40 三.简答题（60分） 3.1试找出满足下列条件的二叉树。（12分） 1）先序序列与后序序列相同 2）中序序列与后序序列相同 3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同 3.2 某算法的计算时间为：T(n) = 4T(n/2) + O(n)，其中T(1) = O(1)，求其时间复杂度，写出具体过程（12分） 3.3已知无向图如下所示：（12分） （1）．给出从V1开始的广度优先搜索序列； （2）．画出它的邻接表； （3）．画出从V1开始深度优先搜索生成树。 3.4采用哈希函数Ｈ（k）=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51。（12分） （1）构造哈希表（画示意图）； （2）装填因子； （3）成功的平均查找长度。 （4）不成功的平均查找长度。 3.5已知待排序的序列为（503，87，512，61，908，170，897，275，653，462），试完成下列各题。(12分) (1) 根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。 (2) 输出最小值后，如何得到次小值。（并画出相应结果图） 四 算法设计（40分）（编码困难可以写伪代码，会适当扣分） 4.1借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。请编写出算法并简要说明算法思想。（20分） 4.2设计非递归算法求树的深度。（20分） typedef struct BiTree { int data； struct BiTree *rchild； struct BiTree *lchild； } * BiTree； 2018年华中科技大学887数据结构与算法分析 复习八套卷 七（ 版）答案 一．名词解释（25分，1个5分） 1.1数据的逻辑结构 答：指数据元素之间的逻辑关系。包括集合、线性结构、树形结构、图状结构或网状结构。 1.2结点的层次 答：从树根开始定义，根结点为第1层，它的子结点为第2层，以此类推。 1.3最短路径 答：带权图中，从一个顶点V0到另一个顶点V1的一条路径上所经过边的权值之和定义为该路径的带权路径长度，其中最短的那条称作最短路径。此路径的长度称为从v到u的距离。 1.4希尔排序 答：又称缩小增量排序，先将整个记录序列分割成若干子序列分别进行直接插入排序，待整个序列中记录基本有序时，再对全体进行一次直接插入排序。 1.5折半查找 答：仅适用于有序的顺序表。将给定的值key与表中间位置元素的关键字比较，相等则查找成功返回位置。若不等则缩小查找范围，重复查找直到找到或者确定表中没有需查找的元素。 二．选择题（25分，1个5分） 2.1设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（A）。 x=2; while(x A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2) 在程序中，执行频率最高的语句为“x=2*x+1语句共执行了 t次，则2t+1=n/2，故t=log2(n/2)-1=log2n-2，得 T(n)=O(log2n)。 2.2．以下数据结构中，（ A ）是非线性数据结构 A．树 B．字符串 C．队 D．栈 2.3由3 个结点可以构造出多少种不同的二叉树？（ D ） A．2 B．3 C．4 D．5 2.4设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( D ) A．8 B．3 C．5 D．9 2.5用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（ C ）。 A． 94,32,40,90,80,46,21,69 B． 32,40,21,46,69,94,90,80 C． 21,32,46,40,80,69,90,94 D． 90,69,80,46,21,32,94,40 三.简答题（60分） 3.1试找出满足下列条件的二叉树。（12分） 1）先序序列与后序序列相同 2）中序序列与后序序列相同 3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同 （１） 若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树 （２） 若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树． （３） 若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树． （４） 若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二 叉树 3.2 某算法的计算时间为：T(n) = 4T(n/2) + O(n)，其中T(1) = O(1)，求其时间复杂度，写出具体过程（12分） 迭代两次可将右端展开为： 设T(n) = 4T(n/2) + n，则a = 4，b = 2，f(n) = n， 代入得T(n) = O(n的平方 )。 3.3已知无向图如下所示：（12分） （1）．给出从V1开始的广度优先搜索序列； （2）．画出它的邻接表； （3）．画出从V1开始深度优先搜索生成树。 设邻接表（略）中顶点的邻接点按顶点编号升序排列（V1编号为1） （2） 广度优先搜索序列：V1V2V3V4V5V6V7V8 （3） 深度优先搜索序列：V1V2V4V8V5V3V6V7 3.4采用哈希函数Ｈ（k）=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51。（12分） （1）构造哈希表（画示意图）； （2）装填因子； （3）成功的平均查找长度。 （4）不成功的平均查找长度。 （1） 散列地址 0 关键字 13 比较次数 1 3.5已知待排序的序列为（503，87，512，61，908，170，897，275，653，462），试完成下列各题。(12分) (1) 根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。 (2) 输出最小值后，如何得到次小值。（并画出相应结果图） (1)建小堆 61 503 87 170 87 512 275 462 512 897 61 908 170 897 275 653 462 (2) 求次小值 908 87 170 275 462 5122 897 503 653 61 503 653 908 1 22 1 2 3 4 1 2 5 6 7 67 2 8 46 1 9 10 11 12 30 1 53 1 41 1 51 1 （2）装填因子=9/13=0.7 （3）ASLsucc =11/9 （4）ASLunsucc =29/13 87 275 503 908 653 61 462 512 170 897 四 算法设计（40分）（编码困难可以写伪代码，会适当扣分） 4.1借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。请编写出算法并简要说明算法思想。（20分） [题目分析]把待查记录看作枢轴，先由后向前依次比较，若小于枢轴，则从前向后，直到查找成功返回其位置或失败返回0为止。 int index (RecType R[],int l,h,datatype key) { int i=l,j=h; while (i { while (i<=j && R[j].key>key) j--; if (R[j].key==key) return j; while (i<=j && R[i].key printf(“Not find”) ; return 0; }//index 4.2设计非递归算法求树的深度。（20分） typedef struct BiTree { int data； struct BiTree *rchild； struct BiTree *lchild； } * BiTree； [题目分析]由孩子兄弟链表表示的树，求高度的递归模型是：若树为空，高度为零；若第一子女为空，高度为1和兄弟子树的高度的大者；否则，高度为第一子女树高度加1和兄弟子树高度的大者。其非递归算法使用队列，逐层遍历树，取得树的高度。 int height(CSTree t) //非递归遍历求以孩子兄弟链表表示的树的深度 {if(t==null) return(0); else{int front=1,rear=1; //front,rear是队头队尾元素的指针 int last=1,h=0; //last指向树中同层结点中最后一个结点，h是树的高度 Q[rear]=t; //Q是以树中结点为元素的队列 while(front<=last) {t=Q[front++]; //队头出列 while(t!=null) //层次遍历 {if (t->firstchild) Q[++rear]=t->firstchild; //第一子女入队 t=t->nextsibling; //同层兄弟指针后移 } if(front>last) //本层结束，深度加1（初始深度为0） {h++;last=rear;} //last再移到指向当前层最右一个结点 }//while(front<=last) }//else }//Height 2018年华中科技大学887数据结构与算法分析 复习八套卷 八（ 版） 一．名词解释（25分，1个5分） 1.1数据的存储结构 1.2串 1.3冲突 1.4快速排序 1.5广度优先搜索 二．选择题（25分，1个5分） 2.1 int frog｛ if(n==0) return 1; else return （n+frog（n-1）/2）; ｝ 上述算法时间复杂度是多少（ ） A. logn B.n C. nlogn D. (n)`2 2.2．连续存储设计时，存储单元的地址（ ）。 A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 2.3一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（ ） A．A[2i](2i<=n) B．A[2i+1](2i+1<=n) C．A[i-2] D．条件不充分，无法确定 2.4在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。 A. LL B. LR C. RL D. RR 2.5对下列关键字序列用快速排序法进行排序时，速度最快的情形是（ ）。 A． {21,25,5,17,9,23,30} B．{25,23,30,17,21,5,9} C． {21,9,17,30,25,23,5} Ｄ．{5,9,17,21,23,25,30} 三.简答题（60分） 3.1已知一棵二叉树的后序遍历序列为EICBGAHDF，同时知道该二叉树的中序遍历序列为CEIFGBADH，试画出该二叉树。 3.2对于求N!。 这是一个简单的\累乘\问题，用递归算法也能解决。 因此，递归算法如下： fact(intn) { if(n== 0 || n == 1) return1; else return n * fact(n – 1); } 求其时间复杂度，写出具体过程。（12分） 3.3设G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。 12分）设从顶点1开始遍历。（12分） 234?1 5?1342 124?3 1235?4 24?5 3.4设哈希表a 、b分别用向量a[0..9],b[0..9]表示 ，哈希函数均为H（key）=key MOD 7,处理冲突使用开放定址法，Hi=[H(key)+Di]MOD 10,在哈希表a中Di用线性探测再散列法，在哈希表b中Di用二次探测再散列法,试将关键字{19,24, 10,17,15,38,18,40}分别填入哈希表a,b中,并分别计算出它们的平均查找长度ASL。（12分） 3.5给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程： (12分) (1) 归并排序 每归并一次书写一个次序。 (2) 快速排序 每划分一次书写一个次序。 四 算法设计（40分）（编码困难可以写伪代码，会适当扣分） 4.1设有一个带头结点的单向链表，数据项递减有序。写一算法，重新排列链表，使数据项递增有序，要求算法时间复杂度为O（n）。（20分） 4.2设计一个算法将二叉树中所有结点的左，右子树相互交换。（20分） typedef struct BiTree { int data； struct BiTree *rchild； struct BiTree *lchild； } * BiTree； 2018年华中科技大学887数据结构与算法分析 复习八套卷 八（ 版）答案 一．名词解释（25分，1个5分） 1.1数据的存储结构 答：指数据结构在计算机中的表示，也成物理结构。主要有顺序存储、连接存储、索引存储、散列存储。 1.2串 答：由零个或者多个字符组成的有限序列。串中任意个连续的字符组成的子序列称为该串的子串。字符在序列中的序号为该字符的位置。 1.3冲突 答：散列函数可能会把两个或以上的不同关键字映射到同一地址，这种情况为冲突 1.4快速排序 答：通过一趟排序将带排记录分割成独立两部分，其中一部分的关键字均比另一部分小，分别对两部分再进行快速排序直至整个序列有序 1.5广度优先搜索 答：类似于树的层次遍历，从顶点v出发，访问了V之后依次访问v的各个未被访问过的邻接顶点。再依次访问它们的邻接点，并使先被访问的顶点的的邻接点先于后访问的顶点的邻接点。直到图中所有已被访问顶点的邻接点都被访问到。如果图中还有顶点未被访问，则另选一个未被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问。 二．选择题（25分，1个5分） 2.1 int frog｛ if(n==0) return 1; else return （n+frog（n-1）/2）; ｝ 上述算法时间复杂度是多少（B） A. logn B.n C. nlogn D. (n)`2 2.2．连续存储设计时，存储单元的地址（ A ）。 A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 2.3一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（ D ） A．A[2i](2i<=n) B．A[2i+1](2i+1<=n) C．A[i-2] D．条件不充分，无法确定 2.4在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( C ) 型调整以使其平衡。 A. LL B. LR C. RL D. RR 2.5对下列关键字序列用快速排序法进行排序时，速度最快的情形是（ A ）。 A． {21,25,5,17,9,23,30} B．{25,23,30,17,21,5,9} C． {21,9,17,30,25,23,5} Ｄ．{5,9,17,21,23,25,30} 三.简答题（60分） 3.1已知一棵二叉树的后序遍历序列为EICBGAHDF，同时知道该二叉树的中序遍历序列为CEIFGBADH，试画出该二叉树。 F C D H A I G E B 3.2求N!。 这是一个简单的\累乘\问题，用递归算法也能解决。 因此，递归算法如下： fact(intn) { if(n== 0 || n == 1) return1; else return n * fact(n – 1); } 求其时间复杂度，写出具体过程。（12分） 算法的递归方程为： T(n) = T(n - 1) + O(1); 迭代展开： T(n) = T(n - 1) + O(1) = T(n - 2) + O(1) + O(1) = T(n - 3) + O(1) + O(1)+ O(1) = ...... = O(1) + ... + O(1) +O(1) + O(1) = n * O(1) = O(n) 3.3设G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。 12分）设从顶点1开始遍历。（12分） 234?1 5?1342 345112224?4?35?深度优先生成树 1 2 3 4 5 广度优先生成树 1 2 3 4 5 3.4设哈希表a 、b分别用向量a[0..9],b[0..9]表示 ，哈希函数均为H（key）=key MOD 7,处理冲突使用开放定址法，Hi=[H(key)+Di]MOD 10,在哈希表a中Di用线性探测再散列法，在哈希表b中Di用二次探测再散列法,试将关键字{19,24, 10,17,15,38,18,40}分别填入哈希表a,b中,并分别计算出它们的平均查找长度ASL。（12分） 散列地址 0 1 2 3 4 5 6 7 8 9 关键字 15 24 10 19 17 38 18 40 比较次数 1 1 2 1 4 5 5 5 哈希表a: ASLsucc=24/8=3； 散列地址 0 1 2 3 4 5 6 7 8 9 关键字 15 17 24 10 19 40 38 18 比较次数 1 3 1 2 1 2 4 4 哈希表b: ASLsucc =18/8 3.5给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程： (12分) (1) 归并排序 每归并一次书写一个次序。 (2) 快速排序 每划分一次书写一个次序。 (1)2路归并 第一趟:18,29,25,47,12,58,10,51； 第二趟:18,25,29,47,10,12,51,58； 第三趟:10,12,18,25,29,47,51,58 (2)快速排序 第一趟:10,18,25,12,29,58,51,47； 第二趟:10,18,25,12,29,47,51,88； 第三趟:10,12,18,25,29,47,51,88 四 算法设计（40分）（编码困难可以写伪代码，会适当扣分） 4.1设有一个带头结点的单向链表，数据项递减有序。写一算法，重新排列链表，使数据项递增有序，要求算法时间复杂度为O（n）。（20分） 本题要求将数据项递减有序的单链表重新排序，使数据项递增有序，要求算法复杂度为O（n）。虽没说要求将链表逆置，这只是叙述不同，本质上是将单链表逆置，现编写如下：LinkedList invert2（LinkedList la） ∥la是带头结点且数据项递减有序的单链表，本算法将其排列成数据项递增有序的单链表。 {p=la->next； /*p为工作指针*/ la->next=null； while（p!=null） {r=p->next； /*暂存p的后继。*/ p->next=la->next；/*将p结点前插入头结点后。*/ la->next=p；p=r； } }∥结束算法 4.2设计一个算法将二叉树中所有结点的左，右子树相互交换。（20分） typedef struct BiTree { int data； struct BiTree *rchild； struct BiTree *lchild； } * BiTree； void exchange(BiTree bt)//将二叉树bt所有结点的左右子树交换 {if(bt){BiTree s； s=bt->lchild; bt->lchild=bt->rchild; bt->rchild=s; //左右子女交换 exchange(bt->lchild); //交换左子树上所有结点的左右子树 exchange(bt->rchild); //交换右子树上所有结点的左右子树 } } 2018年华中科技大学887数据结构与算法分析 最后四套卷 一（ 版） 一．名词解释（25分，1个5分） 1.1算法的确切性 1.2队列假上溢 1.3监视哨 1.4循环链表 1.5强连通图 二．选择题（25分，1个5分） 2.1 Void qingwa(int n) ｛ if(n!=0) { qingwa(n/2) printf(“gua”); qingwa(n/2) } ｝ 上述算法时间复杂度是多少（） A. n B.nlogn C. logn D. (logn)`2 2.2两个共享栈共享数组S[0...n-1],其中一个栈的栈顶指针的top1的初始值是-1，第二个栈的栈顶指针的top2的初始值是n，则判断该共享栈栈满的条件是（） A. top2+2==tot1 B. top1+1==tot2 C. top1+2==tot2 D. top2+1==tot1 2.3构造哈夫曼树依据的基本思路是 A. 回溯算法 B. 贪心算法 C. 分治算法 D. 递归算法 2.4对于关键字序列（16，10，20，12，18，7，14，13，5，19），不可能构成其二叉排序数中的一条查找路径的序列是（） A. 16，10，7，5 B.16，20，18，19 C. 16，10，7，12，14 D. 16，10，12，14 2.5下列各种算法空间性能最好的是（） A. 快速排序 B.堆排序 C. 归并排序 D. 基数排序 三．简答题（60分） 3.1一颗二叉树的先序，中序，后序如下所示，填空，并画出该树。（10分） 先序序列： _ B _ F _ I C E H _ G 中序序列： D _ K F I A_ E J C _ 后序序列： _ K _F B H J _ G _ A 3.2一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。 求该青蛙跳上一个n 级的台阶总共有多少种跳法。（12分） 3.3已知连通图G有6个顶点，顶点之间的邻接关系如下所示。 1 2 3 4 5 6 1 0 1 0 1 1 0 2 1 0 1 1 0 0 3 0 1 0 0 0 1 4 1 1 0 0 1 1 5 1 0 0 1 0 1 6 0 0 1 1 1 0 （1）按照深度优先和广度优先算法写出出结点1开始的深度优先遍历序列与广度优先遍历序列。（6分） （2）分别画出以1为根的深度生成树与广度生成树。（6分） 3.4给定关键字序列（69，8，58，16，25，45，29，40，18，8*，36），回答下列问题。注意，其中有两个字关键字的值均为8，为了加以区别，分别标志为8和8*。 （1）希尔排序是对直接插入排序算法的改进，根据增量取值来划分不同的子序列，在子序列内部按照直接插入排序的思想完成排序。增量依次递减，最终完成整个序列的排序。请分别给出三趟希尔排序的结果，设定增量序列依次为5，3，1。（6分） （2）分析希尔排序利用了直接插入排序的什么特点进行改进以提高排序效率。（4分） （3）分析希尔排序算法的稳定性，给出实例说明。（4分） 3.5假设哈希表的地址范围是0-10，哈希函数为：H(K)=K MOD11 K为关键字，用线性表探测再散列法处理冲突，输入关键字序列｛10，32，17，31，30，36，37，44，63｝ 回答下列问题： （1）画出构造的哈希表。（6分） （2）计算成功查找长度以及失败查找长度。（6分） 四．算法设计（40分）（编码困难可以写伪代码，会适当扣分） 4.1小蝌蚪找妈妈。一个长度为N的数组里面只有2个相同的数，求出这个数，要求时间复杂度为O(N)。 （20分） 例如： 2 3 4 5 6 7 4 输出4 4.2 判断一颗树是否为完全二叉树。（20分） 2018年华中科技大学887数据结构与算法分析 最后四套卷 二（ 版） 一．名词解释（25分，1个5分） 1.1健壮性 1.2线性存储结构 1.3模式匹配 1.4连通分量 1.5拓扑排序 二．选择题（25分，1个5分） 2.1 Void qingwa(int n) ｛ if(n!=0) { qingwa(n-1) printf(“gua”); qingwa(n-1) } ｝ 上述算法时间复杂度是多少（） A. 2`n B.n`2 C. logn D. (logn)`2 2.2线索二叉树是一种（）结构 A. 逻辑 B. 逻辑和存储 C. 物理 D. 线性 2.3下列说法正确的是（） （1）任何一颗二叉树的叶子结点在三种遍历中的相对次序不变。 （2）按二叉树的定义，具有三个结点的二叉树共有6种。 A. （1） （2） B. （2） C. （1） D. （1） （2）都错 2.4无向图G=(V,E)，其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)} 对该图进行深度优先遍历，得到的顶点序列正确的是（） A. a,b,e,c,d,f B.a,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b 2.5快速排序的基本思路是（） A. 回溯算法 B. 贪心算法 C. 分治算法 D. 变治算法 三．简答题（60分） 3.1写出算术表达式（（a+b）+c*（d+e）+f）*（g+h）的后序序列，并画出该树。（12分） 3.2建立下列算法的基本操作执行次数的递推关系并求解（12分） Void s（int n） If（n==1）return 1； Else return S（n-1）+n*n*n； 3.3已知无向图G有10个顶点，顶点之间的邻接关系如下所示。 V1 V2 V3 V4 V5 V6 V7 V8 V9 V0 V1 0 1 1 1 0 0 0 0 0 0 V2 1 0 0 0 0 0 0 0 0 0 V3 1 0 0 1 1 0 0 0 0 0 V4 1 0 1 0 1 0 0 0 0 0 V5 0 0 1 1 0 0 0 0 0 0 V6 0 0 0 0 0 0 1 0 0 0 V7 0 0 0 0 0 1 0 0 0 0 V8 0 0 0 0 0 0 0 0 1 1 V9 0 0 0 0 0 0 0 1 0 1 V0 0 0 0 0 0 0 0 1 1 0 （1）判断该图包含几个连通分量？写出每个分量所包含的顶点集合（6分） （2）画出的深度优先森林与广度优先森林。（6分） 3.4对关键字1，2，3，4，5，6，7，8，9构建平衡二叉树，并求出平均查找长度ASL（12分）。 3.5假设一段仅含有A,B,C,D,E,F这6个字母组成的西文文本，他们在文本中出现的频率分别为：4%，10%，29%，24%，11%，22%。试为其设计一组二进制编码，使得这段西文文本编码后，所得到的二进制位数总长最短，且译码不会有二义性。（12分） 四．算法设计（40分）（编码困难可以写伪代码，会适当扣分） 4.1 一个长度为n的数组由2，1，-1，-2组成，将其排序成为非递增的数组，要求时间复杂度为on （20分） 例如： 1，1，2，2，-2，-2，-1 输出 2，2，1，1，-1，-2，-2 4.2 在二叉树中，统计所有双分支结点（20分） 2018年华中科技大学887数据结构与算法分析 最后四套卷 三（ 版） 一．名词解释（25分，1个5分） 1.1四种物理存储结构 1.2层次遍历 1.3最小生成树 1.4关键路径 1.5装填因子 二．选择题（25分，1个5分） 2.1 T(N)=3T(N/3)+N,其中N>1,T(1)=1 上述算法时间复杂度是多少（） A. 2`n B.n`2 C. logn D. nlogn 2.2假设已知森林F包含三棵树，三棵树的结点个数分别为m1，m2和m3。BT是森林F所对应的二叉树，该二叉树的右子树应该包含的结点个数为（） A. m1 B. m1+m2 C.. m3 D. m2+m3 2.3 对于含有3个关键字的顺序表（a，b，c），它们的查找概率分别为（1/2,1/3,1/6）,则成功查找表中任一元素的平均查找长度为（） A. 3 B. 5/3 C. 2 D. 1 2.4 下列哪一种图的邻接矩阵一定是对称矩阵（） A. 无向图 B.AOV网 C. 有向图 D. AOE网 2.5排序算法的稳定性是指（） A. 时间复杂度相对稳定 B. 空间复杂度相对稳定 C. 排序前后相同关键字相对顺序不变 D. 效率稳定 三．简答题（60分） 3.1假设一颗二叉树的层次序列为A B C D E F G H I J,中序序列D B G E H J A C I F。请画出这颗二叉树（12分） 3.2建立下列算法的基本操作执行次数的递推关系并求解（12分） Void s（int n） If（n==1）return 1； Else ｛ S（n/2）+n*n*n； S（n/2）+n*n*n； ｝ 3.3已知无向图G有6个顶点，顶点之间的邻接关系如下所示。 (v1-v3 1) （1）画出该无向图G的邻接表存储表示，假定每个顶点的单链表中的结点是按顶点序号从小到大的次序链接（4分） （2）根据如上的邻接表，写出的从顶点V1开始的深度优先序列与广度优先序列。（4分） （3）对于上述的无向图G，给出用普利姆算法（V1开始）构造的最小生成树.(4分) 3.4主串a b a b b a b a b c a 模式串a b a b c 给出KMP算法的具体过程（12分）。 3.5折半查找（二分查找）过程可以利用一颗称之为判定树的二叉树来描述，假设对长度为13的有序表（23，25，32，46，50，58，69，78，79，82，88，90，92） （1）画出对应的判定树。（6分） （2）计算等概率情况下查找成功的平均查找长度ASL的值。(6分) 四．算法设计（40分）（编码困难可以写伪代码，会适当扣分） 4.1 编写函数将一整数序列中所有负数移动到正数前面，要求时间复杂度为O（n）。（20分） 4.2 将二叉树结构逆时针旋转90度。（20分） 例： 2018年华中科技大学887数据结构与算法分析 最后四套卷 四（ 版） 一．名词解释（25分，1个5分） 1.1设计算法的目标 1.2表头结点 1.3树的层次 1.4最优二叉树 1.5简单路径 二．选择题（25分，1个5分） 2.1 TN=log2n+根号（n）+1 上述算法时间复杂度是多少（） A. 根号n B.1 C. logn D. log2n+根号（n）+1 2.2线性表是具有n个（）的有限序列（n>0） A. 表元素 B. 数据元素 C. 数据项 D. 数据结构 2.3一颗有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1...N]中时，数组中第i个结点的左孩子为（） A. [2i](2i<=n) B. [2i+1](2i+1<=n) C. [i/2] D. [i/2+1] 2.4假设采用大小为8的数组表示一个循环队列，且当前front和rear分别为3和6，则执行从队列中删除一个数据元素，再插入2个数据元素操作之后，front和rear的值分别是（） A. 2，0 B.4，0 C. 4，7 D. 2，7 2.5有向无环图G中的有向边集合E={ 三．简答题（60分） 3.1已知一个森林的先序序列和后序序列如下，请构造出该森林（12分） 先序序列： A B C D E F G H I J K L M N O 后序序列： C D E B F H I J G A M L O N K 3.2现在有4个青蛙打算过河，他们都在河的某一端，需求34分钟让它们全部跳到河的另一端。时间是晚上，青蛙们需要打着蜡烛才能过河，且只有一根蜡烛。一次最多只能有两只青蛙同时过河。且每个青蛙蹦的速度不一样：甲青蛙过河2分钟，乙青蛙过河4分钟，丙青蛙10分钟，丁青蛙20分钟，两个青蛙一起跳的速度等于跳的最慢的那只青蛙的速度。给出方法。（12分） 3.3已知连通图G有8个顶点，顶点之间的邻接关系如下所示。 1 2 3 4 5 6 7 8 1 0 1 0 1 1 0 1 0 2 1 0 1 1 0 0 0 0 3 0 1 0 0 0 1 0 1 4 1 1 0 0 1 1 0 1 5 1 0 0 1 0 1 1 1 6 0 0 1 1 1 0 1 0 7 0 0 1 0 1 0 1 0 8 0 0 0 1 1 0 0 0 （1）给出判断是否为无向图的代码片段（6分） （2）分别给出以1为开始的深度生成序列与广度生成序列。（6分） 3.4对于整数序列｛498，012，505，902，177，888，270，648，607，149｝，构造一颗二叉排序数，画出构造结果，并计算平均查找长度ASL. 3.5假设哈希表的地址范围是0-10，哈希函数为：H(K)=K MOD11 K为关键字，用随机探测再散列的方法处理冲突，输入关键字序列｛12，21，23，17，19，28，34，39，33｝ 随机数｛1 3 5 6 7。。。｝ 回答下列问题： （1）画出构造的哈希表。（4分） （2）计算成功查找长度以及失败查找长度。（4分） （3）列出查找关键码29时，依次比较的关键码。（4分） 四．算法设计（40分）（编码困难可以写伪代码，会适当扣分） 4.1在一个长度为n的非递增的数组中，求两个元素，使其差值为X，要求时间复杂度为O（n） （20分） 4.2 设计一个非递归算法将树中每个结点的左右孩子位置交换。（20分）
华中科技大学887数据结构与算法分析_复习八套卷与冲刺四套卷
