数据结构问答题

数据结构复习题：绪论

问答题

1、当你为解决某一问题而选择数据结构时,应从哪些方面考虑?

答：通常从两方面考虑：第一是算法所需的存储空间量；第二是算法所需的时间。对算法所需的时间又涉及以下三点：

（1）程序运行时所需输入的数据总量。 （2）计算机执行每条指令所需的时间。 （3）程序中指令重复执行的次数。 2、简述逻辑结构与存储结构的关系.

答：数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。

3、数据运算是数据结构的一个重要方面,试举例说明两个数据结构的逻辑结构和存储方式完全相同,只是对于运算的定义不同,因而两个结构具有显著不同的特性,则这两个数据结构是不同的. 答：栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运算集合不同而成为不同的数据结构。

数据结构复习题：线性表

问答题

1、线性表有两种存储结构：一是顺序表，二是链表。试问： (1)两种存储表示各有哪些主要优缺点?

(2)如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性 表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么?

(3)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么，应采用哪种存储结构?为什么?

答：(1)顺序存储是按索引（隐含的）直接存取数据元素，方便灵活，效率高，但插入、删除操作时将引起元素移动，因而降低效率；链接存储内存采用动态分配，利用率高，但需增设指示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作十分简单。

(2)应选用链接表存储结构。其理由是，链式存储结构用一组任意的存储单元依次存储线性表里各元素，这里存储单元可以是连续的，也可以是不连续的。这种存储结构，在对元素作插入或删除运算时，不需要移动元素，仅修改指针即可。所以很容易实现表的容量扩充。

(3)应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。而链表则是一种顺序存取的存储结构。

2、用线性表的顺序结构来描述一个城市的设计和规划合适吗?为什么?

不合适。因为一个城市的设计和规划涉及非常多的项目，很复杂，经常需要修改、 扩充和删除各种信息，才能适应不断发展的需要。有鉴于此，顺序线性表不能很好适应其需要，故是不合适的。 3、在单链表和双向表中，能否从当前结点出发访问到任一结点?

在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指 针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。 4、对链表设置头结点的作用是什么?(至少说出两条好处)

答：(1) 对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。

(2) 对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。

5、在单链表、双链表和单循环表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去？若可以，其时间复杂度各为多少？

答：1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。

2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。

3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。 6、简述顺序表和链表存储方式的特点。

答：顺序表可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率；而链表内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序表方便，但结点的插入、删除操作较简单。

数据结构复习题：栈和队列

问答题

1、试述栈的基本性质?

答：由栈的定义可知，这种结构的基本性质综述如下：

(1)集合性。栈是由若干个元素集合而成，当没有元素的空集合称为空栈；

(2)线性结构。除栈底元素和栈顶元素外，栈中任一元素均有唯一的前驱元素和后继元素； (3)受的运算。只允许在栈顶实施压入或弹出操作，且栈顶位置由栈指针所指示；

(4)数学性质。当多个编号元素依某种顺序压入，且可任意时刻弹出时，所获得的编号元素排列的数目，恰好满足卡塔南数列的计算，即： Ｃn ＝Ｃn 2n /(n＋1)

其中，n为编号元素的个数，Cn 是可能的排列数目。 4、为什么说栈是一种后进先出表?

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO--Last IN First Out表）。

5、对于一个栈,给出输入项A,B,C。如果输入项序列由A,B,C所组成,试给出全部可能的输出序列。 AＢＣ，ＢＡＣ，ＣＢＡ

6、有字符串次序为3*y-a/y↑2,试利用栈给出将次序改变为3y-*ay2↑/-的操作步骤。(可用X代表扫描该字符串函数中顺序取一字符进栈的操作,用S代表从栈中取出一个字符加到新字符串尾的出栈的操作)。例如:ABC变为BCA,则操作步骤为XXSXX。

