广工2015数据结构复习题目及答案

《数据结构-C语言版》

第一章 绪论

单项选择题

1．在数据结构中，数据的基本单位是_____ ____。

A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量 2．数据结构中数据元素之间的逻辑关系被称为__ ____。

A. 数据的存储结构 B. 数据的基本操作 C. 程序的算法 D. 数据的逻辑结构 3．在数据结构中，与所使用计算机无关的是数据的____ ___。

A. 存储结构 B. 逻辑和物理结构 C. 逻辑结构 D. 物理结构 4．在链式存储结构中，数据之间的关系是通过____ ____体现的。 A. 数据在内存的相对位置 B. 指示数据元素的指针 C. 数据的存储地址 D. 指针 5．计算算法的时间复杂度是属于一种____ ___。

A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法

6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。 A. n2 B. nlogn C. n D. logn

7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。

A. O(1) B. O(n) C. O(200n) D. O(nlog2n)

1

CDCBBDD

第二章 线性表

单项选择题

1．链表不具有的特点是____ ____。

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

2．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为 。

A. 139 B. 140 C. 147 D. 148 3．在线性链表存储结构下，插入操作算法 。 A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满 D. 需要判断是否表空和表满

4．在一个单链表中，若删除p所指结点的后继结点，则执行 。 A. p->next = p->next->next; B. p->next = p->next;

C. p = p->next->next; D. p = p->next; p->next = p->next->next;

5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为 。 A. O(n) B. O(1) C. O(m) D. O(m+n)

6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是 。 A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式 ACCABB 填空题

1．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。 2．在单链表中，指针p所指结点为最后一个结点的条件是 。

3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 。 4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是 。

5．在长度为n的顺序表中插入一个元素的时间复杂度为 。 1前驱 2 p->next==NULL

2

3.1 4.n-i+1 5.O(n) 例题解析

【例2-1】 编写一个算法将一个单链表逆转，要求在原表上进行，不允许重新建链表。 解：该算法可以在遍历原表的时候将各结点的指针逆转，从原表的第一个结点开始，头结点的指针在最后修改成指向原表的最后一个结点，即新表的第一个结点。实现本题功能的函数如下：

void inverse(Lnode *h) {s=h->next;

if(s==NULL) return; q=NULL; p=s;

while(p!=NULL) { p=p->next;

s->next=q; /*逆转指针*/ q=s; /*指针前移*/ s=p; }

h->next=q; /*头指针h的后继是p*/ }

【例2-2】 编写一算法将两个按元素值递增有序排列的单链表A和B归并成一个按元素值递增有序排列的单链表C。

解：对于两个或两个以上的，结点按元素值有序排列的单链表进行操作时，应采用“指针平行移动，依次扫描完成”的方法。从两表的第一个结点开始顺链表逐个将对应数据元素进行比较，复制小的并插入c表尾。当两表中之一已到表尾，则复制另一个链表的剩余部分，插入到c表尾。设pa、pb分别指向两表当前结点，p指向c表的当前表尾结点。若设A中当前所指的元素为a，B中当前所指的元素为b，则当前应插入到 C中的元素c为

?ac???b 例如：A=(3,5,8,11) B=(2,6,8,9,11,15,20)

则 C=(2,3,5,6,8,8,9,11,11,15,20) 实现本题功能的函数如下： Lnode *hb(Lnode *pa,Lnode *pb) {Lnode *p,*q,*pc;

a?b a?b pc=(Lnode*)malloc(sizeof(Lnode)); /*建立表c 的头结点pc*/

3

p=pc; /*p指向C表头结点*/ while(pa!=NULL&&pb!=NULL) {

q=(Lnode*)malloc(sizeof(Lnode)); /*建立新结点q*/

if(pb->datadata) /*比较A、B表中当前结点的数据域值的大小*/ {q->data=pb->data; /*B中结点值小，将其值赋给q的数据域*/ pb=pb->next; /*B中指针pb后移*/ } else

{q->data=pa->data; /*相反，将A结点值赋给q的数据域*/ pa=pa->next; /*A中指针pa后移*/ }

p->next=q; /*将q接在p的后面*/ p=q; /*p始终指向C表当前尾结点*/ }

while(pa!=NULL) /*若表A比B长，将A余下的结点链在C表尾*/ {q=(Lnode*)malloc(sizeof(Lnode)); q->data=pa->data; pa=pa->next; p->next=q; p=q; }

while(pb!=NULL) /*若表B比A长，将B余下的结点链在C表尾*/ {q=(Lnode*)malloc(sizeof(Lnode)); q->data=pb->data; pb=pb->next; p->next=q; p=q; }

p->next=NULL;

p=pc; /*p指向表C的头结点pc*/

pc=p->next; /*改变指针状态，使pc指向p的后继*/ free(p); /*释放p空间*/ return (pc); }

