奸甲挛谅赋价嘉赴笆笆汐热龚
第一周绪论
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的定义只取决于它的一组逻辑特性。;
ADT的定义与计算机内部如何表示和实现无关。;
不论ADT的内部结构如何变化，只要它的数学特性不变，都不影响它的外部使用。;
ADT定义了一个完整的（狭义）数据结构。
2、多选题：
调用下列test( )函数，能够在屏幕上输出“hello world”的是（ ）。
A: void GetMemory(char *p){ p = (char *)malloc(100);}void Test(void){ char *str = NULL; GetMemory(str); strcpy(str, “hello world”); printf(str);}
B: char *GetMemory(void){ char p[ ] = “hello world”; return p;}void Test(void){ char *str = NULL; str = GetMemory(); printf(str);}
C: void Test(void){ char *str = (char *) malloc(100); strcpy(str, “No!”); free(str); if (str != NULL) { strcpy(str, “hello world”); printf(str); }}
D: void GetMemory(char **p, int num){ *p = (char *)malloc(num);}void Test(void){ char *str = NULL; GetMemory(&str, 100); strcpy(str, “hello world”); printf(str);}
答案: void Test(void){ char *str = (char *) malloc(100); strcpy(str, “No!”); free(str); if (str != NULL) { strcpy(str, “hello world”); printf(str); }};
void GetMemory(char **p, int num){ *p = (char *)malloc(num);}void Test(void){ char *str = NULL; GetMemory(&str, 100); strcpy(str, “hello world”); printf(str);}
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+1) 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)的算法运行时间总是小于时间复杂度
的算法的运行时间。
H: 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。
答案: 算法的有穷性是指算法必须能在执行有限个步骤之后终止。;
算法的优劣与算法描述语言无关，与所用计算机也无关。;
所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。
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个元素的存储地址是（ ）。
A: 1042H
B: 1050H
C: 1030H
D: 1038H
答案: 1030H
4、判断题：
顺序表中元素的逻辑顺序与存储顺序总是一致的。
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: 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第 i 个元素的时间与 i 无关。
B: 静态链表在创建时确定了能容纳的元素个数的最大值。
C: 静态链表与动态链表在元素的插入、删除操作上类似，不需做元素的移动。
D: 静态链表需要分配较大的连续空间。
E: 静态链表中元素的指针域存储的是下一个数据元素的内存地址。
F: 静态链表无法实现随机存取。
G: 所谓静态链表就是不允许插入和删除元素的链表。
答案: 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第 i 个元素的时间与 i 无关。;
静态链表中元素的指针域存储的是下一个数据元素的内存地址。;
所谓静态链表就是不允许插入和删除元素的链表。
8、多选题：
下列关于线性表的描述中，正确的是（ ）。
A: 线性表的顺序存储结构优于其链式存储结构。
B: 线性表如果需要频繁进行插入和删除结点操作，顺序存储结构更优于链式存储结构。
C: 线性表的顺序存储结构和链式存储结构都可以进行顺序存取。
D: 顺序存储结构只能用于存储线性结构。
E: 读取线性表的第 i 个元素所需的时间与 i 的大小有关。
F: 静态链表需要分配较大的连续空间，插入和删除不需要移动元素。
G: 在一个长度为 n 的有序单链表中插入一个新结点并仍保持有序的时间复杂度为 O(n)。
H: 在单链表中，可以从头结点开始查找任何一个结点。
答案: 线性表的顺序存储结构和链式存储结构都可以进行顺序存取。;
静态链表需要分配较大的连续空间，插入和删除不需要移动元素。;
在一个长度为 n 的有序单链表中插入一个新结点并仍保持有序的时间复杂度为 O(n)。;
在单链表中，可以从头结点开始查找任何一个结点。
9、多选题：
如果要在单链表中删除 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
10、多选题：
在一个长度为 n (n>1) 的带头结点的单链表上，设有头尾两个指针，下列操作中执行时间与 n 无关的有（ ）。
A: 删除表中的第一个元素
B: 删除表中最后一个元素
C: 在第一个元素前插入一个新元素
D: 在最后一个元素后插入一个新元素
E: 在第一个元素后插入一个新元素
F: 在最后一个元素前插入一个新元素
答案: 删除表中的第一个元素;
在第一个元素前插入一个新元素;
在最后一个元素后插入一个新元素;
在第一个元素后插入一个新元素
第三周栈和队列
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.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: 只有表头指针没有表尾指针的单循环链表。
E: 同时设有表头指针和表尾指针的单链表。
答案: 只有表头指针没有表尾指针的单循环链表。
6、单选题：
以下方法中，（ ）不能区分循环队列的满与空。
A: 牺牲一个存储单元
B: 设置一个标志变量
C: 判断头尾指针相等
D: 使用一个计数器
答案: 判断头尾指针相等
7、多选题：
下列关于栈的叙述中，错误的是（ ）。
A: 采用非递归方式重写递归程序是必须使用栈。
B: 函数调用时，系统要用栈保存必要的信息。
C: 只要确定了入栈次序，即可确定出栈次序。
D: 栈是一种受限的线性表，允许在其两端进行操作。
E: 消除递归不一定需要使用栈。
F: 进栈和出栈操作的算法时间复杂度均为 O(n)。
G: 两个栈共享一片连续的内存空间时，为了提高内存利用率、减少溢出，应当把两个栈的栈底分别设置在整篇内存空间的两端。
答案: 采用非递归方式重写递归程序是必须使用栈。;
只要确定了入栈次序，即可确定出栈次序。;
栈是一种受限的线性表，允许在其两端进行操作。;
进栈和出栈操作的算法时间复杂度均为 O(n)。
8、多选题：
下列关于循环队列的叙述中，正确的是
上方为免费预览版答案，如需购买完整答案，请点击下方红字：
为了方便下次阅读，建议在浏览器添加书签收藏本网页
添加书签方法：
1.电脑按键盘的Ctrl键+D键即可收藏本网页
2.手机浏览器可以添加书签收藏本网页
点击浏览器底部菜单-【添加书签】-收藏本网页
点击浏览器底部菜单-【书签/历史】-可查看本网页
获取更多慕课答案，欢迎在浏览器访问我们的网站：
http://mooc.mengmianren.com
注：请切换至英文输入法输入域名，如果没有成功进入网站，请输入完整域名：http://mooc.mengmianren.com/
我们的公众号
打开手机微信，扫一扫下方二维码，关注微信公众号：萌面人APP
本公众号可查看各种网课答案，还可免费查看大学教材答案
点击这里，可查看公众号功能介绍
APP下载
APP功能说明
1.可查看各种网课答案
点击【萌面人官网】，可查看知到智慧树，超星尔雅学习通，学堂在线等网课答案
点击【中国大学慕课答案】，可查看mooc慕课答案
2.可一键领取淘宝/天猫/京东/拼多多无门槛优惠券
如图所示，点击对应图标即可领取淘宝/天猫/京东/拼多多无门槛优惠券
敛逛荣宦伺寺俩松夸触井省窗