⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 cs6.htm

📁 文章说明的程序设计
💻 HTM
字号:
🔍 
<html>

<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>第六章 树</title>
</head>

<body>

<b><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="4">
<p ALIGN="center" style="line-height: 150%">第六章 树</p>
</font></b><font SIZE="3">
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
</font><b><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">
<p ALIGN="JUSTIFY" style="line-height: 150%">一、填空题</p>
</font></b><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">
<p ALIGN="JUSTIFY" style="line-height: 150%">1．假定一棵树的广义表表示为A(B(E)，C(F(H，l 
J)，G)，D)，则该树的度为<u> ① </u>，树的深度为<u> ② </u>，终端结点的个数为<u> 
③ </u>，单分支结点的个数为<u> ④ </u>，双分支结点的个数为<u> 
⑤ </u>，三分支结点的个数为<u> ⑥ </u>，C结点的双亲结点为<u> 
⑦ </u>，其孩子结点为<u> ⑧ </u>和 <u>⑨ </u>结点。</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">2．一棵深度为h的满k叉树有如下性质：</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">第h层上的结点都是叶子结点，其余各层上的每个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，则各层上的结点数目是<u> 
① </u>，编号为n的结点的双亲结点(若存在)的编号是<u> ②</u>，编号为n的结点的第i个孩子结点(若存在)的编号是<u> 
③</u>，编号为n的结点有右兄弟的条件是<u> ④ </u>，其右兄弟的编号是<u> 
⑤ </u>。</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">3．设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有<u> 
① </u>个。</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">4．对于一个具有n个结点的二叉树，当它为一棵<u> 
1 </u>二叉树时具有最小高度，即</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">为<u> 2 </u>，当它为一棵单支树具有<u> 
3 </u>高度，即为<u> ④ </u>。</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">5．在二叉搜索排序树上进行搜索查找时，其时间复杂度为<u> 
1 </u>，进行删除时，其时间</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">复杂度为<u> 2 </u>。 · ．</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">6．由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为<u> 
①</u>。</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">7．在一棵二叉排序树上按<u> 
1 </u>遍历得到的结点序列是一个有序序列。</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">8．对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">为<u> 1 </u>个，其中<u> 2 </u>个用于链接孩子结点,<u> 
3 </u>个空闲着。</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">9．已知一棵二叉排序树如下图所示，则在查找成功的情况下查找每个元素的平均查找长度为<u> 
1 .</p>
</u></font><u><font SIZE="3">
<p ALIGN="CENTER" style="line-height: 150%"><img SRC="../tp/Image1.gif" WIDTH="184" HEIGHT="116"></p>
</font></u><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">
<p ALIGN="JUSTIFY" style="line-height: 150%">10．一棵具有n个结点的理想平衡二叉树的深度等于<u> 
1 </u>的向上取整或等于<u> 2 </u>的向下取整加1。</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">11．在一棵二叉树中，度为0的结点个数为</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="4">n<sub>o</sub></font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">，度为2的结点个数为</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="4">n<sub>2</sub></font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">，则no=<u> 
1 </u>。</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">12。一棵深度为k的满二叉树的结点总数为<u> 
1 </u>，一棵深度为k的完全二叉树的结点</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">总数的最小值为<u> 2 </u>，最大值为<u> 
3 </u>。</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">13。在具有n个结点的二叉排序树上插入一个新结点时，其时间复杂度大致为<u> 
1 </u>，</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">根据n个数据元素生成一棵二叉排序树肘，其时间复杂度大致为<u> 
2 </u>。</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">14。已知8个数据元素由(35，75，40，15，20，55，95，65)按照依次插入结点的方</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">法生成一棵二叉排序树后，最后两层上的结点总数为<u> 
1 </u>。</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">15．由a，b，c三个结点构成的二叉树，共有<u> 
1 </u>种不同的结构。</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<b>
<p ALIGN="JUSTIFY" style="line-height: 150%">二、选择题</p>
</b>
<p ALIGN="JUSTIFY" style="line-height: 150%">1．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">点数为2个，则度为0的结点数为<u> 
</u>个。</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">(A)4 (B)5 (C)6 (D)7</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">2．假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">为<u> </u>个。 ．</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">(A)15 (B)16 (C)17 （D）47</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">3．假定一棵三叉树的结点数为50，则它的最小高度为<u></p>
</u>
<p ALIGN="JUSTIFY" style="line-height: 150%">(A)3 (B)4 (C)5 （D） 6</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">4．在一棵二叉树上第5层的结点数最多为<u> 
</u>度为1的结则叶子结点数</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">(A)8 (B)16 (C)15 (D)32</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">5．用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组R[1-n]中</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">有左子女，则左子女是结点<u> 
</u>。</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">(A)R[2i+1] (B)R[2i] (C)R[i/2] 
(D)R[2i-1]</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">6．在一棵具有k层的满三叉树中，结点总数为<u> 
</u>。</p>
</font><b><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="4">
<p ALIGN="JUSTIFY" style="line-height: 150%">(A)(3<sup>k</sup>-1)／2 (B)3<sup>k</sup>-1 
(C) (3<sup>k</sup>-1)／3 (D)3<sup>k</p>
</sup></font></b><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">
<p ALIGN="JUSTIFY" style="line-height: 150%">7．由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度<u></p>
</u>
<p ALIGN="JUSTIFY" style="line-height: 150%">(A)23 (B)37 (C)46 (D)44</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">8．在一棵高度为k的理想平衡二叉树中，最少含有<u> 
</u>个结点。</p>
</font><b><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="4">
<p ALIGN="JUSTIFY" style="line-height: 150%">(A)2<sup>k-1</sup> (B) 2<sup>k </sup>+ 
1 (C) 2<sup>k</sup>-1 (D)2<sup>k</p>
</sup></font></b><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">
<p ALIGN="JUSTIFY" style="line-height: 150%">9。树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的<u> 
.</p>
</u>
<p ALIGN="JUSTIFY" style="line-height: 150%">(A)la(2b(3d，3e)，2c) (B)a(b((d)，e)，c)</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">(C)a(b(d，e)，c) (D)a(b，d(e)，c)</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">11。如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">(A)中序 (B)前序 (C)后序 (D)层次序</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">12．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序<u> 
</u>·</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">(A)不发生改变 (B)发生改变 
(C)不能确定 (D)以上都不对</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">13．欲实现任意二叉树的后序遍历的非递归算法而不必使用栈结构，最佳方案是二叉树</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">采用<u> </u>存储结构。</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">(A)二叉链表 (B)广义表 (C)二叉链表 
(D)顺序</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">14．设a，b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是<u></p>
</u>
<p ALIGN="JUSTIFY" style="line-height: 150%">(A)a在b右方 (B)a在b左方 (C)a是b的祖先 
(O)a是b的子孙</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">15．线索二叉树是一种<u> </u>结构。</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">(A)逻辑 (B)逻辑和存储 (C)物理 
(D)线性</p>
</font><font SIZE="3">
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">
<p ALIGN="JUSTIFY" style="line-height: 150%">三、应用题</p>
</font><font SIZE="3">
<p ALIGN="JUSTIFY" style="line-height: 150%">1</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">、</font><font SIZE="3"> 
</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">使用</font><font SIZE="3"> 
(1) </font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">顺序表示和</font><font SIZE="3"> 
(2) </font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">二叉链表表示法，分别画出右图所示二叉树的存储表示。</p>
</font><font SIZE="3">
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">2</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">、一棵高度为</font><font SIZE="3">h</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">的满</font><font SIZE="3">k</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">叉树有如下性质</font><font SIZE="3">: 
</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">第</font><font SIZE="3">h</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">层上的结点都是叶结点</font><font SIZE="3">, 
</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">其余各层上每个结点都有</font><font SIZE="3">k</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">棵非空子树</font><font SIZE="3">, 
</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">如果按层次自顶向下</font><font SIZE="3">, 
</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">同一层自左向右</font><font SIZE="3">, 
</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">顺序从</font><font SIZE="3">1</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">开始对全部结点进行编号</font><font SIZE="3">, 
</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">试问</font><font SIZE="3">:</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">(1) </font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">各层的结点个数是多少</font><font SIZE="3">?</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">(2) </font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">编号为</font><font SIZE="3">i</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">的结点的父结点</font><font SIZE="3">(</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">若存在</font><font SIZE="3">)</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">的编号是多少</font><font SIZE="3">?</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">(3) </font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">编号为</font><font SIZE="3">i</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">的结点的第</font><font SIZE="3">m</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">个孩子结点</font><font SIZE="3">(</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">若存在</font><font SIZE="3">)</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">的编号是多少</font><font SIZE="3">?</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">(4) </font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">编号为</font><font SIZE="3">i</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">的结点有右兄弟的条件是什么</font><font SIZE="3">? 
</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">其右兄弟结点的编号是多少</font><font SIZE="3">?</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">(5) </font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">若结点个数为</font><font SIZE="3"> 
n, </font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">则高度</font><font SIZE="3">h</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">是</font><font SIZE="3">n 
</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">的什么函数关系</font><font SIZE="3">?</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">3</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">、【解答】</p>
</font><font SIZE="3">
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
<p ALIGN="JUSTIFY" style="line-height: 150%"></font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">此树的带权路径长度</font><font SIZE="3">WPL 
= 229</font><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">。</p>
</font><font SIZE="3">
<p ALIGN="JUSTIFY" style="line-height: 150%">　</p>
</font>

</body>

</html>

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -