大学MOOC 数据结构(天津职业技术师范大学)1460980162 最新慕课完整章节测试答案

第二章线性表单元测试

1、单选题：
‎线性表是具有n个 ______ 的有限序列。‍
选项：
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: 便于随机存取
C: 便于插入和删除
D: 便于利用零散的存储器空间
答案: 【 便于插入和删除】

7、单选题：
‍线性表的顺序存储结构和链式存储结构相比，优点是 _______。‌
选项：
A: 所有的操作算法实现简单
B: 便于随机存取 
C: 便于插入和删除
D: 节省存储空间
答案: 【 便于随机存取 】

8、单选题：
‌设线性表有n个元素，以下操作中，_______在顺序表上实现比在链表上实现效率高。‍
选项：
A: 输入第i（1<=i<=n）个元素值
B: 交换第1个元素第2个元素的值
C: 顺序输出这n个元素的值
D: 输出与给定值x相等的元素在线性表中的符号
答案: 【 输入第i（1<=i<=n）个元素值】

9、单选题：
‎对于一个线性表，既要求能够较快地进行插入和删除操作，又要求存储结构能够反映数据元素之间的逻辑关系，则应采用  _______ 存储结构。​
选项：
A: 顺序
B: 链式
C: 散列
D: 索引
答案: 【 链式】

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

11、单选题：
‏以下属于顺序表的优点是  _______。‍
选项：
A: 插入元素方便
B: 删除元素方便
C: 存储密度大
D: 以上都不对
答案: 【 存储密度大】

12、单选题：
‌要求线性表采用静态空间分配方式，且插入和删除操作时不需要移动元素，采用的存储结构是  _______。‍
选项：
A: 单链表
B: 静态链表
C: 双链表
D: 顺序表
答案: 【 静态链表】

13、单选题：
‎如果最常用的操作时取第i个元素及前驱元素，则采用  _______ 存储方式最节省时间。‌
选项：
A: 单链表
B: 双链表
C: 循环单链表
D: 顺序表
答案: 【 顺序表】

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

15、单选题：
‏在长度为n的顺序表中插入一个元素的时间复杂度为 _______。‌
选项：
A: O(n) 
B:  O()
C: O(log2n)   
D: O(1)
答案: 【 O(n) 】

16、单选题：
‍在长度为n的顺序表中删除一个元素的时间复杂度为 _______。‍
选项：
A:  O(1)       
B:  O()
C: O(log2n)
D: O(n)
答案: 【 O(n)】

17、单选题：
‍在两个各有n个元素的递增有序顺序表归并成一个有序顺序表，其最少的比较次数为_______。‏
选项：
A: n
B: 2n-1
C: 2n
D: n-1
答案: 【 n】

18、单选题：
‌将两个长度为n、m的递增有序表归并成一个有序顺序表，其最少的比较次数是_______。（MIN表示取最小值）‏
选项：
A: n
B: m
C: MIN(m, n)
D: 不确定
答案: 【 MIN(m, n)】

19、单选题：
‌在带头节点的单链表L为空的判定条件是 _______。​
选项：
A:  L==NULL
B: L->NEXT==NULL
C:  L->NEXT==L
D:  L!=NULL
答案: 【 L->NEXT==NULL】

20、单选题：
‍对于一个具有n个元素的线性表，建立其单链表的时间复杂度为  _______。‍
选项：
A:  O(log2n)
B: O(1)
C:  O(n)
D:  O()
答案: 【  O(n)】

21、单选题：
‎在单链表中查找指定值的节点的时间复杂度是  _______。‍
选项：
A: O(log2n)
B: O(1)
C: O() 
D: O(n)
答案: 【 O(n)】

22、单选题：
‌以下关于单链表的叙述中，不正确的是 _______。‏
选项：
A: 节点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
B: 逻辑上相邻的元素物理上不必相邻
C: 可以通过头节点直接计算第i个节点的存储地址
D: 插入、删除运算操作简单，不必移动节点
答案: 【 可以通过头节点直接计算第i个节点的存储地址】

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

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

