大学MOOC 数据结构（朱江）(湘潭大学)1449553164 最新慕课完整章节测试答案

小测验算法复杂度

1、单选题：
​下列函数中，哪个函数具有最快的增长速度：‏
选项：
A:
B:
C:
D:
答案: 【 】

2、单选题：
​下面一段代码的时间复杂度是？if ( A > B ) {
    for ( i=0; i<N; i++ )
        for ( j=N*N; j>i; j-- )
            A += B;
}
else {
    for ( i=0; i<N*2; i++ )
        for ( j=N*2; j>i; j-- )
            A += B;
}​
选项：
A:
B:
C:
D:
答案: 【 】

第一章概论

1、单选题：
‎下列函数中，哪两个函数具有相同的增长速度：​
选项：
A: 2N和NN
B: N和2/N
C: N2logN和NlogN2
D: NlogN2和NlogN
答案: 【 NlogN2和NlogN】

2、单选题：
‌下列函数中，哪个函数具有最慢的增长速度：‌
选项：
A: N1.5
B: NlogN2
C: N2logN
D: N(logN)2
答案: 【 NlogN2】

3、单选题：
‍下列哪个函数是O(N)的？‍
选项：
A: (logN)2
B: (NlogN)/1000
C: N(logN)2
D: N2/1000
答案: 【 (logN)2】

4、单选题：
‏下列函数中，哪个函数具有最快的增长速度？‎
选项：
A: N2logN
B: N(logN)4
C: N3
D: NlogN2
答案: 【 N3】

5、判断题：

‎是$O(N)。$

‍选项：
A: 正确
B: 错误
答案: 【 错误】

6、判断题：
‏2N和NN具有相同的增长速度。​
选项：
A: 正确
B: 错误
答案: 【 错误】

7、判断题：
‌NlogN2和NlogN具有相同的增长速度。​
选项：
A: 正确
B: 错误
答案: 【 正确】

8、判断题：
‎(logN)2是O(N)的。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

9、判断题：
‎斐波那契数列FN的定义为：F0=0, F1=1, FN=FN−1+FN−2, N=2, 3, …。用递归函数计算FN的时间复杂度是O(N!)。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

10、判断题：
‎斐波那契数列FN的定义为：F0=0, F1=1, FN=FN−1+FN−2, N=2, 3, …。用递归函数计算FN的空间复杂度是O(N)。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

11、判断题：
‏算法分析的两个主要方面是时间复杂度和空间复杂度的分析。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

第二章线性结构

1、单选题：
​数组A[1..5,1..6]每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为：‏
选项：
A: 1120
B: 1125
C: 1140
D: 1145
答案: 【 1140】

2、单选题：
‍若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用哪种存储方式最节省时间？‌
选项：
A: 双链表
B: 单循环链表
C: 带头结点的双循环链表
D: 顺序表
答案: 【 顺序表】

3、单选题：
‍线性表若采用链式存储结构时，要求内存中可用存储单元的地址‏
选项：
A: 必须是连续的
B: 连续或不连续都可以
C: 部分地址必须是连续的
D: 一定是不连续的
答案: 【 连续或不连续都可以】

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

5、单选题：
‍将线性表La和Lb头尾连接，要求时间复杂度为O(1)，且占用辅助空间尽量小。应该使用哪种结构？‎
选项：
A: 单链表
B: 单循环链表
C: 带尾指针的单循环链表
D: 带头结点的双循环链表
答案: 【 带尾指针的单循环链表】

6、单选题：
‌带头结点的单链表h为空的判定条件是：‌
选项：
A: h == NULL;
B: h->next == NULL;
C: h->next == h;
D: h != NULL;
答案: 【 h->next == NULL;】

7、单选题：
‌设栈S和队列Q的初始状态均为空，元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b、d、c、f、e、a、g，则栈S的容量至少是：‎
选项：
A: 1
B: 2
C: 3
D: 4
答案: 【 3】

8、单选题：
‍设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是？​
选项：
A: 3 2 1 5 4
B: 5 1 2 3 4
C: 4 5 1 3 2
D: 4 3 1 2 5
答案: 【 3 2 1 5 4】

