MOOC 数据结构（陈志贤）(浙江工商大学)1452473197 最新慕课完整章节测试答案

1.1什么是数据结构

1、多选题：
‎数据结构的研究对象主要包括：‏
选项：
A: 数据集合中元素之间的关系
B: 数据集合的存储实现方式
C: 对数据集合进行的操作
D: 操作算法优劣的评价
答案: 【 数据集合中元素之间的关系;
数据集合的存储实现方式;
对数据集合进行的操作;
操作算法优劣的评价】

2、判断题：
​数据结构主要研究非数值计算的问题。‏
选项：
A: 正确
B: 错误
答案: 【 正确】

3、判断题：
​数据结构的研究与计算机硬件无关。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

1.2数据结构的基本概念一——逻辑结构

1、单选题：
‎数据的逻辑结构是指 （        ）关系的整体。‏
选项：
A: 数据存储结构之间
B: 数据类型之间
C: 数据元素之间逻辑
D: 数据项之间逻辑
答案: 【 数据元素之间逻辑】

2、多选题：
‍以下说法不正确的是（        ）。‎
选项：
A: 数据可由若干个数据元素构成。
B: 数据项是不可分割的最小可标识单位。
C: 数据项可由若干个数据元素构成。
D: 数据元素是数据的最小单位。
答案: 【 数据项可由若干个数据元素构成。;
数据元素是数据的最小单位。】

3、多选题：
‏数据的逻辑结构可以分为（        ）。‏
选项：
A: 动态结构和静态结构
B: 线性结构和非线性结构
C: 内部结构和外部结构
D: 集合、线性结构、树形结构、图状结构
答案: 【 线性结构和非线性结构;
集合、线性结构、树形结构、图状结构】

1.2数据结构的基本概念二——物理结构

1、单选题：
​下面关于数据的逻辑结构与存储结构说法正确的是（        ）。‍
选项：
A: 逻辑结构要体现出存储结构。
B: 存储结构要体现出逻辑结构。
C: 两者是一一对应的。
D: 二者毫无关系。
答案: 【 存储结构要体现出逻辑结构。】

2、单选题：
‌在数据的存储中，一个结点通常存储一个（        ）。‍
选项：
A: 数据结构
B: 数据类型
C: 数据元素
D: 数据项
答案: 【 数据元素】

3、单选题：
‌在决定选取任何类型的存储结构时，一般不多考虑（        ）。‏
选项：
A: 对数据有哪些运算
B: 结点个数的多少
C: 各结点的具体取何值
D: 所用编程语言实现这种结构是否方便
答案: 【 各结点的具体取何值】

1.3抽象数据类型

1、单选题：
‌以下关于ADT抽象数据类型说法错误的是（        ）。‎
选项：
A: ADT建立的封装技术将可能的处理实现细节隐蔽起来。
B: 可采用程序设计语言的控制结构和基本数据类型来实现ADT的所提供的逻辑接口。
C: 同一ADT只有唯一的数据结构可以实现。
D: ADT是对数据进行处理的一种逻辑描述。
答案: 【 同一ADT只有唯一的数据结构可以实现。】

2、多选题：
‏下列关于抽象数据类型（ADT）定义的说法，正确的有（        ）。‏
选项：
A: ADT的定义只取决于它的一组逻辑特性。
B: ADT的定义与计算机内部如何表示和实现无关。
C: 不论ADT的内部结构如何变化，只要它的数学特性不变，都不影响它的外部使用。
D: ADT定义了一个完整的（狭义）数据结构。
答案: 【 ADT的定义只取决于它的一组逻辑特性。;
ADT的定义与计算机内部如何表示和实现无关。;
不论ADT的内部结构如何变化，只要它的数学特性不变，都不影响它的外部使用。;
ADT定义了一个完整的（狭义）数据结构。】

1.4什么是算法

1、单选题：
‎计算机中算法是解决某一问题的有限运算序列，必须具备输入、输出、（        ）等5个特性。‎
选项：
A: 确定性、有穷性和健壮性
B: 可读性、正确性和健壮性
C: 可行性、正确性和可读性
D: 可行性、确定性和有穷性
答案: 【 可行性、确定性和有穷性】

