2021 数据结构(西南民族大学) 最新满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2021-08-30到2021-12-31
本篇答案更新状态:已完结

【作业】第二讲 线性结构（2：19：00）[何钦铭] 第一次 作业

1、 问题:2.11  设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有效性
评分规则: 【  顺序表结构  2分 算法函数接口  2分 按序插入 6分
】

2、 问题:2.19  已知线性表中的元素以值递增有序，并以单链表作存储结构。试写一高效的算法，删除有序表中所有其值大于 mink 且小于maxk的数据元素。
评分规则: 【  单链表结构  2分
 算法函数接口  1分
 删除过程  7分
】

3、 问题:2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,……,an) 逆置为（an,an-1,……,a1)。
评分规则: 【  顺序表结构  2分 算法函数接口  2分 逆置过程     2分
】

4、 问题:2.22 试写一算法，对单链表进行就地逆置。
评分规则: 【  单链表结构  2分 算法函数接口  1分 逆置过程     7分
】

【作业】第二讲 线性结构（2：19：00）[何钦铭] 第2次 作业

1、 问题:
评分规则: 【 分步给分
】

2、 问题:3.28 假设以带头结点的循环链表表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
评分规则: 【 结构  3分初始化  5分入队      6分出队      6分
】

3、 问题:3.30 假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。
评分规则: 【 结构  3分队满条件   3分入队      7分出队      7分
】

4、 问题:3.31 假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和’abcba’是回文，‘abcde’和’abababb’则不是回文，试写一个算法判别读入的一个以“@”为结束符的字符序列是否是“回文”
评分规则: 【 分步给分
】

第五讲 树（下）（1：53：28）[何钦铭] 树与二叉树的测试

1、 问题:设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）
选项：
A:5
B:6
C:7
D:8
答案: 【7】

2、 问题:设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）
选项：
A:m-n
B:m-n-1
C:n+1
D:条件不足，无法确定
答案: 【m-n】

3、 问题:若一棵二叉树具有9个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
选项：
A:9
B:10
C:14
D:不确定
答案: 【10】

4、 问题:在一棵三元树中度为3的结点数为3个，度为2的结点数为2个，度为1的结点数为3个，则度为0的结点数为（ ）个
选项：
A:8
B:9
C:10
D:11
答案: 【9】

5、 问题:设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。
选项：
A:M1
B:M1+M2
C:M3
D:M2+M3
答案: 【M2+M3】

6、 问题:一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）
选项：
A:250
B:500
C:254
D:505
E:以上答案都不对
答案: 【以上答案都不对】

7、 问题:13. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )
选项：
A:不确定
B:2n
C:2n+1
D:2n-1
答案: 【2n+1】

8、 问题:一个具有1025个结点的二叉树的高h为（ ）
选项：
A:11
B:10
C:11至1025之间
D:10至1024之间
答案: 【11至1025之间】

9、 问题:一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有(    )结点
选项：
A:
B:
C:
D:
答案: 【】

10、 问题:高度为 k的二叉树最大的结点数为（    ）。
选项：
A:
B:
C:
D:
答案: 【】

11、 问题:利用孩子兄弟链表存储树，则根结点的右指针是（ ）。
选项：
A:指向最左孩子
B:指向最右孩子
C:空
D:非空
答案: 【空】

12、 问题:对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。
选项：
A:先序
B:中序
C:后序
D:从根开始按层次遍历
答案: 【后序】

13、 问题:树的后根遍历序列等同于该树对应的二叉树的( ) 。
选项：
A:先序序列
B:中序序列
C:后序序列
D:层次遍历序列
答案: 【中序序列】

14、 问题:已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。
选项：
A:CBEFDA
B:FEDCBA
C:CBEDFA
D:不定
答案: 【CBEFDA】

15、 问题:一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）
选项：
A:所有的结点均无左孩子
B:所有的结点均无右孩子
C:只有一个结点
D:是任意一棵二叉树
答案: 【只有一个结点】

16、 问题:引入二叉线索树的目的是（ ）
选项：
A:加快查找结点的前驱或后继的速度
B:为了能在二叉树中方便的进行插入与删除
C:为了能方便的找到双亲
D:使二叉树的遍历结果唯一
答案: 【加快查找结点的前驱或后继的速度】

17、 问题:下面几个符号串编码集合中，不是前缀编码的是（ ）。
选项：
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}】

18、 问题:1． 不含任何结点的空树 （        ）。
选项：
A:是一棵树
B:是一棵二叉树;
C:是一棵树也是一棵二叉树
D:既不是树也不是二叉树
答案: 【是一棵树也是一棵二叉树】