MOOC 数据结构(北京交通大学)1450299328 最新慕课完整章节测试答案
第一章 绪论
第一章单元测试1
1、单选题:
______ 是数据的最小单位。
选项:
A: 数据项
B: 数据元素
C: 信息项
D: 表元素
答案: 【 数据项】
2、单选题:
以下说法不正确的是 ______。
选项:
A: 数据项可由若干个数据元素构成
B: 数据可由若干个数据元素构成
C: 数据元素是数据的基本单位
D: 数据项是不可分割的最小标识单位
答案: 【 数据项可由若干个数据元素构成】
3、单选题:
数据结构是指 ______ 的集合以及它们之间的关系。
选项:
A: 数据元素
B: 计算方法
C: 结构
D: 数据
答案: 【 数据元素】
4、单选题:
计算机所处理的数据一般具备某种内在联系,这是指 ______。
选项:
A: 元素和元素之间存在某种关系
B: 元素内部具有某种结构
C: 数据项和数据项之间存在某种关系
D: 数据和数据之间存在某种关系
答案: 【 元素和元素之间存在某种关系】
5、单选题:
在数据结构中,与所使用的计算机无关的是数据的 ______ 结构。
选项:
A: 逻辑
B: 物理
C: 存储
D: 逻辑和存储
答案: 【 逻辑】
6、单选题:
数据的逻辑结构是指 ______ 关系的整体。
选项:
A: 数据元素之间逻辑
B: 数据项之间逻辑
C: 数据类型之间
D: 存储结构之间
答案: 【 数据元素之间逻辑】
7、单选题:
在计算机中存储数据时,通常不仅要存储各数据元素的值,而且还有存储 ______。
选项:
A: 数据元素之间的关系
B: 数据的处理方法
C: 数据元素的类型
D: 数据的存储方法
答案: 【 数据元素之间的关系】
8、单选题:
数据结构在计算机内存中的表示是指 ______。
选项:
A: 数据的存储结构
B: 数据的逻辑结
C: 数据结构
D: 数据元素之间的关系
答案: 【 数据的存储结构】
9、单选题:
在数据的存储中,一个结点通常存储一个 ______。
选项:
A: 数据元素
B: 数据结构
C: 数据类型
D: 数据项
答案: 【 数据元素】
10、单选题:
在决定选取任何类型的存储结构时,一般不多考虑 ______。
选项:
A: 各节点的值如何
B: 节点个数的多少
C: 对数据有哪些运算
D: 所用编程语言实现这种结构是否方便
答案: 【 各节点的值如何】
11、判断题:
数据对象就是一组任意数据元素的集合。
选项:
A: 正确
B: 错误
答案: 【 错误】
12、判断题:
如果数据元素值发生改变,则数据的逻辑结构也随之改变。
选项:
A: 正确
B: 错误
答案: 【 错误】
13、判断题:
逻辑结构相同的数据,可以采用多种不同的存储方法。
选项:
A: 正确
B: 错误
答案: 【 正确】
14、判断题:
逻辑结构不相同的数据,必须采用多种不同的存储方法。
选项:
A: 正确
B: 错误
答案: 【 错误】
15、判断题:
数据的逻辑结构是指数据的各数据项之间的逻辑关系。
选项:
A: 正确
B: 错误
答案: 【 错误】
第一章单元测试2
1、单选题:
计算机中算法指的是解决某一问题的有限运算序列,它必须具备输入、输出、_______。
选项:
A: 可行性、有穷性和确定性
B: 可行性、可移植性和可扩充性
C: 确定性、有穷性和稳定性
D: 易读性、稳定性和确定性
答案: 【 可行性、有穷性和确定性】
2、单选题:
一个算法具有 ________ 等设计目标。
选项:
A: 健壮性
B: 可行性
C: 至少有一个输入
D: 确定性
答案: 【 健壮性】
3、单选题:
以下关于算法的说法正确的是 ____________。
选项:
A: 其他几个都是错误的
B: 算法最终必须由计算机程序实现
C: 算法等同于程序
D: 算法的可行性是指指令不能有二义性
答案: 【 其他几个都是错误的】
4、单选题:
算法的时间复杂度与 _______ 有关。
选项:
A: 问题规模
B: 计算机硬件性能
C: 编译程序质量
D: 程序设计语言
答案: 【 问题规模】
5、单选题:
算法分析的主要任务之一是分析 _______。
选项:
A: 算法的执行时间和问题规模之间的关系
B: 算法是否具有较好地可读性
C: 算法中是否存在语法错误
D: 算法的功能是否符合设计要求
答案: 【 算法的执行时间和问题规模之间的关系】
6、单选题:
算法的时间复杂度为O(),表明该算法的 _______。
选项:
A: 执行时间与成正比
B: 问题规模是
C: 执行时间等于
D: 问题规模与成正比
答案: 【 执行时间与成正比】
7、单选题:
算法分析的目的是 _______。
选项:
A: 分析算法的效率以求改进
B: 找出数据结构的合理性
C: 研究算法中输入和输出的关系
D: 分析算法的易读性和文档性
答案: 【 分析算法的效率以求改进】
8、单选题:
以下函数中时间复杂度最小的是 _______。
选项:
A: T4(n)=20000log2n
B: T1(n)=nlog2n+5000n
C: T2(n)=-8000n
D:
T3(n)=-6000n
答案: 【 T4(n)=20000log2n】
9、单选题:
以下说法中错误的是 _______。
(1)原地工作算法的含义是指不需要任何额外的辅助空间
(2)在相同的问题规模下n下,时间复杂度为O(nlog2n)的算法在执行时间上总是优于时间复杂度为O()的算法
(3)时间复杂度通常是指最坏情况下,估计算法执行时间的一个上限
(4)一个算法的时间复杂度与实现算法的语言无关
选项:
A: (1)、(2)
B: (1)
C: (1)、(4)
D: (3)
答案: 【 (1)、(2)】
10、单选题:
下面程序的时间复杂度为 _______。void fun( int n) { int i=1; while (i<=n) i=i*2}
选项:
A: O(log2n)
B: O(n)
C: O()
D: O(nlog2n)
答案: 【 O(log2n)】
11、单选题:
void fun( int n) { int i=1, k=100; while (i<=n) {k++; i+=2;}}
选项:
A: O(n)
B: O()
C: O(log2n)
D: O(nlog2n)
答案: 【 O(n)】
12、单选题:
下面程序的时间复杂为 _______。for(i=1,s=0; i<=n; i++) { t=1; for(j=1;j<=i;j++) t=t*j;s=s+t;}
选项:
A: O()
B: O(n)
C: O()
D: O()
答案: 【 O()】
13、判断题:
算法的优劣与算法描述语言无关,但与所用的计算机有关。
选项:
A: 正确
B: 错误
答案: 【 错误】
14、判断题:
健壮的算法不会因非法输入数据而出现莫名其妙的状态。
选项:
A: 正确
B: 错误
答案: 【 正确】
15、判断题:
程序一定是算法。
选项:
A: 正确
B: 错误
答案: 【 错误】
第一章绪论单元测试
1、单选题:
______ 是数据的最小单位。
选项:
A: 数据项
B: 数据元素
C: 数据对象
D: 表元素
答案: 【 数据项】
2、单选题:
以下说法不正确的是 ______。
选项:
A: 数据可由若干个数据元素构成
B: 数据项可由若干个数据元素构成
C: 数据元素是数据的基本单位
D: 数据项是不可分割的最小标识单位
答案: 【 数据项可由若干个数据元素构成 】
3、单选题:
数据结构是指 ______ 的集合以及它们之间的关系。
选项:
A: 计算方法
B: 数据元素
C: 结构
D: 数据
答案: 【 数据元素】
4、单选题:
计算机所处理的数据一般具备某种内在联系,这是指 ______。
选项:
A: 数据元素内部具有某种结构
B: 数据项和数据项之间存在某种关系
C: 数据元素和数据元素之间存在某种关系
D: 数据和数据之间存在某种关系
答案: 【 数据元素和数据元素之间存在某种关系 】
5、单选题:
在数据结构中,与所使用的计算机无关的是数据的 ______ 结构。
选项:
A: 物理
B: 逻辑和存储
C: 存储
D: 逻辑
答案: 【 逻辑】
6、单选题:
在数据结构中,可以把数据的逻辑结构分为 ______ 两类。
选项:
A: 紧凑结构和非紧凑结构
B: 动态结构和静态结构
C: 内部结构和外部结构
D: 线性结构和非线性结构
答案: 【 线性结构和非线性结构】
7、单选题:
数据的逻辑结构是指 ______ 关系的整体。
选项:
A: 数据元素之间逻辑
B: 数据项之间逻辑
C: 数据类型之间
D: 存储结构之间
答案: 【 数据元素之间逻辑】
8、单选题:
在计算机中存储数据时,通常不仅要存储各数据元素的值,而且还有存储 ______。
选项:
A: 数据的处理方法
B: 数据元素的类型
C: 数据元素之间的关系
D: 数据的存储方法
答案: 【 数据元素之间的关系】
9、单选题:
数据结构在计算机中的表示是指 ______。
选项:
A: 数据的存储结构
B: 数据元素的值
C: 数据的逻辑结构
D: 数据元素之间的关系
答案: 【 数据的存储结构】
10、单选题:
在数据的存储中,一个结点通常存储一个 ______。
选项:
A: 数据结构
B: 数据类型
C: 数据元素
D: 数据项
答案: 【 数据元素】
11、单选题:
在决定选取任何类型的存储结构时,一般不多考虑 ______。
选项:
A: 数据的值如何
B: 数据量的大小
C: 对数据进行哪些运算
D: 所用编程语言实现这种结构是否方便
答案: 【 数据的值如何】
12、单选题:
数据在计算机的存储器中表示时,逻辑上相邻的两个元素对应的物理地址也是相邻的,这种存储结构称之为 ______。
选项:
A: 索引结构
B: 顺序存储结构
C: 链式存储结构
D: 以上都对
答案: 【 顺序存储结构】
13、单选题:
_______ 不是算法的基本特性。
选项:
A: 可行性
B: 有穷性
C: 健壮性
D: 确定性
答案: 【 健壮性】
14、单选题:
计算机中算法指的是解决某一问题的有限运算序列,它必须具备输入、输出、_______。
选项:
A: 可行性、可移植性和可扩充性
B: 可行性、有穷性和确定性
C: 确定性、有穷性和稳定性
D: 易读性、稳定性和确定性
答案: 【 可行性、有穷性和确定性】
15、单选题:
一个算法具有 ________ 等设计目标。
选项:
A: 可行性
B: 至少有一个输入
C: 确定性
D: 健壮性
答案: 【 健壮性】
16、单选题:
以下关于算法的说法正确的是 ____________。
选项:
A: 算法最终必须由计算机程序实现
B: 算法等同于程序
C: 算法的可行性是指指令不能有二义性
D: 其他几个都是错误的
答案: 【 其他几个都是错误的】
17、单选题:
算法的时间复杂度与 _______ 有关。
选项:
A: 问题规模
B: 计算机硬件性能
C: 编译程序质量
D: 程序设计语言
答案: 【 问题规模】
18、单选题:
算法分析的主要任务之一是分析 _______。
选项:
A: 算法是否具有较好地可读性
B: 算法中是否存在语法错误
C: 算法的功能是否符合设计要求
D: 算法的执行时间和问题规模之间的关系
答案: 【 算法的执行时间和问题规模之间的关系】
19、单选题:
算法的时间复杂度为O(n2),表明该算法的 _______。
选项:
A: 问题规模是
B: 执行时间等于
C: 执行时间与成正比
D: 问题规模与成正比
答案: 【 执行时间与成正比】
20、单选题:
算法分析的目的是 _______。
选项:
A: 找出数据结构的合理性
B: 研究算法中输入和输出的关系
C: 分析算法的效率以求改进
D: 分析算法的易读性和文档性
答案: 【 分析算法的效率以求改进】
21、单选题:
以下函数中时间复杂度最小的是 _______。
选项:
A: T1(n)=nlog2n+5000n
B: T2(n)=-8000n
C: T3(n)=-6000n
D: T4(n)=20000log2n
答案: 【 T4(n)=20000log2n】
22、单选题:
以下函数中时间复杂度最小的是 _______。
选项:
A: T1(n)=1000log2n
B: T2(n)=-1000log2n
C: T3(n)=- 1000log2n
D: T4(n)=2nlog2n-1000log2n
答案: 【 T1(n)=1000log2n 】
23、单选题:
以下说法中错误的是 _______。
(1)原地工作算法的含义是指不需要任何额外的辅助空间
(2)在相同的问题规模下n下,时间复杂度为O(nlog2n)的算法在执行时间上总是优于时间复杂度为O()的算法
(3)时间复杂度通常是指最坏情况下,估计算法执行时间的一个上限
(4)一个算法的时间复杂度与实现算法的语言无关
选项:
A: (1)
B: (1)、(2)
C: (1)、(4)
D: (3)
答案: 【 (1)、(2)】
24、单选题:
下面程序的时间复杂为 _______。for(i=1,s=0; i<=n; i++) {t=1;for(j=1;j<=i;j++) t=t*j;s=s+t;}
选项:
A: O(n)
B: O()
C: O( )
D: O()
答案: 【 O()】
25、单选题:
一个算法的时间复杂度为(+log2n+14n)/,其数量级表示为 _______。
选项:
A: O(n)
B: O()
C: O()
D: O()
答案: 【 O(n) 】
26、单选题:
下面程序的时间复杂度为 _______。void fun( int n) { int i=1; while (i<=n) i=i*2}
选项:
A: O(n)
B: O()
C: O(log2n)
D: O(nlog2n)
答案: 【 O(log2n)】
27、单选题:
下面程序的时间复杂度为 _______。void fun( int n) { int i=1, k=100; while (i<=n) {k++; i+=2;} }
选项:
A: O(n)
B: O()
C: O(log2n)
D: O(nlog2n)
答案: 【 O(n)】
28、判断题:
数据元素是数据的最小单位。
选项:
A: 正确
B: 错误
答案: 【 错误】
29、判断题:
数据对象就是一组任意数据元素的集合。
选项:
A: 正确
B: 错误
答案: 【 错误】
30、判断题:
数据的逻辑结构与数据元素在计算机中如何存储有关。
选项:
A: 正确
B: 错误
答案: 【 错误】
31、判断题:
如果数据元素值发生改变,则数据的逻辑结构也随之改变。
选项:
A: 正确
B: 错误
答案: 【 错误】
32、判断题:
逻辑结构相同的数据,可以采用多种不同的存储方法。
选项:
A: 正确
B: 错误
答案: 【 正确】
33、判断题:
逻辑结构不相同的数据,必须采用多种不同的存储方法。
选项:
A: 正确
B: 错误
答案: 【 错误】
34、判断题:
数据的逻辑结构时指数据的各数据项之间的逻辑关系。
选项:
A: 正确
B: 错误
答案: 【 错误】
35、判断题:
算法的优劣与算法描述语言无关,但与所用的计算机有关。
选项:
A: 正确
B: 错误
答案: 【 错误】
36、判断题:
程序一定是算法。
选项:
A: 正确
B: 错误
答案: 【 错误】
37、判断题:
算法最终必须由计算机程序实现.
选项:
A: 正确
B: 错误
答案: 【 错误】
38、判断题:
算法的可行性是指指令不能有二义性。
选项:
A: 正确
B: 错误
答案: 【 错误】
39、判断题:
健壮的算法不会因非法输入数据而出现莫名其妙的状态。
选项:
A: 正确
B: 错误
答案: 【 正确】
第二章 线性表
第二章线性表单元测试
1、单选题:
线性表是具有n个 ______ 的有限序列。
选项:
A: 表元素
B: 字符
C: 数据元素
D: 数据项
答案: 【 数据元素】
2、单选题:
线性表是 _______。
选项:
A: 一个有限序列,可以为空
B: 一个有限序列不可以为空
C: 一个无限序列,可以为空
D: 一个无限序列,不可以为空
答案: 【 一个有限序列,可以为空】
3、单选题:
关于线性表的正确说法是 _______。
选项:
A: 每个元素都有一个前驱和一个后继元素
B: 线性表中至少有一个元素
C: 表中元素的排序顺序必须是由小到大或由大到小
D: 除第一个元素和最后一个元素外,其余元素有且仅有一个前驱和一个后继元素
答案: 【 除第一个元素和最后一个元素外,其余元素有且仅有一个前驱和一个后继元素】
4、单选题:
线性表采用链表存储时,其存放各个元素的单元地址是 _______。
选项:
A: 必须是连续的
B: 一定是不连续的
C: 部分地址必须是连续的
D: 连续与否均可以
答案: 【 连续与否均可以】
5、单选题:
链表不具备的特点是 _______。
选项:
A: 可随机访问任一节点
B: 插入删除不需要移动元素
C: 不必事先估计存储空间
D: 所需空间与其长度成正比
答案: 【 可随机访问任一节点】
6、单选题:
线性表的静态链表存储结构与顺序存储结构相比,优点是 _______。
选项:
A: 所有的操作算法实现简单
B: 便于随机存取
C: 便于插入和删除
D: 便于利用零散的存储器空间
答案: 【 便于插入和删除】
7、单选题:
线性表的顺序存储结构和链式存储结构相比,优点是 _______。
选项:
A: 所有的操作算法实现简单
B: 便于随机存取
C: 便于插入和删除
D: 节省存储空间
答案: 【 便于随机存取 】
8、单选题:
设线性表有n个元素,以下操作中,_______在顺序表上实现比在链表上实现效率高。
选项:
A: 输入第i(1<=i<=n)个元素值
B: 交换第1个元素第2个元素的值
C: 顺序输出这n个元素的值
D: 输出与给定值x相等的元素在线性表中的符号
答案: 【 输入第i(1<=i<=n)个元素值】
9、单选题:
设线性表中有n个元素,以下操作,_______ 在单链表上实现要比在顺序表上实现效率高。
选项:
A: 删除指定位置元素的后一个元素
B: 在第n个元素的后面插入一个新元素
C: 顺序输出前k个元素
D: 交换第i个元素和第n-i+1个元素的值
答案: 【 删除指定位置元素的后一个元素】
10、单选题:
以下属于顺序表的优点是 _______。
选项:
A: 插入元素方便
B: 删除元素方便
C: 存储密度大
D: 以上都不对
答案: 【 存储密度大】
11、单选题:
要求线性表采用静态空间分配方式,且插入和删除操作时不需要移动元素,采用的存储结构是 _______。
选项:
A: 单链表
B: 静态链表
C: 双链表
D: 顺序表
答案: 【 静态链表】
12、单选题:
如果最常用的操作是取第i个元素及前驱元素,则采用 _______ 存储方式最节省时间。
选项:
A: 单链表
B: 双链表
C: 循环单链表
D: 顺序表
答案: 【 顺序表】
13、单选题:
与单链表相比,双链表的优点之一是 _______。
选项:
A: 插入、删除操作更简单
B: 可以进行随机访问
C: 可以省略表头指针或表尾指针
D: 访问前后相邻结点更方便
答案: 【 访问前后相邻结点更方便】
14、单选题:
在长度为n的顺序表中插入一个元素的时间复杂度为 _______。
选项:
A: O(n)
B: O()
C: O(log2n)
D: O(1)
答案: 【 O(n) 】
15、单选题:
在长度为n的顺序表中删除一个元素的时间复杂度为 _______。
选项:
A: O(1)
B: O()
C: O(log2n)
D: O(n)
答案: 【 O(n)】
16、单选题:
在两个各有n个元素的递增有序顺序表归并成一个有序顺序表,其最少的比较次数为_______。
选项:
A: n
B: 2n-1
C: 2n
D: n-1
答案: 【 n】
17、单选题:
将两个长度为n、m的递增有序表归并成一个有序顺序表,其最少的比较次数是_______。(MIN表示取最小值)
选项:
A: n
B: m
C: MIN(m, n)
D: 不确定
答案: 【 MIN(m, n)】
18、单选题:
在带头结点的单链表L为空的判定条件是 _______。
选项:
A: L==NULL
B: L->NEXT==NULL
C: L->NEXT==L
D: L!=NULL
答案: 【 L->NEXT==NULL】
19、单选题:
对于一个具有n个元素的线性表,建立其单链表的时间复杂度为 _______。
选项:
A: O(log2n)
B: O(1)
C: O(n)
D: O()
答案: 【 O(n)】
20、单选题:
在单链表中查找指定值的结点的时间复杂度是 _______。
选项:
A: O(log2n)
B: O(1)
C: O()
D: O(n)
答案: 【 O(n)】
21、单选题:
以下关于单链表的叙述中,不正确的是 _______。
选项:
A: 结点除自身信息外还包括指针域,因此存储密度小于顺序存储结构
B: 逻辑上相邻的元素物理上不必相邻
C: 可以通过头结点直接计算第i个结点的存储地址
D: 插入、删除运算操作简单,不必移动结点
答案: 【 可以通过头结点直接计算第i个结点的存储地址】
22、单选题:
在单链表中,增加一个头结点的目的是为了 _______。
选项:
A: 使单链表至少有一个结点
B: 标识链表中重要结点的位置
C: 方便运算的实现
D: 说明单链表是线性表的链式存储结构
答案: 【 方便运算的实现 】
23、单选题:
在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 _______。
选项:
A: O(nlog2n)
B: O(1)
C: O(n)
D: O()
答案: 【 O(n)】
24、单选题:
将长度为m的单链表链接在长度为n的单链表之后的算法时间复杂度为 _______。
选项:
A: O(1)
B: O(n)
C: O(m)
D: O(m+n)
答案: 【 O(n)】
25、单选题:
已知一个长度为n的单链表中所有结点是递增有序的,以下叙述中正确的是 _______。
选项:
A: 插入一个结点使之有序的算法的时间复杂度为O(1)
B: 删除最大值结点使之有序的算法的时间复杂度为 O(1)
C: 找最小值结点的算法的时间复杂度为 O(1)
D: 以上都不对
答案: 【 找最小值结点的算法的时间复杂度为 O(1)】
26、单选题:
在一个长度为n(n>1)的带头结点的单链表上,另设有尾指针r(指向尾结点),执行_______操作与链表的长度有关。
选项: