数据结构习题(可用)

第一篇：数据结构习题(可用)

第 1 章绪论

1.填空

⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素

⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。【解答】数据项，数据元素

【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶ 从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。【解答】集合，线性结构，树结构，图结构

⑷ 数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（）、（）、（）、（）、（）。【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性

⑹ 算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（）的函数。【解答】问题规模

⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。2.选择题

⑴ 顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构 B 非线性结构 C 存储位置 D 指针【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。A 树 B 图 C 线性表 D 集合【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。

⑶ 算法指的是（）。A 对特定问题求解步骤的一种描述，是指令的有限序列。B 计算机程序 C 解决问题的计算方法 D 数据处理【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。⑷ 下面（）不是算法所必须具备的特性。A 有穷性 B 确切性 C 高效性 D 可行性【解答】C 【分析】高效性是好算法应具备的特性。

⑸ 算法分析的目的是（），算法分析的两个主要方面是（）。A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性【解答】C，E 3.判断题

⑴ 算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。【解答】错。时间复杂度要通过算法中基本语句执行次数的数量级来确定。⑵ 每种数据结构都具备三个基本操作：插入、删除和查找。

【解答】错。如数组就没有插入和删除操作。此题注意是每种数据结构。⑶ 所谓数据的逻辑结构指的是数据之间的逻辑关系。【解答】错。是数据之间的逻辑关系的整体。⑷ 逻辑结构与数据元素本身的内容和形式无关。【解答】对。因此逻辑结构是数据组织的主要方面。⑸ 基于某种逻辑结构之上的基本操作，其实现是唯一的。

【解答】错。基本操作的实现是基于某种存储结构设计的，因而不是唯一的。

4.分析以下各程序段，并用大O记号表示其执行时间。

【解答】⑴ 基本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n)。⑵ 基本语句是k=k+10*i，共执行了n次，所以T(n)=O(n)。⑶ 分析条件语句，每循环一次，i+j 整体加1，共循环n次，所以T(n)=O(n)。⑷ 设循环体共执行T(n)次，每循环一次，循环变量y加1，最终T(n)=y，即：(T(n)+1)2≤n，所以T(n)=O(n1/2)。

⑸ x++是基本语句，所以

5．设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。试画出其逻辑结构图并指出属于何种结构。【解答】其逻辑结构图如图1-3所示，它是一种图结构。

6.求多项式A(x)的算法可根据下列两个公式之一来设计： ⑴ A(x)=anxn+an-1xn-1+„+a1x+a0 ⑵ A(x)=(„(anx+an-1)x+„+a1)x)+a0

根据算法的时间复杂度分析比较这两种算法的优劣。

【解答】第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进行了优化，减少了不必要的乘法运算。

学习自测及答案

1．顺序存储结构的特点是（），链接存储结构的特点是（）。

【解答】用元素在存储器中的相对位置来表示数据元素之间的逻辑关系，用指示元素存储地址的指针表示数据元素之间的逻辑关系。

2.算法在发生非法操作时可以作出处理的特性称为（）。【解答】健壮性

3.常见的算法时间复杂度用大Ｏ记号表示为：常数阶()、对数阶()、线性阶()、平方阶()和指数阶()。【解答】Ｏ(1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n)，Ｏ(2)4．试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

【解答】数据结构是指相互之间存在一定关系的数据元素的集合。而抽象数据类型是指一个数据结构以及定义在该结构上的一组操作。程序设计语言中的数据类型是一个值的集合和定义在这个值集上一组操作的总称。抽象数据类型可以看成是对数据类型的一种抽象。

第 2 章线性表

1.填空

2n⑴ 在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。

【解答】表长的一半，表长，该元素在表中的位置

⑵ 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。【解答】108 【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108

⑶ 设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。

【解答】p->next=p->next->next ⑷ 单链表中设置头结点的作用是（）。【解答】为了运算方便

【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。

⑸ 非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。【解答】p->next=head 【分析】如图2-8所示。

⑹ 在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。

【解答】s->next =rear->next;rear->next =s;rear =s;q=rear->next->next;rear->next->next=q->next;delete q;【分析】操作示意图如图2-9所示：

⑺ 一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。【解答】Ο(1)，Ο(n)【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。⑻ 可由一个尾指针唯一确定的链表有（）、（）、（）。【解答】循环链表，循环双链表，双链表 2.选择题

⑴ 线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。A 随机存取 B 顺序存取 C 索引存取 D 散列存取【解答】A，B ⑵ 线性表采用链接存储时，其地址（）。

A 必须是连续的B 部分地址必须是连续的 C 一定是不连续的 D 连续与否均可以【解答】D 【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。⑶ 单循环链表的主要优点是（）。A 不再需要头指针了

B 从表中任一结点出发都能扫描到整个链表；

C 已知某个结点的位置后，能够容易找到它的直接前趋； D 在进行插入、删除操作时，能更好地保证链表不断开。【解答】B ⑷ 链表不具有的特点是（）。

A 可随机访问任一元素 B 插入、删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与线性表长度成正比【解答】A ⑸ 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。A 顺序表 B 单链表 C 双链表 D 单循环链表【解答】A 【分析】线性表中最常用的操作是取第i 个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。

⑹ 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（）存储方法最节省时间。

A 单链表 B 带头指针的单循环链表 C 双链表 D 带尾指针的单循环链表【解答】D 【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以，答案是D。

⑺ 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方法最节省运算时间。

A 单链表 B 循环双链表 C单循环链表

D 带尾指针的单循环链表【解答】B 【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、单循环链表都不合适，删除最后一个结点需要知道终端结点的前驱结点的地址，所以，带尾指针的单循环链表不合适，而循环双链表满足条件。

⑻ 在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。A O(1)B O(n)C O(n)D O(nlog2n)【解答】B 【分析】首先应顺序查找新结点在单链表中的位置。

⑼ 对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（）。A O(1)B O(n)C O(n)D O(nlog2n)【解答】C 【分析】该算法需要将n个元素依次插入到有序单链表中，而插入每个元素需O(n)。⑽ 使用双链表存储线性表，其优点是可以（）。

A 提高查找速度 B 更方便数据的插入和删除 C 节约存储空间 D 很快回收存储空间【解答】B

22【分析】在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节约存储空间，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，所以，其插入和删除操作更加方便。

⑾ 在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（）操作。

A s->next=p->next;p->next=s;B q->next=s;s->next=p;C p->next=s->next;s->next=p;D p->next=s;s->next=q;【解答】B 【分析】注意此题是在q和p之间插入新结点，所以，不用考虑修改指针的顺序。⑿ 在循环双链表的p所指结点后插入s所指结点的操作是（）。A p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;B p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;C s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;D s->prior=p;s->next=p->next;p->next->prior=s;p->next=s 【解答】D 【分析】在链表中，对指针的修改必须保持线性表的逻辑关系，否则，将违背线性表的逻辑特征，图2-10给出备选答案C和D的图解。

3.判断题

⑴ 线性表的逻辑顺序和存储顺序总是一致的。

【解答】错。顺序表的逻辑顺序和存储顺序一致，链表的逻辑顺序和存储顺序不一定一致。⑵ 线性表的顺序存储结构优于链接存储结构。【解答】错。两种存储结构各有优缺点。⑶ 设p，q是指针，若p=q，则*p=*q。

【解答】错。p=q只能表示p和q指向同一起始地址，而所指类型则不一定相同。⑷ 线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。

【解答】错。每个元素最多只有一个直接前驱和一个直接后继，第一个元素没有前驱，最后一个元素没有后继。

⑸ 在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随机存取结构。【解答】错。要找到该结点的地址，必须从头指针开始查找，所以单链表是顺序存取结构。

4．请说明顺序表和单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些。

⑴ 若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。⑵ 如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。⑶ 描述一个城市的设计和规划。

【解答】顺序表的优点：① 无需为表示表中元素之间的逻辑关系而增加额外的存储空间；② 可以快速地存取表中任一位置的元素（即随机存取）。顺序表的缺点：① 插入和删除操作需移动大量元素；② 表的容量难以确定；③ 造成存储空间的“碎片”。

单链表的优点：① 不必事先知道线性表的长度；② 插入和删除元素时只需修改指针，不用移动元素。单链表的缺点：① 指针的结构性开销；② 存取表中任意元素不方便，只能进行顺序存取。

⑴ 应选用顺序存储结构。因为顺序表是随机存取结构，单链表是顺序存取结构。本题很少进行插入和删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。

⑵ 应选用链接存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。

⑶ 应选用链接存储结构。因为一个城市的设计和规划涉及活动很多，需要经常修改、扩充和删除各种信息，才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。5．算法设计

⑴ 设计一个时间复杂度为Ｏ(n)的算法，实现将数组A[n]中所有元素循环右移k个位置。【解答】算法思想请参见主教材第一章思想火花。下面给出具体算法。

分析算法，第一次调用Reverse函数的时间复杂度为O(k)，第二次调用Reverse函数的时间复杂度为O(n-k)，第三次调用Reverse函数的时间复杂度为O(n)，所以，总的时间复杂度为O(n)。⑵试分别以顺序表和单链表作存储结构，各写一实现线性表就地逆置的算法。

【解答】顺序表的逆置，即是将对称元素交换，设顺序表的长度为length，则将表中第i个元素与第length-i-1个元素相交换。具体算法如下：

单链表的逆置请参见2.2.4算法2-4和算法2-6。

⑶ 假设在长度大于1的循环链表中，即无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点s的前趋结点。【解答】利用单循环链表的特点，通过指针s可找到其前驱结点r以及r的前驱结点p，然后将结点r删除，如图2-11所示，具体算法如下：

⑷ 设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点。

【解答】从头到尾扫描单链表，若当前结点的元素值与后继结点的元素值不相等，则指针后移；否则删除该后继结点。具体算法如下：

⑸ 判断带头结点的双循环链表是否对称。

【解答】设工作指针p和q分别指向循环双链表的开始结点和终端结点，若结点p和结点q的数据域相等，则工作指针p后移，工作指针q前移，直到指针p和指针q指向同一结点（循环双链表中结点个数为奇数），或结点q成为结点p的前驱（循环双链表中结点个数为偶数）。如图2-12所示。

学习自测及答案

1.已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（）。

A 108 B 180 C 176 D 112 【解答】D 2．在长度为n的线性表中查找值为x的数据元素的时间复杂度为：（）。A O(0)B O(1)C O(n)D O(n)【解答】C 3．在一个长度为n的顺序表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动（）个元素，删除第i（1≤i≤n）个元素时，需向前移动（）个元素。【解答】n-i+1，n-i 4．在单链表中，除了头结点以外，任一结点的存储位置由（）指示。【解答】其前趋结点的指针域

5．当线性表采用顺序存储结构时，其主要特点是（）。【解答】逻辑结构中相邻的结点在存储结构中仍相邻

6．在双链表中，每个结点设置了两个指针域，其中一个指向（）结点，另一个指向（）结点。【解答】前驱，后继

第 3 章特殊线性表——栈、队列和串

1.填空

⑴ 设有一个空栈，栈顶指针为1000H，现有输入序列为1、2、3、4、5，经过push，push，pop，push，pop，push，push后，输出序列是（），栈顶指针为（）。【解答】23，1003H ⑵ 栈通常采用的两种存储结构是（）；其判定栈空的条件分别是（），判定栈满的条件分别是（）。

2【解答】顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针top=-1和top=NULL，栈顶指针top等于数组的长度和内存无可用空间

⑶（）可作为实现递归函数调用的一种数据结构。【解答】栈

【分析】递归函数的调用和返回正好符合后进先出性。⑷ 表达式a*(b+c)-d的后缀表达式是（）。【解答】abc+*d-【分析】将中缀表达式变为后缀表达式有一个技巧：将操作数依次写下来，再将算符插在它的两个操作数的后面。

⑸ 栈和队列是两种特殊的线性表，栈的操作特性是（），队列的操作特性是（），栈和队列的主要区别在于（）。

【解答】后进先出，先进先出，对插入和删除操作限定的位置不同 ⑹ 循环队列的引入是为了克服（）。【解答】假溢出

⑺ 数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为（）。【解答】（rear-front+n）% n 【分析】也可以是（rear-front）% n，但rear-front的结果可能是负整数，而对一个负整数求模，其结果在不同的编译器环境下可能会有所不同。

⑻ 用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（）和（）。【解答】Ｏ(1)，Ｏ(n)【分析】在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。⑼ 串是一种特殊的线性表，其特殊性体现在（）。【解答】数据元素的类型是一个字符 ⑽ 两个串相等的充分必要条件是（）。【解答】长度相同且对应位置的字符相等【分析】例如“abc”≠“abc ”，“abc”≠“bca”。2.选择题

⑴ 若一个栈的输入序列是1，2，3，„，n，输出序列的第一个元素是n，则第i个输出元素是（）。A 不确定 B n-I C n-i-1 D n-i+1 【解答】D 【分析】此时，输出序列一定是输入序列的逆序。

⑵ 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（）。A 6

B 4

C 3

D 2 【解答】C 【分析】由于队列具有先进先出性，所以，此题中队列形同虚设，即出栈的顺序也是e2、e4、e3、e6、e5、e1。

⑶ 一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（）。A 54321 B 45321 C 43512 D 12345 【解答】C 【分析】此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序（指的是元素的序号）的两个元素。

⑷ 设计一个判别表达式中左右括号是否配对的算法，采用（）数据结构最佳 A 顺序表 B 栈 C 队列 D 链表【解答】B 【分析】每个右括号与它前面的最后一个没有匹配的左括号配对，因此具有后进先出性。

⑸ 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（）结构。

A 栈 B队列 C 数组 D线性表【解答】B 【分析】先进入打印缓冲区的文件先被打印，因此具有先进先出性。⑹ 一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（）。

A 4321 B 1234 C 1432 D 3241 【解答】B 【分析】队列的入队顺序和出队顺序总是一致的。⑺ 栈和队列的主要区别在于（）。

A 它们的逻辑结构不一样 B 它们的存储结构不一样 C 所包含的运算不一样 D 插入、删除运算的限定不一样【解答】D 【分析】栈和队列的逻辑结构都是线性的，都有顺序存储和链接存储，有可能包含的运算不一样，但不是主要区别，任何数据结构在针对具体问题时包含的运算都可能不同。

⑻ 设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（）。A S1的栈底位置为0，S2的栈底位置为n-1 B S1的栈底位置为0，S2的栈底位置为n/2 C S1的栈底位置为0，S2的栈底位置为n D S1的栈底位置为0，S2的栈底位置为1 【解答】A 【分析】两栈共享空间首先两个栈是相向增长的，栈底应该分别指向两个栈中的第一个元素的位置，并注意C++中的数组下标是从0开始的。3.判断题

⑴ 栈可以作为实现过程调用的一种数据结构。

【解答】对。只要操作满足后进先出性，都可以采用栈作为辅助数据结构。⑵ 在栈满的情况下不能做进栈操作，否则将产生“上溢”。【解答】对。

⑶ 在循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，则队满的条件是front=rear。

【解答】错。这是队空的判定条件，在循环队列中要将队空和队满的判定条件区别开。⑷ 空串与空格串是相同的。

【解答】错。空串的长度为零，而空格串的长度不为0，其长度是串中空格的个数。

4.设有一个栈，元素进栈的次序为A，B，C，D，E，能否得到如下出栈序列，若能，请写出操作序列，若不能，请说明原因。⑴ C，E，A，B，D ⑵ C，B，A，D，E 【解答】⑴不能，因为在C、E出栈的情况下，A一定在栈中，而且在B的下面，不可能先于B出栈。⑵可以，设Ｉ为进栈操作，Ｏ为入栈操作，则其操作序列为IIIOOOIOIO。

5.举例说明顺序队列的“假溢出”现象。

【解答】假设有一个顺序队列，如图3-6所示，队尾指针rear=4，队头指针front=1，如果再有元素入队，就会产生“上溢”，此时的“上溢”又称为“假溢出”，因为队列并不是真的溢出了，存储队列的数组中还有2个存储单元空闲，其下标分别为0和1。

6.在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，栈顶元素和栈底元素分别是什么？（push(k)表示整数k入栈，pop表示栈顶元素出栈。）【解答】栈顶元素为6，栈底元素为1。其执行过程如图3-7所示。

7．在操作序列EnQueue(1)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，队头元素和队尾元素分别是什么？（EnQueue(k)表示整数k入队，DeQueue表示队头元素出队）。【解答】队头元素为5，队尾元素为9。其执行过程如图3-8所示。

8．空串和空格串有何区别？串中的空格符有何意义？空串在串处理中有何作用？【解答】不含任何字符的串称为空串，其长度为零。仅含空格的串称为空格串，它的长度为串中空格符的个数。串中的空格符可用来分隔一般的字符，便于人们识别和阅读，但计算串长时应包括这些空格符。空串在串处理中可作为任意串的子串。9.算法设计

⑴ 假设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针。试设计相应的入队和出队的算法。

【解答】出队操作是在循环链表的头部进行，相当于删除开始结点，而入队操作是在循环链表的尾部进行，相当于在终端结点之后插入一个结点。由于循环链表不带头结点，需要处理空表的特殊情况。入队算法如下：

出队算法如下：

⑵ 设顺序栈S中有2n个元素，从栈顶到栈底的元素依次为a2n，a2n-1，„，a1，要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a2n，a2n-2，„，a2，a2n-1，a2n-3，„，a1，请设计算法实现该操作，要求空间复杂度和时间复杂度均为O(n)。【解答】操作步骤为： ① ② ③ 将所有元素出栈并入队；

依次将队列元素出队，如果是偶数结点，则再入队，如果是奇数结点，则入栈；将奇数结点出栈并入队； ④ ⑤ ⑥ 将偶数结点出队并入栈；将所有元素出栈并入队；将所有元素出队并入栈即为所求。

学习自测及答案

1．在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，当出栈时，top的变化为（）。