此算法的时间复杂度为O(m+n)，其中m，n分别是两个被合并表的表长。

4

第三章

单项选择题

栈和队列

1．在初始为空的堆栈中依次插入元素f，e，d，c，b，a以后，连续进行了三次删除操作，此时栈顶元素是 。

A. ｃ B.ｄ C.ｂ D. ｅ

2．若某堆栈的输入序列是1，2，3，...，n，输出序列的第一个元素为n，则第i个输出元素为 。

A. i B. n-i C. n-i+1 D. 哪个元素无所谓 3．向一个栈顶指针为h的带头结点链栈中插入指针s所指的结点时，应执行 。 A. h->next = s; B. s->next = h;

C. s->next = h; h = h->next; D. s->next = h->next; h->next=s;

4．一个栈的入栈序列是 a，b，c，d，e，则栈的不可能的输出序列是 。 A. edcba B. decba C. dceab D. abcde 5．栈和队列的共同点是 。

A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点 6．对于循环队列 。

A. 无法判断队列是否为空 B. 无法判断队列是否为满 C. 队列不可能满 D. 以上说法都不是

7. 若用一个大小为6的数组来实现循环队列，且当前队尾指针rear和队头指针front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为 。

A. 1和5 B. 2和4 C. 4和2 D. 5和1 8. 判定一个循环队列 QU（最多元素为 m0）为满队列的条件是 。

A. QU->front==QU->rear B. QU->front!=QU->rear

C. QU->front==(QU->rear+1) % m0 D. QU->front!=(QU->rear+1) % m0 9.判定一个循环队列 QU（最多元素为 m0）为空的条件是 。

A. QU->front==QU->rear B. QU->front!=QU->rear

C. QU->front==(QU->rear+1) % m0 D. QU->front!=(QU->rear+1) % m0

BCDCCDACA 填空题

1．在求表达式值的算符优先算法中使用的主要数据结构是 。

2．设有一个空栈，现输入序列为1，2，3，4，5。经过push，push，pop，push，pop，push，pop，push后，输出序列是 。

3．仅允许在同一端进行插入和删除的线性表称为 。

7．在顺序栈s中，栈为空的条件是 ，栈为满的条件是_____。

4．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺

5

abcdefgh 图6-5 1 棵二叉树

9. 深度为 5 的二叉树至多有 个结点。 A. 16 B. 32 C.31 D.10

10. 设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数至少有 个。

A.k+1 B.2k C.2k-1 D.2k+1

11. 对含有 B 个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。

A.0 B.1 C.2 D.不存在这样的二叉树

1-5 ACDBB 6-10 填空题

1. 有一棵树如图6-7 所示，回答下面的问题：

k1DDCCC

k2k3k4k5k6k7 图6-7 1 棵二叉树

（1）这棵树的根结点是 ； （2）这棵树的叶子结点是 ； （3）结点 k3 的度是 ； （4）这棵树的度为 ；

11

（5）这棵树的深度是 ； （6）结点 k3 的孩子是 ； （7）结点 k3 的双亲结点是 。

2. 深度为 k 的完全二叉树至少有 个结点，至多有 个结点，若按自上而下，从左到右次序给结点编号（从 1 开始），则编号最小的叶子结点的编号是 。 答：①2

k?1

②2-1 ③2

kk?2+1

3. 一棵二叉树的第 i（i≥1）层最多有 个结点；一棵有 n（n>0）个结点的满二叉树共有 个叶子和 个非终端结点。 答：① 2

4. 具有n个结点的完全二叉树的深度为 。

5. 哈夫曼树是带权路径度_______的树，通常权值较大的结点离根_______。 ①最短 ②较近

6．在________遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。

1.答：① k1 ② k2 k5 k7 k4 ③ 2 ④ 3 ⑤ 4 ⑥ k5，k6 ⑦ k1 2. ① ② ③ 3. ① ② ③ 4.floor(log2n)+1 5. ① ② 6. 先根

