MOOC 数据结构与算法(常熟理工学院)1449649163 最新慕课完整章节测试答案
第一章 绪论
文章目录
第一章 绪论单元测验
1、单选题：
研究数据结构就是研究（ ）。
选项：
A: 数据的逻辑结构
B: 数据的存储结构
C: 数据的逻辑结构和存储结构
D: 数据的逻辑结构、存储结构及其数据在运算上的实现
答案: 【 数据的逻辑结构、存储结构及其数据在运算上的实现】
2、单选题：
根据数据元素之间关系的不同特性，以下4类基本逻辑结构反映了4类基本数据组织形式。下列解释错误的是（ ）。
选项：
A: 线性结构中结点按逻辑关系依次排列成一条“锁链”
B: 树形结构具有分支、层次特性，其形态有点像自然界中的树
C: 图状结构中各个结点按逻辑关系相互缠绕，任何两个结点都可以邻接
D: 集合中任何两个结点之间都有逻辑关系，但组织形式松散
答案: 【 集合中任何两个结点之间都有逻辑关系，但组织形式松散】
3、单选题：
算法分析的目的是（ ）
选项：
A: 找出数据结构的合理性
B: 研究算法中的输入和输出的关系
C: 分析算法的易懂性和文档性
D: 分析算法的效率以求改进
答案: 【 分析算法的效率以求改进】
4、单选题：
算法分析的两个主要方面是（ ）。
选项：
A: 空间复杂性和时间复杂性
B: 正确性和简明性
C: 可读性和文档性
D: 数据复杂性和程序复杂性
答案: 【 空间复杂性和时间复杂性】
5、单选题：
计算机算法指的是（ ）。
选项：
A: 计算方法
B: 解决问题的有限运算序列
C: 排序方法
D: 调度方法
答案: 【 解决问题的有限运算序列】
6、单选题：
通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量。以下解释错误的是（ ）。
选项：
A: 正确性算法应能正确地实现预定的功能
B: 易读性指算法应容易阅读和理解，以便于调试、修改和扩充
C: 健壮性指当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果
D: 高效性指算法要达到所需要的时间性能
答案: 【 高效性指算法要达到所需要的时间性能】
7、单选题：
一个算法的时间耗费的数量级称为该算法的( )。
选项：
A: 效率
B: 速度
C: 可实现性
D: 时间复杂度
答案: 【 时间复杂度】
8、单选题：
数据的（ ）包括查找、插入、删除、更新、排序等操作类型。
选项：
A: 存储结构
B: 逻辑结构
C: 算法描述
D: 基本操作
答案: 【 基本操作】
9、单选题：
下列程序段的时间复杂度是（ ）。 for(i=0;i<n;i++) for(j=0;j<m;j++) for(k=0;k<t;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j];
选项：
A: O(m+n+t)
B: O(m*n*t)
C: O(m+n*t)
D: O(m*t+n)
答案: 【 O(m*n*t)】
10、单选题：
组成数据的基本单位是
选项：
A: 数据项
B: 数据类型
C: 数据元素
D: 数据变量
答案: 【 数据元素】
11、单选题：
在数据结构中，从逻辑上可以把数据结构分成
选项：
A: 动态结构和静态结构
B: 紧凑结构和非紧凑结构
C: 线性结构和非线性结构
D: 内部结构和外部结构
答案: 【 线性结构和非线性结构】
12、单选题：
算法的时间复杂度为O(n2)，表明该算法的 （2为上标）
选项：
A: 执行时间与n2成正比（2为上标）
B: 问题规模是n2（2为上标）
C: 执行时间等于n2（2为上标）
D: 问题规模与n2成正比（2为上标）
答案: 【 执行时间与n2成正比（2为上标）】
13、单选题：
数据的运算
选项：
A: 与采用何种存储结构有关
B: 是根据存储结构来定义的效率
C: 有算术运算和关系运算两大类
D: 必须用程序设计语言来描述
答案: 【 与采用何种存储结构有关】
14、单选题：
不是算法的基本特性
选项：
A: 可行性
B: 在规定的时间内完成
C: 指令序列长度有限
D: 确定性
答案: 【 在规定的时间内完成】
15、单选题：
以下函数中时间复杂度最小的是
选项：
A: 
B: 
C: 
D: 
答案: 【 】
16、单选题：
下面程序的时间复杂度是void fun( int n) { int i=1; while (i<=n) i=i*3}
选项：
A: O(n)
B: O(nlog3n) （3为下标）
C: O(n²)
D: O(log3n)（3为下标）
答案: 【 O(log3n)（3为下标）】
17、判断题：
数据的机内表示称为数据的存储结构。
选项：
A: 正确
B: 错误
答案: 【 正确】
18、判断题：
算法就是程序。
选项：
A: 正确
B: 错误
答案: 【 错误】
19、判断题：
算法的时间复杂度取决于问题的规模和待处理数据的初态。
选项：
A: 正确
B: 错误
答案: 【 正确】
20、判断题：
算法的五个特性为：有穷性、输入、输出、完成性和确定性。
选项：
A: 正确
B: 错误
答案: 【 错误】
随堂测验1
1、单选题：
研究数据结构就是研究（）。
选项：
A: 数据的逻辑结构
B: 数据的存储结构
C: 数据的逻辑结构和存储结构
D: 数据的逻辑结构、存储结构及其数据在运算上的实现
答案: 【 数据的逻辑结构、存储结构及其数据在运算上的实现】
2、单选题：
数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是（ ）的有限集合
选项：
A: 算法
B: 数据元素
C: 数据操作
D: 数据对象
答案: 【 数据元素】
3、单选题：
数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中R是D上的（ ）有限集合。
选项：
A: 操作
B: 映象
C: 存储
D: 关系
答案: 【 关系】
随堂测验2
1、单选题：
算法分析的目的是（ ）。
选项：
A: 找出数据结构的合理性
B: 研究算法中的输入和输出的关系
C: 分析算法的效率以求改进
D: 分析算法的易懂性和文档性
答案: 【 分析算法的效率以求改进】
2、单选题：
算法分析的两个主要方面是（ ）。
选项：
A: 空间复杂性和时间复杂性
B: 正确性和简明性
C: 可读性和文档性
D: 数据复杂性和程序复杂性
答案: 【 空间复杂性和时间复杂性】
3、单选题：
某算法执行次数最多的语句的语句执行频度为（3*n+n*log2n+n*n+8）,该算法的时间复杂度表示（ ）。
选项：
A: O(n)
B: O(nlog2n)
C: O(n*n)
D: O(log2n)
答案: 【 O(n*n)】
第二章 - 顺序表
随堂测验1
1、判断题：
线性表的数据元素可以是简单的整数、字符，也可以是有多项数据项组成的复杂数据元素。
选项：
A: 正确
B: 错误
答案: 【 正确】
2、判断题：
顺序表是用连续的存储空间实现的线性表，可以实现数据的随机存储。
选项：
A: 正确
B: 错误
答案: 【 正确】
随堂测验2
1、判断题：
顺序表中插入、删除数据元素通常需要移动数据元素。
选项：
A: 正确
B: 错误
答案: 【 正确】
2、判断题：
顺序表中查找指定位序的元素，时间复杂度为O(n)。
选项：
A: 正确
B: 错误
答案: 【 错误】
第二章 链表及实例应用
第二章 线性表单元测验
1、单选题：
若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
选项：
A: 顺序表
B: 单链表
C: 双链表
D: 单循环链表
答案: 【 顺序表 】
2、单选题：
在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（ ）。
选项：
A: p=p->next;
B: p->next=p->next->next;
C: p->next=p;
D: p=p->next->next;
答案: 【 p->next=p->next->next;】
3、单选题：
已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（ ）。
选项：
A: q->next=s->next；s->next=p；
B: s->next=p；q->next=s->next；
C: p->next=s->next；s->next=q；
D: s->next=q；p->next=s->next；
答案: 【 q->next=s->next；s->next=p； 】
4、单选题：
在以下的叙述中，正确的是（ ）。
选项：
A: 线性表的顺序存储结构优于链表存储结构
B: 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
C: 线性表的链表存储结构适用于频繁插入/删除数据元素的情况
D: 线性表的链表存储结构优于顺序存储结构
答案: 【 线性表的链表存储结构适用于频繁插入/删除数据元素的情况 】
5、单选题：
循环链表的主要优点是（ ）。
选项：
A: 不再需要头指针
B: 已知某结点位置后能容易找到其直接前驱
C: 在进行插入、删除运算时要移动数据少量数据元素
D: 在表中任一结点出发都能扫描整个链表
答案: 【 在表中任一结点出发都能扫描整个链表】
6、单选题：
对一个具有n个元素的线性表，建立其单链表的时间复杂度为：
选项：
A: O(n)
B: O(1)
C: O(n2)[n的平方]
D: O(log2n)
答案: 【 O(n)】
7、单选题：
在p所指结点后插入s所指结点的正确操作是：
选项：
A: s->next =p+1; p->next=s;
B: (*p).next=s; (*s).next=(*p).next;
C: s->next=p->next; p->next=s->next;
D: s->next=p->next; p->next=s;
答案: 【 s->next=p->next; p->next=s;】
8、单选题：
某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）方式最节省运算时间。
选项：
A: 单链表
B: 仅有头指针的循环单链表
C: 双链表
D: 仅有尾指针的循环单链表
答案: 【 仅有尾指针的循环单链表】
9、单选题：
给定n个数据元素，建立对应的有序单链表的时间复杂度是：
选项：
A: O(1)
B: O(n)
C: O(n2)[n的平方]
D: O(nlog2n)
答案: 【 O(n2)[n的平方]】
10、单选题：
非空的循环单链表head的尾结点（由p所指向）满足是：
选项：
A: p->next==NULL
B: p==NULL
C: p->next==head
D: P==head
答案: 【 p->next==head】
11、单选题：
不带头结点的单链表head为空的判定条件是：
选项：
A: head==NULL
B: head->next==NULL
C: head->next==head
D: head!=NULL
答案: 【 head==NULL】
12、单选题：
在一个双向链表中，若删除p所指结点的后继结点，应执行：
选项：
A: p->next=p->next->next; p->next->next->prior=p;
B: p=p->next; p->next=p->next->next;
C: p->next=p->next;p->prior=p->next->prior;
D: p->next->next->prior=p; p->next=p->next->next;
答案: 【 p->next->next->prior=p; p->next=p->next->next;】
13、单选题：
线性表的链式存储结构是一种（ ）的存储结构。
选项：
A: 随机存取
B: 顺序存取
C: 索引存取
D: 散列存取
答案: 【 顺序存取】
14、单选题：
线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。
选项：
A: 必须是连续的
B: 部分地址必须是连续的
C: 一定是不连续的
D: 连续或不连续都可以
答案: 【 连续或不连续都可以】
15、单选题：
将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度是：
选项：
A: O(1)
B: O(n)
C: O(m)
D: O(n+m)
答案: 【 O(m)】
16、判断题：
单链表不是一种随机存储结构。
选项：
A: 正确
B: 错误
答案: 【 正确】
17、判断题：
在具有头结点的单链表中，头指针指向链表的第一个数据结点。
选项：
A: 正确
B: 错误
答案: 【 错误】
18、判断题：
在线性表的顺序存储结构中，逻辑上相邻的两个元素但是在物理位置上不一定是相邻的。
选项：
A: 正确
B: 错误
答案: 【 错误】
19、判断题：
顺序存储的线性表可以随机存取。
选项：
A: 正确
B: 错误
答案: 【 正确】
20、判断题：
在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。
选项：
A: 正确
B: 错误
答案: 【 正确】
随堂测验1
1、单选题：
不带头结点的单链表head为空的判定条件是（ ）。
选项：
A: head==NULL
B: head->next==NULL
C: head->next==head
D: head!=NULL
答案: 【 head==NULL】
随堂测验2
1、单选题：
在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入一个结点s，则执行（ ）。
选项：
A: s->next=p->next; p->next=s;
B: p->next=s->next;s->next=p;
C: q->next=s;s->next=p;
D: p->next=s;s->next=q;
答案: 【 q->next=s;s->next=p; 】
2、单选题：
在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（ ）。
选项：
A: p=p->next;
B: p->next=p->next->next;
C: p->next=p;
D: p=p->next->next;
答案: 【 p->next=p->next->next; 】
随堂测验3
1、单选题：
在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next==head，则（ ）。
选项：
A: p指向头结点
B: p指向尾结点
C: p的直接后继是头结点
D: p的直接后继是尾结点
答案: 【 p的直接后继是尾结点】
2、单选题：
在双向链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（ ）。
选项：
A: p->next=q;q->prior=p;p->next->prior=q;q->next=q;
B: p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;
C: q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;
D: q->next=p->next;q->prior=p;p->next=q;p->next->prior=q;
答案: 【 q->prior=p;q->next=p->next;p->next->prior=q;p->next=q; 】
随堂测验4
1、单选题：
在线性表的下列存储结构中，读取元素花费的时间最少的是（ ）。
选项：
A: 单链表
B: 双链表
C: 循环链表
D: 顺序表
答案: 【 顺序表】
第三章 栈和队列—— 栈的定义及其应用
随堂测验1
1、单选题：
栈和队列的共同点是（ ）
选项：
A: 都是先进先出
B: 都是后进先出
C: 只允许在端点处插入或删除元素
D: 没有共同点
答案: 【 只允许在端点处插入或删除元素】
2、单选题：
若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1＝n，则pi为（ ）
选项：
A: i
B: n-i
C: n-i+1
D: 不确定
答案: 【 n-i】
第三章 栈和队列——队列的定义及其实现
第三章 栈和队列单元测验
1、单选题：
下列关于队列的叙述正确的是（ ）。
选项：
A: 队列是后进先出的线性表
B: 在队列中只能插入数据
C: 在队列中只能删除数据
D: 队列是先进先出的线性表
答案: 【 队列是先进先出的线性表 】
2、单选题：
一个栈的输入序列为123…n，若输出的第一个元素是n，则输出的第i个元素是（ ）。
选项：
A: 不确定
B: n-i+1
C: i
D: n-i
答案: 【 n-i+1】
3、单选题：
在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的操作应执行（ ）。
选项：
A: f->next=s; r=s;
B: r->next=s; r=s;
C: s->next=r; r=s;
D: s->next =f; f=s;
答案: 【 r->next=s; r=s; 】
4、单选题：
用链接方式存储的队列，在进行出队（删除）操作时（ ）。
选项：
A: 仅需修改队头指针
B: 仅需修改队尾指针
C: 必须同时修改队头和队尾指针
D: 可能需要同时修改队头和队尾指针
答案: 【 可能需要同时修改队头和队尾指针】
5、单选题：
栈和队列的共同点是（ ）。
选项：
A: 都是先进先出
B: 都是后进先出
C: 只允许在端点处插入或删除元素
D: 没有共同点
答案: 【 只允许在端点处插入或删除元素 】
6、单选题：
在具有n个单元的循环队列中，设front和rear为队头和队尾指针，则判断队满的条件是（ ）。
选项：
A: rear%n==front
B: (rear-1)%n==front
C: (rear-front+n)%n
D: (rear+1)%n==front
答案: 【 (rear+1)%n==front】
7、单选题：
向一个栈顶指针为top的链栈中插入一个p所指的结点时，其操作步骤是（ ）。
选项：
A: top->next=p;
B: P->next=top->next;top->next=p;
C: p->next=top;top=p;
D: P->next=top;top=top->next;
答案: 【 p->next=top;top=p; 】
8、单选题：
用不带头结点的单链表存储队列时，在进行删除运算时（ ）。
选项：
A: 仅修改头指针
B: 仅修改尾指针
C: 头、尾指针都要修改
D: 头、尾指针可能都要修改
答案: 【 头、尾指针可能都要修改】
9、单选题：
一般情况下，将递归算法转换成等价的非递归算法应该设置：
选项：
A: 堆栈
B: 队列
C: 广义表
D: 数组
答案: 【 堆栈】
10、单选题：
一个循环队列包含60个单元，若队尾指针rear=32，队头指针front=15 ，则当前队列中的元素个数为：
选项：
A: 42
B: 16
C: 17
D: 41
答案: 【 17】
11、单选题：
判断一个顺序栈ST（最多元素为m0）为空的条件是：
选项：
A: ST->top<>0
B: ST->top<>m0
C: ST->top==m0
D: ST->top==0
答案: 【 ST->top==0】
12、单选题：
设栈的输入序列为{1,2,3,4,5,6}，则正确的输出序列为：
选项：
A: 5,3,4,6,1,2
B: 3,2,5,6,4,1
C: 3,1,2,5,4,6
D: 1,5,4,6,2,3
答案: 【 3,2,5,6,4,1】
13、单选题：
循环队列Q[m]存放各队列元素，已知其头尾指针front和rear，则当前队列的元素个数是：
选项：
A: (rear-front+m)%m
B: rear-front+1
C: rear-front-1
D: rear-front
答案: 【 (rear-front+m)%m】
14、判断题：
栈和队列的存储方式既可以是顺序存储，也可以是链式存储。
选项：
A: 正确
B: 错误
答案: 【 正确】
15、判断题：
若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列3，2，5，6，4，1。
选项：
A: 正确
B: 错误
答案: 【 正确】
16、填空题：
假设以S和X分别表示入栈和出栈操作，对输入序列1,2,3,4,5进行SXSSXSSXXX操作后，可得到序列（ ）。
答案: 【 13542】
17、填空题：
设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是（ ）。
答案: 【 3】
18、填空题：
表达式求值是 应用的一个典型例子
答案: 【 栈】
19、填空题：
用单循环链表表示的队列，长度为n，若只设头指针，则出队时间复杂度为：
答案: 【 O(1)##%_YZPRLFH_%##o(1)##%_YZPRLFH_%##O(1)##%_YZPRLFH_%##O（1）】
20、填空题：
用单循环链表表示的队列，长度为n，若只设头指针，则入队的时间复杂度为：
答案: 【 O(n)##%_YZPRLFH_%##O(N)】