25、单选题：
​将长度为m的单链表链接在长度为n的单链表之后的算法时间复杂度为 _______。​
选项：
A: O(1)
B: O(n)
C: O(m)
D: O(m+n)
答案: 【 O(n)】

26、单选题：
‎已知一个长度为n的单链表中所有节点是递增有序的，以下叙述中正确的是 _______。‎
选项：
A: 插入一个节点使之有序的算法的时间复杂度为O(1)
B: 删除最大值节点使之有序的算法的时间复杂度为 O(1)
C: 找最小值节点的算法的时间复杂度为 O(1)
D: 以上都不对
答案: 【 找最小值节点的算法的时间复杂度为 O(1)】

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

28、单选题：
​在一个双链表中，在*p节点之后插入节点*q的操作是 _______。‎
选项：
A: q->prior = p；p-> next=q；p -> next -> prior =q； q ->next = p -> next；
B: q ->next = p -> next；p -> next -> prior =q；p-> next=q；q->prior = p；
C: p-> next=q；q->prior = p；q ->next = p -> next；p -> next -> prior =q；
D: p -> next -> prior =q；q->prior = p；p-> next=q；q ->next = p -> next；
答案: 【 q ->next = p -> next；p -> next -> prior =q；p-> next=q；q->prior = p；】

29、单选题：
‏在一个双链表中，在*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；q-> prior ->next= q；q-> next=p；
D: p -> prior ->next=q；q-> next=p；q -> prior = p->prior；p -> prior = q；
答案: 【 p -> prior ->next=q；q-> next=p；q -> prior = p->prior；p -> prior = q；】

30、单选题：
‏在一个双链表中， 删除*p节点的操作是 _______。​
选项：
A: p -> prior –>next= p-> next；p ->next-> prior = p -> prior；
B: p ->prior= p -> prior -> prior；p -> prior ->prior = p；
C: p-> next -> prior = p；p-> next=p-> next-> next；
D: p -> next= p->prior -> prior；p-> prior = p->prior->prior；
答案: 【 p -> prior –>next= p-> next；p ->next-> prior = p -> prior；】

31、单选题：
‍在一个双链表中， 删除*p节点之后的一个节点，其时间复杂度为_______。‍
选项：
A: O(nlog2n) 
B: O(1) 
C: O(n)
D: O()
答案: 【 O(1) 】

32、单选题：
​非空的循环单链表L的尾节点（由p所指向）满足 _______。‏
选项：
A: p-> next == NULL
B: p == NULL
C: p -> next == L
D:  p==L
答案: 【 p -> next == L】

33、单选题：
‍带表头结点的双循环链表L为空表的条件是 _______。‌
选项：
A: L== NULL
B: L-> next -> prior == NULL
C: L -> prior == NULL
D: L -> next == L  
答案: 【 L -> next == L  】

34、单选题：
‍某线性表最常用的操作是在尾元素之后插入一个元素和删除尾元素，则采用 _______ 存储方式最节省运算时间。‏
选项：
A: 单链表
B: 循环单链表
C: 双链表
D: 循环双链表
答案: 【 循环双链表】

35、单选题：
‍如果对含有n（n>1）个元素的线性表的运算只有4种，即删除第一个元素、删除尾元素、在第一个元素前面插入新元素、在尾元素的后面插入新元素，则最好使用_______。‍
选项：
A: 只有尾节点指针没有头节点的循环单链表
B: 只有尾节点指针没有头节点的非循环双链表
C: 只有开始数据节点指针没有尾节点指针的循环双链表
D: 既有表头指针也有表尾指针的循环单链表
答案: 【 只有开始数据节点指针没有尾节点指针的循环双链表】

36、单选题：
‍在某线性表最常用的操作是在尾元素之后插入一个元素和删除第一个元素。故采用_______ 存储方式最节省时间。‌
选项：
A: 单链表
B: 仅有头节点指针的循环单链表
C: 双链表
D: 仅有尾指针的循环单链表
答案: 【 仅有尾指针的循环单链表】

