第一讲 基本概念（1：15：26）[陈越] 第一讲单元测试
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、 在长度为n的顺序表中，求第i个元素的直接前驱算法的时间复杂度为O(1)。
A:正确
B:错误
答案: 正确
10、 线性表就是顺序存储的表。
A:正确
B:错误
答案: 错误
11、 线性表的顺序存储优于链式存储。
A:正确
B:错误
答案: 错误
12、 数据的逻辑结构是数据结构在计算机中的表示。
A:正确
B:错误
答案: 错误
第二讲 线性结构（2：19：00）[何钦铭] 2.2节单元测试
1、 栈是（ ）。
A:顺序存储的线性结构
B:链式存储的非线性结构
C:限制存取点的线性结构
D:限制存储点的非线性结构
答案: 限制存取点的线性结构
2、 （ ）不是栈的基本操作。
A:删除栈顶元素
B:删除栈底元素
C:判断栈是否为空
D:将栈置为空栈
答案: 删除栈底元素
3、 假定利用数组a[n]顺序存储为一个栈，用top表示栈顶指针，top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（ ）。
A:a[–top]=x
B:a[top–]=x
C:a[++top]=x
D:a[top++]=x
答案: a[++top]=x
4、 和顺序栈相比，链栈有一个比较明显的优势是（ ）。
A:通常不会出现栈满的情况
B:通常不会出现栈空的情况
C:插入操作更容易实现
D:删除操作更容易实现
答案: 通常不会出现栈满的情况
5、 设链表不带头结点且所有操作均在表头进行，则下列最不适合作为链栈的是（ ）。
A:只有表头结点指针，没有表尾指针的双向循环链表
B:只有表尾结点指针，没有表头指针的双向循环链表
C:只有表头结点指针，没有表尾指针的单向循环链表
D:只有表尾结点指针，没有表头指针的单向循环链表
答案: 只有表头结点指针，没有表尾指针的单向循环链表
6、 设有一个空栈，栈顶指针为1000H，每个元素需要1个存储单元，在执行Push、Push、Pop、Push、Pop、Push、Pop、Push操作，栈顶指针的值为（ ）。
A:1002H
B:1003H
C:1004H
D:1005H
答案: 1002H
7、 若一个栈的输入序列是1, 2, 3,……, n，输出序列的第一个元素是n，则第i个输出元是（ ）。
A:不确定
B:n-i
C:n-i-1
D:n-i+1
答案: n-i+1
8、 下列关于栈的描述中错误的是( )。
A:栈是先进后出的线性表
B:栈只能顺序存储
C:栈具有记忆作用
D:对栈的插入与删除操作中，不需要改变栈底指针
答案: 栈只能顺序存储
9、 若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续3次进行退栈操作，则不可能得到的出栈序列是（ ）。
A:dcebfa
B:cbdaef
C:bcaefd
D:afedcb
答案: afedcb
10、 用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234, 为了得到1342的出栈顺序，相应的S和X的操作序列为（ ）。
A:SXSXSSXX
B:SSSXXSXX
C:SXSSXXSX
D:SXSSXSXX
答案: SXSSXSXX
11、 采用共享栈的好处是（ ）。
A:减少存取时间，降低发生上溢的可能
B:节省存储空间，降低发生上溢的可能
C:减少存取时间，降低发生下溢的可能
D:节省存储空间，降低发生下溢的可能
答案: 节省存储空间，降低发生上溢的可能
12、 任何一个递归过程都可以转换成非递归过程。
A:正确
B:错误
答案: 正确
13、 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。
A:正确
B:错误
答案: 错误
14、 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
A:正确
B:错误
答案: 正确
15、 栈结构通常采用的两种存储结构是链表存储结构和数组。
A:正确
B:错误
答案: 错误
16、 若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。
A:正确
B:错误
答案: 错误
17、 一个递归算法必须包括终止条件和递归部分。
A:正确
B:错误
答案: 正确
18、 判定一个顺序栈ST（最多元素为m0）为空的条件是top==m0-1。
A:正确
B:错误
答案: 错误
19、 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为O(____)。
答案: 1
20、 向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动_个元素。
答案: n-i
第二讲 线性结构（2：19：00）[何钦铭] 2.3节单元测试
1、 下列说法中正确的是（ ）。
A:消除递归不一定需要使用栈
B:对同一输入序列进行两组不同的合法入栈和出栈组合操作，所得的输出序列也一定相同
C:通常使用队列来处理函数或过程调用
D:队列和栈都是运算受限的线性表，只允许在表的两端进行运算
答案: 消除递归不一定需要使用栈
2、 一个问题的递归算法求解和其相对应的非递归算法求解（ ）。
A:递归算法通常效率高一些
B:非递归算法通常效率高一些
C:两者相同
D:无法比较
答案: 非递归算法通常效率高一些
3、 为解决计算机主机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
A:栈
B:队列
C:树
D:图
答案: 队列
4、 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作，则不可能得到的出队序列是（ ）。
A:bacde
B:dbace
C:dbcae
D:ecbad
答案: dbcae
5、 栈和队列的主要区别在于（ ）。
A:它们的逻辑结构不一样
B:它们的存储结构不一样
C:所包含的元素不一样
D:插入、删除操作的限定不一样
答案: 插入、删除操作的限定不一样
6、 循环队列存储在数组A[0…n]，则入队时的操作为（ ）。
A:rear=rear+1
B:rear=(rear+1)mod(n-1)
C:rear=(rear+1)modn
D:rear=(rear+1)mod(n+1)
答案: rear=(rear+1)mod(n+1)
7、 用链式存储方式的队列进行删除操作时需要（ ）。
A:仅修改头指针
B:仅修改尾指针
C:头尾指针都要修改
D:头尾指针可能都要修改
答案: 头尾指针可能都要修改
8、 在用单链表实现队列时，队头在链表的（ ）位置。
A:链头
B:链尾
C:链中
D:以上都可以
答案: 链头
9、 最不适合用做链式队列的链表是（ ）。
A:只带队首指针的非循环双链表
B:只带队首指针的循环双链表
C:只带队尾指针的循环双链表
D:只带队尾指针的循环单链表
答案: 只带队首指针的非循环双链表
10、 已知循环队列的存储空间为数组A[21], front指向队头元素的前一个位置，rear指向队尾元素，假设当前front和rear的值分别为8和3,则该队列的长度为（ ）。
A:5
B:6
C:16
D:17
答案: 16
11、 允许对队列进行的操作有（ ）。
A:对队列中的元素排序
B:取出最近进队的元素
C:在队列元素之间插入元素
D:删除队头元素
答案: 删除队头元素
12、 在一个顺序存储的循环队列中，队头指针指向队头元素的( )。
A:前一个位置
B:后一个位置
C:队头元素位置
D:队尾元素的前一位置
答案: 前一个位置
13、 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出栈的序列是e2、e4、 e3、e6、e5、e1,则栈S的容量至少应该是（ ）。
A:6
B:4
C:3
D:2
答案: 3
14、 若用一个大小为6的数组来实现循环队列，且当前 rear和 front 的值分别为 0和3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为( ) 。
A:1和5
B:2和4
C:4和2
D:5和1
答案: 2和4
15、 设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度为（ ）。
A:O(1)
B:O(n)
C:O(
)
D:O(
)
答案: O(n)
16、 在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是front==rear 。
A:正确
B:错误
答案: 正确
17、 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ ）
A:正确
B:错误
答案: 错误
18、 引入循环队列的目的是提高存储空间的利用率。
A:正确
B:错误
答案: 正确
19、 在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是front==(rear+1)% maxSize。
A:正确
B:错误
答案: 正确
20、 在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是(rear-front+1)%maxSize。
A:正确
B:错误
答案: 错误
第二讲 线性结构（2：19：00）[何钦铭] 2.1节单元测试
1、 与单链表相比，双链表（ ）。
A:可随机访问表中结点
B:访问前后结点更为便捷
C:执行插入、删除操作更为简单
D:存储密度等于 1
答案: 访问前后结点更为便捷
2、 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（ ）最节省时间。
A:单链表
B:单循环链表
C:带尾指针的单循环链表
D:带头结点的双循环链表
答案: 带头结点的双循环链表
3、 线性表（a1，a2，…，an）以链接方式存储时，访问第 i 位置元素的时间复杂度为（ ）。
A:O(i)
B:O(1)
C:O(n)
D:O(i-1)
答案: O(n)
4、 假定顺序表中的第一个数据元素的存储地址为第200个存储单元，若每个数据元素占用6个存储单元，则第4个数据元素的地址是第（ ）个存储单元。
A:218
B:224
C:230
D:212
答案: 218
5、 若将某一数组A中的元素，通过头插法插入至单链表B中（单链表初始为空），则插入完毕后，B中结点的顺序（ ）。
A:与数组中元素的顺序相反
B:与数组中元素的顺序相同
C:与数组中元素的顺序无关
D:与数组中元素的顺序部分相同、部分相反
答案: 与数组中元素的顺序相反
6、 顺序表比链表的存储密度更大，是因为（ ）。
A:顺序表的存储空间是预先分配的
B:顺序表不需要增加指针来表示元素之间的逻辑关系
C:链表的所有结点是连续的
D:顺序表的存储空间是不连续的
答案: 顺序表不需要增加指针来表示元素之间的逻辑关系
7、 下面关于线性表的叙述中，错误的是（ ）。
A:线性表采用顺序存储，必须占用一片连续的存储单元
B:线性表采用顺序存储，便于进行插入和删除操作
C:线性表采用链接存储，不必占用一片连续的存储单元
D:线性表采用链接存储，便于插入和删除操作
答案: 线性表采用顺序存储，便于进行插入和删除操作
8、 链表不具有的特点是（ ）。
A:插入、删除不需要移动元素
B:可随机访问任一元素
C:不必事先估计存储空间
D:所需空间与线性长度成正比
答案: 可随机访问任一元素
9、 单链表中，增加一个头结点的目的是为了（ ）。
A:使单链表至少有一个结点
B:标识表结点中首结点的位置
C:方便运算的实现
D:说明单链表是线性表的链式存储
答案: 方便运算的实现
10、 线性表的顺序存储结构是一种（ ）的存储结构。
A:随机存取
B:顺序存取
C:索引存取
D:散列存取
答案: 随机存取
11、 线性表是具有n个（ ）的有限序列。
A:数据表
B:字符
C:数据元素
D:数据项
答案: 数据元素
12、 一个顺序表所占用的存储空间大小与（ ）无关。
A:表的长度
B:元素的存放顺序
C:元素的类型
D:元素中各字段类型
答案: 元素的存放顺序
13、 若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为了提高效率，应采用（ ）的存储方式。
A:单链表
B:双向链表
C:单循环链表
D:顺序表
答案: 顺序表
14、 在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动( )个元素。
A:n
B:i-1
C:n-i
D:n-i-1
答案: n-i
15、 对于顺序表，访问第i个位置的元素和在第i个位置插入一个元素的时间复杂度为（ ）。
A:O(n),O(n)
B:O(n),O(1)
C:O(1),O(n)
D:O(1),O(1)
答案: O(1),O(n)
16、 单链表可以实现随机存取。
A:正确
B:错误
答案: 错误
17、 链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。
A:正确
B:错误
答案: 错误
18、 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A:正确
B:错误
答案: 错误
19、 循环链表不是线性表。
A:正确
B:错误
答案: 错误
20、 线性表的特点是每个元素都有一个前驱和一个后继。
A:正确
B:错误
答案: 错误
21、 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。
A:正确
B:错误
答案: 错误
22、 线性表若采用链式存储表示,在删除时不需要移动元素。
A:正确
B:错误
答案: 正确
23、 在线性链表中删除中间结点时，只需将被删结点释放。
A:正确
B:错误
答案: 错误
24、 链表中的头结点仅起到标识的作用。
A:正确
B:错误
答案: 错误
25、 一个顺序表所占用的存储空间大小与元素的存放顺序无关。
A:正确
B:错误
答案: 正确
26、 在仅设置了尾指针的循环链表中，访问第一个结点的时间复杂度是O(__)。
答案: 1
27、 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_存储结构。
答案: 顺序
28、 链接存储的特点是利用__来表示数据元素之间的逻辑关系。
答案: 指针
29、 将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度是O( )。
答案: m
30、 一个具有n个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为O( ) 。
答案: n
如需购买完整答案，请点击下方红字：
获取更多中国大学慕课答案，请点击这里，进入mooc.mengmianren.com
坦溯松诵垦袖彩稍红户竭裤握