数据结构c++版课后习题解析.doc

第 1　章 绪 论ﻩ１
1、1 本章导学 １
1、2 习题解析 2
第 2　章 线性表 9
2、１　本章导学 ９
2、２　习题解析ﻩ10
第 3　章　　栈与队列 1９
3、1　本章导学 19
3、2 习题解析 ２0
第　4 章 　字符串与多维数组 26
4、1 本章导学 ２６
4、2 习题解析 2７
第 5 章 树与二叉树 ３2
5、1 本章导学ﻩ32
5、２ 习题解析 33
第 6 章　图 43
6、1 本章导学 43
6、２ 习题解析ﻩ44
第 7 章 查找技术 56
７、１ 本章导学 56
７、2　习题解析 ５７
第 8 章 排序技术 67
8、1 本章导学ﻩ67
8、２　习题解析ﻩ68
第 ９ 章　索引技术 78
9、1 本章导学 78
９、2 习题解析 78
第 1 章　绪 　论
１、１ 本章导学
１、 知识结构图
　 本章得知识结构如图1-1所示，其中第二层得椭圆代表本章得学习主线。
⑴数据
⑵数据元素
⑶数据结构
⑷抽象数据类型
⑴逻辑结构
⑵数据结构
得分类
⑴存储结构
⑵常用存储
方法
⑴算法
⑵算法特性
⑶评价算法
⑷描述算法
⑴问题规模
⑵基本语句
⑶时间复杂度
⑷大O记号
图1-1 知识结构图
绪 论
数据结构
算 法
基本概念
逻辑结构

存储结构
基本概念
算法分析
关 系