X:进栈 S:出栈XSXXXSSSXXSXXSXXSSSS 7、跟踪以下代码,显示每次调用后队列中的内容。 InitQueue(qu); EnQueue(qu,'A'); EnQueue(qu,'B);

- 2 -

EnQueue(qu,'C); EnQueue(qu,x; EnQueue(qu,x; EnQueue(qu,'D); EnQueue(qu,'E); EnQueue(qu,'F); EnQueue(qu,x) EnQueue(qu,'G); EnQueue(qu,X) EnQueue(qu,X) EnQueue(qu,X)

答：InitQueue(qu); 队列为空 EnQueue(qu,'A'); 队列为A EnQueue(qu,'B); 队列为AB EnQueue(qu,'C); 队列为ABC EnQueue(qu,x; 队列为ABCx EnQueue(qu,x; 队列为ABCxx EnQueue(qu,'D); 队列为ABCxxD EnQueue(qu,'E); 队列为ABCxxDE EnQueue(qu,'F); 队列为ABCxxDEF EnQueue(qu,x) 队列为ABCxxDEFx EnQueue(qu,'G); 队列为ABCxxDEFxG EnQueue(qu,X) 队列为ABCxxDEFxGX EnQueue(qu,X) 队列为ABCxxDEFxGXX EnQueue(qu,X) 队列为ABCxxDEFxGXXX

8、假设Q[0..10]是一个线性队列,初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变化情况,若不能入队,请指出其元素,并说明理由。 d,e,b,g,h入队 d,e出队 i,j,k,l,m入队 n,o,p入队

解答：d,e,b,g,h入队 d e b g h F r d,e出队

b g h F r i,j,k,l,m入队

b g h i j k l m F r n,o,p入队

b g h i j k l m n o p

F r 所有元素均正好能入队，共有11个存储空间，恰好11个元素

- 3 -

9、假设CQ[0..10]是一个环形队列,初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变化情况,若不能入队,请指出其元素,并说明理由。 d,e,b,g,h入队 d,e出队 i,j,k,l,m入队 b出队 n,o,p入队

解答： 图略 。

p不能入队，共有11个地址，p为第12个元素，故不能入队

10、有5个元素,其进栈次序为A、B、C、D、E,在各种可能的出栈次序中,以元素C、D最先出栈(即C第一个且D第一个出栈)的次序有哪几个? 答：三个：CDEBA，CDBEA，CDBAE

11、设输入元素为1、2、3、P和A,入栈次序为123PA,元素经过栈后到达输出序列,当所有元素均到达输出序列后,有哪些序列可以作为高级语言的变量名?

答：一般说，高级语言的变量名是以字母开头的字母数字序列。故本题答案是: AP321,PA321,P3A21,P32A1,P321A。 12、简要叙述栈和队列的特点.

答：栈和队列都是插入和删除操作的位置受的线性表。栈是限定仅在表尾进行插入和删除的线性表，是后进先出的线性表，而队列是限定在表的一端进行插入，在另一端进行删除的线性表，是先进先出的线性表

数据结构复习题：树和二叉树

问答题

1、对于二叉排序树，当所有结点的权都相等的情况下，最佳二叉排序树有何特点。 其特点是只有最下面的二层结点可以小于２，其它结点的度数必须为２

3、已知一组元素为(46、25、78、62、18、34、12、40、73)，试画出按元素排列顺序输入而生成的一棵二叉排序树。

解答：得到的二叉排序树如下图所示。 46

25 78

18 34 62

12 40 73

4、已知一棵树的边的集合表示为：(L,N),(G,K),(G,L),(G,M),(B,E),(B,F),(D,G), (D,H),(D,I),(D,J),(A,B),(A,C),(A,D))画出这棵树，并回答下列问题： (1)树根是哪个结点？哪些是叶子结点？哪些是非终端结点？ (2)树的度是多少？各个结点的度是多少？

(3)树的深度是多少？各个结点的层数是多少？以结点Ｇ为根的子树的深度是多少？

(4)对于结点Ｇ，它的双亲是哪个结点？它的祖先是哪些结点？它的孩子是哪些结点？ 它的子孙是哪些结点？它的兄弟和堂兄弟分别是哪些结点？

- 4 -

解答：(1)树的根是A，而E、F、C、H、I、J、K、M、N是叶子结点，其它为非终端结点。

(2)树的度为4。deg(A)＝3,deg(B)＝2,deg(D)＝4,deg(G)＝3,deg(L)＝1，其它各叶子结点的度均为0。 (3)树的深度为5（设根结点的深度为1）。level(A)＝1,level(B)＝2,level(C)＝2, …,level(G)＝3,…,level(K)＝4,…，level(N)＝5。

(4)D是G的双亲；A、D是G的祖先；K、L、M是G的孩子；K、L、M和N是G的子孙；H、I、 J是G的兄弟；E、F是G的堂兄弟。

5、设高度为h的二叉树上只有度为0和度为2的结点，问该二叉树的结点数可能达到的最大值和最小值。 解答：最大值(高度为h的满二叉树) 20 ＋21 ＋22 ＋…＋2h-1 ＝2h －1

最小值：第一层只有一个结点，其余的h-1层各有2个结点，所以最小值为2h-1个。 6、设二叉树BT的存储结构如下：

１ ２ ３ ４ ５ ６ ７ ８ ９ 10 ┏━┳━┳━┳━┳━┳━┳━┳━┳━┳━┓ Lchild ┃０┃０┃２┃３┃７┃５┃８┃０┃10┃１┃ ┣━╋━╋━╋━╋━╋━╋━╋━╋━╋━┫ data ┃Ｊ┃Ｈ┃Ｆ┃Ｄ┃Ｂ┃Ａ┃Ｃ┃Ｅ┃Ｇ┃Ｉ┃ ┣━╋━╋━╋━╋━╋━╋━╋━╋━╋━┫ Rchild ┃０┃０┃０┃９┃４┃０┃０┃０┃０┃０┃ ┗━┻━┻━┻━┻━┻━┻━┻━┻━┻━┛ (1) 画出图。

(2) 写出前序、中序、后序遍历次序。 解答：(1)见下图。

A

B

C D

E F G

H I

J

(2)前序遍历：ABCEDFHGIJ 中序遍历：ECBHFDJIGA 后序遍历：ECHFJIGDBA

7、已知一棵二叉树先序遍历结果为ABCDEFGHIJ，中序遍历的结果为CBEDAHGIJF，试画出该二叉树。 解答：由前序遍历结果可知该二叉树的根结点为Ａ。由此及中序遍历结果可知，该二叉树在中序遍历下的左、右子树为

CBED和HGIJF

依此可推出前序遍历的左、右子树的结点序列为 BCDE和FGHIJ

B和F又分别为左、右子树的根结点，进而又可推出以B为根结点的左、右子树，以及 以F为根结点的左、右子树。依此类推，可推出二叉树见下图。 A

- 5 -

B F

C D G

E H I

J

8、设a是含有n个元素的整数数组,写出一个求n个元素的平均值的递归定义。 解答：#include #define AVE(A,B) aver(A,B,0)

double aver(float *a,int n,int t) {

if (t!=n) return (a[t]/n+aver(a,n,t+1)); else return 0; }

int main(void) {

float a[]={1,5,9,13,17}; printf(\"%f\ return 0; }

9、设a是含有n个元素的整数数组:

(1) 写出求该数组中最大元素的递归定义。 (2) 写出求该数组中最小元素的递归定义。 答：(1)int A :: Max (int n) //递归求最大值 {

if (n==1) return E[0]; int t=Max ( n-1 );

if (E[n-1]>t) return E[n-1]; else return t; }

(2) int A :: Min (int n) //递归求最小值 {

if (n==1) return E[0]; int t=Min ( n-1 );

if (E[n-1]>t) return E[n-1]; else return t; }

10、设a是含有n个元素的整数数组:

- 6 -

(1) 写出求n个整数之和的递归定义。 (2) 写出求n个整数之积的递归定义。 解答：（1）int A :: Sum (int n) //递归求数组之和 {

if (n==1) return E[0];

else return E[n-1]+Sum (n-1); }

（2） int A :: Multi (int n) //递归求整数之积 {

if (n==1) return E[0];

else return E[n-1]*Multi (n-1); }

11、二维数组A[4][4](即A[0..3][0..3])的元素起始地址是loc(A[0][0])=1000,元素的长度为2,则LOC(A[2][2])的地址为多少?

答：LOC(A[2][2])= loc(A[0][0])+（2*4+2)*2=1000+20=1020

