2021知到答案 数据结构（山东联盟-青岛大学） 最新智慧树满分章节测试答案

第三章 单元测试

1、单选题：
栈的插入和删除操作在（  ）进行。

选项：
A:任意位置
B:栈底
C:指定位置
D:栈顶
答案: 【栈顶】

2、单选题：
对一个初始为空的栈s执行操作Push(s,5),Push(s,2),Push(s,4),Pop(s,x),getTop(s,x)后，x的值应是（  ）。

选项：
A:5
B:0
C:4
D:2
答案: 【2】

3、单选题：
用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234，为了得到1342出栈顺序，相应的S和X的操作序列为（  ）。
选项：
A:SXSXSSXX
B:SXSSXXSX
C:SSSXXSXX
D:SXSSXSXX
答案: 【SXSSXSXX】

4、单选题：
假设一个栈的输入序列是1,2,3,4，则不可能得到的输出序列是（  ）。

选项：
A:4,3,2,1
B:1,2,3,4
C:1,3,4,2
D:4,1,2,3
答案: 【4,1,2,3】

5、单选题：
已知一个栈的进栈序列为1,2,3,…,n，其输出序列的第一个元素是i，则第j个出栈元素是（  ）。

选项：
A:不确定
B:j-i
C:n-i
D:j-i+1
答案: 【不确定】

6、单选题：
已知一个栈的进栈序列为1,2,3,…,n，其输出序列是p1,p2,p3,…,pn。若p1=n，则pi的值是（  ）。
选项：
A:不确定
B:n-i
C:i
D:n-i+1
答案: 【n-i+1】

7、单选题：
已知一个栈的进栈序列为1,2,3,…,n，其输出序列是p1,p2,p3,…,pn。若p1=3，则p2的值（  ）。

选项：
A:一定是1
B:一定是2
C:可能是1
D:可能是2
答案: 【可能是2】

8、单选题：
已知一个栈的进栈序列为p1,p2,p3,…,pn，其输出序列是1,2,3,…,n。若p3=1，则p1的值（  ）。

选项：
A:一定是3
B:可能是2
C:不可能是2
D:一定是2
答案: 【不可能是2】

9、单选题：
设一个循环队列Q[maxSize]的队头指针为front，队尾指针为rear，队列最大容量为maxSize，除此之外该队列再没有其他数据成员，则该队列的队满条件是（  ）。

选项：
A:Q.front==(Q.rear+1)%maxSize
B:Q.front==Q.rear
C:Q.front+Q.rear>=maxSize
D:Q.rear==(Q.front+1)%maxSize
答案: 【Q.front==(Q.rear+1)%maxSize】

10、单选题：
设循环队列的存储容量为maxSize，队头和队尾指针分别为front和rear。若有一个循环队列Q，可应用下列语句（  ）计算队列元素个数？
选项：
A:(Q.rear-Q.front+maxSize)%maxSize
B:(Q.rear-Q.front)%maxSize+1
C:Q.rear-Q.front+1
D:Q.rear-Q.front
答案: 【(Q.rear-Q.front+maxSize)%maxSize】

11、单选题：
一个队列的进队顺序是1,2,3,4，则该队列可能的输出序列是（  ）。

选项：
A:1,2,3,4
B:4,3,2,1
C:1,4,2,3
D:1,3,2,4
答案: 【1,2,3,4】

12、单选题：
对于链式队列，在执行插入操作时（  ）。

选项：
A:头、尾指针都要修改
B:头、尾指针可能都要修改
C:仅修改尾指针
D:仅修改头指针
答案: 【头、尾指针可能都要修改】

13、单选题：
最适合用作链式队列的链表是（  ）。

选项：
A:只带队头指针的循环单链表
B:带有队头指针和队尾指针的非循环单链表
C:只带队头指针的非循环单链表
D:带有队头指针和队尾指针的循环单链表
答案: 【带有队头指针和队尾指针的非循环单链表】

14、单选题：
最不适合用作链式队列的链表是（  ）。

选项：
A:带有队头指针的双向非循环链表
B:带有队头指针的双向循环链表
C:只带队尾指针的循环单链表
D:只带队尾指针的双向循环链表
答案: 【带有队头指针的双向非循环链表】

15、单选题：
设一个链式队列q的队头指针和队尾指针分别为front和rear，则判断队列空的条件是（  ）。
选项：
A:q.front!=NULL
B:q.rear==NULL
C:q.front==q.rear
D:q.front==NULL
答案: 【q.front==NULL】

