数据结构习题与解析

第1-3章习题

一、选择题

1.若进栈序列为a，b，c，d，进栈过程中可以出栈，则 不可能是一个出栈序列。 A) a,d,c,b

B) b,c,d,a C) c,a,d,b D) c,d,b,a

6.设用一维数组A[1,…,n]来存储一个栈，令A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。当从栈中弹出一个元素时，变量T将变化为 。 A) T=T + 1 B) T=T – 1 C) T不变 D) T= n 7. 一个栈的入栈序列为a，b，c，d，e,则栈不可能的出栈序列是 。 A) e d c b a B) d e c b a C) d c e a b D) a b c d e 8.若语句S的执行时间为O(1),那么下列程序段的时间复杂度为 。

For(i = 0; i <= n ; i++)

For(j = 0; j <=n ;j++) s

A) O(n) B) O(n*n) C) O(n*log2n) D) O(n*i) 18.设计一个判断表达式中左右括号是否配对的算法，采用 数据结构最佳。 A) 队列

B) 堆栈 C) 二叉树 D) 链表

24.一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 A) 1，4，3，2 2，4，1

29.在一个单链表中，若要删除P结点的后续结点，则应执行 。

A) P->next = P->next->next B) p = P->next; P->next = P->next->next C) delete(P->next) D) p = P->next->next

30.在计算递归函数时，如不使用递归过程，则一般情况下必须借助于 数据结构。 A) 栈 B) 树 C) 双向队列 D) 广义表

B) 4，3，2，1 C) 1，2，3，4 D) 3，

1

41.下列叙述中，正确的是 。

A) 用指针的方式存储一棵有n个结点的二叉树最少需要n+1个指针 B) 不使用递归，也可以实现二叉树的前序、中序和后序遍历

C) 已知树的前序遍历并不能唯一确定一棵树，因为不知道树的根结点是哪一个 D) 任一棵树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间

50.以下有关数据结构的叙述，正确的是 。 A) 线性表的线性存储结构优于链式存储结构 个结点，深度为k的二叉树上有2k-1个结点

C) 二维数组是其数据元素为线性表的线性表 D) 栈的操作方式是先进先出

52.在一个单链表中，若要在指针P所指向的结点之后插入结点q，应执行的操作是 。 A) P->next=q

B) P->next=q; q->next=P->next->next C) q->next

B) 二叉树的第i层上有2i-1

= P->next; P->next:=q D)P->next=q; q->next=P->next

56.若进栈序列为3,5,7,9,进栈过程中可以出栈，则 不可能是一个出栈序列。 A) 7,5,3,9 B) 9,5,7,3 C) 9,7,5,3 D) 7,5,9,3

57.设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈，一个元素出栈后立即进入队列Q，若6个元素出队的顺序是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是 。 A) 4

B) 6 C) 3 D) 2

59.有6个元素按6,5,4,3,2,1的顺序进栈，以下序列中，不合法的出栈序列是 。 A) 3,4,6,5,2,1 B) 5,4,3,6,1,2 C) 2,3,1,4,5,6 D) 4,5,3,1,2,6

2

61.下面关于线性表的叙述中，错误的是 。

A) 线性表采用顺序存储，必须占用一片连续的存储单元 序存储，便于进行插入和删除操作

C) 线性表采用链式存储，不必占用一片连续的存储单元 D) 线性表采用链式存储，便于插入和删除操作。 62.下述 是顺序存储方式的优点。

A) 存储密度大 B) 插入运算方便 C) 删除运算方便 D) 可方便地用于各种逻辑结构的存储表示

64.向顺序栈中压入元素时，是 。

A) 先移动栈顶指针，后存入元素 B) 先存入元素，后移动栈顶指针 C) 谁先谁后无关紧要 D) 同时进行

65.在一个顺序存储的循环队列中，队首指针指向队首元素的 。 A) 前一个位置 置

67.栈和队列都是 。 A) 限制存取点的线性结构

B) 限制存取点的非线性结构 C) 顺序存储的

B) 后一个位置

C) 队首元素位置 D) 任意位

B) 线性表采用顺

