《数据结构与算法》课后习题答案Word格式.docx
《《数据结构与算法》课后习题答案Word格式.docx》由会员分享，可在线阅读，更多相关《《数据结构与算法》课后习题答案Word格式.docx（63页珍藏版）》请在冰点文库上搜索。
A->
last）
*/
{k=i+1;
while（k<
=A->
last&
data[i]==A->
data[k]）
k++;
n=k-i-1;
for（j=k;
j<
=A_>
last;
j++）
data[j-n]=A->
data[j];
last=A->
last-n;
i++;
3.写一个算法，从一个给定的顺序表A中删除值在x~y（x<
=y）之间的所有元素，要求
以较高的效率来实现。
【提示】对顺序表A，从前向后依次判断当前元素A->
data[i]是否介于x和y之间，若是，
并不立即删除，而是用n记录删除时应前移元素的位移量；
若不是，则将A->
data[i]向前移
动n位。
n用来记录当前已删除元素的个数。
voiddelete（Seqlist*A,intx,inty）
{i=0;
n=0;
n++;
/*若A->
data[i]介于x和y之间，n自增*/
/*否则向前移动A->
data[i]*/
while（i<
{if（A->
data[i]>
=x&
A->
data[i]<
=y）elseA->
data[i-n]=A->
data[i];
last-=n;
4•线性表中有n个元素，每个元素是一个字符，现存于向量R[n]中，试写一算法，使
R中的字符按字母字符、数字字符和其它字符的顺序排列。
要求利用原来的存储空间，元素
移动次数最小。
【提示】对线性表进行两次扫描，第一次将所有的字母放在前面，第二次将所有的数字放在
字母之后，其它字符之前。
intfch（charc）/*判断c是否字母*/
{if（c>
='
a'
c<
z'
||c>
A'
Z'
）return
（1）;
elsereturn（0）;
intfnum（charc）/*判断c是否数字*/
0'
9'
voidprocess（charR[n]）
{low=0;
high=n-1;
while（low<
high）/*将字母放在前面*/
{while（low<
high&
fch（R[low]））low++;
high&
!
fch（R[high]））high--;
if（low<
high）
{k=R[low];
R[low]=R[high];
R[high]=k;
low=low+1;
high）/*将数字放在字母后面，其它字符前面*/
fnum（R[low]））low++;
while（low<
!
fnum（R[high]））high--;
5•线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个
元素和后n个元素进行整体互换。
即将线性表：
（a1,a2,…，mb1,b2,…，b改变为：
（b1,b2,…,rb,a1,a2,…，m）。
【提示】比较m和n的大小，若m<
n，则将表中元素依次前移m次；
否则，将表中元素依次
后移n次。
voidprocess（Seqlist*L,intm,intn）
{if（m<
=n）
for（i=1;
i<
=m;
i++）{x=L->
data[0];
for（k=1;
k<
=L->
k++）
L->
data[k-1]=L->
data[k];
data[L->
last]=x;
elsefor（i=1;
=n;
last];
for（k=L->
last-1;
k>
=0;
k--）
data[k+1]=L->
data[O]=x;
6•已知带头结点的单链表L中的结点是按整数值递增排列的，试写一算法，将值为x的
结点插入到表L中，使得L仍然递增有序，并且分析算法的时间复杂度。
LinkListCombine（LinkListA,LinkListB）{C=A;
rc=C;
pa=A->
next;
pb=B->
free（B）;
while（pa&
pb）
/*pa指向表A的第一个结点*/
/*pb指向表B的第一个结点*/
/*释放B的头结点*/
/*将pa、pb所指向结点中，值较小的一个插入到链表C的表尾*/
if（pa->
data<
pb->
data）
{rc->
next=pa;
rc=pa;
pa=pa->
else
{rc_>
next=pb;
rc=pb;
pb=pb->
if（pa）rc->
elserc->
next=pb;
/*将链表A或B中剩余的部分链接到链表C的表尾*/
return（C）;
假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一
结点的指针，编写算法删除该结点的前驱结点。
【提示】利用循环单链表的特点，通过s指针可循环找到其前驱结点p及p的前驱结点q,
然后可删除结点*p。
vioddelepre（LNode*s）
{LNode*p,*q;
P=S；
while（p->
next!
=s）
{q=p;
p=p->
q_>
next=s;
free（p）;
9•已知两个单链表A和B分别表示两个集合，其元素递增排列，编写算法求出A和B
的交集C,要求C同样以元素递增的单链表形式存储。
【提示】交集指的是两个单链表的元素值相同的结点的集合，为了操作方便，先让单链表C
带有一个头结点，最后将其删除掉。
算法中指针p用来指向A中的当前结点，指针q用来
指向B中的当前结点，将其值进行比较，两者相等时，属于交集中的一个元素，两者不等时，将其较小者跳过，继续后面的比较。
LinkListIntersect（LinkListA,LinkListB）
{LNode*q,*p,*r,*s;
LinkListC;
C=（LNode*）malloc（sizeof（LNode））;
C->
next=NULL;
r=C;
p=A;
q=B;
while（p&
q）
if（p->
q->
data）p=p->
elseif（p->
data==q->
{s=（LNode*）malloc（sizeof（LNode））;
s->
data=p->
data;
r->
r=s;
q=q_>
}elseq=q->
next;
next=NULL;
C=C->
next;
returnC;
10.设有一个双向链表，每个结点中除有prior、data和next域外，还有一个访问频度
freq域，在链表被起用之前，该域的值初始化为零。
每当在链表进行一次Locata（L,x）运算后，
令值为x的结点中的freq域增1,并调整表中结点的次序，使其按访问频度的非递增序列排
列，以便使频繁访问的结点总是靠近表头。
试写一个满足上述要求的Locata（L,x）算法。
【提示】在定位操作的同时，需要调整链表中结点的次序：
每次进行定位操作后，要查看所
查找结点的freq域，将其同前面结点的freq域进行比较，同时进行结点次序的调整。
typedefstructdnode
{datatypedata;
intfreq;
structDLnode*prior,*next;
}DLnode,*DLinkList;
DlinkListLocate（DLinkListL,datatypex）
{p=L->
while（p&
p->
data!
=x）p=p->
if（!
p）return（NULL）;
p_>
freq++;
while（p->
prior!
=L&
prior->
freq<
freq）{k=p->
p->
data=k;
k=p->
freq;
freq=p->
freq=k;
prior;
return（p）;
/*查找值为x的结点，使p指向它*/
/*若查找失败，返回空指针*/
/*修改p的freq域*/
/*调整结点的次序*/
/*返回找到的结点的地址*/
3.3课后习题解答##
3.3.1选择题
A.仅修改头指针B.仅修改尾指针
C.头、尾指针都要修改D•头、尾指针可能都要修改
9•递归过程或函数调用时，处理参数及返回地址，要用一种称为（C）的数据结构。
A.队列B.静态链表
10.栈和队都是（C）。
C.栈D.顺序表
A•顺序存储的线性结构
332判断题
1•栈和队列的存储，既可以采用顺序存储结构，又可以采用链式存储结构。
2•任何一个递归过程都可以转换成非递归过程。
（“）
3•若输入序列为1,2,3,4,5,6，则通过一个栈可以输出序列3,2,5,6,4,1。
4•通常使用队列来处理函数的调用。
5•循环队列通常用指针来实现队列的头尾相接。
3.3.3简答题
1•循环队列的优点是什么？
如何判别它的空和满？
循环队列的优点是能够克服“假溢满”现象。
设有循环队列sq,队满的判别条件为：
（sq->
rear+1）%maxsize==sq->
front;
或sq->
num==maxsize。
队空的判别条件为：
sq->
rear==sq->
front。
2•栈和队列数据结构各有什么特点，什么情况下用到栈，什么情况下用到队列？
栈和队列都是操作受限的线性表，栈的运算规则是“后进先出”，队列的运算规则是“先
进先出”。
栈的应用如数制转换、递归算法的实现等，队列的应用如树的层次遍历等。
3.什么是递归？
递归程序有什么优缺点？
一个函数在结束本函数之前，直接或间接调用函数自身，称为递归。
例如，函数f在执
行中，又调用函数f自身，这称为直接递归；
若函数f在执行中，调用函数g，而g在执行中，又调用函数f，这称为间接递归。
在实际应用中，多为直接递归，也常简称为递归。
递归程序的优点是程序结构简单、清晰，易证明其正确性。
缺点是执行中占内存空间较
多，运行效率低。
4•设有编号为1,2,3,4的四辆车，顺序进入一个栈式结构的站台，试写出这四辆车开出车站的所有可能的顺序（每辆车可能入站，可能不入站，时间也可能不等）。
1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214,3241,3421,4321
4.3课后习题解答###
4.3.1选择题
1.下面关于串的叙述错误的是（C）。
A.串是字符的有限序列
B•串既可以采用顺序存储，也可以采用链式存储
C.空串是由空格构成的串
D.模式匹配是串的一种重要运算
2.串的长度是指（B）。
A.串中所含不同字母的个数B.串中所含字符的个数
C.串中所含不同字符的个数D.串中所含非空格字符的个数
3.已知串S='
aaab'
，其Next数组值为（D）。
A.0123B.1123C.1231D.1211
4•二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要（D）个字节；
M的第8列和第5行共占（A）个字节；
若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优
先方式存储时的（C）兀素的起始地址一致
茨。
240
D.540
（1）A.
.90
B.180C.
（2）A.
.108
B.114C.
54
D.60
（3）A.
.M[8][5]
B.M[3][10]
C.
M[5][8]
D.M[0][9]
5.数组
A中，每个兀素的存储占
3个单元，
行下标
i从1到8，列下标j从1到10,
从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（C）,若该数组
按行存放，兀素
:
A[8][5]的起始地址是（C）,若该数组按列存放，兀素A[8][5]的起始地址是
（C）。
（1）
A.
80
B.100
C.240
D.270
（2）
SA+141
B.SA+144
C.SA+222
D.SA+225
（3）
B.SA+180
C.SA+117
6.稀疏矩阵采用压缩存储，一般有（
C）两种方法。
A.二维数组和三维数组B.三元组和散列
C.三元组表和十字链表D.散列和十字链表
4.3.2判断题
1.串相等是指两个串的长度相等。
2.KMP算法的特点是在模式匹配时指示主串的指针不会变小。
3.稀疏矩阵压缩存储后，必会失去随机存取功能。
4•数组是线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。
5•若采用三元组存储稀疏矩阵，把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。
6•若一个广义表的表头为空表，则此广义表亦为空表。
7•所谓取广义表的表尾就是返回广义表中最后一个元素。
4.3.3简答题
1.KMP算法较朴素的模式匹配算法有哪些改进？
KMP算法主要优点是主串指针不回溯。
当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出。
2.设字符串S=‘aabaabaabaac'
P=‘aabaac。
（1）给出S和P的next值和nextval值；
（2）若S作主串，P作模式串，试给出利用KMP算法的匹配过程。
【解答】
（1）S的next与nextval值分别为012123456789和002002002009,p的next与nextval值分别为012123和002003。
（2）利用BF算法的匹配过程：
禾U用KMP算法的匹配过程：
第一趟匹配：
aabaabaabaac第一趟匹配：
aabaabaabaac
aabaac（i=6,j=6）aabaac（i=6,j=6）
第二趟匹配：
aa（i=3,j=2）
（aa）baac
第三趟匹配：
a（i=3,j=1）
（成功）（aa）baac
第四趟匹配：
aabaac（i=9,j=6）
第五趟匹配：
aa（i=6,j=2）
第六趟匹配：
a（i=6,j=1）
第七趟匹配：
（成功）aabaac（i=13,j=7）
3•假设按行优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100,每个整
数占4个字节。
问下列元素的存储地址是什么？
（1）aoooo
（2）aiiii（3）a3i25（4）a8247
（i）LOC（a0000）=i00
（2）LOC（aiiii）=i00+（3*5*8*i+5*8*i+8*i+i）*4=776
（3）LOC（a3i25）=i00+（3*5*8*3+5*8*i+8*2+5）*4=i784
（4）LOC（a8247）=i00+（3*5*8*8+5*8*2+8*4+7）*4=48i6
4•假设一个准对角矩阵：
广aiiai2、
a2ia22
a33a34
a43a44
a2m-i,2m-ia2m-i,2m
32m,2m-i32m,2m丿
aii
ai2
a2i
a22
a33
a34
a43
aij
a2m-1,2m
a2m,2m-1
a2m,2m
按以下方式存储于一维数组
B[4m]中（m为一个整数）
0123456…k…4m-14m
写出下标转换函数k=f（i,j）。
由题目可知，每一行有两个非0元素。
当i为奇数时，第i行的兀素为：
ai,i、ai,（i+i）,此时k=2*（i-1）+j-i=i+j-2当i为偶数时，第i行的元素为：
ai,（i-i）、ai,i，此时k=2*（i-1）+j-I+1=i+j-1综上所述，k=i+j-i%2-1。
5.设有n>
h的带宽为3的带状矩阵A，将其3条对角线上的元素存于数组B[3][n]中,
使得元素B[u][v]=aj,试推导出从（i,j）至U（u,v）的下标变换公式。
u=j-i+1
v=j-1
6•现有如下的稀疏矩阵A（如图所示），要求画出以下各种表示方法。
（1）三元组表表示法
（2）十字链表法。
r
22
-15
13
3
-6
91
1
28
丿
（1）三元组表表示法
v
4
2
6
5
7
（2）十字链表法:
7.画出下列广义表的头尾表示存储结构示意图。
（1）A=（（a,b,c）,d,（a,b,c））
（2）B=（a,（b,（c,d）,e）,f）
5.3课后习题解答
5.3.1选择题
B.p_>
ltag=1且p->
rtag=1
D.p->
lchild=NULL且p->
ltag=1
4.如果结点A有3个兄弟，而且B是A的双亲，则B的度是（B）。
5.某二叉树T有n个结点,设按某种顺序对T中的每个结点进行编号，编号值为1,2,...n。
且有如下性质:
T中任意结点v,其编号等于左子树上的最小编号减1，而v的右子树的结点中,其最小编号等于v左子树上结点的最大编号加1,这是按（B）编号的。
A.中序遍历序列B.先序遍历序列C.后序遍历序列D.层次顺序
6.设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点,B中右指针域为空的结点有（C）个。
A.n-1B.nC.n+1D.n+2
7.
B）。
N1，N2和N3。
与
—棵完全二叉树上有1001个结点，其中叶子结点的个数是（
A.500B.501C.490D.495
设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为森林F对应的二叉树根结点的右子树上的结点个数是（D）。
A.N1B.N1+N2C.N2D.N2+N3
9.任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对次序（A）。
A•不发生改变B.发生改变C.
升级会员 