16、单选题：
将递归算法转换成非递归算法时， 通常要借助的数据结构是（   ）。

选项：
A:队列
B:树
C:栈
D:线性表
答案: 【栈】

17、单选题：
栈与一般线性表的区别在于（）。
选项：
A:数据元素的类型不同
B:逻辑数据不同
C:运算是否受限制
D:数据元素的个数不同
答案: 【运算是否受限制】

18、判断题：
栈和队列都是顺序存取结构。

选项：
A:错
B:对
答案: 【对】

19、判断题：
对循环队列初始化时 · 要求队头指针与队尾指针指向同一个位置， 不论队列存储中什么位置都可以。

选项：
A:错
B:对
答案: 【对】

20、判断题：
栈 是 实 现 过 程 和 函 数 等 子 程 序 调 用 所 必 需 的 结 构。

选项：
A:对
B:错
答案: 【对】

第四章 单元测试

1、单选题：
字符串可定义为n(n≥0)个字符的有限（         ），其中，n是字符串的长度，表明字符串中字符的个数。

选项：
A:序列
B:集合
C:聚合
D:数列
答案: 【序列】

2、单选题：
串是一种特殊的线性表，其特殊性体现在（  ）。

选项：
A:可以顺序存储
B:数据元素是一个字符
C:数据元素可以是多个字符
D:可以链接存储
答案: 【数据元素是一个字符】

3、单选题：
有n个字符的字符串的非空子串个数最多有（     ）。
选项：
A:n(n+1)/2
B:n-1
C:n(n-1)/2
D:n
答案: 【n(n+1)/2】

4、单选题：
两个字符串相等的条件是（      ）。

选项：
A:两个串的长度相等，并且两个串包含的字符相同
B:两个串的长度相等
C:两个串包含的字符相等
D:两个串的长度相等，并且对应位置上的字符相同
答案: 【两个串的长度相等，并且对应位置上的字符相同】

5、单选题：
设有两个串：T和P，求P在T中首次出现的位置的运算叫做（     ）。

选项：
A:模式匹配
B:串替换
C:求子串
D:串连接
答案: 【模式匹配】

6、单选题：
在以下关于串的说法中正确的是（）。

选项：
A:用块链存储表示实现的串的结点大小为4,说明每个结点可存储4个字符
B:串长度是指串中不同字符的个数
C:子串是从串中抽取出若干字符组成的串
D:空串是由空格组成的串
答案: 【用块链存储表示实现的串的结点大小为4,说明每个结点可存储4个字符】

7、单选题：
设有两个串T和P，求P在T中首次出现的位置的运算叫做（）。
选项：
A:模式匹配
B:串替换
C:串连接
D:求子串
答案: 【模式匹配】

8、单选题：
设T=”aaaaaacaaaca”，P=“aaac”，使用BF算法的模式匹配过程需要执行的趟数为（）。
选项：
A:3
B:2
C:7
D:4
答案: 【4】

9、判断题：
应用 KMP 算法进行模式匹配时，next 函数值序列的产生仅与模式串有关。

选项：
A:错
B:对
答案: 【对】

10、判断题：
KMP 算法的特点是在模式匹配时指示目标串当前比对位置的指针不会回退。

选项：
A:错
B:对
答案: 【对】

第五章 单元测试

1、单选题：

对稀疏矩阵进行压缩存储的目的是（  ）。

选项：
A:便于进行矩阵运算
B:降低运算的时间复杂度
C:节省存储空间
D:便于输入和输出
答案: 【节省存储空间】

2、单选题：

一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比会失去（   ）特性。

选项：
A:输入输出
B:顺序存储
C:其余选项都不对
D:随机存取
答案: 【随机存取】

3、单选题：

稀疏矩阵常用的压缩存储方法有（   ）。

选项：
A:二维数组
B:三元组和散列表
C:散列表和十字链表
D:三元组和十字链表
答案: 【三元组和十字链表          】

4、单选题：
以下关于一维数组与顺序表不同之处的说法中错误的是（）。
选项：
A:前者的元素可以不连续存放，后者的元素必须相继存放
B:前者的元素数据类型相同，后者的元素数据类型可以不相同
C:前者既可以是逻辑结构也可以是存储结构，后者是线性表的存储结构
D:前者的长度不变，后者的长度可变
答案: 【前者的元素数据类型相同，后者的元素数据类型可以不相同】

5、单选题：
将一个n*n的对称矩阵A的对角线和对角线以上的部分按列优先存放于一个一维数组中，那么A有(    )个矩阵元素未被存于sa中。
选项：
A:n^2/2