2、单选题：
‎数据的运算（即操作） （        ）。‌
选项：
A: 在不同计算机上的实现方法都是相同的。
B: 必须用程序设计语言来描述
C: 与采用何种存储结构有关
D: 有算术运算和关系运算两大类
答案: 【 与采用何种存储结构有关】

3、多选题：
‍算法的设计目标有（        ）等等。‏
选项：
A: 可行性
B: 健壮性
C: 有穷性
D: 正确性
答案: 【 健壮性;
正确性】

1.5算法的分析与度量

1、单选题：
‍算法分析的主要任务之一是分析（        ）。‎
选项：
A: 算法中是否存在语法错误
B: 算法的执行时间与问题规模之间的关系
C: 算法中输入和输出之间的关系
D: 算法是否具有较好的可读性
答案: 【 算法的执行时间与问题规模之间的关系】

2、单选题：
‍给出算法的时间复杂度是属于一种（        ）。‎
选项：
A: 事前统计的方法
B: 事前分析估算的方法
C: 事后统计的方法
D: 事后分析估算的方法
答案: 【 事前分析估算的方法】

3、单选题：
‍下述函数中时间复杂度最小的是（        ） 。‌
选项：
A:
B:
C:
D:
答案: 【 】

4、单选题：
‎下面程序段的时间复杂度是（        ）。​‎i=1;​‎while (i<=n)​‎    i=i*5;​
选项：
A:
B: n
C:
D:
答案: 【 】

第一周绪论单元测验

1、单选题：

‌某算法的时间复杂度为。若该算法在规模为n的数据集上，运行时间为10秒；如果数据规模扩大为2n，该算法大约需要运行（        ）。

‏选项：
A: 10秒
B: 100秒
C: 6-7分钟
D: 以上都不对
答案: 【 以上都不对】

2、单选题：
‌以下函数中时间复杂度最小的是（        ）。‎
选项：
A:
B:
C:
D:
E:
F:
G:
答案: 【 ;
】

3、单选题：
‍下列程序段的时间复杂度是（        ）。‍‍count=0;‍‍for (k=1;k<=n;k*=2)‍‍    for (j=1;j<=n;j++)‍‍        count++;‍‍‍
选项：
A:
B:
C:
D:
答案: 【 】

4、单选题：
下列程序段的时间复杂度是（        ）。‎int k=0,j=0;‎while (j<=n) {
    k++;‎    j+=k;
}‎
选项：
A:

B:
C:
D:
E:
答案: 【 】

5、单选题：
‍下面的数据结构是（        ）。​‍DS=(D,R)，其中D={a,b,c,d,e}，R={r}，​‍r={<a,b>,<a,e>,<b,c>,<d,e>}。​‍注：“<>"表示有序对。​‍​
选项：
A: 集合
B: 线性结构
C: 树形结构
D: 图状结构
E: 顺序存储结构
F: 链式存储结构
答案: 【 图状结构】

6、多选题：
‌下列关于算法的叙述正确的是（        ）。‌
选项：
A: 算法的有穷性是指算法必须能在有限时间和有限步骤内执行完。
B: 算法的时间复杂度与空间复杂度紧密相关。
C: 算法的效率只与问题规模有关，而与数据的存储结构无关。
D: 用不同算法求解同一问题的时间复杂度不同。
E: 算法的优劣与算法描述语言无关，与所用计算机也无关。
F: 算法原地工作的含义是指该算法不需要任何额外的辅助空间。
G: 对于相同规模的n，时间复杂度O(n)的算法运行时间总是小于时间复杂度的算法的运行时间。
答案: 【 算法的有穷性是指算法必须能在有限时间和有限步骤内执行完。;
算法的优劣与算法描述语言无关，与所用计算机也无关。】