数据结构复习题：图

问答题

1、无向图G如下图： B E / \\ / \\ A D G \\ / \\ / C F 试给出

(1)该图的邻接矩阵。 (2)该图的邻接表。

(3)从A出发的“深度优先”遍历序列。 (4)从A出发的“广度优先”遍历序列。 解答：(1) 图G的邻接矩阵

┏０ １ １ ０ ０ ０ ０┓ ┃１ ０ ０ １ ０ ０ ０┃ ┃１ ０ ０ １ ０ ０ ０┃ A＝┃０ １ １ ０ １ １ ０┃ ┃０ ０ ０ １ ０ ０ １┃ ┃０ ０ ０ １ ０ ０ １┃ ┗０ ０ ０ ０ １ １ ０┛ (2)邻接表如见：

┌─┬─┐ ┌─┬─┐ ┌─┬─┐ １│Ａ│ ┼→─┤Ｂ│ ┼→─┤Ｃ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ２│Ｂ│ ┼→─┤Ａ│ ┼→─┤Ｄ│＾│

- 7 -

├─┼─┤ ├─┼─┤ ├─┼─┤ ３│Ｃ│ ┼→─┤Ａ│ ┼→─┤Ｄ│＾│

├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐ ┌─┬─┐ ４│Ｄ│ ┼→─┤Ｂ│ ┼→─┤Ｃ│ ┼→┤Ｅ│＾├→─┤Ｆ│＾│