B:n(n-1)/2
C:n(n+1)/2

D:n(n-1)
答案: 【n(n-1)/2】

6、单选题：
设一维数组 A[n]中每个元素占用 6 个存储单元，若A[5]的存储地址从 100 开始，则该数组的首地址是（ )。

选项：
A:30
B:76

C:64
D:95
答案: 【64】

7、单选题：
在二维数组A[9][10]中，每个数组元素占用3个存储单元，从首地址SA开始按行优先连续存放。在这种情况下，元素A[8][5]的起始地址为 （  ）。
选项：
A:SA+144
B:SA+255
C:SA+222
D:SA+141
答案: 【SA+255】

8、单选题：
设一个稀疏矩阵有1000行850列，其中有1000个非零元素。设每个整数占2字节，数据占4字节。则用三元组表存储该矩阵时所需字节数是（）。
选项：
A:8000

B:1000

C:18000
D:4000
答案: 【8000
】

9、判断题：

二维数组是其数组元素为线性表的线性表。

选项：
A:错
B:对
答案: 【错】

10、判断题：
用一维数组存储特殊矩阵，可以简化对矩阵的存取操作。
选项：
A:错
B:对
答案: 【错】

第六章 单元测试

1、单选题：
树最合适用来表示（   ）。

选项：
A:有序数据元素
B:元素之间具有分支层次关系的数据
C:无序数据元素
D:元素之间无联系的数据
答案: 【元素之间具有分支层次关系的数据】

2、单选题：
一棵有n个结点的树的所有结点的度数之和为（   ）。

选项：
A:n-1
B:n+1
C:2n
D:n
答案: 【n-1】

3、单选题：
设树中某结点不是根结点，则离它最近的祖先结点是（      ）。

选项：
A:父结点的父结点
B:父结点
C:该结点本身
D:根结点
答案: 【父结点】

4、单选题：
在二叉树中某一结点的深度为3,高度为4,该树的髙度至少为（          ）。
选项：
A:7
B:6
C:5
D:8
答案: 【6】

5、单选题：
设一棵高度为h的满二叉树有n个结点，其中有m个叶结点，则（          ）。

选项：
A:h+m=2n
B:m=h-1
C:n=2^h-1
D:n=h+m
答案: 【n=2^h-1】

6、单选题：
具有33个结点的完全二叉树，有（    ）个度为1的结点。

选项：
A:1
B:12
C:16
D:0
答案: 【0】

7、单选题：
一颗有124个叶子结点的完全二叉树最多有（       ）个结点。
选项：
A:250
B:248
C:249
D:247
答案: 【248】

8、单选题：
一颗有129个叶结点的完全二叉树最少有（   ）个结点。
选项：
A:255
B:258
C:254
D:257
答案: 【257】

9、单选题：
如果二叉树T₂是由一棵树T₁转换而来的二叉树，那么T₁中结点的先根序列对应T₂的（     ）序列。

选项：
A:中序遍历
B:层次遍历
C:后序遍历
D:先序遍历
答案: 【先序遍历          】

10、单选题：
如果二叉树T₂是由一棵树T₁转换而来的二叉树，那么T₁中结点的后根序列对应T₂的（   ）序列。

选项：
A:层次遍历
B:先序遍历
C:后序遍历
D:中序遍历
答案: 【中序遍历          】

11、单选题：
一个深度为k且只有k个结点的二叉树，按照完全二叉树顺序存储的方式存放于一个一维数组A[n]中，那么n应至少是（）。

选项：
A:2^k-1
B:2k
C:2k+1
D:2^k
答案: 【2^k-1】

12、单选题：
二叉树的叶子结点在前序、中序和后序遍历过程中的相对顺序（  ）。
选项：
A:其余选项都不对
B:发生改变
C:无法确定
D:不发生改变
答案: 【不发生改变】

13、单选题：
设n、m为一棵二叉树上的两个结点，在中序遍历序列中，n在m前的条件是（）。

选项：
A:n在m右方
B:n是m的祖先
C:n是m的子孙
D:n在m左方
答案: 【n在m左方】

14、单选题：
在一棵二叉树中有两个结点n和m。在该二叉树的前序遍历序列中n在m之前，而在其后序遍历序列中n在m之后，则n和m的关系是（）。
选项：
A:n是m的子孙
B:n是m的左兄弟
C:n是m的祖先
D:n是m的右兄弟
答案: 【n是m的祖先】