线性结构 D) 链式存储的线性结构 68.用链表表示线性表的优点是 。

A) 便于随机存储 B) 花费的存储空间较顺序存储少 C) 便于插入和删除操作 D) 数据元素的物理顺序与逻辑顺序相同

69在一个具有n个单元的顺序栈中，假设以地址高端作为栈顶，以top作为栈顶指针，则当做退栈处理时，top的变化为 。 A) top不变 1

B) top = 0 C) top = top - 1 D) top = top +

3

72.以下 不是队列的基本运算。

A) 从队尾插入一个新元素 B) 从队列中删除第i个元素 C) 判断一个队列是否为空 D) 读取队头元素的值

74.在长度为n的顺序表中，向第i个元素(1 <= I <= n+1)之前插入一个新元素时，需向

后移 动 个元素。 A) n - i

B) n – i + 1 C) n – i - 1 D) i

80.对于一个线性表，若即要求能够进行较快的插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该 。

A) 以顺序方式存储 B) 以链接方式存储 C) 以散列方式存储 D) 可以上面任意一种方式存储

85.在数据结构中，从逻辑上可以把数据结构分为 。

A) 紧凑结构和非紧凑结构 B) 动态机构和静态结构 C) 内部结构和外部结构 D) 线性结构和非线性结构 87. 一维数组与线性表的区别是 。

A) 后者长度固定，前者长度可变 B) 两者长度均可变 C) 前者长度固定，后者长度可变

D) 两者长度均固定

108.下列有关数据的存储结构的叙述中，正确的是 。

A) 数据存储方式的优点是存储密度大，且插入和删除运算效率高 B) 链表的每个结点都恰好包含一个指针

C) 邻接表法只能用于有向图的存储，而相邻矩阵法对于有（无）向图的存储都适用

D) 队列的存储方式既可以是顺序方式，也可以是链接方式

4

二、填空题

4.设有二维数组A[0…9, 0…19]，其每个元素占两个字节，数组按列优先顺序存储，第一个元素的存储地址为100。那么元素a[6,6]的存储地址为 。 7.在计算递归函数时，如果不用递归过程，则应借助于 数据结构。

8.在一个链队中，如果FRONT 和REAR分别表示队首和队尾指针，则插入一个结点S↑的操作是 。

11.从一个长度为N的顺序表中删除第I(1 <= I <= N)个元素，需要向前移动 个元素。

12.数据结构包括的3个方面的内容是：数据的 、数据存储结构和数据的运算。 13.单链表是 的链式存储表示。链栈和链队分别是 和 的链式存储表示。

14.在具有N个单元、顺序存储的循环队列中，队满时共有 个元素。

15.数据结构即数据的逻辑结构包括 、 、和 3种类型，数据的存储结构即物理结构包括 、 、 和 4种基本类型。 17. 是这样一种线性表，即所有插入和删除操作都在表的两端进行。

第4章 数组 习题

11.二维数组M[I,j]的元素是4个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到4，列下标j的范围从0到5。M按行存储时元素M[3,5]的起始地址与M按列存储时元素 的起始地址相同。

A) M[2,4] B) M[3,4] C) M[3,5] D) M[4,4] 二、填空题

9.对于一个二维数组A[1..m,1..n]，若按列为主序存储，则任意一个元素A[I,i]的相对地址是 。

5

第7章查找相关习题

17.有m个结点的霍夫曼树，其结点的个数为 。 A) 2m

B) 2m+1 C) 2m-1 D) 2(m+1)

23.二分查找法适用于存储结构为 的、按关键字排好序的线性表。 A) 顺序存储或链式存储 链式存储

B) 顺序存储 C) 索引存储 D)

31.一个序列中有若干个元素，若只想得到其中1个元素之前的部分排序，最好采用 排序。

A) 堆排序

B) 插入排序 C) shell排序 D) 快速排序

32.下列有关查找与排序的说法中正确的是 。

A) 堆排序所需的时间与待排序的记录个数无关 B) 如果某种排序算法是不稳定的，则该方法没有实际应用价值

C) 任意一颗二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间