A 不变;B top=0;C top=top-1;D top=top+1;【解答】C 2．一个栈的入栈序列是a, b, c, d, e，则栈的不可能的出栈序列是（）。A edcba B cdeba C debca D abcde 【解答】C 3．从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行（）。A x=top;top=top->next;B x=top->data;C top=top->next;x=top->data;D x=top->data;top=top->next;【解答】D 4．设元素1, 2, 3, P, A依次经过一个栈，进栈次序为123PA，在栈的输出序列中，有哪些序列可作为C程序设计语言的变量名。

【解答】PA321, P3A21, P32A1, P321A, AP321 5.设S=“I_ am_ a_ teacther”，其长度为（）。【解答】15 6．对于栈和队列，无论它们采用顺序存储结构还是链接存储结构，进行插入和删除操作的时间复杂度都是（）。【解答】Ｏ(1)7．如果进栈序列为A、B、C、D，则可能的出栈序列是什么？

答：共14种，分别是：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA 8．简述队列和栈这两种数据结构的相同点和不同点。

【解答】相同点：它们都是插入和删除操作的位置受限制的线性表。

不同点：栈是限定仅在表尾进行插入和删除的线性表，是后进先出的线性表，而队列是限定在表的一端进行插入，在另一端进行删除的线性表，是先进先出的线性表。

9.设计算法把一个十进制整数转换为二至九进制之间的任一进制数输出。

【解答】算法基于原理：N=(N div d)×d + N mod d（div为整除运算，mod为求余运算）。

10．假设一个算术表达式中可以包含三种括号：圆括号“（”和“）”，方括号“[”和“]”以及花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用。编写算法判断给定表达式中所含括号是否配对出现。

【解答】假设表达式已存入字符数组A[n]中，具体算法如下：

第 4 章广义线性表——多维数组和广义表

1.填空

⑴ 数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。【解答】存取，修改，顺序存储

【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。

⑵ 二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（）。【解答】1140 【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。⑶ 设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。【解答】d+41 【分析】元素A[8][5]的前面共存储了(1+2+„+8)+5=41个元素。⑷ 稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。【解答】三元组顺序表，十字链表

⑸ 广义表((a),(((b),c)),(d))的长度是（），深度是（），表头是（），表尾是（）。【解答】3，4，(a)，((((b),c)),(d))⑹ 已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（）。【解答】Head(Head(Tail(LS)))2.选择题

⑴ 二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（）个字节，A的第8列和第5行共占（）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（）元素的起始地址一致。A 90 B 180 C 240 D 540 E 108 F 114 G 54 H A[8][5] I A[3][10] J A[5][8] K A[4][9] 【解答】D，E，K 【分析】数组A为9行10列，共有90个元素，所以，存放A至少需要90×6=540个存储单元，第8列和第5行共有18个元素（注意行列有一个交叉元素），所以，共占108个字节，元素A[8][5]按行优先存储的起始地址为d+8×10+5=d+85，设元素A[i][j]按列优先存储的起始地址与之相同，则d+j×9+i=d+85，解此方程，得i=4，j=9。

⑵ 将数组称为随机存取结构是因为（）

A 数组元素是随机的 B 对数组任一元素的存取时间是相等的 C 随时可以对数组进行访问 D 数组的存储结构是不定【解答】B ⑶ 下面的说法中，不正确的是（）

A 数组是一种线性结构 B 数组是一种定长的线性结构 C 除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等 D 数组的基本操作有存取、修改、检索和排序等，没有插入与删除操【解答】C 【分析】数组属于广义线性表，数组被创建以后，其维数和每维中的元素个数是确定的，所以，数组通常没有插入和删除操作。

⑷ 对特殊矩阵采用压缩存储的目的主要是为了（）

A 表达变得简单 B 对矩阵元素的存取变得简单 C 去掉矩阵中的多余元素 D 减少不必要的存储空间【解答】D 【分析】在特殊矩阵中，有很多值相同的元素并且他们的分布有规律，没有必要为值相同的元素重复存储。⑸ 下面（）不属于特殊矩阵。

A 对角矩阵 B 三角矩阵 C 稀疏矩阵 D 对称矩阵【解答】C ⑹ 若广义表A满足Head(A)=Tail(A)，则A为（）

A()B(())C((),())D((),(),())【解答】B ⑺ 下面的说法中，不正确的是（）A 广义表是一种多层次的结构 B 广义表是一种非线性结构 C 广义表是一种共享结构 D 广义表是一种递归【解答】B 【分析】从各层元素各自具有的线性关系讲，广义表属于线性结构。⑻ 下面的说法中，不正确的是（）

A 对称矩阵只须存放包括主对角线元素在内的下（或上）三角的元素即可。B 对角矩阵只须存放非零元素即可。

C 稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储。

D 稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储【解答】D 【分析】稀疏矩阵中大量值为零的元素分布没有规律，因此采用三元组表存储。如果零元素的分布有规律，就没有必要存储非零元素的行号和列号，而需要按其压缩规律找出相应的映象函数。3.判断题

⑴ 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。【解答】错。例如二维数组可以看成是数据元素为线性表的线性表。⑵ 使用三元组表存储稀疏矩阵的元素，有时并不能节省存储空间。

【解答】对。因为三元组表除了存储非零元素值外，还需要存储其行号和列号。⑶ 稀疏矩阵压缩存储后，必会失去随机存取功能。

【解答】对。因为压缩存储后，非零元素的存储位置和行号、列号之间失去了确定的关系。

⑷ 线性表可以看成是广义表的特例，如果广义表中的每个元素都是单元素，则广义表便成为线性表。【解答】对。

⑸ 若一个广义表的表头为空表，则此广义表亦为空表。

【解答】错。如广义表L=(()，(a，b))的表头为空表，但L不是空表。4．一个稀疏矩阵如图4-4所示，写出对应的三元组顺序表和十字链表存储表示。

【解答】对应的三元组顺序表如图4-5所示，十字链表如图4-6所示。

5．设某单位职工工资表ST由“工资”、“扣除”和“实发金额”三项组成，其中工资项包括“基本工资”、“津贴”和“奖金”，扣除项包括“水”、“电”和“煤气”。

⑴ 请用广义表形式表示所描述的工资表ST，并用表头和表尾求表中的“奖金”项； ⑵ 画出该工资表ST的存储结构。

【解答】⑴ ST=((基本工资，津贴，奖金)，(水，电，煤气)，实发金额)Head(Tail(Tail(Head(ST))))=奖金 ⑵ 工资表ST的头尾表示法如图4-7所示。

学习自测及答案 1．二维数组M中每个元素的长度是3个字节，行下标从0到7，列下标从0到9，从首地址d开始存储。若按行优先方式存储，元素M[7][5]的起始地址为（），若按列优先方式存储，元素M[7][5]的起始地址为（）。【解答】d+22，d+141 2．一个n×n的对称矩阵，按行优先或列优先进行压缩存储，则其存储容量为（）。【解答】n(n+1)/2 3．设n行n列的下三角矩阵A（行列下标均从1开始）已压缩到一维数组S[1]~S[n(n+1)/2]中，若按行优先存储，则A[i][j]在数组S中的存储位置是（）。【解答】i×(i-1)/2+j 4．已知广义表LS=(a,(b, c),(d, e, a))，运用Head函数和Tail函数取出LS中原子d的运算是（）。【解答】Head(Head(Tail(Tail(LS))))5．广义表(a, b,(c,(d)))的表尾是（）。

A(d)B(c,(d))C b,(c,(d))D(b,(c,(d)))【解答】D 6．设有三对角矩阵An×n（行、列下标均从0开始），将其三条对角线上的元素逐行存于数组B[3n-2]中，使得B[k]=aij求：

⑴ 用i, j表示k的下标变换公式； ⑵ 用k表示i, j的下标变换公式。

【解答】⑴ 要求i, j表示k的下标变换公式，就是要求在k之前已经存储了多少个非零元素，这些非零元素的个数就是k的值。元素aij求所在的行为i，列为j，则在其前面的非零元素的个数是；k=2 + 3(i－1)+(j－i + 1)= 2i+ j。

⑵ 因为k和i, j之间是一一对应的关系，k+1是当前非零元素的个数，整除即为其所在行号，取余表示当前行中第几个非零元素，加上前面零元素所在列数就是当前列号，即：

第 5 章树和二叉树课后习题讲解

1.填空题

⑴ 树是n（n≥0）结点的有限集合，在一棵非空树中，有（）个根结点，其余的结点分成m（m＞0）个（）的集合，每个集合都是根结点的子树。【解答】有且仅有一个，互不相交

⑵ 树中某结点的子树的个数称为该结点的（），子树的根结点称为该结点的（），该结点称为其子树根结点的（）。

【解答】度，孩子，双亲

⑶ 一棵二叉树的第i（i≥1）层最多有（）个结点；一棵有n（n>0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。【解答】2i-1，(n+1)/2，(n-1)/2 【分析】设满二叉树中叶子结点的个数为n0，度为2的结点个数为n2，由于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。⑷ 设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值是（）。【解答】2h-1，2h-1 【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。⑸ 深度为k的二叉树中，所含叶子的个数最多为（）。【解答】2k-1 【分析】在满二叉树中叶子结点的个数达到最多。⑹ 具有100个结点的完全二叉树的叶子结点数为（）。【解答】50 【分析】100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为50，也就是说，从编号51开始均为叶子。

⑺ 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有（）个叶子结点。【解答】12 【分析】根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。

⑻ 某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（）。【解答】CDBGFEA 【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来。

⑼ 在具有n个结点的二叉链表中，共有（）个指针域，其中（）个指针域用于指向其左右孩子，剩下的（）个指针域则是空的。【解答】2n，n-1，n+1 ⑽ 在有n个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（）。【解答】n，n-1 【分析】n-1个分支结点是经过n-1次合并后得到的。2.选择题

⑴ 如果结点A有3个兄弟，B是A的双亲，则结点B的度是（）。A 1 B 2 C 3 D 4 【解答】D ⑵ 设二叉树有n个结点，则其深度为（）。A n-1 B n C 【解答】D 【分析】此题并没有指明是完全二叉树，则其深度最多是n，最少是

+1。

+1 D 不能确定

⑶ 二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。

A 空或只有一个结点 B 高度等于其结点数 C 任一结点无左孩子 D 任一结点无右孩子【解答】B 【分析】此题注意是序列正好相反，则左斜树和右斜树均满足条件。⑷ 线索二叉树中某结点R没有左孩子的充要条件是（）。

A R.lchild=NULL B R.ltag=0 C R.ltag=1 D R.rchild=NULL 【解答】C 【分析】线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左标志是否为1。

⑸一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（）成立。A n=h+m B h+m=2n C m=h-1 D n=2m-1 【解答】D 【分析】满二叉树中没有度为1的结点，所以有m个叶子结点，则度为2的结点个数为m-1。⑹任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（）。A 肯定不发生改变 B 肯定发生改变 C 不能确定 D 有时发生变化【解答】A 【分析】三种遍历次序均是先左子树后右子树。

⑺如果T' 是由有序树T转换而来的二叉树，那么T中结点的前序序列就是T' 中结点的（）序列，T中结点的后序序列就是 T' 中结点的（）序列。

A 前序 B 中序 C 后序 D 层序【解答】A，B ⑻设森林中有4棵树，树中结点的个数依次为n1、n2、n3、n4，则把森林转换成二叉树后，其根结点的右子树上有（）个结点，根结点的左子树上有（）个结点。A n1-1 B n1 C n1+n2+n3 D n2+n3+n4 【解答】D，A 【分析】由森林转换的二叉树中，根结点即为第一棵树的根结点，根结点的左子树是由第一棵树中除了根结点以外其余结点组成的，根结点的右子树是由森林中除第一棵树外其他树转换来的。⑼ 讨论树、森林和二叉树的关系，目的是为了（）。A 借助二叉树上的运算方法去实现对树的一些运算

B 将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题 C 将树、森林转换成二叉树 D 体现一种技巧，没有什么实际意义【解答】B 3.判断题

⑴ 在线索二叉树中，任一结点均有指向其前趋和后继的线索。

【解答】错。某结点是否有前驱或后继的线索，取决于该结点的标志域是否为1。⑵ 在二叉树的前序遍历序列中，任意一个结点均处在其子女的前面。【解答】对。由前序遍历的操作定义可知。⑶ 二叉树是度为2的树。

【解答】错。二叉树和树是两种不同的树结构，例如，左斜树是一棵二叉树，但它的度为1。⑷ 由树转换成二叉树，其根结点的右子树总是空的。【解答】对。因为根结点无兄弟结点。⑸ 用一维数组存储二叉树时，总是以前序遍历存储结点。

【解答】错。二叉树的顺序存储结构是按层序存储的，一般适合存储完全二叉树。4．证明：对任一满二叉树，其分枝数B＝2(n0-1)。（其中，n0为终端结点数）【解答】因为在满二叉树中没有度为1的结点，所以有：n=n0+n2 设B为树中分枝数，则n=B+1；所以B=n0 +n2-1 再由二叉树性质：n0=n2+1，代入上式有：B=n0+n0-1-1=2(n0-1)

5．已知一棵度为m的树中有：n1个度为1的结点，n2个度为2的结点，„„，nm个度为m的结点，问该树中共有多少个叶子结点？

【解答】设该树的总结点数为n，则n=n0+n1+n2+„„+nm

又：n=分枝数+1=0×n0+1×n1+2×n2+„„+m×nm+1，由上述两式可得： n0= n2+2n3+„„+(m-1)nm+1

6．已知二叉树的中序和后序序列分别为CBEDAFIGH和CEDBIFHGA，试构造该二叉树。【解答】二叉树的构造过程如图5-12 所示。

7．对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。【解答】构造的哈夫曼树如图5-13所示。

树的带权路径长度为： WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2=120

8．已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用[0，1]进行前缀编码，问该字符串的编码至少有多少位。【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图5-14所示。其带权路径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，该字符串的编码长度至少为98位。

9．算法设计

⑴ 设计算法按前序次序打印二叉树中的叶子结点。

【解答】本算法的要求与前序遍历算法既有相同之处，又有不同之处。相同之处是打印次序均为前序，不同之处是此处不是打印每个结点的值，而是打印出其中的叶子结点，即为有条件打印。为此，将前序遍历算法中的访问操作改为条件打印即可。算法如下：

⑵ 设计算法求二叉树的深度。

【解答】当二叉树为空时，深度为0；若二叉树不为空，深度应是其左右子树深度的最大值加1，而其左右子树深度的求解又可通过递归调用本算法来完成。具体算法如下：

⑶ 编写算法，要求输出二叉树后序遍历序列的逆序。

【解答】要想得到后序的逆序，只要按照后序遍历相反的顺序即可，即先访问根结点，再遍历根结点的右子树，最后遍历根结点的左子树。注意和前序遍历的区别，具体算法如下：

⑷ 以孩子兄弟表示法做存储结构，求树中结点x的第i个孩子。

【解答】先在链表中进行遍历，在遍历过程中查找值等于x的结点，然后由此结点的最左孩子域firstchild找到值为x结点的第一个孩子，再沿右兄弟域rightsib找到值为x结点的第i个孩子并返回指向这个孩子的指针。

树的孩子兄弟表示法中的结点结构定义如下： template struct Tnode { T data;TNode *firstchild, *rightsib;};具体算法如下：

学习自测及答案

0．前序遍历和中序遍历结果相同的二叉树是（）。A 根结点无左孩子的二叉树 B 根结点无右孩子的二叉树 C 所有结点只有左子树的二叉树 D 所有结点只有右子树的二叉树【解答】D 1．前序遍历和中序遍历结果相同的二叉树是（）。A 根结点无左孩子的二叉树 B 根结点无右孩子的二叉树 C 所有结点只有左子树的二叉树 D 所有结点只有右子树的二叉树【解答】D 2．由权值为{3, 8, 6, 2, 5}的叶子结点生成一棵哈夫曼树，其带权路径长度为（）。A 24 B 48 C 53 D 72 【解答】C 3．用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1] ~ A[n]中，结点A[i]若有左子树，则左子树的根结点是（）。

A A[2i-1] B A[2i+1] C A[i/2] D A[2i] 【解答】D 4．对任何一棵二叉树T，如果其终端结点的个数为n0，度为2的结点个数为n2，则（）。A n0=n2-1 B n0=n2 C n0=n2+1 D 没有规律【解答】C 5．一棵满二叉树中共有n个结点，其中有m个叶子结点，深度为h，则（）。A n=h+m B h+m=2n C m=h-1 D n=2h-1 【解答】D 6．对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（）。

A h B h+1 C h或h+1 D 任意【解答】C 7．假定一棵度为3的树中结点数为50，则其最小高度应为。A 3 B 4 C 5 D 6 【解答】C 8．在线索二叉树中，一个结点是叶子结点的充要条件为（）。

A 左线索标志为0，右线索标志为1 B 左线索标志为1，右线索标志为0 C 左、右线索标志均为0 D 左、右线索标志均为1 【解答】C 9．对于一棵具有n个结点的树，其所有结点的度之和为（）。【解答】n-1 10．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是（）。【解答】

11．现有按前序遍历二叉树的结果ABC，问有哪几种不同的二叉树可以得到这一结果？【解答】共有5种二叉树可以得到这一结果，如图5-15所示。

12．试找出分别满足下列条件的所有二叉树： ⑴ 前序序列和中序序列相同。⑵ 中序序列和后序序列相同。⑶ 前序序列和后序序列相同。

【解答】 ⑴ 空二叉树、只有一个根结点的二叉树和右斜树。⑵ 空二叉树、只有一个根结点的二叉树和左斜树。⑶ 空二叉树、只有一个根结点的二叉树

13．将下面图5-16所示的树转换为二叉树，图5-17所示的二叉树转换为树或森林。

【解答】图5-16所示树转换的二叉树如图5-18所示，图5-17所示二叉树转换的森林如图5-19所示。

14．以孩子兄弟表示法作为存储结构，编写算法求树的深度。

【解答】采用递归算法实现。若树为空树，则其深度为0，否则其深度等于第一棵子树的深度+1和兄弟子树的深度中的较大者。具体算法如下：

