下载文档原格式
第六章树和二叉树（下载后用阅读版式视图或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。
6.2 试作出101序列检测器得状态图，该同步电路由一根输入线X ，一根输出线Z ，对应与输入序列的101的最后一个“1”，输出Z=1。
其余情况下输出为“0”。
（1） 101序列可以重叠，例如：X ：010101101 Z ：000101001 （2） 101序列不可以重叠，如：X ：010******* Z ：0001000010 解：1）S 0：起始状态，或收到101序列后重新开始检测。
S 1：收到序列起始位“1”。
S 2：收到序列前2位“10”。
10101…X/Z0/01/0X/Z11…100…2）10101…X/Z0/0X/Z11…100…6.3对下列原始状态表进行化简：(a)解：1）列隐含表：A B CDC B ×A B CD C B ×AD BC ××(a)(b)2）进行关联比较 所有的等价类为：AD ，BC 。
最大等价类为：AD ，BC ，重新命名为a,b 。
3）列最小化状态表为：a/1b/0bb/0a/0aX=1X=0N(t)/Z(t)S(t)(b)N （t ）/Z （t ）S （t ）X=0 X=1A B/0 H/0B E/0 C/1C D/0 F/0D G/0 A/1E A/0 H/0F E/1 B/1G C/0 F/0H G/1 D/1解：1）画隐含表：2）进行关联比较：AC,BD,EG ,HF,之间互为等价隐含条件，所以分别等价。
重新命名为： a, b, e, h 3)列最小化状态表：N （t ）/Z （t ） S （t ）X=0 X=1a b/0 h/0b e/0 a/1 e a/0 h/0 h e/1 b/1试分析题图6.6电路，画出状态转移图并说明有无自启动性。
解：激励方程：J1=K1=1；J2=Q1n⎯Q3n，K2=Q1nJ2=Q1n Q2n，K2=Q1n状态方程：Q1n+1=⎯Q1n·CP↓Q2n+1=[Q1n⎯Q3n⎯Q2n+⎯Q1n Q2n]·CP↓Q3n+1=[Q1n Q2n⎯Q3n+⎯Q1n Q3n]·CP↓状态转移表：序号Q3Q2Q10 1 2 3 4 5 000 001 010 011 100 101偏离状态110Æ111111Æ000状态转移图状态转移图：Q3Q2Q1偏离态能够进入有效循环，因此该电路具有自启动性。
数据结构答案第6章第6章图2005-07-14第6章图课后习题讲解1.填空题⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。
【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。
⑵任何连通图的连通分量只有一个，即是（）。
【解答】其自身⑶图的存储结构主要有两种，分别是（）和（）。
【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。
⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。
【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。
⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。
【解答】求第j列的所有元素之和⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。
【解答】出度⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。
【解答】前序，栈，层序，队列⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Krukal算法求最小生成树的时间复杂度为（）。
【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Krukal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。
⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。
【解答】回路⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi,vj,vk的相对次序为（）。
【解答】vi,vj,vk【分析】对由顶点vi,vj,vk组成的图进行拓扑排序。
第六章6.1 请简述类和对象的关系。
答：类是一种抽象数据类型，是定义对象的蓝本，它描述这一类对象所共有的属性。
对象是这种数据类型的一个具体实例。
类是抽象的，而对象是具体的。
用一个形象的比喻：类就像工厂中生产产品的模子，而对象则像用这个模子生产出的具体产品。
6.2 简述类的公有类型成员和私有类型成员的区别。
答：类的共有成员是类为外界提供的接口，外界可以通过它们来访问类。
具体地说，可以从这个类的外部使用对象名加点操作符来访问这个类中的共有成员，如果是静态的共有成员，还可以使用类名加域解析操作符去访问它们。
而类的私有成员则不能用上述的形式从类外直接访问，它们只能被同一类的成员函数访问。
6.3 以下的叙述中，那条是不正确的。
A、在类的成员函数中，可以访问类的public型成员。
B、在类的成员函数中，可以访问类的private型成员。
C、在类的成员函数中，可以访问类的protected型成员。
D、在类的成员函数中，不可以访问类的private型成员。
答：D是不正确的。
6.4 以下的叙述中，那条是正确的。
A、使用对象名和点操作符只能访问类的public成员。
B、使用对象名和点操作符能访问类的public和protected成员，不能访问private成员。
C、使用对象名和点操作符能访问类的public和private成员，不能访问protected成员。
D、使用对象名和点操作符能访问类的任意类型的成员。
答：A是正确的。
6.5 请创建一个表示雇员信息的employee类，其中的数据成员包括：char数组型的私有成员name，用来存放雇员的姓名；int型的私有成员empNo，表示雇员的编号；float型的私有成员salary，存放雇员的月薪。
函数成员包括：给上述每个私有数据成员赋值的公有成员函数，和读取这些私有数据成员的公有成员函数以及显示雇员信息的公有成员函数display。
解：employee类及测试该类的完整程序代码如下：#include<iostream>using namespace std;class employee{private:char name[20];int empNo;float salary;public:void setname(char *cp);void setempNo(int no);void setsalary(float sa);char*getname();int getempNo();float getsalary();void display();};void employee::setname(char*cp){int i=0;while(*cp){name[i]=*cp;i++;cp++;}name[i]='\0';}voidemployee::setempNo(int no){empNo=no;}voidemployee::setsalary(float sa){salary=sa;}char*employee::getname(){return name;}int employee::getempNo(){return empNo;}float employee::getsalary(){return salary;}void employee::display(){cout<<"工号为"<<empNo<<"的雇员"<<name<<"的月薪为"<<salary<<endl;}void main(){employee em1;char name[20];int emno;float sa;cout<<"请输入雇员的姓名：";cin>>name;cout<<"请输入雇员工号：";cin>>emno;cout<<"请输入雇员薪水：";cin>>sa;em1.setname(name);em1.setempNo(emno);em1.setsalary(sa);cout<<"工号为"<<em1.getempNo()<<"的雇员"<<em1.getname()<<"的薪水为"<<em1.getsalary()<<endl;}6.6 创建一个表示汽车的类automobile，其中的数据成员包括：char数组型的私有成员brand，表示汽车的品牌；float型私有成员load，表示汽车的载重量；float型私有成员speed，表示汽车的行驶速度。
第6-7章一．选择/填空1、设图G 的邻接矩阵为0101010010000011100000100，则G 的边数为( D )． A ．5 B ．6 C ．3 D ．42、设有向图（a ）、（b ）、（c ）与（d ）如下图所示，则下列结论成立的是( A )．A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的3、给定无向图G 如下图所示，下面给出的结点集子集中，不是点割集的为（ B ）．A ．{b , d }B ．{d }C ．{a , c }D ．{b , e }4、图G 如下图所示，以下说法正确的是 ( D ) ．A ．{(a , c )}是割边B ．{(a , c )}是边割集C ．{(b , c )}是边割集D ．{(a, c ) ,(b, c )}是边割集5、无向图G 存在欧拉通路，当且仅当(D )．A ．G 中所有结点的度数全为偶数B ．G 中至多有两个奇数度结点C ．G 连通且所有结点的度数全为偶数D ．G 连通且至多有两个奇数度结点6、设G 是有n 个结点，m 条边的连通图，必须删去G 的( A )条边，才能确定G 的一棵生成树．A ．1m n −+B ．m n −C ．1m n ++D ．1n m −+7、已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为（B ）．A ．8B ．5C ．4D ．38、已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 9、连通无向图G 有6个顶点9条边，从G 中删去 4 条边才有可能得到G 的一棵生成树T ．10、如右图 相对于完全图K 5的补图为（A ）。
11、给定无向图，如下图所示，下面哪个边集不是其边割集（ B ）。
A 、；B 、{<v1,v4>,<v4,v6>};C 、；D 、。
12、设D 是有n 个结点的有向完全图,则图D 的边数为( A ) (A))1(−n n (B))1(+n n (C)2/)1(+n n (D)2/)1(−n n 13、无向图G 是欧拉图,当且仅当( C )(A) G 的所有结点的度数都是偶数 (B)G 的所有结点的度数都是奇数(C)G 连通且所有结点的度数都是偶数 (D) G 连通且G 的所有结点度数都是奇数。
习题六参考答案一、选择题1.在一个有个顶点的有向图中，若所有顶点的出度之和为，则所有顶点的入度之和为（A）。
A. B. C. D.2.一个有向图有个顶点，则每个顶点的度可能的最大值是（B）。
A. B. C. D.3.具有6个顶点的无向图至少应有（A）条边才能确保是一个连通图。
A.5B.6C.7D.84.一个有n个顶点的无向图最多有（C）条边。
A. B. C. D.5.对某个无向图的邻接矩阵来说，下列叙述正确的是（A）。
A.第行上的非零元素个数和第列上的非零元素个数一定相等B.矩阵中的非零元素个数等于图中的边数C.第行与第列上的非零元素的总数等于顶点的度数D.矩阵中非全零行的行数等于图中的顶点数6.已知一个有向图的邻接矩阵，要删除所有以第个顶点为孤尾的边，应该（B）。
A.将邻接矩阵的第行删除B.将邻接矩阵的第行元素全部置为0C.将邻接矩阵的第列删除D.将邻接矩阵的第列元素全部置为07.下面关于图的存储的叙述中，哪一个是正确的？……（A）A．用邻接矩阵存储图，占用的存储空间只与图中顶点数有关，而与边数无关B．用邻接矩阵存储图，占用的存储空间只与图中边数有关，而与顶点数无关C．用邻接表存储图，占用的存储空间只与图中顶点数有关，而与边数无关D．用邻接表存储图，占用的存储空间只与图中边数有关，而与顶点数无关8.对图的深度优先遍历，类似于对树的哪种遍历？……（A）A.先根遍历B.中根遍历C．后根遍历D．层次遍历9.任何一个无向连通图的最小生成树（B）。
A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在10.下面是三个关于有向图运算的叙述：（1）求两个指向结点间的最短路径，其结果必定是唯一的（2）求有向图结点的拓扑序列，其结果必定是唯一的（3）求AOE网的关键路径，其结果必定是唯一的其中哪个（些）是正确的？……（D）A.只有（1）B.（1）和（2）C.都正确D.都不正确二、填空题1.若用表示图中顶点数，则有条边的无向图称为完全图。
第6章树和二叉树一、选择题部分答案解释如下。
12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。
42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。
A或B都不全。
由本题可解答44题。
47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域。
52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。
二、判断题6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。
19．任何结点至多只有左子树的二叉树的遍历就不需要栈。
37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。
38 . 新插入的结点都是叶子结点。
42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。
44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。
三.填空题1.(1)根结点(2)左子树(3)右子树2.(1)双亲链表表示法(2)孩子链表表示法(3)孩子兄弟表示法3．p->lchild==null && p->rchlid==null 4.(1) ++a*b3*4-cd (2)18 5.平衡因子6. 97. 128.(1)2k-1 (2)2k-19.(1)2H-1 (2)2H-1 (3)H=⎣log2N⎦+111. ⎣log2i⎦=⎣log2j⎦ 12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) ⎣log2n⎦ +1 13.n14. N2+1 15.(1) 2K+1-1 (2) k+1 16. ⎣N/2⎦ 17. 2k-2 18. 64 19. 99 20. 11 21.(1) n1-1 (2)n2+n322.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2) ⎣log2i⎦+1 23.69 24. 4 25.3h-1 26. ⎣n/2⎦ 27. ⎡log2k⎤+128.(1)完全二叉树 (2)单枝树，树中任一结点（除最后一个结点是叶子外）,只有左子女或只有右子女。