(3)从顶点A出发按深度优先遍历序列(不是唯一的)为A、B、D、C、E、G、F (4)从顶点A出发按广度优先遍历序列(不是唯一的)为A、B、C、D、E、F、G

2、用邻接矩阵表示图时,矩阵元素的个数与顶点个数是否相关?与边的条数是否有关?

答：设图的顶点个数为n(n≥0)，则邻接矩阵元素个数为n2，即顶点个数的平方，与图的边数无关。 3、对于稠密图和稀疏图,就存储空间而言,采用邻接矩阵和邻接表哪个更好些? 答：稠密图采用邻接矩阵好，稀疏图采用邻接表好 4、请回答下列关于图的一些问题:

(1) 有n个顶点的有向强连通图最多有多少条边?这样的图应该是什么形状? (2) 有n个顶点的有向强连通图最少有多少条边?这样的图应该是什么形状?

(3) 表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵? 答：（1）最多有n(n-1)条边 （2）最少有 n条边

（3）106，不一定是稀疏矩阵（稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律） 5、对n个顶点的无向图和有向图,采用邻接矩阵和邻接表表示时,如何判别下列有关问题? (1) 图中有多少条边?

(2) 任意两个顶点i和j是否有边相连? (3) 任意一个顶点的度是多少?

答：无向图采用邻接表时，⑴ 边表中的结点个数之和除以2。⑵ 第i个边表中是否含有结点j。⑶ 该顶点所对应的边表中所含结点个数。

6、己知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,画出该二叉树的先序线索二叉树. 答：二叉树及线索二叉树（略）。 先序序列为：abcdefghij

7、下列整数序列由选序遍历一棵二叉排序树得到:50,40,30,45,65,55,70,80.试构造一棵这样的二叉排序树.

答：

数据结构复习题：内部排序

- 8 -

问答题

1、设有5000个无序的元素，希望用最快速度挑选出其中前10个最大的元素。在以下 的排序方法中，采用哪种方法最好?为什么?

快速排序，堆排序，归并排序，基数排序的Shell排序。

1、上面所列的几种排序方法的速度都很块，但快速排序、归并排序、基数排序和希尔排序都是在排序结束后才能确定数据元素的全部顺序，而无法知道排序过程中部分元素的有序性。而堆排序则每次输入一个最大（或最小）的元素，然后对堆进行调整，保证堆顶的元素总是余下元素中最大（或最小）的。根据题意，只要选取前10个最大的元素，故采用堆排序方法是合适的

2、判断下列序列是否是堆。若不是堆，则把它们依次调整为堆。 (1) (100，85，98，77，80，60，82，40，20，10，66)。 (2) (100，98，85，82，80，77，66，60，40，20，10)。 (3) (100，85，40，77，80，60，66，98，82，10，20)。 (4) (10，20，40，60，66，77，80，82，85，98，100)。 解答：根据堆的定义可知堆中元素满足下面中的某一个式子的关系， ┌≤k2i ┌≥k2i ① ki 或 ② ki └≤k2i＋1 └≥k2i＋1 因此(1)、(2)和(4)序列是堆。(3)不是堆。

(3) 调整为100,98,66,85,80,60,40,77,82,10,20后成为堆。

3、什么是内部排序？什么是排序方法的稳定性和不稳定性？

解答：假设给定含有n个记录(R1 ，R2 ，…，Rn ）的文件，其相应的关键字为(K1 ，K2 ，…， Kn )，则排序是确定一个排列P(1)，P(2)，…，P(n)，使得KP(1) ≤KP(2) ，…，KP(n) ，

从而得到有序文件(RP(1) ，RP(2) ，…，RP(n) )。整个排序过程都在内存进行的排序称为 内部排序。 假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排 序法排序后，若这些相同关键字的记录的相对次序仍然保持不变，则这种排序方法是稳定 的，否则称这种排序方法是不稳定的。 4、输入一个正整数序列{40,28,6,72,100,3,,1,80,91,38},建立一棵二叉排序树,然后删除结点72,分别画出该二叉树及删除结点72后的二叉树。

5、设数据集合d={1,12,5,8,3,10,7,13,9},试完成下列各题: (1) 依次取d中各数据,构造一棵二叉排序树bt; (2) 如何依据此二叉树bt得到d的一个有序序列; (3) 画出在二叉树bt中删除\"12\"后的树结构。 解答：（1）（3）图略。

（2）根据二叉排序树中左子树，根结点，右子树的排列顺序，有序序列：1，3，5，7，8，9，10，12，13 6、对给定的数列R={7,16,4,8,20,9,6,18,5},构告一棵二叉排序树,并且 (1) 给出按中序遍历得到的数列R1 (2) 给出按后序遍历得到的数列R2

解答：图略。中序遍历序列R1：5,6,4,7,8,9,16,18,20 后序遍历序列R2：5,6,4,9,8,18,20,16,7

7、设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77},采用散列函数:H(key)=key%13