第7章图选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（）A）O(n)B）O(n+e)C）O(n*n)D）O(n*n*n)【答案】B 2．设无向图的顶点个数为n，则该图最多有（）条边。A）n-1 B）n(n-1)/2 C）n(n+1)/2 D）n

2【答案】B 3．连通分量指的是（）

A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图【答案】B 4．n个结点的完全有向图含有边的数目（）A）n*n B）n（n+1）C）n/2

D）n*（n-1）

【答案】D 5．关键路径是（）

A）AOE网中从源点到汇点的最长路径【答案】A 6．有向图中一个顶点的度是该顶点的（）

A）入度 B）出度 C）入度与出度之和 D）（入度+出度）/2 【答案】C 7．有e条边的无向图，若用邻接表存储，表中有（）边结点。A）e B）2e C）e-1 D）2(e-1)【答案】B 8．实现图的广度优先搜索算法需使用的辅助数据结构为（）A）栈 B）队列 C）二叉树 D）树【答案】B 9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（）A）栈 B）队列 C）二叉树 D）树【答案】A 10．存储无向图的邻接矩阵一定是一个（）

A）上三角矩阵 B）稀疏矩阵 C）对称矩阵 D）对角矩阵【答案】C 11．在一个有向图中所有顶点的入度之和等于出度之和的（）倍 A）1/2 【答案】B 12．在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（）A）O(n)B）O(n+e)C）O(n)D）O(n)【答案】B 13．下列关于AOE网的叙述中，不正确的是（）A）关键活动不按期完成就会影响整个工程的完成时间 B）任何一个关键活动提前完成，那么整个工程将会提前完成 C）所有的关键活动提前完成，那么整个工程将会提前完成 D）某些关键活动提前完成，那么整个工程将会提前完成【答案】B

2B）AOE网中从源点到汇点的最短路径

C）AOV网中从源点到汇点的最长路径 D）AOV网中从源点到汇点的最短路径

B）1 C）2 D）4 14．具有10个顶点的无向图至少有多少条边才能保证连通（）A）9 【答案】A 15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A）e B）2e C）n-e D）n-2e 【答案】D 2 填空题

1．无向图中所有顶点的度数之和等于所有边数的_____________倍。【答案】2 2．具有n个顶点的无向完全图中包含有_____________条边，具有n个顶点的有向完全图中包含有_____________条边。

【答案】（1）n(n-1)/2（2）n(n-1)3．一个具有n个顶点的无向图中，要连通所有顶点则至少需要_____________条边。【答案】n-1 4．假定一个图具有n个顶点和e条边，则采用邻接矩阵、邻接表表示时，其相应的空间复杂度分别为_____________和_____________。【答案】（1）O(n)（2）O(n+e)5．对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为_____________，对用邻接表表示的图进行任一种遍历时，其时间复杂度为_____________。【答案】（1）O(n)（2）O(e)6．对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为_____________和_____________条。【答案】（1）e（2）2e 7．在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有_____________和_____________结点。【答案】（1）出边（2）入边

8．对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表表示时，求任一顶点度数的时间复杂度依次为_____________和_____________。【答案】（1）O(n)（2）O(e+n)9．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为_____________和_____________。

【答案】（1）n（2）n-1 10．Prim算法和Kruscal算法的时间复杂度分别为_____________和_____________。【答案】（1）O(n)（2）O(eloge)11．针对下图所示的连通网络，试按如下格式给出在Kruscal算法构造最小生成树过程中顺序选出的各条22

222B）10 C）11 D）12 边。

【答案】设边的信息表示为（始点，终点，权值），则在Kruscal算法构造最小生成树过程中顺序选出的各条边为：（3，5，1），（2，4，2），（1，5，3），（1，2，3）。3 判断题

1．图是一种非线性结构，所以只能用链式存储。（）【答案】× 2．图的最小生成树是唯一的。（）【答案】×

3．如果一个图有n个顶点和小于n-1 条边，则一定是非连通图。（）【答案】√ 4．有n-1 条边的图一定是生成树。（）【答案】×

5．用邻接矩阵表示图时，矩阵元素的个数与顶点个数相关，与边数无关。（）【答案】√

6．用邻接表表示图时，顶点个数设为n，边的条数设为e，在邻接表上执行有关图的遍历操作时，时间代价为O(n+e)。（）【答案】√

7．逆邻接表只能用于有向图，邻接表对于有向图和无向图的存储都适用。（）【答案】√ 8．任何一个关键活动提前完成, 那么整个工程将会提前完成。（）【答案】× 9．在AOE网络中关键路径只有一条。（）【答案】×

10．在AOV网络中如果存在环，则拓扑排序不能完成。（）【答案】√ 11．图的邻接矩阵存储是唯一的，邻接表存储也是唯一的。（）【答案】×

12．假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是O(n*e)。（）【答案】×

13．任意一个图都是其自身的子图。（）【答案】√

14．一个无向连通图的生成树是含有该连通图的全部顶点的极大连通子图。（）【答案】× 4 应用题

1．设有一有向图为G=(V，E)。其中，V={ v1, v2, v3, v4, v5}，E={, , , , , , }，请画出该有向图并判断是否是强连通图。分析：作该题的关键是弄清楚以下两点

（1）边集E中表示一条以vi为弧尾，vj为弧头的有向弧。（2）强连通图是任意两顶点间都存在路径的有向图。【答案】该有向图是强连通图，表示如下：

2．画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。并说明在n个顶点的无向完全图中，边的条数为n(n-1)/2。【答案】

【解析】因为在有n个顶点的无向完全图中，每一个顶点与其它任一顶点都有一条边相连，所以每一个顶点有n-1条边与其他顶点相连，则 n个顶点有n(n-1)条边。但在无向图中，顶点i到顶点j与顶点j到顶点i是同一条边，所以总共有n(n-1)/2条边。

3．对n个顶点的无向图G，采用邻接矩阵表示，如何判别下列有关问题：（1）图中有多少条边?（2）任意两个顶点i和j是否有边相连?（3）任意一个顶点的度是多少? 【答案】

（1）无向图的邻接矩阵是对称的，故它的边数应是上三角或下三角的非0元个数。（2）邻接矩阵中如果第i行第j列的元素非0则表示顶点i与顶点j相连。（3）任意一个顶点vi的度是第i行或第i列上非0元的个数。

4．熟悉图的存储结构，画出下面有向图的邻接矩阵、邻接表、逆邻接表、十字链表。写出邻接表表示的图从顶点A出发的深度优先遍历序列和广度优先遍历序列。

【答案】

邻接矩阵如下：邻接表如下：

逆邻接表如下：

十字链表如下：

深度优先遍历序列为ABCFED，广度优先遍历序列为ABDCEF 5．已知下面是某无向图的邻接表，画出该无向图，并分别给出从A出发的深度优先搜索生成树和广度优先搜索生成树。

【解析】作该题的关键是弄清楚邻接表的概念，理解深度优先搜索和广度优先搜索的全过程以及二者的区别。

【答案】该无向图如下所示：

深度优先搜索生成树为：广度优先搜索生成树为：

6．请分别用Prim算法和Kruskal算法构造以下网络的最小生成树，并求出该树的代价。

【解析】Prim算法的操作步骤：首先从一个只有一个顶点的集合开始，通过加入与其中顶点相关联的最小代价的边来扩充顶点集，直到所有顶点都在一个集合中。【答案】

【解析】Kruscal算法的操作步骤：首先将n个顶点看成n个互不连通的分量，从边集中找最小代价的边，如果落在不同连通分量上，则将其加入最小生成树，直到所有顶点都在同一连通分量上。【答案】

7．写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开始时间和最晚开始时间。

【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下（1）求事件的最早发生时间ve(j), 最晚发生时间vl(j);（2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到 vl(0);（3）计算e(i),l(i)：设ai由弧表示，持续时间记为dut，则有下式成立 e(i)=ve(j)l(i)=vl(k)-dut()（4）找出e(i)-l(i)=0的活动既是关键活动。【答案】

关键路径为：a0->a4->a6->a9 8．拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。

【解析】解题关键是弄清拓扑排序的步骤（1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。【答案】（1）0132465（2）0123465 9．给定带权有向图G和源点v1,利用迪杰斯特拉（Dijkstra）算法求从v1到其余各顶点的最短路径。

【解析】求解该题的关键是掌握迪杰斯特拉（Dijkstra）算法的设计原理----从一个顶点v到另一顶点vk的最短路径或者是(v,vk)或者是(v,vj,vk),它的长度或者是从v到vk弧上的权值，或者是D[j]与vj到vk弧上的权值之和，其中D[j]是已经找到的从v到vj的最短路径。【答案】S是已找到最短路径的终点的集合。

10．利用Floyd算法求下图中各对顶点之间的路径。

【解析】Floyd算法是依次添加顶点来修改相应路径，也就是说,若（vi，．．．，vk）和(vk，．．．，vj)分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径，则将（vi，．．．vk，．．．，vj）和已经得到的从vi到vj且中间顶点序号不大于k-１的最短路径相比较，其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。经过n次比较后必求得vi到vj的最短路径，依次，可求得各对顶点间的最短路径。

求解的关键是求解如下的一个n阶方阵序列： D(-1)，D，D，．．．，D，D[i][j]=G．arcs[i][j](k-1)(0)(1)(k)(n-1)其中 D(-1)(k)D=Min{D【答案】 [i][j]，D(k-1)[i][k]+D

(k-1)

[k][j]} 0≤k≤n-1

每对顶点之间的最短路径及长度总结如下：顶点A到顶点C最短路径为：A->C，长度为：１顶点A到顶点B最短路径为：A->C->B，长度为：4 顶点C到顶点A最短路径为：C->B->A，长度为：12 顶点C到顶点B最短路径为：C->B，长度为：3 顶点B到顶点A最短路径为：B->A，长度为：9 顶点B到顶点C最短路径为：B->A->C，长度为：10

第8章查找选择题

1．顺序查找法适合于存储结构为（）的线性表。

A）散列存储 B）顺序存储或链接存储 C）压缩存储 D）索引存储【答案】B 2．下面哪些操作不属于静态查找表（）A）查询某个特定元素是否在表中 C）插入一个数据元素

B）检索某个特定元素的属性 D）建立一个查找表【答案】C 3．下面描述不正确的是（）

A）顺序查找对表中元素存放位置无任何要求，当n较大时，效率低。B）静态查找表中关键字有序时，可用二分查找。C）分块查找也是一种静态查找表。

D）经常进行插入和删除操作时可以采用二分查找。【答案】D 4．散列查找时，解决冲突的方法有（）A）除留余数法【答案】D 5．若表中的记录顺序存放在一个一维数组中，在等概率情况下顺序查找的平均查找长度为（）A）O（1）

【答案】C 6．对长度为4的顺序表进行查找，若第一个元素的概率为1/8，第二个元素的概率为1/4，第三个元素的概率为3/8，第四个元素的概率为1/4，则查找任一个元素的平均查找长度为（）A）11/8 B）7/4 【答案】C 【解析】对顺序表查找，ASL＝，代入题目得： ASL=4*(1/8)+3*(1/4)+2*(3/8)+1*(1/4)=9/4 7．静态查找表与动态查找表二者的根本差别在于（）

A）它们的逻辑结构不一样 B）施加在其上的操作不同 C）所包含的数据元素的类型不一样 D）存储实现不一样【答案】B 8．若查找表中的记录按关键字的大小顺序存放在一个一维数组中，在等概率情况下二分法查找的平均检索长度是（）A）O(n)【答案】B 9．对有14个数据元素的有序表R[14]（假设下标从1开始）进行二分查找，搜索到R[4]的关键码等于给定值，此时元素比较顺序依次为（）。

A）R[1]，R[2]，R[3]，R[4] B）R[1]，R[13]，R[2]，R[3] C）R[7]，R[3]，R[5]，R[4] D）R[7]，R[4]，R[2]，R[3] 【答案】C 10．设有一个长度为100的已排好序的表，用二分查找进行查找，若查找不成功，至少比较（）次。A）9 B）8

C）7

D）6 【答案】B 【解析】二分查找不成功时和给定值进行比较的关键字个数最多不超过二叉判定树的深度。100个元素查找表的判定树深为8（64<100<128）。

11．请指出在顺序表{2,5,7,10,14,15,18,23,35,41,52}中，用二分法查找关键码12需做（）次关键码比较。A）2 B）3 C）4

D）5 【答案】C 12．从具有 n 个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为()。A)O(n)B）O（1）C）O(log 2 n)D）O(n)【答案】C

2B）数字分析法 C）直接定址法 D）链地址法

B）O(log2n)C）O(n)D）O(n)C）9/4 D）11/4 B）O(log2n)C）O(nlog2n)D）O((log2n))

213．分块查找时确定块的查找可以用顺序查找，也可以用（），而在块中只能是（）A）静态查找，顺序查找

C）二分查找，二分查找

【答案】B 14．采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（）个结点最佳。A）10 B）25

C）6 D）625 【答案】B 15．采用分块查找法（块长为s，以二分查找确定块）查找长度为n的线性表时，每个元素的平均查找长度为（）

A）s+n B）log2n＋s/2 C）log2(n/s+1)+s/2 D）(n+s)/2 【答案】C 16．对一棵二叉排序树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是（）A）小于

【答案】A 17．若二叉排序树中关键字互不相同，则下面命题中不正确的是（）A）最小元和最大元一定是叶子 B）最大元必无右孩子 C）最小元必无左孩子【答案】A 18．设二叉排序树中关键字由1至1000的整数构成，现要查找关键字为363的结点，下述关键字序列（）不可能是在二叉排序树上查找到的序列? A）2,252,401,398,330, 344,397,363 B）924, 220, 911, 244, 898, 258, 362, 363 C）2, 399, 387, 219, 266, 382, 381, 278, 363 D）925, 202, 911, 240, 912, 245, 363 【答案】D 19．在初始为空的散列表中依次插入关键字序列(MON,TUE,WED,THU,FRI,SAT,SUN),散列函数为H(k)=i MOD 7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为 [0:6]，采用线性再散列法处理冲突。插入后的散列表应该如（）所示。

A）0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON B）0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MON C）0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON D）0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON 【答案】B 20．若根据查找表建立长度为 m 的散列表，采用线性探测法处理冲突，假定对一个元素第一次计算的散列地址为 d，则下一次的散列地址为()。

A）d B）(d+1)%m C）(d+1)/m D）d+1 【答案】B 21．若根据查找表建立长度为 m 的散列表，采用二次探测法处理冲突，假定对一个元素第一次计算的散列地址为 d，则第四次计算的散列地址为()。

D）新结点总是作为叶结点插入二叉排序树 B）大于

C）等于

D）不小于

B）二分查找，顺序查找 D）散列查找，顺序查找 A)(d+1)%m B）(d-1)%m C）(d+4)%m D）(d-4)%m 【答案】D 22．下面有关散列查找的说法中正确的是（）A）直接定址法所得地址集合和关键字集合的大小不一定相同。

B）除留余数法构造的哈希函数H(key)=key MOD p，其中P必须选择素数。C）构造哈希函数时不需要考虑记录的查找频率。

D）数字分析法适用于对哈希表中出现的关键字事先知道的情况。【答案】D 23．下面有关散列冲突解决的说法中不正确的是（）

A）处理冲突即当某关键字得到的哈希地址已经存在时，为其寻找另一个空地址。B）使用链地址法在链表中插入元素的位置随意，即可以是表头表尾，也可以在中间。C）二次探测能够保证只要哈希表未填满，总能找到一个不冲突的地址。D）线性探测能够保证只要哈希表未填满，总能找到一个不冲突的地址。【答案】C 24．设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7其余地址为空，如用二次探测处理冲突，关键字为49的结点的地址是（）A）8 B）3 C）5

D）9 【答案】D 2 填空题

1．在散列函数H(key)=key%p中，p应取_____________。【答案】素数

2．采用分块查找法（块长为s，以顺序查找确定块）查找长度为n的线性表时的平均查找长度为_____________。【答案】(n/s+1)/2+1 3．己知一个有序表为(12,18,20,25,29,32,40,62,83,90,95,98)，当二分查找值为29和90的元素时，分别需要_____________次和_____________次比较才能查找成功；若采用顺序查找时，分别需要_____________次和_____________次比较才能查找成功。【答案】（1）4（2）4（3）5（4）10 4．从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明 _____________，若元素的值小于根结点的值，则继续向 _____________查找，若元素的值大于根结点的值，则继续向 _____________ 查找。【答案】（1）查找成功

（2）左子树

（3）右子树 5．二分查找的存储结构仅限于 _____________，且是_____________。【答案】（1）顺序存储结构（2）有序

6．假设在有序线性表A[1..20]上进行二分查找，则比较一次查找成功的结点数为 _____________个，比较二次查找成功的结点数为_____________，比较三次查找成功的结点数为_____________，比较四次查找成功的结点数为_____________，比较五次查找成功的结点数为_____________，平均查找长度为_____________。

【答案】（1）1（2）2（3）4（4）8（5）5（6）3.7 7．在对有20个元素的递增有序表作二分查找时，查找长度为5的元素的下标从小到大依次为_____________。（设下标从1开始）【答案】4，9，14，17，20 8．对于线性表（70,34,55,23,65,41,20,100）进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有_____________个，散列地址为7的元素有_____________ 个。【答案】（1）2（2）2 9．索引顺序表上的查找分两个阶段：_____________、_____________。【答案】（1）确定待查元素所在的块（2）在块内查找待查的元素

10．分块查找中，要得到最好的平均查找长度，应对256个元素的线性查找表分成_____________块，每块的最佳长度是_____________。若每块的长度为8，则等概率下平均查找长度为_____________。【答案】（1）16（2）16

（3）21 【解析】分块查找的平均查找长度由两部分组成——查找索引表确定所在块的平均查找长度Lb和在块中查找元素的平均查找长度Lw，即ASLbs=Lb+Lw=(b+s)/2+1，其中s为每块的长度，b为所分的快数。由数学知识可知当s= 时，ASLbs可取得最小值＋1。因此，可得每块的最佳长度是16，应将查找表分为16块。若每块的长度为8，则b=32,因此ASLbs=Lb+Lw=(b+s)/2+1=21。

