数据结构(第3版)习题答案.doc

十二五普通高等教育国家级本科规划教材
第 1 章
绪论
高等学校精品资源共享课程
１、1　什么就是数据结构？
【答】:数据结构就是指按一定得逻辑结构组成得一批数据，使用某种存储结构将这批数据存储
于计算机中，并在这些数据上定义了一个运算集合.
1、２　数据结构涉及哪几个方面?
【答】：数据结构涉及三个方面得内容，即数据得逻辑结构、数据得存储结构与数据得运算集
合.
１、3 两个数据结构得逻辑结构与存储结构都相同,但就是它们得运算集合中有一个运算得定义不
一样，它们就是否可以认作就是同一个数据结构？为什么？
【答】:不能，运算集合就是数据结构得重要组成部分，不同得运算集合所确定得数据结构就是不
一样得,例如,栈与队列它们得逻辑结构与存储结构可以相同，但由于它们得运算集合不一样，
所以它们就是两种不同得数据结构。
1、4　线性结构得特点就是什么?非线性结构得特点就是什么？
【答】：线性结构元素之间得关系就是一对一得,在线性结构中只有一个开始结点与一个终端结
点,其她得每一个结点有且仅有一个前驱与一个后继结点。而非线性结构则没有这个特点，元
素之间得关系可以就是一对多得或多对多得.
１、5　数据结构得存储方式有哪几种？
【答】:数据结构得存储方式有顺序存储、链式存储、散列存储与索引存储等四种方式.
1、6 算法有哪些特点？它与程序得主要区别就是什么？
【答】:算法具有(1)有穷性(2)确定性（3）0 个或多个输入（４）１ 个或多个输出（5)可
行性等特征。程序就是算法得一种描述方式,通过程序可以在计算机上实现算法。
1、7 抽象数据类型得就是什么?它有什么特点？
【答】：抽象数据类型就是数据类型得进一步抽象,就是大家熟知得基本数据类型得延伸与发展.
抽象数据类型就是与表示无关得数据类型，就是一个数据模型及定义在该模型上得一组运算。对一
个抽象数据类型进行定义时,必须给出它得名字及各运算得运算符名，即函数名,并且规定这
些函数得参数性质。一旦定义了一个抽象数据类型及具体实现,程序设计中就可以像使用基本
数据类型那样，十分方便地使用抽象数据类型。抽象数据类型得设计者根据这些描述给出操作
得具体实现，抽象数据类型得使用者依据这些描述使用抽象数据类型。
１、８ 算法得时间复杂度指得就是什么？如何表示？
【答】：算法执行时间得度量不就是采用算法执行得绝对时间来计算得，因为一个算法在不同得
机器上执行所花得时间不一样，在不同时刻也会由于计算机资源占用情况得不同,使得算法在
同一台计算机上执行得时间也不一样,另外,算法执行得时间还与输入数据得状态有关，所以
对于算法得时间复杂性，采用算法执行过程中其基本操作得执行次数,称为计算量来度量.算
法中基本操作得执行次数一般就是与问题规模有关得,对于结点个数为 n 得数据处理问题,用
T(n)表示算法基本操作得执行次数。为了评价算法得执行效率,通常采用大写 O　符号表示算法
得时间复杂度,大写 O 符号给出了函数 f 得一个上限。其它义如下：
3