采用开放地址法的线性探测再散列方法解决冲突,试在0～18的散列地址空间中对该关键字序列构造散列表。 解答： H(19)=19 MOD 13=6 H(01)=01 MOD 13=1 H(23)=23 MOD 13=10

- 9 -

H(14)=14 MOD 13=1(冲突) H(14)=(1+1) MOD 19=2 H(55)=55 MOD 13=3 H(20)=20 MOD 13=7

H(84)=84 MOD 13=6 (冲突)

H(84)=(6+1) MOD 19=7 (仍冲突) H(84)=(6+2) MOD 19=8 H(27)=27 MOD 13=1 (冲突) H(27)=(1+1) MOD 19=2 (冲突) H(27)=(1+2) MOD 19=3 (仍冲突) H(27)=(1+3) MOD 19=4 H(68)=68 MOD 13=3 (冲突)

H(68)=(3+1) MOD 19=4 (仍冲突) H(68)=(3+2) MOD 19=5 H(11)=11 MOD 13=11

H(10)=10 MOD 13=10 (冲突)

H(10)=(10+1) MOD 19=11 (仍冲突) H(10)=(10+2) MOD 19=12 H(77)=77 MOD 13=12 (冲突) H(77)=(12+1) MOD 19=13

因此，各关键字相应的地址分配如下： address(01)=1 address(14)=2 address(55)=3 addre

8、线性表的关键字集合{87,25,310,08,27,132,68,95,187,123,70,63,47},共有13个元素,己知散列函数为:H(key)=k%13

采用拉链法处理冲突。设计出这种链表结构,并计算该表的成功查找的平均查找长度。

9、己知序列{17,18,60,40,7,32,73,65,85},请给出采用冒泡排序法对该序列作为升序排序时的每一趟的结果。 解答：初始：17，18，60，40，7，32，73，65，85 第1趟：17，18，40，7，32，60，65，73，85 第2趟：17，18，7，32，40，60，65，73，85 第3趟：17，7，18，32，40，60，65，73，85 第4趟：7，17，18，32，40，60，65，73，85 第5趟：7，17，18，32，40，60，65，73，85 第5趟无元素交换，则排序结束。

10、己知序列 {503，87，512，61，908，170，7，275，653，462}，请给出采用快速排序法对该序列作升序排序时的每一趟结果。

解答：原始序列：503，87，512，61，908，170，7，275，653，462 第1趟： [462，87，275，61，170]503[7，908，653，512] 第2趟： [170，87，275，61] 462，503[7，908，653，512] 第3趟： [87，61]170[275] 462，503[7，908，653，512] 第4趟： 61 [87]170[275] 462，503[7，908，653，512]

第5趟： 61 ，87，170，[275] 462，503[7，908，653，512]

- 10 -

第6趟： 61 ，87，170，275，462，503[7，908，653，512] 第7趟： 61 ，87，170，275，462，503[512，653]7[908] 第8趟： 61 ，87，170，275，462，503，512，[653] 7[908] 第9趟： 61 ，87，170，275，462，503，653，7[908] 第10趟： 61 ，87，170，275，462，503，653，7，908

11、己知序列{503,87,512,61,908,170,7,275,653,462},请给出采用的基数排序法对该序列作升序排序时的每一趟的结果。

解答：依题意，采用基数排序法排序的各趟的结果如下：

初始：503，87，512，61，908，170，7，275，653，462 1趟（按个位排序）：170，61，462，512，503，653，275，87，7，908 2趟（按十位排序）：503，908，512，653，61，462，170，275，87，7 3趟（按百位排序）：61，87，170，275，462，503，512，653，7，908

12、己知序列{70,83,100,65,10,32,7,9},请给出采用直接插入排序法对该序列作升序排序时的每一趟的结果。 解答：原始序列： 70，83，100，65，10，32，7，9 第1趟结果： 70，83，100，65，10，32，7，9 第2趟结果： 70，83，100，65，10，32，7，9 第3趟结果： 65，70，83，100，10，32，7，9 第4趟结果： 10，65，70，83，100，32，7，9 第5趟结果： 10，32，65，70，83，100，7，9 第6趟结果： 7，10，32，65，70，83，100，9 第7趟结果： 7，9，10，32，65，70，83，100

13、己知序列{10,18,4,3,6,12,1,9,18,8},请给出采用希尔排序法对该序列作升序排序时的每一趟结果。 解答：原始序列：10,18,4,3,6,12,1,9,18,8