11．_____________是一棵二叉树，如果不为空，则它必须满足下面的条件： A）若左子树不空，则左子树上所有结点的值均小于根的值。B）若右子树不空，则右子树上所有结点的值均大于根的值。C）其左右子树均为二叉排序树。【答案】二叉排序树

13．假定有k个关键字互为同义词，若用线性探测法把这些同义词存入散列表中，至少要进行_____________次探测。

【答案】1+2+3...+(k-1)+k=k(k+1)/2 【解析】在散列表的一连串连续空间内，第一个关键字只需探测一次，第二个就要探测2次，如此这般，第k个关键字就要探测k次才能找到位置存放。3 判断题

1．对查找进行时间分析时，只需要考虑查找成功的平均情况。（）【答案】×

【解析】大多数情况下，特别查找表中记录数n很大时，查找不成功的概率可以忽略不计。但是，当查找不成功的情况不能忽视时，查找算法的平均查找长度应是查找成功时的平均查找长度与查找不成功时的平均查找长度之和。

2．在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。（）【答案】√

3．构造一个好的哈希函数必须均匀，即没有冲突。（）【答案】×

【解析】一个好的哈希函数必须均匀，并不代表完全没有冲突，而是尽量减少冲突。4．在一定情况下，有可能设计出无冲突的散列函数H。（）【答案】√

5.二分查找只适用于有序表，包括有序的顺序表和有序的链表。（）【答案】×

【解析】二分查找只适用于顺序表，而不能在链表结构中采用。因为链表查找都是从头指针开始。6．对给定的关键字集合，以不同的次序插入初始为空的树中，有可能得到同一棵二叉排序树。（）【答案】√

7．分块查找适用于任何有序表或者无序表。（）【答案】× 【解析】分块查找适用于任何有序表或者分块有序表，而不适用于任意的无序表。

8．在用线性探测法解决冲突所构造的散列表中，每组同义词中至少有一个元素的地址正好等于其散列地址。（）【答案】×

【解析】当存在堆积的冲突时，可能没有一个元素地址等于其计算所得的散列地址。9．对一棵二叉排序树中序遍历一定得到一个关键字的有序序列。（）【答案】√

10．所谓冲突即是两个关键字的值相同的元素，其散列地址相同。（）【答案】×

【解析】冲突是指两个关键字的值不相同的元素，计算得到的散列地址相同。11．二叉判定树和二叉排序树一样，都不是唯一的。（）【答案】×

【解析】对于同一组结点，由于建立二叉排序树时插入结点的先后次序不同，所构成的二叉排序树的形态及深度也不同，所以含有n个结点的二叉排序树不唯一。但二叉判定树却是唯一的。

12．若二叉树中每个结点的值均大于其左孩子的值，小于其右孩子的值，则该二叉树一定是二叉排序树。（）【答案】×

【解析】判定一棵二叉树是否是二叉排序除上面两个条件外，还必须满足第三个条件，即其左右子树也是二叉排序树。

13．分块查找中，每一块的大小是相同的。（）【答案】×

【解析】最末一块，可以不是整块，前面块的大小必须相同。

14．对一个有序表作二分查找，查找每个元素所需的查找次数均比用顺序查找所需的查找次数要少。（）【答案】×

【解析】顺序查找时最少的比较次数为1，它的比较次数小于位于二叉判定树第二层以上的结点。二分查找时最多的比较次数为二叉判定树的深度。

15．散列表的查找效率主要取决于所选择的散列函数与处理冲突的方法。（）【答案】√ 4 应用题

1．顺序查找时间为O(n)，二分法查找时间为O(log2n)，散列法为O(1)，为什么有高效率的查找方法而低效率的方法不被放弃? 【答案】不同的查找方法适用的范围不同，高效率的查找方法并不是在所有情况下都比其他查找方法效率要高，而且也不是在所有情况下都可以采用。

2．对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较? 【答案】n-1次

【解析】设变量max和min用于存放最大元和最小元(的位置)，第一次取两个元素进行比较，大的放入max，小的放入min。从第2次开始，每次取一个元素先和max比较，如果大于max则以它替换max，并结束本次比较；若小于max则再与min相比较，在最好的情况下，比较下去都不用和min相比较，所以这种情况下，至少要进行n-1次比较就能找到最大元和最小元。

3．若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：

（1）查找不成功，即表中无关键字等于给定值K的记录；（2）查找成功，即表中有关键字等于给定值K的记录。【答案】

（1）不成功时需要n+1 次比较（2）成功时平均为(n+1)/2次

【解析】有序表和无序表顺序查找时，都需要进行n+1次比较才能确定查找失败。因此平均查找长度都为n+1。查找成功时，平均查找长度都为(n+1)/2，有序表和无序表也是一样的。因为顺序查找与表的初始序列状态无关。

4．设有序表为(a, b, c, d, e, f, g, h, i, j, k, p, q)，请分别画出对给定值a, g和n进行折半查找的过程。【答案】

（1）查找a的过程如下(圆括号表示当前比较的关键字)，经过三次比较，查找成功。

（2）g的查找过程如下，一次比较成功。

[a b c d e f(g)h i（3）n的查找过程如下，经过四次比较，查找失败。

j k p q ]

5．为什么有序的单链表不能进行折半查找? 【答案】因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。

6．构造有12个元素的二分查找的判定树，并求解下列问题：（1）各元素的查找长度最大是多少？

（2）查找长度为1、2、3、4的元素各有多少？具体是哪些元素？（3）查找第5个元素依次要比较哪些元素？【答案】12个元素的判断树如下图所示：

（1）最大查找长度是树的深度4。（2）查找长度为1的元素有1个，为第6个，查找长度为2的元素有2个，为第3个和第9个，查找长度为3的元素有4个，为第1、4、7、11个，查找长度为4的元素有5个，为第2、5、8、10、12个。（3）查找第五个元素依次比较6，3，4，5。

7．以数据集合{1,2,3,4,5,6}的不同序列为输入，构造4棵高度为4的二叉排序树。【答案】

图（1）图（2）

图（3）图（4）

8．直接在二叉排序树中查找关键码K与从中序遍历输出的有序序列中用二分查找法查找关键码K，其数据比较次数是否相同？【答案】不相同。

【解析】因为二分查找得到的判定树和二叉排序树的形状不一定相同。9．已知一棵二叉排序树如下：

（1）假如删除关键字28，画出新二叉树。（2）若查找56，需和哪些关键字比较。【答案】（1）删除元素28后，需修改二叉排序树的形态，可用结点28左子树上最大的结点代替它如图（1），也可用其右子树上最小的结点代替它，如图（2）。

图（1）图（2）

2）若要查找56，需和38、49、55、56进行4次比较。

10．设散列函数为h(key)=key%101，解决冲突的方法为线性探测，表中用“-1”表示空单元。

（1）若删去散列表HT中的304（即令HT[1]=-1）之后，在表HT中查找707将会发生什么？

（2）若将删去的表项标记为“-2”，查找时探测到“-2”继续向前搜索，探测到“-1”时终止搜索。请问用这种方法删去304后能否正确地查找到707？【答案】

（1）查找707时，首先根据散列函数计算得出该元素应在散列表中的0单元，但是在0单元没有找到，因此将向下一单元探测，结果发现该单元是-1(为空单元)，所以结束查找，这将导致707无法找到。（2）如果改用“-2”作为删除标记，则可以正确找到707所在的结点。

11．已知散列表的地址区间为0～11，散列函数为H(k)=k % 11，采用线性探测法处理冲突，将关键字序列20,30,70,15,8,12,18,63,19依次存储到散列表中，试构造出该散列表，并求出在等概率情况下的平均查找长度。

【答案】构造散列表如下（每个元素的查找长度标注在该元素的下方）。

等概率情况下成功时的平均查找长度为（1×5＋2＋3＋4＋5）/9＝19/9 12．设散列函数为H(k)=k % 11，采用拉链法处理冲突，将上例中关键字序列依次存储到散列表中，并求出在等概率情况下的平均查找长度。【答案】

在等概率情况下成功的平均查找长度为：(1*5+2*2+3*1+4*1)/9=16/9 13．假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70)，散列地址空间为HT[13]，若采用除留余数法构造散列函数和线性探测法处理冲突，试求出每一元素的初始散列地址和最终散列地址，画出最后得到的散列表，求出平均查找长度。【答案】

构造的散列表如下：

在等概率情况下成功的平均查找长度为(1*7+2*5+3*1+4*1)/14=24/14 14．散列表的地址区间为0～15，散列函数为H(key)=key%13。设有一组关键字{19,01,23,14,55,20,84}, 采用线性探测法解决冲突，依次存放在散列表中。问：（1）元素84存放在散列表中的地址是多少？（2）搜索元素84需要的比较次数是多少？【答案】构造的散列表如下：

（1）元素84存放在散列表中的地址是8。（2）搜索元素84需要的比较3次。

第9章排序选择题

1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（）排序法。A）插入 B）选择 C）希尔 D）二路归并【答案】A 2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（）A）快速排序 B）直接插入排序 C）堆排序 D）归并排序【答案】B 3．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时，无序序列的变化情况如下： 25 84 21 47 15 27 68 35 20 20 15 21 25 47 27 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84 则所采用的排序方法是（）

Ａ）选择排序

Ｂ）希尔排序

Ｃ）归并排序

Ｄ）快速排序【答案】Ｄ

4．下面给出的四种排序法中，（）排序是不稳定排序法。A）插入 B）冒泡 C）二路归并 D）堆【答案】D 5．快速排序方法在（）情况下最不利于发挥其长处。Ａ）要排序的数据量太大

Ｂ）要排序的数据中含有多个相同值Ｃ）要排序的数据已基本有序Ｄ）要排序的数据个数为奇数【答案】Ｃ

6．一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）Ａ）38,40,46,56,79,84 B）40,38,46,79,56,84 C）40,38,46,56,79,84 D）40,38,46,84,56,79 【答案】Ｃ

7．对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为： 50,26,38,80,70,90 ,8,30,40,20 50,8,30,40,20,90,26,38,80,70 26,8,30,40,20,80,50,38,90,70 8,20,26,30,38,40,50,70,80,90 其使用的排序方法是（）

A）快速排序 B）基数排序 C）希尔排序 D）归并排序【答案】C 8．在文件“局部有序”或文件长度较小的情况下，最佳内部排序方法是（）A）直接插入排序 B）冒泡排序 C）简单选择排序 D）归并排序【答案】A 【解析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需n-1趟排序，也即时间复杂度仍为O(n)。而对简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为O(n log2)；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也即n-1趟比较的时间复杂度由O(n)降至O(n)。9．在下列算法中，（）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。

A）堆排序 B）冒泡排序 C）插入排序 D）快速排序【答案】C 【解析】在插入排序中，如果待排序列中的最后一个元素其关键字值为最小，则在最后一趟开始之前，前n-1个排好序的元素都不在其最终位置上，与排好序后的位置相差一个位置。因此，选C。

10．设有5000个无序的元素，希望用最快速度挑选出其中前10个最大的元素，在以下的排序方法中，采用（）方法最好

A）快速排序 B）堆排序 C）希尔排序【答案】B 【解析】用堆排序最好，因为堆排序不需要等整个排序结束就可挑出前10个最大元素，而快速排序和希尔排序都需等待整个排序结束才能知道前10个最大元素。

11．对给出的一组关键字{14，5，19，20，11，19}。若按关键字非递减排序，第一趟排序结果为{14，5，19，20，11，19}，问采用的排序算法是（）

A）简单选择排序 B）快速排序 C）希尔排序 D）二路归并排序【答案】C 12．以下序列不是堆的是（）A）100,85,98,77,80,60,82,40,20,10,66 B）100,98,85,82,80,77,66,60,40,20,10 C）10,20,40,60,66,77,80,82,85,98,100 D）100,85,40,77,80,60,66,98,82,10,20 【答案】D 【解析】根据堆采用完全二叉树的顺序存储形式及堆的特点，因第一个结点即根结点关键字值最大，则应建立一个大根堆，但依据此数据序列建立起堆后关键字值为40的左右孩子结点分别为60、66，不符合大根堆特点。

13．下面排序方法中，关键字比较次数与记录的初始排列无关的是（）A）希尔排序 B）冒泡排序 C）直接插入排序 D）直接选择排序【答案】D 【解析】如果初始排列基本有序，则对希尔排序来说，前几趟的插入工作大为减少。冒泡排序和直接插入

2排序都与初始排序序列有关，只有直接选择排序与初始序列无关．故选D。

14．一组记录的关键字为{45，80，55，40，42，85}，则利用堆排序的方法建立的初始堆为（）A）80,45,50,40,42,85 B）85,80,55,40,42, 45 C）85,80,55,45,42,40 D）85,55,80,42,45,40 【答案】B 15．一组记录的关键字为{25，50，15，35，80，85，20，40，36，70}，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果为（）A）15,25,35,50,20,40,80,85,36,70 B）15,25,35,50,80,20,85,40,70,36 C）15,25,50,35,80,85,20,36,40,70 D）15,25,35,50,80,20,36,40,70,85 【答案】A 【解析】对5个长度为2的有序表一趟归并后得到前两个长度为4的有序表和最后一个长度为2的有序表，故选A。

16．n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（）A）O(1)B）O(log2)C）O(n)D）O(n)【答案】D 【解析】最好情况下至少需要一趟排序，即比较n-1次，故选D。

17．n个元素进行快速排序的过程中，第一次划分最多需要移动（）次元素(包括开始将基准元素移到临时变量的那一次)。

A）n／2 B）n-1 C）n D）n+l 【答案】D 【解析】移动次数最多的情况是对n-1个元素比较时都需移动，加上开始将基准元素移到临时变量以及由临时变量移至正确位置的二次，即共需n+1次，故选D。18．下述几种排序方法中，要求内存量最大的是（）A）插入排序 B）选择排序 C）快速排序 D）归并排序【答案】D 【解析】插入排序和选择排序需要的辅助空间为O(1)，快速排序需要的辅助空间为O(log2)，归并排序需要的辅助空间为O(n)，因此选D。

19．下面排序方法中，时间复杂度不是O(n)的是（）

A）直接插入排序 B）二路归并排序 C）冒泡排序 D）直接选择排序【答案】B 【解析】直接插入排序、冒泡排序和直接选择排序的时间复杂度为O(n)，而二路归并排序的时间复杂度为O(n log2)，故选B。

20．对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是序列（）A）70,75,82,90, 23,16,10,68 B）70,75,68,23,10,16,90,82 C）82,75,70,16,10,90,68,23 D）23,10,16,70,82,75,68,90 【答案】A 【解析】快速排序第一趟划分的方法是：将第1个元素放入最终排好序序列中的正确位置上，则在这个位n

2nn

2置右边小于该元素值的元素都将移到其左边，在这个位置左边大于该元素值的元素都将其移到其右边。由此得到A需移动的元素最多，故选A。2 填空题

1．当数据量特别大需借助外部存储器对数据进行排序，则这种排序称为_____________。【答案】外部排序

2．在堆排序、快速排序和归并排序中，若从节省存储空间考虑，则应首先选取_____________方法，其次选取_____________方法；若只从排序结果的稳定性考虑，则应先择_____________方法；若只从平均情况下排序的速度来考虑，则选择_____________方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取_____________方法。

【答案】（1）堆排序

（2）快速排序

（3）归并排序（4）快速（5）堆

3．对n个元素的序列进行冒泡排序，最少的比较次数是_____________，此时元素的排列情况为_____________，在_____________情况下比较次数最多，其比较次数为_____（4）_ ____。【答案】

（1）n-1（2）从小到大排序（3）元素从大到小排列（4）n(n-1)/2 【解析】初始元素正序时，第一趟比较n-1次，并无数据交换，则不再比较，故只比较n-1次。若反序，则比较(n-1)+(n-2)+(n-3)+„..+2+1共n(n-1)/2次。

4．希尔排序是把记录按下标的一定增量分组，对每组记录进行直接插入排序，随着增量_____________，所分成的组包含的记录越来越多，当增量的值为_____________时，整个数组合为一组。【答案】（1）减少

（2）1 5．直接插入排序需借助的存储单元个数（空间复杂度）为_____________，最好情况下直接插入排序的算法时间复杂度为_____________，最坏情况下该算法的时间复杂度为_____________。【答案】（1）1（2）O(n)（3）O(n)6．对n个数据进行简单选择排序，所需进行的关键字间的比较次数为_____________，时间复杂度为_____________。

【答案】（1）n(n-1)/2（2）O(n)7．对于关键字序列(12，13，11，18，60，15，7，20，25，100)，用筛选法建堆，必须从键值为_____________的关键字开始。【答案】60 【解析】建堆必须从n／2结点开始，而10／2=5位置的结点值为60，故填60。

8．对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到已排序的有序表时，为寻找其插入位置需比较_____________次。【答案】3 【解析】当把第7个记录60插入到有序表时，则前6个记录已经有序，此时记录60由后向前与有序表中的元素进行比较，直到遇到值小于60的记录为止，也即在有序表(15，23，38，54，72，96)中共需比较3次，因此填3。

9．若对顺序存储在A[l]～A[9]的记录(76，38，62，53，80，74，83，65，85)进行堆排序，已知除第一个元素76外，以其余元素为根的结点都已是堆，则对第一个元素进行筛运算时，它将最终被筛到A数组下标为_____________的位置上。【答案】8 【解析】从树结构关键字值看，除根外是小根堆。对第一元素进行筛运算时，得到的数据序列为：38,53,62,65,80,74,83,76,85。

11．在时间复杂度为O(log2)的排序方法中，_____________排序方法是稳定的；在时间复杂度为O(n)的排序方法中，_____________排序方法是不稳定的。n

22【答案】（1）归并

（2）直接选择