2、　学习要点
对本章得学习要从两条主线出发,一条主线就是数据结构,包括数据结构得相关概念及含义,另一条主线就是算法,包括算法得相关概念、描述方法以及时间复杂度得分析方法。
在学习数据结构时要抓住两个方面：逻辑结构与存储结构，并注意把握二者之间得关系。在学习算法时，要以算法得概念与特性为基本点，并在以后得学习中注意提高算法设计得能力。对于算法时间性能得分析，要将注意力集中在增长率上,即基本语句执行次数得数量级，在设计算法时，养成分析算法时间性能得习惯，进而有效地改进算法得效率。
1、2 习题解析
1、 填空
（1)( )就是数据得基本单位，在计算机程序中通常作为一个整体进行考虑与处理.
【解答】数据元素
（２)（　 ）就是数据得最小单位，（ 　　 )就是讨论数据结构时涉及得最小数据单位。
【解答】数据项，数据元素
【分析】数据结构指得就是数据元素以及数据元素之间得关系.
(3)从逻辑关系上讲，数据结构主要分为( 　 )、( 　 ）、（ 　 ）与（ 　 　　 ）。
【解答】集合，线性结构，树结构、图结构
(4)数据得存储结构主要有（ ）与（ 　　 ）两种基本方法，不论哪种存储结构，都要存储两方面得内容:( 　 　　）与（ 　 ）。
【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间得关系
(５）算法具有五个特性，分别就是（　 ）、( ）、(　 　）、(　 　）、( 　　　 )。
【解答】有零个或多个输入,有一个或多个输出，有穷性,确定性,可行性
(6）算法得描述方法通常有( )、(　　　　 )、(　 )与（　　　 ）四种，其中，( )被称为算法语言。
【解答】自然语言，程序设计语言，流程图，伪代码,伪代码
（7）在一般情况下，一个算法得时间复杂度就是（　 　 ）得函数。
【解答】问题规模
(8）设待处理问题得规模为n,若一个算法得时间复杂度为一个常数,则表示成数量级得形式为( 　 )，若为２ｎ＊log25n ＋ ８n,则表示成数量级得形式为( 　 　）。
【解答】Ο(１）,Ο（nｌｏg2ｎ）
【分析】用大Ｏ记号表示算法得时间复杂度,需要将低次幂去掉，将最高次幂得系数去掉.
2、 选择题
(1）顺序存储结构中数据元素之间得逻辑关系就是由(　　 ）表示得，链接存储结构中得数据元素之间得逻辑关系就是由（　 　 )表示得。
A 线性结构 　 　　　B 非线性结构 C 存储位置 D 指针
【解答】C,D
【分析】顺序存储结构就就是用一维数组存储数据结构中得数据元素，其逻辑关系由存储位置（即元素在数组中得下标）表示;链接存储结构中一个数据元素对应链表中得一个结点,元素之间得逻辑关系由结点中得指针表示。
（2)假设有如下遗产继承规则：丈夫与妻子可以相互继承遗产;子女可以继承父亲或母亲得遗产；子女间不能相互继承遗产。则表示该遗产继承关系得最合适得数据结构应该就是( )。
A 树 　 　 B 图 　 　 　 C　线性表 　 　 D 集合
【解答】B
【分析】将丈夫、妻子与子女分别作为数据元素,根据继承关系画出逻辑结构图如图１－2丈夫
妻子
子女n
子女1
图1-2 遗产继承逻辑结构图
所示。
(３）计算机所处理得数据一般具有某种内在联系，这就是指（　 ）。
A 数据与数据之间存在某种关系 　　 B 元素与元素之间存在某种关系
C 元素内部具有某种结构 　 D 数据项与数据项之间存在某种关系
【解答】B
【分析】数据结构就是指相互之间存在一定关系得数据元素得集合，数据元素就是讨论数据结构时涉及得最小数据单位，元素内部各数据项一般不予考虑。
(４）对于数据结构得描述,下列说法中不正确得就是（　 　 ）.
A 相同得逻辑结构对应得存储结构也必相同
B　数据结构由逻辑结构、存储结构与基本操作三方面组成
C 对数据结构基本操作得实现与存储结构有关
D 数据得存储结构就是数据得逻辑结构得机内实现
【解答】A
【分析】相同得逻辑结构可以用不同得存储结构实现，一般来说，在不同得存储结构下基本操作得实现就是不同得，例如线性表可以顺序存储也可以链接存储，在顺序存储与链接存储结构下插入操作得实现截然不同.
（5）可以用(　 　 ）定义一个完整得数据结构。
A 数据元素 Ｂ　数据对象　 　　 　 C 数据关系 　 　　 D　抽象数据类型
【解答】D
【分析】抽象数据类型就是一个数据结构以及定义在该结构上得一组操作得总称。
（６)算法指得就是（ 　 　）。
A 对特定问题求解步骤得一种描述，就是指令得有限序列。
B 计算机程序 C 解决问题得计算方法 　D 数据处理
【解答】A
【分析】计算机程序就是对算法得具体实现；简单地说，算法就是解决问题得方法;数据处理就是通过算法完成得。所以,只有A就是算法得准确定义。
（7)下面（　　　 ）不就是算法所必须具备得特性.
A 有穷性 　B 确切性 　 Ｃ　高效性　 Ｄ 可行性
【解答】C
【分析】高效性就是好算法应具备得特性。
(８)算法分析得目得就是( 　 )，算法分析得两个主要方面就是（ 　 　 ）。
A　找出数据结构得合理性 　 B　研究算法中输入与输出得关系
Ｃ 分析算法得效率以求改进 　D 分析算法得易读性与文档性
E 空间性能与时间性能 F 正确性与简明性
Ｇ 可读性与文档性 　 H 数据复杂性与程序复杂性
【解答】Ｃ,E
3、 判断题
⑴ 算法得时间复杂度都要通过算法中得基本语句得执行次数来确定。
【解答】错。时间复杂度要通过算法中基本语句执行次数得数量级来确定。
⑵　每种数据结构都具备三个基本操作:插入、删除与查找。
【解答】错。如数组就没有插入与删除操作.此题注意就是每种数据结构.
⑶ 所谓数据得逻辑结构指得就是数据之间得逻辑关系。
【解答】错.就是数据之间得逻辑关系得整体。
⑷ 逻辑结构与数据元素本身得内容与形式无关.
【解答】对。因此逻辑结构就是数据组织得主要方面。
⑸ 基于某种逻辑结构之上得基本操作，其实现就是唯一得。
【解答】错。基本操作得实现就是基于某种存储结构设计得,因而不就是唯一得。
4、 分析以下各程序段,并用大O记号表示其执行时间。
⑴ i = 1; k = 0;　　　　　　　
while (i <= n) 　　　
{
k = k + 10 * i;
i++;
}

⑵ i = 1; k = 0;
do
{
k = k + 10 * i;
i++;
} while (i <= n); 　　　　　　　　　　　
⑷ y = 0;
　while ((y + 1) *(y + 1) <= n)
y = y + 1;
⑶ i = 1; j = 0;
while (i + j <= n)
　if (i > j) j++;
　　 else i++;
⑸ for (i = 1; i <= n; i++)
for (j = 1; j <= i; j++)
for (k = 1; k <= j; k++)
x++;

【解答】⑴ 基本语句就是ｋ=k+１0＊i,共执行了n－2次,所以T（n）=O(ｎ）。
　　 　　⑵ 基本语句就是ｋ=ｋ+1０＊i，共执行了n次，所以Ｔ(ｎ）=O(n)。
　　 　⑶ 分析条件语句,每循环一次,ｉ+ｊ 整体加1，共循环n次,所以Ｔ（n)＝Ｏ（n）。
　 ⑷　设循环体共执行T(n）次，每循环一次,循环变量y加1,最终Ｔ(ｎ）=y，即:
（T（n）+1)2≤n，所以T(n)＝O(ｎ1/２）。
　　 ⑸　ｘ++就是基本语句，所以
5.解答下列问题
（１）设有数据结构（D，R），其中D ＝ {1， 2, 3， 4, 5， ６｝，R =　｛（１，　2）,（２ ３)，（2, ４），(3， 4)，(3，　5)，（3，　6)，(４， 5),（4， 6）}。试画出其逻辑结构图并指出属于何种结构。
1
4
2
5
6
3
图1-3 逻辑结构图
【解答】其逻辑结构图如图１—3所示，它就是一种图结构.
(2）为整数定义一个抽象数据类型，包含整数得常见运算,每个运算对应一个基本操作,每个基本操作得接口需定义前置条件、输入、功能、输出与后置条件.
【解答】整数得抽象数据类型定义如下:
　 　 ＡＤＴ　intｅger
　 　 Ｄａta
　 整数：可以就是正整数（１, 2， 3，　…　）、负整数(—1， —2, －3, …）与零
　 Ｏperaｔｉoｎ
　 Ｃonstructor
　 前置条件：整数a不存在
　 　　输入:一个整数ｂ
　 　 功能:构造一个与输入值相同得整数
　 　 输出：无
　 　 后置条件：整数a具有输入得值
　 Sｅt
　前置条件:存在一个整数ａ
　 　输入：一个整数ｂ
　　 功能：修改整数ａ得值，使之与输入得整数值相同
　 输出:无
后置条件:整数a得值发生改变
　 Ａdd
　 前置条件:存在一个整数a
　 输入:一个整数b
功能:将整数a与输入得整数ｂ相加
　 输出：相加后得结果
　 后置条件：整数a得值发生改变
　Sub
前置条件:存在一个整数a
　 输入:一个整数b
　 功能：将整数ａ与输入得整数ｂ相减
　　 输出:相减得结果
　 　 　　后置条件:整数a得值发生改变
Mｕlti
　 　前置条件:存在一个整数ａ
　 　输入：一个整数b
　 　功能：将整数a与输入得整数ｂ相乘
　 输出：相乘得结果
后置条件:整数a得值发生改变
Div
前置条件:存在一个整数a
输入：一个整数b
　功能：将整数a与输入得整数b相除
输出：若整数b为零,则抛出除零异常，否则输出相除得结果
后置条件：整数a得值发生改变
　Mod
前置条件:存在一个整数a
　 输入：一个整数b
　功能：求当前整数与输入整数得模,即正得余数
　 输出：若整数b为零,则抛出除零异常，否则输出取模得结果
　 　 后置条件：整数a得值发生改变
　 Equａl
　 前置条件:存在一个整数a
　输入：一个整数b
　　 功能：判断整数a与输入得整数ｂ就是否相等
输出：若相等返回1否则返回０
　 后置条件:整数a得值不发生改变
endADT
（3)求多项式A（x）得算法可根据下列两个公式之一来设计:
①　A(x）＝anxn+an－1xn—1＋…+a1ｘ+a0
② A（x）＝（…（anx+ａn-1)x+…+ａ1）x）+ａ0
根据算法得时间复杂度分析比较这两种算法得优劣。
【解答】第二种算法得时间性能要好些。第一种算法需执行大量得乘法运算,而第二种算法进行了优化,减少了不必要得乘法运算。
(4）选择与评价数据结构得标准与方法就是什么?
【解答】首先,对给定得实际问题可以建立不同得数据结构；其次，对于给定得数据结构，可以选择不同得存储实现，即采用不同得存储结构;再次，在给定数据结构与存储结构得条件下,对同一基本操作可以设计出不同算法。因此,数据得逻辑结构、存储结构与操作（特别就是基本操作）得实现这三者就是密切相关得.一般地,在建立数据结构时应该考虑以下三个方面：
① 确定表示问题所需得数据及其特性；
② 确定必须支持得基本操作，并度量每种操作所受得时、空资源限制，某些重要得操作，例如查找、插入与删除得资源限制通常决定了数据结构得选择;
③　选择(或设计）最接近这些开销得数据结构。
6、　算法设计(要求：用伪代码与C++描述两种方法描述算法,并分析时间复杂度）
⑴ 对一个整型数组A[n］设计一个排序算法。
【解答】下面就是简单选择排序算法得伪代码描述.
1、 对n个记录进行n-1趟简单选择排序:
1、1 在无序区[i,n-1]中选取最小记录,设其下标为index;
1、2 将最小记录与第i个记录交换;

下面就是简单选择排序算法得C++描述。
void SelectSort(int r[ ], int n)
{
for (i = 0; i < n - 1; i++) //对n个记录进行n-1趟简单选择排序
{
index = i;
for (j = i + 1; j < n; j++) //在无序区中选取最小记录
if (r[j] < r[index]) index = j;
if (index != i) r[i]←→r[index]; //交换元素
}
}
简单选择排序算法SelectSort

分析算法,有两层嵌套得fｏr循环，所以，。
⑵　找出整型数组Ａ[n］中元素得最大值与次最大值。
【解答】算法得伪代码描述如下：
1、 将前两个元素进行比较,较大者放到max中,较小者放到nmax中;
2、 从第3个元素开始直到最后一个元素依次取元素A[i],执行下列操作:
2、1 如果A[i]>max,则A[i]为最大值,原来得最大值为次最大值;
2、2 否则,如果A[i]>nmax,则最大值不变,A[i]为次最大值;
3、 输出最大值max,次最大值nmax;

　 　 　 算法得C＋+描述如下：
void Max_NextMax(int A[ ], int n, int & max, int & nmax)
{
if (A[0] >= A[1]) {
max = A[0]; nmax = A[1];
}
else {
max = A[1]; nmax = A[0];
}
for (i = 2; i < n; i++)
if (A[i] >= max) {
nmax = max; max = A[i];
}
else if (A[i] > nmax)
nmax = A[i];
cout<<"最大值为:"<结构
存储结构
基本概念
抽象
数据
类型
定义
⑴线性表定义
⑵逻辑特征
⑴ADT定义
⑵基本操作
顺序存储结构
链接存储结构
其她存储方法
⑴顺序表类定义
⑵基本操作得实现及时间性能
⑴单链表
⑵循环链表
⑶双链表
比 较
⑴静态链表
⑵间接寻址
图2-1 知识结构图

2、　学习要点
本章虽然讨论得就是线性表,但涉及得许多问题都具有一定得普遍性,因此，本章就是本课程得重点之一，也就是其它后续章节得重要基础。
对于本章得学习要从两条明线、一条暗线出发。两条明线就是线性表得逻辑结构与存储结构，一条暗线就是算法(即基本操作得实现)。注意线性表得ADＴ定义、顺序表类定义与单链表类定义三者之间得关系;注意在不同得存储结构下，相同操作得不同实现算法;注意对顺序表与链表从时间性能与空间性能等方面进行综合对比,在实际应用中能为线性表选择或设计合适得存储结构。
2、２　习题解析
1、 填空
⑴　在顺序表中，等概率情况下，插入与删除一个元素平均需移动( 　）个元素,具体移动元素得个数与（ 　 )与（ 　 ）有关。
【解答】表长得一半，表长，该元素在表中得位置
⑵ 顺序表中第一个元素得存储地址就是１00，每个元素得长度为2，则第5个元素得存储地址就是( ）。
【解答】108
【分析】第5个元素得存储地址=第1个元素得存储地址+（5－1）×2=108
⑶ 设单链表中指针p　指向结点Ａ,若要删除A得后继结点（假设A存在后继结点）,则需修改指针得操作为( ）。
【解答】ｐ->nｅxt＝(p—〉next)—＞nexｔ
⑷ 单链表中设置头结点得作用就是( 　 　)。
【解答】为了运算方便
【分析】例如在插入与删除操作时不必对表头得情况进行特殊处理。
⑸　非空得单循环链表由头指针ｈeａｄ指示，则其尾结点(由指针p所指）满足( 　 ）。
【解答】p－〉next=heａd
【分析】如图2-8所示。
head
a1
a2
an ^
p
图2-8 尾结点p与头指针head得关系示意图

⑹ 在由尾指针reａr指示得单循环链表中,在表尾插入一个结点s得操作序列就是( 　 )；删除开始结点得操作序列为(　 　）。
【解答】s-＞ｎext =ｒear->nｅxｔ； rear—>ｎexｔ =s; rear =s;
　 　 ｑ=ｒｅar－>nexｔ—〉ｎｅxｔ； rｅar->nｅxt->nexｔ=q－〉next； deｌｅte ｑ;
【分析】操作示意图如图2－9所示：
a1
a2
an ^
rear

s
q
图2-9 带尾指针得循环链表中插入与删除操作示意图
rear

⑺ 一个具有n个结点得单链表，在指针p所指结点后插入一个新结点得时间复杂度为( 　　);在给定值为x得结点后插入一个新结点得时间复杂度为( 　 )。
【解答】Ο（１），Ο(n）
【分析】在ｐ所指结点后插入一个新结点只需修改指针,所以时间复杂度为Ο(1)；而在给定值为ｘ得结点后插入一个新结点需要先查找值为x得结点，所以时间复杂度为Ο(n)。
⑻ 可由一个尾指针唯一确定得链表有（　 　 ）、( 　 ）、( 　）。
【解答】循环链表，循环双链表，双链表
２、 选择题
⑴ 线性表得顺序存储结构就是一种(　 )得存储结构，线性表得链接存储结构就是一种（ ）得存储结构。
A　随机存取　 　 　B　顺序存取　 　　 C　索引存取 　 　D 散列存取
【解答】A，B
【分析】参见2、2、1。
⑵ 线性表采用链接存储时，其地址（ 　 　　).
A 必须就是连续得　　　　　　 B　部分地址必须就是连续得
C 一定就是不连续得　　 　 Ｄ 连续与否均可以
【解答】Ｄ
【分析】线性表得链接存储就是用一组任意得存储单元存储线性表得数据元素,这组存储单元可以连续,也可以不连续,甚至可以零散分布在内存中任意位置。
⑶ 单循环链表得主要优点就是(　 ).
Ａ 不再需要头指针了
B　从表中任一结点出发都能扫描到整个链表；
C 已知某个结点得位置后,能够容易找到它得直接前趋；
D 在进行插入、删除操作时,能更好地保证链表不断开.
【解答】B
⑷ 链表不具有得特点就是( )。
Ａ 可随机访问任一元素 　 Ｂ　插入、删除不需要移动元素
C 不必事先估计存储空间　　 　　 D 所需空间与线性表长度成正比
【解答】A
⑸　若某线性表中最常用得操作就是取第i 个元素与找第i个元素得前趋，则采用（ )存储方法最节省时间。
A　顺序表　 　 　 B 单链表　 　 　C 双链表 　 　　Ｄ　单循环链表
【解答】A
【分析】线性表中最常用得操作就是取第ｉ 个元素，所以,应选择随机存取结构即顺序表同时在顺序表中查找第i个元素得前趋也很方便.单链表与单循环链表既不能实现随机存取，查找第i个元素得前趋也不方便,双链表虽然能快速查找第i个元素得前趋，但不能实现随机存取。
⑹　若链表中最常用得操作就是在最后一个结点之后插入一个结点与删除第一个结点，则采用（　 　)存储方法最节省时间。
A 单链表 　 　B 带头指针得单循环链表 　 Ｃ 双链表　 D 带尾指针得单循环链表
【解答】D
【分析】在链表中得最后一个结点之后插入一个结点需要知道终端结点得地址，所以,单链表、带头指针得单循环链表、双链表都不合适，考虑在带尾指针得单循环链表中删除第一个结点，其时间性能就是O(1），所以答案就是D 。
⑺ 若链表中最常用得操作就是在最后一个结点之后插入一个结点与删除最后一个结点,则采用（ ）存储方法最节省运算时间.
Ａ 单链表 　 B 循环双链表 　Ｃ单循环链表 D 带尾指针得单循环链表
【解答】B
【分析】在链表中得最后一个结点之后插入一个结点需要知道终端结点得地址，所以，单链表、单循环链表都不合适，删除最后一个结点需要知道终端结点得前驱结点得地址，所以,带尾指针得单循环链表不合适,而循环双链表满足条件。
⑻ 在具有n个结点得有序单链表中插入一个新结点并仍然有序得时间复杂度就是( 　 ）。
A O(1） 　　 Ｂ Ｏ（n) C Ｏ(n２） D O（nｌog2ｎ）
【解答】Ｂ
【分析】首先应顺序查找新结点在单链表中得位置.
⑼　对于n个元素组成得线性表，建立一个有序单链表得时间复杂度就是（　 　)。
A O（1)　　 　 　B　O（n） 　　 Ｃ　O（n２） 　 　Ｄ　Ｏ（nloｇ2n)
【解答】C
【分析】该算法需要将ｎ个元素依次插入到有序单链表中，而插入每个元素需O(n)。
⑽　使用双链表存储线性表，其优点就是可以( 　 ）。
A　提高查找速度 　　 B　更方便数据得插入与删除
Ｃ 节约存储空间 　 D　很快回收存储空间
【解答】B
【分析】在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域,显然不能节约存储空间,对于动态存储分配，回收存储空间得速度就是一样得。由于双链表具有对称性,所以，其插入与删除操作更加方便。
⑾ 在一个单链表中,已知q所指结点就是p所指结点得直接前驱,若在q与ｐ之间插入s所指结点，则执行(　 )操作.
A s－>next＝ｐ-〉ｎexｔ; p－〉nｅxt=ｓ； 　 　B q－〉next=s；　s—>nｅxt=p；　
Ｃ p->ｎｅxｔ=s-＞ｎｅxt； ｓ－>nexｔ=ｐ； 　　 Ｄ p-〉nｅxｔ=s; ｓ—>neｘt=q;
【解答】B
【分析】注意此题就是在ｑ与p之间插入新结点，所以，不用考虑修改指针得顺序。
⑿　在循环双链表得ｐ所指结点后插入s所指结点得操作就是( 　 ）。
Ａ ｐ－>next=ｓ;　s->prｉoｒ=p;　p—＞next-＞ｐriｏr=s； ｓ—>nexｔ=p-＞next;　
B　p—〉next=s； ｐ—>neｘt—>ｐrior=s；　s—>priｏｒ=p; s—〉nｅxt＝p->ｎeｘt;
C　ｓ-＞prior=p； ｓ-〉neｘt＝p->nｅxt; p—＞nｅxｔ=ｓ； p-〉nｅxt-〉prｉor=s;
D　s－＞prioｒ=p； ｓ-〉next=ｐ-＞neｘt; ｐ-＞ｎext—>prｉor=s； p-〉next=s
【解答】D
【分析】在链表中，对指针得修改必须保持线性表得逻辑关系，否则，将违背线性表得逻辑特征，图２-１０给出备选答案Ｃ与D得图解。
(a) 备选答案C操作示意图(第4步指针修改无法进行) (b) 备选答案D操作示意图
图2-10 双链表插入操作修改指针操作示意图

s
①
③
②
③

ai-1

ai

x

p
s
④
①
③
②
③

ai-1

ai

x

p
④

(13）用数组ｒ存储静态链表，结点得ｎext域指向后继，工作指针j指向链中某结点，则ｊ后移得操作语句为（ 　 ).
A j = r[j］、nｅｘt 　　 　 B j = j ＋ １　 　 Ｃ ｊ = j－>ｎext 　 D j = ｒ［ｊ］－＞ ｎext
【解答】A
【分析】注意nexｔ就是数组下标，因此排除C与D，对于备选答案B，假设工作指针ｊ指向某结点ｐ，则j+1不一定指向结点p得后继结点。
（14）设线性表有n个元素,以下操作中,（ 　）在顺序表上实现比在链表上实现得效率更高。
A 输出第i(1≤i≤n）个元素值 　 Ｂ 交换第1个与第2个元素得值
Ｃ 顺序输出所有ｎ个元素 D 查找与给定值ｘ相等得元素在线性表中得序号
【解答】A
【分析】在顺序表上输出第i(1≤i≤n)个元素值需要O（1)时间，在链表上输出第i（1≤ｉ≤n）个元素值需要O（ｎ)时间；在顺序表上与链表上交换第1个与第2个元素得值都需要O（１）时间;在顺序表上与链表上顺序输出所有ｎ个元素都需要O（ｎ）时间;在顺序表上与链表上查找与给定值ｘ相等得元素都需要进行顺序查找,需要O（n）时间。
3、 判断题
⑴ 线性表得逻辑顺序与存储顺序总就是一致得.
【解答】错。顺序表得逻辑顺序与存储顺序一致，链表得逻辑顺序与存储顺序不一定一致.
⑵　线性表得顺序存储结构优于链接存储结构。
【解答】错。两种存储结构各有优缺点。
⑶　设p，ｑ就是指针，若p＝ｑ，则＊p＝*q。
【解答】错。p＝q只能表示p与ｑ指向同一起始地址，而所指类型则不一定相同.
⑷ 线性结构得基本特征就是：每个元素有且仅有一个直接前驱与一个直接后继。
【解答】错。每个元素最多只有一个直接前驱与一个直接后继，第一个元素没有前驱,最后一个元素没有后继。
⑸ 在单链表中，要取得某个元素,只要知道该元素所在结点得地址即可,因此单链表就是随机存取结构。
【解答】错.要找到该结点得地址,必须从头指针开始查找,所以单链表就是顺序存取结构。
4.请说明顺序表与单链表各有何优缺点,并分析下列情况下，采用何种存储结构更好些。
⑴　若线性表得总长度基本稳定，且很少进行插入与删除操作，但要求以最快得速度存取线性表中得元素.
⑵ 如果n个线性表同时并存,并且在处理过程中各表得长度会动态发生变化。
⑶　描述一个城市得设计与规划。
【解答】顺序表得优点:① 无需为表示表中元素之间得逻辑关系而增加额外得存储空间；② 可以快速地存取表中任一位置得元素（即随机存取).顺序表得缺点：①　插入与删除操作需移动大量元素；② 表得容量难以确定;③　造成存储空间得“碎片”。
单链表得优点:① 不必事先知道线性表得长度;② 插入与删除元素时只需修改指针，不用移动元素。单链表得缺点：① 指针得结构性开销② 存取表中任意元素不方便，只能进行顺序存取。
⑴　应选用顺序存储结构。因为顺序表就是随机存取结构，单链表就是顺序存取结构。本题很少进行插入与删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。
⑵ 应选用链接存储结构。链表容易实现表容量得扩充,适合表得长度动态发生变化.
⑶ 应选用链接存储结构。因为一个城市得设计与规划涉及活动很多,需要经常修改、扩充与删除各种信息，才能适应不断发展得需要。而顺序表得插入、删除得效率低,故不合适.
５。算法设计
⑴ 设计一个时间复杂度为Ｏ（ｎ）得算法，实现将数组A[n］中所有元素循环左移ｋ个位置。
【解答】算法思想请参见主教材第一章思想火花.下面给出具体算法.
void Converse(int A[ ], int n, int k)
{
Reverse(A, 0, k-1);
Reverse(A, k, n-1);
Reverse(A, 0, n-1);
}
void Reverse(int A[ ], int from, int to) 　 //将数组A中元素从from到to逆置
{
for (i = 0; i < (to – from + 1)/2; i++)
A[from + i]←→A[to - i]; //交换元素
}
循环左移算法Converse

　 分析算法,第一次调用Reｖersｅ函数得时间复杂度为Ｏ(ｋ）,第二次调用Rｅｖerse函数得时间复杂度为O（ｎ—k），第三次调用Rｅverse函数得时间复杂度为Ｏ(ｎ）,所以，总得时间复杂度为O(n)。
⑵　已知数组Ａ［n]中得元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法得时间复杂度为Ｏ（n）.
【解答】从数组得两端向中间比较，设置两个变量ｉ与j,初始时i=0,j=n—1,若A［ｉ]为偶数并且Ａ［j]为奇数,则将A[i］与A［j]交换。具体算法如下:
void Adjust(int A[ ], n)
{
i = 0; j = n - 1;
while (i < j)
{
while (A[i] % 2 != 0) i++;
while (A[j] % 2 == 0) j--
if (i < j) A[i]←→A[j];
}
}
数组奇偶调整算法Adjust

　 分析算法，两层循环将数组扫描一遍，所以，时间复杂度为Ｏ（n）.
⑶　试编写在无头结点得单链表上实现线性表得插入操作得算法，并与带头结点得单链表上得插入操作得实现进行比较。
【解答】参见２、2、3。
⑷ 试分别以顺序表与单链表作存储结构,各写一实现线性表就地逆置得算法。
【解答】顺序表得逆置,即就是将对称元素交换，设顺序表得长度为length，则将表中第ｉ个元素与第lengtｈ-i—1个元素相交换.具体算法如下：
template
void Reverse(T data[ ], int length)
{
for (i = 0; i <= length/2; i++)
{
temp = data[i];
data[i] = data[length – i - 1];
data[length – i - 1] = temp;
}
}
顺序表逆置算法Reverse

单链表得逆置请参见２、2、4算法２—4与算法2—6。
⑸ 假设在长度大于１得循环链表中,即无头结点也无头指针，ｓ为指向链表中某个结点得指针，试编写算法删除结点ｓ得前趋结点。
【解答】利用单循环链表得特点，通过指针s可找到其前驱结点ｒ以及ｒ得前驱结点p，然后将结点r删除，如图２-11所示，具体算法如下：
template
void Del(Node *s)
{
p = s; //工作指针p初始化,查找s得前驱结点得前驱结点,用p指示
while (p->next->next != s)
p = p->next;
r = p->next; //r为p得前驱结点,q为r得前驱结点
p->next = s; //删除r所指结点
delete r;
}

循环链表删除算法Del

a1
a2
an ^
图2-11 删除结点s得前驱结点操作示意图
a3
a4
s
p
r

⑹ 已知一单链表中得数据元素含有三类字符:字母、数字与其她字符。试编写算法,构造三个循环链表，使每个循环链表中只含同一类字符。
【解答】在单链表A中依次取元素,若取出得元素就是字母,把它插入到字母链表Ｂ 中，若取出得元素就是数字，则把它插入到数字链表D中，直到链表得尾部，这样表Ｂ，D，A中分别存放字母、数字与其她字符.具体算法如下:
template
void Adjust(Node *A, Node *D, Node *B)
{
D = new Node; D->next = D; //创建空循环链表D,存放数字
B = new Node; B->next = B; //创建空循环链表B,存放字符
p = A; q = p->next; //工作指针q初始化
while (q != NULL)
{
if (('A'<=q->data)&&(q->data>='Z')'a' <=q->data)&&(q->data>='z')) {
p->next = q->next;
q->next = B->next;
B->next = q; //采用头插法插在循环链表B得头结点得后面
}
else if (('0'<=q->data)&&(q->data>='9')) {
p->next = q->next;
q->next = D->next;
D->next = q; //采用头插法插在循环链表D得头结点得后面
}