分成5个子序列的结果：10，1，4，3，6，12，18，9，18，8 再分为2个子序列的结果：10，1，4，3，6，12，18，9，18，8 最后结果： 1，3，4，6，8，9，10，12， 18，18

14、己知序列{10,18,4,3,6,12,1,9,18,8},请给出采用归并排序法对该序列作作升序排序时的每一趟的结果。 解答： 采用2路归并排序的结果如下：

初始状态： 10 ,18 ,4 ,3 ,6 ,12 ,1 ,9 ,18,8 第1趟归并后：10，18，3，4，6，12，1，9，8，18 第2趟归并后：3，4，10，18，1，6，9，12，8，18 第3趟归并后：1，3，4，6，9，10，12，18，8，18

最后1趟归并得结果：1，3，4，6，8，9，10，12，18，18

15、在冒泡排序过程中,有的关键字在某趟排序中朝着与最终排序相反的方向移动。试举例说明之。快速排序过程中有没有这种现象?

在逆序时排序码会朝着与最终位置相反的方向移动。例如（5，4，2，1），第一趟冒泡排序后为（4，2，1，5），关键字4的位置被移动到首位，朝着与最终排序相反的方向移动。快速排序没有这种现象。

16、如果在10^6个记录中找到两个最小的记录,你认为可采用下列方法中的什么关的排序方法所需的关键字比较次数最少?共计多少?

根据堆排序的特点，每次都是输出一个堆顶元素，然后对堆进行再调整，保证堆顶元素总是当前剩下元素的最大或最小，从而可知，欲在一个大量数据的文件中，如10^6个记录中找到两个最小的记录，可采用堆排序。 17、如果只想得到一个序列中第k个最小元素之前的部分排序序列,最好采用什么排序方法?为什么?如由这样的一个序列:{57,40,38,11,13,34,84,75,25,6,19,9,7}得到其第4个最小元素之前的部分序列{6,7,9,11},使用所

- 11 -

选择的算法实现时,要执行多少次比较?

解答：采用堆排序最合适，依题意可知只需取得第k个最小元素之前的排序序列时，堆排序的时间复杂度 Ο(n+klog2n)，若k≤nlog2n，则得到的时间复杂性是Ο(n)。

对于上述序列得到其前4个最小元素，使用堆排序实现时，执行的比较次数如下： 初始建堆：比较20次，得到6； 第一次调整：比较5次，得到7； 第二次调整：比较4次，得到9； 第三次调整：比较5次，得到11。

18、对于快速排序的非递归算法,可以用队列(而不用栈)实现吗?若能,说明理由;若不能,也要说明理由。

可以用队列来代替。在快速排序的过程中，通过一趟划分，可以把一个待排序区间分为两个子区间，然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间时，保存另一个区间的上界和下界。这个功能利用队列可以实现，只不过是处理子区间的顺序有所变动而已。

19、己知下列各种初始状态(长度为n)的元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)?

解答：依题意，最好情况下的比较次数即为最少比较次数。

⑴ 插入第i（2≤i≤n）个元素的比较次数为1，因此总的比较次数为： 1+1+……+1=n-1

⑵ 插入第i（2≤i≤n）个元素的比较次数为i，因此总的比较次数为： 2+3+……+n=(n-1)(n+2)/2

⑶ 比较次数最少的情况是所有记录关键码按升序排列，总的比较次数为： n-1

⑷ 在后半部分元素的关键码均大于前半部分元素的关键码时需要的比较次数最少，总的比较次数为： n-1 20、若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找,试在下述两种情况下分别讨论两者在等概率时的平均查找长度:

(1) 查找不成功,即表中无关键字等于给定值k的记录. (2) 查找成功,即表中有关键字等于给定值k的记录. 答：(1)有序和无序都是n+1 (2)有序和无序都是（n+1）/2

21、己知一个有序表为{12,18,20,25,29,32,40,62,83,90,95,98},当二分查找法为29和90的元素时,分别需要多少次比较才能查找成功?若采用顺序查找时,分别需要多少次比较才能查找成功?

答：二分法查29时，需要比较3次才能查找成功。二分法查90时，需要比较3次才能查找成功；顺序查找29时，需要比较5次才能查找成功。顺序查找90时，需要比较10次才能查找成功。

22、关键字序列{7,4,1,14,100,30,5,9,20,134},设哈希函数为h(key)=Key Mod 13,试给出表长为13的哈希表(用线性探测开放定址法处理冲突),并求出在等概率情况下,查找成功时和查找不成功时的平衡查找长度. 答： k 7 4 1 14 100 30 5 9 20 134 k%13 6 4 1 1 9 4 5 9 7 4

