数据结构(第3版)习题答案Word文档格式.doc
《数据结构(第3版)习题答案Word文档格式.doc》由会员分享，可在线阅读，更多相关《数据结构(第3版)习题答案Word文档格式.doc（105页珍藏版）》请在冰点文库上搜索。
为了评价算法的执行效率，通常采用大写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;
i<
n;
i++）
if（a[i]<
x）x=a[i];
（3）for（i=0;
for（j=0;
j<
j++）
printf（“%d”,i+j）;
（4）for（i=1;
=n-1;
{k=i;
for（j=i+1;
=n;
if（a[j]>
a[j+1]）k=j;
t=a[k];
a[k]=a[i];
a[i]=t;
}
（5）for（i=0;
{++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!
常数
对数
线性
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
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<
stdio.h>
#defineN100
typedefintdatatype;
typedefstruct{
datatypedata[N];
intlength;
}seqlist;
/*预定义最大的数据域空间*/
/*假设数据类型为整型*/
/*此处假设数据元素只包含一个整型的关键字域*/
/*线性表长度*/
/*预定义的顺序表类型*/
算法countx（L,x）用于求顺序表L中值为x的结点的个数。
intcountx（seqlist*L,datatypex）
{
intc=0;
inti;
for（i=0;
L->
length;
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<
j）
{t=L->
data[i];
data[i++]=L->
data[j];
data[j--]=t;
2.5已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为x的结点，
使顺序表中的结点仍然是从小到大有序。
顺序表的定义同题2.3，实现本题要求的算法程序如下：
6
voidinsertx（seqlist*L,datatypex）
{intj;
length<
N）
{j=L->
while（j>
=0&
&
L->
data[j]>
x）
{L->
data[j+1]=L->
j--;
data[j+1]=x;
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）
#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++;
a[S->
top]=x;
charpop（Stack*S）/*出栈*/
top==-1）
{printf（"
ERROR,POPEmptyStack"
）;
return-1;
top--;
returnS->
top+1];
intisEmpty（Stack*S）/*判断栈是否为空*/
top==-1）return1;
return0;
voidoutSeq（char*seq,intlen）/*输出顶点序列*/
inti;
for（i=0;
i<
len;
i++）
printf（"
%2c"
seq[i]）;
\n"
voidscheduler（intpos,intseq_pos）
8
/*
pos:
处理到原始数据中的第pos个元素，
seq_pos：
若出栈，应放在当前输出数组的第seq_pos个位置
*/
inti=0;
chart;
/*对任何一个数，总是先进栈，再出栈。
另外，这里不需要循环，类似于“查找数组中元
素”用递归*/
if（pos<
len）{/*一个数进栈后,有两种处理方式：
要么立刻出栈,要么进行下一个数的进栈*/
push（&
S,d[pos]）;
scheduler（pos+1,seq_pos）;
pop（&
S）;
if（!
isEmpty（&
S））{/*一个数出栈后,有两种处理方式：
要么继续出栈,要么继续下一个数的进
栈*/
t=pop（&
seq[seq_pos++]=t;
scheduler（pos,seq_pos）;
S,t）;
if（pos>
=len&
isEmpty（&
S））
{outSeq（seq,len）;
count++;
intmain（）{
\npleaseinputthenumbescheduled:
"
scanf（"
%d"
&
len）;
/*用len存储待调度的火车数量*/
d[i]='
a'
+i;
/*创建火车编号，如a、b、c、...等*/
theoriginalseqis:
"
outSeq（d,len）;
initStack（&
scheduler（0,0）;
\ncount=%5d"
count）;
方法二：
解题思路：
栈具有先进后出、后进先出的特点，因此，任何一个调度结果应该是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;
{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];
/*对每个str[i]判断其后比它小的数是否为降序序列*/
{m=0;
n&
flag;
if（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
%2d:
cont++）;
str[i]）;
intmain（）
{intstr[100],n,i;
inputaint:
/*输出排列的元素个数*/
&
n）;
i++）/*初始化排列集合*/
str[i]=i+1;
inputtheresult:
perm（str,0,n）;
当参与进出栈的元素个数为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个数的全排列，对满足进出栈
规则的排列则计数并输
升级会员 