2020 数据结构(昆明学院) 最新满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2020-03-06到2020-07-06
本篇答案更新状态:已完结

第8周：树和二叉树（上）（时长：57分37秒） 第8周测验

1、 问题:树最适合用来表示（ ）。
选项：
A:有序数据元素
B:无序数据元素
C:元素之间具有层次关系的数据
D:元素之间无联系的数据
答案: 【元素之间具有层次关系的数据】

2、 问题:现有一“遗传”关系，设x是y的父亲，则x可以把他的属性遗传给y。表示该遗传关系最适合的数据结构为（ ）。
选项：
A:数组
B:树
C:图
D:线性表
答案: 【树】

3、 问题:一棵节点个数为n、高度为h的m（m≥3）次树中，其分支数是（ ）。
选项：
A:nh
B:n+h
C:n-1
D:h-1
答案: 【n-1】

4、 问题:若一棵3次树中有2个度为3的节点，1个度为2的节点，2个度为1的节点，该树一共有（ ）个节点。
选项：
A:5
B:8
C:10
D:11
答案: 【11】

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

6、 问题:有一棵三次树，其中n3=2，n2=1，n0=6，则该树的节点个数为（ ）。
选项：
A:9
B:10
C:12
D:大于等于9的任意整数
答案: 【大于等于9的任意整数】

7、 问题:假设每个节点值为单个字符，而一棵树的后根遍历序列为ABCDEFGHIJ，则其根节点值是（ ）。
选项：
A:A
B:B
C:J
D:以上都不对
答案: 【J】

8、 问题:一棵度为5、节点个数为n的树采用孩子链存储结构时，其中空指针域的个数是（ ）。
选项：
A:5n
B:4n+1
C:4n
D:4n-1
答案: 【4n+1】

9、 问题:有一棵三次树，其中n3=2，n2=2，n1=1，该树采用孩子兄弟链存储结构时，则总的指针域数为（ ）。
选项：
A:10
B:16
C:24
D:36
答案: 【24】

10、 问题:以下关于二叉树的说法中正确的是（ ）
选项：
A:二叉树就是度为2的树
B:二叉树中不存在度大于2的节点
C:二叉树就是度为2有序树
D:二叉树中每个节点的度都为2
答案: 【二叉树中不存在度大于2的节点】

11、 问题:按照二叉树的定义，具有3个节点的二叉树有（ ）种。
选项：
A:3
B:4
C:5
D:6
答案: 【5】

12、 问题:一棵完全二叉树中有1000个节点，其中度为1的节点个数是（ ）。
选项：
A:0
B:1
C:2
D:不确定
答案: 【1】

13、 问题:一棵满二叉树有m个叶子节点和n个节点，其高度为h，则有（ ）。
选项：
A:n=h+m
B:h+m=2n
C:m=h-1
D:
答案: 【】

14、 问题:设森林F中有4棵树，第1、2、3、4棵树的节点个数分别为a、b、c、d，将森林F转换为二叉树B，则B中根节点的左子树上的节点个数是（ ）。
选项：
A:a-1
B:a
C:a+b+c
D:b+c+d
答案: 【a-1】

15、 问题:一棵完全二叉树中有501个叶子节点，则至少有（ ）个节点。
选项：
A:501
B:502
C:1001
D:1002
答案: 【1001】

【作业】第8周：树和二叉树（上）（时长：57分37秒） 第8周作业

1、 问题:若一棵度为4的树中度为1、2、3、4的节点个数分别为4、3、2、2，则该树的总节点个数是多少？
评分规则: 【 参考答案：节点总数n=n0+n1+n2+n3+n4，又由于除根节点外，每个节点都对应一个分支，所以总的分支数等于n-1。而度为i（0≤i≤4）的节点的分支数为i，所以有：总分支数=n-1=0×n0+1×n1+2×n2+3×n3+4×n4。综合两式得：n0=n2+2n3+3n4+1=3+2×2+3×2=14，则n=n0+n1+n2+n3+n4=14+4+3+2+2=25，所以该树的总节点个数是25。
】

