数据结构作业答案.docx
《数据结构作业答案.docx》由会员分享，可在线阅读，更多相关《数据结构作业答案.docx（81页珍藏版）》请在冰点文库上搜索。
数据结构作业答案
第一章绪论
课堂习题
1、试写一算法,自大到小依次输出顺序读入的三个整数X,Y和Z的值。
【解答】
一解：
IFXY;
IFY>ZY<->Z;
IFXY;
此算法最坏情况下比较3次,移动（即赋值9次）
二解:
IFXIFYIFX>TEMPY=TEMP
ELSE
{Y=X;X=TEMP;}
此算法最坏情况下比较3次,移动7次
三解:
IFX{IFY>ZX<->Y
ELSEX<->Z;}
ELSE
{IFXZ;}
IFY此算法最坏情况下比较3次,移动6次
2、抽象数据类型三元组的定义、表示和实现
【解答】抽象数据类型三元组的定义已经给出（见教材12页），要求设计实现三元组基本操作的演示程序。
#include
#include
typedefintElemType;
typedefElemType*Triplet;
typedefintStatus;
#defineOK1
#defineERROR0
#defineOVERFLOW-2
StatusInitTriplet（Triplet*T）
{
ElemTypev1,v2,v3;
*T=（ElemType*）malloc（3*sizeof（ElemType））;
if（*T==0）return（OVERFLOW）;
scanf（"%d,%d,%d",&v1,&v2,&v3）;
（*T）[0]=v1;（*T）[1]=v2;（*T）[2]=v3;
}
StatusDestroyTriplet（Triplet*T）
{
free（*T）;
*T=NULL;
}
StatusGet（TripletT,inti,ElemType*e）
{
if（i<1||i>3）returnERROR;
*e=T[i-1];returnOK;
}
StatusPut（TripletT,inti,ElemTypee）
{
if（i<1||i>3）returnERROR;
（*T）[i-1]=e;returnOK;
}
StatusIsAscending（TripletT）
{
return（（T[0]}
StatusIsDescending（TripletT）
{
return（（T[0]>T[1]）&&（T[1]>T[2]））;
}
StatusMax（TripletT,ElemType*e）
{
*e=（T[0]>=T[1]?
（（T[0]>=T[2]）?
T[0]:
T[2]）:
（（T[1]>=T[2]）?
T[1]:
T[2]）;
returnOK;
}
StatusMin（TripletT,ElemType*e）
{
*e=（T[0]<=T[1]?
（（T[0]<=T[2]）?
T[0]:
T[2]）:
（（T[1]<=T[2]）?
T[1]:
T[2]）;
returnOK;
}
voidmain（）
{
TripletT;
ElemTypee;
intselect,i;
printf（"请输入三个数，建立一个三元组：
\n"）;
if（InitTriplet（&T）==OVERFLOW）
printf（"存储空间分配失败，退出程序\n"）;
else
{
do
{
printf（"1：
取三元组第I个元素\n"）;
printf（"2：
修改三元组第I个元素\n"）;
printf（"3：
判断三元组元素是否递增\n"）;
printf（"4：
判断三元组元素是否递减\n"）;
printf（"5：
取三元组最大元\n"）;
printf（"6：
取三元组最小元\n"）;
printf（"0：
结束\n"）;
scanf（"&d",&select）;
switch（select）
{
case1:
printf（"\ni="）;
scanf（"%d",&i）;
if（Get（T,i,&e）==ERROR）printf（"I值输入不合法\n"）;
elseprintf（"第I个元素的值为%d\n",e）;break;
case2:
printf（"\ni="）;
scanf（"%d",&i）;
printf（"\ne="）;
scanf（"%d",&e）;
if（Put（T,i,e）==ERROR）pprintf（"I值输入不合法\n"）;
elseprintf（"新三元组为：
%4d%4d%4d\n",T[0],T[1],T[2]）;
break;
case3:
if（IsAscending（T）==1）printf（"三元组递增有序\n"）;
elseprintf（"三元组非递增\n"）;break;
case4:
if（IsDescending（T）==1）printf（"三元组递减有序\n"）;
elseprintf（"三元组非递减\n"）;break;
case5:
Max（T,&e）;
printf（"三元组的最大元为%d\n",e）;break;
case6:
Min（T,&e）;
printf（"三元组的最小元为%d\n",e）;break;
case0:
printf（"操作结束\n"）;break;
default:
printf（"选择出错，请输入数字（0-6）\n"）;
}
}while（select!
=0）;
DestroyTriplet（&T）;
}
}
课后练习
一、问答题
1. 什么是数据结构？
2. 叙述四类基本数据结构的名称与含义。
3. 叙述算法的定义与特性。
4. 叙述算法的时间复杂度。
5. 叙述数据类型的概念。
6. 叙述线性结构与非线性结构的差别。
7. 叙述面向对象程序设计语言的特点。
8. 在面向对象程序设计中，类的作用是什么？
9. 叙述参数传递的主要方式及特点。
10. 叙述抽象数据类型的概念。
二、判断题（在各题后填写“√”或“×”）
1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。
（ ）
2. 算法就是程序。
（ ）
3. 在高级语言（如C或PASCAL）中，指针类型是原子类型。
（ ）
三、计算下列程序段中X=X+1的语句频度
for（i=1;i<=n;i++）
for（j=1;j<=i;j++）
for（k=1;k<=j;k++）
x=x+1;
【解答】x=x+1的语句频度为：
T（n）=1+（1+2）+（1+2+3）+……+（1+2+……+n）=n（n+1）（n+2）/6
四、试编写算法，求一元多项式Pn（x）=a0+a1x+a2x2+a3x3+…anxn的值Pn（x0），并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。
注意：
本题中的输入ai（i=0,1,…,n）,x和n，输出为Pn（x0）。
通常算法的输入和输出可采用下列两种方式之一：
（1）通过参数表中的参数显式传递。
（2）通过全局变量隐式传递。
试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出
【解答】
（1）通过参数表中的参数显式传递
优点：
当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。
缺点：
形参须与实参对应，且返回值数量有限。
（2）通过全局变量隐式传递
优点：
减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗
缺点：
函数通用性降低，移植性差
算法如下：
通过全局变量隐式传递参数
PolyValue（）
{inti,n;
floatx,a[],p;
printf（“\nn=”）;
scanf（“%f”,&n）;
printf（“\nx=”）;
scanf（“%f”,&x）;
for（i=0;iscanf（“%f”,&a[i]）;/*执行次数：
n次*/
p=a[0];
for（i=1;i<=n;i++）
{p=p+a[i]*x;/*执行次数：
n次*/
x=x*x;}
printf（“%f”,p）;
}
算法的时间复杂度：
T（n）=O（n）
通过参数表中的参数显式传递
floatPolyValue（floata[],floatx,intn）
{
floatp,s;
inti;
p=x;
s=a[0];
for（i=1;i<=n;i++）
{s=s+a[i]*p;/*执行次数:
n次*/
p=p*x;}
return（p）;
}
算法的时间复杂度：
T（n）=O（n）
五、假设有A、B、C、D、E五个高校进行田径对抗赛，各院校的单项成绩已存入计算机并构成一张表，表中每一行的形式为
项目名称
性别
校名
成绩
得分
编写算法，处理上述表格，以统计各院校的男女总分和团体总分，并输出。
第二章线性表
课堂习题
1、在单链表、双链表和单循环链表中，若仅知道指针P指向某结点，不知道头指针，能否将结点*P从相应的链表中删去？
若可以，其时间复杂度各为多少？
【解答】
在单链表中，由于无法找到结点*P的直接前驱的位置，所以无法删除该结点；在双链表中，结点*P的前驱位置是P->PRIOR；因此可直接将*P删除掉，其时间复杂度为O
（1）;
在单循环链表中,可从P结点依次扫描到其前驱结点,故也能删除掉该结点,其时间复杂度为O（N）。
2、下述算法的功能是什么？
LINKLISTDEMO（LINKLISTL）其中L为带头指针的单链表
{LISTNODE*Q，*P；
IF（L&&L->NEXT）
{
Q=L;L=L->NEXT;P=L;
WHILE（P->NEXT）P=P->NEXT;
P->NEXT=Q;Q->NEXT=NULL;
}
RETURNL
}
【解答】
当L是空链表或仅有一个结点时，L不变；
当L有两个或两个以上结点时，将第一个结点移至链表最后，关指针指向原第二个结点。
3、试分别用顺序表和单链表作为存储结构，实现线性表的就地逆置。
【解答】
顺序表VOIDREVERSELIST（SQLIST*L）
{DATATYPET;
INTI,J;
FOR（I=0;I<=L->LENGTH/2-1;I++）
{J=L->LENGTH-1-I;
T=L->ELEM[I];
L->ELEM[I]=L->ELEM[J];
L->ELEM[J]=T;
}
}
单链表VOIDREVERSELIST（LINKLIST*L）
{LNODE*P,*Q;
P=L->NEXT;
L->NEXT=NULL;
WHILE（P）
{Q=P->NEXT;
P->NEXT=L->NEXT;
L->NEXT=P;
P=Q;
}
}
4、设顺序表L是一个递增有序表，试写一算法将X插入到L中，并使得L仍是一个有序表。
【解答】
VOIDINSERTSOR（SQLIST*L,DATATYPEX）
{INTI;
IF（L->LENGTH>=LISTSIZE）RETURNERROR;
I=L->LENGTH-1;
WHILE（I>=0&&L->DATA[I]>X）
{L->ELEM[I+1]=L->ELEM[I];I--;}
L->ELEM[I+1]=X;
L->LENGTH++;
}
5、已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为M和N，试写一算法将两个链表连接在一起，请分析算法的时间复杂度。
【解答】
LINKLISTCONNECT（LINKLISTL1,LINKLISTL2,INTM,INTN）
{LISTNODE*P,*Q;
INTK;
IF（M>N）
{K=N;P=L2;Q=L1;}
ELSE
{K=M;P=L2;Q=L2;}
WHILE（K>0）
{P=P->NEXT;K--;}
P->NEXT=Q->NEXT;
FREE（Q）;
IF（M>N）RETURNL2;
ELSERETURNL1;
}
6、写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值各不相同。
【解答】
VOIDDELSAMENODE（LINKLISTL）
{LISTNODE*P,*Q,*R;
P=L->NEXT;
WHILE（P）
{Q=P;
R=Q->NEXT;
WHILE（R）
{IFR->DATA==P->DATA
{Q->NEXT=R->NEXT;R=Q->NEXT;}
ELSE
{Q=R;R=R->NEXT;}
}
P=P->NEXT;
}
}
7、假设在长度大于1的单循环链表中，既无头结点也无头指针，S为指向表中某个结点的指针，试编写算法删除结点*S的直接前驱结点。
【解答】
VOIDDELETEFNODE（LISTNODE*S）
{LISTNODE*P,*Q;
P=S;
WHILE（P->NEXT!
=S）
{Q=P;P=P->NEXT;}
Q->NEXT=S;
FREE（P）;
}
8、狐狸逮兔子问题
围绕着山顶有10个圆形排列的洞,狐狸要吃兔子,兔子说:
"可以,但必须找到我,我就藏身于这10个洞中,你先到1号洞找,第二次隔1个洞,（即3号洞）找,第三次就隔2个洞（即6号洞找）,以后如此类推,次数不限."但狐狸从早到晚进进出出了1000次,仍没有找到兔子,问兔子究竟藏在哪个洞里?
【解答】
#include"stdio.h"
#include"stdlib.h"
#defineOK1
#defineOVERFLOW-2
#defineLIST_INIT_SIZE10
typedefintstatus;
typedefintelemtype;
typedefstruct
{elemtype*elem;
intlength;
intlistsize;
}sqlist;
statusinitlist_sq（sqlist*l）
{
l->elem=（elemtype*）malloc（LIST_INIT_SIZE*sizeof（elemtype））;
if（!
（l->elem））returnOVERFLOW;
l->length=0;
l->listsize=LIST_INIT_SIZE;
returnOK;
}
statusrabbit（sqlist*l）
{
inti,current=0;
for（i=0;il->elem[i]=1;
l->elem[0]=0;
for（i=2;i<=1000;i++）
{
current=（current+i）%LIST_INIT_SIZE;
l->elem[current]=0;
}
printf（"theholeare:
"）;
for（i=0;iif（l->elem[i]==1）printf（"%d",i+1）;
returnOK;
}
main（）
{
sqlistl;
initlist_sq（&l）;
rabbit（&l）;
getch（）;
}
9、约瑟夫问题
设有N个人围坐在圆桌周围,现从某个位置M（1<=M<=N）上的人开始报数,报数到K的人就站出来,下一个人,即原来的第K+1个位置上的人,又从1开始报数,再报到K的人站出来,依此重复下去,直到全部的人都站出来为止.试设计一个程序求出出列的序列.
【解答】
#include"stdio.h"
#include"stdlib.h"
#defineNULL0
#defineOK1
#defineERROR0
#defineoverflow-2
typedefintstatus;
typedefintelemtype;
typedefstructcnode
{
elemtypedata;
structcnode*next;
}cnode;
cnode*joseph;
statuscreate_clist（cnode*clist,intn）
{
cnode*p,*q;
inti;
clist=null;
for（i=n;i>=1;i--）
{
p=（cnode*）malloc（sizeof（cnode））;
if（p==null）returnOVERFLOW;
p->data=i;
p->next=clist;
clist=p;
if（i==n）
q=p;
}
q->next=clist;
joseph=clist;
returnok;
}
statusjoseph（cnode*clist,intm,intn,intk）
{
inti;
cnode*p,*q;
if（m>n）returnERROR;
if（!
create_clist（clist,n））returnERROR;
p=joseph;
for（i=1;ip=p->next;
while（p）
{for（i=1;ip=p->next;
q=p->next;
printf（"%d",q->data）;
if（p->next==p）
p=null;
else
{p->next=q->next;
p=p->next;
free（q）;
}
}
clist=null;
}
main（）
{
intm,n,k,i;
cnode*clist;
clist=null;
printf（"\npleaseinputthenumberofpeople:
"）;
scanf（"%d",&n）;
printf（"\npleaseinputthepositionstart:
"）;
scanf（"%d",&m）;
printf（"\npleaseinputtheN0.out:
"）;
scanf（"%d",&k）;
create_clist（clist,n）;
printf（"\nTHEOUTLINE:
\n"）;
joseph（clist,m,n,k）;
getch（）;
}
课后练习
一、术语理解
描述以下三个概念的区别：
头指针，头结点，首元素结点。
二、填空题
（1）在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素个数与 有关。
（2）在顺序表中，逻辑上相邻的元素，其物理位置 相邻。
在单链表中，逻辑上相邻的元素，其物理位置 相邻。
（3）在带头结点的非空单链表中，头结点的存储位置由 指示，首元素结点的存储位置由 指示，除首元素结点外，其它任一元素结点的存储位置由 指示。
三、已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。
按要求从下列语句中选择合适的语句序列。
a.在P结点后插入S结点的语句序列是：
。
b.在P结点前插入S结点的语句序列是：
。
c.在表首插入S结点的语句序列是：
。
d.在表尾插入S结点的语句序列是：
。
供选择的语句有：
（1）P->next=S;
（2）P->next=P->next->next;
（3）P->next=S->next;
（4）S->next=P->next;
（5）S->next=L;
（6）S->next=NULL;
（7）Q=P;
（8）while（P->next!
=Q）P=P->next;
（9）while（P->next!
=NULL）P=P->next;
（10）P=Q;
（11）P=L;
（12）L=S;
（13）L=P;
四、设线性表存于a（1:
arrsize）的前elenum个分量中且递增有序。
试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。
五、写一算法，从顺序表中删除自第i个元素开始的k个元素。
六、已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。
试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：
mink和maxk是给定的两个参变量，它们的值为任意的整数）。
七、试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1,a2...,an）逆置为（an,an-1,...,a1）。
（1） 以一维数组作存储结构，设线性表存于a（1:
arrsize）的前elenum个分量中。
（2） 以单链表作存储结构。
八、假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C。
九、已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
十、设线性表A=（a1,a2,…,am），B=（b1,b2,…,bn），试写一个按下列规则合并A、B为线性表C的算法，使得：
C=（a1,b1,…,am,bm,bm+1,…,bn） 当m≤
升级会员 