例题解析

【例6-1】由如图 6-1 所示的二叉树，回答以下问题。 （1）其中序遍历序列为 ① ； （2）其前序遍历序列为 ② ； （3）其后序遍历序列为 ③ ；

（4）该二叉树的中序线索二叉树为 ④ ； （5）该二叉树的后序线索二叉树为 ⑤ ； （6）该二叉树对应的森林是 ⑥ 。

i?1 ②

2?logn? ③ 2?logn??1

12

abcdgehfi 图6-1 1棵二叉树

解：

① 中序遍历序列为dgbaechif ② 前序遍历序列为abdgcefhi

③ 后序遍历序列为gdbeihfca ④ 该二叉树的中序线索二叉树如图 6.1.1(a)所示 ⑤ 该二叉树的后序线索二叉树如图6-1-1 (b)所示 ⑥ 该二叉树对应的森林如图6-1-2所示

图6-1-1 二叉树的中序线索二叉树和后序线索二叉树

agf

beddhi

图6-1-2 二叉树对应的森林

13

综合题

1．二叉树结点数值采用顺序存储结构，如表6-2所示。

表6-2 二叉树的顺序存储结构

1 e 2 a 3 f 4 5 d 6 7 g 8 9 10 11 12 13 14 15 16 17 18 19 20 c j h i b （1）画出二叉树表示；

（2）写出前序遍历，中序遍历和后序遍历的结果； （3）写出结点值 c 的父结点，其左、右孩子。 解：

（1）该二叉树如图 6-9 所示。

图 6-9 1棵二叉树

（2）本题二叉树的各种遍历结果如下：

前序遍历：eadcbjfghi 中序遍历：abcdjefhgi 后序遍历：bcjdahigfa

（3）c 的父结点为 d，左孩子为 j，没有右孩子。

2．有一份电文中共使用 5 个字符：a、b、c、d、e，它们的出现频率依次为 4、7、5、2、9，试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。

14

解：依题意，本题对应的哈夫曼树如图 6-15 所示。

各字符对应的哈夫曼编码如下： a：001 b：10 c：01 d：000 e：11

图6-15 一棵哈夫曼树

3．设给定权集 w={2，3，4，7，8，9}，试构造关于 w 的一棵哈夫曼树，并求其加权路径长度 WPL。

解：本题的哈夫曼树如图 6-16 所示。

15

图6-16 一棵哈夫曼树

其加权路径长度 WPL=7×2+8×2+4×3+2×4+3×4+9×2=80

4. 已知一棵二叉树的中序序列为 cbedahgijf，后序序列为cedbhjigfa，画出该二叉树的先序线索二叉树。

解：由后序序列的最后一个结点 a 可推出该二叉树的树根为 a，由中序序列可推出 a的左子树由 cbed 组成，右子树由 hgijf 组成，又由 cbed 在后序序列中的顺序可推出该子树的根结点为 b，其左子树只有一个结点 c，右子树由 ed 组成，显然这里的 e 是根结点，其右子树为结点 d，这样可得到根结点 a 的左子树的先序序列为：bcde；再依次推出右子树的先序序列为：fghij。因此该二叉树如图 6-17所示。

图 6-17 二叉树

设二叉树的先序线索链表如图 6-18所示。

16

图 6-18 二叉树的先序线索链表

第7章 图

单项选择题

1．在一个图中，所有顶点的度数之和等于所有边数的 倍。 A. 1/2 B. 1 C. 2 D. 4

2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 B 倍。 A. 1/2 B. 1 C. 2 D. 4 3．具有 4 个顶点的无向完全图有 条边。

A. 6 B. 12 C. 16 D. 20

4．具有 6 个顶点的无向图至少应有 条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8

5．在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 条边。 A. n B. n+1 C. n-1 D. n/2

6．对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是 。 A. n B. (n-1)2 C. n-1 D. n2

7．对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则所有邻接表中的结点总数是 。

17

A. e/2 B. e C. 2e D. n+e 8．已知一有向图的邻接表存储结构如图 7-2 所示。

（1）根据有向图的深度优先遍历算法，从顶点 v1 出发，所得到的顶点序列是 。 A. v1，v2，v3，v5，v4 B. v1，v2，v3，v4，v5 C. v1，v3，v4，v5，v2 D. v1，v4，v3，v5，v2

