大学MOOC 数据结构与算法(桂林电子科技大学)1002997002 最新慕课完整章节测试答案
第1章 绪论
第1章习题测试
1、单选题：
for（i=0；i<m；i++）for（j=0；j<n；j++）A[i][j]=i*j；上面算法的时间复杂度为( )
选项：
A: 
B: 
C: O(m×n)
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、单选题：
在以下的叙述中，正确的是（）
选项：
A: 线性表的线性存储结构优于链表存储结构
B: 二维数组是其数据元素为线性表的线性表
C: 栈的操作方式是先进先出
D: 队列的操作方式和先进后出
答案: 【 二维数组是其数据元素为线性表的线性表】
10、单选题：
在数据结构中，从逻辑上可以把数据结构分成（）
选项：
A: 动态结构和静态结构
B: 紧凑结构和非紧凑结构
C: 线性结构和非线性结构
D: 内部结构和外部结构
答案: 【 线性结构和非线性结构】
11、单选题：
分析下面语句是时间复杂度为（）for(count = 0, i = 1; i <= n; i=i*2) count++;
选项：
A: O(n)
B: O(2n)
C: 
D: 
答案: 【 】
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、单选题：
下面程序段的时间复杂度是（）。s=0;for (i=0;i<n;i++) for (j=0;j<n;j++) s+=B[i][j];sum=s;
选项：
A: O(n)
B: 
C: O(2n)
D:
答案: 【 】
14、单选题：
下面程序段的时间复杂度是（）。for(count = 0, i = 1; i <= n; i++) for(j = 1; j <=n; j=j*2) count++;
选项：
A:
B: O(n)
C:
D: 
答案: 【 】
15、单选题：
在数据结构中，与所使用的计算机无关的数据叫（）结构。
选项：
A: 存储
B: 物理
C: 逻辑
D: 物理和逻辑
答案: 【 逻辑】
16、单选题：
若一个算法中的语句频度之和是
，则算法的时间复杂度为（）
选项：
A: O(n)
B:
C:
D:
答案: 【 】
17、填空题：
数据结构研究3个要素分别是数据的逻辑结构、（）和数据的操作。
答案: 【 数据的物理结构##%_YZPRLFH_%##数据的物理存储##%_YZPRLFH_%##物理结构##%_YZPRLFH_%##物理存储##%_YZPRLFH_%##数据的存储结构】
18、填空题：
数据的物理结构包括顺序存储结构、（ ）、散列存储结构和索引存储结构
答案: 【 链式存储结构##%_YZPRLFH_%##链式存储表示##%_YZPRLFH_%##链式表示】
19、填空题：
数据的逻辑结构是指数据元素之间的（ ）关系，这种关系是从具体实际问题抽象出来的数学模型，是独立于在计算机中的存储形式的。
答案: 【 逻辑】
20、填空题：
数据结构中评价算法的两个重要指标是（ ）和空间复杂度
答案: 【 时间复杂度##%_YZPRLFH_%##时间效率】
21、填空题：
数据结构是研讨数据的逻辑结构和（ ），以及它们之间的相互关系，并对与这种结构定义相应的运算、设计出相应的算法
答案: 【 物理结构##%_YZPRLFH_%##物理存储##%_YZPRLFH_%##存储结构】
22、填空题：
抽象数据类型ADT的定义为具有一定行为的抽象（数学）类型。它不关心类型中值的具体表示方式和操作的具体实现。ADT的全称是（ ）
答案: 【 Abstract Data Type##%_YZPRLFH_%##abstract data type##%_YZPRLFH_%##abstract Data Type##%_YZPRLFH_%##Abstract data Type##%_YZPRLFH_%##Abstract Data type】
23、填空题：
线性结构中元素之间存在一对一的关系，树形结构中元素之间存在( )关系，图形结构中元素之间存在多对多的关系。
答案: 【 一对多的##%_YZPRLFH_%##一对多】
24、填空题：
算法（ ）性质是指算法必须在执行了有穷步之后结束，并且每一步在有穷的时间内完成。
答案: 【 有穷性】
25、填空题：
算法（）性质是指算法中的每一条指令必须有确定的含义，没有二义性，对相同的输入必须有相同的输出。
答案: 【 确定性】
26、填空题：
当用户的输入非法时，算法应能够识别并做出相应的反应或处理，而不是产生错误动作和陷入中断状态。因此对应非法输入应返回错误标记加以识别，以方便高层调用时能够做出处理。以上是指算法的（）评价标准
答案: 【 健壮性】
27、填空题：
算法是针对具体需求设计的，应满足预先设定的功能和性能要求，要求对于给定的合法输入都要产生正确的输出。这是指算法的（ ）评价标准
答案: 【 正确性】
28、填空题：
算法的执行时间是( )的函数。
答案: 【 问题规模##%_YZPRLFH_%##问题的规模##%_YZPRLFH_%##问题规模n##%_YZPRLFH_%##问题的规模n】
29、填空题：
线性结构中元素之间存在一对一的关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在（）的关系。
答案: 【 多对多】
30、填空题：
线性结构中元素之间存在（）的关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多的关系
答案: 【 一对一】
第2章 线性表
第2章习题测试
1、单选题：
从一个长度为n的顺序表中删除第i个元素（0 ≤ i ≤ n-1）时，需向前移动的元素的个数是（）
选项：
A: i
B: n-i+1
C: n-i
D: n-i-1
答案: 【 n-i-1】
2、单选题：
设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）
选项：
A: q=p->next；q->data=p->data；p->next=q->next；free(q)；
B: q=p->next；p->next=q->next；free(q)；
C: q=p->next；p->data=q->data；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: p—＞next= p—＞next;free(p->next)
B: q=p—＞next;p—＞next= q—＞next;free(q)
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= =NULL
B: head—＞next= =NUL
C: head—＞next= =head
D: head!=NULL
答案: 【 head—＞next= =NUL】
8、单选题：
在一个单链表中，已知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 】
9、单选题：
某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
选项：
A: 非循环的单链表
B: 非循环的双链表
C: 仅有尾指针的单循环链表
D: 仅有头指针的单循环链表
答案: 【 仅有尾指针的单循环链表】
10、单选题：
一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功时的比较次数为（）
选项：
A: 3
B: 4
C: 5
D: 6
答案: 【 4】
11、单选题：
对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）
选项：
A: 顺序表
B: 用头指针表示的单循环链表
C: 单链表
D: 用尾指针表示的单循环链表
答案: 【 用尾指针表示的单循环链表】
12、单选题：
顺序表具有的特点是（）
选项：
A: 不必事先估计所需存储空间大小
B: 随机访问
C: 插入与删除时不必移动元素
D: 顺序表的插入与删除时的时间复杂度比链式存储的要高
答案: 【 随机访问】
13、单选题：
在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（）
选项：
A: O(1)
B: O(n)
C:
D:
答案: 【 O(n)】
14、单选题：
在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的( )
选项：
A: 直接前趋
B: 直接后继
C: 开始结点
D: 终端结点
答案: 【 直接后继】
15、单选题：
设顺序表为{4，6，12，32，40，42，50，60，72 },用折半查找法查找72，需要进行的键值比较次数为( )
选项：
A: 2
B: 3
C: 4
D: 5
答案: 【 4】
16、单选题：
若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为（）
选项：
A: 1，2，3
B: 9，5，2，3
C: 9，5，3
D: 9，4，2，3
答案: 【 9，4，2，3】
17、单选题：
若最常用的操作是读取线性表中某个位置元素的值，则采用（ ）存储方式最节省时间
选项：
A: 带尾指针的单链表
B: 带尾指针的单循环链表
C: 单链表
D: 顺序表
答案: 【 顺序表】
18、单选题：
设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为( )
选项：
A: 236
B: 239
C: 242
D: 245
答案: 【 239】
19、单选题：
设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）
选项：
A: O(1)
B:
C:
D: O(n)
答案: 【 O(n)】
20、单选题：
在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ ）
选项：
A: 数据元素的相邻地址表示
B: 数据元素在表中的序号表示
C: 指向后继元素的指针表示
D: 数据元素的值表示
答案: 【 指向后继元素的指针表示】
21、单选题：
从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点
选项：
A: n
B: n/2
C: 2n
D: 1
答案: 【 n/2】
22、单选题：
在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上（）
选项：
A: 一定相邻
B: 一定不相邻
C: 不一定相邻
D: 以上答案都不对
答案: 【 不一定相邻】
23、单选题：
使用双向链表存储数据，其优点是（）
选项：
A: 提高检索速度
B: 很方便地插入和删除数据
C: 节约存储空间
D: 很快回收存储空间
答案: 【 很方便地插入和删除数据】
24、单选题：
在下图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两条语句实现该操作，它们依次是（）
选项：
A: b→link = p→link；p→link = a；
B: p→link = s；s→link→link = p→link；
C: s→link→link = p→link；p→link = s；
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，7，27
B: 15，21，27
C: 5，21，27
D: 5，7，9
答案: 【 5，21，27】
26、单选题：
对以下单循环链表分别执行下列程序段，说明执行结果中，各个结点的数据域分别是（）
p = tail→link→link; p→info = tail→info;
选项：
A: 2，3，6，8
B: 2，8，6，8
C: 2，3，6，2
D: 8，3，6，8
答案: 【 8，3，6，8】
27、单选题：
对以下单链表执行如下程序段，说明执行结果中，各个结点的数据域分别是（）
void fun (Linklist H) //H是带有头结点的单链表
{ PNode p,q;
p=H->link;
H->link=NULL;
while (p)
{ q=p; p=p->link;
q->link=H->link;
H->link=q;
}
}
选项：
A: 2，4，6，8
B: 8，6，4，2
C: 2，8，6，4
D: 2，4，8，6
答案: 【 8，6，4，2】
28、单选题：
对以下链表执行如下程序段，说明执行结果中，各个结点数据域分别是（）
void pur_LinkList(LinkList H)
{ PNode p, q, r ,s; p=H->link;
if(p==NULL ) return;
while (p->link)
{ s=p;
q=p->link;
while (q)
{ if (q->info==p->info)
{ s->link=q->link; free(q); q=s->link;}
else {s=q;q=q->link;}
}
p=p->link;
}
}