D) 中序遍历二叉树的结点就可以得到排好序的结点序列 33.对5个不同的数据进行排序，最少需要比较 次。 A) 3

B) 4 C) 5 D) 6

34.长度为12的按关键字排序的查找表采用顺序组织方式，若采用二分查找，则在等概率情况下，查找失败时的ASL值是 。 A) 37/12

B) 62/13 C) 39/12 D) 49/13

35.堆的形状是一棵 。 A) 二叉排序树 叉树

B) 满二叉树 C) 完全二叉树 D) 不是二

6

36.静态查找表与动态查找表的根本区别在于 。

A) 它们的逻辑结构不一样 B) 施加于其上的操作不同 C) 所包含的数据元素的类型不一样 D) 存储实现不一样

37.在表长为n的顺序表中，实行顺序查找，在查找不成功时，与关键字比较的次数为 。 A) n

B) 1 C) n + 1 D) n - 1

51.设有一个已按各元素的值排好序的线性表，其长度大于2，对给定的值k，分别用顺序查找法和二分查找法查找一个与k值相等的元素，比较的次数分别为s和b。那么在查找不成功的情况下，正确的s和b的数量关系是 。

A) 与k值大小有关 B) 总有s = b C) 总有s > b D) 总有s < b (53)-- (54)题基于下述描述

散列表的地址区间为0-17，散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列 (26,25,72,38,8,18,59)依次存储到散列表中。 53.元素59存放在散列表中的地址为 。 A) 8

B) 9 C) 10 D) 11

54.存放元素59需要搜索的次数是 。 A) 2

B) 3 C) 4 D) 5

55.已知10个数据元素为(54,28,16,34,73,62,95,60,26,43)的关键码序列，对该序列按从小到大排序，经过冒泡排序后的序列为 。

A) 16,28,34,54,73,62,60,26,43,95 B) 28,16,34,54,62,73,60,26,43,95 C) 28,16,34,54,62,60,73,26,42,95 D) 16,28,34,54,62,60,73,26,42,95 75.用顺序查找法对具有n个结点的线性表查找，查找一个结点说需要的平均查找时间为 。 A) O(n2)

B) O(nlog2n) C) O(n) D) O(log2n)

7

77.在对长度为n的、顺序存储的有限序列进行二分查找时，对应的二分查找判定树的高度为 。 A) n

B) [log2n] C) [log2n(n+1)] D) [log2n]

78.采用二分查找的方法查找长度为n的有序表时，查找每个元素时平均比较次数与对应判定树的的高度（假定高度不小于2）的关系为 。 A) 前者小于后者 前者大于等于后者

79.现存在一个有序表为(10,15,17,18,25,29,48,52,58,69,90)，当二分查找值为58的元素

时， 次比较后方可查找成功。 A) 1

B) 2 C) 3 D) 4

B) 前者大于后者 C) 前者等于后者 D)

82.对线性表进行二分法查找，其前提条件是 。

A) 线性表以顺序方式存储，并且按关键码值排好序 B) 线性表以顺序方式存储，并且按关键码值的检索频率排好序

D) 线性表以链接方式

C) 线性表以链接方式存储，并且按关键码值排好序 存储，并且按关键码值的检索频率排好序

106.为了有效地利用散列查找技术，需要解决的问题是 。

Ⅰ.找一个好的散列函数 Ⅱ.设计有效的解决冲突的方法 Ⅲ.用整数表示关键码值 A) Ⅰ和Ⅱ 二、填空题

20.散列法存储中处理碰撞的方法主要有两类：链接法和 。

第5章树 和 第8章图 相关习题

B) Ⅱ 和 Ⅲ C) Ⅰ，Ⅱ和Ⅲ D) Ⅰ和Ⅲ

8

9.树最适合用来表示 。

A) 有序数据元素 B) 无序数据元素 C) 元素之间具有分支层次关系的数据 D) 元素之间无联系的数据 10.深度为5的二叉树至多有 个结点。

A) 16 B) 32 C) 31 D) 10 12.在一棵具有4层的完全二叉树中，结点总数最多为 。

A) 14 B) 15 C) 16 D) 17 13.对树中的一个结点x，在先根序列中的序号为pre(x)，在后根序列中的序号为post(x)，若树中结点x是结点y的

