数据结构C语言版第三版清华大学出版社习题参考答案.docx
《数据结构C语言版第三版清华大学出版社习题参考答案.docx》由会员分享，可在线阅读，更多相关《数据结构C语言版第三版清华大学出版社习题参考答案.docx（45页珍藏版）》请在冰点文库上搜索。
数据结构C语言版第三版清华大学出版社习题参考答案
附录习题参考答案
习题1参考答案
1.1.选择题
（1）.A.
（2）.A.（3）.A.（4）.B.,C.（5）.A.（6）.A.（7）.C.（8）.A.（9）.B.（10.）A.
1.2.填空题
（1）.数据关系
（2）.逻辑结构物理结构
（3）.线性数据结构树型结构图结构
（4）.顺序存储链式存储索引存储散列表（Hash）存储
（5）.变量的取值范围操作的类别
（6）.数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系
（7）.关系网状结构树结构
（8）.空间复杂度和时间复杂度
（9）.空间时间
（10）.Ο（n）
1.3名词解释如下：
数据：
数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。
数据项：
数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。
数据元素：
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。
数据逻辑结构：
数据的逻辑结构就是指数据元素间的关系。
数据存储结构：
数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。
数据类型：
是指变量的取值范围和所能够进行的操作的总和。
算法：
是对特定问题求解步骤的一种描述，是指令的有限序列。
1.4语句的时间复杂度为：
（1）Ο（n2）
（2）Ο（n2）
（3）Ο（n2）
（4）Ο（n-1）
（5）Ο（n3）
1.5参考程序：
main（）
{
intX,Y,Z；
scanf（“%d,%d,%d”,&X,&Y,Z）；
if（X>=Y）
if（X>=Z）
if（Y>=Z）
{printf（“%d,%d,%d”,X,Y,Z）;}
else
{printf（“%d,%d,%d”,X,Z,Y）;}
else
{printf（“%d,%d,%d”,Z,X,Y）;}
else
if（Z>=X）
if（Y>=Z）
{printf（“%d,%d,%d”,Y,Z,X）;}
else
{printf（“%d,%d,%d”,Z,Y,X）;}
else
{printf（“%d,%d,%d”,Y,X,Z）;}
}
1.6参考程序：
main（）
{
inti,n;
floatx,a[],p;
printf（“\nn=”）;scanf（“%f”,&n）;
printf（“\nx=”）;scanf（“%f”,&x）;
for（i=0;i<=n;i++）
scanf（“%f”,&a[i]）;
p=a[0];
for（i=1;i<=n;i++）
{p=p+a[i]*x;
x=x*x;}
printf（“%f”,p）’
}
习题2参考答案
2.1选择题
（1）.C.
（2）.B.（3）.B.（4）.B.5.D.6.B.7.B.8.A.9.A.10.D.
2.2.填空题
（1）.有限序列
（2）.顺序存储和链式存储
（3）.Ｏ（n）O（n）
（4）.n-i+1n-i
（5）.链式
（6）.数据指针
（7）.前驱后继
（8）.Ο
（1）Ο（n）
（9）.s->next=p->next;p->next=s;
（10）.s->next
2.3.解题思路：
将顺序表A中的元素输入数组a，若数组a中元素个数为n,将下标为0，1,2,…,（n-1）/2的元素依次与下标为n,n-1,…,（n-1）/2的元素交换，输出数组a的元素。
参考程序如下：
main（）
{
inti,n;
floatt,a[];
printf（“\nn=”）;scanf（“%f”,&n）;
for（i=0;i<=n-1;i++）
scanf（“%f”,&a[i]）;
for（i=0;i<=（n-1）/2;i++）
{t=a[i];a[i]=a[n-1-i];a[n-1-i]=t;}
for（i=0;i<=n-1;i++）
printf（“%f”,a[i]）;
}
2.4算法与程序：
main（）
{
inti,n;
floatt,a[];
printf（“\nn=”）;scanf（“%f”,&n）;
for（i=0;iscanf（“%f”,&a[i]）;
for（i=1;iif（a[i]>a[0]）
{t=a[i];a[i]=a[0];a[0]=t;}
printf（“%f”,a[0]）;
for（i=2;iif（a[i]>a[1]）
{t=a[i];a[i]=a[1];a[1]=t;}
printf（“%f”,a[0]）;
}
2.5算法与程序：
main（）
{
inti,j,k,n;
floatx,t,a[];
printf（“\nx=”）;scanf（“%f”,&x）;
printf（“\nn=”）;scanf（“%f”,&n）;
for（i=0;iscanf（“%f”,&a[i]）;//输入线性表中的元素
for（i=0;i k=i;
for（j=i+1;j if（k<>j）{t=a[i];a[i]=a[k];a[k]=t;}
}
for（i=0;iif（a[i]>x）break;
for（k=n-1;k>=i;i--）//移动线性表中元素，然后插入元素x
a[k+1]=a[k];
a[i]=x;
for（i=0;i<=n;i++）//依次输出线性表中的元素
printf（“%f”,a[i]）;
}
2.6算法思路：
依次扫描A和B的元素，比较A、B当前的元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，最后将未扫描完顺序表中的余下部分赋给C即可。
C的容量要能够容纳A、B两个线性表相加的长度。
有序表的合并算法：
voidmerge（SeqListA,SeqListB,SeqList*C）
{inti，j，k；
i=0；j=0；k=0；
while（i<=A.last&&j<=B.last）
if（A.data[i]<=B.data[j]）
C->data[k++]=A.data[i++]；
else
C->data[k++]=B.data[j++]；
while（i<=A.last）
C->data[k++]=A.data[i++]；
while（j<=B.last）
C->data[k++]=B.data[j++]；
C->last=k-1；
}
2.7算法思路：
依次将A中的元素和B的元素比较，将值相等的元素赋给C，如此直到线性表扫描完毕，线性表C就是所求递增有序线性表。
算法：
voidmerge（SeqListA,SeqListB,SeqList*C）
{inti，j，k；
i=0；j=0；k=0；
while（i<=A.last）
while（j<=B.last）
if（A.data[i]=B.data[j]）
C->data[k++]=A.data[i++]；
C->last=k-1；
}
习题3参考答案
3.1.选择题
（1）.D
（2）.C（3）.D（4）.C（5）.B（6）.C（7）.C（8）.C（9）.B（10）.AB
（11）.D（12）.B（13）.D（14）.C（15）.C（16）.D（17）.D（18）.C（19）.C（20）.C
3.2.填空题
（1）FILO,FIFO
（2）-1,34X*+2Y*3/-
（3）stack.top,stack.s[stack.top]=x
（4）p>llink->rlink=p->rlink,p->rlink->llink=p->rlink
（5）（R-F+M）%M
（6）top1+1=top2
（7）F==R
（8）front==rear
（9）front==（rear+1）%n
（10）N-1
3.3答：
一般线性表使用数组来表示的
线性表一般有插入、删除、读取等对于任意元素的操作
而栈只是一种特殊的线性表
栈只能在线性表的一端插入（称为入栈,push）或者读取栈顶元素或者称为“弹出、出栈”（pop）。
3.4答：
相同点：
栈和队列都是特殊的线性表，只在端点处进行插入，删除操作。
不同点：
栈只在一端（栈顶）进行插入，删除操作；队列在一端（top）删除，一端（rear）插入。
3.5答：
可能序列有14种：
ABCD;ACBD;ACDB;ABDC;ADCB;BACD;BADC;BCAD;BCDA;BDCA;CBAD;CBDA;CDBA;DCBA。
3.6答：
不能得到4，3，5，6，1，2，最先出栈的是4,则按321的方式出，不可能得到1在2前的序列，可以得到1，3，5，4，2，6，按如下方式进行push
（1）,pop（）,push
（2）,push（3）,pop（）,push（4）,push（5）,pop（）,pop（）,pop（）,push（6）,pop（）。
3.7答：
stack
3.8非递归:
intvonvert（intno,inta[]）//将十进制数转换为2进制存放在a[]，并返回位数
{
intr;
SeStacks,*p;
P=&s;
Init_stack（p）;
while（no）
{
push（p,no%2）;
no/=10;
}
r=0;
while（!
empty_stack（p））
{
pop（p,a+r）;
r++;
}
returnr;
}
递归算法:
voidconvert（intno）
{
if（no/2>0）
{
Convert（no/2）;
Printf（“%d”,no%2）;
}
else
printf（“%d”,no）;
}
3.9参考程序：
voidview（SeStacks）
{
SeStack*p;//假设栈元素为字符型
charc;
p=&s;
while（!
empty_stack（p））
{
c=pop（p）;
printf（“%c”,c）;
}
printf（”\n”）;
}
3.10答：
char
3.11参考程序：
voidout（linkqueueq）
{
inte;
while（q.rear!
=q.front）
{
dequeue（q,e）;
print（e）;//打印
}
}
习题4参考答案
4.1选择题：
（1）.A
（2）.D（3）.C（4）.C（5）.B（6）.B（7）.D（8）.A（9）.B（10）.D
4.2填空题：
（1）串长相等且对应位置字符相等
（2）不含任何元素的串，0
（3）所含字符均是空格，所含空格数
（4）10
（5）“helloboy”
（6）13
（7）1066
（8）模式匹配
（9）串中所含不同字符的个数
（10）36
4.3StrLength（s）=14,StrLength（t）=4,SubStr（s，8，7）=”STUDENT”,SubStr（t，2，1）=”O”,
StrIndex（s,“A”）=3,StrIndex（s，t）=0,StrRep（s，“STUDENT”，q）=”IAMAWORKER”,
4.4StrRep（s,”Y”,”+”）;StrRep（s,”+*”,”*Y”）;
4.5空串：
不含任何字符；空格串：
所含字符都是空格
串变量和串常量:
串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过程中是可以改变和重新赋值的
主串与子串：
子串是主串的一个子集
串变量的名字与串变量的值:
串变量的名字表示串值的标识符
4.6
intEQUAl（S,T）
{
char*p,*q;
p=&S;
q=&T;
while（*p&&*q）
{
if（*p!
=*q）
return*p-*q;
p++;
q++;
}
return*p-*q;
}
4.7
（1）6*8*6=288
（2）1000+47*6=1282
（3）1000+（8+4）*8=1096
（4）1000+（6*7+4）*8=1368
4.8
习题5参考答案
5.1选择
（1）C
（2）B（3）C（4）B（5）C（6）D（7）C（8）C（9）B（10）C
（11）B（12）C（13）C（14）C（15）C（16）B
5.2填空
（1）1
（2）1036；1040
（3）2i
（4）1；n;n-1;2
（5）2k-1；2k-1
（6）ACDBGJKIHFE
（7）p!
=NULL
（8）Huffman树
（9）其第一个孩子;下一个兄弟
（10）先序遍历；中序遍历
5.3
叶子结点:
C、F、G、L、I、M、K；
非终端结点：
A、B、D、E、J；
各结点的度：
结点：
ABCDEFGLIJKM
度：
430120000100
树深：
4
5.4
无序树形态如下：
二叉树形态如下：
5.5
二叉链表如下:
三叉链表如下:
5.6
先序遍历序列:
ABDEHICFJG
中序遍历序列:
DBHEIAFJCG
后序遍历序列:
DHIEBJFGCA
5.7
（1）先序序列和中序序列相同：
空树或缺左子树的单支树；
（2）后序序列和中序序列相同：
空树或缺右子树的单支树；
（3）先序序列和后序序列相同：
空树或只有根结点的二叉树。
5.8
这棵二叉树为:
5.9
先根遍历序列:
ABFGLCDIEJMK
后根遍历序列:
FGLBCIDMJKEA
层次遍历序列:
ABCDEFGLIJKM
5.10
证明：
设树中结点总数为n，叶子结点数为n0，则
n=n0+n1+……+nm
（1）
再设树中分支数目为B，则
B=n1+2n2+3n3+……+mnm
（2）
因为除根结点外，每个结点均对应一个进入它的分支，所以有
n=B+1（3）
将
（1）和
（2）代入（3），得
n0+n1+……+nm=n1+2n2+3n3+……+mnm+1
从而可得叶子结点数为：
n0=n2+2n3+……+（m-1）nm+1
5.11
由5.10结论得，n0=（k-1）nk+1
又由n=n0+nk，得nk=n-n0，代入上式，得
n0=（k-1）（n-n0）+1
叶子结点数为：
n0=n（k-1）/k
5.12
intNodeCount（BiTreeT）
{//计算结点总数
if（T）
if（T->lchild==NULL）&&（T-->rchild==NULL）
return1;
else
returnNodeCount（T->lchild）+Node（T-->rchild）+1;
else
return0;
}
5.13
voidExchangeLR（Bitreebt）{
/*将bt所指二叉树中所有结点的左、右子树相互交换*/
if（bt&&（bt->lchild||bt->rchild））{
bt->lchild<->bt->rchild;
Exchange-lr（bt->lchild）;
Exchange-lr（bt->rchild）;
}
}/*ExchangeLR*/
5.14
intIsFullBitree（BitreeT）
{/*是则返回1，否则返回0。
*/
Init_Queue（Q）;/*初始化队列*/
flag=0;
In_Queue（Q，T）;/*根指针入队列，按层次遍历*/
while（!
Empty_Queue（Q））
{
Out_Queue（Q,p）;
if（!
p）flag=1;/*若本次出队列的是空指针时，则修改flag值为1。
若以后出队列的指针存在非空，则可断定不是完全二叉树*/
elseif（flag）return0;/*断定不是完全二叉树*/
else
{
In_Queue（Q，p->lchild）;
In_Queue（Q，p->rchild）;/*不管孩子是否为空，都入队列。
*/
}
}/*while*/
return1;/*只有从某个孩子指针开始，之后所有孩子指针都为空，才可断定为完全二叉树*/
}/*IsFullBitree*/
5.15
转换的二叉树为：
5.16
对应的森林分别为：
5.17
typedefcharelemtype;
typedefstruct
{elemtypedata;
intparent;
}NodeType;
（1）求树中结点双亲的算法:
intParent（NodeTypet[],elemtypex）{
/*x不存在时返回-2,否则返回x双亲的下标（根的双亲为-1*/
for（i=0;iif（x==t[i].data）returnt[i].parent;
return-2;
}/*Parent*/
（2）求树中结点孩子的算法:
voidChildren（NodeTypet[],elemtypex）{
for（i=0;iif（x==t[i].data）
break;/*找到x,退出循环*/
}/*for*/
if（i>=MAXNODE）printf（“x不存在\n”）;
else{
flag=0;
for（j=0;jif（i==t[j].parent）
{printf（“x的孩子:
%c\n”,t[j].data）;
flag=1;
}
if（flag==0）printf（“x无孩子\n”）;
}
}/*Children*/
5.18
typedefcharelemtype;
typedefstructChildNode
{intchildcode;
structChildNode*nextchild;
}
typedefstruct
{elemtypedata;
structChildNode*firstchild;
}NodeType;
（1）求树中结点双亲的算法:
intParentCL（NodeTypet[],elemtypex）{
/*x不存在时返回-2,否则返回x双亲的下标*/
for（i=0;iif（x==t[i].data）{
loc=i;/*记下x的下标*/
break;
}
if（i>=MAXNODE）return-2;/*x不存在*/
/*搜索x的双亲*/
for（i=0;ifor（p=t[i].firstchild;p!
=NULL;p=p->nextchild）
if（loc==p->childcode）
returni;/*返回x结点的双亲下标*/
}/*ParentL*/
（2）求树中结点孩子的算法:
voidChildrenCL（NodeTypet[],elemtypex）{
for（i=0;iif（x==t[i].data）/*依次打印x的孩子*/
{
flag=0;/*x存在*/
for（p=t[i].firstchild;p;p=p->nextchild）
{printf（“x的孩子:
%c\n”,t[p->childcode].data）;
flag=1;
}
if（flag==0）printf（“x无孩子\n”）;
return;
}/*if*/
printf（“x不存在\n”）;
return;
}/*ChildrenL*/
5.19
typedefcharelemtype;
typedefstructTreeNode
{elemtypedata;
structTreeNode*firstchild;
structTreeNode*nextsibling;
}NodeType;
voidChildrenCSL（NodeType*t,elemtypex）{/*层次遍历方法*/
Init_Queue（Q）;/*初始化队列*/
In_Queue（Q,t）;
count=0;
while（!
Empty_Queue（Q））{
Out_Queue（Q,p）;
if（p->data==x）
{/*输出x的孩子*/
p=p->firstchild;
if（!
p）printf（“无孩子\n”）;
else
{printf（“x的第%i个孩子:
%c\n”,++count,p->data）;/*输出第一个孩子*/
p=p->nextsibling;/*沿右分支*/
while（p）{
printf（“x的第%i个孩子:
%c\n”,++count,p->data）;
p=p->nextsibling;
}
}
return;
}
if（p->firstchild）In_Queue（Q,p->firstchild）;
if（p->nextsibling）In_Queue（Q,p->nextsibling）;
}
}/*ChildrenCSL*/
5.20
（1）哈夫曼树为:
（2）在上述哈夫曼树的每个
升级会员 