12．设表中元素的初态是按键值递增的，若分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则_____________最省时间，_____________最费时间。【答案】（1）冒泡排序

（2）快速排序

【解析】若初始序列已经有序，则冒泡排序仅需一趟(比较n-1次)；而快速排序则需n-1趟，其时间复杂度升至O(n)。因此填：冒泡排序，快速排序。

13．从一个无序序列建立一个堆的方法是：首先将要排序的n个键值分放到一棵______________的各个结点中，然后从i=_____________的结点Ki开始，逐步把以Ki-

1、Ki-

2、„、K1为根的子树排成堆，直到以Kl为根的树排成堆，就完成了建堆的过程。【答案】（1）完全二叉树（2）n／2下取整。

14．在归并排序中，若待排序记录的个数为20，则共需要进行_____________趟归并，在第三趟归并中，是把长度为_____________的有序表归并为长度为_____________的有序表。【答案】（1）5（2）4（3）8 【解析】第一次把长度为1的归并为长度的2的子表共10个，第二次把长度为2的归并成长度为4的子表共5个，第三次把长度为4的归并为长度为8的共3个，第四次长度为8归并为长度为16的，第5次归并成一个有序表。3 判断题

1．对一个堆，按二叉树层次进行遍历可以得到一个有序序列（）【答案】×

【解析】堆的定义只规定了结点与其左、右孩子结点间的大小关系，而同一层上属不同父母的结点之间并无明确的大小关系，所以堆的层次遍历并不能得到一个有序序列。2．内部排序就是整个排序过程完全在内存中进行的排序（）【答案】√

3．在数据基本有序时，直接插入排序法一定是性能最好的算法（）【答案】×

【解析】在数据量较少且数据基本有序时，直接插入法性能较好，但当数据量大时，则该算法的性能会大大降低。

4．当数据序列已有序时，若采用冒泡排序法，数据比较n-1次（）【答案】√

5．内排序中的快速排序方法，在任何情况下均可得到最快的排序效果（）【答案】×

【解析】快速排序在待排序记录为随机分布时效果最好，基本有序时效果最差。6．用希尔方法排序时，若关键字的初始排序杂乱无序，则排序效率就低（）【答案】×

【解析】希尔排序又称“缩小增量排序”，即每趟只对相同增量距离的关键字进行比较，这与关键字序列初始有序或无序无关。

7．有一小根堆，堆中任意结点的关键字均小于它的左、右孩子关键字。则其具有最大值的结点一定是一个叶结点并可能在堆的最后两层中（）【答案】√

8．对n个记录的集合进行归并排序，在最坏情况下所需要的时间是O(n)（）【答案】×

【解析】归并排序不受记录初始序列的影响，即所谓的最坏情况，其所需时间也是O(nlog2)。9．对n个记录的集合进行冒泡排序，在最坏情况下所需要的时间是O(n)（）

第二篇：数据结构习题与答案

第 1 章绪论

课后习题讲解

1.填空

⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素

⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。【解答】数据项，数据元素

【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶ 从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。【解答】集合，线性结构，树结构，图结构

⑷ 数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系

⑸ 算法具有五个特性，分别是（）、（）、（）、（）、（）。【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性

⑹ 算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。【解答】自然语言，程序设计语言，流程图，伪代码，伪代码

⑺ 在一般情况下，一个算法的时间复杂度是（）的函数。【解答】问题规模

⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。【解答】Ο(1)，Ο(nlog2n)

【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。2.选择题

⑴ 顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构 B 非线性结构 C 存储位置 D 指针【解答】C，D

【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。A 树 B 图 C 线性表 D 集合【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。

⑶ 算法指的是（）。

A 对特定问题求解步骤的一种描述，是指令的有限序列。B 计算机程序 C 解决问题的计算方法 D 数据处理【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。⑷ 下面（）不是算法所必须具备的特性。A 有穷性 B 确切性 C 高效性 D 可行性【解答】C

【分析】高效性是好算法应具备的特性。

⑸ 算法分析的目的是（），算法分析的两个主要方面是（）。A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性

E 空间性能和时间性能 F 正确性和简明性

G 可读性和文档性 H 数据复杂性和程序复杂性【解答】C，E 3.判断题

【解答】错。如数组就没有插入和删除操作。此题注意是每种数据结构。

⑶ 所谓数据的逻辑结构指的是数据之间的逻辑关系。【解答】错。是数据之间的逻辑关系的整体。

⑷ 逻辑结构与数据元素本身的内容和形式无关。【解答】对。因此逻辑结构是数据组织的主要方面。⑸ 基于某种逻辑结构之上的基本操作，其实现是唯一的。

【解答】错。基本操作的实现是基于某种存储结构设计的，因而不是唯一的。4.分析以下各程序段，并用大O记号表示其执行时间。

【解答】⑴ 基本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n)。

⑵ 基本语句是k=k+10*i，共执行了n次，所以T(n)=O(n)。

⑶ 分析条件语句，每循环一次，i+j 整体加1，共循环n次，所以T(n)=O(n)。

⑷ 设循环体共执行T(n)次，每循环一次，循环变量y加1，最终T(n)=y，即：

(T(n)+1)2≤n，所以T(n)=O(n1/2)。

⑸ x++是基本语句，所以

5．设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。试画出其逻辑结构图并指出属于何种结构。

【解答】其逻辑结构图如图1-3所示，它是一种图结构。

6.为整数定义一个抽象数据类型，包含整数的常见运算，每个运算对应一个基本操作，每个基本操作的接口需定义前置条件、输入、功能、输出和后置条件。【解答】整数的抽象数据类型定义如下：

ADT integer Data 整数a：可以是正整数(1, 2, 3, …)、负整数(-1,-2,-3, …)和零 Operation Constructor

前置条件：整数a不存在输入：一个整数b

功能：构造一个与输入值相同的整数输出：无

后置条件：整数a具有输入的值

Set 前置条件：存在一个整数a 输入：一个整数b

功能：修改整数a的值，使之与输入的整数值相同

输出：无

后置条件：整数a的值发生改变

Add

前置条件：存在一个整数a 输入：一个整数b

功能：将整数a与输入的整数b相加

输出：相加后的结果

后置条件：整数a的值发生改变

Sub

前置条件：存在一个整数a 输入：一个整数b

功能：将整数a与输入的整数b相减

输出：相减的结果

后置条件：整数a的值发生改变

Multi

前置条件：存在一个整数a 输入：一个整数b

功能：将整数a与输入的整数b相乘

输出：相乘的结果

后置条件：整数a的值发生改变 Div

前置条件：存在一个整数a 输入：一个整数b

功能：将整数a与输入的整数b相除

输出：若整数b为零，则抛出除零异常，否则输出相除的结果

后置条件：整数a的值发生改变

Mod

前置条件：存在一个整数a 输入：一个整数b

功能：求当前整数与输入整数的模，即正的余数

输出：若整数b为零，则抛出除零异常，否则输出取模的结果

后置条件：整数a的值发生改变 Equal

前置条件：存在一个整数a 输入：一个整数b

功能：判断整数a与输入的整数b是否相等

输出：若相等返回1，否则返回0 后置条件：整数a的值不发生改变

endADT

7.求多项式A(x)的算法可根据下列两个公式之一来设计：

⑴ A(x)=anxn+an-1xn-1+…+a1x+a0 ⑵ A(x)=(…(anx+an-1)x+…+a1)x)+a0

根据算法的时间复杂度分析比较这两种算法的优劣。

【解答】第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进行了优化，减少了不必要的乘法运算。

8.算法设计（要求：算法用伪代码和C++描述，并分析最坏情况下的时间复杂度）⑴ 对一个整型数组A[n]设计一个排序算法。【解答】下面是简单选择排序算法的伪代码描述。

下面是简单选择排序算法的C++描述。

分析算法，有两层嵌套的for循环，所以。

⑵ 找出整型数组A[n]中元素的最大值和次最大值。【解答】算法的伪代码描述如下：

算法的C++描述如下：

分析算法，只有一层循环，共执行n-2次，所以，T(n)=O(n)。

学习自测及答案

1．顺序存储结构的特点是（），链接存储结构的特点是（）。

【解答】用元素在存储器中的相对位置来表示数据元素之间的逻辑关系，用指示元素存储地址的指针表示数据元素之间的逻辑关系。

2.算法在发生非法操作时可以作出处理的特性称为（）。【解答】健壮性

3.常见的算法时间复杂度用大Ｏ记号表示为：常数阶()、对数阶()、线性阶()、平方阶()和指数阶()。【解答】Ｏ(1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n)4．将下列函数按它们在n 时的无穷大阶数，从小到大排列。

n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n,(3/2)n, n!, n2+log2n

【解答】log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2,(3/2)n, n!5．试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

6.对下列用二元组表示的数据结构,试分别画出对应的逻辑结构图，并指出属于何种结构。

⑴ A=(D，R)，其中D={a1, a2, a3, a4}，R={ } ⑵ B=(D，R)，其中D={a, b, c, d, e, f}，R={，，} ⑶ C=(D，R)，其中D={a，b，c，d，e，f}，R={，，,} ⑷ D=(D，R)，其中D={1, 2, 3, 4, 5, 6}，R={(1, 2)，(1, 4)，(2, 3)，(2, 4)，(3, 4)，(3, 5)，(3, 6)，(4, 6)}

【解答】⑴ 属于集合，其逻辑结构图如图1-4(a)所示；⑵ 属于线性结构，其逻辑结构图如图1-4(b)所示；⑶ 属于树结构，其逻辑结构图如图1-4(c)所示；⑷ 属于图结构，其逻辑结构图如图1-4(d)所示。

