大学MOOC 数据结构与算法(周口师范学院)1002128023 最新慕课完整章节测试答案
第一章绪论
1.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: 错误
答案: 【 错误】
7、判断题：
数据元素是数据的最小单位。
选项：
A: 正确
B: 错误
答案: 【 错误】
8、判断题：
数据的物理结构是指数据在计算机内的实际存储形式。
选项：
A: 正确
B: 错误
答案: 【 正确】
9、判断题：
数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.
选项：
A: 正确
B: 错误
答案: 【 错误】
第1章单元测试题
1、单选题：
数据结构中，与所使用的计算机无关的是数据的 结构
选项：
A: 存储
B: 物理
C: 逻辑
D: 物理和存储
答案: 【 逻辑】
2、单选题：
算法分析的目的是：
选项：
A: 找出数据结构的合理性
B: 研究算法中的输入和输出的关系
C: 分析算法的效率以求改进
D: 分析算法的易懂性和文档性
答案: 【 分析算法的效率以求改进 】
3、单选题：
算法分析的两个主要方面是：
选项：
A: 空间复杂性和时间复杂性
B: 正确性和简明性
C: 可读性和文档性
D: 数据复杂性和程序复杂性
答案: 【 空间复杂性和时间复杂性】
4、单选题：
计算机算法指的是：
选项：
A: 计算方法
B: 排序方法
C: 解决问题的有限运算序列
D: 调度方法
答案: 【 解决问题的有限运算序列】
5、单选题：
计算机算法必须具备输入、输出和 等5个特性。
选项：
A: 可行性、可移植性和可扩充性
B: 可行性、确定性和有穷性
C: 确定性、有穷性和稳定性
D: 易读性、稳定性和安全性
答案: 【 可行性、确定性和有穷性】
6、单选题：
下面关于算法说法错误的是（ ）【提高题】
选项：
A: 算法最终必须由计算机程序实现
B: 为解决某问题的算法同为该问题编写的程序含义是相同的
C: 算法的可行性是指指令不能有二义性
D: 其它几个都是错误的
答案: 【 其它几个都是错误的】
7、单选题：
在下面的程序段中，对x的赋值语句的频度为（ ）[提高题]for（ i=1；i for（ j=1；j x:=x+1;
选项：
A: O(2n)
B: O(n)
C: O(n2)
D: O(log2n)
答案: 【 O(n2) 】
8、单选题：
程序段【提高题】for(i=n-1;i>=1;i--)for(j=1;j>=i;j--) if( A[j]>A[j+1]) A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（ ）
选项：
A: O（n）
B: O(nlogn)
C: O(n3)
D: O(n2)
答案: 【 O(n2) 】
9、单选题：
连续存储设计时，存储单元的地址（ ）。【提高题】
选项：
A: 一定连续
B: 一定不连续
C: 不一定连续
D: 部分连续，部分不连续
答案: 【 一定连续 】
10、单选题：
计算机算法指的是（1）。【提高题】
选项：
A: 计算方法
B: 排序方法
C: 解决问题的步骤序列
D: 调度方法
答案: 【 解决问题的步骤序列 】
11、判断题：
数据的逻辑结构是指数据的各数据项之间的逻辑关系；
选项：
A: 正确
B: 错误
答案: 【 错误】
12、判断题：
算法的优劣与算法描述语言无关，但与所用计算机有关。( )
选项：
A: 正确
B: 错误
答案: 【 错误】
13、判断题：
健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( )
选项：
A: 正确
B: 错误
答案: 【 正确】
14、判断题：
数据结构的抽象操作的定义与具体实现有关。( )
选项：
A: 正确
B: 错误
答案: 【 错误】
15、判断题：
数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ( )
选项：
A: 正确
B: 错误
答案: 【 错误】
16、填空题：
数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科。
答案: 【 操作对象 关系】
17、填空题：
数据结构被形式地定义为（D, R），其中D是 的有限集合，R是D上的 有限集合。
答案: 【 数据元素 关系】
18、填空题：
数据结构包括数据的 、数据的 和数据的 这三个方面的内容。
答案: 【 逻辑结构 存储结构 运算】
19、填空题：
线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。
答案: 【 一对一 一对多 多对多】
20、填空题：
在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 后续结点，其余每个结点有且只有1个后续结点。
答案: 【 没有 没有】
21、填空题：
一个数据结构在计算机中 称为存储结构
答案: 【 表示##%_YZPRLFH_%##映像】
22、填空题：
在下面的程序段中，对ｘ的赋值语句的频度为______. for(i=1;i for(j=1;j for(k=1;k ｘ=ｘ＋delta；
答案: 【 O(n3)】
23、填空题：
对于给定的n个元素,可以构造出的逻辑结构有 （1） ， （2） ， （3） ，__（4）_四种。
答案: 【 集合 线性结构 树 图】
24、填空题：
数据的逻辑结构是指 。
答案: 【 数据元素之间的逻辑关系】
25、填空题：
数据结构中评价算法的两个重要指标是 。
答案: 【 时间复杂度 空间复杂度】
随堂测验题
1、单选题：
1.算法的时间复杂度取决于（ ）
选项：
A: 问题的规模
B: 待处理数据的初态
C: C. A和B
D: A或B
答案: 【 问题的规模】
2、单选题：
2.一个算法应该是（ ）。
选项：
A: 程序
B: 问题求解步骤的描述
C: 要满足五个基本特性
D: A和C
答案: 【 问题求解步骤的描述】
3、单选题：
3.下面关于算法说法错误的是（ ）
选项：
A: 算法最终必须由计算机程序实现
B: 为解决某问题的算法同为该问题编写的程序含义是相同的
C: 算法的可行性是指指令不能有二义性
D: 以上几个都是错误的
答案: 【 以上几个都是错误的】
4、单选题：
4.下面说法错误的是（ ）
选项：
A: 算法原地工作的含义是指不需要任何额外的辅助空间
B: 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
C: 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
D: 同一个算法，实现语言的级别越高，执行效率就越低
答案: 【 算法原地工作的含义是指不需要任何额外的辅助空间】
第二章线性结构
栈和队列单元测试
1、单选题：
为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中读取数据。该缓冲区的逻辑结构是（ ）。
选项：
A: 栈
B: 队列
C: 树
D: 图
答案: 【 队列】
2、单选题：
若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确的操作是（ ）。
选项：
A: top=top+1;V[top]=x;
B: V[top]=x;top=top+1;
C: top=top-1;V[top]=x;
D: V[top]=x;top=top-1;
答案: 【 top=top-1;V[top]=x;】
3、单选题：
设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。
选项：
A: 线性表的顺序存储结构
B: 队列
C: 线性表的链式存储结构
D: 栈
答案: 【 栈】
4、单选题：
对于循环队列（ ）。
选项：
A: 无法判断队列是否为空
B: 无法判断队列是否为满
C: 队列不可能满
D: 以上说法都不是
答案: 【 以上说法都不是】
5、单选题：
循环队列A[0...m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（ ）。
选项：
A: (rear-front+m)%m
B: rear-front+1
C: rear-front-1
D: rear-front
答案: 【 (rear-front+m)%m】
6、单选题：
设顺序队列的容量为MaxSize，其头指针为front，尾指针为rear，空队列的条件为（ ）。
选项：
A: front=rear
B: front=MaxSize
C: front+1=rear
D: rear=0
答案: 【 front=rear】
7、单选题：
循环队列存储在数组A[0...m]中，则入队时的操作为（ ）。
选项：
A: rear=rear+1
B: rear=（rear+1）%（m-1）
C: rear=（rear+1）%m
D: rear=（rear+1）%（m+1）
答案: 【 rear=（rear+1）%（m+1）】
8、单选题：
若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？（ ）
选项：
A: 1和5
B: 2和4
C: 4和2
D: 5和 1
答案: 【 2和4】
9、单选题：
栈和队列的共同点是（ ）。
选项：
A: 都是先进后出
B: 都是后进先出
C: 只允许在端点处插入和删除元素
D: 没有共同点
答案: 【 只允许在端点处插入和删除元素】
10、单选题：
将递归算法转变成对应非递归算法时，需要使用（ ）保存中间结果。
选项：
A: 栈
B: 队列
C: 二叉树
D: 单链表
答案: 【 栈】
11、单选题：
队列操作的原则是（ ）。
选项：
A: 先进先出
B: 后进先出
C: 只能进行插入
D: 只能进行删除
答案: 【 先进先出】
12、单选题：
在下列栈的基本操作中，（ ）的初始条件不要求栈S已存在。
选项：
A: InitStack(&S)
B: DestroyStack(&S)
C: ClearStack(&S)
D: StackEmpty(S)
答案: 【 InitStack(&S)】
13、单选题：
在算符优先级中，算符“+”和“（”的优先关系是（ ）。
选项：
A: “+”大于“（”
B: “+”小于“（”
C: “+”等于“（”
D: 取决于它们出现的位置
答案: 【 “+”小于“（”】
14、单选题：
设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次加入栈S，若每个元素出栈后立即加入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容量至少是（ ）。【提高题】
选项：
A: 1
B: 2
C: 3
D: 4
答案: 【 3】
15、单选题：
若元素a,b,c,d,e,f依次进栈，允许进栈、出栈操作交替进行，但不允许连续三次进行出栈操作，则不可能得到的出栈序列是（ ）。【提高题】
选项：
A: d,c,e,b,f,a
B: c,b,d,a,e,f
C: b,c,a,e,f,d
D: a,f,e,d,c,b
答案: 【 a,f,e,d,c,b】
16、单选题：
元素a,b,c,d,e依次加入初始为空的栈中，若元素进栈后可停留，可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（ ）。【提高题】
选项：
A: 3
B: 4
C: 5
D: 6
答案: 【 4】
17、单选题：
已知操作符包括'+'，'-'，'*'，'/'，'(' 和 ')'。将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定预算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。【提高题】
选项：
A: 5
B: 6
C: 7
D: 8
答案: 【 5】
18、单选题：
假设栈初始为空，将中缀表达式a/b+(c*d-e*f)/g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是（ ）。【提高题】
选项：
A: +(*-
B: +(-*
C: /+(*-*
D: /+-*
答案: 【 +(-*】
19、单选题：
已知程序如下：int s(int n)
{
return (n<=0)?0:s(n-1)+n;
}
int main(void)
{
printf("%d",s(1));
}程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是（ ）。【提高题】
选项：
A: main()->S(1)->S(0)
B: S(1)->S(0)->main()
C: main()->S(0)->S(1)
D: S(0)->S(1)->main()
答案: 【 main()->S(1)->S(0)】
20、单选题：
一个栈的输入序列为1,2,3,...,n,若输出序列的第一个元素是n，输出第i（1≤i≤n）个元素是（ ）。【提高题】
选项：
A: 不确定
B: n-i
C: i
D: n-i+1
答案: 【 n-i+1】
21、单选题：
中缀表达式(A+B)*(C-D)/(E-F*G)的后缀表达式是（ ）。【提高题】
选项：
A: A+B*C-D/E-F*G
B: AB+CD-*EFG*-/
C: AB+C*D-E/F-G*
D: ABCDEFG+*-/-*
答案: 【 AB+CD-*EFG*-/】
22、单选题：
表达式a*(b+c)-d的后缀表达式是（ ）。【提高题】
选项：
A: abcd*+-
B: abc+*d-
C: abc*+d-
D: -+*abcd
答案: 【 abc+*d-】
23、单选题：
利用栈求表达式的值时，设立操作数栈OPND，设OPND只有两个存储单元，在下列表达式中，不发生上溢的是（ ）。【提高题】
选项：
A: A-B*(C-D)
B: (A-B)*C-D
C: (A-B*C)-D
D: (A-B)*(C-D)
答案: 【 (A-B)*C-D】
24、单选题：
若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。【提高题】
选项：
A: i-j-1
B: i-j
C: j-i+1
D: 不确定的
答案: 【 不确定的】
25、单选题：
有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）【提高题】
选项：
A: 5 4 3 6 1 2
B: 4 5 3 1 2 6
C: 3 4 6 5 2 1
D: 2 3 4 1 5 6
答案: 【 3 4 6 5 2 1 】
26、单选题：
设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。【提高题】
选项：
A: 1，2，4，3
B: 2，1，3，4
C: 1，4，3，2
D: 4，3，1，2
E: 3，2，1，4
答案: 【 4，3，1，2】
27、单选题：
设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ ）。【提高题】
选项：
A: 5 1 2 3 4
B: 4 5 1 3 2
C: 4 3 1 2 5
D: 3 2 1 5 4
答案: 【 3 2 1 5 4】
28、单选题：
设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（ ）。【提高题】
选项：
A: fedcba
B: bcafed
C: dcefba
D: cabdef
答案: 【 cabdef】
29、单选题：
输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）【提高题】
选项：
A: push,pop,push,pop,push,pop
B: push,push,push,pop,pop,pop
C: push,push,pop,pop,push,pop
D: push,pop,push,push,pop,pop
答案: 【 push,push,push,pop,pop,pop】
30、单选题：
和顺序栈相比，链栈有一个比较明显的优势是（ ）。
选项：
A: 通常不会出现栈满的情况
B: 通常不会出现栈空的情况
C: 插入操作更容易实现
D: 删除操作更容易实现
答案: 【 通常不会出现栈满的情况】
31、单选题：
一个递归算法必须包括（ ）。
选项：
A: 递归部分
B: 终止条件和递归部分
C: 迭代部分
D: 终止条件和迭代部分
答案: 【