（2）根据有向图的广度优先遍历算法，从顶点 v1 出发，所得到的顶点序列是 。 A. v1，v2，v3，v4，v5 B. v1，v3，v2，v4，v5 C. v1，v2，v3，v5，v4 D. v1，v4，v3，v5，v2

123452445324

图7-2一个有向图的邻接表存储结构

9. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用 。 A. 求关键路径的方法 B. 求最短路径的 Dijkstra 方法 C. 广度优先遍历算法 D. 深度优先遍历算法

1-5.CBAAC 6-9 DCCBD

填空题

1．n 个顶点的连通图至少 条边。

2．在无向图 G 的邻接矩阵 A 中，若 A[i][j]等于 1，则 A[j][i]等于 。 3．已知图G的邻接表如图 7-3 所示，其从顶点 v1 出发的深度优先搜索序列为 ，其从顶点 v1 出发的广度优先搜索序列为 。

18

v1v2v3v4v5v6v2v3v6v5v5v4v4v6v3

图7-3 G的邻接表

4．设x,y是图G中的两顶点，则（x,y）与（y,x）被认为______边，但与是______的两条弧。答：①无向，②有向

5.已知一个图的邻接矩阵表示，删除所有从第 i 个结点出发的边的方法是 。 6．在有向图的邻接矩阵上，由第i行可得到第______个结点的出度，而由第j列可得到第___ ____个结点的入度。①i ②j

7. 在无向图中，如果从顶点v到顶点v’有路径，则称v和v’是______的。如果对于图中的任意两个顶点vi,vj∈V，且vi和vj都是连通的，则称G为______。①连通，②连通图 1. n-1 2. 1

3. 答：① v1，v2，v3，v6，v5，v4 ② v1，v2，v5，v4，v3，v6 4. ① ②

5. 将矩阵第 i 行全部置为 0 5. ① ② 6. ① ②

例题解析

【例7-1】对m个顶点的无向图G，采用邻接矩阵，如何判别下列有关问题： （1） 图中有多少条边？

（2） 任意两个顶点i和j是否有边相连？

19

（3） 任意一个顶点的度是多少？ 解：

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

⑵当A[ i,j ]≠0时，表示两顶点i,j之间有边相连。 ⑶计算邻接矩阵上顶点对应行上非零元素的个数。

综合题

1．给出如图 7-4 所示的无向图G的邻接矩阵和邻接表两种存储结构。

图7-4 无向图G

解：图 G 对应的邻接矩阵和邻接表两种存储结构分别如图所示。

2．用广度优先搜索和深度优先搜索对如图 7-5 所示的图 G 进行遍历（从顶点1出发），给出遍历序列。

解：搜索本题图的广度优先搜索的序列为：1，2，3，6，4，5，8，7，深度优先搜索的序列为：1，2，6，4，5，7，8，3。

20

12365847 图7-5无向图G

3．使用普里姆算法构造出如图 7-6 所示的图 G 的一棵最小生成树。1652155432364566 图7-6无向图G

解：使用普里姆算法构造棵最小生成树的过程如图 7-11所示。

21

11136(a)115346(b)34111346(c)1153354642242242(d)(e)

图 7-11 普里姆算法构造最小生成树的过程

4．使用克鲁斯卡尔算法构造出如图 7-7 所示的图 G 的一棵最小生成树。

16776425202351541812810253

图7-7 无向图G

解：使用克鲁斯卡尔算法构造棵最小生成树的过程如图 7-12所示。

22

1256374125346(a)(b)6(c)16742583764112525836(d)464(e)16181245825376(f)4

图 7-12 克鲁斯卡尔算法构造最小生成树的过程

第8章 查找

单项选择题

1.顺序查找法适合于存储结构为 的线性表。 A. 散列存储 B. 顺序存储或链接存储 C. 压缩存储 C. 索引存储

2.对线性表进行折半查找时，要求线性表的存储方式是 。 A. 顺序存储 B. 链接存储

C. 以关键字有序排序的顺序存储 D. 以关键字有序排序的链接存储

3.对有 18 个元素的有序表作二分（折半）查找，则查找A[3]的比较序列的下标为 。 A. 1.2.3 B. 9.5.2.3 C. 9.5.3 D. 9.4.2.3

