下载文档原格式
第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）习题一、选择题1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。
表示该遗传关系最适合的数据结构为( )。
A.向量B.树 C图 D.二叉树2．树最合适用来表示( )。
A.有序数据元素B元素之间具有分支层次关系的数据C无序数据元素 D.元素之间无联系的数据3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。
A. la (2b (3d,3e),2c)B. a(b(D,e),c)C. a(b(d,e),c)D. a(b,d(e),c)4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。
A. 2h_lB.h C．2h-1 D. 2h5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。
A. 2iB. 2i-lC. 2i+lD. 2i+26.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为 ( )。
A.3B.4C.5D.67.深度为5的二叉树至多有( )个结点。
A. 31B. 32C. 16D. 108.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。
A. 15B. 16C. 17D. 479.题图6-1中，( )是完全二叉树，( )是满二叉树。
..专业知识编辑整理..10.在题图6-2所示的二叉树中：(1)A结点是A.叶结点B根结点但不是分支结点 C根结点也是分支结点 D.分支结点但不是根结点(2)J结点是A.叶结点B．根结点但不是分支结点 C根结点也是分支结点 D.分支结点但不是根结点(3)F结点的兄弟结点是A.EB.D C．空 D.I(4)F结点的双亲结点是A.AB.BC.CD.D(5)树的深度为A.1B.2C.3D.4(6)B结点的深度为A.1B.2C.3D.4(7)A结点所在的层是A.1B.2C.3D.4..专业知识编辑整理..11.在一棵具有35个结点的完全二叉树中，该树的深度为( )。
第六章 统计热力学基础内容提要：1、 系集最终构型：其中“n*”代表最可几分布的粒子数目2.玻耳兹曼关系式：玻耳兹曼分布定律：其中，令为粒子的配分函数。
玻耳兹曼分布定律描述了微观粒子能量分布中最可几的分布方式。
3、 系集的热力学性质：（1）热力学能U ：（2）焓H ：**ln ln ln !i n i m iig t t n ≈=∏总2,ln ()N VQU NkT T∂=∂iiiQ g e βε-=∑*i ii i i i i in g e g e N g e Q βεβεβε---==∑m ln ln S k t k t ==总（3）熵S ：（4）功函A ：（5）Gibbs 函数G ：（6）其他热力学函数：4、粒子配分函数的计算（1）粒子配分函数的析因子性质粒子的配分函数可写为：,ln ln ln()mN V S k t Q Q Nk NkT Nk N T=∂=++∂ (i)tvenrkTi ikTkTkTkTkTt r v e n trvent r v e nQ g eg eg eg eg eg eQ Q Q Q Q εεεεεε------===∑∑∑∑∑∑2,ln N VQ H U pV NkT NkTT ∂⎛⎫=+=+ ⎪∂⎝⎭lnQA NkT NkT N=--lnQ G NkT N=-()22ln ln ln ln V V U Q Q C Nk Nk T T T ∂∂∂⎛⎫==+ ⎪∂∂⎝⎭∂（2）热力学函数的加和性质1）能量2）熵3）其他5、 粒子配分函数的计算及对热力学函数的贡献（1）粒子总的平动配分函数平动对热力学函数的贡献：2222ln ()ln ln ln ()()()iVt v r V V V t r v Q U NkT TQ Q Q NkT NkT NkT T T T U U U ∂=∂∂∂∂⎡⎤⎡⎤⎡⎤=+++⎢⎥⎢⎥⎢⎥∂∂∂⎣⎦⎣⎦⎣⎦=+++t r v H H H H =+++t r v A A A A =+++t r v G G G G =+++3/222()t mkT Q V hπ=2ln 3()2i t V Q U NkT NkT T ∂==∂2ln 5()2i t V Q H NkT NkT NkT T ∂=+=∂t r v S S S S =+++（2）转动配分函数1）异核双原子分子或非对称的线形分子转动特征温度：高温区低温区中温区2) 同核双原子分子或对称的线形多原子分子配分函数的表达式为在相应的异核双原子分子的Q r 表达式中除以对称数σ。
第七章图论习题7.11.a)非简单图；（有自圈）b)非简单图；（有自圈）c)简单图。
3.证明：因为n个顶点的有向简单图中，每两个不同顶点之间最多有两条边，因此其边数最多。
为：)1(22-Cn=nn4. 利用定理7.1.3证明：因为任何图均有偶数个奇结点，而3度正则图的所有结点度数均为3，即均为偶结点。
所以，3度正则图必有偶数个奇结点。
5. 利用定理7.1.31'2'1 5 36'3'6 2 45'4'6.证明：假设六个人分别为：a, b, c, d, e, f。
则分两种情况讨论。
①若a认识的人大于等于3个，即b, c, d, e, f中至少有3个与a认识。
不妨设c, d, e与a 认识，则c, d, e必定互相不认识。
（否则，c, d, e中互相认识的两人与a就构成三个人互相都认识。
产生矛盾。
）②若a认识的人小于3个，即b, c, d, e, f中至少有3个与a不认识。
不妨设b, c, d与a均不认识。
则因为没有3个人彼此都认识，所以b, c, d中必有两个人互相不认识。
假设c, d互相不认识，则a, c, d三个人彼此都不认识。
8. a ) 图中有一个与两个度数为3的结点邻接的结点，其度数也为3。
而b ) 图中没有任何一个度数为3的结点与两个度数为3的结点邻接。
所以，a ) 与b ) 不同构。
9. b ) 图的中心结点其入度为0，而a ) 图中没有入度为0 的结点。
所以两图不同构。
10. n 阶简单无向图的结点度数不可能超过n-1，即取值范围为：{0, 1, 2, … , n -1}。
证明n （n>1）阶图中必有两个结点度数相等，抽屉原则应该可以使用，但n 个结点，n 种度数可能，抽屉原则似乎用不上。
但我们发现，若图中有孤立点，则所有结点的度数只可能从0到n-2中取值，即只有n-1种可能性。
于是分两种情况：① 若G 中无孤立点（度数为0的结点），则G 中n 个结点的度数只能从1到n-1中取值。
第1章通信网络概论及数学基础1.1通信网络有哪些基本要素组成？试举例列出五种常用的通信网络。
1.2常用的通信链路有哪些？其主要特征是什么？1.3试简述分组交换网的要点。
1.4什么叫做虚电路？它与传统电话交换网中的物理链路有何差异？1.5 A TM信元与分组有何差别？ATM网络是如何支持不同种类业务的？1.6分层的基本概念是什么？什么是对等层？1.7试述OSI七层模型和TCP/IP协议体系的区别和联系。
1.8一个典型的通信网络可由哪些物理子网构成？路由器在该网络中的作用是什么？1.9通信网络要研究的基本理论问题有哪些？1.10 设随机过程定义为：，其中Y是离散随机变量，且。
试求该过程在时的均值，和时的自相关函数值。
1.11 设随机过程是一个随机相位信号，即，式中A和w c为常量， 是一个均匀分布的随机变量，其概率密度函数为。
试求的均值函数和自相关函数。
并讨论其平稳性和各态历经性。
1.12 试求Poisson过程的均值函数，方差函数和相关函数。
1.13 设到达某商店的顾客组成强度为的Poisson流，每个顾客购买商品的概率为p，各顾客是否购买商品与其它顾客无关，分别用和表示购买商品顾客和未购买商品顾客的顾客流过程，请证明他们分别是强度为和的Poisson流。
1.14 设某办公室来访的顾客数组成Poisson流，平均每小时到访的顾客数为3人，求：（1）一上午（8到12点）没有顾客来访的概率；（2）下午（2点到6点）第一个顾客到达的时间分布。
图1-25习题1-16图1.15 设有三个黑球和三个白球，把这六个球任意分给甲乙两人，并把甲拥有的白球数定义为该过程的状态，则有四种状态0，1，2，3。
现每次从甲乙双方各取一球，然后相互交换。
经过n次交换后过程的状态记为，试问该过程是否是马氏链？如是，试计算其一步转移概率矩阵，并画出其状态转移图。
1.16分别利用Prim-Dijkstra算法和Kruskal算法求解图1-25中的最小重量生成树。
06-练习题解答1. 下列附表是使用无类别域间路由选择（CIDR）的路由选择表，地址字节是用十六进制表示的。
在C4.50.0.0/12中的“/12”表示开头有12个1的网络掩码，也就是FF.F0.0.0。
注意，最后三个登录项涵盖每一个地址，因此起到了缺省路由的作用。
试指出具有下列目标地址的IP分组将被投递到哪一个下站地？路由选择表(1) C4.5E.13.87解答：网络号C4.5E.10.0/20（下一站地是B）的第3字节可以用二进制表示成0001 0000。
目标地址C4.5E.13.87的第3字节可以用二进制表示成13=0001 0011，显然取20位掩码与网络号C4.5E.10.0/20（10=00010010）相匹配（最长匹配），所以具有该目标地址的IP分组将被投递到下站地B。
(2) C4.5E.22.09解答：网络号C4.50.0.0/12（下一站地是A）的第2字节可以用二进制表示成0101 0000。
目标地址C4.5E.22.09的第2字节可以用二进制表示成0101 1110，显然取12位掩码与网络号C4.50.0.0/12相匹配（最长匹配），所以具有该目标地址的IP分组将被投递到下站地A。
(3) C3.41.80.02解答：网络号80.0.0.0/1（下一站地是E）的第1字节可以用二进制表示成1000 0000。
目标地址C3.41.80.02的第1字节可以用二进制表示成1100 0011，显然取1位掩码与网络号80.0.0.0/1相匹配（唯一匹配），所以具有该目标地址的IP分组将被投递到下站地E。
(4) 5E.43.91.12解答：网络号40.0.0.0/2（下一站地是F）的第1字节可以用二进制表示成0100 0000。
目标地址5E.43.91.12的第1字节可以用二进制表示成0101 1110，显然取2位掩码与网络号40.0.0.0/2相匹配（最长匹配），所以具有该目标地址的IP分组将被投递到下站地F。
第六章图与网络分析习题及参考答案案习题六图与网络分析习题及参考答案.1 十名学生参加六门课程的考试。
由于选修内容不同，考试门数也不一样。
下表给出了每个学生应参加考试的课程（打⊙的）：学生考试课程 A B C D E F1 ⊙⊙⊙2 ⊙⊙3 ⊙⊙4⊙⊙⊙5⊙⊙⊙6 ⊙⊙7⊙⊙⊙8 ⊙⊙9 ⊙⊙⊙10⊙⊙⊙规定考试在三天内结束，每天上下午各安排一门。
学生希望每人每天最多考一门，又课程A必须安排在第一天上午考，课程F安排在最后一门，课程B只能安排在下午考，试列出一张满足各方面要求的考试日程表。
参考答案把同一个研究生参加的考试课程用边连接，得图如下。
由图看出，课程A只能同E排在一天，B同C排在一天，D同F在一天。
再据题意，考试日程表只能是下表：B E 上午下午第一天 A EA F 第二天 C B第三天 D FD C2 求下图的最小生成树和最大生成树：V6 3需参考答案将每小块稻田及水源地各用一个点表示，连接这些点的树图的边数即为至少要挖开的堤埂数。
（至少挖开11条）4. 请用标号法求下图所示的最短路问题，弧上数字为距离：参考答案路线为1－2－4－6，距离为9个单位5 用Dijkstra标号法求下图中始点到各顶点的最短路，弧上数字为距离：v3 3 v51 5 4v1 24v2 2 v4参考答案1－2，3，4，5最短路：3*,1*,5*,4*6最短路问题：某公司使用一种设备，此设备在一定年限内随着时间的推移逐渐损坏。
每年购买价格和不同年限的维修使用费如下表所示。
假定公司在第一年开始时必须购买一台此设备，请建立此问题的网络图，确定设备更新方案，使维修费和新设备购置费的总数最小。
说明解决思路和方法，不必求解。
年份 1 2 3 4 5价格20 21 23 24 26使用年限0－1 1－2 2－3 3－4 4－5费用8 13 19 23 30参考答案弧（i，j）的费用或“长度”等于j－i年里的设备维修费加上第i 年购买的新设备的价格。
第六章部分习题答案第七题原题：在这道习题中，我们探讨CRC的某些性质。
对于在6.2.3节中给出的⽣成多项式G（=1001），回答下列问题： a.为什么它能够检测数据D中的任何单⽐特差错？ b.上述G能够检测任何奇数⽐特差错吗？为什么？解题思路：本题思路很简单，将题⽬转换⼀下，就是⼀个能被G模2整除的数，如果突然增⼤某个值，那么它还能被G模2整除吗？注意：根据第六章内容，模2运算加不进位、减不借位，因此可以认为都是增⼤某个值。
a问题解答：如果第i位⽐特被翻转，则被校验的数⼤⼩变为：K = (D * 2r)XOR R + 2i，其中(D * 2r)XOR R这部分能被G模2整除，剩下的2i是否能被G模2整除呢？答案是不能，因为G中有2位是1，明显是除不尽的。
b问题解答：可以注意到，G=1001这个数能被11模2整除，但是任何包含奇数个1的数（这些1不必要连续）不能被11模2整除。
因此能够检测出来。
第⼋题原题：在6.3节中，我们提供了时隙ALOHA效率推导的概要。
在本习题中，我们将完成这个推导。
a.前⾯讲过，当有N个活跃节点时，时隙ALOHA的效率是Np(1-p)N-1。
求出使这个表达式最⼤化的p值p*。
b.使⽤在（a）中求出的p值，令N接近于⽆穷，求出时隙ALOHA的效率。
（提⽰：当N接近于⽆穷时，(1 - 1/N)N接近于1/e。
）解题思路：涉及到⼀些⾼等数学求导和极限的知识。
a问题解答：对于⼀个连续函数的最⼤值，我们可以通过求导的⽅式来计算，原式 f(p) = Np(1-p)N-1则其导数 f`(p) = (Np)`(1-p)N-1 - Np((1-p)N-1)`= N(1-p)N-1 - Np(N - 1)(1-p)N-2= N(1-p)N-2((1 - p) - p(N - 1))= N(1-p)N-2(1 - pN)当导数为0时，能取到最⼤值，则此时p=1/N，即p*=1/N。
b问题解答：将a问题求出的p*带⼊原式，变形为N*1/N(1 - 1/N)N-1=(1 - 1/N)N-1。