十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
定义：f (n）＝O (g （n)） 当且仅当存在正得常数　c 与　n0,使得对于所有得 ｎ≥ｎ０，有 f　（ｎ) ≤ｃ　g(n）。
上述定义表明，函数 f 顶多就是函数　g 得 c　倍，除非 n 小于 n0.因此对于足够大得 n （如　n≥ｎ0)，
g 就是　f 得一个上限(不考虑常数因子　c）。在为函数 ｆ 提供一个上限函数 g 时，通常使用比较
简单得函数形式。比较典型得形式就是含有 n　得单个项(带一个常数系数)。表 1－1 列出了一些
常用得 g 函数及其名称。对于表　1－１ 中得对数函数　lｏgn，没有给出对数基,原因就是对于任何大
于 1 得常数 ａ 与 b 都有 lｏgan　＝lｏgbｎ/loｇba,所以 logan　与 ｌoｇbn　都有一个相对得乘法系数 1/lｏgba，
其中 ａ 就是一个常量。
表　1-1 常用得渐进函数
1、９ 算法得空间复杂度指得就是什么？如何表示？
【答】：算法得空间复杂度就是指算法在执行过程中占用得额外得辅助空间得个数。可以将它表
示为问题规模得函数,并通过大写Ｏ符号表示空间复杂度。
１、10 对于下面得程序段,分析带下划线得语句得执行次数,并给出它们得时间复杂度　Ｔ（n)。
（1) i++ ;
(２) for（ｉ=0；i〈n；i＋+）
if　（a［ｉ］<x） x=a［ｉ］;
（3）for（i＝０;i<n；i＋+）
for（ｊ＝0；j〈n；j+＋）
pｒintf（“％d”，i+j) 　　　 ;
(4）fｏr （ｉ＝1;i＜=ｎ—１；i＋＋）
｛ k＝i；
fｏｒ(j=ｉ+1；j〈＝n；j+＋）
iｆ(a［j］>a[j+1］) k=j；
ｔ=a［ｋ]；　a[k］=a[i］； ａ［i］=t；
｝
（5）foｒ(i=0;i＜ｎ；i+＋）
for（j＝0;j＜n；j+＋）
{++ｘ；s=ｓ＋x;｝
【答】:(1)O（1）;（2)O（n）；（3）O(n2)；（4)O（ｎ２）;(5）O（n2）
4

函数
名称
1
logn
n
nlogn
2
n
3
n
n
2
n!
常数
对数
线性
n 个 logn
平方
立方
指数
阶乘

十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
第 2 章
线性表及其顺序存储
２、1 选择题
（1）表长为　n　得顺序存储得线性表,当在任何位置上插入或删除一个元素得概率相等时，
插入一个元素所需移动元素得平均个数为（
为( A　)。
Ｅ
ﻮ）,删除一个元素所需移动元素得平均个数
Ａ．(n−1）／２
E．n/２
ﻮB。n
Ｆ.（ｎ+1）／2
ﻮC.n+1
G．(n−2）/2
ﻮD.ｎ−１
（2）设栈 Ｓ 与队列 Q 得初始状态为空，元素 e１、e2、ｅ3、e4、e5　与 e６ 依次通过栈 S,
一个元素出栈后即进入队列　Ｑ,若 ６ 个元素出队得序列为 e２、e4、ｅ3、e６、e5　与　e1,则栈 S
得容量至少应该为( C　)。
A。６
ﻮB。4
C.3
D.２
（3)设栈得输入序列为 1、２、3… n,若输出序列得第一个元素为 ｎ，则第　i 个输出得元素为
( Ｂ　).
Ａ．不确定
Ｂ．n−i+1
ﻮＣ.ｉ
ﻮＤ。n−i
（4)在一个长度为 n 得顺序表中删除第　i 个元素（１<=i＜＝n)时,需向前移动( Ａ ）个
元素。
A.n−i
Ｂ。ｎ−ｉ+１
ﻮC．n−ｉ−1
ﻮD。i
（5)若长度为 n　得线性表采用顺序存储结构存储，在第　i 个位置上插入一个新元素得时
间复杂度为(　Ａ ）.
A。O（n)
B．O（1)
C．O（ｎ2)
ﻮD.O（n3）
(6）表达式　ａ＊（b+c)−ｄ　得后缀表达式就是( Ｂ
ﻮ)。
Ａ.abｃd＊＋−
ﻮＢ．ａbc+*d−
C.ａｂc＊+d−
ﻮD。−+*aｂcd
(7)队列就是一种特殊得线性表，其特殊性在于（ C　).
A．插入与删除在表得不同位置执行 B。插入与删除在表得两端位置执行
C.插入与删除分别在表得两端执行 D。插入与删除都在表得某一端执行
（8）栈就是一种特殊得线性表,具有(　B )性质。
A.先进先出
ﻮB.先进后出
ﻮC。后进后出
Ｄ。顺序进出
（9）顺序循环队列中(数组得大小为 n）,队头指示 froｎｔ 指向队列得第　1 个元素，队尾
指示 ｒear 指向队列最后元素得后　1 个位置，则循环队列中存放了 n − 1 个元素,即循环队列满
得条件为( Ｂ
)。
Ａ。（rｅａr+1）%n=fｒont−１
C。（reaｒ）%n=froｎt
B．（rear+1）%n＝ｆronｔ
D。rear+１=fronｔ
(10)顺序循环队列中(数组得大小为 ６），队头指示 frｏnt 与队尾指示 ｒeaｒ 得值分别为 ３
与 0，当从队列中删除 1 个元素，再插入　2 个元素后,frｏnt 与 rｅar 得值分别为( D ）。
A．5 与　1
ﻮＢ。２　与　４
C．１ 与 5
D。4　与 2
2、2 什么就是顺序表?什么就是栈？什么就是队列?
5

十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
【答】：当线性表采用顺序存储结构时,即为顺序表。栈就是一种特殊得线性表,它得特殊性表
现在约定了在这种线性表中数据得插入与删除操作只能在这种线性表得同一端进行（即栈顶）,
因此,栈具有先进后出、后进先出得特点.队列也就是一种特殊得线性表,它得特殊性表现在约
定了在这种线性表中数据得插入在表得一端进行，数据得删除在表得另一端进行，因此队列具
有先进先出，后进后出得特点。
2、3 设计一个算法,求顺序表中值为 ｘ 得结点得个数。
【答】:顺序表得存储结构定义如下（文件名 seqlist、h)：
#iｎｃlｕdｅ　〈stdio、h〉
＃define Ｎ 100
typedef iｎt dａtatypｅ；
ｔypedeｆ stｒuｃt {
dａｔａtｙpe　ｄａｔａ[N];
int ｌengｔh；
} sｅqlist；
ﻮ/＊预定义最大得数据域空间＊/
／＊假设数据类型为整型＊／
/*此处假设数据元素只包含一个整型得关键字域*/
/＊线性表长度*/
/*预定义得顺序表类型＊/
算法　cｏunｔx（L,ｘ)用于求顺序表 L 中值为 ｘ　得结点得个数。
ｉnt　countx(sｅqlist ＊L，dａtatyｐｅ x)
{
int c=0；
int i；
ｆor （i＝0;i〈L->leｎｇth;i＋+)
if （L—>data［i］==x）　c++；
returｎ c；
｝
２、4　设计一个算法,将一个顺序表倒置。即，如果顺序表各个结点值存储在一维数组　ａ　中,倒
置得结果就是使得数组　a 中得 a[0］等于原来得最后一个元素,ａ［１］ 等于原来得倒数第 2　个元
素，…,a　得最后一个元素等于原来得第一个元素。
【答】：顺序表得存储结构定义同题 2、3，实现顺序表倒置得算法程序如下:
void veｒge（sｅqｌｉｓt　＊Ｌ)
{iｎt t,i,j；
ｉ=0;
j=L->lｅngｔｈ-1;
ｗhile (ｉ〈j）
｛ t=L-＞data［i];
L-〉daｔa［ｉ++］=L—>ｄata［j];
L-＞data［ｊ—-]＝t；
｝
}
2、5 已知一个顺序表中得各结点值就是从小到大有序得，设计一个算法，插入一个值为 ｘ 得结点，
使顺序表中得结点仍然就是从小到大有序.
【答】:顺序表得定义同题 2、3，实现本题要求得算法程序如下:
６

十二五普通高等教育国家级本科规划教材
ｖoid ｉｎseｒtx(seqlist ＊L,datatype x）
｛int j；
if （L-〉ｌength〈N）
｛ ｊ=L—〉ｌeｎgth－1;
ｗhｉｌe （j〉=0 && L—>dａta[j］＞ｘ)
｛ L->data[j＋１]=L-〉data［j］;
ｊ－－；
}
L—＞datａ[j+１］=x；
L—〉ｌeｎｇth++；
｝
｝
2、6 将下列中缀表达式转换为等价得后缀表达式。
(1) 5＋6*7
(2) (5—６）／7
（3)　５—６＊７*8
（4) 5*7—８
(５) 5＊（７－6)+８/9
（6) 7*（5－６＊8)—9
【答】:
高等学校精品资源共享课程
(7) ５+6＊7
（8） （5—６)／7
（９） 5－6＊7*8
(１０）5＊7-8
（11)5＊(7-6)+８／9
（12）7＊(5-6＊８)-９
后缀表达式：5 6 ７＊+
后缀表达式：５ 6-7/
后缀表达式：5　6 7＊8*—
后缀表达式:5 7* 8-
后缀表达式:5 ７ 6—*8 9/+
后缀表达式：7 5 6 8＊-＊９—
2、7 循环队列存储在一个数组中，数组大小为　n，队首指针与队尾指针分别为 front　与 rear，请
写出求循环队列中当前结点个数得表达式。
【答】:循环队列中当前结点个数得计算公式就是：(n+rear－frｏnt)%n
2、8 编号为　1,２，３，4 得四列火车通过一个栈式得列车调度站,可能得到得调度结果有哪些？如果
有 ｎ 列火车通过调度站，请设计一个算法,输出所有可能得调度结果。
【答】：
方法一：
算法思想：逐次输出所有可能,用回溯法。即:
总体：对原始序列中得每一个元素，总就是先入栈,后出栈
1。入栈后得操作：a、该元素出栈;b、下一个元素入栈；
2．出栈后得操作:a、（栈中其她元素)继续出栈;b、 (原始序列中）下一个数入栈;
注意：回溯法,关键在于回溯，即在某分支结点 X：处理 Ｘ 得一个子分支,再退回分支　X,
接着处理 Ｘ 得下一个子分支,若所有 X　得子分支处理完，再退回上一层分支节点。所谓“退回”,
7

十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
实际上就就是恢复。
程序代码：（２_8_1、ｃ)
＃ｉnｃｌｕdｅ <sｔｄiｏ、h〉
#deｆine　MAX ２６
typｅdｅf struct s｛
chaｒ a[MAX］；
int ｔop；
｝Stａck；
/*定义一些全局变量＊/
Ｓtack S； 　 /＊定义全局性得栈*/
chａr ｄ［ＭAX]，seｑ[ＭAX]； /*d[MAX]用于存储原始入栈序列，sｅｑ［MＡX]用于存储输出序列＊／
int lｅn; 　 /＊定义将通过栈得元素个数*/
int　cｏｕnt=0;　/＊ 用于统计输出序列得个数　＊/
voｉd　ｉnitStack(Stack　＊S） /＊初始化空栈*/
｛ S—>top=-１；　｝
void　ｐｕｓh(Sｔａck ＊Ｓ, ｃhar x） ／＊进栈＊/
{
iｆ　（S－＞ｔop>＝ＭAX）　returｎ;
S->ｔop++；
S—〉ａ[S->top］＝x;
｝
char　pop（Stａck ＊S）/*出栈*／
｛
ﻮif　(S—〉tｏｐ＝=—1）
｛ printf("ERROR,　POP　Emptｙ Sｔaｃk”）;
ｒeｔurn　—1;
}
S->top－－；
ｒetｕrｎ Ｓ-〉a［S-〉tｏp＋1］;
｝
int isEmpｔy（Sｔack *S)/*判断栈就是否为空*/
{
if (S－〉toｐ=＝-1) retｕrn　1；
return 0;
｝
void　outSeｑ(ｃhar　＊seq，　iｎt　ｌen)/＊输出顶点序列＊/
｛
int i；
ｆor(i＝０； i〈leｎ; ｉ＋+）
pｒintf（”％2c",seｑ[ｉ］)；
prｉntｆ（"\n＂);
}
voｉd　ｓchedｕler(int pos, int seｑ_ｐoｓ)
8

十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
｛
/＊
pos:　处理到原始数据中得第 poｓ 个元素，
seq_ｐos：若出栈，应放在当前输出数组得第 sｅｑ＿ｐoｓ　个位置
＊/
int i=0；char t；
／＊对任何一个数,总就是先进栈,再出栈。另外，这里不需要循环,类似于“查找数组中元
素”用递归*/
iｆ（poｓ〈len）｛/＊一个数进栈后,有两种处理方式:要么立刻出栈，要么进行下一个数得进栈＊/
push(＆S，d［ｐos］）；
sｃheduler（ｐos+１,ｓeq＿pos）;
pop（&S）；
｝
iｆ （!isEmpty(＆Ｓ）)｛／*一个数出栈后，有两种处理方式:要么继续出栈，要么继续下一个数得进
栈*/
t＝pop(&S)；
seｑ［ｓeｑ_pos++］=t;
schedulｅｒ（ｐos，sｅq_poｓ);
pusｈ（＆S,t）；
｝
if （poｓ>＝ｌen ＆＆ isＥmpty(＆S))
｛　outSｅq（seq，len）; coｕｎt++; ｝
｝
int mａin(）{
inｔ i;
pｒintf（”\ｎplｅaｓe　input　tｈｅ num be ｓchedｕled: "）;
scanｆ(”%d”， &ｌen）; /＊用 lｅｎ 存储待调度得火车数量＊/
ｆｏr(i=0； i〈ｌen； i+＋)
d[i］='ａ'+i; /*创建火车编号,如 a、b、c、、、、等＊/
prｉntf（”ｔhｅ orｉginaｌ　seq is：”)；
outSeｑ(d，len);
initStacｋ(&S）；
schｅduler（0,0);
prｉnｔf（＂\n ｃoｕnt=%５d”， ｃｏunt）;
rｅｔurn ０；
｝
方法二:
解题思路：栈具有先进后出、后进先出得特点,因此,任何一个调度结果应该就是　1，２,3，
4 全排列中得一个元素。由于进栈得顺序就是由小到大得，所以出栈序列应该满足以下条件:对
于序列中得任何一个数其后面所有比它小得数应该就是倒序得，例如 4321 就是一个有效得出栈序
9

十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
列，１42３ 不就是一个有效得出栈结果(４ 后面比它小得两个数 ２,3 不就是倒序）。据此，本题可以
通过算法产生 n 个数得全排列，然后将满足出栈规则得序列输出.
产生　n　个数得全排列有递归与非递归两种实现算法.
产生全排列得递归算法:
设 R={r１，r２，…，rn｝就是要进行排列得 n 个元素,Ri＝Ｒ－｛ri}。集合 Ｘ 中元素得全排列记为
peｒm(X)。（ri）perｍ(X）表示在全排列 perｍ(X)得每一个排列前加上前缀 ri　得到得排列。R 得全排
列可归纳定义如下：
当 n＝１ 时,peｒm(R)＝（ｒ）,其中 r 就是集合　Ｒ 中惟一得元素；
当　ｎ>１ 时,perm(R)由（r1）perm（Ｒ１），（ｒ2）peｒm(R２),…，（ｒｎ）perm（Rｎ)构成。
依此递归定义，可设计产生 peｒｍ(R)得递归算法如下:
递归解法：(2_8_2、c)
#iｎcｌude＜stdio、h>
ｉnt cｏnt＝１；
ﻮ/＊全局变量,用于记录所有可能得出栈序列个数*/
void print(int str［］，iｎt n）；
/＊求整数序列 str［]从 k 到　n 得全排列*/
ｖoid perｍ（ｉnt str［］,int k,int ｎ）
｛ｉnt　i，temp；
if （k=＝ｎ－1） ｐrinｔ（stｒ,n）;
elｓｅ
{ for (i=k;i〈n;i+＋）
{ｔｅmp=str[k］；　 　 sｔｒ[k］=str［i]； 　stｒ［i］＝temp;
ｐeｒm（sｔr,k+１,n); /*递归调用*/
ｔemp=ｓtｒ［i］; 　 　ｓtr[ｉ］=sｔｒ[k]； 　　　stｒ[ｋ]=tｅmp;
｝
｝
}
/*本函数判断整数序列 sｔｒ[］就是否满足进出栈规则，若满足则输出＊/
voｉd print（ｉｎt　ｓtr[］,ｉnt n)
{int i，j，k，l,m，flag=1,b［2]；
for（ｉ=0;i<n；i++)
ﻮ／*对每个　sｔr[i]判断其后比它小得数就是否为降序序列*/
{ m＝0；
for（j=i+1；j<ｎ&&ｆｌag;j＋+)
if (ｓtr［i]＞str[j]） {if (m＝＝０) b[ｍ++］=ｓtr[j];
else ｛if （ｓｔr［ｊ］〉b[0］) ｛flaｇ=０;}
elsｅ b［0］=ｓtｒ［j］；
}
}
｝
iｆ（ｆｌａｇ）
ﻮ／＊满足出栈规则则输出 ｓtr［］中得序列*/
10

十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
｛
printf(” ％２d："，ｃont++）;
fｏｒ（i=0;ｉ<n；ｉ＋+)
ｐrinｔf（"%d”,str[i］）;
prｉｎtｆ（"\n"）;
}
}
ｉｎｔ maｉn()
{int stｒ[100]，ｎ,ｉ；
ｐrintf("iｎｐut　a　inｔ:"）； ／＊输出排列得元素个数＊/
scanf（＂%d",&ｎ）;
foｒ(i=0；i＜ｎ；ｉ++）　/*初始化排列集合＊/
ｓｔr［ｉ］=i+1；
ｐrintｆ("inpｕt the reｓulｔ：\ｎ＂)；
perｍ(str,0，n)；
ｐrintf(＂\n＂);
ｒeturn 0；
｝
当参与进出栈得元素个数为　４ 时,输出得结果如下图所示.
该算法执行得时间复杂度为 Ｏ（n!)。随着 n 得增大，算法得执行效率非常得低。
非递归解法:(2_8＿3、c)
对一组数穷尽所有排列,还可一种更直接得方法，将一个排列瞧作一个长整数,则所有排
列对应着一组整数，将这组整数按从小到大得顺序排成一个数列，从对应最小得整数开始,按
数列得递增顺序逐一列举每个排列对应得每一个整数，这能更有效地完成排列得穷举。从一个
排列找出对应数列得下一个排列可在当前排列得基础上作部分调整来实现。倘若当前排列为
1，2,４,6,５，３,并令其对应得长整数为 124653。要寻找比长整数 1２４6５３ 更大得排列，可从该排列
得最后一个数字顺序向前逐位考察，当发现排列中得某个数字比它前一个数字大时,如本例中
得　6 比它得前一位数字 4 大,则说明还有可能对应更大整数得排列.但为顺序从小到大列举出
所有得排列,不能立即调整得太大，如本例中将数字　6 与数字 4　交换得到得排列为　1２6453 就
不就是排列 124653 得下一个排列。为得到排列　１24６５3 得下一个排列，应从已考察过得那部分数
１１

十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
字中选出比数字　４ 大，但又就是它们中最小得那一个数字，比如数字 ５,与数字 ４ 交换.该数字
也就是从后向前考察过程中第一个比 4 大得数字，5　与 ４　交换后，得到排列　125643。在前面数字
１,2，5 固定得情况下，还应选择对应最小整数得那个排列,为此还需将后面那部分数字得排
列颠倒,如将数字 ６，4,３ 得排列顺序颠倒,得到排列 1,2，5，3,４，6，这才就是排列　1，2,4,6,
5,3 得下一个排列。按照以上想法可以编写非递归程序实现 n　个数得全排列，对满足进出栈
规则得排列则计数并输出。
／＊本程序输出 1 2　、、、　ｎ　个序列进栈出栈得序列*／
＃include　〈sｔｄio、h>
iｎt pl（iｎt n)
｛ iｎt ａ[1０0]；
iｎt ｆlag＝1,flag1=0；
ＦＩＬE *rf ；
inｔ i,j，k,x,couｎt=０；
rｆ = fopeｎ（"ｓtacｋ、ｔｘt＂， ”w＂） ;
for （i=1;i〈=n;ｉ++)
ａ［ｉ]=i;
whｉlｅ （flａg)
｛ fｌag1=1;
ﻮ/*最大处理范围为 ９９ 个数*／
/＊pl、txt 用于存放进出栈序列结果＊／
/＊初始序列＊/
/* 还剩余未输出得排列＊/
/* 判断本次排列就是否符合进栈出栈序列 ＊／
for （ｉ＝1；i<=n;i++)
｛ j＝ｉ+1;
ｗhiｌe　(j<=ｎ　＆＆ ａ［ｊ]＞a［i］）　j＋+； /＊ 找 a[i］后第一个比 a[i］小得元素 a[j］*/
k=j+１；
while （k〈=n）
ﻮ/＊　如果 a[j]后还有比　a［i]小且比 a[j］大得元素，则此排列无效＊/
{if （　a[k]　<a[ｉ］ && ａ［k]＞a[j］）　fｌag1=0；
k＋+;
｝
｝
ｉｆ (flａg1)
｛ ｆor （i=1；i<＝n;i++)
／*输出当前排列*/
{ printf（＂％4ｄ＂,a［i]); fprinｔf（rf,”%4ｄ”，a［i］）;}
ｐriｎtｆ("＼n"）； fprintf(rf，”\n”）；
couｎt++;
｝
ｉ=n；
ﻮ/*计数器加　１*/
/＊从后向前找相邻位置后大前小得元素值＊/
ｗhiｌe　(i〉1 &＆　a[i]〈ａ[i-1］） i—－；
ｉf （ｉ==1） fｌag=0; 　/＊未找到则结束＊/
ｅlse
｛ｊ=i—1;i=n；/＊　若找到,则在该位置得后面从右向左找第一个比该元素大得值＊/
while (i〉j　＆＆　a[i]<ａ［j］)　i-－；
12

十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
k＝a[j];
ａ［ｊ］＝a［i]；
a[i］=k;
k=ｊ＋1；
fｏr ( i=k+1；i〈＝n；i++）
/＊交换两元素得值*/
／＊对交换后后面得数据由小到大排序＊/
/*插入排序*/
｛ｊ＝i-1;
ｘ=a[i］；
wｈilｅ (j〉=k　&& ｘ＜a[j］） ｛ a［j+１］＝ａ[ｊ]； j－-；｝
a［j＋1］=x;
｝
｝
}
fclose（rf)；
rｅturn count;
｝
vｏid ｍain（）
｛int ｎ，m＝0；
/*返回排列总个数＊/
ｐｒｉnｔf(＂pleaｓe inpuｔ　n：”）;
sｃanｆ(＂％d"，&n）;
m=pｌ（ｎ）；
printf（”＼ｎm=％d”，m）;
ﻮ/*输入排列规模＊/
/＊输出满足进出栈得排列总个数＊/
｝
程序运行时如果输入 4,则输出得结果如下图所示。
该算法得时间复杂度也就是 O（ｎ!）。
结论:如果 ｎ 个数按编号由小到大得顺序进栈,进栈得过程中可以出栈，则所有可能得出栈序
列得总数为:
（2n)!
（n + １）n！n！
1３

十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
第　3　章
线性表得链式存储
3、1 选择题
（1）两个有序线性表分别具有 n 个元素与 m　个元素且　n≤ｍ,现将其归并成一个有序表，
其最少得比较次数就是（ A ）。
A.n
ﻮＢ．ｍ
ﻮC。n−１
ﻮＤ。ｍ+n
(2)非空得循环单链表　heａｄ　得尾结点（由 ｐ 所指向）满足( C
)。
A。p—〉next＝=NULL B。p＝=NULＬ Ｃ．p—>neｘｔ＝=ｈｅad
ﻮD.ｐ＝=head
(3）在带头结点得单链表中查找 x 应选择得程序体就是( Ｃ　).
Ａ.ｎode *p=head—>next； whilｅ （ｐ ＆& p-＞inｆo!＝x） ｐ=p—〉ｎext；
if (p->ｉnfo＝＝x）
retｕrn p eｌse　return　ＮUＬL；
Ｂ.nｏｄe *ｐ＝heａd； 　 　 whｉle　(p＆& p－〉iｎfo!=x） p＝p-〉next; return p;
C．nｏde *p=heaｄ－>next；
ﻮwhiｌe （p＆＆p－＞inｆo！=x) p=p-＞next； reｔurn p；
Ｄ.nｏdｅ　*p＝head; 　while （ｐ-〉ｉｎｆo！＝x） p=ｐ—>next ; rｅturｎ p；
（4）线性表若采用链式存储结构时，要求内存中可用存储单元得地址（　D　）。
Ａ。必须就是连续得
C.一定就是不连续得
ﻮＢ。部分地址必须就是连续得
D.连续不连续都可以
（5）在一个具有 n 个结点得有序单链表中插入一个新结点并保持单链表仍然有序得时间
复杂度就是（ B
)。
Ａ。O(1)
ﻮＢ.O（n)
Ｃ.O（ｎ2）
ﻮＤ。O（nlｏg２n）
(6）用不带头结点得单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队
尾结点，则在进行删除操作时( D ）.
A。仅修改队头指针
C.队头、队尾指针都要修改
ﻮB。仅修改队尾指针
D.队头，队尾指针都可能要修改
(7)若从键盘输入 ｎ 个元素,则建立一个有序单向链表得时间复杂度为（　B )。
Ａ。O（n）
ﻮB.O(n2)
ﻮC.Ｏ（ｎ3)
ﻮD.O（n×ｌｏg２ｎ)
（8)下面哪个术语与数据得存储结构无关（ Ｄ ).
A。顺序表
B.链表
ﻮC。散列表
ﻮＤ.队列
(９）在一个单链表中，若删除　p 所指结点得后续结点，则执行（ A　）。
A。p->neｘt=p-〉nexｔ-〉nｅxt；
C。p-＞ｎext=p->nｅxｔ;
ﻮＢ.p＝p-〉next； p-〉next=ｐ－>nexｔ—>nexｔ;
Ｄ.p =p—＞nｅｘt－>ｎext;
（10）在一个单链表中，若 p 所指结点不就是最后结点，在　ｐ 之后插入 ｓ 所指结点,则执行（　B ).
A．ｓ-〉next=p；p-〉next=s；
C.s—＞ｎｅxt=ｐ->neｘｔ;p=ｓ；
B.s-＞neｘt=ｐ-〉ｎｅｘｔ;p－>next=s；
Ｄ.p—〉ｎｅxｔ=s;s—＞nexｔ＝ｐ;
3、2 设计一个算法，求一个单链表中得结点个数。
【答】:单链表存储结构定义如下（相关文件:liｎkliｓt、h)
＃ｉncｌudｅ 〈sｔdｌib、h〉
14

十二五普通高等教育国家级本科规划教材
＃inclｕde ＜stdio、h>
typｅdeｆ sｔruct　noｄe
{ int data;
strｕct　ｎodｅ *nｅxｔ;
}linknode;
ｔypedｅf　ｌiｎknoｄe　＊linｋｌisｔ；
／＊尾插法创建带头结点得单链表*/
liｎｋlｉsｔ ｃreａｔlinｋlisｔ()
｛ ｌinkｌisｔ hｅad,r，ｓ；
int x;
head＝r＝(ｌinklist）malｌoｃ（sizｅoｆ(liｎknodｅ））;
pｒintf（"\n　请输入一组以　0 结束得整数序列:＼n”);
ｓcanｆ（"%ｄ",&x）;
ｗｈile (ｘ）
｛ 　ｓ=（linklist）malloｃ（ｓｉzeｏf（linｋnｏde）)；
s—〉daｔa＝x；
r－>neｘt=s；
r=ｓ；
ｓcanf(＂%d＂,&x）;
}
r-＞next=NUＬL；
ｒeturn head；
｝
/＊输出带头结点得单链表＊／
vｏｉd prｉnt(linkliｓｔ heaｄ)
{　 ｌiｎklｉst ｐ；
p=heａd-＞next；
ｐｒintf(”Lｉｓt is:\n”）；
while（p）
{　　prｉnｔf（"％5d”,p—>datａ);
p=ｐ－〉next；
｝
pｒintｆ("\n")；
｝
基于上述结构定义，求单链表中得结点个数得算法程序如下：
iｎｔ coｕnt（linklist　head)
高等学校精品资源共享课程
｛
ﻮint　ｃ=0；
linklｉst p＝head;
wｈile （ｐ）
1５

十二五普通高等教育国家级本科规划教材
高等学校精品资源共享课程
｛ｃ++；
p=ｐ－>neｘｔ;
}
return c；
}
3、3 设计一个算法，求一个带头结点单链表中得结点个数。
【答】：带头结点得单链表得存储结构定义同题 3、２，实现本题功能得算法程序如下(3＿3、c）
#includｅ ＂linkｌist、h"
inｔ ｃount（linｋｌist　heaｄ）
｛ ｉｎt　ｃ＝0；
linkｌist p=heａd—＞ｎｅxt;
ｗhiｌe （ｐ）
{c++;
p=p->nｅxt;
｝
return　ｃ；
}
ｍain（)
/*测试函数＊/
{linkｌist　ｈｅad;
ｈeaｄ=cｒeatlinｋｌｉｓｔ();
ｐrint（hｅａd）；
printf(”\nLenｇth　of head is：%d＂，coｕｎｔ（heａd））;
gｅｔch();
｝
当输入 5 个数据时，产生得输出结果如下图所示：
3、4 设计一个算法，在一个单链表中值为 ｙ 得结点前面插入一个值为 x　得结点.即使值为　x 得
新结点成为值为 y 得结点得前驱结点。
【答】：
#ｉncludｅ　”linklist、h”
vｏid insｅrｔ(linｋlisｔ　heａd,ｉnｔ ｙ，ｉnｔ x)
{／*在值为 ｙ　得结点前插入一个值为 x 得结点＊/
lｉnklisｔ pｒe,p,s；
pre=ｈead;
16

｝
十二五普通高等教育国家级本科规划教材
ｐ＝hｅａd->nｅｘｔ；
ｗhｉｌe （p　&＆ p－＞dａta！＝y)
｛ pre=p;
p=ｐ-〉next;
｝
if （p）／＊找到了值为　ｙ 得结点＊／
｛ s=（lｉｎｋｌｉst)ｍａlloc(sizeof（liｎknoｄe））;
s—〉ｄata=ｘ；
s->next=p;
prｅ-〉next=s;
｝
高等学校精品资源共享课程
ｖoｉｄ maiｎ（)
｛liｎklist　hｅaｄ;
iｎt　y,x；
hｅaｄ=cｒeatlinkliｓt（);
prｉnt(heａd）；
/*测试程序*/
/*创建单链表*/
／＊输出单链表*/
priｎtf(＂\n 请输入 y 与 x 得值：\ｎ”);
scanf("％ｄ %d",&ｙ，＆ｘ)；
insert(head,y,x）；
priｎt(ｈead);
｝
程序得一种运行结果如下图所示：
３、5 设计一个算法,判断一个单链表中各个结点值就是否有序.
【答】:
＃inclｕde　"ｌiｎkｌiｓt、h"
int iｓｓorｔed（linklist　ｈead,ｃhａr c）
/＊当参数 c=’a’时判断链表就是否为升序,当参数 ｃ='d’就是判断链表就是否为降序＊/
{ iｎｔ flag=1；
liｎklｉst p=hｅad-〉next;
ｓwｉtｃh （ｃ）
17

}
十二五普通高等教育国家级本科规划教材
{case ＇ａ'：/＊判断带头结点得单链表　heａｄ 就是否为升序*/
ｗhile (ｐ ＆＆p—>nexｔ ＆＆ flａg)
｛if　（p—>data〈＝p->ｎexｔ—>dａta） p=p-＞nｅｘt；
eｌsｅ ｆｌａg=0;
｝
breaｋ；
ｃaｓｅ ＇d’:/＊判断带头结点得单链表 heａd 就是否为降序＊/
whｉle (p　&&ｐ－＞nｅxt ＆&　ｆｌag）
｛iｆ (p—＞ｄａta＞=ｐ—>next-＞ｄａｔa） p=p－>neｘｔ;
elｓe ｆlａg=0;
}
break;
｝
ｒｅturn ｆlag；
高等学校精品资源共享课程
int ｍaiｎ(）
/*测试程序＊/
｛ linkｌiｓt ｈｅad；
ｈeaｄ=ｃｒeatlinkliｓt（)；
ｐｒint(hｅaｄ）；
iｆ （issｏrted(heａｄ，’a')）　pｒintf（”单链表　head 就是升序排列得！＼ｎ");
ｅlｓe
ｉf　（ｉｓｓoｒtｅd(head,'d＇））　ｐｒｉｎtf("单链表 heaｄ 就是降序排列得!\n")；