7、多选题：
‏下列叙述正确的是（        ）。‏‏‏
选项：
A: 数据元素是数据项中不可分割的最小可标识单位。
B: 从逻辑上可以把数据结构分为顺序结构、链式结构等类别。
C: 研究数据结构就是研究数据的逻辑结构和存储结构。
D: 数据类型可看成是程序设计语言中已实现的数据结构。
E: 数据元素之间的关联关系在数据的逻辑结构中体现。
F: 数据对象是由有限个类型相同的数据元素构成的。
G: 逻辑结构不相同的数据，必须采用不同类型的存储方法。
H: 如果数据元素值发生改变，则数据的逻辑结构也随之改变。
I: 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
答案: 【 数据类型可看成是程序设计语言中已实现的数据结构。;
数据元素之间的关联关系在数据的逻辑结构中体现。;
数据对象是由有限个类型相同的数据元素构成的。;
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。】

2.1线性表的定义一——概念和ADT

1、单选题：
‌下列有关线性表的叙述中，正确的是（      ）。‌
选项：
A: 线性表中元素之间的关系是线性关系。
B: 线性表中至少有一个元素。
C: 线性表中的任一元素有且仅有一个直接前趋。
D: 线性表中的任一元素有且仅有一个直接后继。
答案: 【 线性表中元素之间的关系是线性关系。】

2、判断题：
‌插入和删除操作是线性表的基本操作，这两种操作在数组中也经常使用。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

2.1线性表的定义二——合并与归并

1、单选题：
‏将两个长度均为n的有序线性表归并成一个有序线性表，最少需要（    ）次比较。​
选项：
A: n-1
B: n
C: 2n-1
D: 2n
答案: 【 n】

2、单选题：
‎假设两个集合分别存储在两个线性表中，长度分别为m和n，将它们合并到一个新的线性表中，则该线性表的最小长度是（    ）。‏
选项：
A: m+n
B: min(m,n)
C: max(m,n)
D: 无法确定
答案: 【 max(m,n)】

2.2顺序表

1、单选题：
‎顺序表具有随机存取特性，指的是（    ）。​
选项：
A: 查找值为 x 的元素与顺序表中元素个数 n 无关
B: 查找值为 x 的元素与顺序表中元素个数 n 有关
C: 查找序号为 i 的元素与顺序表中元素个数 n 无关
D: 查找序号为 i 的元素与顺序表中元素个数 n 有关
答案: 【 查找序号为 i 的元素与顺序表中元素个数 n 无关】

2、单选题：
‌顺序表中，删除一个元素所需要的时间（    ）。‎
选项：
A: 与删除元素的位置及顺序表的长度都有关
B: 只与删除元素的位置有关
C: 只与顺序表的长度有关
D: 与删除元素的位置及顺序表的长度都无关
答案: 【 与删除元素的位置及顺序表的长度都有关】

3、单选题：
‎假设某顺序表中第一个元素的存储地址是1010H，每个元素占8个存储单元，则第5个元素的存储地址是（    ）。‍‎【注意：本题的地址采用十六进制表示（数字末尾加H）】‍
选项：
A: 1042H
B: 1050H
C: 1030H
D: 1038H
答案: 【 1030H】

4、单选题：
‏在N个结点的顺序表中插入一个结点，等概率情况下，平均需要移动（    ）个结点。‏
选项：
A: (n-1)/2
B: n/2
C: (n+1)/2
D: n
答案: 【 n/2】

5、判断题：
​顺序表中元素的逻辑顺序与存储顺序总是一致的。‏
选项：
A: 正确
B: 错误
答案: 【 正确】

2.3线性链表一——单链表

1、单选题：
​已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（    ）。‎
选项：
A: O(n)
B: O(m*n)
C: O(min(m,n))
D: O(max(m,n))
答案: 【 O(max(m,n))】

2、单选题：
‏下列关于单链表的说法，错误的是（    ）。‍
选项：
A: 数据域用于存储线性表的一个数据元素。
B: 指针域用于存储一个指向本结点对应元素的直接后继所在结点的指针。
C: 单链表中各结点的地址不可以连续。
D: 单链表无法随机存取。
答案: 【 单链表中各结点的地址不可以连续。】

3、多选题：
​单链表具备的特点有（    ）。 ‍
选项：
A: 插入和删除不需要移动元素。
B: 不必事先估计整个线性表所需的存储空间。
C: 所需存储空间与线性表长度成正比。
D: 只能顺序访问。
答案: 【 插入和删除不需要移动元素。;
不必事先估计整个线性表所需的存储空间。;
所需存储空间与线性表长度成正比。;
只能顺序访问。】

