数据结构课件题目（附答案） - 图文

… 第一章

1.算法的计算量的大小称为计算的（ B ）。 A. 效率 B. 复杂性 C. 现实性 D. 难度 2.一个算法应该是（ B ）。

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 3．下面说法错误的是（ A ）

(1）算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 4.在数据结构中，从逻辑上可以将之分为( D )。

A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 内部结构和外部结构 D. 线性结构和非线性结构 5.计算算法的时间复杂度是属于一种( B )。

A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法 6.可以用( D )定义一个完整的数据结构:

A. 数据元素 B. 数据对象 C. 数据关系 D. 抽象数据类型 7.算法分析的目的是___C____。

A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 8.设计一个―好‖的算法应考虑达到的目标有___BCD___。

A. 是可行的 B. 是健壮的 C. 无二义性 D. 可读性好

第二章

1.线性表是具有n个（ C ）的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项 E．信息项

2.若线性表最常用的操作是存取第I个元素及其前驱和后继元素的值，为节省时间应采用的存储方式( A )。

A.单链表 B.双向链表 C.单循环链表 D.顺序表

3.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

A. 单链表 B. 仅有头指针的单循环链表 C. 双链表 D. 仅有尾指针的单循环链表 4.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( A )最节省时间。 A. 带头结点的双循环链表 B. 单循环链表 C. 带尾指针的单循环链表 D. 单链表 5.静态链表中指针表示的是( C )

A.下一元素的地址 B.内存储器的地址

C.下一元素在数组中的位置 D.左链或右链指向的元素的地址 6.下述哪一条是顺序存储结构的优点？（ C ）

A．插入运算方便 B．可方便地用于各种逻辑结构的存储表示

…

C．存储密度大 D．删除运算方便

7.下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元 B．线性表采用顺序存储，便于进行插入和删除操作 C．线性表采用链接存储，不必占用一片连续的存储单元 D．线性表采用链接存储，便于插入和删除操作。

8.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 9.链表不具有的特点是（ B ）

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

10.(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。

(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是（ B ）

A.(1),(2) B.(1) C.(1),(2),(3) D.(2)

11.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。 A. O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 12.单链表中，增加一个头结点的目的是为了( C ）。

A．使单链表至少有一个结点 B．标识表结点中首结点的位置 C．方便运算的实现 D．说明单链表是线性表的链式存储

13.对于双向循环链表,在p指针所指的结点之后插入s指针所指结点的操作应为（ D ）。 A． p->right=s ; s->left=p; p->right->left=s ; s->right=p->right; B． p->right=s ; p->right->left=s ; s->left=p; s->right=p->right; C． s->left=p; s->right=p->right; p->right=s ; p->right->left=s ; ; D． s->left=p; s->right=p->right; p->right->left=s ; p->right=s ;

14.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ B ） A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL

第三章 无 第四章

1.下面关于串的的叙述中，哪一个是不正确的？（B）

A．串是字符的有限序列 B．空串是由空格构成的串

C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2.串是一种特殊的线性表，下面哪个叙述体现了这种特殊性？（A） A. 数据元素是一个字符 B. 可以顺序存储 C. 数据元素可以是多个字符 D. 可以链接存储 3.串的长度是指（ B ）

A．串中所含不同字母的个数 B．串中所含字符的个数

…

C．串中所含不同字符的个数 D．串中所含非空格字符的个数

4.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（ C ）。 A．2n-1 B．n C．(n/2)+(n/2) D．(n/2)+(n/2)-1 E. (n/2)-(n/2)-1 F. 其他情况

2222第五章

1.数组是同类型值的集合。（F ）

2.从逻辑结构上看，n维数组的每个元素均属于n个向量。（ T ）

3.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ F ）

第六章

1.n(n>0)个结点的树的高度:最低是多少？(2)最高是多少？(n) 2.n(n>0)个结点的二叉树的高度:最低是多少？最高是多少？ 3.有关二叉树下列说法正确的是（ B ）

A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 4.一棵124个叶结点的完全二叉树，最多有( C )个结点。 A.247 B.248 C.249; D.250; E.251

5.已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( C )。 A. 311 B. 312 C. 313 D. 314 E. 其它 6.一个具有1025个结点的二叉树的高h为（ C ）

A．11 B．10 C．11至1025之间 D．10至1024之间 7.一棵树高为K的完全二叉树至少有（ C ）个结点

A. 2 –1 B. 2 –1 C. 2-1 D. 2

8.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有___12___个叶子结点。

9.已知二叉树的 先序序列ABDFCEHG中序序列DBFAHECG请构造该二叉树。

10.已知二叉树的后序序列DMFBHELGCA 中序序列DBMFAHECGL请构造该二叉树。 11.一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。 先序序列为：_ _ C D E _ G H I _ K 中序序列为：C B _ _ F A _ J K I G

后序序列为： _ E F D B _ J I H _ A 12.试找出满足下列条件的二叉树 1）先序序列与后序序列相同 2）中序序列与后序序列相同 3）先序序列与中序序列相同

4）中序序列与层次遍历序列相同

13.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ B ）。

A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEGB

KK?1KK

…

14.一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足( C )。 A. 其中任意一个结点均无左孩子 B. 其中任意一个结点均无右孩子 C. 其中只有一个叶子结点 D. 其中度为2的结点最多为一个

15.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是( B )的二叉树 A．空或只有一个结点 B. 高度等于其结点数 C．任一结点无左孩子 D. 任一结点无右孩子 16.二叉树在线索化后，仍不能有效求解的问题是（D ）。

A. 先序线索二叉树中求先序后继 B. 中序线索二叉树中求中序后继 C. 中序线索二叉树中求中序前驱 D. 后序线索二叉树中求后序后继 17.引入二叉线索树的目的是（ A ）

A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一

18.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( C ) A. X的双亲 B. X的右子树中最左的结点 C. X的左子树中最右结点 D. X的左子树中最右叶结点

19.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( B )。 A. 0 B. 1 C. 2 D. 不确定 20.将树转换成二叉树 AA

B C D B C E F GHI J

EG D F K L AH J K 树转换成的二叉树其右子树一定为空 L I GB21.森林转为二叉树

JCHA G J K B C D H I DIEK F L M N E LF 22.已知一个森林的先序序列和后序序列如下，请构造出该森林。 先序序列：ABCDEFGHIJKLMNO M后序序列：CDEBFHIJGAMLONK 解：森林的前序序列和后序序列对应其转换的二叉树的前序序列和中序序列，应先据此构造N二叉树，再构造出森林

23.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别

…

为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是 （ D )。

A．M1 B．M1+M2 C．M3 D．M2+M3

24.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ C ）个。

A．n-1 B．n C．n+1 D．n+2 25.设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是( D )。

A. 在树T中，X是其双亲的第一个孩子 B. 在树T中，X一定无右边兄弟 C. 在树T中，X一定是叶子结点 D. 在树T中，X一定有左边兄弟 26.设树形T在后根次序下的结点排列和各结点相应的次数如： 后根次序：ＢＤＥＦＣＧＪＫＩＬＨＡ 次 数：００００３０００２０２４ 请画出Ｔ的树形结构图。

27.给定权值7，6，3，32，5，26，12，9，构造相应的哈夫曼树，并计算其带权路径长度。为使结果答案唯一，请用左结点的值小于等于右结点的值来构造哈夫曼树。

第七章

1.图中有关路径的定义是（ A ）。

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2.设无向图的顶点个数为n，则该图最多有（ B ）条边。

A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0 E．n

3.一个有n个结点的图，最少有（ B ）个连通分量，最多有（ D ）个连通分量。 A．0 B．1 C．n-1 D．n 4.要连通具有n个顶点的有向图，至少需要（b）条边。

A．n-l B．n C．n+l D．2n

5.G是一个非连通无向图，共有28条边，则该图至少有____9__个顶点。

6.用邻接表存储图所用的空间大小 A 。

A.与图的顶点数和边数都有关 B.只与图的边数有关 C.只与图的顶点数有关 D.与边数的平方有关 7.图G是n个顶点的无向完全图，则下列说法正确的有：BCD A. G的邻接多重表需要n(n-1)个边结点和n个顶点结点； B. G的连通分量个数最少； C. G为连通图； D. G所有顶点的度的总和为n(n-1);

8.在有向图的邻接表存储结构中，顶点v在链表中出现的次数是( B )。

A. 顶点v的度 B. 顶点v的出度 C. 顶点v的入度 D. 依附于顶点v的边数 8.图的遍历举例

(1)假定以邻接表存储，邻接点按编号升序排列。遍历序列如下：

2

…

深度优先搜索：

V1->V2->V4->V8->V5->V6->v3->v7 广度优先搜索

V1->V2->V3->V4->v5->v6->v7->v8

(2)已知邻接矩阵求遍历序列 深度优先搜索： ?01110?V1->V2->V3->V4->V5 ?00000??? ?00010?宽度优先搜索： ??01000?V1->V2->V3->V4->V5 ??01100???

(3)已知邻接表求遍历序列

深度优先遍历：V1->V2->V3->V6->V5->V4 宽度优先遍历：V1->V2->V5->V4->V3->V6

9.深度优先(广度优先)生成树 v1 v2 v3 v4 v5 v6 10.最小生成树

1 0 1 0 0 1 3 2 4 4 2 2 6 v1 v2 v3 v4 v5 v6 v7 v8 0 1

V1 V ∧ 2 V V ∧ 3

V3456V2 ① ⑤ 1 2 5 ∧ 4 4 ∧ 3∧ 3 5 2 ∧ 4 ∧ 5 ∧ 5 ∧ 3 4 ∧ 5 ∧ v1 19 16 21 11 v2 6 v1 v2 ④ ② 33 v6 14 v3 5 v6 v5 v4 ③ v3 v5 18 v4

…

11.试画出从顶点v1开始利用Prim算法得到的最小生成树

8 V2 V3 112510?????12 1 1?89???V1 ?128??2?9 2 10 5 ??59??4?? V4 V5 ?10??24???4

12.利用Kruskal算法求最小生成树

11

14

41 232232

454 538 4438 33 2256 6656

45 457 7

…

13.用DAG图描述((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e) 14.AOV-网的拓扑排序 v2 v2

表

达

式+ * * * + e * v5 + v1 v3 v5 v1 v3 a d b c vv6 4 v6 v4

15.写出有向图的所有拓扑排序，并指出应用教材中的算法求得的是哪个序列，设邻接表的边表结点中的邻接点序号是递增的。

1 100 10 V016.求最短路径 V1 30 V2V32 5 10 50 60 V5V4

3 4 20 V6 17.求最短路径－Floyd算法

18.设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ D ）

aa e b d f c a c f d e b a e d f c b a e f d c b a e f d b c

A．5个 B．4个 C．3个 D．2个

bec19.下面哪一方法可以判断出一个有向图是否有环（回路）：（AB） A. 深度优先遍历 B. 拓扑排序C. 求最短路径 D. 求关键路径 df

…

20.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ D ）。

A．G中有弧 B．G中有一条从Vi到Vj的路径 C．G中没有弧 D．G中有一条从Vj到Vi的路径 21.关键路径是AOE网中( B )

A. 从始点到终点的最短路径 B. 从始点到终点的最长路径

C. 从始点到终点的边数最多的路径 D. 从始点到终点的边数最少的路径 22.下列关于AOE网的叙述中，不正确的是（ B ）。 A．关键活动不按期完成就会影响整个工程的完成时间

B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动若提前完成，那么整个工程将会提前完成 23.下列有关图的说法错误的是（ C ）

A. 在有向图中，出度为0的结点4称为叶子。

B. 用邻接矩阵表示图，容易判断任意两个结点之间是否有边相连，并求得各结点的度。 C. 按深度方向遍历图和先根次序遍历树类似，得到的结果是唯一的。

D. 若有向图G中从结点Vi到结点Vj有一条路径，则在图G的结点的线性序列中结点Vi必在结点Vj之前的话，则称为一个拓扑序列。

第八章

1.地址为(1664)10大小为(128)10的存储块的伙伴地址是什么？buddy(1664,7)=1664-2=1536 2.地址为(2816)10大小为(64)10的存储块的伙伴地址是什么？buddy(2816,6)=2816+2=2880 3.已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23，45，52，100，11和19的存储空间，然后再顺序释放大小为45，52，11的占用块。假设以伙伴系统实现动态存储管理。

（1） 画出可利用空间表的初始状态。

（2） 画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。

（3） 画出在回收3个占用块之后可利用空间表的状态。

67第九章

1.画出含有12个元素的有序表的判定树

（1）求查找成功时的平均查找长度（2）求查找失败时的平均查找长度

2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( C )。

A. (n-1)/2 B. n/2 C. (n+1)/2 D. n

3.对线性表进行二分查找（就是折半查找）时，要求线性表必须（ ） A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序

4.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( C )

A. 必定快 B. 不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 5.在有序表A[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依

…

次是___1，3，6，8，11，13，16，19_______ 6.分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成___30______块最好：若分成25块，其平均查找长度为__31.5（块内顺序查找）_______。

7.设关键码序列为：63，90，70，55，67，42，98，83，则构造一棵二叉排序树的过程如下：

8.二叉排序树上删除10 或40或45或55

9.构造二叉排序树

将{for,case,while,switch,break,do,define,const,if,int}中的关键字依次插入初态为空的二叉排序树（按字母在字母表中的序号排序）中，请画出所得到的树T。然后画出删除for之后的二叉排序树T。

10.按关键字序列15,21,27,43,36,8,11构造平衡二叉树

…

11.构造平衡二叉树

给定表{25，18，48，07，76，52，81，70，92，15}，

按表中元素顺序构造一棵AVL树，并求其在等概率情况下查找成功的平均查找长度。 12.已知长度为11的表（xal,wan,wil,zol,yo,xul,yum,wen,wim,zi,yon）按表中元素顺序依次插入一棵初始为空的: (1) 二叉排序树;

(2) 平衡二叉排序树； (3) 最佳二叉排序树

分别求其在等概率的情况下查找成功的平均查找长度。

13.二叉查找树的查找效率与二叉树的( （1）C )有关, 在 (（2）C )时其查找效率最低 (1) A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2) A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

14.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C ) A.(100,80,90,60,120,110,130) B.(100,120,110,130,80,60,90) C.(100,60,80,90,120,110,130) D.(100,80,60,90,120,130,110)

15.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1,则应作( C ) 型调整以使其平衡。 A. LL B. LR C. RL D. RR

16.设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树中查到的序列？说明原因。

（1）51,250,501,390,320,340,382,363 （2）24,877,125,342,501,623,421,363

答：序列（2）不可能是二叉排序树中查到363的序列。查到501后，因363<501，后面应该出现小于501的数，但序列中出现了623，故不可能。 17.下面关于m阶B树说法正确的是( B )

①每个结点至少有两棵非空子树； ②树中每个结点至多有m一1个关键字;

③所有叶子在同一层上; ④当插入一个数据项引起B树结点分裂后，树长高一层。

A. ①②③ B. ②③ C. ②③④ D. ③ 18.下面关于B和B+树的叙述中，不正确的是( C )

A. B树和B+树都是平衡的多叉树。 B. B树和B+树都可用于文件的索引结构。 C. B树和B+树都能有效地支持顺序检索。 D. B树和B+树都能有效地支持随机检索。 19.一棵3阶B-树中含有2047个关键字，包括叶子结点层，该树的最大深度为( B )。

A. 11 B. 12 C. 13 D. 14 20.已知2棵2-3 B-树如下（省略外结点）： 对树（a）,请分别画出先后插入26，85两个新结点后的树形；

对树（b）,请分别画出先后删除53，37两个结点后的树形。

24 4545 2461 9053 90

50 1003 1230 3761 703375370

21.下面关于哈希(Hash，杂凑)查找的说法正确的是( C ) A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有哈希函数中最好的

100

…

C．不存在特别好与坏的哈希函数，要视情况而定

D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可

22.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( D )

A. k-1次 B. k次 C. k+1次 D. k（k+1）/2次

23.散列函数有一个共同的性质，即函数值应当以( D )取其值域的每个值。 A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 24.将10个元素散列到100000个单元的哈希表中，则（ C ）产生冲突。 A. 一定会 B. 一定不会 C. 仍可能会

第十章

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

希尔排序示例：请给出对一组记录（54,38,96,23,15,90,72,60,45,83）进行希尔排序（增量序列为5，3，1）时的排序过程。

冒泡排序示例：一组关键字（19,01,26,92,87,11,43,87,21），进行冒泡排序，试列出每一趟排序后的关键字序列 快速排序示例

对下列一组关键字（46,58,15,45,90,18,10,62）试写出快速排序的每一趟的排序结果 堆排序示例

已知一组关键字（46,58,15,45,90,18,10,62）试写出堆排序建的初始堆和排序的过程

2.已知8个记录，其关键字分别为 (179，208，306，093，859，984，271，033) 试用基数排序法实施排序，描述其排序过程

3.以关键码序列（503，087，512，061，908，170，897，275，653，246）为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：

（1）直接插入排序；（2）希尔排序（增量5，3，1）；（3）起泡排序 （4）快速排序；（5）简单选择排序（6）堆排序；（7）归并排序；（8）基数排序。 4.下列内部排序算法中：

A. 快速排序 B. 直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序 (1)其比较次数与序列初态无关的算法是( CD ) (2)不稳定的排序算法是( ADF )

(3)在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序，k<

(4)排序的平均时间复杂度为O(n?logn)的算法是( ACF ),为O(n?n)的算法是( BDE ) 5.设被排序的结点序列共有N个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为( C )。 A. O(N)， O(N)， O(N) B. O(N)， O(N*log2N), O(N*log2N) C. O(N)， O(N*log2N), O(N2) D. O(N2)，O(N*log2N), O(N2) 6.一个排序算法的时间复杂度与( B )有关。

A. 排序算法的稳定性 B. 所需比较关键字的次数C. 所采用的存诸结构 D. 所需辅助存诸空间的大小

7.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录

…

为基准得到的一次划分结果为( C )。

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) 8.有些排序算法在每趟排序过程中，都会有一个元素被放置在其最终的位置上，下列算法不会出现此情况的是( A )。

A. SHELL排序（希尔排序） B. 堆排序 C. 冒泡排序 D. 快速排序

9.在下列排序方法中，( D )方法可能出现这种情况：在最后一趟开始之前，所有的元素都不在其最终应在的正确位置上。

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

10.就分类算法所用的辅助空间而言，堆分类、快速分类和归并分类的关系是( A )。 A. 堆分类<快速分类<归并分类 B. 堆分类<归并分类<快速分类 C. 堆分类>归并分类>快速分类 D. 堆分类>快速分类>归并分类

11.设要将序列(q,h,c,y,p,a,m,s,r,d,f,x) 中的关键码按字母升序重新排序，

(1)( B )是初始步长为4的shell排序一趟扫描的结果； (2)( C )是对排序初始建堆的结果；

(3)( A )是以第一个元素为分界元素的快速一趟扫描的结果 从下面供选择的答案中选出正确答案填入括号内。 A.f,h,c,d,p,a,m,q,r,s,y,x B.p,a,c,s,q,d,f,x,r,h,m,y

C.a,d,c,r,f,q,m,s,y,p,h,x D.h,c,q,p,a,m,s,r,d, ,x,y E.h,q,c,y,a,p,m,s,d,r,f,x

12.基于比较方法的n个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是( A )。

A. O(nlogn) B. O(logn) C. O(n) D. O(n*n)

13.外部排序是把外存文件调入内存,可利用内部排序的方法进行排序,因此排序所花的时间取决于内部排序的时间。( F )

14.在外排序过程中，对长度为n的初始序列进行―置换—选择‖排序时，可以得到的最大初始有序段的长度不超过n/2。( F )

15.外排中使用置换选择排序的目的，是为了增加初始归并段的长度。T

16.在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？ 答：这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。对4，3，2，1气泡排序就可否定本题结论了。

17.设某文件经内排序后得到100个初始归并段(初始顺串),若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？

答：设归并路数为k，归并趟数为s，则s=[logk100]，因为[logk100]=3，因为k为整数，故k=5,即最少5-路归并可以完成排序。

18.设有11个长度(即包含记录的个数)不同的初始归并段，它们所包含的记录个数分别为25,40,16,38,77,64,53,88,9,48,98。试根据它们做4路平衡归并，要求：

(1)指出总的归并趟数； (3分)(2)构造最佳归并树； (8分) (3)根据最佳归并树计算每一趟及总的读记录数。(5分) 答：（1）三趟归并（2）最佳归并树图略。 （3）设每次读写一个记录。 第一趟50次读写 总的读写次数：5052

[(9+16)*3+(25+38+40)*2+(48+53+64+77)*2+(88+98)]*2

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