数据结构第七章习题答案

第七章排序课后习题解答一、单项选择题1．下列内部排序算法中：A．快速排序 B.直接插入排序C. 二路归并排序D. 简单选择排序E. 起泡排序F. 堆排序（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<<n）的情况下，排序效率最高的算法是（）（4）排序的平均时间复杂度为O(n•logn)的算法是（）为O(n•n)的算法是（）【解答】（1） DC （2）ADF （3）B （4）ACF BDE2．比较次数与排序的初始状态无关的排序方法是( )。

A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序【解答】D3．对一组数据（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. 插入【解答】A4．下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择B. 冒泡C. 归并D. 堆【解答】C5．一组记录的关键码为（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)【解答】C6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。

A．冒泡 B. 希尔 C. 快速 D. 堆【解答】C7. 就平均性能而言，目前最好的内排序方法是( )排序法。

A. 冒泡B. 希尔插入C. 交换D. 快速【解答】 D8. 下列排序算法中，占用辅助空间最多的是：( )A. 归并排序B. 快速排序C. 希尔排序D. 堆排序【解答】 A9. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。

第七章图
1．下面是一个图的邻接表结构，画出此图，并根据此存储结构和深度优先搜索算法写出从C开始的深度优先搜索序列。

1
2
3
4
5
【解答】
A B F
C D E
C开始的深度优先搜索序列：CDEABF（唯一的结果）
2．假定要在某县所辖六个镇（含县城）之间修公路，若镇I和镇J 之间有可能通过道路连接，则Wij表示这条路的长度。

要求每个镇都通公路且所修公路总里程最短，那么应选择哪些线路来修。

(1).画出该图。

(2).用C语言描述该图的数组表示法存储结构，并注明你所使用变量
的实际含义。

(3).图示你所定义的数据结构。

(4).标识出你选择的线路。

【解答】 （1）
（2）
#define MAX 6 typedef struct {
char vexs[MAX]; // 顶点信息 int arcs[MAX][MAX]; // 边的信息
int vexnum, arcnum; // 顶点数，边数 } MGraph; （3）略
（4）{(1,3), (3,4), (2,4), (4,5), (5,6)}
3．图G 如下所示。

(1).给出该图的所有强连通分量。

(2).在图中删除弧<2,1>，然后写出从顶点1开始的拓扑有序序列。

5
4
6
1
3
2
4
15 10
2
15
20
30
4
10
10
【解答】
(1) 共4个强连通分量：
(2) 1,3,2,6,5,4。

第7章 《图》习题参考答案一、单选题（每题1分，共16分）（ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。

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

A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。

A ．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有 条边。

A ．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有 条边。

A ．14 B. 28 C. 56 D. 112 （B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。

A ．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。

A ．栈 B. 队列 C. 树 D. 图 （）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ D ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2C. 0 4 2 3 1 6 5D. 0 1 2 34 6 5 （ D ）10. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（ A ）11. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是A ．0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 1 3 4 2 5 6D. 0 3 6 1 5 4 2⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡0100011101100001011010110011001000110010011011110A ．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3（A）12. 深度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（D）13. 广度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（A）14. 任何一个无向连通图的最小生成树A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）二、填空题（每空1分，共20分）1. 图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。

《数据结构（C语言版第2版）》（严蔚敏著）第七章练习题答案第7章查找1．选择题（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。

A．(n-1)/2B．n/2C．(n+1)/2D．n答案：C解释：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2。

（2）适用于折半查找的表的存储方式及元素排列要求为（）。

A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序答案：D解释：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

（3）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用()查找法。

A．顺序查找B．折半查找C．分块查找D．哈希查找答案：C解释：分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。

由于块内是无序的，故插入和删除比较容易，无需进行大量移动。

如果线性表既要快速查找又经常动态变化，则可采用分块查找。

（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。

若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。

A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50答案：A解释：表中共10个元素，第一次取⎣(1+10)/2⎦=5，与第五个元素20比较，58大于20，再取⎣(6+10)/2⎦=8，与第八个元素70比较，依次类推再与30、50比较，最终查找失败。

（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。

A．3B．4C．5D．6答案：B解释：22个记录的有序表，其折半查找的判定树深度为⎣log222⎦+1=5，且该判定树不是满二叉树，即查找失败时至多比较5次，至少比较4次。

（6）折半搜索与二叉排序树的时间性能（）。