7.求下列算法的时间复杂度。count=0;x=1;while(x { x*=2;count++;} return count;【解答】Ｏ(log2n)

第 2 章线性表

课后习题讲解 1.填空

⑴ 在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。

【解答】表长的一半，表长，该元素在表中的位置

⑵ 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。【解答】108 【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108 ⑶ 设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。

【解答】p->next=(p->next)->next ⑷ 单链表中设置头结点的作用是（）。【解答】为了运算方便

【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。

⑸ 非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。【解答】p->next=head 【分析】如图2-8所示。

⑹ 在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。

【解答】s->next =rear->next;rear->next =s;rear =s;q=rear->next->next;rear->next->next=q->next;delete q;【分析】操作示意图如图2-9所示：

⑺ 一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。【解答】Ο(1)，Ο(n)

【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。⑻ 可由一个尾指针唯一确定的链表有（）、（）、（）。【解答】循环链表，循环双链表，双链表 2.选择题

⑴ 线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。

A 随机存取 B 顺序存取 C 索引存取 D 散列存取【解答】A，B 【分析】参见2.2.1。

⑵ 线性表采用链接存储时，其地址（）。

B 从表中任一结点出发都能扫描到整个链表；

A 可随机访问任一元素 B 插入、删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与线性表长度成正比【解答】A

⑸ 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。A 顺序表 B 单链表 C 双链表 D 单循环链表【解答】A 【分析】线性表中最常用的操作是取第i 个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。

⑹ 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（）存储方法最节省时间。

A 单链表 B 带头指针的单循环链表 C 双链表 D 带尾指针的单循环链表【解答】D 【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以，答案是D。⑺ 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方法最节省运算时间。

A 单链表 B 循环双链表 C单循环链表

⑻ 在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。A O(1)B O(n)C O(n2)D O(nlog2n)【解答】B 【分析】首先应顺序查找新结点在单链表中的位置。

⑼ 对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（）。A O(1)B O(n)C O(n2)D O(nlog2n)【解答】C 【分析】该算法需要将n个元素依次插入到有序单链表中，而插入每个元素需O(n)。⑽ 使用双链表存储线性表，其优点是可以（）。A 提高查找速度 B 更方便数据的插入和删除 C 节约存储空间 D 很快回收存储空间【解答】B 【分析】在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节约存储空间，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，所以，其插入和删除操作更加方便。

⑾ 在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（）操作。

3.判断题

⑴ 线性表的逻辑顺序和存储顺序总是一致的。

【解答】错。每个元素最多只有一个直接前驱和一个直接后继，第一个元素没有前驱，最后一个元素没有后继。

⑸ 在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随机存取结构。【解答】错。要找到该结点的地址，必须从头指针开始查找，所以单链表是顺序存取结构。4．请说明顺序表和单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些。

【解答】顺序表的优点：① 无需为表示表中元素之间的逻辑关系而增加额外的存储空间；② 可以快速地存取表中任一位置的元素（即随机存取）。顺序表的缺点：① 插入和删除操作需移动大量元素；② 表的容量难以确定；③ 造成存储空间的―碎片‖。

⑵ 应选用链接存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。

⑶ 应选用链接存储结构。因为一个城市的设计和规划涉及活动很多，需要经常修改、扩充和删除各种信息，才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。5．算法设计 ⑴ 设计一个时间复杂度为Ｏ(n)的算法，实现将数组A[n]中所有元素循环右移k个位置。【解答】算法思想请参见主教材第一章思想火花。下面给出具体算法。

分析算法，第一次调用Reverse函数的时间复杂度为O(k)，第二次调用Reverse函数的时间复杂度为O(n-k)，第三次调用Reverse函数的时间复杂度为O(n)，所以，总的时间复杂度为O(n)。

⑵ 已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为Ｏ(n)。

【解答】从数组的两端向中间比较，设置两个变量i和j，初始时i=0，j=n-1，若A[i]为偶数并且A[j]为奇数，则将A[i]与A[j]交换。具体算法如下：

分析算法，两层循环将数组扫描一遍，所以，时间复杂度为Ｏ(n)。

⑶ 试编写在无头结点的单链表上实现线性表的插入操作的算法，并和带头结点的单链表上的插入操作的实现进行比较。【解答】参见2.2.3。

⑷ 试分别以顺序表和单链表作存储结构，各写一实现线性表就地逆置的算法。

【解答】顺序表的逆置，即是将对称元素交换，设顺序表的长度为length，则将表中第i个元素与第length-i-1个元素相交换。具体算法如下：

单链表的逆置请参见2.2.4算法2-4和算法2-6。

⑸ 假设在长度大于1的循环链表中，即无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点s的前趋结点。

【解答】利用单循环链表的特点，通过指针s可找到其前驱结点r以及r的前驱结点p，然后将结点r删除，如图2-11所示，具体算法如下：

⑹ 已知一单链表中的数据元素含有三类字符：字母、数字和其他字符。试编写算法，构造三个循环链表，使每个循环链表中只含同一类字符。

【解答】在单链表A中依次取元素，若取出的元素是字母，把它插入到字母链表B 中，若取出的元素是数字，则把它插入到数字链表D中，直到链表的尾部，这样表B，D，A中分别存放字母、数字和其他字符。具体算法如下：

⑺ 设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点。

【解答】从头到尾扫描单链表，若当前结点的元素值与后继结点的元素值不相等，则指针后移；否则删除该后继结点。具体算法如下：

⑻ 判断带头结点的双循环链表是否对称。

学习自测及答案

1.已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（）。A 108 B 180 C 176 D 112 【解答】D 2．在长度为n的线性表中查找值为x的数据元素的时间复杂度为：（）。

A O(0)B O(1)C O(n)D O(n2)【解答】C 3．在一个长度为n的顺序表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动（）个元素，删除第i（1≤i≤n）个元素时，需向前移动（）个元素。【解答】n-i+1，n-i

4．在单链表中，除了头结点以外，任一结点的存储位置由（）指示。【解答】其前趋结点的指针域

5．当线性表采用顺序存储结构时，其主要特点是（）。【解答】逻辑结构中相邻的结点在存储结构中仍相邻 6．在双链表中，每个结点设置了两个指针域，其中一个指向（）结点，另一个指向（）结点。【解答】前驱，后继

7．设A是一个线性表（a1, a2, …, an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai与ai+1之间（1≤i≤n）的概率为插入一个元素所要移动的元素个数又是多少？【解答】

，则平均每。

8．线性表存放在整型数组A[arrsize]的前elenum 个单元中，且递增有序。编写算法，将元素x插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。

【解答】本题是在一个递增有序表中插入元素x，基本思路是从有序表的尾部开始依次取元素与x比较，若大于x，此元素后移一位，再取它前面一个元素重复上述步骤；否则，找到插入位置，将x插入。具体算法如下：

9.已知单链表中各结点的元素值为整型且递增有序，设计算法删除链表中所有大于mink且小于maxk的所有元素，并释放被删结点的存储空间。

【解答】因为是在有序单链表上的操作，所以，要充分利用其有序性。在单链表中查找第一个大于mink的结点和第一个小于maxk的结点，再将二者间的所有结点删除。

10．设单循环链表L1，对其遍历的结果是：x1, x2, x3,…, xn-1, xn。请将该循环链表拆成两个单循环链表L1和L2，使得L1中含有原L1表中序号为奇数的结点且遍历结果为：x1, x3,… ；L2中含有原L1表中序号为偶数的结点且遍历结果为：… , x4, x2。【解答】算法如下：

第 3 章特殊线性表——栈、队列和串

课后习题讲解

1.填空

⑴ 设有一个空栈，栈顶指针为1000H，现有输入序列为1、2、3、4、5，经过push，push，pop，push，pop，push，push后，输出序列是（），栈顶指针为（）。【解答】23，1003H ⑵ 栈通常采用的两种存储结构是（）；其判定栈空的条件分别是（），判定栈满的条件分别是（）。【解答】顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针top=-1和top=NULL，栈顶指针top等于数组的长度和内存无可用空间

⑶（）可作为实现递归函数调用的一种数据结构。【解答】栈

⑸ 栈和队列是两种特殊的线性表，栈的操作特性是（），队列的操作特性是（），栈和队列的主要区别在于（）。

【解答】后进先出，先进先出，对插入和删除操作限定的位置不同 ⑹ 循环队列的引入是为了克服（）。【解答】假溢出

⑴ 若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（）。A 不确定 B n-i C n-i-1 D n-i+1 【解答】D 【分析】此时，输出序列一定是输入序列的逆序。

B C D 2 【解答】C 【分析】由于队列具有先进先出性，所以，此题中队列形同虚设，即出栈的顺序也是e2、e4、e3、e6、e5、e1。

⑸ 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（）结构。

A 栈 B队列 C 数组 D线性表【解答】B 【分析】先进入打印缓冲区的文件先被打印，因此具有先进先出性。⑹ 一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（）。A 4321 B 1234 C 1432 D 3241 【解答】B 【分析】队列的入队顺序和出队顺序总是一致的。⑺ 栈和队列的主要区别在于（）。

⑼ 设有两个串p和q，求q在p中首次出现的位置的运算称作（）。A 连接 B 模式匹配 C 求子串 D 求串长【解答】B 3.判断题

⑴ 有n个元素依次进栈，则出栈序列有(n-1)/2种。

【解答】错。应该有种。

⑵ 栈可以作为实现过程调用的一种数据结构。

【解答】对。只要操作满足后进先出性，都可以采用栈作为辅助数据结构。⑶ 在栈满的情况下不能做进栈操作，否则将产生―上溢‖。【解答】对。

⑷ 在循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，则队满的条件是front=rear。

【解答】错。这是队空的判定条件，在循环队列中要将队空和队满的判定条件区别开。⑸ 空串与空格串是相同的。

【解答】错。空串的长度为零，而空格串的长度不为0，其长度是串中空格的个数。

【解答】假设有一个顺序队列，如图3-6所示，队尾指针rear=4，队头指针front=1，如果再有元素入队，就会产生―上溢‖，此时的―上溢‖又称为―假溢出‖，因为队列并不是真的溢出了，存储队列的数组中还有2个存储单元空闲，其下标分别为0和1。

8．空串和空格串有何区别？串中的空格符有何意义？空串在串处理中有何作用？

【解答】不含任何字符的串称为空串，其长度为零。仅含空格的串称为空格串，它的长度为串中空格符的个数。串中的空格符可用来分隔一般的字符，便于人们识别和阅读，但计算串长时应包括这些空格符。空串在串处理中可作为任意串的子串。9.算法设计

⑴ 假设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针。试设计相应的入队和出队的算法。

出队算法如下：

⑵ 设顺序栈S中有2n个元素，从栈顶到栈底的元素依次为a2n，a2n-1，…，a1，要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a2n，a2n-2，…，a2，a2n-1，a2n-3，…，a1，请设计算法实现该操作，要求空间复杂度和时间复杂度均为O(n)。【解答】操作步骤为： ① 将所有元素出栈并入队；

② 依次将队列元素出队，如果是偶数结点，则再入队，如果是奇数结点，则入栈； ③ 将奇数结点出栈并入队； ④ 将偶数结点出队并入栈； ⑤ 将所有元素出栈并入队； ⑥ 将所有元素出队并入栈即为所求。

⑶ 用顺序存储结构存储串S，编写算法删除S中第 i个字符开始的连续j个字符。

【解答】先判断串S中要删除的内容是否存在，若存在，则将第i+j-1之后的字符前移j个位置。算法如下：

⑷ 对于采用顺序存储结构的串S，编写一个函数删除其值等于ch的所有字符。

【解答】从后向前删除值为ch的所有元素，这样所有移动的元素中没有值为ch的元素，能减少移动元素的次数，提高算法的效率。算法如下：

⑸ 对串的模式匹配KMP算法设计求模式滑动位置的next函数。【解答】参见3.2.5 学习自测及答案

1．在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，当出栈时，top的变化为（）。A 不变 B top=0;C top=top-1;D top=top+1;【解答】C 2．一个栈的入栈序列是a, b, c, d, e，则栈的不可能的出栈序列是（）。A edcba B cdeba C debca D abcde 【解答】C 3．从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行（）。A x=top;top=top->next;B x=top->data;C top=top->next;x=top->data;D x=top->data;top=top->next;【解答】D 4．设元素1, 2, 3, P, A依次经过一个栈，进栈次序为123PA，在栈的输出序列中，有哪些序列可作为C++程序设计语言的变量名。

【解答】PA321, P3A21, P32A1, P321A, AP321 5.设S=“I_ am_ a_ teacther”，其长度为（）。【解答】15 第 4 章广义线性表——多维数组和广义表

课后习题讲解

1.填空

⑴ 数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。【解答】存取，修改，顺序存储

⑶ 设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。【解答】d+41 【分析】元素A[8][5]的前面共存储了(1+2+…+8)+5=41个元素。⑷ 稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。【解答】三元组顺序表，十字链表

⑵ 将数组称为随机存取结构是因为（）

A 数组是一种线性结构 B 数组是一种定长的线性结构

C 除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等 D 数组的基本操作有存取、修改、检索和排序等，没有插入与删除操【解答】C 【分析】数组属于广义线性表，数组被创建以后，其维数和每维中的元素个数是确定的，所以，数组通常没有插入和删除操作。

⑷ 对特殊矩阵采用压缩存储的目的主要是为了（）A 表达变得简单 B 对矩阵元素的存取变得简单 C 去掉矩阵中的多余元素 D 减少不必要的存储空间【解答】D 【分析】在特殊矩阵中，有很多值相同的元素并且他们的分布有规律，没有必要为值相同的元素重复存储。⑸ 下面（）不属于特殊矩阵。

A 对角矩阵 B 三角矩阵 C 稀疏矩阵 D 对称矩阵

【解答】C ⑹ 若广义表A满足Head(A)=Tail(A)，则A为（）A()B(())C((),())D((),(),())【解答】B ⑺ 下面的说法中，不正确的是（）

A 广义表是一种多层次的结构 B 广义表是一种非线性结构 C 广义表是一种共享结构 D 广义表是一种递归【解答】B 【分析】从各层元素各自具有的线性关系讲，广义表属于线性结构。⑻ 下面的说法中，不正确的是（）

A 对称矩阵只须存放包括主对角线元素在内的下（或上）三角的元素即可。B 对角矩阵只须存放非零元素即可。

C 稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储。

【解答】对。因为三元组表除了存储非零元素值外，还需要存储其行号和列号。⑶ 稀疏矩阵压缩存储后，必会失去随机存取功能。

【解答】对。因为压缩存储后，非零元素的存储位置和行号、列号之间失去了确定的关系。

⑷ 线性表可以看成是广义表的特例，如果广义表中的每个元素都是单元素，则广义表便成为线性表。【解答】对。

⑸ 若一个广义表的表头为空表，则此广义表亦为空表。

【解答】错。如广义表L=(()，(a，b))的表头为空表，但L不是空表。

4．一个稀疏矩阵如图4-4所示，写出对应的三元组顺序表和十字链表存储表示。

【解答】对应的三元组顺序表如图4-5所示，十字链表如图4-6所示。

5．已知A为稀疏矩阵，试从空间和时间角度比较采用二维数组和三元组顺序表两种不同的存储结构完成求运算的优缺点。

【解答】设稀疏矩阵为m行n列，如果采用二维数组存储，其空间复杂度为Ｏ(m×n)；因为要将所有的矩阵元素累加起来，所以，需要用一个两层的嵌套循环，其时间复杂度亦为Ｏ(m×n)。如果采用三元组顺序表进行压缩存储，假设矩阵中有t个非零元素，其空间复杂度为Ｏ(t)，将所有的矩阵元素累加起来只需将三元组顺序表扫描一遍，其时间复杂度亦为Ｏ(t)。当t << m×n时，采用三元组顺序表存储可获得较好的时、空性能。

6．设某单位职工工资表ST由―工资‖、―扣除‖和―实发金额‖三项组成，其中工资项包括―基本工资‖、―津贴‖和―奖金‖，扣除项包括―水‖、―电‖和―煤气‖。

⑴ 请用广义表形式表示所描述的工资表ST，并用表头和表尾求表中的―奖金‖项； ⑵ 画出该工资表ST的存储结构。

【解答】⑴ ST=((基本工资，津贴，奖金)，(水，电，煤气)，实发金额)Head(Tail(Tail(Head(ST))))=奖金

⑵ 工资表ST的头尾表示法如图4-7所示。

7．若在矩阵A中存在一个元素ai,j（0≤i≤n-1，0≤j≤m-1），该元素是第i行元素中最小值且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵A，试设计一个求该矩阵所有马鞍点的算法，并分析最坏情况下的时间复杂度。

【解答】在矩阵中逐行寻找该行中的最小值，然后对其所在的列寻找最大值，如果该列上的最大值与该行上的最小值相等，则说明该元素是鞍点，将它所在行号和列号输出。

具体算法如下：

分析算法，外层for循环共执行n次，内层第一个for循环执行m次，第二个for循环最坏情况下执行n次，所以，最坏情况下的时间复杂度为Ｏ(mn+n2)。

学习自测及答案

1．二维数组M中每个元素的长度是3个字节，行下标从0到7，列下标从0到9，从首地址d开始存储。若按行优先方式存储，元素M[7][5]的起始地址为（），若按列优先方式存储，元素M[7][5]的起始地址为（）。【解答】d+22，d+141 2．一个n×n的对称矩阵，按行优先或列优先进行压缩存储，则其存储容量为（）。【解答】n(n+1)/2 3．设n行n列的下三角矩阵A（行列下标均从1开始）已压缩到一维数组S[1]~S[n(n+1)/2]中，若按行优先存储，则A[i][j]在数组S中的存储位置是（）。【解答】i×(i-1)/2+j 4．已知广义表LS=(a,(b, c),(d, e, a))，运用Head函数和Tail函数取出LS中原子d的运算是（）。【解答】Head(Head(Tail(Tail(LS))))5．广义表(a, b,(c,(d)))的表尾是（）。A(d)B(c,(d))C b,(c,(d))D(b,(c,(d)))【解答】D 6．设有三对角矩阵An×n（行、列下标均从0开始），将其三条对角线上的元素逐行存于数组B[3n-2]中，使得B[k]=aij求：

⑴ 用i, j表示k的下标变换公式； ⑵ 用k表示i, j的下标变换公式。

7．已知两个n×n的对称矩阵按压缩存储方法存储在已维数组A和B中，编写算法计算对称矩阵的乘积。【解答】对称矩阵采用压缩存储，乘积矩阵也采用压缩存储。注意矩阵元素的表示方法。

第 5 章树和二叉树

课后习题讲解

1.填空题

⑵ 树中某结点的子树的个数称为该结点的（），子树的根结点称为该结点的（），该结点称为其子树根结点的（）。

【解答】度，孩子，双亲

⑷ 设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值是（）。【解答】2h-1，2h-1 【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。

⑸ 深度为k的二叉树中，所含叶子的个数最多为（）。【解答】2k-1 【分析】在满二叉树中叶子结点的个数达到最多。

⑹ 具有100个结点的完全二叉树的叶子结点数为（）。【解答】50 【分析】100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为50，也就是说，从编号51开始均为叶子。

⑼ 在具有n个结点的二叉链表中，共有（）个指针域，其中（）个指针域用于指向其左右孩子，剩下的（）个指针域则是空的。【解答】2n，n-1，n+1

⑽ 在有n个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（）。【解答】n，n-1 【分析】n-1个分支结点是经过n-1次合并后得到的。

2.选择题

⑴ 如果结点A有3个兄弟，B是A的双亲，则结点B的度是（）。A 1 B 2 C 3 D 4 【解答】D

⑵ 设二叉树有n个结点，则其深度为（）。A n-1 B n C +1 D 不能确定【解答】D 【分析】此题并没有指明是完全二叉树，则其深度最多是n，最少是

+1。

⑶ 二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A 空或只有一个结点 B 高度等于其结点数 C 任一结点无左孩子 D 任一结点无右孩子【解答】B 【分析】此题注意是序列正好相反，则左斜树和右斜树均满足条件。

⑷ 线索二叉树中某结点R没有左孩子的充要条件是（）。A R.lchild=NULL B R.ltag=0 C R.ltag=1 D R.rchild=NULL 【解答】C 【分析】线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左标志是否为1。

⑸ 深度为k的完全二叉树至少有（）个结点，至多有（）个结点，具有n个结点的完全二叉树按层序从1开始编号，则编号最小的叶子的序号是（）。A 2k-2+1 B 2k-1 C 2k-1 D 2k–1-1 E 2k+1 F 2k+1-1 G 2k-1+1 H 2k 【解答】B，C，A 【分析】深度为k的完全二叉树最少结点数的情况应是第k层上只有1个结点，最多的情况是满二叉树，编号最小的叶子应该是在结点数最少的情况下，叶子结点的编号。

⑹ 一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（）成立。A n=h+m B h+m=2n C m=h-1 D n=2m-1 【解答】D 【分析】满二叉树中没有度为1的结点，所以有m个叶子结点，则度为2的结点个数为m-1。

⑺ 任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（）。A 肯定不发生改变 B 肯定发生改变 C 不能确定 D 有时发生变化【解答】A 【分析】三种遍历次序均是先左子树后右子树。

⑻ 如果T' 是由有序树T转换而来的二叉树，那么T中结点的前序序列就是T' 中结点的（）序列，T中结点的后序序列就是 T' 中结点的（）序列。A 前序 B 中序 C 后序 D 层序【解答】A，B

⑼ 设森林中有4棵树，树中结点的个数依次为n1、n2、n3、n4，则把森林转换成二叉树后，其根结点的右子树上有（）个结点，根结点的左子树上有（）个结点。A n1-1 B n1 C n1+n2+n3 D n2+n3+n4 【解答】D，A 【分析】由森林转换的二叉树中，根结点即为第一棵树的根结点，根结点的左子树是由第一棵树中除了根结点以外其余结点组成的，根结点的右子树是由森林中除第一棵树外其他树转换来的。

⑽ 讨论树、森林和二叉树的关系，目的是为了（）。A 借助二叉树上的运算方法去实现对树的一些运算

B 将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题 C 将树、森林转换成二叉树

D 体现一种技巧，没有什么实际意义【解答】B 3.判断题

⑴ 在线索二叉树中，任一结点均有指向其前趋和后继的线索。

【解答】错。某结点是否有前驱或后继的线索，取决于该结点的标志域是否为1。

⑵ 在二叉树的前序遍历序列中，任意一个结点均处在其子女的前面。【解答】对。由前序遍历的操作定义可知。

⑶ 二叉树是度为2的树。

【解答】错。二叉树和树是两种不同的树结构，例如，左斜树是一棵二叉树，但它的度为1。

⑷ 由树转换成二叉树，其根结点的右子树总是空的。【解答】对。因为根结点无兄弟结点。

⑸ 用一维数组存储二叉树时，总是以前序遍历存储结点。

【解答】错。二叉树的顺序存储结构是按层序存储的，一般适合存储完全二叉树。

4．证明：对任一满二叉树，其分枝数B＝2(n0-1)。（其中，n0为终端结点数）【解答】因为在满二叉树中没有度为1的结点，所以有： n=n0+n2

设B为树中分枝数，则 n=B+1 所以 B=n0 +n2-1 再由二叉树性质： n0=n2+1 代入上式有：

B=n0+n0-1-1=2(n0-1)

5．证明：已知一棵二叉树的前序序列和中序序列，则可唯一确定该二叉树。【解答】证明采用归纳法。

设二叉树的前序遍历序列为a1a2a3… an，中序遍历序列为b1b2b3… bn。

当n=1时，前序遍历序列为a1，中序遍历序列为b1，二叉树只有一个根结点，所以，a1= b1，可以唯一确定该二叉树；

假设当n<=k时，前序遍历序列a1a2a3… ak和中序遍历序列b1b2b3… bk可唯一确定该二叉树，下面证明当n=k+1时，前序遍历序列a1a2a3… akak+1和中序遍历序列b1b2b3… bk bk+1可唯一确定一棵二叉树。

在前序遍历序列中第一个访问的一定是根结点，即二叉树的根结点是a1，在中序遍历序列中查找值为a1的结点，假设为bi，则a1=bi且b1b2… bi-1是对根结点a1的左子树进行中序遍历的结果，前序遍历序列a2a3… ai是对根结点a1的左子树进行前序遍历的结果，由归纳假设，前序遍历序列a2a3… ai和中序遍历序列b1b2… bi-1唯一确定了根结点的左子树，同样可证前序遍历序列ai+1ai+2… ak+1和中序遍历序列bi+1bi+2… bk+1唯一确定了根结点的右子树。

6．已知一棵度为m的树中有：n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，问该树中共有多少个叶子结点？

【解答】设该树的总结点数为n，则 n=n0+n1+n2+……+nm 又：

n=分枝数+1=0×n0+1×n1+2×n2+……+m×nm+1 由上述两式可得：

n0= n2+2n3+……+(m-1)nm+1 7．已知二叉树的中序和后序序列分别为CBEDAFIGH和CEDBIFHGA，试构造该二叉树。【解答】二叉树的构造过程如图5-12 所示。

8．对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。

【解答】构造的哈夫曼树如图5-13所示。

树的带权路径长度为：

WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2 =120 9．已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用[0，1]进行前缀编码，问该字符串的编码至少有多少位。

【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图5-14所示。其带权路径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，该字符串的编码长度至少为98位。

10．算法设计 ⑴ 设计算法求二叉树的结点个数。

【解答】本算法不是要打印每个结点的值，而是求出结点的个数。所以可将遍历算法中的―访问‖操作改为―计数操作‖，将结点的数目累加到一个全局变量中，每个结点累加一次即完成了结点个数的求解。具体算法如下：

⑵ 设计算法按前序次序打印二叉树中的叶子结点。

⑶ 设计算法求二叉树的深度。

⑷ 编写算法，要求输出二叉树后序遍历序列的逆序。

⑸ 以二叉链表为存储结构，编写算法求二叉树中结点x的双亲。

【解答】对二叉链表进行遍历，在遍历的过程中查找结点x并记载其双亲。具体算法如下：

⑹ 以二叉链表为存储结构，在二叉树中删除以值x为根结点的子树。

【解答】对二叉链表进行遍历，在遍历的过程中查找结点x并记载其双亲，然后将结点x的双亲结点中指向结点x的指针置空。具体算法如下：

⑺ 一棵具有n个结点的二叉树采用顺序存储结构，编写算法对该二叉树进行前序遍历。【解答】按照题目要求，设置一个工作栈以完成对该树的非递归算法，思路如下：

① 每访问一个结点，将此结点压栈，查看此结点是否有左子树，若有，访问左子树，重复执行该过程直到左子树为空。

② 从栈弹出一个结点，如果此结点有右子树，访问右子树执行步骤①，否则重复执行步骤②。具体算法如下：

⑻ 编写算法交换二叉树中所有结点的左右子树。

【解答】对二叉树进行后序遍历，在遍历过程中访问某结点时交换该结点的左右子树。具体算法如下：

⑼ 以孩子兄弟表示法做存储结构，求树中结点x的第i个孩子。

树的孩子兄弟表示法中的结点结构定义如下： template struct TNode { T data;TNode *firstchild, *rightsib;};具体算法如下：

学习自测及答案

1．前序遍历和中序遍历结果相同的二叉树是（）。A 根结点无左孩子的二叉树 B 根结点无右孩子的二叉树

C 所有结点只有左子树的二叉树 D 所有结点只有右子树的二叉树【解答】D 1．前序遍历和中序遍历结果相同的二叉树是（）。A 根结点无左孩子的二叉树 B 根结点无右孩子的二叉树 C 所有结点只有左子树的二叉树 D 所有结点只有右子树的二叉树【解答】D

2．由权值为{3, 8, 6, 2, 5}的叶子结点生成一棵哈夫曼树，其带权路径长度为（）。A 24 B 48 C 53 D 72 【解答】C

3．用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1] ~ A[n]中，结点A[i]若有左子树，则左子树的根结点是（）。