15、单选题：
前序序列与中序序列正好相反的非空二叉树是（）。
选项：
A:右单支树
B:完全二叉树
C:满二叉树
D:左单支树
答案: 【左单支树】

16、单选题：
在中序线索二叉树中，指针 t 所指结点的左子树为空的充要条件是（ ） 。
选项：
A:其余选项都不对
B:t->ltag==1 且 t->lchild==NULL
C:t->ltag==1
D:t->lchild== NULL
答案: 【t->ltag==1 且 t->lchild==NULL】

17、单选题：
设森林F对应的二叉树为A，它有m个结点。A的根为p，p的右子树中结点个数为n，则森林F中第一棵树的结点个数是（）。
选项：
A:m-n
B:n+1
C:无法确定
D:m-n-1

答案: 【m-n】

18、单选题：
设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（）个。
选项：
A:n-1

B:n+1
C:n
D:n+2
答案: 【n+1】

19、单选题：
用n个权重构造出来的Huffman 树共有（ ）个结点。
选项：
A:2n-1

B:n+1
C:2n
D:2n+1
答案: 【2n-1
】

20、单选题：
设T是Huffman树，具有5个叶结点，树T的高度最高可以是（）。
选项：
A:3
B:4
C:6
D:5
答案: 【5】

第七章 单元测试

1、单选题：
在无向图中定义顶点的度为与它相关联的（    ）的数目。
选项：
A:边
B:权值
C:权
D:顶点
答案: 【边】

2、单选题：
具有 n 个顶点且每一对不同的顶点之间都有一条边的无向图被称为（ ）。

选项：
A:无向连通图
B:无向树图
C:无向完全图
D:无向强连通图
答案: 【无向完全图】

3、单选题：
一个有 n 个顶点的无向图最多有（  ）边。

选项：
A:n(n-1)
B:n(n-1)/2

C:n
D:2n

答案: 【n(n-1)/2
】

4、单选题：
具有 6 个顶点的无向图至少应有（   ）条边才能确保是一个连通图。

选项：
A:5

B:7

C:6

D:8

答案: 【5
】

5、单选题：
图的简单路径是指（   ）不重复的路径。

选项：
A:边

B:顶点

C:权值
D:边与顶点均

答案: 【顶点
】

6、单选题：
在一个具有 n 个顶点的有向图中，若所有顶点的出度之和为 s，则所有顶点的入度之和为（   ）。
选项：
A:s

B:s-1

C:s+1

D:n

答案: 【s
】

7、单选题：
在下列有关图的说法中正确的是（ ）。

选项：
A:具有 n 个顶点的无向图最多有 n(n-1)条边，最少有 n-1 条边
B:在有向图中，各顶点的入度之和等于各顶点的出度之和
C:在无向图中，边的条数是结点度数之和
D:在图结构中，顶点可以没有任何前驱和后继
答案: 【在有向图中，各顶点的入度之和等于各顶点的出度之和】

8、单选题：
对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接矩阵表示，则该矩阵中的非零元素个数是（  ）。
选项：
A:e
B:e^2
C:2e
D:n^2

答案: 【2e】

9、单选题：
无向图的邻接矩阵是一个（    ）。

选项：
A:对角矩阵
B:上三角矩阵
C:对称矩阵
D:零矩阵
答案: 【对称矩阵】

10、单选题：
有 n 个顶点和 e 条边的无向图采用邻接矩阵存储，零元素的个数为（   ）。
选项：
A:e
B:n^2-e
C:n^2-2e

D:2e
答案: 【n^2-2e
】

11、单选题：
从邻接矩阵可知，该有向图共有（     ）条有向边。
选项：
A:9
B:4

C:2

D:3

答案: 【4
】

12、单选题：
带权有向图G用邻接矩阵 A 存储，则顶点 i 的入度等于A中（   ）。

选项：
A:第i行非∞且非0的元素个数
B:第i列非∞且非0的元素个数
C:第 i 列非∞的元素之和
D:第 i 行非∞的元素之和
答案: 【第i列非∞且非0的元素个数】

13、单选题：
下列说法中正确的是（ ）。

选项：
A:一个图的邻接矩阵表示不唯一，邻接表表示也不唯一
B:一个图的邻接矩阵表示不唯一，邻接表表示唯一
C:一个图的邻接矩阵表示是唯一的，邻接表表示也唯一
D:一个图的邻接矩阵表示是唯一的，邻接表表示不唯一
答案: 【一个图的邻接矩阵表示是唯一的，邻接表表示不唯一】

14、单选题：
用邻接表存储图所用的空间大小（   ）。

