大学MOOC 数据结构(中国传媒大学)1206634839 最新慕课完整章节测试答案

第二章线性表单元测验

1、单选题：
​在一个长度为n的顺序表中向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要向后移动_____      个元素。​
选项：
A: n-i 
B: n-i+1 
C: n-i-1
D: i
答案: 【 n-i+1 】

2、单选题：
‏链表不具有的特点是_____      。‎
选项：
A: 可随机访问任一元素
B: 插入元素不需要移动元素
C: 不必事先估计存储空间
D: 所需空间与线性表的长度成正比
答案: 【 可随机访问任一元素】

3、单选题：
‌在线性表的下列存储结构中，读取指定序号的元素花费时间最少的是_____      。‍
选项：
A: 单链表
B: 双向链表
C: 循环链表
D: 顺序表
答案: 【 顺序表】

4、单选题：
​对于用一维数组 d [1..n]顺序存储的线性表，其算法时间复杂度为O(1)的操作是_____      。‌
选项：
A: 将n个元素从小到大排序
B: 从线性表中删除第i个元素（1≤i≤n）
C: 查找第i个元素（1≤i≤n）
D: 向线性表的第i个元素之后插入一个元素（0≤i≤n）
答案: 【 查找第i个元素（1≤i≤n）】

5、单选题：
‌静态链表（使用数组来存储的链表）中结点内指针指示的是_____      。‌
选项：
A: 内存地址
B: 数组下标
C: 链表中下一个元素在数组中的地址
D: 左、右孩子地址
答案: 【 链表中下一个元素在数组中的地址】

6、单选题：
‌单链表L为空的判断条件是_____      。​
选项：
A: L==NULL     
B: L->next==NULL
C: L->next!=NULL
D: L!=NULL
答案: 【 L->next==NULL】

7、单选题：
‍某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_____ 存储方式最节省时间。‎
选项：
A: 单链表
B: 不带头结点且仅有头指针的单循环链表
C: 双向（非循环）链表
D: 不带头结点且仅有尾指针（指向终端结点的指针）的单循环链表
答案: 【 不带头结点且仅有尾指针（指向终端结点的指针）的单循环链表】

8、单选题：
‌在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_____ 。‏
选项：
A: O(1)
B: O(n)
C: O()
D: O()
答案: 【 O(n)】

9、单选题：
‏将两个有n个元素的有序表归并成一个有序表，其最多比较次数为_____      。‌
选项：
A: n
B: 2n-1
C: 2n
D: n-1
答案: 【 2n-1】

10、单选题：
‏在一个长度为n（n>1）的带头结点的单链表h上，另设有尾指针r（指向尾结点），执行以下                操作与链表的长度有关。‎
选项：
A: 删除单链表中的第一个结点
B: 删除单链表中的最后一个结点
C: 在单链表第一个结点前插入一个新结点
D: 在单链表最后一个结点后插入一个新结点
答案: 【 删除单链表中的最后一个结点】

11、单选题：
​在单链表中，若*p结点不是终端结点，在其后插入*s结点的操作是                。‎
选项：
A: s->next = p; p->next = s;
B: s->next = p->next; p->next = s;
C: s->next = p->next; p = s;
D: p->next = s; s->next = p;
答案: 【 s->next = p->next; p->next = s;】

12、单选题：
‏在单链表中增加一个头结点的目的是为了      。‏
选项：
A: 使单链表至少有一个结点
B: 标识链表中重要结点位置
C: 方便某些运算的实现
D: 说明单链表是线性表的链式存储结构
答案: 【 方便某些运算的实现】

13、单选题：
‎在双向链表中的*p结点之后插入一个结点*s的操作是                 。‌
选项：
A: s->prior=p; p->next=s; p->next->prior=s; s->next=p->next;
B: s->next=p->next; p->next->prior=s; p->next=s; s->prior=p;
C: p->next=s; s->prior=p; s->next=p->next; p->next->prior=s;
D: p->next->prior=s; p->next=s; s->next=p->next; s->prior=p; 
答案: 【 s->next=p->next; p->next->prior=s; p->next=s; s->prior=p;】