G D E F B A C H I 祖先，则下列4个序列中， 是正确的。

A) pre(x)>pre(y)和post(x)>post(y) B) pre(x)>pre(y)和post(x)post(y) D) pre(x)

B) 层次序 C) 前序 D) 中序

19.在一棵具有5层的完全二叉树中，结点总数最少为 。 A) 15

B) 16 C) 5 D) 31

20.图的广度优先遍历类似于树的 。

A) 后序遍历 B) 先序遍历 C) 中序遍历 历

22.将下图所示的二叉树存储为对称序线索二叉树，则结点H的左线索指向 。 A) 结点A B) 结点C C) 结点E D) 结点G

25.设有6个结点的无向图，该图至少应有 条边，才能确保它是一个连通图。

D) 按层遍

9

A) 5 B) 6 C) 7 D) 8

39.在完全二叉树中，如果一个结点是叶结点，则它没有 。 A) 右子节点

B) 左子节点

D) 左子节点和右子节点

C) 左子节点、右子节点和兄弟结点

42.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树的结点为n，则二叉树B中另一棵子树的结点个数为 。 A) m-n+1

B) n+1 C) m-n-1 D) m-n

46.已知一棵二叉树结点的先根序列为ABDGCFK，中根序列为DGBAFCK，则结点的后根序列为 。 A) ACFKBDG ABCDFKG

47.下列关于树的判断中，错误的是 。 A) 二叉树是树的特殊情况

B) 树和二叉树之间最主要的区别是：二叉树中，结点的子树要区分左子树和右子树，即使在结点中只有一棵树的情况下也要明确指出该子树是左子树还是右子树 C) 由树转换成二叉树，其根结点的右子树总是空的

D) 二叉树中具有两个子女的父结点，在中序遍历序列中，它的后序结点最多只能有

一个子女结点

48.如果结点A有3个兄弟结点，而且B是A的双亲结点，则B的度为 。 A) 2

B) 3 C) 4 D) 5

B) GDBFKCA C) KCFAGDB D)

49.设A是一个森林，B是由A转换得到的二叉树，A中有n个非终端结点，B中在指针域为空的结点有 个。

A) n – 1 B) n C) n + 1 D) n + 2

58.如果二叉树中任何一个结点的值都小于它的左子树上所有结点的值，且大于右子树

10

上所有结点的值，要得到个结点值的递增序列，应按下列 次序排列结点。 A) 先根

B) 中根 C) 后根 D) 层次

76.设森林F中有3棵树。第一、第二和第三棵树的结点个数分别是m1,m2和m3，则与森林F对应的二叉树根结点的右子树上的结点个数是 。 A) m3

B) m2 + m3 C) m1 D) m1 + m2

86.该二叉树对应的森林结点的层次次序序列为 。 A) E,G,F,A,C,D,B

D) E,G,A,C,D,F,B

B) E,A,C,B,D,G,F C) E,A,G,C,F,B,D

90.一个满二叉树，共有n个结点，其中m个为树叶，则 。

A) n = m + 1 B) m = (n + 1)/2 C) n = 2m D) n = 2 * m 91.设电文中出现的字母为A,B,C,D和E，每个字母在电文中出现的次数分别为9、27、3、5和11。按霍夫曼编码，则字母C的编码应是 。 A) 110

B) 1110 C) 10 D) 111

93.3个结点可以构造出 种不同的二叉树。 A) 2

B) 3 C) 4 D) 5

97.现有一棵度为3的树，它含有两个度为3的结点，一个度为2的结点和两个度为1的结点，由此可知度为0的结点数为 。 A) 4

B) 5 C) 6 D) 7

98.假定在一棵二叉树中，双分支结点数为12个，单分支结点数为29个，则叶子结点数为 。 A) 12

B) 13 C) 14 D) 41

99.假定一棵二叉树的结点为97，则它的最小高度为 。 A) 4

B) 5 C) 6 D) 7

100.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1,…,n]中，结点

11

A[i]若有左子女，则左子女结点是 。 A) A[2i – 1]