选项：
A:与图的顶点数和边数都有关
B:与边数的平方有关
C:只与图的顶点数有关
D:只与图的边数有关系
答案: 【与图的顶点数和边数都有关】

15、单选题：
在下列有关图的存储结构的说法中错误的是（   ）。

选项：
A:用邻接矩阵存储一个图时所占用的存储空间大小与图中的顶点个数有关，而与图的边数无关
B:邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用
C:邻接矩阵只适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）
D:对同一个有向图来说，邻接表中边结点数与逆邻接表中边结点数相等
答案: 【邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用】

16、单选题：
设图有n个顶点和e条边，采用邻接矩阵时，遍历图时的顶点所需时间为（）。

选项：
A:O(e)
B:O(ne)
C:O(n)

D:O(n^2)

答案: 【O(n^2)
】

17、单选题：
设图有n个顶点和e条边，采用邻接表时，遍历图的顶点所需时间为（）。
选项：
A:O(n+e)
B:O(e)
C:O(n^2)

D:O(ne)
答案: 【O(n+e)】

18、单选题：
如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。
选项：
A:连通图
B:强连通图
C:有回路
D:—棵树
答案: 【连通图】

19、单选题：
如果一个连通网络 G 中各边权值互不相同， 权值最小的边一定包含在 G 的(  )生成树中。
选项：
A:广度优先
B:深度优先
C:最小
D:任何
答案: 【最小】

20、单选题：
任何一个连通图的最小生成树（ ）。
选项：
A:有一棵或多棵
B:只有一棵
C:可能不存在
D:一定有多棵
答案: 【有一棵或多棵】

21、单选题：
Dijkstra 算法是（ ）来求出图中从某顶点到其余顶点最短路径的。
选项：
A:通过深度优先遍历求出图的某顶点到其余顶点的所有路径
B:按长度递增的顺序求出图的某顶点到其余顶点的最短路径
C:按长度递减的顺序求出图的某项点到其余顶点的最短路径
D:通过广度优先遍历求出图的某顶点到其余顶点的最短路径
答案: 【按长度递增的顺序求出图的某顶点到其余顶点的最短路径】

22、单选题：
已知一个带权有向图如图所示，依据Dijkstra算法求从顶点1到其余各顶点的最短路径的顺序应是（  ）。
选项：
A:2 5 4 6 3
B:2 3 5 4 6

C:2 5 3 4 6

D:5 4 6 3 2

答案: 【2 5 3 4 6
】

23、单选题：
如果一个有向图具有拓扑有序序列，并且顶点按拓扑有序序列编号， 那么它的邻接矩阵必定为（ ）。
选项：
A:对称矩阵
B:上三角矩阵
C:三对角矩阵
D:下三角矩阵
答案: 【上三角矩阵】

24、单选题：
若一个有向图中的部分顶点不能通过拓扑排序排到一个拓扑有序序列里，则可断定该有向图是一个（ ） 。
选项：
A:含有顶点数大于 1 的强连通分量
B:DAG图
C:强连通图
D:含有多个入度为 0 的顶点的图
答案: 【含有顶点数大于 1 的强连通分量】

25、单选题：
在如图所示的 AOE 网中， 关键路径长度为（  ）。
选项：
A:23
B:22
C:16
D:13
答案: 【23】

第八章 单元测试

1、单选题：
顺序查找算法适用于（      ）结构。
选项：
A:查找树
B:查找网
C:连通图
D:线性表
答案: 【线性表           】

2、单选题：
在顺序存储的线性表R[30]上进行顺序查找的平均查找长度为（        ）。
选项：
A:16

B:15
C:15.5

D:20
答案: 【15.5
】

3、单选题：
对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找到表中任一元素的平均查找长度为（ ）。
选项：
A:5
B:19/4

C:39/8

D:5.5
答案: 【39/8
】

4、单选题：
如果有5个关键字{a,b,c,d,e}放在顺序表中，它们的查找概率分别为{0.35,0.25，0.20,0.15,0.05}，按照（   ）顺序存放可使平均查找长度达到最小。

选项：
A:a,c,e,d,b
B:d,a,b,c,e
C:a,b,c,d,e
D:e,d,c,b,a
答案: 【a,b,c,d,e】

5、单选题：
对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素的查找成功的平均查找长度为（    ）。
选项：
A:n/2
B:(n-1)/2

C:n/4
D:(n+1)/2

答案: 【(n+1)/2
】

6、单选题：
对线性表进行折半查找时，要求线性表必须（      ）。