A A[2i-1] B A[2i+1] C A[i/2] D A[2i] 【解答】D

4．对任何一棵二叉树T，如果其终端结点的个数为n0，度为2的结点个数为n2，则（）。A n0=n2-1 B n0=n2 C n0=n2+1 D 没有规律【解答】C

5．一棵满二叉树中共有n个结点，其中有m个叶子结点，深度为h，则（）。A n=h+m B h+m=2n C m=h-1 D n=2h-1 【解答】D

6．对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（）。

A h B h+1 C h或h+1 D 任意【解答】C

7．假定一棵度为3的树中结点数为50，则其最小高度应为。A 3 B 4 C 5 D 6 【解答】C

8．在线索二叉树中，一个结点是叶子结点的充要条件为（）。A 左线索标志为0，右线索标志为1 B 左线索标志为1，右线索标志为0 C 左、右线索标志均为0 D 左、右线索标志均为1 【解答】C

9．对于一棵具有n个结点的树，其所有结点的度之和为（）。【解答】n-1

10．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是（）。【解答】

11．现有按前序遍历二叉树的结果ABC，问有哪几种不同的二叉树可以得到这一结果？【解答】共有5种二叉树可以得到这一结果，如图5-15所示。

12．试找出分别满足下列条件的所有二叉树： ⑴ 前序序列和中序序列相同。⑵ 中序序列和后序序列相同。⑶ 前序序列和后序序列相同。

【解答】 ⑴ 空二叉树、只有一个根结点的二叉树和右斜树。⑵ 空二叉树、只有一个根结点的二叉树和左斜树。⑶ 空二叉树、只有一个根结点的二叉树

13．将下面图5-16所示的树转换为二叉树，图5-17所示的二叉树转换为树或森林。

【解答】图5-16所示树转换的二叉树如图5-18所示，图5-17所示二叉树转换的森林如图5-19所示。

14．以孩子兄弟表示法作为存储结构，编写算法求树的深度。

【解答】采用递归算法实现。若树为空树，则其深度为0，否则其深度等于第一棵子树的深度+1和兄弟子树的深度中的较大者。具体算法如下：

15．设计算法，判断一棵二叉树是否为完全二叉树。

【解答】根据完全二叉树的定义可知，对完全二叉树按照从上到下、从左到右的次序（即层序）遍历应该满足： ⑴ 若某结点没有左孩子，则其一定没有右孩子； ⑵ 若某结点无右孩子，则其所有后继结点一定无孩子。

若有一结点不满足其中任意一条，则该二叉树就一定不是完全二叉树。因此可采用按层次遍历二叉树的方法依次对每个结点进行判断是否满足上述两个条件。为此，需设两个标志变量BJ和CM，其中BJ表示已扫描过的结点是否均有左右孩子，CM存放局部判断结果及最后的结果。具体算法如下：

第 6 章图

课后习题讲解

1.填空题

⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。

⑵ 任何连通图的连通分量只有一个，即是（）。【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。【解答】邻接矩阵，邻接表

【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。

⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。【解答】求第j列的所有元素之和

⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。【解答】出度

⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。【解答】前序，栈，层序，队列

⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal算法求最小生成树的时间复杂度为（）。【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。

⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。【解答】回路

⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。2.选择题

⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。

⑵ n个顶点的强连通图至少有（）条边，其形状是（）。A n B n+1 C n-1 D n×(n-1)E 无回路

F 有回路

G 环状

H 树状【解答】A，G ⑶ 含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（）。A 1 B n/2 C n-1 D n 【解答】C 【分析】若超过n-1，则路径中必存在重复的顶点。

⑷ 对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（）。A n B(n-1)2 C n-1 D n2 【解答】D ⑸ 图的生成树（），n个顶点的生成树有（）条边。A 唯一

B 不唯一

C 唯一性不能确定 D n E n +1 F n-1 【解答】C，F ⑹ 设无向图G=(V, E)和G' =(V', E')，如果G' 是G的生成树，则下面的说法中错误的是（）。A G' 为 G的子图 B G' 为 G的连通分量

C G' 为G的极小连通子图且V = V' D G' 是G的一个无环子图【解答】B 【分析】连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中顶点的所有边都加上，所以，连通分量中可能存在回路。

⑺ G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。A 6 B 7 C 8 D 9 【解答】D 【分析】n个顶点的无向图中，边数e≤n(n-1)/2，将e=28代入，有n≥8，现已知无向图非连通，则n=9。⑻ 最小生成树指的是（）。A 由连通网所得到的边数最少的生成树 B 由连通网所得到的顶点数相对较少的生成树 C 连通网中所有生成树中权值之和为最小的生成树 D 连通网的极小连通子图

⑼ 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（）。A 求关键路径的方法

B 求最短路径的方法 C 广度优先遍历算法

D 深度优先遍历算法【解答】D 【分析】当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序（退出DFSTraverse算法）即为逆向的拓扑序列。

⑽ 下面关于工程计划的AOE网的叙述中，不正确的是（）?br /> A 关键活动不按期完成就会影响整个工程的完成时间

B 任何一个关键活动提前完成，那么整个工程将会提前完成 C 所有的关键活动都提前完成，那么整个工程将会提前完成 D 某些关键活动若提前完成，那么整个工程将会提前完【解答】B 【分析】AOE网中的关键路径可能不止一条，如果某一个关键活动提前完成，还不能提前整个工程，而必须同时提高在几条关键路径上的关键活动。3.判断题

⑴ 一个有向图的邻接表和逆邻接表中的结点个数一定相等。

【解答】对。邻接表和逆邻接表的区别仅在于出边和入边，边表中的结点个数都等于有向图中边的个数。⑵ 用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。【解答】对。邻接矩阵的空间复杂度为Ｏ(n2)，与边的个数无关。⑶ 图G的生成树是该图的一个极小连通子图【解答】错。必须包含全部顶点。

⑷ 无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的

【解答】错。有向图的邻接矩阵不一定对称，例如有向完全图的邻接矩阵就是对称的。⑸ 对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。【解答】错。只有连通图从某顶点出发进行一次遍历，可访问图的所有顶点。⑹ 在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。【解答】错。只能说明从顶点a到顶点b有一条路径。

⑺ 若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑序列必定存在。【解答】对。参见第11题的证明。

⑻ 在AOE网中一定只有一条关键路径?br />【解答】错。AOE网中可能有不止一条关键路径，他们的路径长度相同。

4．n个顶点的无向图，采用邻接表存储，回答下列问题?br />⑴ 图中有多少条边？ ⑵ 任意两个顶点i和j是否有边相连？ ⑶ 任意一个顶点的度是多少?br />【解答】 ⑴ 边表中的结点个数之和除以2。⑵ 第i个边表中是否含有结点j。⑶ 该顶点所对应的边表中所含结点个数。

5．n个顶点的无向图，采用邻接矩阵存储，回答下列问题： ⑴ 图中有多少条边？

⑵ 任意两个顶点i和j是否有边相连？ ⑶ 任意一个顶点的度是多少？【解答】

⑴ 邻接矩阵中非零元素个数的总和除以2。

⑵ 当邻接矩阵A中A[i][j]=1（或A[j][i]=1）时，表示两顶点之间有边相连。⑶ 计算邻接矩阵上该顶点对应的行上非零元素的个数。6．证明：生成树中最长路径的起点和终点的度均为１。【解答】用反证法证明。

设v1, v2, …, vk是生成树的一条最长路径，其中，v1为起点，vk为终点。若vk的度为2，取vk的另一个邻接点v，由于生成树中无回路，所以，v在最长路径上，显然v1, v2, …, vk , v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。同理可证起点v1的度不能大于1，只能为1。

7．已知一个连通图如图6-6所示，试给出图的邻接矩阵和邻接表存储示意图，若从顶点v1出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列。

【解答】邻接矩阵表示如下：

深度优先遍历序列为：v1 v2 v3 v5 v4 v6 广度优先遍历序列为：v1 v2 v4 v6 v3 v5 邻接表表示如下：

8．图6-7所示是一个无向带权图，请分别按Prim算法和Kruskal算法求最小生成树。

【解答】按Prim算法求最小生成树的过程如下：

按Kruskal算法求最小生成树的过程如下：

9．对于图6-8所示的带权有向图，求从源点v1到其他各顶点的最短路径。

【解答】从源点v1到其他各顶点的最短路径如下表所示。源点终点最短路径最短路径长度 v1 v7 v1 v7 7 v1 v5 v1 v5 11 v1 v4 v1 v7 v4 13 v1 v6 v1 v7 v4 v6 16 v1 v2 v1 v7 v2 22 v1 v3 v1 v7 v4 v6 v3 25 10．如图6-9所示的有向网图，利用Dijkstra算法求从顶点v1到其他各顶点的最短路径。

【解答】从源点v1到其他各顶点的最短路径如下表所示。源点终点最短路径最短路径长度 v1 v3 v1 v3 15 v1 v5 v1 v5 15 v1 v2 v1 v3 v2 25 v1 v6 v1 v3 v2 v6 40 v1 v4 v1 v3 v2 v4 45 11．证明：只要适当地排列顶点的次序，就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0。【解答】任意n个结点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v0v1v2…vn-1，我们来证明此时的邻接矩阵A为上三角矩阵。证明采用反证法。

假设此时的邻接矩阵不是上三角矩阵，那么，存在下标i和j（i>j），使得A[i][j]不等于零，即图中存在从vi到vj的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，vi的位置一定在vj之前，而在上述拓扑序列v0v1v2…vn-1中，由于i>j，即vi的位置在vj之后，导致矛盾。因此命题正确。12.算法设计

⑴ 设计算法，将一个无向图的邻接矩阵转换为邻接表。

【解答】先设置一个空的邻接表，然后在邻接矩阵上查找值不为零的元素，找到后在邻接表的对应单链表中插入相应的边表结点。邻接矩阵存储结构定义如下： const int MaxSize=10;template struct AdjMatrix {

T vertex[MaxSize];//存放图中顶点的数组 int arc[MaxSize][MaxSize];//存放图中边的数组 int vertexNum, arcNum;//图的顶点数和边数 };邻接表存储结构定义如下： const int MaxSize=10;struct ArcNode //定义边表结点 { int adjvex;//邻接点域 ArcNode *next;};template

struct VertexNode //定义顶点表结点 { T vertex;ArcNode *firstedge;};struct AdjList { VertexNode adjlist[MaxSize];int vertexNum, arcNum;//图的顶点数和边数 };具体算法如下：

第三篇：数据结构课后习题答案总结

第一章

第1章作业：1.1,1.2,1.6(1)(3)1.8 1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。● 数据：指能够被计算机识别、存储和加工处理的信息载体。

● 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。

● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。

● 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

● 逻辑结构：指数据元素之间的逻辑关系。

● 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.● 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。

1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。

答：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构是线性结构。

这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。

在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。

1.6 设n为正整数，利用大“O”记号，将下列程序段的执行时间表示为n的函数。

(1)i=1;k=0;while(ij)j++;else i++;} 分析：

通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，所以该程序段的执行时间为：

T(n)=O(n)

1.8 按增长率由小至大的顺序排列下列各函数：2100,(3/2)n，(2/3)n，nn ,n0.5 , n!，2n，lgn ,nlgn, n(3/2)

答：常见的时间复杂度按数量级递增排列,依次为:常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)、立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。先将题中的函数分成如下几类：

常数阶：2 对数阶：lgn K次方阶：n、n0.5(3/2)100

指数阶(按指数由小到大排)：nlgn、(3/2)n、2n、n!、nn

注意：(2/3)^n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。

根据以上分析按增长率由小至大的顺序可排列如下：(2/3)n < 2100 < lgn < n0.5 < n(3/2)< nlgn <(3/2)n < 2n < n!< nn

第二章

第二章作业：2.2，2.6,2.9,2.13 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。