4、多选题：
‌在一个单链表中，已知 q 是 p 的前趋结点，若在 q 和 p 之间插入结点 s ，则应当执行语句序列（    ）。‎
选项：
A: s -> next = p -> next;     p -> next = s;
B: s -> next = q -> next;     p -> next = s;
C: s -> next = q -> next;     q -> next = s;
D: q -> next = s;     s -> next = p;
答案: 【 s -> next = q -> next;     q -> next = s;;
q -> next = s;     s -> next = p;】

2.3线性链表二——静态链表

1、单选题：
‌静态链表中的指针域存放的是（    ）。​
选项：
A: 下一个元素的地址
B: 内存地址
C: 下一个元素在数组中的位置
D: 以上都不对
答案: 【 下一个元素在数组中的位置】

2、判断题：
‍静态链表不需要一开始就分配所有的存储空间，可以等到要插入数据元素时再申请​
选项：
A: 正确
B: 错误
答案: 【 错误】

2.4循环链表和双向链表

1、单选题：
‍对于双向链表，在两个结点之间插入一个新结点需修改的指针共（    ）个。​
选项：
A: 1
B: 2
C: 3
D: 4
答案: 【 4】

2、单选题：
‌非空的循环单链表 head 的尾结点 p 满足 （    ）。​
选项：
A: p -> next == head
B: p -> next == NULL
C: p == NULL
D: p == head
答案: 【 p -> next == head】

3、单选题：
‍对于长度为 n（n≥1）的双向链表 L ，在 p 所指结点之前插入一个新结点，其时间复杂度为（    ）。‍
选项：
A: O(1)
B: O(n)
C: O(nlogn)
D:
答案: 【 O(1)】

4、多选题：
‍对于一个头指针为 head 的带头结点的双向循环链表，可以作为判定该表为空表的条件是（    ）。‍
选项：
A: head == NULL
B: head == NULL
C: head -> prior == head
D: head -> next == head
答案: 【 head -> prior == head;
head -> next == head】

2.5顺序表与线性链表的比较一——顺序表与链表

1、单选题：
‍静态链表与顺序表相比，优点在于（    ）。​
选项：
A: 所有操作的算法实现更简单
B: 便于随机存取
C: 便于插入和删除
D: 便于利用零散的存储空间
答案: 【 便于插入和删除】

2、单选题：
​若某线性表最常用的操作是存取任意指定序号的元素和在表尾元素之后进行插入和删除操作，则采用（        ）存储方式最节省时间。‏
选项：
A: 带头结点的单链表
B: 不带头结点的单链表
C: 带头结点的双向循环链表
D: 顺序表
答案: 【 顺序表】

3、单选题：
‏设线性表中有 2n 个元素，以下操作中，（    ）在单链表上实现要比在顺序表上实现效率更高。‌
选项：
A: 删除指定位置元素的下一个元素
B: 在最后一个元素的后面插入一个新元素
C: 顺序输出前 k 个元素
D: 交换第 i 个元素和第 n-i+1 个元素的值 （i=1, 2, …, n）
答案: 【 删除指定位置元素的下一个元素】

2.5顺序表与线性链表的比较二——各种链表的对比

1、单选题：
​与非循环单链表相比，循环单链表的主要优点是（    ）。‏
选项：
A: 不再需要头指针
B: 已知某个节点的位置后，能够容易找到它的前驱节点
C: 在进行插入、删除操作时，能更好地保证链表不断开
D: 从表中任意节点出发都能扫描到整个链表
答案: 【 从表中任意节点出发都能扫描到整个链表】

2、单选题：
​若某线性表最常用的操作是在表尾结点插入新结点和删除表尾结点，则采用（        ）存储方式最节省时间。‍
选项：
A: 带头结点的双向循环链表
B: 不带头结点的单链表
C: 仅有尾指针的循环单链表
D: 仅有头指针的循环单链表
答案: 【 带头结点的双向循环链表】