4.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用 查找方法。

23

A. 分块 B. 顺序 C. 二分 D. 散列

5.有一个有序表为{2，5，7，11，22，45，49，62，71，77，90，93，120}，当折半查找值为 90 的结点时，经过 次比较后查找成功。 A. 1 B. 2 C. 4 D. 8

6.设哈希表长 m=14，哈希函数 H(key)=key % 11。表中已有 4 个结点：addr(14)=3， addr(38)=5，addr(61)=6，addr(85)=8，其余地址为空，如用线性探测再散列处理冲突，关键字为 49 的结点的地址是 。

A. 7 B. 3 C. 5 D. 4

7.在采用链接法处理冲突的开散列表上，假定装填因子a 的值为 4，则查找任一元素的平均查找长度为 。

A. 3 B.3.5 C.4 D.2.5 1-4 BCDA 5-7CAA 填空题

1.在各种查找方法中，平均查找长度与结点个数 n 无关的查法方法是 。 2.二分查找的存储结构仅限于 。

3.在散列存储中，装填因子α的值越大，则 ；α的值越小，则 。 ① 存取元素时发生冲突的可能性就越大 ② 存取元素时发生冲突的可能性就越小 4.对于二叉排序树的查找，若根结点元素的键值大于被查元素的键值，则应该在二叉树的___________上继续查找。

5.高度为8的平衡二叉树至少有_______个结点。 6. 在散列函数 H(key)=key % p 中，p 应取 。

1. 散列表查找

2. 有序的顺序存储结构 3. ① ② 4. 左子树 5. 54 6. 素数

例题解析

【例8-1】设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H(key)=key % 13 ,采用开放地址法的二次探测再散列方法解决冲突，试在 0～18 的散列地址空间中对该关键字序列构造哈希表。

解：依题意，m=19，二次探测再散列的下一地址计算公式为：

d1=H(key)

d2j=( d1+j*j) % m

24

d2j?1=( d1-j*j) % m； j=1，2，... 其计算函数如下：

H(19)=19 % 13=6 H(01)=01 % 13=1 H(23)=23 % 13=10 H(14)=14 % 13=1 (冲突) H(14)=(1+1*1) % 19=2 H(55)=55 % 13=3 H(20)=20 % 13=7 H(84)=84 % 13=6 (冲突) H(84)=(6+1*1) % 19=7 (仍冲突) H(84)=(6-1*1) % 19=5 H(27)=27 % 13=1 (冲突)

H(27)=(1+1*1) % 19=2 (冲突) H(27)=(1-1) % 19=0 H(68)=68 % 13=3 (冲突) H(68)=(3+1*1) % 19=4 H(11)=11 % 13=11 H(10)=10 % 13=10 (冲突) H(10)=(10+1*1) % 19=11 (仍冲突) H(10)=(10-1*1) % 19=9 H(77)=77 % 13=12

因此：各关键字的记录对应的地址分配如下： addr(27)=0

addr(01)=1 addr(14)=2 addr(55)=3 addr(68)=4 addr(84)=5 addr(19)=6 addr(20)=7 addr(10)=9 addr(23)=10 addr(11)=11 addr(77)=12

其他地址为空。

25

综合题

1.设散列表为 T［0..12］，散列函数为 H（key）= key，给定键值序列是｛39，36，28，38，44，15，42，12，06，25｝，请画出分别用拉链法和线性探查法处理冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和查找失败时的平均查找长度。 解 用散列函数 H（key）= key% 13计算出键值序列的散列地址。并用探查次数表示待查键值需对散列表中键值比较次数。

键值序列：｛39，36，28，38，44，15，42，12，06，25｝ 散列地址： 0，10，2，12，5，2，3，12，6，12 （1）线性探查法处理冲突

用线性探查法处理冲突构造的散列表见表8-1所示。

表8-1 用线性探查法处理冲突构造的散列表

下标 T［0..12］ 查找成功探查次数 查找失败探查次数

0 1 9

1 3 8

2 1 7

3 2 6

4 2 5

5 1 4

6 1 3

7 9 2

8 1

9 1

10 11 12 36 1 2

1

38 1 10

39 12 28 15 42 44 06 25

在等概率的情况下，查找成功的平均查找长度 ASL=（1×6+2×2+3×1+9×1）/10=2.2