37、单选题：
‌‌‌两个表长都为n、不带表头结点的单链表，结点类型都相同，头指针分别为h1与h2，且前者是循环链表，后者是非循环链表，则 _______。‌
选项：
A: 对于两个链表来说，删除首节点的操作，其时间复杂度都是O(1)
B: 对于两个链表来说，删除尾节点的操作，其时间复杂度都是O(n)
C: 循环链表要比非循环链表占用更多的内存空间
D: h1和h2是不同类型的变量
答案: 【 对于两个链表来说，删除尾节点的操作，其时间复杂度都是O(n)】

38、单选题：
‏在长度为n的 _______ 上，删除第一个元素，其算法的时间复杂度为O(n)。‍
选项：
A: 只有表头指针的不带表头节点的循环单链表
B: 只有表尾指针的不带表头节点的循环单链表
C: 只有表尾指针的带表头节点的循环单链表
D: 只有表头指针的带表头节点的循环单链表
答案: 【 只有表头指针的不带表头节点的循环单链表】

39、单选题：
‌下面关于线性表的叙述错误的是 _______。‍
选项：
A: 线性表采用顺序存储必须占用一片连续的存储空间        
B: 线性表采用链式存储不必占用一片连续的存储空间
C: 线性表采用链式存储便于插入和删除操作的实现
D: 线性表采用顺序存储便于插入和删除操作的实现
答案: 【 线性表采用顺序存储便于插入和删除操作的实现】

40、单选题：
​对于双链表，在两个节点之间插入一个新节点是，需要修改 _______ 个指针域。​
选项：
A: 1
B: 2
C: 3
D: 4
答案: 【 4】

41、单选题：
​在单链表中，要删除某一指定的节点，必须找到该节点的 _______ 节点。‍
选项：
A: 后继
B: 头节点
C: 前驱
D: 尾节点
答案: 【 前驱】

42、单选题：
​求一个单链表长度的算法的时间复杂度为  _______。​
选项：
A: O(log2n)
B:   O(n)
C: O(1) 
D:  O()
答案: 【   O(n)】

43、判断题：
‍线性表中每个元素都有一个前驱元素和一个后继元素。‎
选项：
A: 正确
B: 错误
答案: 【 错误】

44、判断题：
‎线性表中所有元素的排列顺序必须从小到大或从大到小。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

45、判断题：
‍静态链表既有顺序存储结构的优点，又有动态链表的优点，所以，利用它存取第i个元素的时间与元素个数n无关。‎
选项：
A: 正确
B: 错误
答案: 【 错误】

46、判断题：
‎静态链表与动态链表在元素的插入、删除方面类似，不需要做元素的移动。‏
选项：
A: 正确
B: 错误
答案: 【 正确】

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

48、判断题：
‏在循环单链表中，从表中任一节点出发都可以通过前后移动操作遍历整个循环链表。‎
选项：
A: 正确
B: 错误
答案: 【 错误】

49、判断题：
‏在单链表中，可以从头节点开始查找任何一个节点。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

50、判断题：
‎在双链表中，可以从任一节点开始沿着同一方向查找到任何其他节点。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

第三章栈和队列单元测试

1、单选题：
​元素A、B、C、D依次进栈后，栈顶元素是 _______。‏
选项：
A: A
B: B
C: C
D: D
答案: 【 D】

2、单选题：
经过以下运算后， x的值是 _______。‍InitStack (s); Push(s, a); Push(s, b); Pop(s, x); GetTop(s,x)‍‌‍
选项：
A: a
B: b
C: 1
D: 0
答案: 【 a】

3、单选题：
经过以下栈运算后，StackEmpty(s)的值是 _______。​InitStack (s); Push(s, a); Push(s, b); Pop(s, x); Pop(s,y)​‎​
选项：
A: a
B: b
C: 1
D: 0
答案: 【 1】

4、单选题：
已知一个栈的进栈序列是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】

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

6、单选题：
‎设一个栈的输入序列为A、B、C、D，则借助一个栈所得的输出序列不可能是_______。‍
选项：
A: ABCD
B: DCBA
C: ACDB
D: DABC
答案: 【 DABC】