散列地址 0 1 2 3 4 5 6 7 8 9 10 11 12 关键字 1 14 4 30 7 5 20 100 9 134

成功到位次数 1 2 1 2 1 3 2 1 2 8

不成功到位次数 1 3 2 1 9 8 7 6 5 4 3 2 1 查找成功的平均查找长度为（1+2+1+2+1+3+2+1+2+8）/10=23/10

查找不成功的平均查找长度为 （1+3+2+1+9+8+7+6+5+4+3+2+1）/13=4

- 12 -

23、比较直接插入排序和希尔排序的不同点.

答：直接插入排序：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。 希尔排序：是针对直接插入排序算法的改进，该方法又称缩小增量排序。该方法实质上是一种分组插入方法 24、给出关键字序列{17，8，21，35，32，15，21，25，12，23}的直接插入排序过程. 答：（8，17）21，35，32，15，21，25，12，23 （8，17，21）35，32，15，21，25，12，23 （8，17，21，35）32，15，21，25，12，23 （8，17，21，32，35）15，21，25，12，23 （8，15，17，21，32，35）21，25，12，23 （8，15，17，21，21，32，35）25，12，23 （8，15，17，21，21，25，32，35）12，23 （8，12，15，17，21，21，25，32，35）23 （8，12，15，17，21，21，23，25，32，35） 25、指出堆和二叉排序树的区别?

答：在二叉排序树中，每个结点的值均大于其左子树上所有结点的值，小于其右子树上所有结点的值，对二叉排序树进行中序遍历得到一个有序序列。所以，二叉排序树是结点之间满足一定次序关系的二叉树；堆是一个完全二叉树，并且每个结点的值都大于或等于其左右孩子结点的值（这里的讨论以大根堆为例），所以，堆是结点之间满足一定次序关系的完全二叉树。

26、堆排序是否是一种稳定的排序方法?为什么?试举例说明。

答：堆排序不是稳定的排序方法。因为堆排序再调整堆时，有可能使原来键值相等的元素的相对位置改变，所以是不稳定排序。例如对键值序列｛7，4，2，2｝，建小根堆由小到大排序的结果是｛2，2，4，7｝，两个2的相对位置改变了。

27、对于n个元素组成的线性表进行快速排序，所需要进行的比较次数与这n个元素的初始排列有关。问: (1)当 n=7 时，最好情况下需进行多少次比较？请说明理由。 (2)当 n=7 时，给出一个最好情况的初始排列的实例。

(3)当 n=7 时，在最坏情况下需进行多少次比较？请说明理由。 (4)当 n=7 时，给出一个最坏情况的初始排序的实例。

答：(1) 在最好情况下，假设每次划分能得到两个长度相等的子文件，文件的长度n=2k-1，那么第一遍划分得到两个长度均为?n/2?的子文件，第二遍划分得到4个长度均为?n/4?的子文件，以此类推，总共进行k=log2(n+1)遍划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一遍需比较6次，第二遍分别对两个子文件（长度均为3，k=2）进行排序，各需2次，共10次即可。 (2) 在最好情况下快速排序的原始序列实例：4,1,3,2,6,5,7。

(3) 在最坏情况下，若每次用来划分的记录的关键字具有最大值(或最小值)，那么只能得到左(或右)子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递增次序排列时，快速排序的效率与冒泡排序相同，其时间复杂度为O(n2)。所以当n=7时，最坏情况下的比较次数为21次。 (4) 在最坏情况下快速排序的初始序列实例： 7,6,5,4,3,2,1，要求按递增排序。

28、已知{503,87,512,61,908,170,7,275,653,462}，采用二路归并排序法对该序列作升序排序时的每一趟的结果。

答：初始关键字： 503，87，512，61，908，170，7，275，653，462 一趟归并之后：87，503，61，512，170，908，275，7，462，653 两趟归并之后：61，87，503，512，170，275，7，908，462，653 三趟归并之后：61，87，170，275，503，512，7，908，462，653 四趟归并之后：61，87，170，275，462，503，512，653，7，908

- 13 -

29、在堆排序、快速排序和归并排序中:

(1)若只从存储空间考虑，则应首先选取哪能种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？ (2)若只从排序结果的稳定性考虑，则应选取哪种排序方法？ (3)若只从平均情况下排序最快考虑，则应选取哪种排序方法？

(4)若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？ 答：(1)堆排序，快速排序，归并排序 (2)归并排序 (3)快速排序 (4)堆排序