3、单选题：
​若某线性表最常用的操作是在表尾结点之后插入新结点和删除表头结点，则采用（        ）存储方式最节省时间。‎
选项：
A: 仅有头指针的循环单链表
B: 仅有尾指针的循环单链表
C: 带头结点的单链表
D: 带头结点的双向循环链表
答案: 【 仅有尾指针的循环单链表】

4、单选题：
​下列关于链表的描述，正确的是（    ）。‍
选项：
A: 在循环单链表中，从表中任一结点出发都可以通过前后移动操作来遍历整个循环链表。
B: 在双向链表中，可以从任一结点开始沿同一方向查找到任何其他结点。
C: 单链表不具有随机存取特性，而双向链表具有随机存取特性。
D: 为了方便插入和删除，可以使用双向链表存放数据。
答案: 【 为了方便插入和删除，可以使用双向链表存放数据。】

第二周线性表单元测验

1、单选题：
​顺序表中，结点的插入和删除操作的时间复杂度分别为（        ）。‎
选项：
A: O(1)、O(1)
B: O(n)、O(1)
C: O(1)、O(n)
D: O(n)、O(n)
答案: 【 O(n)、O(n)】

2、单选题：
‏在表长为n的顺序表中，下列操作中需要移动元素最多的是（        ）。‌
选项：
A: 删除表中的第一个元素。
B: 删除表中的最后一个元素。
C: 在第一个元素之前插入一个元素。
D: 在最后一个元素之前插入一个元素。
E: 在最后一个元素之后插入一个元素。
F: 在最后一个元素之后插入一个元素。
答案: 【 在第一个元素之前插入一个元素。】

3、单选题：
‌带头结点的双向链表 L 为空表时应满足（        ）。‌
选项：
A: L == NULL
B: L -> prior == L -> next
C: L -> prior == NULL
D: L -> next == NULL
答案: 【 L -> next == NULL】

4、单选题：
​在只设有表尾指针 rear 但没有头结点的非空循环单链表中，删除表尾结点的时间复杂度为（        ）。‎
选项：
A: O(1)
B: O(n)
C: O(nlogn)
D:
答案: 【 O(n)】

5、单选题：
‌当元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用（        ）存储结构。‎
选项：
A: 顺序表
B: 静态单链表
C: 双向循环链表
D: 单链表
E: 循环单链表
F: 双向链表
G: 静态循环单链表
答案: 【 顺序表】

6、单选题：
‌已知指针 p 指向某双向链表的一个中间结点，下列语句序列实现的操作是（        ）。​‌q = p -> prior; ​‌p -> prior = q -> prior;​‌q -> prior -> next = p;​‌free(q);​
选项：
A: 删除 p 结点
B: 删除 p 结点的直接前驱结点
C: 删除 p 结点的直接后继结点
D: 删除 p 结点及其所有后继结点
答案: 【 删除 p 结点的直接前驱结点】

7、单选题：
‍下列关于存储相同数据元素的说法中，正确的是（    ）。‍‍‍
选项：
A: 顺序存储比链式存储少占空间
B: 顺序存储比链式存储多占空间
C: 链式存储比顺序存储难于扩充空间
D: 顺序存储和链式存储都要求占用整块存储空间
答案: 【 顺序存储比链式存储少占空间】

8、单选题：
‏在单链表中，增加头结点的主要目的是（    ）。‏
选项：
A: 方便运算的实现
B: 标识表结点中首元结点的位置
C: 使单链表至少有一个结点
D: 说明单链表是线性表的链式存储实现
答案: 【 方便运算的实现】

9、单选题：
‍非空的单循环链表的头指针为head，尾指针为rear， 则下列条件中总是成立的为（    ）。‏
选项：
A: rear->next == head
B: rear->next >next == head
C: head->next == rear
D: head->next->next == rear
E: head->prior == rear
F: rear->prior == head
答案: 【 rear->next == head;
head->prior == rear】

10、单选题：
‍双向链表中有两个指针域:prior和next，分别指回前驱及后继。设p指向链表中的一个结点，q指向待插入结点，现要求在p前插入q,则正确的插入语句序列为（    ）。‌
选项：
A: p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior;
B: q->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q->next;
C: q->next=p; p->next=q; p->prior->next=q; q->next=p;
D: p->prior->next=q; q->next=p; q->prior=p->prior; p->prior=q;
E: q->prior=p->prior; q->next=p; q->prior->next=q;q->next->prior=q;
答案: 【 p->prior->next=q; q->next=p; q->prior=p->prior; p->prior=q;;
q->prior=p->prior; q->next=p; q->prior->next=q;q->next->prior=q;】

