厦门大学数据结构与算法陈海山期末习题答案解析Word格式.docx
《厦门大学数据结构与算法陈海山期末习题答案解析Word格式.docx》由会员分享，可在线阅读，更多相关《厦门大学数据结构与算法陈海山期末习题答案解析Word格式.docx（35页珍藏版）》请在冰点文库上搜索。
空间复杂度（SpaceComplexity）：
算法运行所需要的存储空间度量，S（n）=O（f（n））。
1-6设数组A中只存放正数和负数。
试设计算法，将A中的负数调整到前半区间，正数调整到后半区间。
分析算法的时间复杂度。
A[n+1]
For（inti=n-1,j=0;
i>
j;
i--）
{
If（a[i]>
0）continue;
Else{
A[n]=A[i];
A[i]=A[j];
A[j]=A[n];
J++;
}
时间复杂度为O（n）
1-7将上三角矩阵A=（aij）n⨯n的非0元素逐行存于B[（n*（n+1）/2]中，使得B[k]=aij且k=f1（i）+f2（j）+c（f1,f2不含常数项），试推导函数f1,f2和常数c。
k+1=1+2+3+…+（i-1）+j
k=1/2*i*（i-1）+j-1;
1-8描述下列递归函数的功能。
intF（intm,intn）
if（n>
m）returnF（n,m）;
elseif（n==0）returnm;
else
r=m%n;
returnF（n,r）;
求m与n的最大公约数
1-9编写递归算法：
0，m=0且n≥0
g（m,n）=
g（m-1,2n）+n，m>
0且n≥0
doubleg（doublem,doublen）
If（m==0&
&
n>
=0）
return0;
returng（m-1,2*n）+n;
1-10将下列递归过程改写为非递归过程。
voidtest（int&
s）
intx;
scanf（“%d”,&
x）;
if（x==0）s=0;
test（s）;
s+=x;
习题2表
2-1如果长度为n的线性表采用顺序存储结构存储，则在第i（1≤i≤n+1）个位置插入一个新元素的算法的时间复杂度为（）。
（A）O
（1）（B）O（n）（C）O（nlog2n）（D）O（n2）
B
需要让线性表移动n+1-i个
2-2在一个有127个元素的顺序表中插入一个新元素，要求保持顺序表元素的原有（相对）顺序不变，则平均要移动（）个元素。
（A）7（B）32（C）64（D）127
Cn/2+1
2-3将关键字2，4，6，8，10，12，14，16依次存放于一维数组A[0...7]中，如果采用折半查找方法查找关键字，在等概率情况下查找成功时的平均查找长度为（）。
（A）21/8（B）7/2（C）4（D）9/2
A
3,2,3,1,3,2,3,4
公式法1*2^0+2*2^1+3*2^2+…+i*2^（n-1）;
2-4已知顺序表L递增有序。
设计一个算法，将a和b插入L中，要求保持L递增有序且以较高的效率实现。
先用折半查找法查询位置，然后移动
voidinsert（intL[],inta,intb）//a<
b
inti=0,p,q;
n=length（L）;
//L现有长度
//查找确定a、b的位置
for（;
i<
n;
i++）
{
if（L[i]<
=a&
（a<
L[i+1]||i==n-1））
p=i+1;
//a的最终位置
n++;
break;
}
=b&
（b<
q=i+2;
//b的最终位置
//移动元素，插入a，b
for（i=n+1;
q;
L[i]=L[i-2];
L[q]=b;
//插入b
for（i=q-1;
p;
L[i]=L[i-1];
L[p]=a;
//插入a
2-5简单描述静态查找和动态查找的区别。
A静态查找表只查找
B、静态查找表不改变数据元素集合内的数据元素
C、动态查找表不只查找
D、动态查找表还插入或删除集合内的数据元素
2-6综合比较顺序表和链表。
（1）存储空间利用率高——只存储元素值。
（2）随机存取——可以通过计算来确定顺序表中第i个数据元素的存储地址Li=L0+（i-1）*m,其中，L0为第一个数据元素的存储地址，
m为每个数据元素所占用的存储单元数。
（3）插入和删除数据元素会引起大量结点移动.
顺序表：
内存中地址连续
长度不可变更
支持随机查找可以在O
（1）内查找元素
适用于需要大量访问元素的而少量增添/删除元素的程序
链表：
内存中地址非连续
长度可以实时变化
不支持随机查找查找元素时间复杂度O（n）
适用于需要进行大量增添/删除元素操作而对访问元素无要求的程序
2-7解释链表的“头指针、头结点和首元素结点”三个概念。
“头指针”是指向头结点的指针。
"
头结点"
是为了操作的统一、方便而设立的，放在首元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。
“首元结点”也就是第一元素结点，它是头结点后边的第一个结点。
2-8描述下列算法的主要功能是（）。
①构造头结点L，取q=L;
②产生1个结点p;
③q−>
next=p;
④输入p−>
data的值;
⑤取q=p;
⑥重复执行②至⑤n次;
⑦p−>
next=NULL;
（A）通过输入n个数据元素构建链表L
（B）采用前插法，在链表L中输入n个数据元素
（C）通过产生n个结点构建链栈L，q为栈顶指针
（D）在链队列L中输入n个数据元素，q为队尾指针
2-9设L是不带头结点的单链表的头指针，k是一个正整数，则下列算法的主要功能是（）。
LinkSearch（LinkListL,intk）
k0=0;
p=L->
next;
//next为单链表的指针域
q=p;
while（p）
if（k0<
=k）k0++;
elseq=q->
p=p->
q->
next=0;
（A）计算单链表L的长度
（B）查找单链表L中倒数第k个结点
（C）删除单链表L中最后面的k个结点
（D）将单链表L中第k个结点q的指针置0
只遍历一次的高效算法
（排除法）
B
2-10设链表L不带头结点，试分析算法的功能。
A（Linklist&
L）
if（L&
L->
next）
Q=L;
L=L->
P=L;
while（P->
next）P=P->
P->
next=Q;
Q->
}//A算法结束
将链表的第一个结点接到最后一个结点后面
2-11设两个循环链表的长度分别为n和m，则将这两个循环链表连接成一个循环链表，最好的时间复杂度为（）。
（A）O
（1）（B）O（n）（C）O（m）（D）O（min（n，m））
首先取一个指针p指向la的第一个节点（不包括头节点，头节点是空），然后让la头指针指向lb的第二个节点，接着用lb的第一个节点填充lb的头节点，最后将la头节点next指向p
如下图：
还是不明白请自己看ppt第二章P65
2-12设有6个数据元素A，B，C，D，E，F依次进栈。
如果6个数据元素的出栈顺序为B，C，D，F，E，A，则该栈的最小容量为（）。
（A）2（B）3（C）4（D）5
操作栈内元素出栈顺序
A，B入栈A,B
B出栈AB
C入栈A,C
C出栈AB,C
D入栈A,D
D出栈AB,C,D
E,F入栈A,E,F
F出栈A,EB,C,D,F
E出栈AB,C,D,F,E
A出栈B,C,D,F,E,A
因此栈的最小容量只需3
2-13设进栈序列为123，试给出所有可能的出栈序列。
所有可能的出栈序列为：
1,2,3（1入栈，1出栈，2入栈，2出栈，3入栈，3出栈）
1,3,2（1入栈，1出栈，2,3,入栈，3出栈，2出栈）
2,1,3（1,2入栈，2出栈，1出栈，3入栈，3出栈）
2,3,1（1,2入栈，2出栈，3入栈，3出栈，1出栈）
3,2,1（1,2,3入栈，3出栈，2出栈，1出栈）
注意：
唯一只有3,1,2不可能出现，因为3要先出栈，前面1,2,3要按顺序一起入栈，因此不可能出现1在2的前面，后面的题目也是一样。
原则就是只要后入栈的先出栈，那么这个元素前面入栈的元素一定按照入栈顺序的反序排列
2-14如果进栈序列为123456，能否得到出栈序列435612和135426?
435612不能得到6的后面不可能出现1,2的出栈顺序
135426能够得到
2-15简述算法的功能（设数据元素类型为int）：
voidproc（LinkQueue*Q）
LinkStackS;
InitStack（S）;
while（!
EmptyQueue（Q））
DeleteQueue（Q,d）;
Push（S,d）;
EmptyStack（S））
Pop（S,d）;
InsertQueue（Q,d）;
将链队列中的顺序倒过来
如原来ABCDEF，执行完这个算法之后是FEDCBA
2-16按照格式要求给出调用F（3,'
A'
'
B'
C'
）的运行结果：
voidF（intn,charx,chary,charz）
if（n==1）printf（"
1%c→%c\n"
x,z）;
else
F（n-1,x,z,y）;
printf（"
%d%c→%c\n"
n,x,z）;
F（n-1,y,x,z）;
自己去计算，类似汉诺塔
1A->
C
2A->
1C->
3A->
1B->
2B->
2-17已知一维数组B[0..20]用于存储一个下三角矩阵A元素。
设A中第一个元素的下标为1，1，则数组元素B[10]对应A中下标为（）的元素。
（A）2，5（B）4，3（C）5，1（D）6，1
因此B中第10个元素，也就是B[9]对应A[4][4]
[B[10]对应A中是A[5][1]
2-18已知An⨯n为稀疏矩阵。
试从时间和空间角度比较，采用二维数组和三元组顺序表两种存储结构计算∑aij的优缺点。
稀疏矩阵为n行n列.
1）采用二维数组存储，其空间复杂度为Ｏ（n×
n）；
因为要将所有的矩阵元素累加起来，所以，需要用一个两层的嵌套循环，其时间复杂度亦为Ｏ（n×
n）。
2）采用三元组顺序表进行压缩存储，假设矩阵中有t个非零元素，其空间复杂度为Ｏ（t），将所有的矩阵元素累加起来只需将三元组顺序表扫描一遍，其时间复杂度亦为Ｏ（t）。
当t
<
n×
n时，采用三元组顺序表存储可获得较好的时、空性能。
2-19链地址法是Hash表的一种处理冲突的方法，它是将所有哈希地址相同的数据元素都存放在同一个链表中。
关于链地址法的叙述，不正确的是（）。
（A）平均查找长度较短pptP165上面有表述
（B）相关查找算法易于实现查找的时候只需找到哈希地址的那条链，再顺着那条链遍历下去就可以实现。
（C）链表的个数不能少于数据元素的个数可以少于，很明显
（D）更适合于构造表前无法确定表长的情况链表的特点之一‘
2-20设哈希（Hash）函数H（k）=（3k）%11，用线性探测再散列法处理冲突，di=i。
已知为关键字序列22，41，53，46，30，13，01，67构造哈希表如下：
哈希地址012345678910
关键字2241300153461367
则在等概率情况下查找成功时的平均查找长度是（）。
（A）2（B）24/11（C）3（D）3.5
有公式ASL=1/2（1+1/（1-a））=1/2（1+1/（1+11/3））=7/3其中a=8/11（实际填入的数量/线性表的大小）
2-21有100个不同的关键字拟存放在哈希表L中。
处理冲突的方法为线性探测再散列法，其平均查找长度为。
试计算L的长度（一个素数），要求在等概率情况下，查找成功时的平均查找长度不超过3。
素数表：
101,103,107,109,113,127,131,137,139,149,151,157,163,167。
设线性表L长度ln,有:
α=100/ln<
=0.8求出ln>
=125,即由题意选择127这个素数
习题3树
3-1若深度为5的完全二叉树第5层有3个叶子结点，则该二叉树一共有（）个结点。
（A）8（B）13（C）15（D）18
D
利用公式前四层有2^5-1=15个节点，总共为15+3=18个。
3-2设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）。
（A）5（B）6（C）7（D）8
一共有1*4+2*2+3+4=15个度，4+2+1+1=8个节点
叶子为15-8+1=8
解析：
节点数=度数+1
此题也可用画图法（图略）
3-3已知二叉树T中有50个叶子结点，试计算T的总结点数的最小值。
由于是二叉树，那么可知欲使节点数最小，则该二叉树需满足至多存在一个结点的入度为1（即——使每两个结点都有一个父节点）。
50/2=25,（25-1）/2=1212/2=66/2=3（3+1）/2=22/2=1红色部分+1为之前25个结点归根时剩下的1个。
那么总共有50+25+12+6+3+2+1=99个结点
节点数/2+1=叶子数
3-4已知一棵度为k的树中，有n1个度为1的结点，n2个度为2的结点，…，nk个度为k的结点。
试计算该树的叶子结点数。
叶子结点为
3-5对于任意非空二叉树，要设计出其后序遍历的非递归算法而不使用栈结构，最适合的方法是对该二叉树采用（）存储结构。
（A）二叉链表（B）三叉链表（C）索引（D）顺序
三叉链表比二叉链表多一个指向父结点的指针
3-6一棵二叉树的叶子结点在其先序、中序和后序序列中的相对位置（）。
（A）肯定发生变化（B）可能发生变化（C）不会发生变化（D）无法确定
举例子说明即可
3-7设二叉树T按照二叉链表存储，试分析下列递归算法的主要功能。
intF（BiTreeT）
if（!
T）return0;
T->
Lchild&
!
Rchild）return1;
returnF（T->
Lchild）+F（T->
Rchild）;
求二叉树T的叶子结点数
Rchild）+1;
求二叉树T的结点数
3-8已知二叉树T的先序序列为ABCDEF，中序序列为CBAEDF,则T的后序序列为（）。
（A）CBEFDA（B）FEDCBA（C）CBEDFA（D）不确定
3-9简述由先序序列和中序序列构造二叉树的基本操作方法。
1）取先序遍历序列的第一个值，用该值构造根结点，，然后在中序遍历序列中查找与该元素相等的值，这样就可以把序列分为三部分：
左子树（如果有）、根结点和右子树（如果有）。
2）将两个序列都分成三部分，这样就分别形成了根结点的左子树和右子树的先序遍历和后序遍历的序列。
3）重复1）和2）步骤，直至所有结点都处理完就可以完整构成一颗二叉树了。
3-10已知二叉树的先序序列为ebadcfhgikj，中序序列为abcdefghijk，试画出该二叉树。
e
bf
adh
cgi
k
j
3-11已知二叉树T的中序序列和后序序列分别为
（中序）3,7,11,14,18,22,27,35
（后序）3,11,7,14,27,35,22,18
试画出二叉树T。
18
1422
735
31127
3-12已知二叉树T按照二叉链表存储，设计算法，计算T中叶子结点的数目。
3-13已知二叉树T按照二叉链表存储，设计算法，交换T的左子树和右子树。
递归：
IntExchangeBTree（BiTreeT）
temp=（BiTree）malloc（sizeof（BiTNode））;
if（!
T）return;
lchild&
!
rchild）return;
temp=T->
lchild;
T->
lchild=T->
rchild;
rchild=temp;
ExchangeBTree（T->
lchild）;
rchild）;
3-14先序后继线索化算法是根据二叉链表建立先序后继线索二叉链表，其基本原则是在前驱空指针域中写入后继线索，即将右子树的（）指针写入左子树的最后一个叶子结点右指针域。
（A）线索（B）根结点（C）前驱结点（D）后继结点
3-15设计算法，在先序线索二叉树中，查找给定结点p在先序序列中的后继。
线索二叉树：
根据某次遍历,在二叉树中的相关空指针域都写入线索（后继线索或前驱线索），即成为线索二叉树。
线索二叉树可理解为已经线索化的二叉树。
先序后继：
先序遍历中得到的后继（先序前驱,中序后继,中序前驱,后序后继,后序前驱）。
线索二叉树的存储结构
typedefstructNode{
Typedata；
//数据元素域
structNode*Lchild；
//左孩子域
structNode*Rchild；
//右孩子域
intTag；
//0:
分支结点,1:
叶子结点
}BiTNode，*BiTree；
findBirthNode（BiTNodep）
If（p->
tag==0）//p的左子树非空,指向左子树
Returnp->
Lchild;
Else//p为空，后驱则是右子树
Rchild;
3-16设计一种二进制编码，使传送数据a，act，case，cat，ease，sea，seat，state，tea的二进制编码长度最短。
要求描述：
（1）数据对象；
a,c,t,s,e
（2）权值集；
8,3,5,5,6
（3）哈夫曼树；
略
（4）哈夫曼编码。
00,010,011,10,11
3-17按照“逐点插入方法”建立一个二叉排序树，树的形状取决于（）。
（A）数据序列的存储结构（B）数据元素的输入次序
（C）序列中的数据元素的取值范围（D）使用的计算机的软、硬件条件
显然D错误，A也错误因为大小是相对的，对于C，1，3,5和1，10,100相对位置一样，假若插入次序也一样的话，树的形状也不会变得，所以选B
3-18用利用逐点插入法建立序列（50,72,43,85,75,20,35,45,65,30）对应的二叉排序树以后，查找元素35要在元素间进行（）次比较。
（A）3（B）4（C）5（D）8
150
24372
320456585
43575
30
3-19在平衡二叉树中，插入关键字46后得到一颗新的平衡二叉树。
在新的平衡二叉树中，关键字37所在结点的左、右孩子结点中保存的关键字是（）。
（A）18，46（B）25，46（C）25，53（D）25，69
3-20用依次插入关键字的方法，为序列{5,4,2,8,6,9}构造一棵平衡二叉树（要求分别画出构造过程中的各棵不平衡二叉树）。
每次都将平衡
升级会员 