选项：
A:以顺序方式存储
B:以顺序方式存储，且结点按关键字有序排序
C:以链接方式存储
D:以链接方式存储，且结点按关键字有序排序
答案: 【以顺序方式存储，且结点按关键字有序排序】

7、单选题：
采用折半查找方式查找一个长度为n的有序顺序表时，其平均查找长度为（ ）。
选项：
A:O(n)
B:O(n^2)
C:O(nlog2n)
D:O(log2n)
答案: 【O(log2n)】

8、单选题：
采用折半查找法查找长度为n的有序顺序表，查找每个元素的数据比较次数（  ）对应二叉判定树的高度（设高度≥2）。

选项：
A:等于
B:小于等于

C:小于
D:大于
答案: 【小于等于
】

9、单选题：
折半查找和二叉排序树的时间性能（      ）。
选项：
A:完全不同

B:不定
C:有时不相同

D:相同
答案: 【有时不相同
】

10、单选题：
在常用的描述二叉排序树的存储结构中，关键字值最大的结点（     ）。

选项：
A:左指针一定为空
B:左右指针均不为空
C:右指针一定为空
D:左右指针均为空
答案: 【右指针一定为空】

11、单选题：
m阶B-树是一棵（           ）。

选项：
A:m叉查找树
B:m-1叉高度平衡查找树
C:m+1叉高度平衡查找树
D:m叉高度平衡查找树
答案: 【m叉高度平衡查找树】

12、单选题：
下列关于m阶B-树的说法中错误的是（              ）。

选项：
A:根结点至多有m棵子树
B:非失败结点至少有m/2（m为偶数）或m/2+1（m为奇数）棵子树
C:根结点中的数据是有序的
D:所有叶结点都在同一层次上
答案: 【非失败结点至少有m/2（m为偶数）或m/2+1（m为奇数）棵子树】

13、单选题：
下面关于B-树和B+树的叙述中错误的是（  ）。
选项：
A:B-树和B+树都能有效地支持随机查找
B:B-树和B+树都是平衡的多叉查找树
C:B-树和B+树都能有效地支持顺序查找
D:B-树和B+树都可用于文件的索引结构
答案: 【B-树和B+树都能有效地支持顺序查找】

14、单选题：
散列法存储的基本思想是根据（    ）来决定元素的存储地址。

选项：
A:元素的序号
B:非码属性
C:元素个数
D:关键字值
答案: 【关键字值       】

15、单选题：
设一个散列表中有n个元素，用散列法进行查找，理想情况下的平均查找长度是（   ）。
选项：
A:O(n)
B:O(n^2)
C:O(1)
D:O(log2n)
答案: 【O(1) 】

16、单选题：
使用散列函数将元素的关键字值映射为散列地址时，常会产生冲突。此时的冲突是指（    ）。

选项：
A:两个元素的关键字值不同，而非关键字值相同
B:装填因子过大，数据元素过多
C:两个元素具有相同的序号
D:不同关键字值对应到相同的存储地址
答案: 【不同关键字值对应到相同的存储地址】

17、单选题：
以下关于散列函数选择原则的叙述中，不正确的是（        ）。

选项：
A:装填因子必须限制在0.8以下
B:散列函数计算出来的地址应能均匀分布在整个地址空间中
C:散列函数应是简单的，能在较短的时间内计算出结果
D:散列函数的定义域应包括全部关键字值,值域必须在表范围之内
答案: 【装填因子必须限制在0.8以下】

18、单选题：
计算出的地址分布最均匀的散列函数是（     ）。

选项：
A:除留余数法
B:折叠法
C:数字分析法
D:平方取中法
答案: 【除留余数法           】

19、单选题：
除留余数法的基本思路是：设散列表的地址空间为0～m-1，元素的关键字值为k，用p去除k，将余数作为元素的散列地址，即h(k)=k%p，为了减少发生冲突的可能性，一般取p为（      ）。

选项：
A:m
B:大于m的最小素数
C:小于或等于m的最大素数
D:小于或等于m的最大合数
答案: 【小于或等于m的最大素数】

20、单选题：
解决散列法中出现的冲突问题常采用的方法是（        ）。

选项：
A:数字分析法、除留余数法、线性探测法
B:数字分析法、除留余数法、平方取中法
C:数字分析法、线性探测法、双散列法
D:线性探测法、二次探测散列法、链地址法
答案: 【线性探测法、二次探测散列法、链地址法】

21、单选题：
在用开放定址法构造出的散列表中，散列到同一个地址而引起的“二次聚集”问题是由于（  ）引起的。