30、有一个有序表R[1..13]={1,3,9,12,32,41,45,62,75,77,82,95,100},当用二分查找法查找关键字为82的结点时,经多少次比较后查找成功,依次与哪些关键字进行比较?

答：经4次比较后查找成功，依次与关键字45，77，95，82进行比较。

31、以关键字序列{265,301,751,129,937,863,742,694,76,438}为例,给出归并排序算法的各趟排序结束时,关键字序列的状态.

答：初始关键字： 265，301，751，129，937，863，742，694，76，438 一趟归并之后：265，301，129，751，863，937，694，742，76，438 两趟归并之后：129，265，301，751，694，742，863，937，76，438 三趟归并之后：129，265，301，694，742，751，863，937，76，438 四趟归并之后： 76，129，256，301，438，694，742，751，863，937

32、画出对长度为10的有序表进行二分查找的一棵判断树,并求其等概率时查找成功的平均查找长度. 答：判断树（略）。

ASL=（1+2+2+3+3+3+3+4+4+4）/10=2.9 33、简述二路归并排序思想.

答：将两个有序表合并为一个有序表。1个元素的表总是有序的，所以对n个元素的待排序列，每个元素可看成1个有序子表。对子表两两合并生成 个子表，所得子表除最后一个子表长度可能为1外，其余子表长度均为2。再进行两两合并，直到生成n个元素按关键码有序的表。

34、己知待排序的关键字序列为:{72,71,74,80,68,14,86,37,17}.请列出快速排序过程中第一趟排序的最终结果.

答：初始关键字： [72]，71，74，80，68，14，86，37，17 （1） 17，71，74，80，68，14，86，37，72 （2） 17，71，72，80，68，14，86，37，74 （3） 17，71，37，80，68，14，86，72，74 （4） 17，71，37，72，68，14，86，80，74 完成一趟排序： 17，71，37，14，68，[72]，86，80，74

35、设有关键字序列为:{2,4,6,9,14,16,13}.基本区域长度为8(地址0..7),哈希函数采用除留余数法,用线性探查法解决冲突.试画出其存储结构,并给出查找成功的平均查找长度. 答：k 2 4 6 9 14 16 13 k%8 0 0 0 1 6 0 5

得到的散列表如下：

0 1 2 3 4 5 6 7 2 4 6 9 16 13 14

- 14 -

成功到位次数 1 2 3 3 5 1 1 查找成功的平均查找长度为 （1+2+3+3+5+1+1）/7=16/7

36、己知一组元素的排序码为(46,74,16,53,14,26,40,38,86,65,27,34)

1. 利用直接插入排序的方法写出每次向前面有序表插入一个元素后的排序结果. 2. 利用直接选择排序方法写出每次选择和交换后的排列结果.

3. 利用堆排序的方法写出在构成初始堆和利用堆排序的过程中,每次筛运算后的排列结果,并画出初始堆所对应的完全二叉树.

4 利用快速排序的方法写出每一层划分后的排列结果,并画出由此快速排序得到的二叉搜索树. 5 利用归并排序的方法写出每一趟二路归并排序后的结果.

答：(1) ( 46 ) ( 74 16 53 14 26 40 38 86 65 27 34 ) ← 初态 ( 46 74 ) ( 16 53 14 26 40 38 86 65 27 34 ) ( 16 46 74 ) ( 53 14 26 40 38 86 65 27 34 ) ( 16 46 53 74 ) ( 14 26 40 38 86 65 27 34 ) ( 14 16 46 53 74 ) ( 26 40 38 86 65 27 34 ) ( 14 16 26 46 53 74 ) ( 40 38 86 65 27 34 ) ( 14 16 26 40 46 53 74 ) ( 38 86 65 27 34 ) ( 14 16 26 38 40 46 53 74 ) ( 86 65 27 34 ) ( 14 16 26 38 40 46 53 74 86 ) ( 65 27 34 ) ( 14 16 26 38 40 46 53 65 74 86 ) ( 27 34 ) ( 14 16 26 27 38 40 46 53 65 74 86 ) ( 34 ) ( 14 16 26 27 34 38 40 46 53 65 74 86 ) (2) ( 46 74 16 53 14 26 40 38 86 65 27 34 )

37、给出关键字序列{17，8，21，35，32，15，21，25，12，23}的希尔排序过程. 答：希尔排序（增量为5，2，1）的过程如下：

初始关键字 17 8 21 35 32 15 21 25 12 23 （d1=5） 第一趟排序结果 15 8 21 12 23 17 21 25 35 32 （d2=2） 第二趟排序结果 15 8 21 12 21 17 23 25 35 32 （d3=1） 第三趟排序结果 8 12 15 17 21 21 23 25 32 35

- 15 -