14、单选题：
​在双向链表中删除*p结点之后的一个结点的操作是                     。‎
选项：
A: p->next=p->next->next; p->next->next->prior=p;
B: p->next->prior=p; p->next=p->next->next;
C: p->next=p->next->next; p->next->prior=p;
D: p->next->next=p->next; p->next->prior=p; 
答案: 【 p->next=p->next->next; p->next->prior=p;】

15、单选题：
‎在带头结点*head的单循环链表中，至少有一个结点的条件是                。‎
选项：
A: head->next != NULL
B: head->next != head
C: head->next->next!=NULL
D: head!=NULL
答案: 【 head->next != head】

16、单选题：
在带头结点*head的单循环链表中至少有一个结点时，尾结点*p应该满足的条件是            。‍​‍
选项：
A: p->next==NULL
B: p==head->next
C: p == NULL
D: p->next == head
答案: 【 p->next == head】

17、单选题：
‏给定有n个元素的一维数组，建立一个有序单链表的时间复杂度是                   。‍
选项：
A: O(1)
B: O(n)
C: O()
D: O()
答案: 【 O()】

18、单选题：
‏数据结构反映了数据元素之间的结构关系，其中单链表是一种                。‏
选项：
A: 顺序存储线性表
B: 非顺序存储非线性表
C: 顺序存储表
D: 非顺序存储表
答案: 【 非顺序存储表】

19、单选题：
‌与单链表相比，双向链表的优点之一是                  。‎
选项：
A: 访问前后相邻结点更为灵活方便
B: 可以省略表头指针或表尾指针
C: 可以进行随机访问
D: 插入、删除操作更为方便
答案: 【 访问前后相邻结点更为灵活方便】

20、单选题：
‍设线性表中有2n个元素，                  在单链表上实现要比在顺序表上实现效率更高。‌
选项：
A: 删除所有值为x的元素
B: 在最后一个元素的后面插入一个新元素
C: 顺序输出前k个元素的值
D: 交换第i个元素和第2n-i+1个元素的值（i=0,...,n-1）
答案: 【 删除所有值为x的元素】

21、判断题：
‎与顺序表相比，在链表中顺序访问所有结点，其算法的效率比较低。‎
选项：
A: 正确
B: 错误
答案: 【 错误】

22、判断题：
‍如果单链表带有头结点，则插入操作永远不会改变头结点指针的值。‌‍‌
选项：
A: 正确
B: 错误
答案: 【 错误】

23、判断题：
‏在单循环链表中，任何一个结点的指针域都不可能为空。‍
选项：
A: 正确
B: 错误
答案: 【 正确】

24、判断题：
​线性表的顺序存储结构优于链式存储结构。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

25、判断题：
‏凡是为空的单链表都是不含任何结点的。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

第三章栈和队列单元测试

1、单选题：
​栈和队列具有相同的           。‏
选项：
A: 抽象数据类型
B: 逻辑结构
C: 存储结构
D: 运算
答案: 【 逻辑结构】

2、单选题：
‌若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次退栈工作，则不可能得到的出栈序列是          。‏
选项：
A: dcebfa
B: cbdae
C: bcaefd
D: afedcb
答案: 【 afedcb】

3、单选题：
‌设n个元素的进栈序列是1、2、3、…、n，其输出序列是p1、p2、p3、…、pn，若p1=n，则pi的值是          。‏
选项：
A: i
B: n-i
C: n-i+1
D: 不确定
答案: 【 n-i+1】

4、单选题：
‌设n个元素的进栈序列是1、2、3、…、n，其输出序列是p1、p2 、p3 、… 、pn，若p1=3，则p2的值是          。‌
选项：
A: 一定是2
B: 一定是1
C: 不可能是1
D: 以上都不对
答案: 【 不可能是1】

