数据结构课后习题部分参考答案

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐数据结构课后习题部分参考答案数据结构课后习题部分参考答案

第一章

一、挑选题

1．C2．C3．A4．D5．B

二、推断题

1．╳2．╳3．╳4．╳5．∨

三、简答题

1．常见规律结构：

集合结构，数据元素之间的关系仅仅是属于同一个集合。

线性结构，除第一个元素惟独一个直接后继、最后一个元素惟独一个直接前驱，其余元素有且惟独唯一一个直接前驱、有且惟独唯一一个直接后继，数据元素之间存在一对一的关系。

树形结构，树中惟独唯一一个根元素，除根元素之外，其余元素惟独一个直接前驱，但可以有多个直接后继元素，数据元素之间存在一对多的关系。

图形结构，元素之间关系随意，数据元素之间存在多对多的关系。

常用的存储结构：

挨次存储，把规律上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为挨次存储结构。通常用数组实现。

链式存储，对规律上相邻的元素不要求其物理位置相邻，元素间的规律关系通过附加的指针字段来表示，由此得到的存储表示称为链式存储结构。通常用指针来实现。

除上述两种办法外，有时为了查找便利还采纳索引存储办法和散列存储办法。

索引存储：在存储结点信息的同时，还建立附加的索引表来标识结点的地址。

散列存储：按照元素的关键码确定元素存储位置的存储方式。

2．算法与程序的区分：

程序不一定满足有穷性(如操作系统)；

程序中的指令必需是机器可执行的，算法中的指令则无此限制；

算法代表了对问题的解，程序则是算法在计算机上的特定的实现(一个算法若用程序设计语言来描述，它才是一个程序);

数据结构+算法=程序。

3．例如有一张同学成果表，记录了一个班的同学各门课的成果。按同学的姓名为一行记成的表。这个表就是一个数据结构。每个记录就是一个结点，对于囫囵表来说，惟独一个开头结点和一个终端结点，其他的结点则各有一个也惟独一个直接前趋和直接后继。这几个关系就确定了这个表的规律结构——线形结构。

那么我们怎样把这个表中的数据存储到里呢?用高级语言如何表示各结点之间的关系呢?是用一片延续的内存单元来存放这些记录（挨次存储）还是随机存放各结点数据再用指针举行链接（链式存储）呢?这就是存储结构的问题，我们都是从高级语言的层次来研究这个问题的。

最后，我们有了这个表，绝对要用它，那么就是要对这张表中的记录举行查询，修改，删除等操作，对这个表可以举行哪些操作以及如何实现这些操作就是数据的运算问题了。4．例如栈和队列，两个数据结构的规律结构和存储方式彻低相同，只是对于运算（如插入、删除）的定义不同，两个结构具有显著不同的特性。

5．语句频度

（1）n-1（2）1（3）n(n+1)/2（4）n/2-1（5）100

6．时光复杂度

（1）O(log3n)（2）O(n2)（3）O(n2)

7．算法思想：

P(x，n)=(…((anx+an-1)x+an-2)x+…+a1)x+a0

语句：

y=0;

for(i=n;i>=0;i--)

y=y*x+ai;

函数：

voidp()