2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。2.6 下述算法的功能是什么? LinkList Demo(LinkList L){ // L 是无头结点单链表 ListNode *Q,*P;if(L&&L->next){ Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;} return L;}// Demo 答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。

2.7 设线性表的n个结点定义为(a0,a1,...an-1)，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList.解：算法如下: #define ListSize 100 // 假定表空间大小为100 typedef int DataType;//假定DataType的类型为int型 typedef struct{ DataType data[ListSize];// 向量data用于存放表结点 int length;// 当前的表长度 } Seqlist;//以上为定义表结构

void InsertList(Seqlist *L, Datatype x, int i){ //将新结点x插入L所指的顺序表的第i个结点ai的位置上，即插入的合法位置为：0<=i<=L->length int j;if(i < 0 || i > L-> length)Error(“position error”);// 非法位置，退出，if(L->length>=ListSize)Error(“overflow“);

for(j=L->length-1;j >= i;j--)L->data[ j+1]=L->data [ j ];L->data[ i ]=x;L->length++;} 2.9 设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。

答：因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，该位置也空出来了。

算法如下：

//顺序表存储结构如题2.7 void InsertIncreaseList(Seqlist *L , Datatype x){ int i;if(L->length>=ListSize)Error(“overflow”);

for(i=L-> length;i>0 && L->data[ i-1 ] > x;i--)L->data[ i ]=L->data[ i ];// 比较并移动元素 L->data[ i ] =x;L-> length++;} 2.13 设 A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。

解：根据已知条件，A和B是两个递增有序表，所以可以先取A表的表头建立空的C表。然后同时扫描A表和B表，将两表中最大的结点从对应表中摘下，并作为开始结点插入C表中。如此反复，直到A表或B表为空。最后将不为空的A表或B表中的结点依次摘下并作为开始结点插入C表中。这时，得到的C表就是由A表和B表归并成的一个按元素值递减有序的单链表C。并且辅助空间为O(1)。

算法如下：

LinkList MergeSort(LinkList A , LinkList B){// 归并两个带头结点的递增有序表为一个带头结点递减有序表 ListNode *pa , *pb , *q , *C;pa=A->next;//pa指向A表开始结点

C=A;C->next=NULL;//取A表的表头建立空的C表 pb=B->next;//pb指向B表开始结点 free(B);//回收B表的头结点空间 while(pa && pb){ if(pb->data <= pa->data){ // 当B中的元素小于等于A中当前元素时，将pa表的开始结点摘下 q=pa;pa=pa->next;} else {// 当B中的元素大于A中当前元素时，将pb表的开始结点摘下 q=pb;pb=pb->next;} q->next=C->next;C->next=q;//将摘下的结点q作为开始结点插入C表 } //若pa表非空，则处理pa表 while(pa){ q=pa;pa=pa->next;q->next=C->next;C->next=q;} //若pb表非空，则处理pb表 while(pb){ q=pb;pa=pb->next;q->next=C->next;C->next=q;} return(C);} 该算法的时间复杂度分析如下：

算法中有三个while 循环，其中第二个和第三个循环只执行一个。每个循环做的工作都是对链表中结点扫描处理。整个算法完成后，A表和B表中的每个结点都被处理了一遍。所以若A表和B表的表长分别是m和n，则该算法的时间复杂度O(m+n)

●练习2.1：写出在线性表中的查找运算算法。

即查找数据元素x在表中的位置，也就是数据元素下标值加1。

例如：若L.data[i]=x,则返回i+1;若不存在，则返回n+1 练习2.2：编写尾插法建立链表的算法。

练习2.3：若是带头指针的单链表，算法又是怎样？

若是两个链表，既知道头结点，又知道尾结点，算法又是怎样？

●练习2：按升序打印带头结点h的单链表中各节点的数据域值，并将打印完的节点从表中删除。

第三章

第三章作业：3.2, 3.3，3.4（2），3.6，3.11 3.2 循环队列的优点是什么? 如何判别它的空和满? 答：循环队列的优点是：它可以克服顺序队列的“假上溢”现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的“空”或“满”不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。

3.3设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。3.4 指出下述程序段的功能是什么?(2)SeqStack S1, S2, tmp;

DataType x;

...//假设栈tmp和S2已做过初始化

while(!StackEmpty(&S1))

{

x=Pop(&S1);

Push(&tmp,x);

}

while(!StackEmpty(&tmp))

{

x=Pop(&tmp);

Push(&S1,x);

Push(&S2, x);

}(2)程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。

3.6 利用栈的基本操作，写一个将栈S中所有结点均删去的算法void ClearStack(SeqStack *S)，并说明S为何要作为指针参数

解：算法如下

void ClearStack(SeqStack *S)

{ // 删除栈中所有结点

S->Top =-1;//其实只是将栈置空

}

因为要置空的是栈S，如果不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影响，系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作的结果返回给实参的话，就只能用指针来做参数传递了。

3.8 设计算法判断一个算术表达式的圆括号是否正确配对。(提示：对表达式进行扫描，凡遇到‘(’就进栈，遇‘)’就退掉栈顶的‘(’，表达式被扫描完毕，栈应为空。解：

根据提示，可以设计算法如下：

int PairBracket(char *SR)

{//检查表达式SR中括号是否配对

int i;

SeqStack S;//定义一个栈

InitStack(&s);

for(i=0;i

{

if(SR[i]==‘(’)Push(&S, SR[i]);//遇‘(’时进栈

if(SR[i]==‘)’)//遇‘)’

if(!StackEmpty(S))//栈不为空时，将栈顶元素出栈

Pop(&s);

else return 0;//不匹配，返回0

}

if（EmptyStack(&s)）return 1;// 匹配，返回1

else return 0;//不匹配，返回0

} 6.12 若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。

(1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。(2)已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。(3)已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同的二叉树。解：

(1)已知二叉树的前序序列为ABDGHCEFI和中序序列GDHBAECIF，则可以根据前序序列找到根结点为A，由此，通过中序序列可知它的两棵子树包分别含有GDHB和ECIF结点，又由前序序列可知B和C分别为两棵子树的根结点...以此类推可画出所有结点：

○A / ○B ○C / / ○D ○E○F / / ○G ○H ○I

(2)以同样的方法可画出该二叉树：

○A / ○B ○F ○C ○G / ○D ○E ○H

(3)这两棵不同的二叉树为：

○A ○A / ○B ○B 6.21 以二叉链表为存储结构，写一算法交换各结点的左右子树。

答：要交换各结点的左右子树，最方便的办法是用后序遍历算法，每访问一个结点时把两棵子树的指针进行交换，最后一次访问是交换根结点的子树。

void ChangeBinTree(BinTree *T)

{ //交换子树

if(*T)

{ //这里以指针为参数使得交换在实参的结点上进行后序遍历

BinTree temp;

ChangeBinTree(&(*T)->lchild);

ChangeBinTree(&(*T)->rchild);

temp=(*T)->lchild;

(*T)->lchild=(*T)->rchild;

(*T)->rchild=temp;

}

} 9.11试写出二分查找的递归算法。解：

int BinSearch(SeqList R，KeyType K，int low，int high)

{ //在有序表R[low..high]中进行二分查找，成功时返回结点的位置，失败时返回零

int mid； //置当前查找区间上、下界的初值

if(low<=high){ //当前查找区间R[low..high]非空

mid=(low+high)/2；

if(R[mid].key==K)return mid； //查找成功返回

if(R[mid].key>K)

return BinSearch(R，K,low，mid-1)//在R[low..mid-1]中查找

else

return BinSearch(R，K,mid+1，high)； //在R[mid+1..high]中查找

}

return 0； //当low>high时表示查找区间为空，查找失败

} //BinSeareh 10.7.将哨兵放在R[n]中，被排序的记录放在R[0..n-1]中，重写直接插入排序算法。解：

重写的算法如下：

void InsertSort(SeqList R)

{//对顺序表中记录R[0..n-1]按递增序进行插入排序

int i,j;

for(i=n-2;i>=0;i--)//在有序区中依次插入R[n-2]..R[0]

if(R[i].key>R[i+1].key)//若不是这样则R[i]原位不动

{

R[n]=R[i];j=i+1;//R[n]是哨兵

do{ //从左向右在有序区中查找插入位置

R[j-1]=R[j];//将关键字小于R[i].key的记录向右移

j++;

}while(R[j].key

R[j-1]=R[n];//将R[i]插入到正确位置上

}//endif

}//InsertSort.12.1 常见的文件组织方式有哪几种?各有何特点? 文件上的操作有哪几种? 如何评价文件组织的效率? 答：

常用的文件组织方式有：顺序文件、索引文件、散列文件和多关键字文件。

●顺序文件的特点是，它是按记录进入文件的先后顺序存放，其逻辑结构和物理顺序是一致的。

●索引文件的特点是，在主文件之外还另外建立了一张表，由这张表来指明逻辑记录和物理记录之间的一一对应关系。索引文件在存储器上分为两个区：索引区和数据区，前者存放索引表，后者存放主文件。●散列文件是利用散列存储方式组织的，它类似于散列表，即根据文件中关键字的特点，设计一个散列函数和处理冲突的方法，将记录散列到存储设备上，对于散列文件，磁盘上的文件记录通常是成组存放的。

●多关键字文件则包含有多个次关键索引的，不同于前述几种文件，只含有一个主关键字。

文件的操作有两种：检索和维护。

评价一个文件组织的效率，是执行文件操作(如查找、删除等)所花费的时间和文件组织所需的存储空间。

第四篇：数据结构查找习题及答案

第9章查找

一、单选题

1.对一棵二叉搜索树按（）遍历，可得到结点值从小到大的排列序列。

A.先序 B.中序

C.后序

D.层次

2.从具有n个结点的二叉搜索树中查找一个元素时，在平均情况下的时间复杂度大致为（）。

A.O(n)

B.O(1)

C.O(logn)

D.O(n2)3.从具有n个结点的二叉搜索树中查找一个元素时，在最坏情况下的时间复杂度为（）。

A.O(n)

B.O(1)

C.O(logn)

D.O(n2)4.在二叉搜索树中插入一个结点的时间复杂度为（）。

A.O(1)B.O(n)

C.O(logn)

D.O(n2)5.分别以下列序列构造二叉搜索树，与用其它三个序列所构造的结果不同的是（）。

A．（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130）D.（100，80，60，90，120，130，110）

6.在一棵AVL树中，每个结点的平衡因子的取值范围是（）。

A.-11 B.-22 C.12

D.01 7.根据一组关键字（56，42，50，64，48）依次插入结点生成一棵AVL树，当插入到值为（）的结点时需要进行旋转调整。A.42 B.50

C.64

D.48 8.深度为4的AVL树至少有（）个结点。

A．9 B.8

C.7

D.6 9.一棵深度为k的AVL树，其每个分支结点的平衡因子均为0，则该平衡二叉树共有（）个结点。A.2k-1-1 B.2k-1+1

C.2k-1

D.2k

10.在AVL树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（）型调整以使其平衡。A.LL

B.LR

C.RL

D.RR

二、判断题 1.二叉搜索树的任意一棵子树中，关键字最小的结点必无左孩子，关键字最大的结点必无右孩子。

2.二叉搜索树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。

3.二叉搜索树按照中序遍历将各结点打印出将各结点打印出来，将得到按照由小到大的排列。

4.若二叉搜索树的根结点没有左儿子，则根结点一定是值最小的结点。5.二叉搜索树一定是满二叉树。

6.从二叉搜索树的根结点一直沿右儿子向下找不一定能找到树中值最大的结点。7.二叉搜索树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。8.若二叉搜索树中关键码互不相同，则其中最小元素和最大元素一定是叶子结点。9.在任意一棵非空二叉搜索树中，删除某结点后又将其插入，则所得二叉搜索树与原二叉搜索树相同。

10.当向二叉搜索树中插入一个结点，则该结点一定成为叶子结点。11.AVL树是指左右子树的高度差的绝对值不大于1的二叉树。12.AVL是一棵二叉树，其树上任一结点的平衡因子的绝对值不大于1。

13.在AVL树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。

三、填空题

1.在一棵二叉搜索树上实施遍历后，其关键字序列是一个有序表。

2.一个无序序列可以通过构造一棵_______而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。

3.在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定________该结点的值，右子树上所有结点的值一定________该结点。

4.从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明_______，若元素的值小于根结点的值，则继续向_______查找，若元素的值大于根结点的值，则继续向________查找。

5.向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则接着向根结点的________插入，若元素的值大于根结点的值，则接着向根结点的________插入。6.根据n个元素建立一棵二叉搜索树的时间复杂度大致为________。7.二叉树中某一结点左子树的深度减去右子树的深度称为该结点的_______。8.深度为4的平衡二叉树中至少有个结点，至多有个结点。

9.在一棵AVL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过________。

四、应用题

1.一棵二叉搜索树的结构如下图所示，结点的值为1～8，请标出各结点的值。

2.若依次输入序列{62,68,30,61,25,14,53,47,90,84}中的元素，生成一棵二叉搜索树。画出生成后的二叉搜索树（画出生成过程）。

3.依次读入给定的整数序列{7,16,4,8,20,9,6,18,5}，构造一棵二叉搜索树,并计算在等概率情况下该二叉搜索树的平均查找长度ASL。（要求给出构造过程）

4.从空二叉树开始，严格按照二叉搜索树的插入算法（不进行平衡旋转），逐个插入关键码{18,73,10,5,68,99,27,41,51,32,25}构造出一棵二叉搜索树，画出这棵二叉搜索树并写出其前序、后序遍历序列。

5.若一棵二叉搜索树的关键字输入序列为{80，6，10，7，8，25，100，90}，请画出该二叉搜索树。

6.设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉搜索树并给出构造过程。

7.假定一个关键字序列为(38,52,25,74,68,16,30,54,90,72)，画出按序列中元素的次序生成的一棵二叉搜索树，求出其平均查找长度。

8.将数列（24，15，38，27，121，76，130）的各元素依次插入一棵初始为空的二叉搜索树中，请画出最后的结果并求等概率情况下查找成功的平均查找长度。

9.输入一个正整数序列{40,28,6,72,100,3,54,1,80,91,38}，建立一棵二叉搜索树，然后删除结点72，分别画出该二叉树及删除结点72后的二叉树。

10.根据元素插入的先后次序不同，可构成多种形态的二叉搜索树。请画出4棵含1，2，3，4四个元素且以1为根、深度为3的二叉搜索树。11.请画出从下面的二叉搜索树中删除关键码40后的结果。

***604050

12.对关键字序列（25, 16, 34, 39, 28, 56），1）画出按此序列生成的二叉搜索树。2）计算等概率下查找成功时的平均查找长度。

13.输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。

(1)按次序构造一棵二叉搜索树BS。

(2)依此二叉搜索树，如何得到一个从大到小的有序序列？

(3)假定每个元素的查找概率相等，试计算该二叉搜索树的平均查找长度(4)画出在此二叉搜索树中删除“66”后的树结构。

14.试推导深度为5的平衡二叉树最少包含多少个结点，并画出一棵这样的树。

15.画出在一个初始为空的AVL树中依次插入3,1,4,6,9,8,5,7时每一插入后AVL树的形态。若做了某种旋转，说明旋转的类型。

16.给定一个关键字序列4,5,7,2,1,3,6，生成一棵AVL树，画出构造过程。

17.给定关键字序列4,5,7,2,1,3,6，分别生成二叉搜索树和AVL树，并用二叉搜索树和AVL树两种方法查找，给出查找6的查找次数及查找成功的平均查找长度。

18.给定关键词输入序列{CAP, AQU, PIS, ARI, TAU, GEM, CAN, LIB, VIR, LEO, SCO}，假定关键词比较按英文字典序，试画出从一棵空树开始，依上述顺序（从左到右）输入关键词，用AVL树的插入算法生成一棵AVL树的过程，并说明生成过程中采用了何种转动方式进行平衡调整，标出树中各结点的平衡因子。

参考答案

一、6-10.ABCCC 1-5.BCABC

二、6-10.××××√ 11-13.√√× 1-5.√√√√×

三、1.2.3.4.5.6.7.8.9.四、1.中序

二叉搜索树小于，大于

查找成功，左子树，右子树左子树，右子树 O(n2)平衡因子 7, 15 1

2.3.ASL=(1+2*2+3*3+4*3)/9 = 26/9 = 2.89 4.前序：18 10 5 73 68 27 25 41 32 51 99 后序：5 10 25 32 51 41 27 68 99 73 18 5.6.7.二叉搜索树如图所示，平均查找长度等于32/10。

8.平均查找长度=1+2×2+3×2+4×2=19/7。

9.二叉搜索树

删除72后的二叉搜索树

10.11.或12.（1）

（2）(1+2*2+3*2+4*1)/6 = 2.5

13.（1）构造的二叉搜索树为：（4）删除结点66后

(2)对于一个二叉搜索树，想得到一个从大到小的序列只要先读右子树再读根结点，最后读左子树的遍历这颗二叉树就可以了。如果是要从小到大的序列，则只需中序遍历这颗二叉树即可。

(3)该二叉树的平均查找长度为：ASL=（1*1+2*2+3*4+4*3）/10=2.9 14.略 15.16.17.二叉搜索树

AVL树

从二叉搜索树查找6需4次，平均查找长度ASL=(1+2+2+3+3+3+4)/7=18/7≈2.57。从平衡二叉树查找6需2次，平均查找长度ASL=(1+2+2+3+3+3+3)=17/7≈2.43。18.单向左旋先右旋后左旋

第五篇：数据结构第九章排序习题及答案[小编推荐]

习题九

排序

一、单项选择题

1．下列内部排序算法中：

A．快速排序 B.直接插入排序 C.二路归并排序 D.简单选择排序 E.起泡排序 F.堆排序

（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）

（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<

（4）排序的平均时间复杂度为O(n•logn)的算法是（）为O(n•n)的算法是（）2．比较次数与排序的初始状态无关的排序方法是()。

A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序 3．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）84 47 25 15 21（2）15 47 25 84 21（3）15 21 25 84 47（4）15 21 25 47 84 则采用的排序是()。

A.选择 B.冒泡 C.快速 D.插入

4．下列排序算法中()排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A.选择 B.冒泡 C.归并 D.堆 5．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。

A．(38,40,46,56,79,84)B.(40,38,46,79,56,84)C．(40,38,46,56,79,84)D.(40,38,46,84,56,79)6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。A．冒泡 B.希尔 C.快速 D.堆

7.就平均性能而言，目前最好的内排序方法是()排序法。

A.冒泡 B.希尔插入 C.交换 D.快速 8.下列排序算法中，占用辅助空间最多的是：()A.归并排序 B.快速排序 C.希尔排序 D.堆排序

9.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。

A.3 B.10 C.15 D.25 10.快速排序方法在（）情况下最不利于发挥其长处。

A.要排序的数据量太大 B.要排序的数据中含有多个相同值 C.要排序的数据个数为奇数 D.要排序的数据已基本有序 11．下列四个序列中，哪一个是堆（）。

A.75,65,30,15,25,45,20,10 B.75,65,45,10,30,25,20,15 C.75,45,65,30,15,25,20,10 D.75,45,65,10,25,30,20,15 12.有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（）

A．-1，4，8，9，20，7，15，7 B．-1，7，15，7，4，8，20，9 C．-1，4，7，8，20，15，7，9 D．A，B，C均不对。

二、填空题

1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为________的。

2.按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。

3．直接插入排序用监视哨的作用是___________________________。

4．对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_______。

5．下面的c函数实现对链表head进行选择排序的算法,排序完毕,链表中的结点按结点值从小到大链接。请在空框处填上适当内容,每个空框只填一个语句或一个表达式： #include typedef struct node {char data;struct node *link;}node;node *select(node *head){node *p,*q,*r,*s;p=(node *)malloc(sizeof(node));p->link=head;head=p;while(p->link!=null){q=p->link;r=p;while((1)____________){ if(q->link->datalink->data)r=q;q=q->link;} if((2)___________){s=r->link;r->link=s->link;

s->link=((3)_________);((4)_________);}((5)________);} p=head;head=head->link;free(p);return(head);}

6．下面的排序算法的思想是：第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比较将次小的放在r[2]中，将次大的放在r[n-1]中，…,依次下去，直到待排序列为递增序。（注：<-->）代表两个变量的数据交换）。

void sort(SqList &r,int n){ i=1;while((1)______){ min=max=1;for(j=i+1;(2)________;++j){if((3)________)min=j;else if(r[j].key>r[max].key)max=j;} if((4)_________)r[min] <---->r[j];if(max!=n-i+1){if((5)_______)r[min] <----> r[n-i+1];else((6)______);} i++;} }//sort

7．下列算法为奇偶交换排序，思路如下：第一趟对所有奇数的i,将a[i]和a[i+1]进行比较,第二趟对所有偶数的i,将a[i]和a[i+1]进行比较,每次比较时若a[i]>a[i+1],将二者交换;以后重复上述二趟过程,直至整个数组有序。

void oesort(int a[n]){int flag,i,t;do {flag=0;for(i=1;ia[i+1]){flag=(1)______;t=a[i+1];a[i+1]=a[i];(2)________;} for(3)________ if(a[i]>a[i+1]){flag=(4)________;t=a[i+1];a[i+1]=a[i];a[i]=t;} }while(5)_________;}

第九章排序

一、单项选择题 1．（1）DC（2）ADF（3）B（4）ACF BDE 2．D 3．A 4．C 5．C 6．C 7.D 8.A 9.C 10.D 11．C 12.C

二、填空题 1.稳定、不稳定 2.内部、外部

3．免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。4．n(n-1)/2 5．题中为操作方便，先增加头结点（最后删除），p指向无序区的前一记录，r指向最小值结点的前驱，一趟排序结束，无序区第一个记录与r所指结点的后继交换指针。

(1)q->link!=NULL(2)r!=p(3)p->link(4)p->link=s(5)p=p->link 6．.(1)ir[n-i+1] 7．(1)1(2)a[i]=t(3)(i=2;i<=n;i+=2)(4)1(5)flag

数据结构习题(可用)

第一篇：数据结构习题(可用)

第二篇：数据结构习题与答案

第三篇：数据结构课后习题答案总结

第四篇：数据结构查找习题及答案

第五篇：数据结构第九章排序习题及答案[小编推荐]

相关范文推荐

纪委可用材料

辞职报告可用

无知者无畏可用材料

数据结构参考材料[范文大全]

严蔚敏数据结构课后习题及答案解析

可用好词好句

趣味知识讲座可用

2010班委工作总结(可用)