B) A[2i + 1] C) A[i/2] D) A[2i]

102.由分别带权为9,2,5,7的4个叶子结点构造一棵霍夫曼树，该树的带权路径长度为 。 A) 23

B) 37 C) 44 D) 46

103.下列各项叙述中，正确的是 。

A) 二叉树中每个结点有两个子结点，而对一般的树则无此限制 B) 用树的前序遍历和中序遍历可以推导出树的后续遍历

C) 在二叉树中插入结点，该二叉树便不再是二叉树 D) 用一维数组存储二叉树，总是以前序遍历顺序存储结点 104.二叉树的前序遍历和中序遍历如下：

前序遍历：EFHIGJK 中序遍历：HFIEJKG 该二叉树根中右子树的根是 。 A) E

B) F C) G

D) H

107.在下列存储形式中， 不是树的存储形式。 A) 双亲表示法 顺序存储表示法

109-110题基于下面的叙述：

某二叉树结点的中序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E。 109.该二叉树结点的前序序列为 。 A) E,G,F,A,C,D,B D) E,G,A,C,D,F,B

110.该二叉树对应的森林包括 棵树。 A) 1

B) 2

C) 3

D) 4

B) 孩子链表表示法 C) 孩子兄弟表示法

D)

B) E,A,C,B,D,G,F C) E,A,G,C,F,B,D

12

二、填空题

1.若一棵二叉树中只有叶结点和左、右子树皆非空的结点，设叶结点的个数为K，则左右子树皆非空的结点个数是 。

2.在树中，一个结点的直接孩子结点的个数称为该结点的 。

3.如果对于给定的一组权值，说构造出的二叉树的带权路径长度最小，则该树成为 。

5.设根结店的层次为0，则具有n个结点的完全二叉树的深度为 。 18.一棵二叉树的结点数为33，则其最大的深度为 。

19.按后根次序遍历树或森林等同于按 次序遍历对应的二叉树。

第9章 排序 相关习题

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

A) 插入排序 B) 归并排序 C) 选择排序 D) 快速排序 3.在对一组记录(60,43,100,30,21,79,65,21,90)进行直接插入排序时，当把它的第七个记录65插入有序表时，为寻找插入位置，需比较 次。 A) 1 B) 2 C) 3 D) 4

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

A) (79,46,56,38,40,84) B)

(84,79,56,38,40,46)

C)

(84,79,56,46,40,38) D) (84,56,79,40,38,46)

5.一组记录的排序码为(46,79,56,38,40,84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 。 A) (38,40,46,56,79,84) B)

(40,38,46,79,56,84)

C)

13

(40,38,46,56,79,84) D) (40,38,46,84,56,79)

14.对下列关键字序列用快速排序法进行排序时，速度最快的排序方法是 。 A) (5,9,17,21,23,25,30)

B) (21,9,17,30,25,23,5) C)

(21,25,5,17,9,23,30) D) (25,23,30,17,21,5,9)

15.在文件局部有序或文件长度较小的情况下，最佳的排序方法是 。 A) 冒泡排序 D) 简单选择排序

26.每次把待排序的区间划分为左、右两个子区间，其中左区间中元素的排序码均不大于基准元素的排序码，右区间中元素的排序码均不小于基准元素的排序码，这种排序方法叫做 。 A) 堆排序

B) 快速排序 C) 起泡排序 D) 希尔排序

B) 直接插入排序 C) 快速排序

27.组记录的排序码为字母序列(Q,D,F,X,A,P,N,B,Y,M,C,W)，按归并排序方法对该序列进行一趟归并后的结果为 。

A) (D,F,Q,X,A,B,N,P,C,M,W,Y) B) (D,F,Q,A,P,X,B,N,Y,C,M,W) C) (D,Q,F,X,A,P,N,B,Y,M,C,W) D) (D,Q,F,X,A,P,B,N,M,Y,C,W)

28.一组序列的关键字为(25,48,16,79,82,23,40,36,72)，其中含有5个长度为2的有序表，按归并排序方法对该序列进行一趟归并后的结果为 。