11、多选题：
‌下面关于静态链表的表述中，错误的有（        ）。‍
选项：
A: 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第 i 个元素的时间与 i 无关。
B: 静态链表在创建时确定了能容纳的元素个数的最大值。
C: 静态链表与动态链表在元素的插入、删除操作上类似，不需做元素的移动。
D: 静态链表需要分配较大的连续空间。
E: 静态链表中元素的指针域存储的是下一个数据元素的内存地址。
F: 静态链表无法实现随机存取。
G: 所谓静态链表就是不允许插入和删除元素的链表。
答案: 【 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第 i 个元素的时间与 i 无关。;
静态链表中元素的指针域存储的是下一个数据元素的内存地址。;
所谓静态链表就是不允许插入和删除元素的链表。】

12、多选题：
‏下列关于线性表的描述中，正确的是（        ）。‏
选项：
A: 线性表的顺序存储结构优于其链式存储结构。
B: 线性表如果需要频繁进行插入和删除结点操作，顺序存储结构更优于链式存储结构。
C: 线性表的顺序存储结构和链式存储结构都可以进行顺序存取。
D: 顺序存储结构只能用于存储线性结构。
E: 读取线性表的第 i 个元素所需的时间与 i 的大小有关。
F: 静态链表需要分配较大的连续空间，插入和删除不需要移动元素。
G: 在一个长度为 n 的有序单链表中插入一个新结点并仍保持有序的时间复杂度为 O(n)。
H: 在单链表中，可以从头结点开始查找任何一个结点。
答案: 【 线性表的顺序存储结构和链式存储结构都可以进行顺序存取。;
静态链表需要分配较大的连续空间，插入和删除不需要移动元素。;
在一个长度为 n 的有序单链表中插入一个新结点并仍保持有序的时间复杂度为 O(n)。;
在单链表中，可以从头结点开始查找任何一个结点。】

13、多选题：
​如果要在单链表中删除 p 所指结点，可执行如下语句序列：    q = p -> next ;    p -> date = q -> date ;    p -> next = (        );    free(q);‍
选项：
A: p -> next -> next
B: q
C: q -> next
D: q -> next -> next
E: p
答案: 【 p -> next -> next;
q -> next】

14、多选题：
​在一个长度为 n (n>1) 的带头结点的单链表上，设有头尾两个指针，下列操作中执行时间与 n 无关的有（        ）。‏
选项：
A: 删除表中的第一个元素
B: 删除表中最后一个元素
C: 在第一个元素前插入一个新元素
D: 在最后一个元素后插入一个新元素
E: 在第一个元素后插入一个新元素
F: 在最后一个元素前插入一个新元素
答案: 【 删除表中的第一个元素;
在第一个元素前插入一个新元素;
在最后一个元素后插入一个新元素;
在第一个元素后插入一个新元素】

15、多选题：
‎在双向链表中，删除指针p所指的结点时，则修改指针的正确语句序列为（    ）。‌
选项：
A: p->prior->next=p->next; p->next->prior=p->prior;
B: p->prior=p->prior->prior; p->prior->next=p;
C: p->next->prior=p; p->next=p->next->next;
D: p->next=p->prior->prior; p->prior=p->next->next;
E: p->next->prior=p->prior; p->prior->next=p->next;
答案: 【 p->prior->next=p->next; p->next->prior=p->prior;;
p->next->prior=p->prior; p->prior->next=p->next;】

3.1栈的定义与实现

1、单选题：

‌一个栈的入栈序列为1,2,3,…,n，其出栈序列是。若，则为（        ）。

‎选项：
A: i
B: n-i
C: n-i+1
D: 不确定
答案: 【 n-i+1】

2、单选题：
‏设栈最大长度为3，入栈序列为1、2、3、4、5、6，则不可能的出栈序列是（    ）。​
选项：
A: 1、2、3、4、5、6
B: 2、1、3、4、5、6
C: 3、4、2、1、5、6
D: 4、3、2、1、5、6
答案: 【 4、3、2、1、5、6】

