华东理工大学 网 络 教 育 学 院

《离散数学（专）》阶段练习四

（第七章、第九章）

一、判断题（对的在括弧中打个“√”，错的在括弧中打个“”）

1、任意一棵树都至少拥有三个1度点. （ ）

2、任一连通图都至少有一棵生成树，且生成树可以不唯一. （ ）

3、任意一棵二叉树的树叶可对应一个前缀码. （ ）

4、所谓叶结点的层数，就是叶结点到根结点的通路长度. （ ）

5、对集合，定义在其上的运算是封闭的. （ ）

6、半群就是运算满足封闭性且存在幺元的代数系统. （ ）

7、独异点一定是半群. （ ）

8、群中的每个元素都有逆元，但对应的逆元不唯一. （ ）

9、群与其任一子群具有相同的幺元. （ ）

10、交换群就是对运算满足交换律且每个元素都有逆元的独异点. （ ）

11、记集合的幂集为，则代数系统构成交换群.（ ）

12、交换群必定是循环群. （ ）

13、循环群中的生成元一定是唯一的. （ ）

14、群中无零元. （ ）

15、设G为群，那么成立：对a, b, cG，若ab=ac，则b=c. （ ）

16、已知群有两个子群，，那么和中，是群子群的只有. （ ）

二、一棵树有个2度点，个3度点，……，个度点，其余均为1度点，试问：这棵树有多少个1度点？

三、选择题

1、关于树，下列选项中唯一错误的是（ ）.

（A）恰有一个结点入度为0的有向树，叫做根树

（B）根树中，除了叶结点以外的点，都可以叫做分支点

（C）所谓3叉正则树，就是存在一个分支点并且该分支点恰有3个儿子的的根树.

（D）所谓树高，即根树中离根结点最远的叶结点所在的层数.

2、下列四个关于树的定义的选项中，唯一一个不正确的是（ ）.

（A）树是连通的无圈图

（B）树是连通且边数比点数多1的图

（C）树是无圈且边数比点数少1的图

（D）树是每一条边都是割边的连通图.

3、下面的各个符号串组成的集合中，不是前缀码的是（ ）.

（A）; （B）;

（C）; （D）.

4、对代数系统，下列四个论述中正确的只有（ ）.

A. 若存在零元，则零元是唯一的

B. 若存在左幺元，则左幺元必是唯一的

C. 若同时存在左、右幺元，则左、右幺元必相等

D. 若一个元素存在左逆元，则它一定也存在右逆元

5、群是除了不必满足下列（ ）这一特征但却必须满足其余特征的代数系统.

A. 可交换性 B. 可结合性 C. 存在幺元

D. 封闭性 E. 中每个元素都有逆元

6、设和都是群的子群，则下列选项中一定还是群的子群的只有（ ）.

A. B.

C. D.

7、交换群是只须同时满足（ ）等特征的独异点.

A. 存在生成元 B. 存在零元

C. 存在幺元 D. 可交换性且中每个元素都有逆元

8、下列关于叉树的描述正确的是（ ）.

A. 除了树叶以外，所有其它点的出度必须都大于等于的根树

B. 所有点的出度都小于的根树

C. 所有点的出度都小于等于，但必须能取到至少一次的根树

D. 除了树叶以外，所有其它点的出度都必须等于的根树

四、填空题

对于实数集合，下表所列的二元运算是否具有左边一列中的那些性质，请在相应的位置上添上“是”或“否”.

五、设是一个代数系统，是实数集合上的一个二元运算，它使得对于中的任意元素、，都有

其中的运算“”、“”即为实数的加法、乘法.

试证明：是幺元，且独异点.

六、设是一个半群，而且对于中的元素和，如果，则有，试证明：

1、对于中任一个元素，必有；

2、对于中任一个元素和，必有.

七、设和都是群的子群，试证明也是的子群.

八、设是个独异点，并且对于中的每一个元素都有，其中是幺元，证明是一个阿贝尔群.

九、在实数集合上定义如下二元运算：

x *

其中“”右边的运算依次为实数的乘法、减法和加法运算.

（1）、二元运算“*”满足哪些性质（在封闭性、交换性以及结合性中讨论）？并给出理由.

（2）、代数系统*中是否有幂等元（即满足的元素）？是否有幺元e ？若有，请求出e.

（3）每个元素是否都有逆元？若有，请求出相应元素.

十、1、给定权，试以它们构造一棵最优二叉树.

2、对给定权值11，5，13，4，2，1，8，6，3，9，7.请画出一棵最优4叉树.

《离散数学（专）》阶段练习四

（第七章、第九章）答案

一、判断题（对的在括弧中打个“√”，错的在括弧中打个“”）

二、 解：设树有个1度点，是的边数，于是有

解之即得

三、选择题

四、填空题

解：

五、证明：（1），由即知，是幺元.

（2），显然，即封闭性成立；

又，有

显然上两式相等，即满足可结合性，综合得是幺元，且独异点.

六、证明：1、因为，所以由题设即知有.

证明：2、由，即知

其中利用了题1的结果：，有.

七、证明：，因为和都是子群，所以，由于运算在中的封闭性，所以有，由非空子集成为子群的充分条件即得也是的子群.

八、证明：由，都有成立，及是幺元，即知，亦即中每个元素的逆元都是其自身。故已经是个群了.

又，由封闭性显然有，且由前段结论，又有，，进而有

即在中满足交换性.

综合即得是一个阿贝尔群.

九、

（1）、解：满足封闭性、交换性、结合性. 理由略.

（2）、

（3）

十、1、解：构造过程为从左下到右上.

2、解：

（1）从小到达将权排序如右：1，2，3，4，5，6，7，8，9，11，13.

（2）计算：由于，故取余数1加1等于2个最小的权值“1”和“2”，放在最左下角作为兄弟，……，最后作图如下：

华东理工大学网络教育学院