大学MOOC 数据结构19秋-张玉华(苏州大学)1207053808 最新慕课完整章节测试答案
第一章绪论
绪论
1、单选题：
以下与数据的存储结构无关的术语是
选项：
A: 循环队列
B: 链表
C: 哈希表
D: 栈
答案: 【 栈】
2、单选题：
数据结构中数据之间的逻辑关系被称为
选项：
A: 数据的存储结构
B: 数据的基础操作
C: 程序的算法
D: 数据的逻辑结构
答案: 【 数据的逻辑结构】
3、单选题：
算法分析的目的是
选项：
A: 找出数据结构的合理性
B: 研究算法中的输入和输出的关系
C: 分析算法的效率以求改进
D: 分析算法的易读性和文档性
答案: 【 分析算法的效率以求改进】
4、判断题：
数据项是数据的最小单位
选项：
A: 正确
B: 错误
答案: 【 正确】
5、判断题：
每种数据结构都应具备三种基本运算：插入、删除和查找。
选项：
A: 正确
B: 错误
答案: 【 错误】
6、判断题：
算法独立于具体的程序设计语言，与具体的计算机无关。
选项：
A: 正确
B: 错误
答案: 【 正确】
7、填空题：
数据结构中评价算法的两个重要指标是
答案: 【 时间复杂度和空间复杂度】
8、填空题：
数据结构是由数据的 、 和 三部分组成。
答案: 【 逻辑结构、存储结构、运算】
课堂练习
1、填空题：
分析以下算法的时间复杂度。int fun(int n){int i=1,j=100 ;while (i<n) { ++j; i+=2; }}
答案: 【 O(n)】
2、填空题：
分析以下算法的时间复杂度。int fun(int n){int i=1,s=1 ;while (s<n) s+=++i ;return i;}
答案: 【 O(根号n)】
第二章栈
几种表达式
1、单选题：
中缀表达式(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*-/】
栈
1、单选题：
若元素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】
2、单选题：
表达式a*(b+c)-d的后缀表达式是
选项：
A: abcd*+-
B: abc+*d-
C: abc*+d-
D: -+*abcd
答案: 【 abc+*d-】
3、单选题：
输入序列为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】
4、判断题：
同一组不重复输入序列执行不同的入、出栈组合操作，所得结果也可能相同。
选项：
A: 正确
B: 错误
答案: 【 正确】
5、判断题：
设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂性为O(i）。
选项：
A: 正确
B: 错误
答案: 【 错误】
6、判断题：
栈是实现过程和函数等子程序必须的结构。
选项：
A: 正确
B: 错误
答案: 【 正确】
7、填空题：
栈是受限的线性表，其运算遵循 的原则。
答案: 【 FILO，或者LIFO，或者先进后出，或者后进先出】
8、填空题：
设a=6，b=4，c=2，d=3，e=2，则后缀表达式abc-/de*+的值为
答案: 【 9】
9、填空题：
有五个数据依次进栈：1，2，3，4，5.在各种出栈的序列中，以3，4先出栈的序列有 个。
答案: 【 3】
栈的LIFO特性
1、单选题：
设栈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】
2、单选题：
如进栈序列1,2,3,4,5.可能得到的出栈序列为？
选项：
A: 1,2,5,3,4
B: 3,1,2,5,4
C: 3,2,5,4,1
D: 1,4,2,3,5
答案: 【 3,2,5,4,1】
栈的顺序实现
1、判断题：
顺序存储结构要求连续的存储区域，在存储管理上不够灵活，因此不常用。
选项：
A: 正确
B: 错误
答案: 【 错误】
2、判断题：
对任何数据结构，链式存储结构一定优于顺序存储结构。
选项：
A: 正确
B: 错误
答案: 【 错误】
第三章队列
队列的定义
1、单选题：
栈和队列的共同点是
选项：
A: 都是先进先出
B: 都是后进先出
C: 只允许在端点处插入和删除元素
D: 没有共同点
答案: 【 只允许在端点处插入和删除元素】
2、判断题：
栈和队列都是操作受限的线性表。栈是插入和删除只能在一端进行的线性表；队列是插入在一端进行，删除在另一端进行的线性表。
选项：
A: 正确
B: 错误
答案: 【 正确】
队列的顺序实现
1、单选题：
已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是
选项：
A: 0,0
B: 0，n-1
C: n-1,0
D: n-1，n-1
答案: 【 0，n-1】
2、填空题：
循环队列的引入，目的是为了克服
答案: 【 假溢出时大量移动元素】
顺序队列
1、单选题：
为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是
选项：
A: 栈
B: 队列
C: 树
D: 图
答案: 【 队列】
2、单选题：
已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是
选项：
A: 0，0
B: 0，n-1
C: n-1，0
D: n-1，n-1
答案: 【 0，n-1】
3、单选题：
允许对队列进行的操作有
选项：
A: 对队列中元素排序
B: 取出最近进队列的元素
C: 在队头元素之前插入元素
D: 删除队头元素
答案: 【 删除队头元素】
4、判断题：
栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。
选项：
A: 正确
B: 错误
答案: 【 正确】
5、判断题：
通常使用队列的FILO特性进行函数或过程的调用。
选项：
A: 正确
B: 错误
答案: 【 错误】
6、判断题：
循环队列是逻辑上形成了环状，物理实现上仍然是连续的数组。
选项：
A: 正确
B: 错误
答案: 【 正确】
7、填空题：
已知一循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front和rear，则此循环队列判断队满的条件是
答案: 【 (rear+1)%(n-m+1)==front】
8、填空题：
循环队列容量为Q，当rear<front时，队列的长度为
答案: 【 （rear-front+Q)%Q】
第四章链栈和链队列
栈和队列
1、单选题：
队列的“先进先出”特性是指
选项：
A: 最后插入队列中的元素总是最后被删除
B: 当同时进行插入、删除操作时，总是插入操作优先
C: 每当有删除操作时，总要先做一次插入操作
D: 每次从队中删除的总是最早插入的元素
答案: 【 最后插入队列中的元素总是最后被删除】
2、单选题：
四个元素1，2，3，4依次进栈，出栈次序不可能出现的情况是
选项：
A: 1，2，3，4
B: 4，1，3，2
C: 1，4，3，2
D: 4，3，2，1
答案: 【 4，1，3，2】
3、单选题：
若用单链表来表示队列，下列几种数据结构中最合适的是
选项：
A: 带尾指针的非循环链表
B: 带尾指针的循环链表
C: 带头指针的非循环链表
D: 带头指