ds6习.htm

这是清华大学所用的数据结构的电子版教材

<p class="MsoNormal"><span lang="EN-US"><font size="5" color="#FFFFFF"><b>6</b></font></span><font size="5" color="#FFFFFF"><b><span style="font-family:宋体;  
mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">．</span><span lang="EN-US">4</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;  
mso-hansi-font-family:&quot;Times New Roman&quot;">已知一棵树为</span><span lang="EN-US">m</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">的树中有</span><span lang="EN-US">n<sub>1</sub></span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">个度为</span><span lang="EN-US">1</span><span style="font-family:  
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">的结点，</span><span lang="EN-US">n<sub>2</sub></span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;  
mso-hansi-font-family:&quot;Times New Roman&quot;">个度为</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">的结点，</span><span lang="EN-US">…n<sub>m</sub></span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">个度为</span><span lang="EN-US">m</span><span style="font-family:  
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">的结点，问该树中有多少片叶子？</span></b></font></p>  
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span lang="EN-US">6.5 </span><span style="font-family:宋体;    
mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">一个深度为</span><span lang="EN-US">h</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;  
mso-hansi-font-family:&quot;Times New Roman&quot;">的满</span><span lang="EN-US">k</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">叉树有如下性质：第</span><span lang="EN-US">h</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">层上的结点都是叶子结点，其余各层上每个结点都有</span><span lang="EN-US">k</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">棵非空子树。如果按层次顺序（同层自左至右）从未有过开始对全部结点编号，问：</span></b></font></p>  
<p class="MsoNormal" style="text-indent: -36.0pt; mso-list: l0 level1 lfo3; tab-stops: list 36.0pt; margin-left: 36.0pt; margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman" lang="EN-US">1.</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">各层的结点数目是多少？</span></b></font></p>  
<p class="MsoNormal" style="text-indent: -36.0pt; mso-list: l0 level1 lfo3; tab-stops: list 36.0pt; margin-left: 36.0pt; margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman" lang="EN-US">2.</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">编号为</span><span lang="EN-US">i</span><span style="font-family:  
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">的结点的双亲结点（若存在）的编号是多少？</span></b></font></p>  
<p class="MsoNormal" style="text-indent: -36.0pt; mso-list: l0 level1 lfo3; tab-stops: list 36.0pt; margin-left: 36.0pt; margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman" lang="EN-US">3.</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">编号为</span><span lang="EN-US">i</span><span style="font-family:  
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">的结点的第</span><span lang="EN-US">j</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;  
mso-hansi-font-family:&quot;Times New Roman&quot;">个孩子结点(若存在)的编号是多少？</span></b></font></p>  
<p class="MsoNormal" style="text-indent: -36.0pt; mso-list: l0 level1 lfo3; tab-stops: list 36.0pt; margin-left: 36.0pt; margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman" lang="EN-US">4.</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">编号为</span><span lang="EN-US">i</span><span style="font-family:  
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">的结点有右兄弟的条件是什么？其右兄弟的编号是多少？</span></b></font></p>  
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span lang="EN-US">6</span><span style="font-family:宋体;  
mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">．</span><span lang="EN-US">6     
</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;  
mso-hansi-font-family:&quot;Times New Roman&quot;">高度为</span><span lang="EN-US">h</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">的完全二叉树至少有多少个结点？至多有多少个结点？</span></b></font></p>  
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span lang="EN-US">6</span><span style="font-family:宋体;  
mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">．</span><span lang="EN-US">7     
</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;  
mso-hansi-font-family:&quot;Times New Roman&quot;">在具有</span><span lang="EN-US">n</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">个结点的</span><span lang="EN-US">k</span><span style="font-family:  
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">叉树（</span><span lang="EN-US">k</span><span style="font-family:宋体">≥<span lang="EN-US">2</span></span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">）的</span><span lang="EN-US">k</span><span style="font-family:  
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">叉树链表表示中，有多少个空指针？</span></font></b></p>  
<p class="MsoNormal"><span lang="EN-US"><font size="5" color="#FFFFFF"><b>6</b></font></span><font size="5" color="#FFFFFF"><b><span style="font-family:宋体;  
mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">．</span><span lang="EN-US">8     
</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;  
mso-hansi-font-family:&quot;Times New Roman&quot;">假设二叉树包含的结点数据为</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">，</span><span lang="EN-US">3</span><span style="font-family:  
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">，</span><span lang="EN-US">7</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;  
mso-hansi-font-family:&quot;Times New Roman&quot;">，</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">，</span><span lang="EN-US">12</span><span style="font-family:  
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">。</span></b></font></p>  
<p class="MsoNormal" style="margin-left:47.25pt;text-indent:-36.0pt;mso-list:  
l24 level1 lfo5;tab-stops:list 47.25pt"><b><font size="5" color="#FFFFFF"><span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman" lang="EN-US">1.</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;  
mso-hansi-font-family:&quot;Times New Roman&quot;">画出两棵高度最大的二叉树；</span></font></b></p>  
<p class="MsoNormal" style="margin-left:47.25pt;text-indent:-36.0pt;mso-list:  
l24 level1 lfo5;tab-stops:list 47.25pt"><b><font size="5" color="#FFFFFF"><span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman" lang="EN-US">2.</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;  
mso-hansi-font-family:&quot;Times New Roman&quot;">画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。</span></font></b></p>  
<p class="MsoNormal"><span lang="EN-US"><font size="5" color="#FFFFFF"><b>6</b></font></span><font size="5" color="#FFFFFF"><b><span style="font-family:宋体;  
mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">．</span><span lang="EN-US">9     
</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;  
mso-hansi-font-family:&quot;Times New Roman&quot;">试找出分别满足下面条件的所有二叉树：</span></b></font></p>  
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>1.<span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">前序序列和中序序列相同；</span><span style="mso-spacerun: yes" lang="EN-US">&nbsp;&nbsp;   
</span></b></font></p>  
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;  
mso-hansi-font-family:&quot;Times New Roman&quot;"><font size="5" color="#FFFFFF"><b>2.中序序列和后序序列相同；</b></font></span></p>  
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font color="#FFFFFF"><b><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;"><font size="5">3.前序序列和后序序列相同；</font></span><font size="5"><span style="mso-spacerun: yes" lang="EN-US">&nbsp;&nbsp;   
</span></font></b></font></p>  
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;  
mso-hansi-font-family:&quot;Times New Roman&quot;"><font size="5" color="#FFFFFF"><b>4.前序、中序、后序序列均相同。</b></font></span></p>  
<p class="MsoNormal"><span lang="EN-US"><b><font size="5" color="#FFFFFF">6</font></b></span><b><font size="5" color="#FFFFFF"><span style="font-family:宋体;  
mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">．</span><span lang="EN-US">10<span style="mso-spacerun: yes">&nbsp;     
</span></span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">试采用顺序存储方法和链接存储方法分别画出</span><span lang="EN-US">6.     
30</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">所示各二叉树的存储结构。</span></font></b></p>  
<p class="MsoNormal" align="center"><b><font size="5" color="#FFFFFF"><span style="mso-spacerun: yes" lang="EN-US">&nbsp;&nbsp;<img border="0" src="ds6习13.gif" width="182" height="148"><img border="0" src="ds6习14.gif" width="128" height="144"><img border="0" src="ds6习15.gif" width="101" height="140"></span></font></b></p> 
<p class="MsoNormal" align="center"><b><font size="5" color="#FFFFFF"><span style="mso-spacerun: yes" lang="EN-US">&nbsp;</span></font></b><b><font size="5" color="#FFFFFF"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;; 
mso-hansi-font-family:&quot;Times New Roman&quot;">图</span><span lang="EN-US">6.30</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family: 
&quot;Times New Roman&quot;"></span></font></b></p> 
<p class="MsoNormal"><span lang="EN-US"><b><font size="5" color="#FFFFFF">6</font></b></span><b><font size="5" color="#FFFFFF"><span style="font-family:宋体; 
mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">．</span><span lang="EN-US">11     
</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;  
mso-hansi-font-family:&quot;Times New Roman&quot;">分别写出图</span><span lang="EN-US">6.30</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:  
&quot;Times New Roman&quot;">所示各二叉树的前序、中序和后序序列。</span></font></b></p>