7、单选题：
一个栈的进栈序列是abcde，则栈的不可能的输出序列是 _______。‍‍‍
选项：
A: edcba
B: decba
C: dceab
D: abcde
答案: 【 dceab】

8、单选题：
已知一个栈的进栈序列是1，2，3，…n，其输出序列的第一个元素是i（1≤i≤n），则第j（1≤j≤n）个出栈元素是_______。​‍​
选项：
A: i
B: n-i
C: j-i+1
D: 不确定
答案: 【 不确定】

9、单选题：
‍已知一个栈的进栈序列是1,2,3，…n，其输出序列是p1,p2,…pn，若p1=n,则pi的值是_______。​
选项：
A: i
B: n-i
C: n-i+1
D: 不确定
答案: 【 n-i+1】

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

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

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

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

14、单选题：
‌设有5个元素的进栈序列是a，b，c，d，e，其输出序列是c，e，d，b，a，则该栈的容量至少是 _______。‎‌‎
选项：
A: 1
B: 2
C: 3
D: 4
答案: 【 4】

15、单选题：
‎在数据处理过程中常需要保存一些中间数据，如果后保存的数据先处理，则使用_______来保存这些数据。‏
选项：
A: 线性表
B: 栈
C: 队列
D: 单链表
答案: 【 栈】

16、单选题：
‌判定一个顺序栈st为（元素个数最多为MaxSize）空的条件为  _______。​
选项：
A: st.top==-1
B:  st.top!=-1
C: st.top!=MaxSize
D: st.top==MaxSize
答案: 【 st.top==-1】

17、单选题：
​判定一个顺序栈st为（元素个数最多为MaxSize）为栈满的条件为  _______。‏
选项：
A:  st.top！==-1 
B: st.top=-1
C: st.top!=MaxSize-1
D: st.top==MaxSize-1
答案: 【 st.top==MaxSize-1】

18、单选题：
‏表达式a*(b+c)-d的后缀表达式是 _______。‍
选项：
A: a b c d * + -
B: a b c + * d -
C: a b c * + d - 
D: - + * a b c d 
答案: 【 a b c + * d -】

19、单选题：
‎若一个栈用数组data[1..n]存储，初始栈顶指针top为n+1，则以下元素x进入栈的正确操作是 _______。‍
选项：
A: top++; data[top]=x;
B: data[top]=x;top++;
C: top--; data[top]=x;
D: data[top]=x;top--;
答案: 【 top--; data[top]=x;】

20、单选题：
‌若一个栈用数组data[1..n]存储，初始栈顶指针top为n，则以下元素x进入栈的正确操作是 _______。‍
选项：
A: top++; data[top]=x;
B: data[top]=x;top++;
C: top--; data[top]=x;
D:  data[top]=x;top--;
答案: 【  data[top]=x;top--;】

21、单选题：
‌若一个栈用数组data[1..n]存储，初始栈顶指针top为0，则以下元素x进入栈的正确操作是 _______。‏
选项：
A: top++; data[top]=x; 
B:  data[top]=x;top++;
C: top--; data[top]=x; 
D: data[top]=x;top--;
答案: 【 top++; data[top]=x; 】

22、单选题：
‎若一个栈用数组data[1..n]存储，初始栈顶指针top为1，则以下元素x进入栈的正确操作是 _______。‍
选项：
A: top++; data[top]=x; 
B: data[top]=x;top++;
C: top--; data[top]=x;
D: data[top]=x;top--;
答案: 【 data[top]=x;top++;】

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

24、单选题：
‏以下各链表均不带有头节点，其中最不合适用作链栈的链表是 _______。‏
选项：
A: 只有表头指针没有表尾指针的循环双链表
B: 只有表尾指针没有表头指针的循环双链表
C: 只有表尾指针没有表头指针的循环单链表
D: 只有表头指针没有表尾指针的循环单链表
答案: 【 只有表头指针没有表尾指针的循环单链表】

25、单选题：
‏如果以链表作为栈的存储结构，则退栈操作时 _______。‌
选项：
A: 必须判断链栈是否为满