选项：
A:同义词之间发生冲突
B:同义词之间或非同义词之间发生冲突
C:散列表“溢出”
D:非同义词之间发生冲突
答案: 【同义词之间或非同义词之间发生冲突】

22、单选题：
散列表的平均查找长度（        ）。

选项：
A:与处理冲突方法无关而与表的长度有关
B:与处理冲突方法有关而与表的长度无关
C:与处理冲突方法有关且与表的长度有关
D:与处理冲突方法无关且与表的长度无关
答案: 【与处理冲突方法有关而与表的长度无关】

23、判断题：
在由n个元素组成的有序表上进行折半查找时，对任一个元素进行查找的长度都不会大于。
选项：
A:错
B:对
答案: 【对】

24、判断题：
对于两棵具有相同关键码集合而形状不同的二叉查找树，按中序遍历它们得到的序列的各元素的顺序是一样的。
选项：
A:对
B:错
答案: 【对】

25、判断题：
在一棵AVL树中删除一个结点后，失去平衡的结点多于一个。
选项：
A:对
B:错
答案: 【错】

第九章 单元测试

1、单选题：
每次从未排序的序列中取出一个元素与已排序的序列中的元素依次进行比较，然后把它插入到已排序序列中的适当位置，此种排序方法叫做（       ）排序。

选项：
A:简单选择排序
B:二路归并排序
C:直接插入排序
D:起泡排序
答案: 【直接插入排序       】

2、单选题：
对5个不同的数据元素进行直接插入排序，最多需要进行（     ）次比较。
选项：
A:25

B:15

C:8
D:10

答案: 【10
】

3、单选题：
有一种排序方法，如果最小的元素位于待排序序列的最后，则在最后一趟排序开始之前，所有元素都不在其最终位置上，这种排序方法是（    ）。

选项：
A:快速排序
B:简单选择排序
C:直接插入排序
D:起泡排序
答案: 【直接插入排序       】

4、单选题：
每次直接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做（ ）排序。

选项：
A:选择排序
B:基数排序
C:冒泡排序
D:堆排序
答案: 【冒泡排序       】

5、单选题：
每次从待排序序列中挑选出一个最小或最大元素，把它交换到该序列的最前端，此种排序方法叫做（     ）排序。

选项：
A:二路归并排序
B:简单选择排序
C:起泡排序
D:直接插入排序
答案: 【简单选择排序       】

6、单选题：
在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将序列{tang,deng,an,wan,shi,bai,fang,li}中的关键字按升序排列，则（    ）是冒泡排序一趟扫描的结果。

选项：
A:deng,an,tang,shi,bai,fang,li,wan
B:an,deng,bai,li,shi,tang,fang,wan
C:deng,tang,an,wan,bai,shi,fang,li
D:deng,tang,an,wan,bai,shi,li,fang
答案: 【deng,an,tang,shi,bai,fang,li,wan】

7、单选题：
在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合{tang,deng,an,wan,shi,bai,fang,li}中的关键字按升序排列，则（    ）是初始步长为4的希尔排序一趟扫描的结果。

选项：
A:an,tang,deng,wan,shi,bai,fang,li
B:shi,bai,an,li,tang,deng,fang,wan
C:li,deng,an,shi,bai,fang,tang,wan
D:an,bai,deng,fang,li,shi,tang,wan
答案: 【shi,bai,an,li,tang,deng,fang,wan】

8、单选题：
在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合{tang,deng,an,wan,shi,bai,fang,li}中的关键字按升序排列，则（    ）是以第一个元素为分界元素的快速排序一趟扫描的结果。

选项：
A:deng,tang,an,wan,bai,shi,fang,li
B:deng,an,tang,shi,bai,fang,li,wan
C:li,deng,an,shi,bai,fang,tang,wan
D:shi,bai,an,li,tang,deng,fang,wan
答案: 【li,deng,an,shi,bai,fang,tang,wan】

9、单选题：
一个元素序列的关键字为{46,79,56,38,40,84}，采用快速排序（以位于最左位置的元素为基准）得到的第一次划分结果为（    ）。

选项：
A:{38,46,79,56,40,84}
B:{38,46,56,79,40,84}
C:{40,38,46,79,56,84}
D:{38,79,56,46,40,84}
答案: 【{40,38,46,79,56,84}】

10、单选题：
在快速排序中，要使最坏情况下的空间复杂度为O(log₂n)，要对快速排序做（  ）修改。

选项：
A:先排小子区间
B:先排大子区间
C:采用链表排序
D:划分轴点为三者取中
答案: 【划分轴点为三者取中           】