2、 问题:对于度为m的树T，其高度为h，则最少的节点个数和最多的节点个数分别是多少？
评分规则: 【 参考答案：第i层最多有个节点，所以最多节点个数=最少节点的情况是：某一层有m个节点，其他每层只有一个节点，此时节点个数=m+(h-1)=m+h-1。
】

3、 问题:对于含有n个节点的m次树，采用孩子链存储结构时，其中空指针域的个数有多少？
评分规则: 【 参考答案：该m次树中有n个节点，采用孩子链存储结构时，每个节点有m个指针，总指针域个数=m×n。又由于分支数=n-1，而每个分支是由一个非空指针域引出的，所以总的非空指针域个数=n-1，因此，空指针域的个数=总指针域个数-空指针域的个数=m×n-(n-1)=n(m-1)+1。
】

4、 问题:任意一个有n个节点的二叉树，已知它有m个叶子节点，试证明有(n-2m+1)个度数为1的节点。
评分规则: 【 参考答案：证明：设n1为二叉树中度为1的节点数，n2为度2的节点数，则总的节点数为：n=n1+n2+m根据二叉树的性质1可知n0=n2+1，即n2=n0-1=m-1，所以有n=n1+n2+m=n1+2m-1，则n1=n-2m+1。
】

5、 问题:为什么说一棵非空完全二叉树，一旦节点个数n确定了，其树形也就确定了。
评分规则: 【 参考答案：按层序编号时，完全二叉树的节点编号为1～n，如果已知各类节点个数，该完全二叉树的形态一定是确定的。若n已知，则可以根据其奇偶性确定n1：当n为偶数，n1=1，当n为奇数，n1=0，而n0=n2+1，n=n0+n1+n2=2n0-1+n1，n0=(n-n1+1)/2，从而n0和n2也确定了，所以这样的完全二叉树的形态就确定了。
】

6、 问题:已知一棵完全二叉树的第6层（设根为第1层）有8个叶子节点，则该完全二叉树的节点个数最多是多少？
评分规则: 【 参考答案：完全二叉树的叶子节点只能在最下两层，对于本题，节点最多的情况是第6层为倒数第二层，即1～6层构成一个满二叉树，其节点总数为-1=63。其中第6层有=32个节点，含8个叶子节点，则另外有32-8=24个非叶子节点，它们中每个节点有两个孩子节点（均为第7层的叶子节点），计48个叶子节点。这样最多的节点个数=63+48=111。
】

7、 问题:假设非空二叉树采用顺序存储结构，每个节点值为单个字符。设计一个算法求编号为i的节点的层次。
评分规则: 【 参考答案：int log2(int x) //求以2为底的x的对数{ int i=0; while (x!=1) { i++; x=x/2; } return i;}int Level(SqBTree t，int n，int i) //输出编号为i的节点的层次{ if (i<1 || i>n) return 0; else return log2(i)+1;}
】

8、 问题:假设非空二叉树采用顺序存储结构，每个节点值为单个字符。设计一个算法输出编号为i的节点的所有祖先节点值。
评分规则: 【 参考答案：void Ancestor(SqBTree t，int n，int i) //输出编号为i的节点的所有祖先节点值{ int j; if (i<=1 || i>n) return; else { j=i/2; while (j!=0) { printf(“%c “，t[j]); j=j/2; } } printf(“”);}
】

第9周：树和二叉树（下）（时长：57分24秒） 第9周测验

1、 问题:一颗二叉树的括号表示为“1(2(4，5(6，7))，3)”）。设N代表二叉树的根，L代表根节点的左子树，R代表根节点的右子树。若遍历后的节点序列为3，1，7，5，6，2，4，则其遍历方式是（ ）。
选项：
A:LRN
B:NRL
C:RLN
D:RNL
答案: 【RNL】

2、 问题:若二叉树（每个节点值为单个字符）的中序遍历序列是abcdef，且c为根节点，则（ ）。
选项：
A:节点c有两个孩子
B:二叉树有两个度为0的节点
C:二叉树的高度为5
D:以上都不对
答案: 【节点c有两个孩子】

3、 问题:若知道一棵二叉树的（ ），便可以唯一确定该二叉树。
选项：
A:先序序列
B:中序序列
C:中序和后序序列
D:先序和后序序列
答案: 【中序和后序序列 】

4、 问题:一棵二叉树的先序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）。
选项：