数据结构习题(可用)_数据结构习题答案
数据结构习题(可用)由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构习题答案”。
第 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
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 【解析】如果初始排列基本有序，则对希尔排序来说，前几趟的插入工作大为减少。冒泡排序和直接插入
2n
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)（）
n