9、单选题：
‏若借助堆栈将中缀表达式a+b*c+(d*e+f)*g转换为后缀表达式，当读入f时，堆栈里的内容是什么（按堆栈自底向上顺序）？​
选项：
A: +(*+
B: +(+
C: ++(+
D: abcde
答案: 【 +(+】

10、单选题：
‎从栈顶指针为ST的链栈中删除一个结点且用X保存被删结点的值，则执行：‌
选项：
A: X= ST->data;
B: X= ST; ST = ST->next;
C: X= ST->data; ST = ST->next;
D: ST = ST->next; X= ST->data;
答案: 【 X= ST->data; ST = ST->next;】

11、单选题：
‍为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是？‎
选项：
A: 堆栈
B: 队列
C: 树
D: 图
答案: 【 队列】

12、单选题：
‍若已知一队列用单向链表表示，该单向链表的当前状态（含3个对象）是：1->2->3，其中x->y表示x的下一节点是y。此时，如果将对象4入队，然后队列头的对象出队，则单向链表的状态是：‏
选项：
A: 1->2->3
B: 2->3->4
C: 4->1->2
D: 答案不唯一
答案: 【 2->3->4】

13、单选题：
‌若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？‎
选项：
A: 2和0
B: 2和2
C: 2和4
D: 2和6
答案: 【 2和0】

14、单选题：
‍设栈S和队列Q的初始状态均为空，元素{1, 2, 3, 4, 5, 6, 7}依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是{2, 5, 6, 4, 7, 3, 1}，则栈S的容量至少是：‍
选项：
A: 1
B: 2
C: 3
D: 4
答案: 【 4】

15、判断题：
‌对于顺序存储的长度为N的线性表，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。​
选项：
A: 正确
B: 错误
答案: 【 正确】

16、判断题：
‎若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用顺序表存储最节省时间。‏
选项：
A: 正确
B: 错误
答案: 【 正确】

17、判断题：
‌在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

18、判断题：
‍将N个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是O(logN)。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

19、判断题：
‏通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

20、判断题：
‏若一个栈的输入序列为1，2，3，…，N，输出序列的第一个元素是i，则第j个输出元素是j−i−1。​
选项：
A: 正确
B: 错误
答案: 【 错误】

21、判断题：
‎所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

22、判断题：
‏在用数组表示的循环队列中，front值一定小于等于rear值。‎
选项：
A: 正确
B: 错误
答案: 【 错误】

第三章树-树&二叉树

1、单选题：
‎树最适合于用来表示‌
选项：
A: 有序数据元素
B: 无序数据元素
C: 元素之间无联系的数据
D: 元素之间具有分支层次关系的数据
答案: 【 元素之间具有分支层次关系的数据】

2、单选题：
‏一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）个。​
选项：
A: 15
B: 16
C: 17
D: 47
答案: 【 16】

3、单选题：
‎以二叉链表作为二叉树的存储结构，在具有 n 个结点的二叉链表中（n>0），空链域的个数为 __‌
选项：
A: n+1
B: n
C: n-1
D: 无法确定
答案: 【 n+1】

4、单选题：
‏有一个四叉树，度2的结点数为2，度3的结点数为3，度4的结点数为4。问该树的叶结点个数是多少？‌
选项：
A: 10
B: 12
C: 20
D: 21
答案: 【 21】

5、单选题：
​对于任意一棵高度为 5 且有 10 个结点的二叉树，若采用顺序存储结构保存，每个结点占 1 个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元的数量至少是：‌
选项：
A: 31
B: 16
C: 15
D: 10
答案: 【 31】

6、单选题：
‎二叉树的中序遍历也可以循环地完成。给定循环中堆栈的操作序列如下（其中push为入栈，pop为出栈）：‎‎‎‎push(1), push(2), push(3), pop(), push(4), pop(), pop(), push(5), pop(), pop(), push(6), pop()‎‎以下哪句是对的？‎
选项：
A: 6是根结点
B: 3和5是兄弟结点
C: 2是4的父结点
D: 以上全不对
答案: 【 3和5是兄弟结点】

7、单选题：
​二叉树中第5层（根的层号为1）上的结点个数最多为：‏
选项：
A: 8
B: 15
C: 16
D: 32
答案: 【 16】

8、单选题：
‏如果二叉树的后序遍历结果是FDEBGCA，中序遍历结果是FDBEACG，那么该二叉树的前序遍历结果是什么？‌
选项：
A: ABCDEFG
B: ABDF