数据结构(第3版)习题答案.doc
《数据结构(第3版)习题答案.doc》由会员分享，可在线阅读，更多相关《数据结构(第3版)习题答案.doc（105页珍藏版）》请在冰点文库上搜索。
十二五普通高等教育国家级本科规划教材
第1章
绪论
高等学校精品资源共享课程
1.1什么是数据结构？
【答】：
数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储
于计算机中，并在这些数据上定义了一个运算集合。
1.2数据结构涉及哪几个方面？
【答】：
数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集
合。
1.3两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不
一样，它们是否可以认作是同一个数据结构？
为什么？
【答】：
不能，运算集合是数据结构的重要组成部分，不同的运算集合所确定的数据结构是不
一样的，例如，栈与队列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不一样，
所以它们是两种不同的数据结构。
1.4线性结构的特点是什么？
非线性结构的特点是什么？
【答】：
线性结构元素之间的关系是一对一的，在线性结构中只有一个开始结点和一个终端结
点，其他的每一个结点有且仅有一个前驱和一个后继结点。
而非线性结构则没有这个特点，元
素之间的关系可以是一对多的或多对多的。
1.5数据结构的存储方式有哪几种？
【答】：
数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。
1.6算法有哪些特点？
它和程序的主要区别是什么？
【答】：
算法具有
（1）有穷性
（2）确定性（3）0个或多个输入（4）1个或多个输出（5）可
行性等特征。
程序是算法的一种描述方式，通过程序可以在计算机上实现算法。
1.7抽象数据类型的是什么？
它有什么特点？
【答】：
抽象数据类型是数据类型的进一步抽象，是大家熟知的基本数据类型的延伸和发展。
抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。
对一
个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这
些函数的参数性质。
一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本
数据类型那样，十分方便地使用抽象数据类型。
抽象数据类型的设计者根据这些描述给出操作
的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。
1.8算法的时间复杂度指的是什么？
如何表示？
【答】：
算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的
机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在
同一台计算机上执行的时间也不一样，另外，算法执行的时间还与输入数据的状态有关，所以
对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。
算
法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为n的数据处理问题，用
T（n）表示算法基本操作的执行次数。
为了评价算法的执行效率，通常采用大写O符号表示算法
的时间复杂度，大写O符号给出了函数f的一个上限。
其它义如下：
3
十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
定义：
f（n）=O（g（n））当且仅当存在正的常数c和n0，使得对于所有的n≥n0，有f（n）≤cg（n）。
上述定义表明，函数f顶多是函数g的c倍，除非n小于n0。
因此对于足够大的n（如n≥n0），
g是f的一个上限（不考虑常数因子c）。
在为函数f提供一个上限函数g时，通常使用比较
简单的函数形式。
比较典型的形式是含有n的单个项（带一个常数系数）。
表1-1列出了一些
常用的g函数及其名称。
对于表1-1中的对数函数logn，没有给出对数基，原因是对于任何大
于1的常数a和b都有logan=logbn/logba,所以logan和logbn都有一个相对的乘法系数1/logba，
其中a是一个常量。
表1-1常用的渐进函数
1.9算法的空间复杂度指的是什么？
如何表示？
【答】：
算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。
可以将它表
示为问题规模的函数，并通过大写O符号表示空间复杂度。
1.10对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度T（n）。
（1）i++;
（2）for（i=0;iif（a[i]（3）for（i=0;ifor（j=0;jprintf（“%d”,i+j）;
（4）for（i=1;i<=n-1;i++）
{k=i;
for（j=i+1;j<=n;j++）
if（a[j]>a[j+1]）k=j;
t=a[k];a[k]=a[i];a[i]=t;
}
（5）for（i=0;ifor（j=0;j{++x;s=s+x;}
【答】：
（1）O
（1）；
（2）O（n）；（3）O（n2）；（4）O（n2）；（5）O（n2）
4
函数
名称
1
logn
n
nlogn
2
n
3
n
n
2
n!
常数
对数
线性
n个logn
平方
立方
指数
阶乘
十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
第2章
线性表及其顺序存储
2.1选择题
（1）表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，
插入一个元素所需移动元素的平均个数为（
为（A）。
E
），删除一个元素所需移动元素的平均个数
A．（n−1）/2
E．n/2
B．n
F．（n+1）/2
C．n+1
G．（n−2）/2
D．n−1
（2）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，
一个元素出栈后即进入队列Q，若6个元素出队的序列为e2、e4、e3、e6、e5和e1，则栈S
的容量至少应该为（C）。
A．6
B．4
C．3
D．2
（3）设栈的输入序列为1、2、3…n，若输出序列的第一个元素为n，则第i个输出的元素为
（B）。
A．不确定
B．n−i+1
C．i
D．n−i
（4）在一个长度为n的顺序表中删除第i个元素（1<=i<=n）时，需向前移动（A）个
元素。
A．n−i
B．n−i+1
C．n−i−1
D．i
（5）若长度为n的线性表采用顺序存储结构存储，在第i个位置上插入一个新元素的时
间复杂度为（A）。
A．O（n）
B．O
（1）
C．O（n2）
D．O（n3）
（6）表达式a*（b+c）−d的后缀表达式是（B
）。
A．abcd*+−
B．abc+*d−
C．abc*+d−
D．−+*abcd
（7）队列是一种特殊的线性表，其特殊性在于（C）。
A．插入和删除在表的不同位置执行B．插入和删除在表的两端位置执行
C．插入和删除分别在表的两端执行D．插入和删除都在表的某一端执行
（8）栈是一种特殊的线性表，具有（B）性质。
A．先进先出
B．先进后出
C．后进后出
D．顺序进出
（9）顺序循环队列中（数组的大小为n），队头指示front指向队列的第1个元素，队尾
指示rear指向队列最后元素的后1个位置，则循环队列中存放了n−1个元素，即循环队列满
的条件为（B
）。
A．（rear+1）%n=front−1
C．（rear）%n=front
B．（rear+1）%n=front
D．rear+1=front
（10）顺序循环队列中（数组的大小为6），队头指示front和队尾指示rear的值分别为3
和0，当从队列中删除1个元素，再插入2个元素后，front和rear的值分别为（D）。
A．5和1
B．2和4
C．1和5
D．4和2
2.2什么是顺序表？
什么是栈？
什么是队列？
5
十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
【答】：
当线性表采用顺序存储结构时，即为顺序表。
栈是一种特殊的线性表，它的特殊性表
现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈顶），
因此，栈具有先进后出、后进先出的特点。
队列也是一种特殊的线性表，它的特殊性表现在约
定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具
有先进先出，后进后出的特点。
2.3设计一个算法，求顺序表中值为x的结点的个数。
【答】：
顺序表的存储结构定义如下（文件名seqlist.h）：
#include
#defineN100
typedefintdatatype;
typedefstruct{
datatypedata[N];
intlength;
}seqlist;
/*预定义最大的数据域空间*/
/*假设数据类型为整型*/
/*此处假设数据元素只包含一个整型的关键字域*/
/*线性表长度*/
/*预定义的顺序表类型*/
算法countx（L,x）用于求顺序表L中值为x的结点的个数。
intcountx（seqlist*L,datatypex）
{
intc=0;
inti;
for（i=0;ilength;i++）
if（L->data[i]==x）c++;
returnc;
}
2.4设计一个算法，将一个顺序表倒置。
即，如果顺序表各个结点值存储在一维数组a中，倒
置的结果是使得数组a中的a[0]等于原来的最后一个元素，a[1]等于原来的倒数第2个元
素，…，a的最后一个元素等于原来的第一个元素。
【答】：
顺序表的存储结构定义同题2.3，实现顺序表倒置的算法程序如下：
voidverge（seqlist*L）
{intt,i,j;
i=0;
j=L->length-1;
while（i{t=L->data[i];
L->data[i++]=L->data[j];
L->data[j--]=t;
}
}
2.5已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为x的结点，
使顺序表中的结点仍然是从小到大有序。
【答】：
顺序表的定义同题2.3，实现本题要求的算法程序如下：
6
十二五普通高等教育国家级本科规划教材
voidinsertx（seqlist*L,datatypex）
{intj;
if（L->length{j=L->length-1;
while（j>=0&&L->data[j]>x）
{L->data[j+1]=L->data[j];
j--;
}
L->data[j+1]=x;
L->length++;
}
}
2.6将下列中缀表达式转换为等价的后缀表达式。
（1）5+6*7
（2）（5-6）/7
（3）5-6*7*8
（4）5*7-8
（5）5*（7-6）+8/9
（6）7*（5-6*8）-9
【答】：
高等学校精品资源共享课程
（7）5+6*7
（8）（5-6）/7
（9）5-6*7*8
（10）5*7-8
（11）5*（7-6）+8/9
（12）7*（5-6*8）-9
后缀表达式：
567*+
后缀表达式：
56-7/
后缀表达式：
567*8*-
后缀表达式：
57*8-
后缀表达式：
576-*89/+
后缀表达式：
7568*-*9-
2.7循环队列存储在一个数组中，数组大小为n，队首指针和队尾指针分别为front和rear，请
写出求循环队列中当前结点个数的表达式。
【答】：
循环队列中当前结点个数的计算公式是：
（n+rear-front）%n
2.8编号为1,2,3,4的四列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些？
如果
有n列火车通过调度站，请设计一个算法，输出所有可能的调度结果。
【答】：
方法一：
算法思想：
逐次输出所有可能，用回溯法。
即：
总体：
对原始序列中的每一个元素，总是先入栈，后出栈
1．入栈后的操作：
a.该元素出栈；b.下一个元素入栈；
2．出栈后的操作：
a.（栈中其他元素）继续出栈；b.（原始序列中）下一个数入栈；
注意：
回溯法，关键在于回溯，即在某分支结点X：
处理X的一个子分支，再退回分支X，
接着处理X的下一个子分支,若所有X的子分支处理完，再退回上一层分支节点。
所谓“退回”，
7
十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
实际上就是恢复。
程序代码：
（2_8_1.c）
#include
#defineMAX26
typedefstructs{
chara[MAX];
inttop;
}Stack;
/*定义一些全局变量*/
StackS;/*定义全局性的栈*/
chard[MAX],seq[MAX];/*d[MAX]用于存储原始入栈序列，seq[MAX]用于存储输出序列*/
intlen;/*定义将通过栈的元素个数*/
intcount=0;/*用于统计输出序列的个数*/
voidinitStack（Stack*S）/*初始化空栈*/
{S->top=-1;}
voidpush（Stack*S,charx）/*进栈*/
{
if（S->top>=MAX）return;
S->top++;
S->a[S->top]=x;
}
charpop（Stack*S）/*出栈*/
{
if（S->top==-1）
{printf（"ERROR,POPEmptyStack"）;
return-1;
}
S->top--;
returnS->a[S->top+1];
}
intisEmpty（Stack*S）/*判断栈是否为空*/
{
if（S->top==-1）return1;
return0;
}
voidoutSeq（char*seq,intlen）/*输出顶点序列*/
{
inti;
for（i=0;iprintf（"%2c",seq[i]）;
printf（"\n"）;
}
voidscheduler（intpos,intseq_pos）
8
十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
{
/*
pos:
处理到原始数据中的第pos个元素，
seq_pos：
若出栈，应放在当前输出数组的第seq_pos个位置
*/
inti=0;chart;
/*对任何一个数，总是先进栈，再出栈。
另外，这里不需要循环，类似于“查找数组中元
素”用递归*/
if（pos要么立刻出栈,要么进行下一个数的进栈*/
push（&S,d[pos]）;
scheduler（pos+1,seq_pos）;
pop（&S）;
}
if（!
isEmpty（&S））{/*一个数出栈后,有两种处理方式：
要么继续出栈,要么继续下一个数的进
栈*/
t=pop（&S）;
seq[seq_pos++]=t;
scheduler（pos,seq_pos）;
push（&S,t）;
}
if（pos>=len&&isEmpty（&S））
{outSeq（seq,len）;count++;}
}
intmain（）{
inti;
printf（"\npleaseinputthenumbescheduled:
"）;
scanf（"%d",&len）;/*用len存储待调度的火车数量*/
for（i=0;id[i]='a'+i;/*创建火车编号，如a、b、c、...等*/
printf（"theoriginalseqis:
"）;
outSeq（d,len）;
initStack（&S）;
scheduler（0,0）;
printf（"\ncount=%5d",count）;
return0;
}
方法二：
解题思路：
栈具有先进后出、后进先出的特点，因此，任何一个调度结果应该是1，2，3，
4全排列中的一个元素。
由于进栈的顺序是由小到大的，所以出栈序列应该满足以下条件：
对
于序列中的任何一个数其后面所有比它小的数应该是倒序的，例如4321是一个有效的出栈序
9
十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
列，1423不是一个有效的出栈结果（4后面比它小的两个数2，3不是倒序）。
据此，本题可以
通过算法产生n个数的全排列，然后将满足出栈规则的序列输出。
产生n个数的全排列有递归与非递归两种实现算法。
产生全排列的递归算法：
设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。
集合X中元素的全排列记为
perm（X）。
（ri）perm（X）表示在全排列perm（X）的每一个排列前加上前缀ri得到的排列。
R的全排
列可归纳定义如下：
当n=1时，perm（R）=（r），其中r是集合R中惟一的元素；
当n>1时，perm（R）由（r1）perm（R1）,（r2）perm（R2）,…,（rn）perm（Rn）构成。
依此递归定义，可设计产生perm（R）的递归算法如下：
递归解法：
（2_8_2.c）
#include
intcont=1;
/*全局变量，用于记录所有可能的出栈序列个数*/
voidprint（intstr[],intn）;
/*求整数序列str[]从k到n的全排列*/
voidperm（intstr[],intk,intn）
{inti,temp;
if（k==n-1）print（str,n）;
else
{for（i=k;i{temp=str[k];str[k]=str[i];str[i]=temp;
perm（str,k+1,n）;/*递归调用*/
temp=str[i];str[i]=str[k];str[k]=temp;
}
}
}
/*本函数判断整数序列str[]是否满足进出栈规则,若满足则输出*/
voidprint（intstr[],intn）
{inti,j,k,l,m,flag=1,b[2];
for（i=0;i/*对每个str[i]判断其后比它小的数是否为降序序列*/
{m=0;
for（j=i+1;jif（str[i]>str[j]）{if（m==0）b[m++]=str[j];
else{if（str[j]>b[0]）{flag=0;}
elseb[0]=str[j];
}
}
}
if（flag）
/*满足出栈规则则输出str[]中的序列*/
10
十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
{
printf（"%2d:
",cont++）;
for（i=0;iprintf（"%d",str[i]）;
printf（"\n"）;
}
}
intmain（）
{intstr[100],n,i;
printf（"inputaint:
"）;/*输出排列的元素个数*/
scanf（"%d",&n）;
for（i=0;istr[i]=i+1;
printf（"inputtheresult:
\n"）;
perm（str,0,n）;
printf（"\n"）;
return0;
}
当参与进出栈的元素个数为4时，输出的结果如下图所示。
该算法执行的时间复杂度为O（n!
）。
随着n的增大，算法的执行效率非常的低。
非递归解法：
（2_8_3.c）
对一组数穷尽所有排列，还可一种更直接的方法，将一个排列看作一个长整数，则所有排
列对应着一组整数，将这组整数按从小到大的顺序排成一个数列，从对应最小的整数开始，按
数列的递增顺序逐一列举每个排列对应的每一个整数，这能更有效地完成排列的穷举。
从一个
排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。
倘若当前排列为
1,2,4,6,5,3，并令其对应的长整数为124653。
要寻找比长整数124653更大的排列，可从该排列
的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它前一个数字大时，如本例中
的6比它的前一位数字4大，则说明还有可能对应更大整数的排列。
但为顺序从小到大列举出
所有的排列，不能立即调整得太大，如本例中将数字6与数字4交换得到的排列为126453就
不是排列124653的下一个排列。
为得到排列124653的下一个排列，应从已考察过的那部分数
11
十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
字中选出比数字4大，但又是它们中最小的那一个数字，比如数字5，与数字4交换。
该数字
也是从后向前考察过程中第一个比4大的数字，5与4交换后，得到排列125643。
在前面数字
1，2，5固定的情况下，还应选择对应最小整数的那个排列，为此还需将后面那部分数字的排
列颠倒，如将数字6，4，3的排列顺序颠倒，得到排列1,2,5,3,4,6，这才是排列1，2，4，6，
5，3的下一个排列。
按照以上想法可以编写非递归程序实现n个数的全排列，对满足进出栈
规则的排列则计数并输
升级会员 