3、单选题：
‌在 n 个单元的顺序栈中，假设以地址高端（下标为 n-1 的单元）作为栈底，以 top 作为栈顶指针，则向栈中压入一个元素时，top的变化是（    ）。‍
选项：
A: top 不变
B: top=top->next
C: top=top-1
D: top=top+1
答案: 【 top=top-1】

3.2栈的应用举例一——数制转换、括号匹配、行编辑器

1、单选题：
‏利用栈将十进制数 N（N<100）转换为二进制数时，为了确保栈在处理过程中不会发生上溢，则该栈至少要有（    ）个存储单元。‌
选项：
A: 6
B: 7
C: 8
D: 9
答案: 【 7】

2、单选题：
‎利用栈对表达式 { ( a - b ) / [ c * ( d + e ) ] * ( f - g ) } 进行括号匹配的检验时，该栈至少要有（    ）个存储单元才能确保不发生上溢。‍
选项：
A: 3
B: 5
C: 7
D: 9
答案: 【 3】

3、单选题：
‎如果“#”表示退格符，“@”表示退行符，则从终端接收字符串“fro##or@while##te”后，栈中从栈底到栈顶的内容为（    ）。‌
选项：
A: forwhite
B: white
C: fro##or@while##te
D: while##te
答案: 【 white】

3.2栈的应用举例三—表达式求值

1、单选题：
​利用栈求表达式的值时，假设操作符栈 OPND 只有2个存储单元。在处理下列表达式的过程中，不会发生上溢的是（    ）。‌
选项：
A: A-B*(C-D)
B: (A-B)*C-D
C: (A-B*C)-D
D: (A-B)*(C-D)
答案: 【 (A-B)*C-D】

2、单选题：
‎表达式 (a+b)*(c+d)-e 的后缀表达式是（    ）。‌
选项：
A: abcde++*-
B: ab+cde+*-
C: ab+cd+e*-
D: ab+cd+*e-
答案: 【 ab+cd+*e-】

3.3栈与递归的实现二——递归的实现

1、单选题：
递归函数如下：‏void f ( int n ) {‏    printf( "%d", n%10 );‏    if ( n/10 != 0)  f( n/10 );‏}‏执行语句 f( 857 ) 的输出结果是（    ）。‏
选项：
A: 857
B: 758
C: 75
D: 7
答案: 【 758】

2、单选题：
‏递归函数如下：​‏void print( int w ) {​‏    int i;​‏    if ( w != 0 ) {​‏        print( w-1 );​‏        for ( i=1; i<=w; i++ )​‏            printf( "%3d", i );​‏        printf( "n" );​‏    }​‏} ​‏执行语句 print( 3 ) 的输出结果是（    ）。​
选项：
A:   1  1  2  1  2  3
B:   1  2  3  1  2  1
C:   1  2  2  3  3  3
D:   3  3  3  2  2  1
答案: 【   1  1  2  1  2  3】

3.4队列的定义与实现一——定义和链队列

1、单选题：
​若用单链表来表示队列，则应该选用（    ）。​
选项：
A: 带尾指针的非循环队列
B: 带尾指针的循环链表
C: 带头指针的非循环链表
D: 带头指针的循环链表
答案: 【 带尾指针的循环链表】

2、单选题：
​栈和队列的共同点是（    ）。‍
选项：
A: 都是先进后出
B: 都是后进先出
C: 只允许在端点处插入和删除元素
D: 没有共同点
答案: 【 只允许在端点处插入和删除元素】

3、单选题：
‏在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据打印，该缓冲区应是一个（    ）结构。​
选项：
A: 数组
B: 线性表
C: 堆栈
D: 队列
答案: 【 队列】

3.4队列的定义与实现二——循环队列和双端队列

1、单选题：
‏循环队列存储在数组A[0..7]中，假设当前队尾指针Rear和队头Front的值分别为0和5，当队列中加入2个元素、删除3个元素后，Rear和Front的值分别为多少（        ）。‍
选项：
A: 7和3
B: 0和2
C: 2和0
D: 3和7
答案: 【 2和0】