A) (16,25,35,48,23,40,79,82,36,72) B) (16,25,35,48,79,82,23,36,40,72) C) (16,25,48,35,79,82,23,36,40,72) D) (16,25,35,48,79,23,36,40,72,82) 38.若待排序序列已基本有序，要使它完全有序，则从关键码比较次数和移动次数考虑，应当使用的排序方法是 。 A) 快速排序 序

40.在设有关键码序列(16,9,4,25,15,2,13,18,17,5,8,24)，要按关键码值递增的次序排

B) 直接选择排序 C) 归并排序 D) 直接插入排

14

序，采用初始增量为4的希尔排序法，一趟扫描后的结果为 。 A) (15,2,4,18,16,5,8,24,17,9,13,25)

B) (2,9,4,25,15,16,13,18,17,5,8,24)

C) (9,4,16,15,2,13,18,17,5,8,24,25) D) (9,16,4,25,2,15,13,18,5,17,8,24) 43.设待排序的记录为(20,16,13,14,19)，并经过下列过程将这些记录排序，则所用的排序方法是 。 20 16 13 14 19 16 20 13 14 19

13 16 20 14 19 A) 冒泡排序 D) 直接插入排序 13 14 16 20 19

13 14 16 19 20

44.对于关键码序列K = { 53,30,37,12,45,24,96} ,从空二叉树开始逐个插入每个关键码，建立与集合K对应的二叉排序树（又称二叉查找树）BST，若希望得到的BST高度最小，则应选择的输入序列是 。 A) 37,24,12,30,53,45,96

B) 30,24,12,37,45,96,53 C)

B) 希尔排序 C) 堆排序

12,24,30,37,45,53,96 D) 45,24,53,12,37,96,30

45.用某种排序方法对线性表(D,I,C,G,A,E,H,F,B)进行关键码升序排列时，结点序列的变化情况如下： ①D,I,C,A,G,E,H,F,B A,B,C,D,F,E,G,H,I

②C,A,B,D,G,E,H,F,I

③

④A,B,C,D,E,F,G,H,I

那么采用的排序方法为 A) 选择排序

B) 快速排序 C) 希尔排序 D) 合并排序

60.设有n个结点进行排序，不稳定的排序方法是 。 A) 归并排序

B) 直接插入排序 C) 冒泡排序 D) shell

15

排序

63.对已建好的初始堆(84,79,56,38,36,40)进行排序，输出堆顶元素后，形成的堆为 。

A) 79,56,38,46,40

B) 79,56,46,38,40 C)

79,46,38,56,40 D) 79,46,56,38,40

66.若关键码序列(k1,k2,…,kn)是一个堆，序列中元素的关系是 。

A) ki <= k2i且ki <= k2i+1 或ki >= k2i 且ki >= k2i+1 B) k1 <= K2 <= … <= kn C) k1 >= K2 >= … >= kn D) 元素间没有任何限制

70.对n个记录的文件进行堆排序，最坏情况下的执行时间为 。 A) O(log2n)

B) O(n) C) O(nlog2n) D) O(n2)

71.用直接插入排序方法对下面4个序列进行由小到大的排序，元素比较次数最少的是 。

A) 94,32,40,90,80,46,21,69 B)

32,40,21,46,69,,94,90,80

C)

21,32,46,40,80,69,90,94 D) 90,69,80,46,21,32,94,40

73.已知12个数据元素为(34,76,45,18,26,54,92,60,25,37,03,78)，对该数列按从小到大排序。若采用希尔排序方法排序，设第一趟排序的增量为6，第二趟排序的增量为3，则第二趟排序和的序列为 。

A) 34,60,25,18,03,54,92,76,45,37,26,78 B) 18,25,03,26,34,37,54,60,45,76,78,92

C) 18,03,25,34,26,45,37,60,54,92,76,78 D) 以上都不正确 83.下列 关键码序列不符合堆的定义。 A) A,C,D,G,H,M,P,Q,R,X

B) A,C,M,D,H,P,X,G,O,R C)

Q,D,P,R,C,Q,X,M,H,G D) A,D,C,M,P,G,H,X,R,Q

84.对n个记录的文件进行快速排序，所需的辅助存储空间为 。

