大学MOOC 数据结构(安庆师范大学)1458378161 最新慕课完整章节测试答案
第一章 绪论
随堂测验题
1、单选题：
1.算法的时间复杂度取决于（ ）
选项：
A: 问题的规模
B: 待处理数据的初态
C: C. A和B
D: A或B
答案: 【 问题的规模】
2、单选题：
2.一个算法应该是（ ）。
选项：
A: 程序
B: 问题求解步骤的描述
C: 要满足五个基本特性
D: A和C
答案: 【 问题求解步骤的描述】
3、单选题：
3.下面关于算法说法错误的是（ ）
选项：
A: 算法最终必须由计算机程序实现
B: 为解决某问题的算法同为该问题编写的程序含义是相同的
C: 算法的可行性是指指令不能有二义性
D: 以上几个都是错误的
答案: 【 以上几个都是错误的】
4、单选题：
4.下面说法错误的是（ ）
选项：
A: 算法原地工作的含义是指不需要任何额外的辅助空间
B: 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
C: 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
D: 同一个算法，实现语言的级别越高，执行效率就越低
答案: 【 算法原地工作的含义是指不需要任何额外的辅助空间】
第二章 线性结构
随堂测验
1、单选题：
循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。
选项：
A: (rear-front+m)%m
B: rear-front+1
C: rear-front-1
D: rear-front
答案: 【 (rear-front+m)%m 】
2、单选题：
循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
选项：
A: rear=rear+1
B: rear=(rear+1) mod (m-1)
C: rear=(rear+1) mod m
D: rear=(rear+1)mod(m+1)
答案: 【 rear=(rear+1)mod(m+1)】
3、单选题：
若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )
选项：
A: 1和 5
B: 2和4
C: 4和2
D: 5和1
答案: 【 2和4】
4、判断题：
循环队列通常用指针来实现队列的头尾相接。（ ）
选项：
A: 正确
B: 错误
答案: 【 正确】
5、判断题：
循环队列也存在空间溢出问题。（ ）
选项：
A: 正确
B: 错误
答案: 【 正确】
第三章 树和二叉树
哈夫曼树与哈夫曼编码
1、单选题：
下述编码中哪一个不是前缀码（ ）。
选项：
A: （00，01，10，11）
B: （0，1，00，11）
C: （0，10，110，111）
D: （1，01，000，001）
答案: 【 （0，1，00，11）】
2、单选题：
下面几个符号串编码集合中，不是前缀编码的是（ ）。
选项：
A: {0,10,110,1111}
B: {11,10,001,101,0001}
C: {00,010,0110,1000}
D: {b,c,aa,ac,aba,abb,abc}
答案: 【 {11,10,001,101,0001}】
3、单选题：
下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字递增有序（）。
选项：
A: 二叉排序树
B: 哈夫曼树
C: AVL树
D: 堆
答案: 【 哈夫曼树 】
4、判断题：
霍夫曼树的结点个数不能是偶数。
选项：
A: 正确
B: 错误
答案: 【 正确】
5、判断题：
哈夫曼树无左右子树之分。
选项：
A: 正确
B: 错误
答案: 【 错误】
6、判断题：
哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
选项：
A: 正确
B: 错误
答案: 【 正确】
7、填空题：
有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为___
答案: 【 80】
8、填空题：
设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有______个结点。
答案: 【 2*n0-1】
树和森林
1、单选题：
设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。
选项：
A: n-1
B: n
C: n+1
D: n+2
答案: 【 n+1 】
2、判断题：
二叉树是一般树的特殊情形。
选项：
A: 正确
B: 错误
答案: 【 错误】
3、判断题：
树与二叉树是两种不同的树型结构。
选项：
A: 正确
B: 错误
答案: 【 正确】
4、判断题：
度为二的树就是二叉树。
选项：
A: 正确
B: 错误
答案: 【 错误】
5、填空题：
一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为______。
答案: 【 21】
6、填空题：
先根遍历树正好等同于按___遍历对应的二叉树
答案: 【 先序】
7、填空题：
后根遍历树正好等同于按___遍历对应的二叉树。
答案: 【 中序】
随堂测验
1、单选题：
对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。
选项：
A: 先序
B: 中序
C: 后序
D: 从根开始按层次遍历
答案: 【 后序 】
2、单选题：
二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是：
选项：
A: E
B: F
C: G
D: H
答案: 【 G】
3、单选题：
已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。
选项：
A: acbed
B: decab
C: deabc
D: cedba
答案: 【 cedba 】