设待查键值 k不在散列表中：若 H（k）= k% 13= d，则从 i=d开始顺次与 T［i］位置的键值进行比较，直到遇到空位，才确定其查找失败，同时累计 k键值的比较次数，例如若 k% 13= 0，则必须将 k与 T［0］、T［1］、?、T［8］中的键值进行比较之后，发现 T［8］为空，比较次数为 9、类似地可对 k% 13=1，2，3，?，12进行分析可得查找失败的平均查找长度。

ASL =（9+8+7+6+5+4+3+2+1+1+10）/13 = 59/13 = 4.54 （2）拉链法处理冲突

用拉链法处理冲突构造的散列表见图8-2所示。

26

图8-2 拉链法处理冲突构造的散列表

在等概率的情况下查找成功的平均查找长度： ASL=（1×7+2×2+3×1）/10=1.4

设待查键值 k不在散列表中，若 k% 13= d。则需在 d链表中查找键值为 k的结点，直到表尾，若不存在则查找失败，设 d链表中有 i个结点，则 k需与表中键值比较 i次，查找失败的平均长度为：

ASL=（1+ 0+ 2+ 1+ 0+ 1+ 1+ 0+0+0+1+0+3）/13=10/13 = 0.77

2.线性表的关键字集合{87，25，310，08，27，132，68，95，187，123，70，63，7}，共有 13 个元素，已知散列函数为：H(k) = k % 13 ，采用拉链法处理冲突。设计出这种链表结构，并计算该表的成功查找的平均查找长度。 解：依题意，得到：

H(87)=87 % 13=9 H(25)=25 % 13=12 H(310)=310 % 13=11 H(08)=08 % 13=8 H(27)=27 % 13=1 H(132)=132 % 13=2 H(68)=68 % 13=3 H(95)=95 % 13=4 H(187)=187 % 13=5 H(123)=123 % 13=6 H(70)=70 % 13=5 H(63)=63 % 13=11

27

H(47)=47 % 13=8

采用拉链法处理冲突的链接表如图8-3 所示。成功查找的平均查找长度： ASL=(1×10+2×3)/13=16/13=1

313 0 1 27 ^ 2 132 ^ 3 68 ^ 4 95 ^ 5 70 187 ^ 6 123 ^ 7 8 08 47 ^ 9 87 ^ 10

11 63 310 ^ 12

25 ^ 图8.3 处理冲突的链接表

28

第9章 排序

单项选择题

1.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序

2.设有 10000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素，排序方法最好选用 。

A. 起泡排序 B. 快速排序 C. 堆排序 D. 基数排序

3.在待排序的元素序列基本有序的前提下，效率最高的排序方法是 。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序

4.一组记录的排序码为(46，79，56，38，40，84)，则利用堆排序的方法建立的初始堆为 。 A. 79，46，56，38，40，80 B. 84，79，56，38，40，46 C. 84，79，56，46，40，38 D. 84，56，79，40，46，38

5.在下列算法中， 算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。

A．堆排序 B．冒泡排序 C．插入排序 D.快速排序

