MOOC 数据结构与算法(桂林电子科技大学)1205728807 最新慕课完整章节测试答案
CH1 概述
概述测验
1、单选题：
for（i=0；i<m；i++）for（j=0；j<n；j++）A[i][j]=i*j；上面算法的时间复杂度为( )
选项：
A: O(m×n）
B: 
C: 
D: O(m+n）
答案: 【 O(m×n）】
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、单选题：
算法评价标准包括正确性、可读性、健壮性和（）
选项：
A: 高效性
B: 有穷性
C: 可行性
D: 确定性
答案: 【 高效性】
9、单选题：
分析下面语句是时间复杂度为（）for(count = 0, i = 1; i <= n; i=i*2) count++;
选项：
A: 
B: O(n)
C: O(2n)
D: 
答案: 【 】
10、单选题：
在数据结构中，从逻辑上可以把数据结构分成（）
选项：
A: 线性结构和非线性结构
B: 动态结构和静态结构
C: 紧凑结构和非紧凑结构
D: 内部结构和外部结构
答案: 【 线性结构和非线性结构】
11、单选题：
下面程序段的时间复杂度是（）。s=0;for (i=0;i<n;i++) for (j=0;j<n;j++) s+=B[i][j];sum=s;
选项：
A: O(n^{2})
B: O(n)
C: O(n^{1/2})
D: O(2n)
答案: 【 O(n^{2}) 】
12、单选题：
下面程序段的时间复杂度是（）。for (i=0;i<n;i++) for (j=0;j<m;j++) A[i][j]=0;
选项：
A: O(m*n)
B: O(m)
C: O(n)
D: O(n*n)
答案: 【 O(m*n)】
13、单选题：
下面程序段的时间复杂度是（）。for (i=0;i<n;i++) for(j=0;j<n;j++) s+=B[i][j]
选项：
A: 
B: <span style="color: rgb(51, 51, 51);font-family: "&">O(n)
C: 
D: O(2n)
答案: 【 】
14、单选题：
下面程序段的时间复杂度是（）。for(count = 0, i = 1; i <= n; i++) for(j = 1; j <=n;
j=j*2)
count++;
选项：
A: 
B: 
C: O(n)
D: 
答案: 【 】
15、单选题：
若一个算法中的语句频度之和是
，则算法的时间复杂度为（）
选项：
A:
B: O(n)
C: 
D: 
答案: 【
】
CH2 线性表
线性表测验
1、单选题：
从一个长度为n的顺序表中删除第i个元素（0 ≤ i
≤ n-1）时，需向前移动的元素的个数是（）
选项：
A: n-i-1
B: i
C: n-i+1
D: n-i
答案: 【 n-i-1】
2、单选题：
设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）
选项：
A: q=p->next；p->data=q->data；p->next=q->next；free(q)；
B: q=p->next；q->data=p->data；p->next=q->next；free(q)；
C: q=p->next；p->next=q->next；free(q)；
D: q=p->next；p->data=q->data；free(q)；
答案: 【 q=p->next；p->data=q->data；p->next=q->next；free(q)； 】
3、单选题：
链表不具有的特点是（）
选项：
A: 可随机访问任一元素
B: 插入和删除时不需要移动元素
C: 不必事先估计存储空间
D: 所需空间与线性表的长度成正比
答案: 【 可随机访问任一元素】
4、单选题：
在双向链表存储结构中，删除p所指的结点的前趋结点（若存在）时需修改指针（ ）
选项：
A: ((p->llink) ->llink) ->rlink=p; p->llink=(p->llink) ->llink;
B: ((p->rlink) ->rlink) ->llink=p; p->rlink=(p->rlink) ->rlink;
C: (p->llink) ->rlink=p->rlink; (p->rlink) ->llink=p->llink;
D: p->llink=(p->llink) ->llink; ((p->llink) ->llink) ->rlink=p;
答案: 【 ((p->llink) ->llink) ->rlink=p; p->llink=(p->llink) ->llink;】
5、单选题：
对线性表进行二分查找时，要求线性表必须（）
选项：
A: 以顺序方式存储，且结点按关键字有序排序
B: 以顺序方式存储
C: 以链接方式存储
D: 以链接方式存储，且结点按关键字有序排序
答案: 【 以顺序方式存储，且结点按关键字有序排序】
6、单选题：
在一个单链表中，若删除p所指结点的后续结点，则语句执行顺序为（）
选项：
A: q=p—＞next;p—＞next= q—＞next;free(q)
B: p—＞next= p—＞next;free(p->next)
C: p= p—＞next; p—＞next= p—＞next—＞next;free(p)
D: p= p—＞next—＞next;free(p->next)
答案: 【 q=p—＞next;p—＞next= q—＞next;free(q)】
7、单选题：
带头结点的单链表head为空的判定条件是()
选项：
A: head—＞next= =NUL
B: head= =NULL
C: head—＞next= =head
D: head!=NULL
答案: 【 head—＞next= =NUL】
8、单选题：
在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入结点s，则执行的操作序列是( )
选项：
A: q->next=s; s->next=p
B: s->next=p->next; p->next=s
C: p->next= s－>next; s->next=p
D: p->next = s; s->next=q
答案: 【 q->next=s; s->next=p 】
9、单选题：
某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
选项：
A: 仅有尾指针的单循环链表
B: 非循环的单链表
C: 非循环的双链表
D: 仅有头指针的单循环链表
答案: 【 仅有尾指针的单循环链表】
10、单选题：
一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功时的比较次数为（）
选项：
A: 4
B: 3
C: 5
D: 6
答案: 【 4】
11、单选题：
对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）
选项：
A: 用尾指针表示的单循环链表
B: 顺序表
C: 用头指针表示的单循环链表
D: 单链表
答案: 【 用尾指针表示的单循环链表】
12、单选题：
顺序表具有的特点是（）
选项：
A: 随机访问
B: 不必事先估计所需存储空间大小
C: 插入与删除时不必移动元素
D: 顺序表的插入与删除时的时间复杂度比链式存储的要高
答案: 【 随机访问】
13、单选题：
在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（）
选项：
A: O(n)
B: O(1)
C: 
D: 
答案: 【 O(n)】
14、单选题：
在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的( )
选项：
A: 直接后继
B: 直接前趋
C: 开始结点
D: 终端结点
答案: 【 直接后继】
15、单选题：
设顺序表为{4，6，12，32，40，42，50，60，72 },用折半查找法查找72，需要进行的键值比较次数为( )
选项：
A: 4
B: 2
C: 3
D: 5
答案: 【 4】
16、单选题：
若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为（）
选项：
A: 9，4，2，3
B: 1，2，3
C: 9，5，2，3
D: 9，5，3
答案: 【 9，4，2，3】
17、单选题：
若最常用的操作是读取线性表中某个位置元素的值，则采用（ ）存储方式最节省时间
选项：
A: 顺序表
B: 带尾指针的单链表
C: 带尾指针的单循环链表
D: 单链表
答案: 【 顺序表】
18、单选题：
设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为( )
选项：
A: 239
B: 236
C: 242
D: 245
答案: 【 239】
19、单选题：
设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）
选项：
A: O(n)
B: O(1)
C: 
D: 
答案: 【 O(n)】
20、单选题：
在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ ）
选项：
A: 指向后继元素的指针表示
B: 数据元素的相邻地址表示
C: 数据元素在表中的序号表示
D: 数据元素的值表示
答案: 【 指向后继元素的指针表示】
21、单选题：
从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点
选项：
A: n/2
B: n
C: 2n
D: 1
答案: 【 n/2】
22、单选题：
在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上（）
选项：
A: 不一定相邻
B: 一定相邻
C: 一定不相邻
D: 以上答案都不对
答案: 【 不一定相邻】
23、单选题：
使用双向链表存储数据，其优点是（）
选项：
A: 很方便地插入和删除数据
B: 提高检索速度
C: 节约存储空间
D: 很快回收存储空间
答案: 【 很方便地插入和删除数据】
24、单选题：
在下图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两条语句实现该操作，它们依次是（）
选项：
A: s→link→link = p→link；p→link = s；
B: b→link = p→link；p→link = a；
C: p→link = s；s→link→link = p→link；
D: s→link = p→link；p→link = s；
答案: 【 s→link→link = p→link；p→link = s；】
25、单选题：
对以下双链表分别执行如下程序段，说明执行结果中，各个结点的数据域分别是（）
p = rear;
while( p→llink != head ) { p→info = p→info * 3; p = p→llink; }
选项：
A: 5，21，27
B: 5，7，27
C: 15，21，27
D: 5，7，9
答案: 【 5，21，27】
26、单选题：
对以下单循环链表分别执行下列程序段，说明执行结果中，各个结点的数据域分别是（）
p = tail→link→link; p→info = tail→info;
选项：
A: 8，3，6，8
B: 2，3，6，8
C: 2，8，6，8
D: 2，3，6，2
答案: 【 8，3，6，8】
27、单选题：
对以下单链表执行如下程序段，说明执行结果中，各个结点的数据域分别是（）
void fun (Linklist H) //H是带有头结点的单链表
{ PNode p,q;
p=H->link;
H->link=NULL;
while (p)