数据结构C语言版复习题答案.docx
《数据结构C语言版复习题答案.docx》由会员分享，可在线阅读，更多相关《数据结构C语言版复习题答案.docx（22页珍藏版）》请在冰点文库上搜索。
数据结构C语言版复习题答案
习题1
一、选择题
1.B2.D3.D4.A5.C6.A7.B8.D9.C10.A
二、简答题
1.答：
数据的逻辑结构通常有四种，即集合、线性结构、树形结构和图状结构。
存储结构主要有顺序存储结构和链式存储结构。
2.答：
比如一分通讯录，记录了相关人员的，将其按一人占一行构成表，这个表就是一个数据结构。
每一行是一个记录，对于整个表来说，只有一个开始结点和一个终端结点，其它结点也只有一个前驱和一个后继。
这几个关系就确定了表的逻辑结构。
3.答：
算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。
算法具有有穷性、确定性、可行性、输入和输出5个特性。
4.答：
它是一种树型结构，可以用二元组描述为：
A={K,R}
K={a,b,c,d,e,f,g,h,i}
R={（a,b）,（a,c）,（c,d）,（c,e）,（d,f）,（d,g）,（e,h）,（f,i）}
5.答：
（1）A对应的逻辑图形如下图左，它是一种线性结构。
（2）B对应的逻辑图形如上图右所示，它是一种树型结构。
（3）C对应的逻辑图形如下图所示，它是一种图型结构。
三、计算题
解：
（1）O（n）；
（2）O（n）；（3）O（n1/2）；（4）略。
习题2
一、选择题
1.A2.B3.B4.D5.A6.C7.B8.A9.C10.C
二、简答题
1.答：
线性表是具有n个数据元素的一个有限序列。
线性表的特点是：
数据元素之间是一对一的关系。
除第一个元素外，每个元素有且只有一个直接前驱；除最后一个元素外，每个元素有且只有一个直接后继。
2.答：
头指针是链表的一个标识，它用来指向带头结点的链表中的头结点。
头结点是在链表的第一个数据元素之前附加的一个结点，它的作用是使对第一个结点的操作和其它结点一致，表空与非空时处理一致，不需要特殊处理，简化了操作。
3.答：
顺序表的特点是逻辑位置相邻的数据元素其物理位置也相邻，因此可以进行随机存储，是一种随机存储结构。
其插入和删除操作的时间复杂度均为O（n）。
链表中的数据元素使用一组任意的存储单元存储，不要求逻辑位置相邻的数据元素物理位置也相邻，而是采用附加的指针表示元素之间的逻辑关系。
链表的插入和删除结点均不需要移动其他结点，但是，其查找运算必须从头指针开始顺序查找，其时间复杂度为O（n）。
4.答：
算法如下
voidConvert（SqList&L）{
inti,j,temp;
j=L.length-1;
i=0;
while（itemp=L.elem[i];
L.elem[i]=L.elem[j];
L.elem[j]=temp;
i++;
j--;
}
}
5.答：
算法如下
voidDelete（SqList&La,SqListLb）{
inti,j,k;
i=0;j=0;
while（iif（La.elem[i]elseif（La.elem[i]>Lb.elem[j]）j++;
elseListDelete_Sq（La,i+1,k）;
}
}
6.答：
算法如下
voidInvertList（LinkList&L）{
LinkListp,q,r;
p=L->next;
q=p->next;
p->next=NULL;
while（q!
=NULL）{
r=q->next;
q->next=p;
p=q;
q=r;
}
L->next=p;
}
7.答：
算法如下
voidMergeOrder（LinkListLa,LinkListLb）{
LinkListpa,pb,Lc,pc;
pa=La->next;
pb=Lb->next;
Lc=pc=La;
while（pa&&pb）{
if（pa->data<=pb->data）{
pc->next=pa;
pc=pa;
pa=pa->next;
}else{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
if（!
pa）pc->next=pb;
elsepc->next=pa;
}
8.答略。
9.答：
算法如下
intLength（LinkListL）{
inti=0;
LinkListp;
p=L->next;
while（p）{
p=p->next;
i++;
}
returni;
}
习题3
一、选择题
1.C2.B3.A4.D5.B6.A7.C8.A9.B10.B
二、简答题
1.答：
栈是限定在表的一端进行插入和删除操作的线性表。
队列是只允许在表的一端进行插入，而在另一端进行删除元素的线性表。
栈的操作是按照后进先出原则进行的，因此又称作后进先出的线性表。
队列的操作是按照先进先出原则进行的，因此又称作先进先出的线性表。
2.答：
当front¹0，rear=M时，再有元素入队发生溢出，称之为“假溢出”，存储空间还有剩余。
为了改进这种状况，可以将顺序队列想象为一个首尾相接的环状空间，称之为循环队列。
3.答：
（1）相应入队列操作
StatusEnQueue_L（LinkQueue&Q,ElemTypee）{
p=（QLink）malloc（sizeof（QNode））;
p->data=e;p->next=Q->next;
Q->next=p;
Q=p;
returnOK;
}
（2）相应出队列的操作
StatusDeQueue_L（LinkQueue&Q,ElemType&e）{
if（Q->next==Q）returnERROR;
p=Q.next->next;
e=p->data;
Q->next->next=p->next;
free（p）;
returnOK;
}
4.答：
intpush（ElemTypex,inti）{
if（top1==top2-1）return0;
elseif（i==1）{
top1++;
C[top1]=x;
}else{
top2--;
C[top2]=x;
}
return1;
}
intpop（inti,ElemType&e）{
if（i=1）{
if（top1==0）return0;
else{
x=C[top1];
top1--;
}
}else{
if（top2==n+1）
return0;
else{
x=C[top2];
top2++;
}
}
return1;
}
5.答：
算法如下
voidPrint（intn）{
inti;
if（n==0）
return;
for（i=1;i<=n;i++）
printf（"%3d",n）;
printf（"\n"）;
Print（n-1）;
}
6．答：
算法如下
ElemTypeBottom（StackS）{
ElemTypex,y;
StackT;
InitStack（T）;
while（!
StackEmpty（S））{
pop（S,x）;
push（T,x）;
}
while（!
StackEmpty（T））{
pop（T,y）;
push（S,y）;
}
returnx;
}
习题4
一、选择题
1.B2.D3.B4.D5.A
二、简答题
1.答：
长度为零的串称为空串，记作""。
空格也是串的字符集合中的一个元素，由一个或多个空格组成的串称为空格串。
例如""，其长度为串中空格的个数。
2.答：
虽然串是由字符组成的，但串和字符是两个不同的概念。
串是长度不确定的字符序列，而字符只是一个字符。
即使是长度为1的串也与字符不同。
例如，串"a"和字符'a'就是两个不同的概念，因为在存储时串的结尾通常加上串结束标志'\0'。
3.答：
在串的顺序存储结构是用一维数组存放串中的字符。
一种方法是用静态存分配的方法定义的数组，数组元素的个数是在编译时确定的，在运行时是不可改变的，称之为静态顺序存储。
另一种方法是用动态存分配的方法定义的数组，数组元素的个数是在程序运行时用户申请确定的，称之为动态顺序存储。
4.答：
StatusStrDelete（String&S,inti,intj）{
intlen;
len=j-i+1;
if（i<1||i>S[0]||j>S[0]）//非法情况的处理
returnERROR;
S[pos..S[0]-len]=S[pos+len..S[0]];//将S中从下标从pos+len开始的元素前移len位
S[0]=S[0]-len;//串长的处理
returnOK;
}
5.答：
StatusSubString（StringS1,StringS2）{
inti,j,k,flag=0;
i=1;
while（iflag）{
j=1;
if（S1[i]==S2[j]）{
k=i+1;j++;
while（S1[k]==S2[j]）{
k++;j++;
}
if（j==s2[0]）flag=1;
elsei++;
}
elsei++;
}
returnflag;
}
6.答：
StatusStringCmp（StringS2,StringS1）{
intk;
if（S2.length!
=S1.length）returnERROR;
for（k=0;kif（S2.ch[k]!
=S1.ch[k]）
returnERROR;
returnOK;
}
习题5
一、选择题
1.D2.B3.A4.B5.D6.D7.B8.D9.B10.B
二、简答题
1.答：
所谓行序优先存储，其基本思想为：
从第1行的元素开始按顺序存储，第1行元素存储完成后，再按顺序存储第2行的元素，然后依次存储第3行，……直到最后一行的所有元素存储完毕为止。
而列序优先存储即为：
依次按顺序存储第1列，第2列，……直到最后一列的所有元素存储完毕为止。
2.答：
我们把相同的元素或零元素在矩阵中的分布有一定的规律的称为特殊矩阵。
压缩存储的原则是：
对多个值相同的元素只存储一次，对零元素甚至不分配存储空间。
3.答：
矩阵中非零元素的个数远远小于矩阵元素的总数，这样的矩阵称为稀疏矩阵。
稀疏存储的原则是只存储非零元。
三、计算题
（1）228
（2）1282（3）1072（4）1276
四、设计题
1．voidproc1（matrixA）/*第
（1）题解*/
{
ints=0,i,j;
for（i=0;is=s+A[i][1];
for（i=0;is=s+A[i][n];
for（j=0;js=s+A[1][j];
for（j=0;js=s+A[m][j];
s=s-A[0][0]-A[0][n-1]-A[m-1][0]-A[m-1][n-1];/*减去4个角的重复元素值*/
printf（"s=%d\n",s）;
}
voidproc2（matrixA）/*第
（2）题解*/
{
ints=0,i,j;
i=0;
while（i{
j=0;
while（j{
s=s+A[i][j];
j=j+2;/*跳过一列*/
}
i=i+2;/*跳过一行*/
}
printf（"s=%d\n",s）;
}
voidproc3（matrixA）/*第
（2）题解*/
{
inti,s;
if（m!
=n）printf（"m!
=n"）;
else
{
s=0;
for（i=0;is=s+A[i][i];/*求第一列对角线之和*/
for（i=0;is=s+A[n-i-1][i];/*累加第二条对角线之和*/
printf（"s=%d\n",s）;
}
}
2．voidmmult（）{
matrixA;
inti,s;
for（i=0;i<4;i++）
for（j=0;j<4;j++）
scanf（"%d",A[i][j];
s=1;
for（i=0;i<4;i++）
s=s*A[i][i];
for（i=0;i<4;i++）
s=s*A[3-i][i];
printf（"两条对角线元素之积：
%d\n",s）;
}
习题6
一、选择题
1.C2.B3.A4.A5.B6.B7.D8.C9.A10.D
二、设计题
1．答案略。
2.解：
给定二叉树的先序序列和中序序列可以重构出该二叉树；给定二叉树的先序序列和后序序列则不能构造出该二叉树。
反例为：
先序序列ab，后序序列ba可对应两棵二叉树。
3.解：
（1）mk-1
（2）（mh-1）/（m-1）
（3）i=1时,该结点为根,无双亲结点;否则其双亲结点的编号为（i+m-2）/m
（4）编号为i的结点的第j个孩子结点（若有）的编号为i*m+（j-（m-1））
4.解：
5.解：
voidRelease（BiTreeT）{
if（T!
=NULL）{
Release（T->lchild）;
Release（T->rchild）;
free（T）;
}
}
6.解：
intDepth（BiTreeT）{
if（!
T）return0;//如果T为空，则其深度为0
else{//若T不空返回其子树中深度较大值加1
if（Depth（T->lchild）>=Depth（T->rchild））
returnDepth（T->lchild）+1;
elsereturnDepth（T->rchild）+1;
}
}
7.解：
voidLevel（BiTreeb,BiTreep,int*h,intlh）{
if（b==NULL）*h=0;
elseif（p==b）*h=lh;
else{
Level（p,b->lchild,h,lh+1）;
if（*h==-1）
Level（p,b->rchild,h,lh+1）;
}
}
习题7
一、选择题
1.C2.D3.A4.B5.B6.D7.A8.D9.C10.C11.D12.C
二、简答题
1.对于无向图，如果在深度优先遍历中遇到回边，则必定存在环。
对于有向图，如果从有向图的某个顶点v出发的遍历，在DFS（v）结束之前出现了一条从顶点u指向v的回边，则此有向图必定存在环。
因为u在深度优先生成树上是v的子树，即存在u到v的路径，现在又出现一条从u指向v的弧，则它们必然构成一条回路。
2.用邻接矩阵表示图时，矩阵元素的个数与顶点个数无关；但和边数有关。
三、设计题
1．解：
图（a）和图（b）的入度和出度为：
2.解：
（1）按普里姆算法求得的最小生成树：
（2）按克鲁斯卡尔算法求得的最小生成树
3.解：
4.解：
intvisited[MAXSIZE];
intExist_Path_DFS（GraphG,inti,intj）{
intk;
ArcNode*p;
if（i==j）return1;
else{
visted[i]=1;
for（p=G.vertices[i].firstarc;p;p=p->nextarc）{
k=p->adjvex;
if（!
visited[k]&&Exist_Path_DFS（k,j））
return1;
}
}
}
5．答案略。
6．答案略。
习题8
一、选择题
1.C3.D4.B5.A6.B7.D8.C9.C10.C
二、简答题
1.答：
静态查找是指只在数据元素集合中查找是否存在关键字等于某个给定关键字的数据元素。
动态查找除包括静态查找的要求外，还包括在查找过程中同时插入数据元素集合中不存在的数据元素，或者从数据元素集合中删除已存在的某个数据元素的要求。
2.答：
为了确定要查找的记录位置，与给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度ASL（AverageSearchLength）。
对于含有n个记录的表，平均查找长度的计算公式为：
其中，Pi为查找第i个元素的概率。
3.答：
与二叉排序树相比，B-树是一种平衡多叉排序树。
这里说的平衡是指所有叶结点都在同一层上，从而可避免出现像二叉排序树那样的分支退化现象；多叉是指多于二叉。
因此B-树是一种动态查找效率较二叉排序树更高的树。
三、设计题
1．解：
2.解：
3.解：
（1）m的取值为13
（2）
地址
0
1
2
3
4
5
6
7
8
9
10
11
12
key
80
75
88
90
102
113
126
47
35
23
11
51
探测次数
6
5
6
5
7
10
11
习题9
一、选择题
1.B2.D3.B4.C5.D6.C
二、设计题
1.解：
intQuickSort（SeqListR,intj,intlow,inthigh）{
//对R[low..high]快速排序
intpivotpos;//划分后的基准记录的位置
if（lowpivotpos=Partition（R,low,high）;//对R[low..high]做划分
if（pivotpos==j）returnr[j];
elseif（pivotpos>j）return（R,j,low,pivotpos-1）;
elsereturnquicksort（R,j,pivotpos+1,high）;
}
}//QuickSort
2.解：
voidselectsort（linklisthead）{
RecNode*p,*q,*s;
if（head->next）&&（head->next->next）{
p=head->next;//p指向当前已排好序最大元素的前趋
while（p->next）{
q=p->next;s=p;
while（q）{
if（q->keykey）s=q;
q=q->next;
}//endwhile
交换s结点和p结点的数据;
p=p->next;
}//endwhile
}//endif
}//endsort
3.解：
voidQuickSort（SeqListR,intlow,inthigh）{
//对R[low..high]快速排序
intpivotpos;
if（high-low<=2）{//若当前区元素少于3个
//则进行直接插入排序
InsertSort（R,low,high）;
}else{
pivotpos=midPartion（R,low,high）;
QuickSort（R,low,pivotpos-1）;
QuickSort（R,pivotpos+1，high）;
}
}//QuickSort
intmidPartion（SeqListR,inti,intj）{
//三者取中规则定基准
if（R[（i+j）/2].key>R[i].key）{
交换R[（i+j）/2]和R[i];
}
if（R[i].key>R[j].key）
{交换R[i]和R[j];}
if（R[i].key）{交换R[i]和R[（i+j）/2];}
returnPartion（R,i,j）;
}
4.解：
voidHeapDelete（seqlist*R,inti）{
intlarge;
intlow,high;
intj;
if（i>R->length） Error（"havenosuchnode"）;
R->data[i].key=R->data[R->length].key;
R->length--;
R->data[R->length].key=key;//插入新的记录
for（j=i/2;j>0;j--）{//建堆
low=j;high=R->length;
R->data[0].key=R->data[low].key;//R->data[low]是当前调整的结点
for（large=2*low;large<=high;large*=2）{
if（largedata[large].keydata[large+1].key）
large++;
if（R->data[0].keydata[large].key）{
R->data[low].key=R->data[large].key;
low=large;//令low指向新的调整结点
}elsebreak;
}
R->data[low].key=R->data[0].key;
}
}
～～～～THEEND～～～～
升级会员 