6.一组记录的关键码为(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

7.一组记录的排序码为(48，16， 79，35，82，23，36，72)，按归并排序的方法对该序列进行一趟归并后的结果为 。

A. 16 48 35 79 23 82 36 72 B. 16 35 48 79 82 23 36 72 C. 16 48 35 79 82 23 36 72 D. 16 35 48 79 23 36 72 82

8.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序

9.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为 。

A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序

1-5 DCABC

29

6-9 CACD 填空题

1.在对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第 8 个记录 45 插入到有序表时，为寻找插入位置需比较 次。

2.对于关键字序列（12，13，11，18，60，15，7，20，25，100），用筛选法建堆，必须从键值为 的关键字开始。

3.对 n个记录的表 r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为 4.在插入和选择排序中，若初始数据基本正序，则选用 ；若初始数据基本反序则选用 。 插入排序 选择排序

5.对 n 个元素的序列进行起泡排序时，最少的比较次数是 。 6. 排序不需要进行记录关键字间的比较。 1. 5 2. 60 3. n(n-1)/2 4. ① ② 5. n-1 6. 基数

综合题

1.已知序列49．38，65，97，76，13，27，请给出采用起泡排序对该序列作升序排列的每一趟的结果。

2.已知序列{503，87，512，61，908，170，897，275，653，462}，采用快速排序法对该序列作升序排序时的每一趟的结果。

3.已知序列{265，301，751，129，937，863，742，694，076，438}，采用基数排序法对该序列作升序排序时的每一趟的结果。

4.已知序列{503，17，512，908，170，897，275，653，426，154，509，612，677，765，703，94}，请给出采用希尔排序法(d1=8)对该序列作升序排序时的每一趟的结果。 5.已知序列{35，89，61，135，78，29，50}，请给出采用插入排序法对该序列作升序排序时的每一趟的结果。

6.已知序列{11，18，4，3，6，15，1，9，18，8}，请给出采用归并排序法对该序列作升序排序时的每一趟的结果。

1.解：根据起泡排序法的基本思想，比较无序区中相邻关键字。按照大小关系调整其位置，本题的解法是，通过比较已知序列中相邻关键字，并根据需要调整其位置、重复此过程直到没有关键字的位置交换为止，结果正好是关键字的升序排列。

30

依题意，采用起泡排序法排序的各趟的结果如下： 初始：49，38、65，97，76，13，27 第一趟；38，49，65，76，13，27，97 第二趟：38，49，65，13，27，76，97 第二趟：38，49．13，27，65，76，97 第四趟：38，13，27，49，65，76，97

第五趟：13，27，38，49，65．76，97 第六趟：13，27，38，49，65，76，97 第六题无元素交换，排序结束。

2.依题意，采用快速排序法排序的各趟的结果如下：

初始：503，87，512，61，908，170，897，275，653，462 第 1 趟：[462，87，275，61，170] 503 [897，908，653，512] 第 2 趟：[170，87，275，61] 462，503 [897，908，653，512] 第 3 趟：[61，87] 170 [275] 462，503 [897，908，653，512] 第 4 趟：61 [87] 170 [275] 462，503 [897，908，653，512] 第 5 趟：61，87，170 [275] 462，503 [897，908，653，512] 第 6 趟：61，87，170，275，462，503 [897，908，653，512] 第 7 趟：61，87，170，275，462，503 [512，653] 897 [908] 第 8 趟：61，87，170，275，462，503，512 [653] 897 [908] 第 9 趟：61，87，170，275，462，503，512，653，897 [908] 第 10 趟：61，87，170，275，462，503，512，653，897，908 3.依题意，采用基数排序法排序的各趟的结果如下：

初始态：265 301 751 129 937 863 742 694 076 438

第一趟：[] [301 751] [742] [863] [694] [265] [076] [937] [438] [129] 第二趟：[301] [] [129] [937 438] [742] [751] [863 265] [076] [] [694] 第三趟：[075] [129] [265] [301] [438] [] [694] [742 751] [863] [937] 4.依题意，采用希尔排序法排序的各趟的结果如下：

初始：503，17，512，908，170，897，275，653，426，154，509，612，677，765，703，94

第 1 趟(d1=8)：426，17，509，612，170，765，275，94，503，154，512，908，677，897，703，653

第 2 趟(d2=4)：170，17，275，94，426，154，509，612，503，765，512，653，677，897，703，908

第 3 趟(d3=2)：170，17，275，94，426，154，503，612，509，653，512，765，677，897，703，908

第 4 趟(d1=1)：17，94，154，170，275，426，503，509，512，612，653，677，703，765，897，908

5.依题意，采用直接插入排序法排序的各趟的结果如下

初始：(35)89，61，135，78，29，50

31

第一趟：（35，89，)6l，135，78，29，50 第二趟：(35，61，89，)135，78，29，50 第三趟：(35，6l，89，135)78，29，50 第四趟：(35，61，78，89，135)29，50 第五趟：(29，35，61，78，89．135)50 第六趟：(29，35，50，61，78，89，135)

依题意，采用归并排序法排序的各趟的结果如下：

初始：11，18，4，3，6，15，1，9，18，8

第 1 趟：[11，18] [3，4] [6，15] [1，9] [8，18] 第 2 趟：[3，4，11，18] [1，6，9，15] [8，18] 第 3 趟：[3，4，11，18] [1，6，8，9，15，18] 第 4 趟：[1，3，4，6，8，9，11，12，18，18] 第 4 趟归并完毕，则排序结束。

32

6.

本文来源：https://www.bwwdw.com/article/84go.html