11、单选题：
在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合{ tang, deng, an, wan, shi, bai,fang, li }中的关键字按升序排列，则（    ）是大根堆排序初始建堆的结果。

选项：
A:wan, tang, fang, li, shi, bai, an, deng
B:an, tang, deng, wan, shi, bai, fang, li
C:an, bai, deng, fang, li, shi, tang, wan
D:deng, tang, an, wan, bai, shi, fang, li
答案: 【wan, tang, fang, li, shi, bai, an, deng】

12、单选题：
堆是一种有用的数据结构。例如关键字序列（    ）就是一个小根堆。

选项：
A:16, 53, 23, 94, 31, 72
B:16, 31, 23, 94, 53, 72
C:16, 72, 31, 23, 94, 53
D:94, 53, 31, 72, 16, 53
答案: 【16, 31, 23, 94, 53, 72】

13、单选题：
向具有 n 个结点的堆中插入一个新元素的时间复杂度为（    ）。

选项：
A:O(1)
B:O(nlog₂n)
C:O(n)
D:O(log₂n)
答案: 【O(log₂n)】

14、单选题：
在内排序的过程中，通常需要对待排序元素序列的关键字做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合{tang,deng,an,wan,shi,bai,fang,li}中的关键字按升序排列，则（    ）是二路归并排序一趟扫描的结果。
选项：
A:an,deng,bai,li,shi,tang,fang,wan
B:deng,tang,an,wan,bai,shi,fang,li
C:deng,tang,an,wan,bai,shi,li,fang
D:deng,an,tang,shi,bai,fang,li,wan
答案: 【deng,tang,an,wan,bai,shi,fang,li】

15、单选题：
将两个各有m个元素的有序序列归并成一个有序序列，关键字比较次数最少为（      ）。
选项：
A:m

B:m-1
C:2m-1

D:2m
答案: 【m
】

16、单选题：
排序算法的稳定性是指（）。
选项：
A:经过排序后，能使值相同的数据保持原顺序中的相对位置不变
B:经过排序后，数据序列的存放数组的结构保持不变
C:经过排序后，数据序列的存放数组的结构随之变化
D:经过排序后，能使值相同的数据保持原顺序中的绝对位置不变
答案: 【经过排序后，能使值相同的数据保持原顺序中的相对位置不变】

17、单选题：
若要求在最坏情况下也能尽快地对序列进行稳定的排序，则应选（）。
选项：
A:堆排序
B:冒泡排序
C:归并排序
D:快速排序
答案: 【归并排序】

18、单选题：
设一个待排序序列为{92,83,77,64,54,43,38,27,15},将该序列排好序经过了16次关键字比较，使用的排序方法是（ ）。

选项：
A:折半插入排序
B:直接插入排序
C:冒泡排序
D:简单选择排序
答案: 【折半插入排序】

19、单选题：
对序列{27,21,15,18,41,7,12}用希尔排序法进行排序， 经过一趟排序后，序列变为{27,7,12,18,41,21,15 }，那么这一趟采用的增量是（）。
选项：
A:4
B:5
C:2
D:3
答案: 【4】

20、单选题：
若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需执行的关键字比较次数是（ ）。
选项：
A:25

B:15
C:10
D:3
答案: 【15】

21、单选题：
若元素序列{11,12,13,7,8,9,23,4,5}是采用下列排序方法之一得到的第二趟排序后的结果，则该排序方法只能是（ ） 。

选项：
A:二路归并排序
B:冒泡排序
C:插入排序

D:选择排序
答案: 【插入排序
】

22、单选题：
从一个具有 n 个元素的堆中删除一个元素的时间复杂度为（）。
选项：
A:O(nlogn)
B:O(n)
C:O(1)
D:O(logn)
答案: 【O(logn)】

23、单选题：
对由n个元素所组成的序列按关键字排序时，二路归并排序算法，所需要的辅助存储是（）。
选项：
A:O(1)
B:O(nlogn)
C:O(logn)
D:O(n)
答案: 【O(n)】

24、单选题：
下列排序算法中，最坏情况下的时间代价不高于 O(nlogn)的是（）。
选项：
A:插入排序
B:归并排序
C:堆排序
D:快速排序
答案: 【归并排序】

25、单选题：
如果将所有中国人按照生日（不考虑年份，只考虑月、日）来排序，那么下列排序算法中，排序速度最快的算法是（）。

选项：
A:希尔排序
B:归并排序
C:快速排序
D:基数排序
答案: 【基数排序】