数据结构与实训习题答案.docx
《数据结构与实训习题答案.docx》由会员分享，可在线阅读，更多相关《数据结构与实训习题答案.docx（58页珍藏版）》请在冰点文库上搜索。
数据结构与实训习题答案
第1章习题答案
1.填空题
（1）在计算机中的存储映像（是逻辑结构在计算机中的实现或存储表示）数据元素的表示元素之间关系的表示数据元素。
（2）已经实现是一个概念分离分离
（3）时、空效率指人对算法阅读理解的难易程度对于非法的输入数据，算法能给出相应的响应，而不是产生不可预料的后果。
（4）软硬件环境问题规模的
（5）最坏
（6）O（n4）O（n2）
（7）时间复杂度
（8）n
O（n2）
2.判断题
（1）×
（2）×（3）√（4）√（5）√（6）√（7）×（8）×（9）×（10）×
3.简答题
（1）略（见教材第3页的1.2数据结构的基本概念）
（2）（a）n-1，O（n）（b）n-1,O（n）
（c）11*n+1,O（n）（n为初始值100）
（d）
O（
）（e）n,O（n）
第2章习题及答案
1、填空题
（1）address+m*i
（2）顺序顺序顺序链式存储链式存储
（3）亦相邻不一定
（4）n-i+1
（5）0≤i≤la的长度-1≤j≤lb的长度-10≤k≤lc的长度-1
（6）
插入的位置，节点数n（顺序表长度n）
（7）其前驱O（n）O
（1）
（8）其前驱O（n）O
（1）
（9）p→next=p→next→next
（10）head→next==Nullhead==Nullhead→next==headhead==Null
（11）head→next=head→next→nexthead=head→next
（12）x=p→prior→data;p→prior→data=p→next→data;p→next→data=x;
（13）p==head→prior（或p→next==head）
2．判断题
（1）×
（2）√（3）×（4）×（5）×（6）×（7）√（8）×（9）×（10）×
3．简答题
（1）
单向循环链表
双向循环链表
存储密度
高
低
查找后继的时间复杂度
O
（1）
O
（1）
查找前驱的时间复杂度
O（n）
O
（1）
（2）在带头结点的单链表上，查找指针p所指结点的前驱。
（3）交换指针p与指针q所指结点的值。
4．算法设计题
（1）
voidreverse（SeqListl）
{for（i=0;i<=（l.listlength-1）/2;i++）
l.elem[i]<—>l.elem[l.listlength-1-i];
}
（2）
voiddelete（SeqList,inti,intk）
/*从顺序表中删除自第i个元素开始的k个元素*/
{if（i<0||i>l.listlength-1||k<0）
{printf（“Error”）;
return;
}
if（i+k<=l.listlength）/*表中从i个元素起到最后一个元素有k个元素*/
{for（j=i+k;jl.elem[j-k]=l.elem[j];
l.listlengt=l.listlength-k;
}
else/*表中从i个元素起直到最后一个元素不足k个元素*/
l.listlength=i;
}
（3）
voidinsert（LinkListh,ElementTypex）
/*将x插入到递增链表h中，插入后的链表有序性不变*/
{if（h→next==Null）/*空表时*/
{q=（linklist）malloc（sizeof（ListNode））;
q→next=Null;
q→data=x;
h→next=q;
}
p1=h→next;p2=h;
while（p1→next!
=Null&&p1→data{p2=p1;
p1=p1→next;
}
if（p1→next==Null&&p1→data{q=（linklist）malloc（sizeof（ListNode））;
q→next=Null;
q→data=x;
p1→next=q;
}
else/*（p1→next==Null&&p1→data>=x）||（p1→next!
=Null&&p1→data>=x）*/
{q=（LinkList）malloc（sizeof（ListNode）;
q→data=x;
p2→next=q;
q→next=p1;
}
}
（4）
voiddelete（LinkListp）
/*在不带头结点且长度大于1的单向循环链表中，p指向某结点，删除p的前驱结点*/
{ppp=p→next;
while（ppp→next→next!
=p）
ppp=ppp→next;
/*删除p的前驱结点*/
pp=ppp→next;
ppp→next=pp→next;
free（pp）;
}
（5）
voiddelete（LinkListh）
/*h为带头结点的，非降序排列的单链表的头指针，删除表中值相同的结点，使之只保留一个*/
{p=h→next;
if（!
p）return;
x=p→data;
while（p→next）
if（x!
=p→next→data）
{x=p→next→data;
p=p→next
}
else
{q=p→next;
p→next=p→next→next;
free（q）;
}
}
voiddelete（LinkListh）
/*删除带头结点的单链表h（指向头结点）中值为x的结点的前驱结点*/
{if（!
（h→next））return;
if（!
（h→next→next））return;
p1=h→next→next;
p2=h;
while（p1→next&&p1→data!
=x）
{p1=p1→next;
p2=p2→next;
}
if（p1→data==x）
{q=p2→next;
p2→next=p1;
free（q）;
}
}
（7）
Linklistsubtraction（LinkListla,LinkListlb）
/*la,lb分别为表示集合A,B的带头结点的单链表的头指针，A-B由la链表返回*/
{if（!
（la→next））
return（la）;
else
{pa1=la→next;
pa2=la;
}
if（!
（lb→next））return（la）;
while（pa1）
{pb=lb→next;
while（pb&&pa1→data!
=pb→data）
pb=pb→next;
if（pb）/*pa1→data==pb→data*/
{pa2→next=pa1→next;
free（pa1）;
pa1=pa2→next;
}
else
{pa1=pa1→next;
pa2=pa2→next;
}
}
return（la）;
}
（8）
LinkListintersection（LinkListla,LinkListlb）
/*la,lb,lc分别为表示集合A,B,C的带头结点的递增有序的单链表的头指针，C=A∩B由lc链表返回*/
{lc=（LinkList）malloc（sizeof（LinkNode））;
lc→next=null;
tail=lc;/*tail指向lc链的尾结点*/
if（!
（la→next））
return（lc）;
else
pa=la→next;
if（!
（lb→next））return（lc）;
while（pa）
{pb=lb→next;
while（pb&&pa→data!
=pb→data）
pb=pb→next;
if（pb）insert（lc,tail,pa→data）;
pa=pa→next;
}
return（lc）;
}
voidinsert（LinkListl,LinkListtail,ElemenTypex）
/*将值x插入到单链表l的尾部*/
{p=（LinkList）malloc（sizeof（LinkNode））
p→data=x;
p→next=null;
tail→next=p;
tail=p;
}
SeqListintersection（SeqListla,SeqListlb）
/*集合A,B,C对应的顺序递增表为la,lb,lc，C=A∩B由lc表示*/
{lc.listlength=0;
if（la.listlength==0||lb.listlength==0）return（lc）
for（a=0;a{for（b=0;b=la.elem[a];b++）
if（b{lc.elem[lc.listlength]=la.elem[a];
lc.listlength++;
}
}
retuen（lc）;
}
（9）
voiddelete（LinkListh,ElementTypeminElementTypemax）
/*h是带头结点的无序单链表的头指针，删除结点值大于min小于max的结点*/
{if（!
（h→next））return;
p1=h→next;
p2=h;
while（p1）
if（p1→data>min&&p1→data{p2→next=p1→next;
free（p1）;
p1=p2→next;
}
else
{p1=p1→next;
p2=p2→next;
}
}
（10）
voidseparation（LinkListh,LinkList*ph1,LinkList*ph2）
/*h为带头结点的单链表的头指针，该表中含有两类字符数据元素：
字母与数字，拆分h为两条带头结点的单项循环链表*ph1、*ph2，其中*ph1链中存放字母，*ph2链中存放数字*/
{if（!
（h→next））return;
p=h→next;
free（h）;
*ph1=（LinkList）malloc（sizeof（LinkNode））;
（*ph1）→next=*ph1;
*ph2=（LinkList）malloc（sizeof（LinkNode））;
（*ph2）→next=*ph2;
while（p）
{h=p;
p=p→next;
if（h→data>=’0’&&h→data<=’9’）/*数字字符插入到*ph2链*/
{h→next=（*ph2）→next;
（*ph2）→next=h;
}
else/*字母字符插入到*ph1链*/
{h→next=（*ph1）→next;
（*ph1）→next=h;
}
}
}
（11）
voidmerge（DoubleListhead1,DoubleListhead2）
/*head1、head2分别为两个带头结点的双向循环链表的头指针，将head1链接到head2*/
{if（head1→next==head1）return;/*head1为空链表*/
head2→prior→next=head1→next;
head1→next→prior=head2→prior;
head1→prior→next=head2;
head2→prior=head1→prior;
free（head1）;
}
（12）
voiddelete（DoubleListhead,DoubleNode*p）
/*head为带头结点的双向循环链表的头指针，p指向head链中的某一个结点，删除p的前驱结点*/
{if（p→prior==head）return;/*p结点无前驱结点*/
q=p→prior;/*q指向p的前驱结点*/
p→prior→prior→next=p;
p→prior=p→prior→prior;
free（q）;
}
第3章习题及答案
1．填空题
（1）1，3，51
（2）push,pop,push,push,pop,push,pop,pop
（3）栈空栈满
（4）O
（1）O
（1）
（5）=s.top-1=s.top+1
（6）s
（7）空
（8）栈底栈顶
（9）队尾队首（头）
（10）是否为空是否为满
（11）21
（12）front→next==rear
（13）front==rear（rear+1）%MAX==frontrear+MAX-frort
2．判断题
（1）√
（2）×（3）√（4）√（5）×（6）√（7）√（8）×（9）√（10）√
3．简答题
（1）当进行入队操作时，队尾指针的值已经到达数组空间的最大下标（MaxSize-1），而队首指针的值却大于0，这时就产生了假溢出现象。
（2）使栈s中的元素顺序置逆。
（3）借助于另一链栈t，使得链栈s去掉指定的元素e。
4．算法设计题
（1）
intmaxvalue（SeqStacks）
/*s是存有整数序列a1,a2,…,an的堆栈，用递归求其中的最大值*/
{if（s.top!
=-1）
if（s.top==0）
return（Pop（s））;
else
{e=Pop（s）;
return（max（e,maxvalue（s）））;
}
}
（2）
intg（intn）
/*递归计算g（n）的值g（n）=1（当n=0），g（n）=n*g（n/2）（当n>0）*/
{if（n>=0）
if（n==0）
return
（1）;
else
return（n*g（n/2））;
}
（3）
intakm（intm,intn）
/*递归计算akm（m,n）的值*/
{if（m>=0&&n>=0）
if（m==0）
return（n+1）;
elseif（n==0）
return（akm（m-1,1））;
else
return（akm（m-1,akm（m,n-1）））;
}
（4）
（5）
对于输入序列1,2,3,4,对应的24种排列是：
1,2,3,41,2,4,31,3,2,41,3,4,21,4,2,31,4,3,2
2,1,3,42,1,4,32,3,1,42,3,4,12,4,1,32,4,3,1
3,1,2,43,1,4,23,2,1,43,2,4,13,4,1,23,4,2,1
4,1,2,34,1,3,24,2,1,34,2,3,14,3,1,24,3,2,1
无下划线的序列可以通过相应的入、出栈得到。
可以通过入、出栈得到的输出序列中的每一个数，在它后面的比它小的数应是降序排列的。
（6）
voidAddQueue（Queueq,ElementTypee）
/*入队*/
{if（q.count==maxsige）
{printf（“\noverflow”）;
return;
}
q.elem[（q.front+q.count）%MaxSize]=e;
q.count++;
}
ElementTypeDeleteQueue（Queueq）
/*出队*/
{if（q.count==0）return（nil）;
e=q.elem[q.front];
q.front=（q.front+1）%MaxSize;
q.count--;
return（e）;
}
（7）
①A,D是合法的
②
intlegality（SeqListl）
/*入、出栈序列存放在l.elem[]数组中，该序列合法返回1，否则返回0*/
{count=0;
for（i=0;iif（l.elem[i]==’I’
count++;
else
{count--;
if（count<0）return（0）;/*栈空时出栈*/
}
if（count==0）
return
（1）;
else
return（0）;/*栈不空（没有回到初始状态*/
}
（8）
typedefstructQnode
{ElementTypedata;
StructQnode*next;
}QueueNode;
typedefQueueNode*LinkQueue;
voidAddQueue（LinkQueuerear,ElementTypee）
/*带头结点的循环链表队列，只有指向尾结点的指针rear，对其实现入队操作*/
{p=（LinkQueue）malloc（sizeof（QueueNode））;
p→data=e;
p→next=rear→next;
rear→next=p;
rear=p;
}
ElementypeDeleteQueue（LinkQueuerear）
/*带头结点的循环链表队列，只有指向尾结点的指针rear，对其实现出队操作*/
{if（rear→next==rear）
{printf（“\nempty”）;
return（nil）;
}
p=rear→next→next;
e=p→data;
rear→next→next=rear→next→next→next;
free（p）;
return（e）;
}
（9）
①
voidAddQueue（CirQueueq,ElementTypee）
/*借助于堆栈s1、s2实现队列q的入队*/
{Push（s1,e）;
}
②
ElementTypeDeleteQueue（CirQueueq）
/*借助于堆栈s1、s2实现队列q的出队*/
{if（Empty（s1）&&Empty（s2））
{printf（“\nempty”）;
return（nil）;
}
else
if（!
Empty（s2））
Pop（s2）;
else
{while（!
Empty（s1））
Push（s2,Pop（s1））;
Pop（s2）;
}
}
第4章习题及答案
1.填空题
（1）字符
（2）0空格的个数
（3）14“bccadcabcadfabc”“abc”81（true）“bccadcbcadf”“abcbccadcabcadf”“bcadcabcadf”
（4）197
（5）三维数组arr[6][2][3]的每个元素的长度为4个字节，如果数组以行优先的顺序存储，且第1个元素的地址是4000，那么元素arr[5][0][2]的地址是4000+4*（5*2*3+0*3*2）=4128
2.判断题
（1）×
（2）√（3）×（4）√（5）√（6）√（7）×（8）√（9）×（10）√
3.
（1）
v=j
（2）符号表
s
3
0
t
5
3
u
7
8
…
堆
0
1
2
3
4
5
6
7
8
9
10
11
a
b
c
x
a
b
c
y
z
x
a
b
c
y
z
↑
free
（3）最坏情况下的时间复杂度为O（m*n），其中m为串s的长度，n为串t的长度
（4）三维数组arr[6][2][3]的每个元素的长度为4个字节，该数组要占6*2*3*4=144个字节，若数组以列优先的顺序存储，设第一个元素的首地址是4000，则元素arr[5][0][2]的存储地址是4029。
（5）
①
②（（0,0,1）,（0,3,2）,（1,1,3）,（2,3,5）,（3,0,2）,（3,2,5））
（6）
行优先：
a0,0,0,0a0,0,0,1a0,0,0,2a0,0,1,0a0,0,1,1a0,0,1,2
a0,1,0,0a0,1,0,1a0,1,0,2a0,1,1,0a0,1,1,1a0,1,1,2
a0,2,0,0a0,2,0,1a0,2,0,2a0,2,1,0a0,2,1,1a0,2,1,2
a1,0,0,0a1,0,0,1a1,0,0,2a1,0,1,0a1,0,1,1a1,0,1,2
a1,1,0,0a1,1,0,1a1,1,0,2a1,1,1,0a1,1,1,1a1,1,1,2
a1,2,0,0a1,2,0,1a1,2,0,2a1,2,1,0a1,2,1,1a1,2,1,2
列优先：
a0,0,0,0a1,0,0,0a0,1,0,0a1,1,0,0a0,2,0,0a1,2,0,0
a0,0,1,0a1,0,1,0a0,1,1,0a1,1,1,0a0,2,1,0a1,2,1,0
a0,0,0,1a1,0,0,1a0,1,0,1a1,1,0,1a0,2,0,1a1,2,0,1
a0,0,1,1a1,0,1,1a0,1,1,1a1,1,1,1a0,2,1,1a1,2,1,1
a0,0,0,2a1,0,0,2a0,1.0,2a1,1,0,2a0,2,0,2a1,2,0,2
a0,0,1,2a1,0,1,2a0,1,1,2a1,1,1,2a0,2,1,2a1,2,1,2
（7）稀疏矩阵压缩存储后会失去随机存取的功能，因为稀疏矩阵不能根据元素在矩阵中的位置求得在其在三元组顺序表中的位置，而特殊矩阵则可以。
（8）当3t时，三元组的表示才有意义。
（9）
①i=j或i+j=n+1
②
4、算法设计题
（1）
voidAssign（BlockLink*s,chart[]）
/*将存放在字符数组t中常量赋给s*/
{ss=s;
for（i=0;t[0]!
=’\0’;i++）
{if（i%NodeNum==
升级会员 