第八章排序：习题
习 题
一、选择题
1．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。
A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序
2．设有1000个无序的记录，希望用最快的速度挑选出其中前10个最大的记录，最好选用( )排序法。
A.冒泡排序 B.快速排序 C.堆排序 D.基数排序
3．在待排序的记录序列基本有序的前提下，效率最高的排序方法是( )。
A.插入排序 B.选择排序 C.快速排序 D.归并排序’
4．不稳定的排序方法是指在排序中，关键字值相等的不同记录的前后相对位置( )。
A.保持不变 B.保持相反 C.不定 D.无关
5．内部排序是指在排序的整个过程中，全部数据都在计算机的( )中完成的排序。
A. 内存储器 B.外存储器
C.内存储器和外存储器 D.寄存器
6．用冒泡排序的方法对n个数据进行排序，第一趟共比较( )对记录。
A.1 B.2 C.n-l D.n
7．直接插入排序的方法是从第( )个记录开始，插入前边适当位置的排序方法。
A.1 B.2 C.3 D.n
8．用堆排序的方法对n个数据进行排序，首先将n个记录分成( )组。
A.1 B.2 C.n-l D.n
9．归并排序的方法对n个数据进行排序，首先将n个记录分成( )组，两两归并。
A.1 B.2 C.n-l D.n
10．直接插入排序的方法要求被排序的数据( )存储。
A.必须是顺序 B.必须是链表 C.顺序或链表 D.二叉树
习题八 查找
一、单项选择题
1．顺序查找法适合于存储结构为（ ）的线性表。
A． 散列存储 B. 顺序存储或链式存储
C. 压缩存储 D. 索引存储
2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。
A． (n-1)/2 B. n/2 C. (n+1)/2 D. n
3．适用于折半查找的表的存储方式及元素排列要求为( )
A．链接方式存储，元素无序 B．链接方式存储，元素有序
C．顺序方式存储，元素无序 D．顺序方式存储，元素有序
4．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )
A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减
5．当采用分块查找时，数据的组织方式为 ( )
A．数据分成若干块，每块内数据有序
B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D. 数据分成若干块，每块（除最后一块外）中数据个数需相同
6．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（ ）。
A．正确 B. 错误
7. 二叉查找树的查找效率与二叉树的(（1） )有关, 在 (（2） )时其查找效率最低。
(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置
1、用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。( )
2、有e条边的无向图，在邻接表中有e个结点。（ ）3、强连通图的各顶点间均可达。
4、无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（ ）
5、一个网（带权图）都有唯一的最小生成树。( )
6、最小生成树问题是构造连通网的最小代价生成树。( )
7、关键路径是AOE网中从源点到终点的最长路径。（ ）
8、在AOE图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。
9、n个顶点的完全有向图的边数为n(n-1)。（ ）
10、稀疏图的存储结构采用邻接表比较合适。（ ）
11、在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。
1．具有4个顶点的无向完全图有（ ）条边。
A．6 B．12 C．16 D．20
2．下列哪一种图的邻接矩阵是对称矩阵？（ ）
A．有向图 B．无向图 C．AOV网 D．AOE网
3、在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。
A. O(n) B. O(n+e) C. O(n2) D. O(n3)
4、(1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；
(2). 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3) ；（图用邻接矩阵表示）
(3). Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。
上面不正确的是（ ）。
A．(1),(2),(3) B．(1) C．(1),(3) D．(2),(3)
数据结构--内部排序算法
1、下列排序算法中，_____________排序在某趟结束后不一定能选出一个元素放到其最终的位置上。
（1）选择 （2）冒泡 （3）归并 （4）堆
2、下列排序算法中，依次将待排序列中的元素和前面有序序列合并为一个新的有序序列的排序算法是___________________。
（1）直接插入排序 （2）冒泡排序 (3)快速排序 （4）直接选择排序
3、下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是______________。
（1）直接插入排序列 （2）快速排序 （3）直接选择排序 （4）堆排序
4、依次将待排序序列中的元素和有序子序列合并一个新的有序子序列的算法是______________。
（1）快速排序 （2）插入排序 （3）冒泡排序 （4）堆排序
5、已知数据表A中每个元素距其最终位置不远，则采用_____________排序算法最节省时间。
（1）堆排序 （2）插入排序 （3）快速排序 （4）直接选择排序
6、下列排序算法中，_______________算法可能会出现下面情况，在最后一趟开始之前，所有元素都不在其最终的位置上。
（1）堆排序 （2）冒泡排序 （3）快速排序 （4）插入排序
7、数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用____________排序算法最节省时间。
（1）堆排序 （2）希尔排序 （3）快速排序 （4）直接选择排序
8、下列算法中，____________每一趟都能选出一个元素放在其最终位置上，并且是不稳定的。
（1）冒泡排序 （2）希尔排序 （3）直接选择排序列 （4）直接插入排序
9、下列排序算法中，某一趟结束后未必能选出一个元素放在其最位置上的是__________________。