2、单选题：
​某队列允许在两端进行入队操作，但仅允许在一端进行出队操作，则入队序列abcde不可能得到的出队序列是（    ）。​
选项：
A: bacde
B: dbace
C: dbcae
D: ecbad
答案: 【 dbcae】

第三周栈和队列单元测验

1、单选题：

‏一个栈的入栈序列为1,2,3,…,n，其出栈序列是。若，则可能取值的个数是（        ）。

‌选项：
A: n-3
B: n-2
C: n-1
D: n
E:

F: n(n-1)
G:
答案: 【 n-1】

2、单选题：
​循环队列 Q 采用数组空间 Q.base[0,n-1] 存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列中的元素个数是（    ）。‌
选项：
A: rear-front
B: rear-front+1
C: rear-front+n
D: (rear-front+n)%n
E: rear-front-1
F: (rear-front)%n
答案: 【 (rear-front+n)%n】

3、单选题：
‍已知操作符包括 “+”，“-”，“/”，“(” 和 “)”。将中缀表达式 a+b-a*((c+d)/e-f)+g 转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是(        )。​
选项：
A: 5
B: 7
C: 8
D: 11
答案: 【 5】

4、单选题：
‏在宾馆的客房管理中，为了保证每间客房硬件设施的磨损率尽可能均等，可以利用（    ）这种数据结构来管理空闲的客房，以使得每间客房的使用率尽可能均等。‌
选项：
A: 线性表
B: 栈
C: 队列
D: 双端队列
E: 双栈
F: 超栈
G: 超队列
答案: 【 队列】

5、单选题：
‌以下方法中，（        ）不能区分循环队列的满与空。‎
选项：
A: 牺牲一个存储单元
B: 设置一个标志变量
C: 判断头尾指针相等
D: 使用一个计数器
答案: 【 判断头尾指针相等】

6、单选题：
​设栈S用顺序存储结构表示，则栈S为空的条件是（    ）。‏
选项：
A: S.top != S.base
B: S.top == S.base
C: S.top != S.base + n
D: S.top == S.base + n
答案: 【 S.top == S.base】

7、单选题：
‏设有一空栈，现有输入序列为1，2，3，4，5，经过PUSH，PUSH，POP，GetTop，PUSH，GetTop，PUSH，POP，PUSH后，得到的输出序列为（　 ）。​
选项：
A: 5，4，3，2，1
B: 2，1，3，4
C: 2，3
D: 2，4
答案: 【 2，4】

8、单选题：
‎链栈与顺序栈相比，有一个比较明显的优点是（　）。 ‌
选项：
A: 插入操作更加方便
B: 通常不会出现栈满的情况
C: 不会出现栈满的情况
D: 删除操作更加方便
答案: 【 通常不会出现栈满的情况】

9、单选题：

‏利用栈将十进制正数 N（N<）转换为十六进制数时，为了确保栈在处理过程中不会发生上溢，则该栈至少要有（    ）个存储单元。

‎选项：
A: 3
B: 4
C: 5
D: 6
答案: 【 4】

10、多选题：
‍下列关于栈的叙述中，错误的是（        ）。‏‍‏
选项：
A: 采用非递归方式重写递归程序是必须使用栈。
B: 函数调用时，系统要用栈保存必要的信息。
C: 只要确定了入栈次序，即可确定出栈次序。
D: 栈是一种受限的线性表，允许在其两端进行操作。
E: 消除递归不一定需要使用栈。
F: 进栈和出栈操作的算法时间复杂度均为 O(n)。
G: 两个栈共享一片连续的内存空间时，为了提高内存利用率、减少溢出，应当把两个栈的栈底分别设置在整篇内存空间的两端。
答案: 【 采用非递归方式重写递归程序是必须使用栈。;
只要确定了入栈次序，即可确定出栈次序。;
栈是一种受限的线性表，允许在其两端进行操作。;
进栈和出栈操作的算法时间复杂度均为 O(n)。】

11、多选题：
‍下列关于循环队列的叙述中，正确的是（        ）。‍
选项：
A: 循环队列不会产生假溢出。