{floatx,y;

intn,i,a;

scanf("%f",

scanf("%d",

y=0;

for(i=n;i>=0;i--)

{scanf("%d",

y=y*x+a;}

printf("x=%4.2f,y=%6.4f",x,y);

}

其次章

一、挑选题

1．A2．A3．D4．C5．D

6．B7．C8．B9．A10．D

11．B12．D

二、推断题

1．╳2．∨3．╳4．∨5．╳

6．∨7．╳8．∨9．∨10．╳

11．╳12．╳

三、算法设计题

1．

第一种办法（从后往前比较）：

因已知挨次表L是递增有序表，所以只要从挨次表终端结点（设为i位置元素）开头向前寻觅到第一个小于或等于x的元素位置i后，插入该位置后面即可。

在寻觅过程中，因为大于x的元素都应放在x之后，所以可边寻觅，边后移元素，当找到第一个小于或等于x的元素位置i时，插入x的位置i+1也空出来了。

算法如下：

voidInsertIncreaseList1(seqlist*L,datatypex)

{inti;

if(L->elemnum==maxsize)printf("overflow");//L->elemnum中存放当前挨次表中的元素个数

for(i=L->elemnum-1;i>=0i--)L->data[i+1]=L->data[i];//从后往前比较并移动元素

L->data[i+1]=x;

L->elemnum++;

}

其次种办法（先前往后比较）：

voidInsertIncreaseList2(seqlist*L,datatypex)

{inti,j;

if(L->elemnum==maxsize)printf("overflow");

i=0;

while((ielemnum-1)//先前往后比较寻觅插入位置

for(j=L->elemnum-1;j>=i;j--)L->data[j+1]=L->data[j];//腾位置

L->data[i]=x;//插入

L->elemnum++;

}

2（思路同算法2-16）

6（同1类似，最好也做一下。1是挨次存储，6是链式存储。做完同1比较一下）

7（看算法2-17,尾插实现）

第三章

一、挑选题

1．C2．B3．D4．B5．B

6．C7．B8．D9．C10．C

二、推断题

1．∨2．∨3．∨4．╳5．╳

三、简答题

1循环队列的优点是：它可以克服挨次队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"通常有两种办法：

（1）另设一个变量num记录当前队列中的元素个数,当num==0时队空，num==maxsize时队满。

（2）少用一个存储单元(即少存一个元素),队空条件为front==rear，队满条件为(rear+1)%maxsize==front。

2．栈的特点是先进后出，队列的特点是先进先出。

先进后出用栈；先进先出用队列。

3．一个直接调用自己或通过一系列调用间接调用自己的过程称为递归。

递归程序结构清楚，可读性强，而且简单用数学归纳法来证实程序的正确性。

递归程序运行效率低，不论是耗费的计算时光还是占用的存储空间都比非递归程序要多。4．1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321（十四种可能）

四、算法设计题

1．思想：将一半字符入栈)

算法为：

//以下为挨次栈的存储结构定义

#defineStackSize100//假定预分配的栈空间最多为100个元素

typedefcharDataType;//假定栈元素的数据类型为字符

typedefstruct{

DataTypedata[StackSize];

inttop;

}SeqStack;

intIsHuiwen(char*t)

{//推断t字符向量是否为回文，若是，返回1，否则返回0

SeqStacks;

inti,len;

chartemp;

InitStack(

len=strlen(t);//求向量长度

for(i=0;i<len/2;i++)//将一半字符入栈

Push(

if（len%2==1）i++；//处理向量长度为奇数的状况

while(!EmptyStack(

if(temp!=S[i])return0;//不等则返回0

elsei++;

}

return1;//比较完毕均相等则返回1

}

2．我们通常用一个有三个重量（存储元素的空间、front、rear）的结构体变量实现循环队列，此题即要求用一个数组和两个容易变量（而不是一个结构体变量）实现循环队列的入队和出队。

5．思想：对表达式举行扫描，凡碰到'('就进栈，遇')'就退掉栈顶的'('，表达式被扫描完毕，栈应为空。

算法如下：

intPairBracket(char*SR)

{//检查表达式ST中括号是否配对

inti;

SeqStackS;//定义一个栈

InitStack(

for(i=0;i<strlen(SR);i++)

{

if(S[i]=='(')Push(//遇'('时进栈

if(S[i]==')')//遇')'

if(!StackEmpty(S))//栈不为空时，将栈顶元素出栈

Pop(

elsereturn0;//不匹配，返回0

}

ifEmptyStack(//匹配，返回1

elsereturn0;//不匹配，返回0

}

第五章

一、挑选题

1．C2．C3.B4．B5．B

6．C7．B8．D9．A10．D

11．D12．C13．B14．D15．B

二、推断题

1．╳2．∨3．╳4．╳5．∨

6．╳7．╳8．╳9．∨10．╳

11.╳12.∨13．╳14．╳15．╳

16．╳17．∨18．╳19．╳20．∨

三、简答题

1．一棵度为2的树与一棵二叉树的区分在于:度为2的