5、单选题：
经过以下队列运算后，队头的值是   B   。    InitQueue(Q);  EnQueue(Q,a);   EnQueue(Q,b);   EnQueue(Q,c);   DeQueue(Q, e);‎‏‎
选项：
A: a
B: b
C: 1
D: 0
答案: 【 b】

6、单选题：
‍设循环队列中数组的下标是0 ~ N-1，其头尾指针分别为f和r，则其元素个数为           。‍
选项：
A:  r - f 
B: r - f -1 
C:  (r - f )%N+1
D: (r – f + N) %N
答案: 【 (r – f + N) %N】

7、单选题：
‌若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，从队列中删除一个元素，再加入两个元素后，rear和front的值分别是           。‏
选项：
A: 1和5
B: 2和4
C: 4和2
D: 5和1
答案: 【 2和4】

8、单选题：
‎判定一个循环队列Q（存放元素位置0 ~ QueueSize-1），队满的条件是           。​
选项：
A: Q.front==Q.rear
B: Q.front+1==Q.rear
C: Q.front==(Q.rear+1)%QueueSize
D: Q.rear==(Q.front+1)%QueueSize
答案: 【 Q.front==(Q.rear+1)%QueueSize】

9、单选题：
假设用Q[0..M]实现循环队列，Q[f]、Q[r]分别为队头元素的前一个位置和队尾元素位置。若用(r+1)%(M+1)==f 作为队满的标志，则            。‍​‍
选项：
A: 可用f == r作为队空的标志
B: 可用f > r作为队空的标志
C: 可用(f+1)%(M+1) == r作为队空的标志
D: 队列中最多可以有M+1个元素
答案: 【 可用f == r作为队空的标志】

10、单选题：
‏最不适合用做链栈的链表是（以下链表没有头结点）          。‌
选项：
A: 只有（链表）表头指针无表尾指针的循环双链表
B: 只有表尾指针无表头指针的循环双链表
C: 只有表尾指针无表头指针的循环单链表
D: 只有表头指针无表尾指针的循环单链表
答案: 【 只有表头指针无表尾指针的循环单链表】

11、单选题：
‍设栈S和队列Q的初始状态为空，元素e1~e6依次通过栈S，每个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是           。‌
选项：
A: 5
B: 4
C: 3
D: 2
答案: 【 3】

12、单选题：
已知一个栈的进栈序列为p1、p2、p3、…、 pn，输出序列为1、2、3、…、n，若p3=1，则p1          。‌‎‌
选项：
A: 可能是2
B: 一定是2
C: 不可能是2
D: 不可能是3
答案: 【 不可能是2】

13、单选题：
​若栈采用顺序存储方式存储，现有两栈共享空间V[1..m]，top[i]代表第i（i=1,2）个栈的栈顶，栈1的底在V[1]，栈2的底在V[m]，则栈满的条件是__________。‎
选项：
A: |top[2]-top[1]|=0
B: top[1]+1=top[2]
C: top[1]+top[2]=m
D: top[1]=top[2]
答案: 【 top[1]+1=top[2]】

14、单选题：
‍递归过程和函数调用时，处理参数及返回地址要用一种称为____________的数据结构。‎
选项：
A: 队列
B: 多维数组
C: 线性表
D: 栈
答案: 【 栈】

15、判断题：
‍顺序栈中元素值的大小是有序的。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

16、判断题：
‏在n个元素进栈以后，它们的出栈顺序和进栈顺序一定正好相反。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

17、判断题：
‎栈顶元素和栈底元素有可能是同一个元素。‏
选项：
A: 正确
B: 错误
答案: 【 正确】

18、判断题：
‎若用s[1]~s[m]表示顺序栈的存储空间，则对栈的进栈和出栈操作均最多只能进行m次。​
选项：
A: 正确
B: 错误
答案: 【 错误】

19、判断题：
​栈是一种对进栈、出栈操作的次序作了限制的线性表。‏
选项：
A: 正确
B: 错误