16

A) O(1) B) O(log2n) C) O(n) D) O(n2)

88.下列排序方法中，稳定的排序方法是 。 A) 快速排序 择排序

89.用快速排序法对下列关键字序列进行排序，速度最慢的是 。

A) {7,11,19,23,25,27,32} B) {27,25,32,19,23,7,11} C) {23,11,19,32,27,25,7} D) {23,27,7,19,11,25,32} 92.下列关键码序列中， 是一个堆。 A) (93,30,52,22,15,71)

B)

(15,52,22,93,30,71)

C)

B) 二分法插入排序 C) 希尔排序 D) 直接选

(15,30,22,93,52,71) D) (15,71,30,22,93,52)

94.具有12个记录的序列，采用冒泡排序，最少的比较次数是 。 A) 11

B) 66 C) 1 D) 144

95.已知待排序的记录的关键字为{50,34,65,76,97,27,13,37,49}，采用直接插入排序方法将记录按关键字从小到大排序。当插入37时，需要比较的记录个数为 。 A) 2

B) 3 C) 4 D) 5

96.对序列{22,86,19,49,12,30,65,35,18}进行排序，排序过程如下：

(1) {22,86,19,49,12,30,65,35,18} (2) {18,12,19,22,49,30,65,35,86}

(3) {15,18,19,22,35,30,49,65,86} (4) {15,18,19,22,30,35,49,65,86} 那么，可以认为对其使用的排序方法是 A) 快速排序 序

101.已知8个数据元素为(26,75,15,23,14,62,72,19)，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为 。 A) 3

B) 4 C) 5 D) 6

B) 选择排序 C) 插入排序 D) 冒泡排

17

105.排序的重要目的 以后对已排序的数据元素进行 。 A) 打印输出

B) 分类 C) 查找 D) 合并

111.有一组随机数：25,84,21,47,15,27,68,35,20。现在采用某种算法对它们进行排序，具体过程如下：

Ⅰ.25 84 21 47 15 27 68 35 20 Ⅱ.20 15 21 25 47 27 68 35 84 Ⅲ.15 20 21 25 35 27 47 68 84 Ⅳ.15 20 21 25 27 35 47 68 84 A) 选择排序 二、填空题

6.在一棵二叉树排序树中，按 遍历得到的结点序列是一个有序序列。 10.快速排序法在被排序的数据量 时，最不利于发挥其长处。

16.对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较 次。 参考答案 一、 选择题 1.C 11.B 2.C 12.B 3.C 13.C 23.B 33.B 43.D 53.D 63.D 73.C 83.C 4.B 14.A 24.C 34.B 44.A 54.C 64.A 74.B 84.B 5.C 15.A 25.A 35.C 45.B 55.B 65.A 75.C 85.D 6.A 16.C 26.B 36.B 46.B 56.B 66.A 76.B 86.D 7.C 17.C 27.D 37.C 47.A 57.C 67.A 77.D 87.C 8.B 18.B 28.A 38.B 48.C 58.B 68.C 78.A 88.B 9.C 19.B 29.A 10.C 20.D 30.A B) 快速排序 C) 冒泡排序 D) Shell排序

21.C 22.B 31.A 41.B 51.A 61.B 32.D 42.C 52.C 62.A 39.D 40.A 49.C 50.C 59.A 60.D 69.D 70.C 79.B 89.A 80.B 90.B 18

71.C 72.B 81.B

82.A 91.B 92.C 93.D 94.A 95.C 96.A 97.C 98.B 99.C 100.D 101.B 102.C 103.D 104.C 105.C 106.C 107.C 108.D 109.B 110.B

二、 填空题 1 k-1 2 度

3 最优二叉树或霍夫曼树 4 232 5 |Log2n| 6 中序 7 栈

8 REAR->NEXT=S; REAR=S 9

(j-1)*n+i-1

10 大 11 N-1

12 逻辑结构 13 线性表 栈 队列 14 N-1

15 线性结构 树型结构 图形结构顺序 链接 索引 散列 16 3 17 队列 18 33 19 对称序 20 开地址法

19

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