大学MOOC 数据结构(中国传媒大学)1206073804 最新慕课完整章节测试答案
第一章绪论
第一章绪论单元测验
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、单选题：
下面算法的时间复杂度为____________。char Compare ( SimpleType x1, SimpleType x2 ) { if ( x1 > x2 ) return‘>’; else if ( x1 == x2 ) return ‘=’; else return‘<’; }
选项：
A: 
B: 
C: 
D: 
答案: 【 】
12、单选题：
下面算法的时间复杂度是_____________。 设n为3的倍数，且void fun(int n) {int i, j, x, y; for (i = 1; i <=n; i ++){if (3 * i <=n) { for (j = 3 * i; j <= n; j ++){ x ++; y = 3 * x + 2; }} } }
选项：
A: 
B: 
C: 
D: 
答案: 【 】
13、判断题：
任何数据结构都具备三个基本运算：插入、删除和查找。
选项：
A: 正确
B: 错误
答案: 【 正确】
14、判断题：
数据的逻辑结构与各数据元素在计算机中如何存储有关。
选项：
A: 正确
B: 错误
答案: 【 错误】
15、判断题：
数据的逻辑结构是指数据的各数据项之间的逻辑关系。
选项：
A: 正确
B: 错误
答案: 【 错误】
16、判断题：
数据结构、数据元素、数据项在计算机中的映像（或表示）分别称为存储结构、结点结构和数据域。typedef struct LNode { ElemType data; Struct LNode *next;}LNode, *LinkList;
选项：
A: 正确
B: 错误
答案: 【 正确】
17、判断题：
数据的逻辑结构可以独立于存储结构来考虑。
选项：
A: 正确
B: 错误
答案: 【 正确】
18、判断题：
在算法的评价标准中，正确性指的是算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。
选项：
A: 正确
B: 错误
答案: 【 错误】
19、判断题：
已知一个程序的时间复杂度为
，其中以串行方式（即非嵌套方式）先后调用了两个子函数，一个子函数的时间复杂度为
，另外一个子函数的时间复杂度为
，因此整个程序的时间复杂度为
。
选项：
A: 正确
B: 错误
答案: 【 错误】
20、判断题：
计算算法的时间复杂度属于事前分析估算的方法。
选项：
A: 正确
B: 错误
答案: 【 正确】
21、填空题：
在顺序表、哈希表、有序表和单链表中，属于逻辑结构的是__________。
答案: 【 有序表】
22、填空题：
数据的存储结构包括顺序存储、链式存储、散列存储和___________。
答案: 【 索引存储】
23、填空题：
数据的存储结构是数据的____________在计算机内的表示，前者依赖于后者。
答案: 【 逻辑结构】
24、填空题：
数据类型是值的集合和定义在这个值集上的一组___________的总称。
答案: 【 操作】
25、填空题：
在算法的评价标准中， _________性指的是算法的逻辑必须是清晰的、简单的和结构化的，所有的变量名、函数名必须有实际含义，且算法中必须加入注释。
答案: 【 可读】
第二章线性表
第二章线性表单元测验
1、单选题：
在一个长度为n的顺序表中向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要向后移动_____ 个元素。
选项：
A: n-i
B: n-i+1
C: n-i-1
D: i
答案: 【 n-i+1 】
2、单选题：
链表不具有的特点是_____ 。
选项：
A: 可随机访问任一元素
B: 插入元素不需要移动元素
C: 不必事先估计存储空间
D: 所需空间与线性表的长度成正比
答案: 【 可随机访问任一元素】
3、单选题：
在线性表的下列存储结构中，读取指定序号的元素花费时间最少的是_____ 。
选项：
A: 单链表
B: 双向链表
C: 循环链表
D: 顺序表
答案: 【 顺序表】
4、单选题：
对于用一维数组 d [1..n]顺序存储的线性表，其算法时间复杂度为O(1)的操作是_____ 。
选项：
A: 将n个元素从小到大排序
B: 从线性表中删除第i个元素（1≤i≤n）
C: 查找第i个元素（1≤i≤n）
D: 向线性表的第i个元素之后插入一个元素（0≤i≤n）
答案: 【 查找第i个元素（1≤i≤n）】
5、单选题：
静态链表（使用数组来存储的链表）中结点内指针指示的是_____ 。
选项：
A: 内存地址
B: 数组下标
C: 链表中下一个元素在数组中的地址
D: 左、右孩子地址
答案: 【 链表中下一个元素在数组中的地址】
6、单选题：
单链表L为空的判断条件是_____ 。
选项：
A: L==NULL
B: L->next==NULL
C: L->next!=NULL
D: L!=NULL
答案: 【 L->next==NULL】
7、单选题：
某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_____ 存储方式最节省时间。
选项：
A: 单链表
B: 不带头结点且仅有头指针的单循环链表
C: 双向（非循环）链表
D: 不带头结点且仅有尾指针（指向终端结点的指针）的单循环链表
答案: 【 不带头结点且仅有尾指针（指向终端结点的指针）的单循环链表】
8、单选题：
在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_____ 。
选项：
A: O(1)
B: O(n)
C: O(
)
D: O(
)
答案: 【 O(n)】
9、单选题：
将两个有n个元素的有序表归并成一个有序表，其最多比较次数为_____ 。
选项：
A: n
B: 2n-1
C: 2n
D: n-1
答案: 【 2n-1】
10、单选题：
在一个长度为n（n>1）的带头结点的单链表h上，另设有尾指针r（指向尾结点），执行以下 操作与链表的长度有关。
选项：
A: 删除单链表中的第一个结点
B: 删除单链表中的最后一个结点
C: 在单链表第一个结点前插入一个新结点
D: 在单链表最后一个结点后插入一个新结点
答案: 【 删除单链表中的最后一个结点】
11、单选题：
在单链表中，若*p结点不是终端结点，在其后插入*s结点的操作是 。
选项：
A: s->next = p; p->next = s;
B: s->next = p->next; p->next = s;
C: s->next = p->next; p = s;
D: p->next = s; s->next = p;
答案: 【 s->next = p->next; p->next = s;】
12、单选题：
在单链表中增加一个头结点的目的是为了 。
选项：
A: 使单链表至少有一个结点
B: 标识链表中重要结点位置
C: 方便某些运算的实现
D: 说明单链表是线性表的链式存储结构
答案: 【 方便某些运算的实现】
13、单选题：
在双向链表中的*p结点之后插入一个结点*s的操作是 。
选项：
A: s->prior=p; p->next=s; p->next->prior=s; s->next=p->next;
B: s->next=p->next; p->next->prior=s; p->next=s; s->prior=p;
C: p->next=s; s->prior=p; s->next=p->next; p->next->prior=s;
D: p->next->prior=s; p->next=s; s->next=p->next; s->prior=p;
答案: 【 s->next=p->next; p->next->prior=s; p->next=s; s->prior=p;】
14、单选题：
在双向链表中删除*p结点之后的一个结点的操作是 。
选项：
A: p->next=p->next->next; p->next->next->prior=p;
B: p->next->prior=p; p->next=p->next->next;
C: p->next=p->next->next; p->next->prior=p;
D: p->next->next=p->next; p->next->prior=p;
答案: 【 p->next=p->next->next; p->next->prior=p;】
15、单选题：
在带头结点*head的单循环链表中，至少有一个结点的条件是 。
选项：
A: head->next != NULL
B: head->next != head
C: head->next->next!=NULL
D: head!=NULL
答案: 【 head->next != head】
16、单选题：
在带头结点*head的单循环链表中至少有一个结点时，尾结点*p应该满足的条件是 。
选项：
A: p->next==NULL
B: p==head->next
C: p == NULL
D: p->next == head
答案: 【 p->next == head】
17、单选题：
给定有n个元素的一维数组，建立一个有序单链表的时间复杂度是 。
选项：
A: O(1)
B: O(n)
C: O(
)
D: O(
)
答案: 【 O()】
18、单选题：
数据结构反映了数据元素之间的结构关系，其中单链表是一种 。
选项：
A: 顺序存储线性表
B: 非顺序存储非线性表
C: 顺序存储表
D: 非顺序存储表
答案: 【 非顺序存储表】
19、单选题：
与单链表相比，双向链表的优点之一是 。
选项：
A: 访问前后相邻结点更为灵活方便
B: 可以省略表头指针或表尾指针
C: 可以进行随机访问
D: 插入、删除操作更为方便
答案: 【 访问前后相邻结点更为灵活方便】
20、单选题：
设线性表中有2n个元素， 在单链表上实现要比在顺序表上实现效率更高。
选项：
A: 删除所有值为x的元素
B: 在最后一个元素的后面插入一个新元素
C: 顺序输出前k个元素的值
D: 交