MOOC 数据结构与算法(大连理工大学)1205981804 最新慕课完整章节测试答案
1 绪论
绪论单元测验
1、单选题：
在链接存储结构中，要求 。
选项：
A: 每个结点占用一片连续的存储区域
B: 所有结点占用一片连续的存储区域
C: 结点的最后一个域是指针类型
D: 每个结点有多少个后继就设多少个指针
答案: 【 每个结点占用一片连续的存储区域】
2、单选题：
对于数据结构的描述，下列说法中不正确的是 。
选项：
A: 相同的逻辑结构对应的存储结构也必须相同
B: 数据结构由逻辑结构、存储结构和基本操作三个方面构成
C: 数据结构基本操作的实现与存储结构有关
D: 数据的存储结构是数据的逻辑结构的机内实现
答案: 【 相同的逻辑结构对应的存储结构也必须相同】
3、单选题：
以下关于链接存储结构的叙述中， 是不正确的。
选项：
A: 结点除数据信息外还包括指针域，因此存储密度小于顺序存储结构
B: 逻辑上相邻的结点在物理上不一定相邻
C: 可以通过计算得到第i个节点的存储地址
D: 插入和删除操作方便，不必移动结点
答案: 【 可以通过计算得到第i个节点的存储地址】
4、单选题：
可以用 、数据关系和基本操作定义一个完整的抽象数据类型。
选项：
A: 数据元素
B: 数据对象
C: 原子类型
D: 存储结构
答案: 【 数据元素】
5、单选题：
算法指得是 。
选项：
A: 对特定问题求解步骤的一种描述，是指令的有限序列
B: 计算机程序
C: 解决问题的计算方法
D: 数据处理
答案: 【 对特定问题求解步骤的一种描述，是指令的有限序列】
6、单选题：
下面 不是算法所必须具备的特性。
选项：
A: 有穷性
B: 确切性
C: 高效性
D: 可行性
答案: 【 高效性】
7、单选题：
某算法的时间复杂度是O(n^2)，表明该算法 。
选项：
A: 问题规模是n^2
B: 执行时间等于n^2
C: 执行时间与n^2成正比
D: 问题规模与n^2成正比
答案: 【 执行时间与n^2成正比】
8、单选题：
设某算法完成对n个元素进行处理，所需的时间是T(n)=100nlgn+200n+500，则该算法的时间复杂度是 。
选项：
A: O(1)
B: O(n)
C: O(nlgn)
D: O(nlgn)+O(n)
答案: 【 O(nlgn)】
9、单选题：
算法的时间复杂度属于一种 。
选项：
A: 事前统计的方法
B: 事前分析估算的方法
C: 事后统计的方法
D: 事后分析估算的方法
答案: 【 事前分析估算的方法】
随堂测验1
1、单选题：
在链接存储结构中，要求 。
选项：
A: 每个结点占用一片连续的存储区域
B: 所有结点占用一片连续的存储区域
C: 结点的最后一个域是指针类型
D: 每个结点有多少个后继就设多少个指针
答案: 【 每个结点占用一片连续的存储区域】
2、单选题：
对于数据结构的描述，下列说法中不正确的是 。
选项：
A: 相同的逻辑结构对应的存储结构也必须相同
B: 数据结构由逻辑结构、存储结构和基本操作三个方面构成
C: 数据结构基本操作的实现与存储结构有关
D: 数据的存储结构是数据的逻辑结构的机内实现
答案: 【 相同的逻辑结构对应的存储结构也必须相同】
3、单选题：
以下关于链接存储结构的叙述中， 是不正确的。
选项：
A: 结点除数据信息外还包括指针域，因此存储密度小于顺序存储结构
B: 逻辑上相邻的结点在物理上不一定相邻
C: 可以通过计算得到第i个节点的存储地址
D: 插入和删除操作方便，不必移动结点
答案: 【 可以通过计算得到第i个节点的存储地址】
4、单选题：
可以用 、数据关系和基本操作定义一个完整的抽象数据类型。
选项：
A: 数据元素
B: 数据对象
C: 原子类型
D: 存储结构
答案: 【 数据元素】
5、多选题：
顺序存储结构中数据元素之间的逻辑关系是由 表示的，链接存储结构中的数据元素之间的逻辑关系式由 表示的。
选项：
A: 线性结构
B: 非线性结构
C: 存储位置
D: 指针
答案: 【 存储位置;
指针】
随堂测验2
1、单选题：
算法指得是 。
选项：
A: 对特定问题求解步骤的一种描述，是指令的有限序列。
B: 计算机程序
C: 解决问题的计算方法
D: 数据处理
答案: 【 对特定问题求解步骤的一种描述，是指令的有限序列。】
2、单选题：
下面 不是算法所必须具备的特性。
选项：
A: 有穷性
B: 确切性
C: 高效性
D: 可行性
答案: 【 高效性】
3、单选题：
某算法的时间复杂度是O(n^2)，表明该算法 。
选项：
A: 问题规模是n^2
B: 执行时间等于n^2
C: 执行时间与n^2成正比
D: 问题规模与n^2成正比
答案: 【 执行时间与n^2成正比】
4、单选题：
设某算法完成对n个元素进行处理，所需的时间是T(n)=100nlgn+200n+500，则该算法的时间复杂度是 。
选项：
A: O(1)
B: O(n)
C: O(nlgn)
D: O(nlgn)+O(n)
答案: 【 O(nlgn)】
5、单选题：
算法的时间复杂度属于一种 。
选项：
A: 事前统计的方法
B: 事前分析估算的方法
C: 事后统计的方法
D: 事后分析估算的方法
答案: 【 事前分析估算的方法】
2 线性表
线性表单元测验
1、单选题：
将两个各有n个元素的有序顺序表归并成一个有序顺序表，其最少的比较次数是 。
选项：
A: n
B: 2n-1
C: 2n
D: n-1
答案: 【 n】
2、单选题：
在长度为n的线性表中查找值为x的数据元素的时间复杂度为 。
选项：
A: O(0)
B: O(1)
C: O(n)
D: O(n^2)
答案: 【 O(n)】
3、单选题：
线性表的顺序存储结构是一种 的存储结构。
选项：
A: 随机存取
B: 顺序存取
C: 索引存取
D: 散列存取
答案: 【 随机存取】
4、单选题：
设线性表中有2n个元素，以下操作中， 在单链表上实现要比在顺序表上实现效率更高。
选项：
A: 删除指定的元素
B: 在最后一个元素的后面插入一个新元素
C: 顺序输出前k个元素
D: 交换第i个元素和第2n-i-1个元素的值（i=0,1,…,n-1）
答案: 【 删除指定的元素】
5、单选题：
如果最常用的操作是取第i个节点及其前驱，则采用 存储方式最节省时间。
选项：
A: 单链表
B: 双链表
C: 单循环链表
D: 顺序表
答案: 【 顺序表】
6、单选题：
与单链表相比，双链表的优点之一是 。
选项：
A: 插入、删除操作更简单
B: 可以进行随机访问
C: 可以省略表头指针或表尾指针
D: 访问前后相邻结点更灵活
答案: 【 访问前后相邻结点更灵活】
7、单选题：
带头结点的单链表L为空的判定条件是 。
选项：
A: L==NULL
B: L->next==NULL
C: L->next==L
D: L!=NULL
答案: 【 L->next==NULL】
8、单选题：
在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行 操作。
选项：
A: s->next=p->next ; p->next=s;
B: q->next=s ; s->next=p;
C: p->next=s->next ; s->next=p;
D: p->next=s ; s->next=q;
答案: 【 q->next=s ; s->next=p;】
9、单选题：
设指针rear指向带头结点的循环单链表的尾结点，若要删除链表的第一个元素结点，正确的操作是 。
选项：
A: s=rear ; rear=rear->next;
B: rear=rear->next;
C: rear=rear->next->next;
D: s=rear->next->next ; rear->next->next=s->next;
答案: 【 s=rear->next->next ; rear->next->next=s->next;】
10、单选题：
经过以下栈运算后，x的值是 。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s.x);
选项：
A: a
B: b
C: 0
D: 1
答案: 【 a】
11、单选题：
一个栈的进栈a,b,c,d,e则栈的不可能的输出序列是 。
选项：
A: edcba
B: decba
C: dceab
D: abcde
答案: 【 dceab 】
12、单选题：
已知一个栈的进栈序列是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】
13、单选题：
判定一个顺序栈st为（元素个数最多为MaxSize）空的条件为 。
选项：
A: st.top==-1
B: st.top!=-1
C: st.top!=MaxSize
D: st.top==MaxSize
答案: 【 st.top==-1】
14、单选题：
链栈与顺序栈相比有一个明显的优点，即 。
选项：
A: 插入操作更方便
B: 通常不会出现栈满的情况
C: 不会出现栈空的情况
D: 删除操作更加方便
答案: 【 通常不会出现栈满的情况】
15、单选题：
设环形队列中数组的下标是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】
16、单选题：
对于链队，在进行删除操作时， 。
选项：
A: 仅修改头指针
B: 仅修改尾指针
C: 头、尾指针都要修改
D: 头、尾指针可能都要修改
答案: 【 头、尾指针可能都要修改】
17、单选题：
对于含有n个字符的链串s，查找元素值为x的算法时间复杂度为 。
选项：
A: O(1)
B: O(n)
C: O(n^2)
D: O(lgn)
答案: 【 O(n)】
18、单选题：
已知t=”abcaabbcabcaabdab”，该模式串的特征数组值为 。
选项：
A: -1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1
B: 0,1,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1
C: -1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,7,1
D: -1,0,0,0,1,1,2,3,0,1,2,3,4,5,6,0,1
答案: 【 -1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1】
随堂测验1
1、单选题：
将两个各有n个元素的有序顺序表归并成一个有序顺序表，其最少的比较次数是 。
选项：
A: n
B: 2n-1
C: 2n
D: n-1
答案: 【 n】
2、单选题：
在长度为n的线性表中查找值为x的数据元素的时间复杂度为 。
选项：
A: O(0)
B: O(1)
C: O(n)
D: O(n^2)
答案: 【 O(n)】
3、单选题：
线性表的顺序存储结构是一种 的存储结构。
选项：
A: 随机存取
B: 顺序存取
C: 索引存取
D: 散列存取
答案: 【 随机存取】
4、多选题：
在一个长度为n的顺序表的第i(1≤i≤n+1)个元素之前插入一个元素，需向后移动 个元素，删除第i(1≤i≤n)个元素时，需向前移动 个元素。
选项：
A: n-i
B: n-i+1
C: n-i
D: n-i+1
答案: 【 n-i+1;
n-i】
随堂测验2
1、单选题：
设线性表中有2n个元素，以下操作中， 在单链表上实现要比在顺序表上实现效率更高。
选项：
A: 删除指定的元素
B: 在最后一个元素的后面插入一个新元素
C: 顺序输出前k个元素
D: 交换第i个元素和第2n-i-1个元素的值（i=0,1,…,n-1）
答案: 【 删除指定的元素】
2、单选题：
如果最常用的操作是取第i个节点及其前驱，则采用 存储方式最节省时间。
选项：
A: 单链表
B: 双链表
C: 单循环链表
D: 顺序表
答案: 【 顺序表】
3、单选题：
与单链表相比，双链表的优点之一是 。
选项：
A: 插入、删除操作更简单
B: 可以进行随机访问
C: 可以省略表头指针或表尾指针
D: 访问前后相邻结点更灵活
答案: 【 访问前后相邻结点更灵活】
4、单选题：
带头结点的单链表L为空的判定条件是 。
选项：
A: L==NULL
B: L->next==NULL
C: L->next==L
D: L!=NULL
答案: 【 L->next==NULL】
5、单选题：
在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行 操作。
选项：
A: s->next=p->next ; p->next=s;
B: q->next=s ; s->next=p;
C: p->next=s->next ; s->next=p;
D: p->next=s ; s->next=q;
答案: 【 q->next=s ; s->next=p;】
6、单选题：
设指针rear指向带头结点的循环单链表的尾结点，若要删除链表的第一个元素结点，正确的操作是 。
选项：
A: s=rear ; rear=rear->next;
B: rear=rear->next;
C: rear=rear->next->next;
D: s=rear->next->next ; rear->next->next=s->next;
答案: 【 s=rear->next->next ; rear->next->next=s->next;】
随堂测验3
1、单选题：
经过以下栈运算后，x的值是 。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s.x);
选项：
A: a
B: b
C: 0
D: 1
答案: 【 a】
2、单选题：
一个栈的进栈a,b,c,d,e则栈的不可能的输出序列是 。
选项：
A: edcba
B: decba
C: dceab
D: abcde
答案: 【 dceab】
3、单选题：
已知一个栈的进栈序列是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】
4、单选题：
判定一个顺序栈st为（元素个数最多为MaxSize）空的条件为 。
选项：
A: st.top==-1
B: st.top!=-1
C: st.top!=MaxSize
D: st.top==MaxSize
答案: 【 st.top==-1 】
5、单选题：
链栈与顺序栈相比有一个明显的优点，即 。
选项：
A: 插入操作更方便
B: 通常不会出现栈满的情况
C: 不会出现栈空的情况
D: 删除操作更加方便
答案: 【 通常不会出现栈满的情况】
随堂测验4
1、单选题：
设环形队列中数组的下标是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】
2、单选题：
对于链队，在进行删除操作时，&nbs