数据结构徐孝凯编著部分习题参考解答Word文档下载推荐.docx
《数据结构徐孝凯编著部分习题参考解答Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构徐孝凯编著部分习题参考解答Word文档下载推荐.docx（42页珍藏版）》请在冰点文库上搜索。
<
q.a<
"
x**2"
;
if（q.b）
if（q.b>
0）
cout<
+"
q.b<
x"
else
if（q.c）
if（q.c>
0）
q.c;
cout<
endl;
2.（给单号题解答）
（1）charCompare（SimpleTypex1,SimpleTypex2）
if（x1>
x2）return'
>
'
elseif（x1==x2）return'
='
elsereturn'
时间复杂度为O
（1）。
（3）doubleProduct（doublea[],intn）
doublep=1;
for（inti=0;
i<
n;
i++）
p*=a[i];
returnp;
时间复杂度为O（n）。
（5）intCount（inta[],intn,intc[5]）
//用数组c[5]保存统计结果
intd[5]={20,50,80,130,201};
//用来保存各统计区间的上限
inti,j;
for（i=0;
i<
5;
i++）c[i]=0;
//给数组c[5]中的每个元素赋初值0
i++）
if（a[i]<
0||a[i]>
200）
return0;
//返回数值0表示数组中数据有错，统计失败。
for（j=0;
j<
j++）//查找a[i]所在的区间
if（a[i]<
d[j]）break;
c[j]++;
//使统计相应区间的元素增1
return1;
//返回数值1表示统计成功
时间复杂度为O（n）
3.（给单号题解答）
（1）voidInitSet（intm[]）
for（inti=1;
=SETSIZE;
m[i]=0;
（3）voidSetUnion（intm1[],intm2[],intm3[]）
InitSet（m3）;
if（m1[i]==1||m2[i]==1）m3[i]=1;
（5）intSetIs（intm[],intitem）
if（m[item]==1）return1;
elsereturn0;
（7）intSetDelete（intm[],intitem）
if（m[item]==1）{m[item]=0;
}
return0;
第二章集合
2.1选择题
1.C2.B3.A4.A5.C6.B
7.D8.B9.A10.C11.D
2.2填空题（给单号题解答）
1.尾部（或表尾）3.1
5.O（n）7.小于等于
9.O（n1*n2）11.O（n2）
2.3运算题（给单号题解答）
1.S={23,72,12,49,35}
3.S={72,35,49,12,23}
5.{23,12}
7.{12,23}
2.4算法分析题（给单号题解答）
1.
运行结果:
1534716
05
3.运行结果：
163479051
2.5算法设计题（给单号题解答）
boolDeleteSet1（SetSq&
S,ElemTypeitem）
S.len;
if（S.set[i]==item）break;
if（i==S.len）returnfalse;
//删除失败返回假
S.set[i]=S.set[S.len-1];
//最后一个元素移到被删元素位置
S.len--;
//集合长度减1
if（float（S.len）/S.MaxSize<
0.4&
&
S.MaxSize>
10）
{//缩减空间处理
ElemType*p=newElemType[S.MaxSize/2];
//空间减少一半
if（!
p）{//分配失败退出运行
cout<
存储空间用完!
exit
（1）;
}
for（i=0;
i++）//把原空间内容复制到新空间中
p[i]=S.set[i];
delete[]S.set;
//释放原集合空间
S.set=p;
//使set指向新集合空间
S.MaxSize=S.MaxSize/2;
//把集合空间大小修改为新的长度
returntrue;
//删除成功返回真
3.
ElemTypeMaxValue（SetSq&
S）
{
if（S.len==0）{cout<
集合为空!
exit
（1）;
ElemTypex=S.set[0];
if（S.set[i]>
x）x=S.set[i];
returnx;
5.
voidDifferenceSet（sNode*&
Head1,sNode*Head2）
sNode*p=Head2;
while（p!
=NULL）{
DeleteSet（Head1,p->
data）;
p=p->
next;
第三章线性表
3.1单项选择题
1.B2.A3.C4.C5.B
6.A7.C8.D9.B10.B
11.A12.C13.D14.B15.A
3.2填空题（给单号题解答）
1.O（n）O（n）
3.O（n）
5.O（n）O（n2）
7.O
（1）O（n）
9.相同
11.p->
next->
next
13.相同
15.3
17.10（或trueNULL）
3.3算法分析题（给单号题解答）
1.（15,12,8,50,30,5,8,12）
3.（8,9,12,20,26,50）
3.4算法设计题（给单号题解答）
1.
//从顺序存储的线性表上统计出值为x的元素个数的算法。
intCount（LiseSq&
L,ElemTypex）//L可以为值参
inti=0,j;
for（j=0;
j<
L.len;
j++）
if（L.list[j]==x）i++;
returni;
//从带头结点的单链接存储的线性表上统计出值为x的元素个数的算法。
intCount（sNode*HL,ElemTypex）
sNode*p=HL->
//将指向第一个结点的指针赋给p
inti=0;
//用i作为统计变量
if（p->
data==x）i++;
3.
//从顺序存储的线性表上删除所有其值重复的多余元素，使所有元素的值均不同。
voidDelete2（ListSq&
L）
//每循环一次将删除list[i]后面与此值相同的的所有元素
while（i<
L.len）{
intj=i+1;
while（j<
L.len）
{
if（L.list[j]==L.list[i]）{//从顺序表中删除data[j]元素
intk;
for（k=j+1;
k<
k++）
L.list[k-1]=L.list[k];
L.len--;
}
elsej++;
i++;
//从单链接存储的线性表上删除所有其值重复的多余结点，使所有结点的值均不同。
voidDelete2（sNode*&
HL）
sNode*p=HL;
//p指向第一个结点
//用t2指向待处理的结点，t1指向t2的前驱结点
sNode*t1=p,*t2=p->
//此循环将从p后面的单链表中删除所有与p结点值相同的结点
while（t2!
if（t2->
data==p->
data）{//删除t2结点
t1->
next=t2->
deletet2;
t2=t1->
//t2指向新的结点
else{//指针后移，以便处理下一个结点
t1=t2;
t2=t2->
//p指向下一个结点
voidInsert（sNode*&
HL,constElemType&
item）
sNode*newptr;
newptr=newsNode;
newptr->
data=item;
sNode*ap,*cp;
ap=HL;
cp=HL->
while（cp!
=HL）
if（item<
cp->
data）break;
else{ap=cp;
cp=cp->
next=cp;
ap->
next=newptr;
7.
voidJosephus（intn,intm,ints）
//使用带表头附加结点的循环单链表解决约瑟夫问题。
//生成表头附加结点，此时循环单链表为空。
sNode*HL=newsNode;
HL->
next=HL;
inti;
//生成含有n个结点的、结点值依次为1,2,...,n的带表头附加结点
//的循环单链表。
for（i=n;
i>
=1;
i--）{
//生成新结点。
sNode*newptr=newsNode;
newptr->
data=i;
//把新结点插入到表头。
next=HL->
HL->
//从表头开始顺序查找出第s个结点，对应第一个开始报数的人
sNode*ap=HL,*cp=HL->
for（i=1;
s;
i++）{
//ap和cp指针后移一个位置。
ap=cp;
cp=cp->
//若cp指向了表头附加结点，则仍需后移ap和cp指针，
//使之指向表头结点。
if（cp==HL）{ap=HL;
//依次使n-1个人出列。
//顺序查找出待出列的人，即为循环结束后cp所指向的结点
for（intj=1;
m;
j++）{
ap=cp;
cp=cp->
if（cp==HL）{ap=HL;
//输出cp结点的值，即出列的人
data<
"
//从单链表中删除cp结点
ap->
next=cp->
deletecp;
//使cp指针指向被删除结点的后继结点
cp=ap->
//若cp指向了表头附加结点，则后移ap和cp指针
//使最后一个人出列。
HL->
//删除表头结点和表头附加结点。
deleteHL->
deleteHL;
9.
intFind（GLNode*GL,charch）
//从广义表GL中查找单元素字符等于ch的算法，若查找成功
//则返回数值1，否则返回数值0。
while（GL!
if（GL->
tag==0）{//处理单元素结点
if（GL->
data==ch）return1;
//查找成功返回1
elseGL=GL->
//否则继续向后查找
else{//处理子表结点。
intx=Find（GL->
sublist,ch）;
//向子表中继续查找。
if（x）//若在子表中查找成功则返回1，否则继续向后查找。
return1;
else
GL=GL->
//当查找到表为空时返回0。
第四章栈和队列
4.1单选题
1．A2.B3.C4.B5.D6.C
7.C8.A9.C10.B11.A12.D
13.D14.A15.C16.D17.B
4.2填空题（给单号题解答）
1．队尾队首
3．栈顶指针写入
5．Q.front==Q.rear（Q.rear+1）%MaxSize==Q.front
7．新结点的指针域栈顶指针
9．top==0
11.3x2+*5-
13．相反次序
15．返回地址
17.pop（S）pop（S）push（S,d）
4.3运算题（给单号题解答）
1.
第
（1）个序列可以得到，操作过程为：
push（S,A）,push（S,B）,push（S,C）,pop（S）,push（S,D）,pop（S）,pop（S）,push（S,E）,pop（S）,push（S,F）,pop（S）,pop（S）。
第
（2）个序列可以得到，操作过程为：
push（S,A）,pop（S）,push（S,B）,pop（S）,push（S,C）,push（S,D）,push（S,E）,pop（S）,pop（S）,push（S,F）,pop（S）,pop（S）。
第（3）个序列不可以得到，因为按照栈的后进先出或者称先进后出的原则，当A,B,C,D相继入栈，再做两次出栈时，A和B仍在栈中，此后只能B在A前面出栈，而在此序列中出现了A先于B出栈的情况，所以说此序列是错误的。
第（4）个序列不可以得到，因为在某一时刻，C和D同在栈中，并且D是栈顶，此后只能D先于C出栈，而在此序列中出现了C先于D出栈的情况，所以是错误的。
3.
0123456
80
34
23
45
67
rearfront
15
36
48
4.4算法分析题（给单号题解答）
1.求出数组a中n个元素之和。
3.把一个正整数num转换为一个十六进制数输出
4.5算法设计题（给单号题解答）
1.intSquareSum（intn）
if（n==0）return0;
elsereturnn*n+SquareSum（n-1）;
3.递归算法为：
intFib（intn）
if（n==1||n==2）returnn-1;
//终止递归条件
elsereturnFib（n-1）+Fib（n-2）;
非递归算法为：
intFib1（intn）
inta,b,c;
//c代表当前项，a和b分别代表当前项前面的
//第2项和第1项
a=0;
b=1;
//分别给a和b赋初值
elsefor（inti=3;
=n;
c=a+b;
//求出当前项
a=b;
//把前面第1项赋给前面第2项
b=c;
//把当前项赋给前面第1项
returnc;
//返回所求的第n项
5.参考算法如下：
voidInitStack（BothStack&
BS,intk）
if（k==1）
BS.top1=-1;
elseif（k==2）
BS.top2=MaxSize;
elseif（k==3）{
voidClearStack（BothStack&
{//函数体同上
boolStackEmpty（BothStack&
returnBS.top1==-1;
returnBS.top2==MaxSize;
elseif（k==3）
return（BS.top1==-1）&
（BS.top2==MaxSize）;
else{
cerr<
k的值不正确!
ElemTypePeek（BothStack&
if（k==1）{
if（BS.top1==-1）{
Stack1isempty!
returnBS.stack[BS.top1];
elseif（k==2）{
if（BS.top2==MaxSize）{
Stack2isempty!
returnBS.stack[BS.top2];
voidPush（BothStack&
BS,intk,constElemType&
if（BS.top1==BS.top2-1）{
Stackoverflow!
BS.top1++;
BS.stack[BS.top1]=item;
BS.top2--;
BS.stack[BS.top2]=item;
ElemTypePop（BothStack&
BS.top1--;
returnBS.stack[BS.top1+1];
BS.top2++;
returnBS.stack[BS.top2-1];
任何递归算法都可以编写为非递归算法的形式，这通常需要在非递归算法中定义和使用栈。
对于求解迷宫问题同样可以编写出递归算法，为此需要定义栈中的元素类型ElemType为描述迷宫中当前位置的结构类型，该结构类型为：
structitems//定义描述迷宫中当前位置的结构类型
{
intx,y,d;
//x和y分别表示当前位置的行坐标和列坐标，
//d表示移动到下一步的方向
};
求解迷宫的非递归算法如下：
voidSeekPath（intm,intn）
//查找m*n迷宫中从入口（1,1）到出口（m,n）的一条通路
//将入口点访问标记置为1，表示将访问它
mark[1][1]=1;
//定义栈并初始化，栈的元素类型为items
StackSqS;
InitStack（S,5）;
//定义temp为进出栈的变量
itemstemp;
//将入口点位置及方向初值-1压入栈
temp.x=1;
temp.y=
升级会员 