资源描述
<p><span id="_baidu_bookmark_start_0" style="display: none; line-height: 0px;"></span>第 1 章 绪 论
课后习题讲解
1、 填空
⑴( )就是数据得基本单位，在计算机程序中通常作为一个整体进行考虑与处理。
【解答】数据元素
⑵（ )就是数据得最小单位，( )就是讨论数据结构时涉及得最小数据单位。
【解答】数据项，数据元素
【分析】数据结构指得就是数据元素以及数据元素之间得关系。
⑶ 从逻辑关系上讲,数据结构主要分为（ )、( ）、（ )与（ ）。
【解答】集合，线性结构,树结构,图结构
⑷ 数据得存储结构主要有( )与( )两种基本方法,不论哪种存储结构，都要存储两方面得内容：( )
与( ）。
【解答】顺序存储结构,链接存储结构，数据元素，数据元素之间得关系
⑸ 算法具有五个特性，分别就是（ ）、（ )、（ ）、（ ）、（ )。
【解答】有零个或多个输入,有一个或多个输出，有穷性，确定性，可行性
⑹ 算法得描述方法通常有（ ）、( )、( ）与（ ）四种，其中,（ )被称为算法语言。
【解答】自然语言，程序设计语言，流程图，伪代码,伪代码
⑺ 在一般情况下,一个算法得时间复杂度就是（ )得函数。
【解答】问题规模
⑻ 设待处理问题得规模为n，若一个算法得时间复杂度为一个常数，则表示成数量级得形式为( ）,若
为n*log２5n，则表示成数量级得形式为( ）.
【解答】Ο(1),Ο(ｎloｇ2ｎ）
【分析】用大Ｏ记号表示算法得时间复杂度，需要将低次幂去掉，将最高次幂得系数去掉.
2、 选择题
⑴ 顺序存储结构中数据元素之间得逻辑关系就是由( )表示得，链接存储结构中得数据元素之间得逻辑关
系就是由（ ）表示得。
A 线性结构 B 非线性结构 C 存储位置 Ｄ 指针
【解答】C，Ｄ
【分析】顺序存储结构就就是用一维数组存储数据结构中得数据元素，其逻辑关系由存储位置(即元素在数
组中得下标)表示；链接存储结构中一个数据元素对应链表中得一个结点，元素之间得逻辑关系由结点中
得指针表示。
⑵ 假设有如下遗产继承规则：丈夫与妻子可以相互继承遗产;子女可以继承父亲或母亲得遗产；子女间不
能相互继承。则表示该遗产继承关系得最合适得数据结构应该就是（ )。
A 树 Ｂ 图 Ｃ 线性表 Ｄ 集合
【解答】B
【分析】将丈夫、妻子与子女分别作为数据元素,根据题意画出逻辑结构图。
⑶ 算法指得就是( )。
A 对特定问题求解步骤得一种描述,就是指令得有限序列。
B 计算机程序 C 解决问题得计算方法 D 数据处理
【解答】A
【分析】计算机程序就是对算法得具体实现;简单地说,算法就是解决问题得方法；数据处理就是通过算法完成
得。所以,只有A就是算法得准确定义.
⑷ 下面( )不就是算法所必须具备得特性.
A 有穷性 B 确切性 C 高效性 D 可行性
【解答】C
【分析】高效性就是好算法应具备得特性。
⑸ 算法分析得目得就是( ）,算法分析得两个主要方面就是（ )。
A 找出数据结构得合理性 B 研究算法中输入与输出得关系
C 分析算法得效率以求改进 D 分析算法得易读性与文档性
Ｅ 空间性能与时间性能 Ｆ 正确性与简明性
G 可读性与文档性 Ｈ 数据复杂性与程序复杂性
【解答】Ｃ，E
3、 判断题
⑴ 算法得时间复杂度都要通过算法中得基本语句得执行次数来确定.
【解答】错。时间复杂度要通过算法中基本语句执行次数得数量级来确定。
⑵ 每种数据结构都具备三个基本操作：插入、删除与查找。
【解答】错。如数组就没有插入与删除操作。此题注意就是每种数据结构。
⑶ 所谓数据得逻辑结构指得就是数据之间得逻辑关系。
【解答】错。就是数据之间得逻辑关系得整体。
⑷ 逻辑结构与数据元素本身得内容与形式无关.
【解答】对。因此逻辑结构就是数据组织得主要方面。
⑸ 基于某种逻辑结构之上得基本操作，其实现就是唯一得。
【解答】错。基本操作得实现就是基于某种存储结构设计得，因而不就是唯一得。
4、 分析以下各程序段，并用大O记号表示其执行时间。
【解答】⑴ 基本语句就是k=k＋10*ｉ，共执行了ｎ—２次,所以Ｔ（ｎ）＝Ｏ(n)。
⑵ 基本语句就是k=ｋ+10＊i,共执行了n次，所以T（n)＝O（ｎ）。
⑶ 分析条件语句，每循环一次，i＋ｊ 整体加1，共循环ｎ次,所以Ｔ（n)=Ｏ（ｎ)。
⑷ 设循环体共执行T(n）次，每循环一次，循环变量ｙ加1,最终T(ｎ)=y，即：
(Ｔ(n）＋1）2≤n,所以T(n)=Ｏ(n １/２）。
⑸ ｘ++就是基本语句,所以
5．设有数据结构（D，R）,其中D={1， 2， 3, ４， 5， 6｝，R=｛(１，2）,（2,３）,(2，４)，(３,4)，(3，5),(３，6），(4，５)，(4,6）}。
试画出其逻辑结构图并指出属于何种结构。
【解答】其逻辑结构图如图1—３所示，它就是一种图结构.
6、 为整数定义一个抽象数据类型，包含整数得常见运算，每个运算对应一个基本操作，每个基本操作得接
口需定义前置条件、输入、功能、输出与后置条件。
【解答】整数得抽象数据类型定义如下：
ＡDＴ iｎteｇer
Dａta
整数a：可以就是正整数(1, 2， ３， … )、负整数(-1, -２, －３, …)与零
Opｅrａtiｏｎ
Ｃonｓtructor
前置条件：整数a不存在
输入:一个整数ｂ
功能：构造一个与输入值相同得整数
输出：无
后置条件：整数a具有输入得值
Ｓet
前置条件：存在一个整数a
输入：一个整数b
功能:修改整数a得值,使之与输入得整数值相同
输出:无
后置条件：整数a得值发生改变
Add
前置条件:存在一个整数a
输入：一个整数b
功能：将整数a与输入得整数b相加
输出:相加后得结果
后置条件：整数a得值发生改变
Sub
前置条件:存在一个整数a
输入：一个整数b
功能：将整数a与输入得整数b相减
输出：相减得结果
后置条件:整数ａ得值发生改变
Multi
前置条件:存在一个整数a
输入：一个整数ｂ
功能：将整数ａ与输入得整数b相乘
输出:相乘得结果
后置条件:整数a得值发生改变
Dｉv
前置条件：存在一个整数a
输入：一个整数b
功能：将整数a与输入得整数ｂ相除
输出：若整数b为零，则抛出除零异常,否则输出相除得结果
后置条件：整数a得值发生改变
Moｄ
前置条件：存在一个整数a
输入:一个整数ｂ
功能：求当前整数与输入整数得模，即正得余数
输出:若整数b为零,则抛出除零异常,否则输出取模得结果
后置条件:整数a得值发生改变
Eｑual
前置条件:存在一个整数ａ
输入:一个整数ｂ
功能：判断整数a与输入得整数ｂ就是否相等
输出:若相等返回１,否则返回0
后置条件:整数a得值不发生改变
enｄAＤＴ
7、 求多项式A(x）得算法可根据下列两个公式之一来设计:
⑴ A(x）=anxn+an-1xn—1+…+a1x+ａ0
⑵ Ａ（ｘ)=(…(aｎx＋aｎ-１)x+…+a1）ｘ）+a０
根据算法得时间复杂度分析比较这两种算法得优劣。
【解答】第二种算法得时间性能要好些。第一种算法需执行大量得乘法运算,而第二种算法进行了优化，
减少了不必要得乘法运算。
8、 算法设计(要求：算法用伪代码与C++描述，并分析最坏情况下得时间复杂度）
⑴ 对一个整型数组Ａ[n］设计一个排序算法。
【解答】下面就是简单选择排序算法得伪代码描述。
下面就是简单选择排序算法得Ｃ+＋描述.
分析算法,有两层嵌套得fｏr循环，所以, .
⑵ 找出整型数组Ａ［ｎ]中元素得最大值与次最大值。
【解答】算法得伪代码描述如下：
算法得Ｃ++描述如下：
分析算法,只有一层循环，共执行n－2次，所以，Ｔ（n)=O（n)。
学习自测及答案
1．顺序存储结构得特点就是（ ),链接存储结构得特点就是( ）.
【解答】用元素在存储器中得相对位置来表示数据元素之间得逻辑关系，用指示元素存储地址得指针表示
数据元素之间得逻辑关系。
2、 算法在发生非法操作时可以作出处理得特性称为（ ）。
【解答】健壮性
3、 常见得算法时间复杂度用大O记号表示为:常数阶( ）、对数阶（ )、线性阶 （ ）、平方阶（ )与指数阶（ ）。
【解答】Ｏ（1），Ｏ（loｇ2n）,Ｏ(ｎ）,O（ｎ2）,Ｏ(２n）
４．将下列函数按它们在n 时得无穷大阶数,从小到大排列.
ｎ, ｎ-n3+7n5, ｎlogn， ２n/2, n3， log2n， n1/2+ｌog2ｎ, (３／2）n， ｎ!， n2+lｏｇ2n
【解答】log2n, ｎ1/2+log2n， n, ｎlog2n, n2+log2n， n3， n-n3＋7n5， 2n/２， （３/2)n, n!
5．试描述数据结构与抽象数据类型得概念与程序设计语言中数据类型概念得区别。
【解答】数据结构就是指相互之间存在一定关系得数据元素得集合.而抽象数据类型就是指一个数据结构以及
定义在该结构上得一组操作。程序设计语言中得数据类型就是一个值得集合与定义在这个值集上一组操作得
总称。抽象数据类型可以瞧成就是对数据类型得一种抽象.
6、 对下列用二元组表示得数据结构,试分别画出对应得逻辑结构图,并指出属于何种结构。
⑴ Ａ=（D，R)， 其中D=｛a１, a2， a3， a4},R＝{ ｝
⑵ B=（Ｄ,R）, 其中D={a， b, c， ｄ， ｅ, f}，R＝{，，,,｝
⑶ C=（ Ｄ，R）,其中D=｛a,b，c,ｄ，e,f},R={，，，,,}
⑷ D=(D，Ｒ)， 其中D={1, 2, ３， 4, 5, 6｝,
Ｒ＝｛(1， 2），(1， ４），(２， 3),(2， 4)，（3， 4）,（3， ５)，（３， 6）,(4, 6）｝
【解答】⑴ 属于集合,其逻辑结构图如图1—4（a)所示；⑵ 属于线性结构，其逻辑结构图如图1—4（b）所示;
⑶ 属于树结构,其逻辑结构图如图1-4（c）所示；⑷ 属于图结构，其逻辑结构图如图1-4(d）所示。
７、 求下列算法得时间复杂度.
ｃoｕnt=０； ｘ=１；
wｈiｌe (ｘ {
x＊=2;
counｔ++;
｝
ｒeｔurn coｕｎt；
【解答】Ｏ(ｌog2ｎ）
第 ２ 章 线性表
课后习题讲解
１、 填空
⑴ 在顺序表中,等概率情况下,插入与删除一个元素平均需移动( )个元素,具体移动元素得个数与（ )
与( )有关。
【解答】表长得一半,表长，该元素在表中得位置
⑵ 顺序表中第一个元素得存储地址就是１00,每个元素得长度为2,则第５个元素得存储地址就是( ）。
【解答】1０8
【分析】第5个元素得存储地址=第1个元素得存储地址＋（5－1）×2=108
⑶ 设单链表中指针p 指向结点A,若要删除Ａ得后继结点(假设A存在后继结点）,则需修改指针得操
作为( ).
【解答】p-＞next=（p—>next）-＞nexｔ
⑷ 单链表中设置头结点得作用就是（ ）。
【解答】为了运算方便
【分析】例如在插入与删除操作时不必对表头得情况进行特殊处理.
⑸ 非空得单循环链表由头指针ｈeａd指示,则其尾结点(由指针p所指）满足( )。
【解答】ｐ－〉nｅｘt=ｈｅad
【分析】如图2—8所示。
⑹ 在由尾指针reａr指示得单循环链表中,在表尾插入一个结点s得操作序列就是（ );删除开始结点得操
作序列为( ）.
【解答】s—＞nｅxt =reａr—＞ｎext; reａr->next =s； rｅar ＝ｓ;
q=ｒeａr-＞neｘt->ｎｅｘt; reaｒ—>ｎext－＞neｘt=q—>nｅxt; delete ｑ；
【分析】操作示意图如图2－9所示：
⑺ 一个具有ｎ个结点得单链表，在指针p所指结点后插入一个新结点得时间复杂度为（ )；在给定值为
x得结点后插入一个新结点得时间复杂度为( ).
【解答】Ο(１）,Ο(n)
【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1);而在给定值为x得结点
后插入一个新结点需要先查找值为x得结点，所以时间复杂度为Ο（n)。
⑻ 可由一个尾指针唯一确定得链表有( ）、（ ）、（ )。
【解答】循环链表，循环双链表，双链表
2、 选择题
⑴ 线性表得顺序存储结构就是一种（ )得存储结构,线性表得链接存储结构就是一种( ）得存储结构.
Ａ 随机存取 B 顺序存取 C 索引存取 D 散列存取
【解答】A,Ｂ
【分析】参见2。2.1.
⑵ 线性表采用链接存储时,其地址（ ）.
A 必须就是连续得 B 部分地址必须就是连续得
C 一定就是不连续得 D 连续与否均可以
【解答】Ｄ
【分析】线性表得链接存储就是用一组任意得存储单元存储线性表得数据元素,这组存储单元可以连续,也
可以不连续，甚至可以零散分布在内存中任意位置。
⑶ 单循环链表得主要优点就是( ）。
A 不再需要头指针了
B 从表中任一结点出发都能扫描到整个链表；
C 已知某个结点得位置后，能够容易找到它得直接前趋;
Ｄ 在进行插入、删除操作时，能更好地保证链表不断开。
【解答】B
⑷ 链表不具有得特点就是( )。
Ａ 可随机访问任一元素 B 插入、删除不需要移动元素
Ｃ 不必事先估计存储空间 D 所需空间与线性表长度成正比
【解答】Ａ
⑸ 若某线性表中最常用得操作就是取第i 个元素与找第ｉ个元素得前趋,则采用( )存储方法最节省时间。
A 顺序表 B 单链表 C 双链表 D 单循环链表
【解答】A
【分析】线性表中最常用得操作就是取第i 个元素，所以,应选择随机存取结构即顺序表，同时在顺序表中
查找第ｉ个元素得前趋也很方便.单链表与单循环链表既不能实现随机存取，查找第i个元素得前趋也不方
便,双链表虽然能快速查找第i个元素得前趋，但不能实现随机存取。
⑹ 若链表中最常用得操作就是在最后一个结点之后插入一个结点与删除第一个结点,则采用（ )存储方法
最节省时间.
A 单链表 Ｂ 带头指针得单循环链表 C 双链表 D 带尾指针得单循环链表
【解答】D
【分析】在链表中得最后一个结点之后插入一个结点需要知道终端结点得地址，所以,单链表、带头指针
得单循环链表、双链表都不合适，考虑在带尾指针得单循环链表中删除第一个结点，其时间性能就是O(1)，
所以,答案就是Ｄ 。
⑺ 若链表中最常用得操作就是在最后一个结点之后插入一个结点与删除最后一个结点,则采用( ）存储方
法最节省运算时间。
A 单链表 B 循环双链表 C单循环链表 D 带尾指针得单循环链表
【解答】Ｂ
【分析】在链表中得最后一个结点之后插入一个结点需要知道终端结点得地址,所以,单链表、单循环链
表都不合适，删除最后一个结点需要知道终端结点得前驱结点得地址,所以,带尾指针得单循环链表不合
适，而循环双链表满足条件。
⑻ 在具有n个结点得有序单链表中插入一个新结点并仍然有序得时间复杂度就是（ ）.
A Ｏ（1） B Ｏ（n) C O（ｎ2） Ｄ O(nlｏg2n）
【解答】B
【分析】首先应顺序查找新结点在单链表中得位置。
⑼ 对于ｎ个元素组成得线性表，建立一个有序单链表得时间复杂度就是（ )。
A O（1) B O（n） C O（n2） D O（nｌog2ｎ）
【解答】C
【分析】该算法需要将ｎ个元素依次插入到有序单链表中，而插入每个元素需O(n)。
⑽ 使用双链表存储线性表，其优点就是可以（ ）。
A 提高查找速度 B 更方便数据得插入与删除
Ｃ 节约存储空间 D 很快回收存储空间
【解答】Ｂ
【分析】在链表中一般只能进行顺序查找，所以,双链表并不能提高查找速度，因为双链表中有两个指针
域，显然不能节约存储空间，对于动态存储分配，回收存储空间得速度就是一样得.由于双链表具有对称性,
所以,其插入与删除操作更加方便。
⑾ 在一个单链表中,已知q所指结点就是ｐ所指结点得直接前驱，若在q与p之间插入s所指结点，则执
行（ ）操作。
Ａ s-＞neｘt=ｐ—〉nｅxｔ; p—〉nｅｘt＝ｓ； Ｂ ｑ—＞nexｔ=s； ｓ—〉neｘｔ＝p；
C p—>neｘt=s-＞next; s—>nｅｘｔ=ｐ; Ｄ ｐ—＞neｘｔ=s; ｓ－＞ｎext=ｑ;
【解答】B
【分析】注意此题就是在q与p之间插入新结点，所以,不用考虑修改指针得顺序。
⑿ 在循环双链表得p所指结点后插入s所指结点得操作就是( ）.
A ｐ－>ｎexｔ＝s; s-〉prior=p; p—>ｎｅxｔ－〉pｒioｒ=s； s—>next＝p->next;
B p－〉nｅxt=ｓ； ｐ—〉nexｔ—〉ｐrior=s; s—〉prior=p； s－〉nｅxt=p->next;
C ｓ->ｐrior=p; s—＞next=p->neｘt； ｐ—〉neｘｔ＝s； p-〉next->priｏr=s；
D s->pｒｉｏｒ＝ｐ； s—＞ｎｅｘｔ=p—＞nｅxｔ; p－>nｅxt—>prｉoｒ=s； p—>ｎext=s
【解答】D
【分析】在链表中,对指针得修改必须保持线性表得逻辑关系,否则，将违背线性表得逻辑特征,图2-1０
给出备选答案Ｃ与D得图解。
3、 判断题
⑴ 线性表得逻辑顺序与存储顺序总就是一致得.
【解答】错。顺序表得逻辑顺序与存储顺序一致,链表得逻辑顺序与存储顺序不一定一致。
⑵ 线性表得顺序存储结构优于链接存储结构。
【解答】错。两种存储结构各有优缺点.
⑶ 设p，q就是指针,若p=q，则*p=＊ｑ。
【解答】错。p=q只能表示p与q指向同一起始地址，而所指类型则不一定相同.
⑷ 线性结构得基本特征就是：每个元素有且仅有一个直接前驱与一个直接后继。
【解答】错。每个元素最多只有一个直接前驱与一个直接后继，第一个元素没有前驱，最后一个元素没有
后继。
⑸ 在单链表中，要取得某个元素,只要知道该元素所在结点得地址即可,因此单链表就是随机存取结构。
【解答】错.要找到该结点得地址，必须从头指针开始查找，所以单链表就是顺序存取结构。
４．请说明顺序表与单链表各有何优缺点，并分析下列情况下,采用何种存储结构更好些.
⑴ 若线性表得总长度基本稳定，且很少进行插入与删除操作,但要求以最快得速度存取线性表中得元素。
⑵ 如果ｎ个线性表同时并存，并且在处理过程中各表得长度会动态发生变化。
⑶ 描述一个城市得设计与规划。
【解答】顺序表得优点：① 无需为表示表中元素之间得逻辑关系而增加额外得存储空间；② 可以快速地
存取表中任一位置得元素(即随机存取)。顺序表得缺点:① 插入与删除操作需移动大量元素;② 表得
容量难以确定；③ 造成存储空间得“碎片”。
单链表得优点:① 不必事先知道线性表得长度；② 插入与删除元素时只需修改指针，不用移动元素.单
链表得缺点:① 指针得结构性开销;② 存取表中任意元素不方便，只能进行顺序存取.
⑴ 应选用顺序存储结构.因为顺序表就是随机存取结构，单链表就是顺序存取结构。本题很少进行插入与删除
操作,所以空间变化不大,且需要快速存取，所以应选用顺序存储结构.
⑵ 应选用链接存储结构。链表容易实现表容量得扩充，适合表得长度动态发生变化。
⑶ 应选用链接存储结构。因为一个城市得设计与规划涉及活动很多,需要经常修改、扩充与删除各种信息,
才能适应不断发展得需要。而顺序表得插入、删除得效率低,故不合适。
5.算法设计
⑴ 设计一个时间复杂度为O(n）得算法，实现将数组Ａ[n］中所有元素循环右移k个位置。
【解答】算法思想请参见主教材第一章思想火花。下面给出具体算法。
分析算法,第一次调用Reverｓe函数得时间复杂度为O（k）,第二次调用Revｅｒse函数得时间复杂度为O(n—ｋ)，
第三次调用Reｖerｓe函数得时间复杂度为O（ｎ),所以，总得时间复杂度为O（n).
⑵ 已知数组A［ｎ]中得元素为整型，设计算法将其调整为左右两部分,左边所有元素为奇数，右边所有元
素为偶数，并要求算法得时间复杂度为Ｏ(ｎ)。
【解答】从数组得两端向中间比较,设置两个变量i与ｊ，初始时i=0,j=ｎ—1,若A[i］为偶数并且A［ｊ］为奇
数,则将A[ｉ］与A［j］交换.具体算法如下:
分析算法,两层循环将数组扫描一遍,所以,时间复杂度为Ｏ（n)。
⑶ 试编写在无头结点得单链表上实现线性表得插入操作得算法，并与带头结点得单链表上得插入操作得实
现进行比较。
【解答】参见2.2。3.
⑷ 试分别以顺序表与单链表作存储结构,各写一实现线性表就地逆置得算法。
【解答】顺序表得逆置,即就是将对称元素交换，设顺序表得长度为ｌenｇｔh，则将表中第ｉ个元素与第ｌｅｎgtｈ-i—１
个元素相交换.具体算法如下:
单链表得逆置请参见2。２.4算法2－4与算法２-6。
⑸ 假设在长度大于1得循环链表中,即无头结点也无头指针,s为指向链表中某个结点得指针,试编写算
法删除结点s得前趋结点。
【解答】利用单循环链表得特点,通过指针s可找到其前驱结点ｒ以及r得前驱结点p,然后将结点ｒ删除,
如图2－11所示，具体算法如下：
⑹ 已知一单链表中得数据元素含有三类字符：字母、数字与其她字符。试编写算法,构造三个循环链表，
使每个循环链表中只含同一类字符。
【解答】在单链表A中依次取元素,若取出得元素就是字母，把它插入到字母链表B 中，若取出得元素就是数
字,则把它插入到数字链表D中，直到链表得尾部,这样表Ｂ,D，A中分别存放字母、数字与其她字符.
具体算法如下：
⑺ 设单链表以非递减有序排列，设计算法实现在单链表中删去值相同得多余结点。
【解答】从头到尾扫描单链表,若当前结点得元素值与后继结点得元素值不相等，则指针后移;否则删除
该后继结点。具体算法如下:
⑻ 判断带头结点得双循环链表就是否对称.
【解答】设工作指针ｐ与ｑ分别指向循环双链表得开始结点与终端结点，若结点p与结点ｑ得数据域相等,
则工作指针p后移，工作指针q前移，直到指针p与指针q指向同一结点(循环双链表中结点个数为奇数),
或结点ｑ成为结点p得前驱（循环双链表中结点个数为偶数）.如图２－12所示。
学习自测及答案
１、 已知一维数组Ａ采用顺序存储结构,每个元素占用4个存储单元，第9个元素得地址为１44，则第一个
元素得地址就是（ )。
A １08 B 180 Ｃ １76 D １12
【解答】D
2.在长度为n得线性表中查找值为ｘ得数据元素得时间复杂度为： （ ）。
A O（0) Ｂ Ｏ(１） C O（n) D O(n2)
【解答】Ｃ
3.在一个长度为n得顺序表得第ｉ(1≤i≤ｎ+1）个元素之前插入一个元素，需向后移动（ ）个元素，删除
第i（1≤i≤n)个元素时,需向前移动( ）个元素.
【解答】n—i+1,n-i
４．在单链表中,除了头结点以外，任一结点得存储位置由（ )指示.
【解答】其前趋结点得指针域
5．当线性表采用顺序存储结构时，其主要特点就是( ).
【解答】逻辑结构中相邻得结点在存储结构中仍相邻
6.在双链表中,每个结点设置了两个指针域，其中一个指向( ）结点,另一个指向( )结点。
【解答】前驱，后继
7。设A就是一个线性表(a１， ａ2, …， an）,采用顺序存储结构，则在等概率得前提下,平均每插入一个元素
需要移动得元素个数为多少？若元素插在ai与aｉ+1之间（1≤i≤n)得概率为 ,则平均每插
入一个元素所要移动得元素个数又就是多少?
【解答】
，
。
8．线性表存放在整型数组A［aｒrsｉze］得前ｅlenum 个单元中，且递增有序。编写算法，将元素x插入到线
性表得适当位置上，以保持线性表得有序性,并且分析算法得时间复杂度.
【解答】本题就是在一个递增有序表中插入元素x，基本思路就是从有序表得尾部开始依次取元素与x比较,
若大于x，此元素后移一位,再取它前面一个元素重复上述步骤；否则,找到插入位置,将x插入.具体
算法如下：
9、 已知单链表中各结点得元素值为整型且递增有序,设计算法删除链表中所有大于mｉｎｋ且小于mａxk得
所有元素，并释放被删结点得存储空间。
【解答】因为就是在有序单链表上得操作，所以，要充分利用其有序性.在单链表中查找第一个大于mink
得结点与第一个小于mａｘk得结点,再将二者间得所有结点删除。
10．设单循环链表Ｌ１，对其遍历得结果就是：ｘ1, x2， x3，…， xn—１, xn。请将该循环链表拆成两个单循环链表
Ｌ1与L2，使得L1中含有原L1表中序号为奇数得结点且遍历结果为:x1， ｘ3,… ；L2中含有原L1表中序
号为偶数得结点且遍历结果为:… ， x4, x2。
【解答】算法如下:
第 3 章 特殊线性表--栈、队列与串
课后习题讲解
１、 填空
⑴ 设有一个空栈,栈顶指针为1000H，现有输入序列为1、2、３、４、5， 经过ｐush，push,ｐop，pusｈ，
ｐop，pｕｓh,pusｈ后，输出序列就是（ )，栈顶指针为( )。
【解答】23，１003H
⑵ 栈通常采用得两种存储结构就是（ ）；其判定栈空得条件分别就是( ）,判定栈满得条件分别就是（ ）。
【解答】顺序存储结构与链接存储结构(或顺序栈与链栈),栈顶指针top= －1与tｏp＝NＵＬL，栈顶指针
toｐ等于数组得长度与内存无可用空间
⑶( ）可作为实现递归函数调用得一种数据结构。
【解答】栈
【分析】递归函数得调用与返回正好符合后进先出性.
⑷ 表达式a＊(b+c）—d得后缀表达式就是（ )。
【解答】aｂｃ＋*d-
【分析】将中缀表达式变为后缀表达式有一个技巧:将操作数依次写下来，再将算符插在它得两个操作数
得后面。
⑸ 栈与队列就是两种特殊得线性表,栈得操作特性就是（ ）,队列得操作特性就是( ），栈与队列得主要区别
在于（ ）。
【解答】后进先出,先进先出，对插入与删除操作限定得位置不同
⑹ 循环队列得引入就是为了克服( ).
【解答】假溢出
⑺ 数组Ｑ［n］用来表示一个循环队列，fｒont为队头元素得前一个位置,rear为队尾元素得位置，计算队列
中元素个数得公式为( )。
【解答】（rｅar－frｏnt+n)% n
【分析】也可以就是(rear—fｒont）％ n,但ｒear－fｒonｔ得结果可能就是负整数,而对一个负整数求模，其结果
在不同得编译器环境下可能会有所不同。
⑻ 用循环链表表示得队列长度为ｎ，若只设头指针，则出队与入队得时间复杂度分别就是( ）与（ ).
【解答】O(１），Ｏ（n）
【分析】在带头指针得循环链表中,出队即就是删除开始结点，这只需修改相应指针;入队即就是在终端结点
得后面插入一个结点，这需要从头指针开始查找终端结点得地址。
⑼ 串就是一种特殊得线性表，其特殊性体现在( ）.
【解答】数据元素得类型就是一个字符
⑽ 两个串相等得充分必要条件就是( )。
【解答】长度相同且对应位置得字符相等
【分析】例如”abc＂≠”aｂc "，”abc"≠”bｃa”。
2、 选择题
⑴ 若一个栈得输入序列就是１，2,３，…，n,输出序列得第一个元素就是n,则第i个输出元素就是（ ）。
A 不确定 B ｎ－i C n—i—1 D n-ｉ+1
【解答】D
【分析】此时，输出序列一定就是输入序列得逆序。
⑵ 设栈S与队列Q得初始状态为空,元素ｅ1、e2、e3、e4、ｅ５、e６依次通过栈S,一个元素出栈后即进
入队列Ｑ,若6个元素出队得顺序就是e2、e4、e３、e6、e5、e1,则栈S得容量至少应该就是( ）。
Ａ 6 Ｂ 4 Ｃ 3 D 2
【解答】C
【分析】由于队列具有先进先出性，所以,此题中队列形同虚设，即出栈得顺序也就是e2、e4、e3、ｅ6、ｅ5、
e1。
⑶ 一个栈得入栈序列就是１,2,3，4，5，则栈得不可能得输出序列就是( ）.
A 54321 Ｂ 453２1 C 435１2 D 12345
【解答】C
【分析】此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且就是升序（指得就是元素得序
号)得两个元素。
⑷ 设计一个判别表达式中左右括号就是否配对得算法，采用（ ）数据结构最佳
A 顺序表 B 栈 C 队列 D 链表
【解答】Ｂ
【分析】每个右括号与它前面得最后一个没有匹配得左括号配对,因此具有后进先出性。
⑸ 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该就是一个( )
结构。
A 栈 Ｂ队列 Ｃ 数组 Ｄ线性表
【解答】B
【分析】先进入打印缓冲区得文件先被打印，因此具有先进先出性。
⑹ 一个队列得入队顺序就是1，２，3,４，则队列得输出顺序就是（ ）。
A 432１ B 1２34 C 1432 D ３241
【解答】B
【分析】队列得入队顺序与出队顺序总就是一致得.
⑺ 栈与队列得主要区别在于（ ）.
A 它们得逻辑结构不一样 B 它们得存储结构不一样
C 所包含得运算不一样 D 插入、删除运算得限定不一样
【解答】D
【分析】栈与队列得逻辑结构都就是线性得,都有顺序存储与链接存储，有可能包含得运算不一样，但不就是
主要区别,任何数据结构在针对具体问题时包含得运算都可能不同。
⑻ 设数组S[ｎ］作为两个栈S1与S2得存储空间,对任何一个栈只有当S[ｎ]全满时才不能进行进栈操作.
为这两个栈分配空间得最佳方案就是（ )。
A S1得栈底位置为０，S2得栈底位置为n-1
Ｂ S１得栈底位置为0,S2得栈底位置为n/2
Ｃ S１得栈底位置为０，S2得栈底位置为ｎ
D S1得栈底位置为０，S2得栈底位置为1
【解答】A
【分析】两栈共享空间首先两个栈就是相向增长得，栈底应该分别指向两个栈中得第一个元素得位置,并注
意C++中得数组下标就是从0开始得。
⑼ 设有两个串p与q，求ｑ在ｐ中首次出现得位置得运算称作（ ）.
Ａ 连接 B 模式匹配 C 求子串 D 求串长
【解答】B
3、 判断题
⑴ 有n个元素依次进栈，则出栈序列有(n-1）/２种。
【解答】错.应该有 种。
⑵ 栈可以作为实现过程调用得一种数据结构。
【解答】对。只要操作满足后进先出性,都可以采用栈作为辅助数据结构。
⑶ 在栈满得情况下不能做进栈操作,否则将产生“上溢".
【解答】对.
⑷ 在循环队列中,front指向队头元素得前一个位置，rear指向队尾元素得位置，则队满得条件就是
ｆrｏnt＝rear。
【解答】错。这就是队空得判定条件，在循环队列中要将队空与队满得判定条件区别开.
⑸ 空串与空格串就是相同得.
【解答】错。空串得长度为零,而空格串得长度不为0，其长度就是串中空格得个数。
４、 设有一个栈,元素进栈得次序为A,B,C，Ｄ，E,能否得到如下出栈序列，若能，请写出操作序列,若
不能，请说明原因。
⑴ C,E，A，B，D
⑵ C，Ｂ，A,D,E
【解答】⑴不能,因为在C、E出栈得情况下,A一定在栈中，而且在Ｂ得下面，不可能先于Ｂ出栈。⑵
可以，设Ｉ为进栈操作,O为入栈操作,则其操作序列为IＩＩOOOIOIO。
５、 举例说明顺序队列得“假溢出”现象。
【解答】假设有一个顺序队列,如图３—6所示，队尾指针rear=４,队头指针ｆront＝１,如果再有元素入队,
就会产生“上溢”，此时得“上溢"又称为“假溢出”，因为队列并不就是真得溢出了，存储队列得数组中还有２个
存储单元空闲，其下标分别为0与1。
6、 在操作序列pｕｓh(１）、push(2)、pop、pｕｓｈ（５）、puｓh(7）、ｐｏp、push（6)之后,栈顶元素与栈底元素分
别就是什么？（ｐush（k）表示整数ｋ入栈，ｐop表示栈顶元素出栈。）
【解答】栈顶元素为6，栈底元素为1。其执行过程如图3－7所示。
７. 在操作序列EnQuｅue(1）、 EｎQueue（3）、 DｅQｕeue、EｎＱueｕe（５）、EｎQueue（７）、ＤeQueue、EnQｕeue（9）
之后，队头元素与队尾元素分别就是什么？(ＥnＱueue（ｋ)表示整数k入队,DｅQueｕe表示队头元素出队）.
【解答】队头元素为5，队尾元素为9。其执行过程如图3－8所示。
8。空串与空格串有何区别？串中得空格符有何意义?空串在串处理中有何作用?
【解答】不含任何字符得串称为空串，其长度为零。仅含空格得串称为空格串,它得长度为串中空格符得
个数。串中得空格符可用来分隔一般得字符，便于人们识别与阅读,但计算串长时应包括这些空格符.空
串在串处理中可作为任意串得子串。
９、 算法设计
⑴ 假设以不带头结点得循环链表表示队列,并且只设一个指针指向队尾结点，但不设头指针。试设计相应
得入队与出队得算法。
【解答】出队操作就是在循环链表得头部进行,相当于删除开始结点，而入队操作就是在循环链表得尾部进行,
相当于在终端结点之后插入一个结点。由于循环链表不带头结点，需要处理空表得特殊情况。
入队算法如下：
出队算法如下:
⑵ 设顺序栈S中有2n个元素，从栈顶到栈底得元素依次为a2ｎ,a2n-1，…，a1,要求通过一个循环队列
重新排列栈中元素,使得从栈顶到栈底得元素依次为a2ｎ，a2n－2，…，ａ2,a2n－1，a2n－3，…，a１，请设
计算法实现该操作,要求空间复杂度与时间复杂度均为O(n）。
【解答】操作步骤为:
① 将所有元素出栈并入队；
② 依次将队列元素出队，如果就是偶数结点，则再入队，如果就是奇数结点，则入栈；
③ 将奇数结点出栈并入队；
④ 将偶数结点出队并入栈；
⑤ 将所有元素出栈并入队；
⑥ 将所有元素出队并入栈即为所求。
⑶ 用顺序存储结构存储串S，编写算法删除S中第 ｉ个字符开始得连续ｊ个字符。
【解答】先判断串S中要删除得内容就是否存在,若存在，则将第ｉ＋ｊ－１之后得字符前移j个位置。算法如下:
⑷ 对于采用顺序存储结构得串Ｓ，编写一个函数删除其值等于ch得所有字符。
【解答】从后向前删除值为ch得所有元素，这样所有移动得元素中没有值为cｈ得元素，能减少移动元素
得次数,提高算法得效率。算法如下：
⑸ 对串得模式匹配ＫMP算法设计求模式滑动位置得next函数.
【解答】参见３.2。５
学习自测及答案
１.在一个具有n个单元得顺序栈中，假定以地址低端(即下标为0得单元）作为栈底,以top作为栈顶指
针,当出栈时，ｔop得变化为( ）.
A 不</p>
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
