MOOC 算法与数据结构(东莞理工学院)1450427189 最新慕课完整章节测试答案
(第十二周) 第八章 查找（下）
文章目录
8.9 哈希表（一）——基本概念
1、单选题：
将 10 个元素散列到 100000 个单元的哈希表，则（ ）产生冲突。
选项：
A: 一定会
B: 不一定会
C: 仍可能会
D: 以上都不对
答案: 【 仍可能会】
2、单选题：
以下与数据的存储结构无关的术语是（ ）。
选项：
A: 链表
B: 循环队列
C: 哈希表
D: 栈
答案: 【 栈】
8.9 哈希表（三）——冲突处理方法
1、单选题：
设有一组记录的关键字为 {19，14，26，1，68，20，46，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13，散列地址为1的链中有（ ）个记录。
选项：
A: 1
B: 2
C: 3
D: 4
答案: 【 3】
2、单选题：
假设有K个关键字互为同义词，若用线性探测法把这K个关键字存入哈希表中，至少要进行（ ）次探测。
选项：
A: K
B: 
C: K(K+1)/2
D: K(K-1)/2
答案: 【 K(K+1)/2】
3、单选题：
设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（ ）。
选项：
A: 3
B: 5
C: 8
D: 9
答案: 【 9】
4、多选题：
以下属于冲突处理方法的是（ ）。
选项：
A: 除留余数法
B: 直接定址法
C: 链地址法
D: 开放定址法
答案: 【 链地址法;
开放定址法】
5、判断题：
处理冲突的各种方法中，链地址法和公共溢出区法通常比开地址法的时间效率更高。
选项：
A: 正确
B: 错误
答案: 【 错误】
8.9 哈希表（二）——哈希函数的构造方法
1、单选题：
哈希函数有一个共同的性质，即函数应当以（ ）取其值域的每个值。
选项：
A: 最大概率
B: 最小概率
C: 平均概率
D: 同等概率
答案: 【 同等概率】
2、单选题：
设哈希表长度为 m，哈希函数 h(key)=key%p，为了减少发生冲突的可能性，一般取 p 为（ ）。
选项：
A: 小于m的最大奇数
B: 小于m的最小素数
C: 小于m的最大偶数
D: 小于m的最小合数
答案: 【 小于m的最小素数】
3、单选题：
关于哈希函数，以下说法错误的是（ ）。
选项：
A: 哈希函数的主要目的在于在元素和关键字之间建立一一对应的关系。
B: 哈希函数就是关键字本身。
C: 构造哈希函数时应尽量使关键字的所有组成部分都能起作用。
D: 同一组数据，可以使用不同的哈希函数得到不同的哈希表。
答案: 【 哈希函数就是关键字本身。】
8.9 哈希表（四）——查找及性能分析
1、单选题：
现有长度为 7、初始为空的散列表（哈希表）HT，散列函数 H(k)=k%7，用线性探测再散列法解决冲突。将关键字 22, 43, 15 依次插入到HT后，查找成功的平均查找长度是（ ）。
选项：
A: 1.5
B: 1.6
C: 2
D: 3
答案: 【 2】
2、单选题：
用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是（ ）。
选项：
A: 存储效率
B: 散列函数
C: 装填（装载）因子
D: 平均查找长度
答案: 【 平均查找长度】
3、多选题：
哈希表的平均查找长度和（ ）直接关系。
选项：
A: 哈希表记录类型
B: 哈希函数
C: 处理冲突的方法
D: 装填因子
答案: 【 哈希函数;
处理冲突的方法;
装填因子】
第十二周 查找（下） 单元测验
1、单选题：
在 19 个记录中查找其中的某个记录，若要求最多只需要进行 4 次关键字比较，则可采用的查找方法是（ ）。
选项：
A: 顺序查找
B: 折半查找
C: 哈希查找
D: 二叉排序树查找
E: 3阶B-树查找
F: 斐波那契查找
G: 差值查找
答案: 【 哈希查找;
3阶B-树查找】
2、单选题：
已知一棵 3 阶 B-树如下图所示，下列关于插入关键字 85 后的树形的表述中正确的有（ ）。
选项：
A: 树的高度将增加1层。
B: 第二层的结点个数增加到3。
C: 最底层最右边的非终端结点包含的关键字仍为80和90。
D: 最底层最左边的非终端结点包含的关键字不再只有5。
E: 关键字 85 被插入到第二层最右边的结点中。
F: 关键字 60 和 65 都位于最底层非终端结点中。
G: 关键字 80位于根结点中。
答案: 【 第二层的结点个数增加到3。;
关键字 85 被插入到第二层最右边的结点中。】
3、单选题：
下面关于 B-树和 B+ 树的叙述中，不正确的结论是 （ ） 。
选项：
A: B-树和B+树都能有效地支持顺序检索
B: B-树和B+树都能有效地支持随机检索
C: B-树和B+树都可用于文件的索引结构
D: B-树和B+树都是平衡的多路查找树
E: B-树和B+树都是动态索引结构
F: m阶的B-树和B+树中每个结点均最多只有m棵子树
G: m阶的B-树和B+树的分支结点在结构上是相同的。
答案: 【 B-树和B+树都能有效地支持顺序检索;
m阶的B-树和B+树的分支结点在结构上是相同的。】
4、单选题：
下面关于 B-树插入和删除操作的叙述中，正确的是（ ）。
选项：
A: 若插入过程中根结点发生分裂，则 B-树的高度加 1。
B: 每当进行插入操作，就需要在 B-树的最下面一层增加一个新结点。
C: 若要删除的关键码出现在根结点中，则不能真正删除，只能做标记。
D: 删除可能引起 B-树结点个数减少，但不会造成 B-树高度减小。
答案: 【 若插入过程中根结点发生分裂，则 B-树的高度加 1。】
5、多选题：
以下关于哈希表的叙述中正确的是（ ）。
选项：
A: 哈希冲突时指同一个关键字对应多个不同的哈希地址。
B: 若哈希表的装填因子小于1，则可避免冲突的产生。
C: 哈希函数构造的越复杂越好，因为这样随机性好，冲突小。
D: 不存在特别好与坏的哈希函数，要视情况而定。
E: 哈希表不需比较关键字即可查找到元素。
F: 哈希函数在关键字与哈希地址之间建立映像。
G: 不管采用何种处理冲突方法，都可直接删除元素。
H: 哈希表只能存储数据元素的值，不能存储数据元素之间的关系。
I: 用线性探测法解决冲突的散列表中，散列函数值相同的关键字总是存放在一片连续的存储单元中。
答案: 【 不存在特别好与坏的哈希函数，要视情况而定。;
哈希函数在关键字与哈希地址之间建立映像。;
哈希表只能存储数据元素的值，不能存储数据元素之间的关系。】
6、多选题：
已知待散列存储的关键字序列为（4,16,38,51,64,77），哈希函数为 H(key)=key%13，哈希表 HT 的长度为 13，采用二次探测再散列法解决冲突，下列关于由此构造的哈希表的表述中正确的有（ ）。
选项：
A: 关键字 77 的写入地址是 9。
B: 关键字 16 的写入地址是 3。
C: 关键字 4 的写入地址是 4。
D: 在等概率情况下查找成功的平均查找长度是 13/6 。
E: 关键字 38 的写入地址是 11。
F: 关键字 51 的写入地址是 0。
G: 关键字 64 的写入地址是 12。
H: 哈希地址 5~7 都是空闲的。
答案: 【 关键字 16 的写入地址是 3。;
关键字 4 的写入地址是 4。;
在等概率情况下查找成功的平均查找长度是 13/6 。;
关键字 51 的写入地址是 0。;
哈希地址 5~7 都是空闲的。】
（第一周） 第一章 绪论
1.1 什么是数据结构
1、多选题：
数据结构的研究对象主要包括：
选项：
A: 数据集合中元素之间的关系
B: 数据集合的存储实现方式
C: 对数据集合进行的操作
D: 操作算法优劣的评价
答案: 【 数据集合中元素之间的关系;
数据集合的存储实现方式;
对数据集合进行的操作;
操作算法优劣的评价】
2、判断题：
数据结构主要研究非数值计算的问题。
选项：
A: 正确
B: 错误
答案: 【 正确】
3、判断题：
数据结构的研究与计算机硬件无关。
选项：
A: 正确
B: 错误
答案: 【 错误】
1.2 数据结构的基本概念（一）——逻辑结构
1、单选题：
数据的逻辑结构是指 （ ）关系的整体。
选项：
A: 数据存储结构之间
B: 数据类型之间
C: 数据元素之间逻辑
D: 数据项之间逻辑
答案: 【 数据元素之间逻辑】
2、多选题：
以下说法不正确的是（ ）。
选项：
A: 数据可由若干个数据元素构成。
B: 数据项是不可分割的最小可标识单位。
C: 数据项可由若干个数据元素构成。
D: 数据元素是数据的最小单位。
答案: 【 数据项可由若干个数据元素构成。;
数据元素是数据的最小单位。】
3、多选题：
数据的逻辑结构可以分为（ ）。
选项：
A: 动态结构和静态结构
B: 线性结构和非线性结构
C: 内部结构和外部结构
D: 集合、线性结构、树形结构、图状结构
答案: 【 线性结构和非线性结构;
集合、线性结构、树形结构、图状结构】
1.2 数据结构的基本概念（二）——物理结构
1、单选题：
下面关于数据的逻辑结构与存储结构说法正确的是（ ）。
选项：
A: 逻辑结构要体现出存储结构。
B: 存储结构要体现出逻辑结构。
C: 两者是一一对应的。
D: 二者毫无关系。
答案: 【 存储结构要体现出逻辑结构。】
2、单选题：
在数据的存储中，一个结点通常存储一个（ ）。
选项：
A: 数据结构
B: 数据类型
C: 数据元素
D: 数据项
答案: 【 数据元素】
3、单选题：
在决定选取任何类型的存储结构时，一般不多考虑（ ）。
选项：
A: 对数据有哪些运算
B: 结点个数的多少
C: 各结点的具体取何值
D: 所用编程语言实现这种结构是否方便
答案: 【 各结点的具体取何值】
1.3 抽象数据类型
1、多选题：
下列关于抽象数据类型（ADT）定义的说法，正确的有（ ）。
选项：
A: ADT的定义只取决于它的一组逻辑特性。
B: ADT的定义与计算机内部如何表示和实现无关。
C: 不论ADT的内部结构如何变化，只要它的数学特性不变，都不影响它的外部使用。
D: ADT定义了一个完整的（狭义）数据结构。
答案: 【 ADT的定义只取决于它的一组逻辑特性。;
ADT的定义与计算机内部如何表示和实现无关。;
不论ADT的内部结构如何变化，只要它的数学特性不变，都不影响它的外部使用。;
ADT定义了一个完整的（狭义）数据结构。】
2、多选题：
调用下列test( )函数，能够在屏幕上输出“hello world”的是（ ）。
选项：
A: void GetMemory(char *p){ p = (char *)malloc(100);}void Test(void){ char *str = NULL; GetMemory(str); strcpy(str, "hello world"); printf(str);}
B: char *GetMemory(void){ char p[ ] = "hello world"; return p;}void Test(void){ char *str = NULL; str = GetMemory(); printf(str);}
C: void Test(void){ char *str = (char *) malloc(100); strcpy(str, "No!"); free(str); if (str != NULL) { strcpy(str, "hello world"); printf(str); }}
D: void GetMemory(char **p, int num){ *p = (char *)malloc(num);}void Test(void){ char *str = NULL; GetMemory(&str, 100); strcpy(str, "hello world"); printf(str);}
答案: 【 void Test(void){ char *str = (char *) malloc(100); strcpy(str, "No!"); free(str); if (str != NULL) { strcpy(str, "hello world"); printf(str); }};
void GetMemory(char **p, int num){ *p = (char *)malloc(num);}void Test(void){ char *str = NULL; GetMemory(&str, 100); strcpy(str, "hello world"); printf(str);}】
1.4 什么是算法
1、单选题：
计算机中算法是解决某一问题的有限运算序列，必须具备输入、输出、（ ）等5个特性。
选项：
A: 确定性、有穷性和健壮性
B: 可读性、正确性和健壮性
C: 可行性、正确性和可读性
D: 可行性、确定性和有穷性
答案: 【 可行性、确定性和有穷性】
2、单选题：
数据的运算（即操作） （ ）。
选项：
A: 在不同计算机上的实现方法都是相同的。
B: 必须用程序设计语言来描述
C: 与采用何种存储结构有关
D: 有算术运算和关系运算两大类
答案: 【 与采用何种存储结构有关】
3、多选题：
算法的设计目标有（ ）等等。
选项：
A: 可行性
B: 健壮性
C: 有穷性
D: 正确性
答案: 【 健壮性;
正确性】
1.5 算法的分析与度量
1、单选题：
算法分析的主要任务之一是分析（ ）。
选项：
A: 算法中是否存在语法错误
B: 算法的执行时间与问题规模之间的关系
C: 算法中输入和输出之间的关系
D: 算法是否具有较好的可读性
答案: 【 算法的执行时间与问题规模之间的关系】
2、单选题：
给出算法的时间复杂度是属于一种（ ）。
选项：
A: 事前统计的方法
B: 事前分析估算的方法
C: 事后统计的方法
D: 事后分析估算的方法
答案: 【 事前分析估算的方法】
3、单选题：
下述函数中时间复杂度最小的是（ ） 。
选项：
A: 
B: 
C: 
D: 
答案: 【 】
4、单选题：
下面程序段的时间复杂度是（ ）。i=1;while (i<=n) i=i*5;
选项：
A: 
B: n
C: 
D: 
答案: 【 】
第一周 绪论 单元测验
1、单选题：
某算法的时间复杂度为
。若该算法在规模为n的数据集上，运行时间为10秒；如果数据规模扩大为2n，该算法大约需要运行（ ）。
选项：
A: 10秒
B: 100秒
C: 6-7分钟
D: 以上都不对
答案: 【 以上都不对】
2、单选题：
以下函数中时间复杂度最小的是（ ）。
选项：
A: 
B: 
C: 
D: 
E: 
F: 
G: 
答案: 【 ;】
3、单选题：
下列程序段的时间复杂度是（ ）。count=0;for (k=1;k<=n;k*=2) for (j=1;j<=n;j+1) count++;
选项：
A: 
B: 
C: 
D: 
答案: 【 】
4、单选题：
下列程序段的时间复杂度是（ ）。int k=0,j=0;while (j<=n) {
k++; j+=k;
}
选项：
A:
B:
C: 
D: 
E:
答案: 【 】
5、单选题：
下面的数据结构是（ ）。DS=(D,R)，其中D={a,b,c,d,e}，R={r}，r={<a,b>,<a,e>,<b,c>,<d,e>}。注：“<>"表示有序对。
选项：
A: 集合
B: 线性结构
C: 树形结构
D: 图状结构
E: 顺序存储结构
F: 链式存储结构
答案: 【 图状结构】
6、多选题：
下列关于算法的叙述正确的是（ ）。
选项：
A: 算法的有穷性是指算法必须能在执行有限个步骤之后终止。
B: 算法的时间复杂度与空间复杂度紧密相关。
C: 算法的效率只与问题规模有关，而与数据的存储结构无关。
D: 用不同算法求解同一问题的时间复杂度不同。
E: 算法的优劣与算法描述语言无关，与所用计算机也无关。
F: 算法原地工作的含义是指该算法不需要任何额外的辅助空间。
G: 对于相同规模的n，时间复杂度O(n)的算法运行时间总是小于时间复杂度
的算法的运行时间。
H: 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。
答案: 【 算法的有穷性是指算法必须能在执行有限个步骤之后终止。;
算法的优劣与算法描述语言无关，与所用计算机也无关。;
所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。】
7、多选题：
下列叙述正确的是（ ）。
选项：
A: 数据元素是数据项中不可分割的最小可标识单位。
B: 从逻辑上可以把数据结构分为顺序结构、链式结构等类别。
C: 研究数据结构就是研究数据的逻辑结构和存储结构。
D: 数据类型可看成是程序设计语言中已实现的数据结构。
E: 数据元素之间的关联关系在数据的逻辑结构中体现。
F: 数据对象是由有限个类型相同的数据元素构成的。
G: 逻辑结构不相同的数据，必须采用不同类型的存储方法。
H: 如果数据元素值发生改变，则数据的逻辑结构也随之改变。
I: 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
答案: 【 数据类型可看成是程序设计语言中已实现的数据结构。;
数据元素之间的关联关系在数据的逻辑结构中体现。;
数据对象是由有限个类型相同的数据元素构成的。;
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。】
（第七周） 第六章 树和二叉树（上）
6.1 树的定义
1、单选题：
在一棵度为 3 的树上，度为 3 的结点数为 3 个，度为 2 的结点数为 2 个，度为 1 的结点数为 2 个，则度为 0 的结点数为（ ）个。
选项：
A: 不确定
B: 8
C: 9
D: 10
答案: 【 9】
2、单选题：
树最适合用来表示（ ）。
选项：
A: 有序数据元素
B: 无序数据元素
C: 元素之间具有分支层次关系的数据
D: 元素之间无联系的数据
答案: 【 元素之间具有分支层次关系的数据】
3、单选题：
假设一棵树的嵌套括号表示为 (a(b(e),c(f(h,i,j),g),d))，则该树上终端结点的个数为（ ）。
选项：
A: 4
B: 5
C: 6
D: 7
答案: 【 6】
4、单选题：
一棵含有 n 个结点的 m (m>=3) 叉树，其分支数为（ ）。
选项：
A: mn
B: n+m
C: n-1
D: 无法确定
答案: 【 n-1】
6.2 二叉树（一）——定义和性质
1、单选题：
一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。
选项：
A: 250
B: 500
C: 254
D: 501
答案: 【 501】
2、单选题：
深度为6（根的层次为1）的二叉树至多有( )个结点。
选项：
A: 62
B: 63
C: 64
D: 65
答案: 【 63】
3、单选题：
设高度为 h 的二叉树中只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点上下限分别为（ ）。
选项：
A: 
B: 
C: 
D: 
答案: 【 】
4、多选题：
在一棵含有 n 个结点的二叉树中，若度为 2 的结点数为 
，度为 1 的结点数为 
，度为 0 的结点数为 
，则该树的最大高度为（ ）。
选项：
A: n
B: 
C: 
D: 
答案: 【 n;
】
5、填空题：
4个结点的二叉树可以有 种不同的形态。
答案: 【 14】
6.2 二叉树（二）——存储结构
1、单选题：
假设二叉树的顺序存储结构如下图所示：1234567891011121314abcÆdÆeÆÆfgÆÆh则该二叉树的中序遍历序列为（ ）。
选项：
A: fdgbache
B: bfdgache
C: bfdgahec
D: fdgbahec
答案: 【 bfdgache】
2、单选题：
含有 n 个结点的二叉树采用顺序存储结构，至少需要分配（ ）个存储单元。
选项：
A: n
B: 2n
C: 
D: 
答案: 【 】
3、单选题：
含有 n 个结点的二叉树，若采用二叉链表存储，则整个存储结构中只有（ ）个非空指针域。
选项：
A: n-1
B: n
C: n+1
D: 不确定
答案: 【 n-1】
4、单选题：
含有 n 个结点的二叉树，若采用三叉链表存储，则整个存储结构中有（ ）个空的指针域。
选项：
A: n-1
B: n
C: n+1
D: n+2
答案: 【 n+2】
6.3 二叉树的遍历（一）——递归算法
1、单选题：
任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序（ ）。
选项：
A: 不发生变化
B: 发生变化
C: 不能确定
D: 以上都不对
答案: 【 不发生变化】
2、单选题：
某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是（ ）的二叉树。
选项：
A: 空或只有一个结点
B: 高度等于其结点数
C: 任一结点无左孩子
D: 任一结点无右孩子
答案: 【 高度等于其结点数】
3、单选题：
在一非空二叉树的中序遍历序列中，根结点的右边（ ）。
选项：
A: 只有右子树上的所有结点
B: 只有右子树上的部分结点
C: 只有左子树上的部分结点
D: 只有左子树上的所有结点
答案: 【 只有右子树上的所有结点】
6.3 二叉树的遍历（三）——应用
1、单选题：
设一棵二叉树的中序遍历序列为 BDCAE，后序遍历序列为 DBEAC，则这棵二叉树的前序遍历序列为（ ）。
选项：
A: CAEBD
B: CDBEA
C: CBDAE
D: CBDEA
答案: 【 CBDAE】
2、单选题：
设一棵二叉树的先序遍历序列为 ABCDEFG，中后序遍历序列为 BDCEAGF，则这棵二叉树的后序遍历序列为（ ）。
选项：
A: CABDEFG
B: DACEFBG
C: DECBGFA
D: ADCFEG
答案: 【 DECBGFA】
3、单选题：
设一棵二叉树的扩展后序遍历序列为 
，则这棵二叉树的前序和中序遍历序列分别为（ ）。
选项：
A: ABCDEFG 和 DECBGFA
B: ABCDEFG 和 BDCEAG
C: AFGBDEC和 CBEDAFG
D: ABCDEFG 和 CBEDAFG
答案: 【 ABCDEFG 和 CBEDAFG】
第七周 第六章树和二叉树（上） 单元测验
1、单选题：
已知一棵二叉树有10个结点，则其中至多有（ ）个结点有两个子结点。
选项：
A: 3
B: 4
C: 5
D: 6
E: 1
F: 7
答案: 【 4】
2、单选题：
若二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJKG，则该二叉树的右子树的根是（ ）。
选项：
A: E
B: F
C: G
D: H
E: I
F: J
G: K
答案: 【 G】
3、单选题：
若一个深度为 3 的二叉树的先序遍历为 ABCDE，则该二叉树有（ ）种可能的形态。
选项：
A: 3
B: 4
C: 5
D: 6
E: 7
F: 8
答案: 【 6】
4、单选题：
下列关于二叉树的叙述中，正确的有（ ）。
选项：
A: n (n>2) 个结点的二叉树中至少有一个度为 2 的结点。
B: 任何一棵完全二叉树中，叶子结点或者和分支结点一样多，或者只比分支结点多一个。
C: 二叉树就是度为 2 的树。
D: 完全二叉树最适合采用顺序存储结构。
E: 满二叉树中的所有棵子树都是完全二叉树。
F: 完全二叉树中，若某个结点无左孩子，则其必为叶子。
G: 在叶子数目和权值均相同的所有二叉树中，最优二叉树一定是完全二叉树。
答案: 【 任何一棵完全二叉树中，叶子结点或者和分支结点一样多，或者只比分支结点多一个。;
完全二叉树最适合采用顺序存储结构。;
满二叉树中的所有棵子树都是完全二叉树。;
完全二叉树中，若某个结点无左孩子，则其必为叶子。】
5、