大学MOOC 2020年春数据结构B(SPOC)(余文君)(华中农业大学)1450084161 最新慕课完整章节测试答案
第1章绪论
绪论
1、单选题：
在数据结构中，从逻辑上可以把数据结构分成________。
选项：
A: 动态结构和静态结构
B: 紧凑结构和非紧凑结构
C: 线性结构和非线性结构
D: 内部结构和外部结构
答案: 【 线性结构和非线性结构】
2、单选题：
算法分析的目的是________。
选项：
A: 找出数据结构的合理性
B: 研究算法中的输入和输出的关系
C: 分析算法的效率以求改进
D: 分析算法的易懂性和文档性
答案: 【 分析算法的效率以求改进 】
3、单选题：
算法分析的两个主要方面是________。
选项：
A: 空间复杂度和时间复杂度
B: 正确性和简单性
C: 可读性和文档性
D: 数据复杂性和程序复杂性
答案: 【 空间复杂度和时间复杂度】
4、单选题：
计算机算法指的是解决问题的有限运算序列，它必须具备输入、输出和________等5个特性。
选项：
A: 可执行性、可移植性和可扩充性
B: 可行性、确定性和有穷性
C: 确定性、有穷性和稳定性
D: 易读性、稳定性和安全性
答案: 【 可行性、确定性和有穷性】
5、单选题：
下面程序段的时间复杂度为____________。for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;
选项：
A: O(m2)
B: O(n2)
C: O(m*n)
D: O(m+n)
答案: 【 O(m*n) 】
6、单选题：
执行下面程序段时，执行S语句的次数为____________。for(int i=1; i<=n; i++)for(int j=1; j<=i; j++) S;
选项：
A: n2
B: n2/2
C: n(n+1)
D: n(n+1)/2
答案: 【 n(n+1)/2】
7、单选题：
下面算法的时间复杂度为____________。int f( unsigned int n ) {if ( n==0 || n==1 ) return 1; else return n*f(n-1); }
选项：
A: O(1)
B: O(n)
C: O(n2)
D: O(n!)
答案: 【 O(n)】
8、单选题：
下面程序段的时间复杂性的量级为____________。for(i=1;i＜＝n; i++) for(j=1;j＜＝m; j++){c[i][j]=0; for(k=1;k＜＝w;k++)c[i][j]+=a[i][k]*b[k][j] }
选项：
A: O(i*j*k)
B: O(n*m*k)
C: O(n*j*k)
D: O(n*m*w)
答案: 【 O(n*m*w)】
9、单选题：
下面关于算法说法错误的是____________。
选项：
A: 算法最终必须由计算机程序实现
B: 为解决某问题的算法同为该问题编写的程序含义是相同的
C: 算法的可行性是指指令不能有二义性
D: 以上几个都是错误的
答案: 【 算法的可行性是指指令不能有二义性】
10、多选题：
数据结构是一门研究非数值计算的程序设计问题中计算机的 ① 以及它们之间的 ② 和运算等的学科。
选项：
A: 数据元素
B: 关系
C: 逻辑存储
D: 数据映象
答案: 【 数据元素;
关系】
第2章线性表
线性表
1、单选题：
线性表是_______ 。
选项：
A: 一个有限序列，可以为空
B: 一个有限序列，不能为空
C: 一个无限序列，可以为空
D: 一个无序序列，不能为空。
答案: 【 一个有限序列，可以为空】
2、单选题：
对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的_______个元素。
选项：
A: n/2
B: (n+1)/2
C: (n –1)/2
D: n
答案: 【 n/2】
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、单选题：
单链表中，增加一个头结点的目的是为了_______。
选项：
A: 使单链表至少有一个结点
B: 标识表结点中首结点的位置
C: 方便运算的实现
D: 说明单链表是线性表的链式存储
答案: 【 方便运算的实现 】
9、单选题：
若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_______存储方式最节省运算时间。
选项：
A: 单链表
B: 仅有头指针的单循环链表
C: 双链表
D: 仅有尾指针的单循环链表
答案: 【 仅有尾指针的单循环链表】
10、单选题：
若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用_______存储方式最节省运算时间。
选项：
A: 单链表
B: 顺序表
C: 双链表
D: 单循环链表
答案: 【 顺序表】
11、单选题：
一个向量(一种顺序表)第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是_______。
选项：
A: 110
B: 108
C: 100
D: 120
答案: 【 108】
12、单选题：
不带头结点的单链表head为空的判定条件是______。
选项：
A: head = = NULL;
B: head->next = = NULL;
C: head->next = = head;
D: head! = NULL;
答案: 【 head = = NULL;】
13、单选题：
带头结点的单链表head为空的判定条件是______。
选项：
A: head = = NULL;
B: head->next = = NULL;
C: head->next = = head;
D: head! = NULL;
答案: 【 head->next = = NULL;】
14、单选题：
在一个单链表中，若p所指结点不是最后结点，在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;】
15、单选题：
在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行______。
选项：
A: s->next=p->next; p->next=s;
B: p->next=s->next; s->next=p;
C: q->next=s; s->next=p;
D: p->next=s; s->next=q;
答案: 【 q->next=s; s->next=p; 】
16、单选题：
从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_____个结点。
选项：
A: n
B: n/2
C: (n-1)/2
D: (n+1)/2
答案: 【 (n+1)/2】
17、单选题：
给定有n个结点的向量，建立一个有序单链表的时间复杂度_______。
选项：
A: O(1)
B: O(n)
C: O(n^2)
D: O(nlogn)
答案: 【 O(n^2)】
18、单选题：
顺序存储结构是一种___的存储结构。
选项：
A: 随机存取
B: 索引存取
C: 顺序存取
D: 散列存取
答案: 【 随机存取】
19、单选题：
在以下的叙述中，正确的是___。
选项：
A: 线性表的顺序存储结构优于链表存储结构
B: 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
C: 线性表的链表存储结构适用于频繁插入/删除数据元素的情况
D: 线性表的链表存储结构优于顺序存储结构
答案: 【 线性表的链表存储结构适用于频繁插入/删除数据元素的情况】
20、单选题：
非空的循环单链表head的尾结点（由p所指向）满足____。
选项：
A: p->next= =NULL
B: p= =NULL
C: p->next= =head
D: p= =head
答案: 【 p->next= =head】
21、单选题：
在一个单链表中，若删除p所指结点的后续结点，则执行____。
选项：
A: p->next= p->next->next；
B: p= p->next; p->next= p->next->next；
C: p->next= p->next;
D: p= p->next->next；
答案: 【 p->next= p->next->next；】
22、单选题：
在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移____个元素。
选项：
A: n-i
B: n-i+1
C: n-i-1
D: i
答案: 【 n-i+1】
23、单选题：
在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移____个元素。
选项：
A: n-i
B: n-i+1
C: n-i-1
D: i
答案: 【 n-i】
24、单选题：
在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为____。
选项：
A: n
B: n/2
C: (n+1)/2
D: (n-1)/2
答案: 【 (n+1)/2】
25、单选题：
在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行____。
选项：
A: HL = p; p->next = HL;
B: p->next = HL; HL = p;
C: p->next = HL; p = HL;
D: p->next = HL->next; HL->next = p;
答案: 【 p->next = HL; HL = p;】
26、单选题：
一个带头结点head的循环单链表为空的判断条件是____。
选项：
A: head==NULL
B: head->next==NULL
C: head->next==head
D: head!=NULL
答案: 【 head->next==head】
27、单选题：
在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行____。
选项：
A: p = q->next ; p->next = q->next;
B: p = q->next ; q->next = p;
C: p = q->next ; q->next = p->next;
D: q->next = q->next->next; q->next = q;
答案: 【 p = q->next ; q->next = p->next;】
28、单选题：
将两个各有n个元素的有序表归并成一个有序表，在最坏的情况下，其比较次数是____。
选项：
A: 2n-1
B: n
C: n+1
D: n-1
答案: 【 2n-1】
29、判断题：
线性表的逻辑顺序与存储顺序总是一致的。
选项：
A: 正确
B: 错误
答案: 【 错误】
30、判断题：
顺序存储的线性表可以按序号随机存取。
选项：
A: 正确
B: 错误
答案: 【 正确】
31、判断题：
顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。
选项：
A: 正确
B: 错误
答案: 【 正确】
32、判断题：
线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。
选项：
A: 正确
B: 错误
答案: 【 正确】
33、判断题：
在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。
选项：
A: 正确
B: 错误
答案: 【 错误】
34、判断题：
在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
选项：
A: 正确
B: 错误
答案: 【 正确】
35、判断题：
线性表的链式存储结构优于顺序存储结构。
选项：
A: 正确
B: 错误
答案: 【 错误】
36、判断题：
在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。
选项：
A: 正确
B: 错误
答案: 【 正确】
37、判断题：
线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
选项：
A: 正确
B: 错误
答案: 【 正确】
38、判断题：
在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
选项：
A: 正确
B: 错误
答案: 【 错误】
39、判断题：
线性表中，每一个元素均存在前驱。
选项：
A: 正确
B: 错误
答案: 【 错误】
40、判断题：
线性表中，每一个元素均存在后继。
选项：
A: 正确
B: 错误
答案: 【 错误】
41、判断题：
线性表中，存在唯一一个被称为第一元素的元素。
选项：
A: 正确
B: 错误
答案: 【 正确】
42、判断题：
线性表中，存在唯一一个被称为最后一个元素的元素。
选项：
A: 正确
B: 错误
答案: 【 正确】
43、判断题：
线性结构是一种一对一的结构。
选项：
A: 正确
B: 错误
答案: 【 正确】
第3章栈和队列
栈和队列
1、单选题：
一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是____。
选项：
A: edcba
B: decba
C: dceab
D: abcde
答案: 【 dceab 】
2、单选题：
若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为____。
选项：
A: i
B: n=i
C: n-i+1
D: 不确定
答案: 【 n-i+1】
3、单选题：
栈结构通常采用的两种存储结构是____。
选项：
A: 顺序存储结构和链式存储结构
B: 散列方式和索引方式
C: 链表存储结构和数组
D: 线性存储结构和非线性存储结构
答案: 【 顺序存储结构和链式存储结构】
4、单选题：
判定一个顺序栈ST（最多元素为m0）为空的条件是____。
选项：
A: top !=0
B: top= =0
C: top !=m0
D: top= =m0-1
答案: 【 top= =0】
5、单选题：
判定一个顺序栈ST（最多元素为m0）为栈满的条件是____。
选项：
A: top！=0
B: top= =