📄 ds6习.htm
字号:
<p class="MsoNormal"><font color="#FFFFFF"><b><span lang="EN-US"><font size="5">6</font></span><font size="5"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">．</span><span lang="EN-US">12
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">若二叉树中个结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序列均能惟一地确定一棵二叉树，但由前序序列和后序序列却不一定能惟一地确定一棵二叉树。</span></font></b></font></p>
<p class="MsoNormal" style="text-indent: -36.0pt; mso-list: l8 level1 lfo7; tab-stops: list 36.0pt; margin-left: 36.0pt; margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">1.
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">已知一棵二叉树的前序序列和中序序列分别为</span><span lang="EN-US">ABDGHCEFI</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">和</span><span lang="EN-US">GDHBAECIF</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，请画出此二叉树。</span></b></font></p>
<p class="MsoNormal" style="text-indent: -36.0pt; mso-list: l8 level1 lfo7; tab-stops: list 36.0pt; margin-left: 36.0pt; margin-top: 0; margin-bottom: 0"><font color="#FFFFFF"><b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman""><font size="5">2.
已知一棵二叉树的中序序列和后序序列分别为</font></span><font size="5"><span lang="EN-US">BDCEAFHG</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">和</span><span lang="EN-US">DECBHGFA</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，请画出此二叉树。</span></font></b></font></p>
<p class="MsoNormal" style="text-indent: -36.0pt; mso-list: l8 level1 lfo7; tab-stops: list 36.0pt; margin-left: 36.0pt; margin-top: 0; margin-bottom: 0"><font color="#FFFFFF"><b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman""><font size="5">3.
已知两棵二叉树前序序列和后序序列均为</font></span><font size="5"><span lang="EN-US">AB</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">和</span><span lang="EN-US">BA</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，请画出这两棵不同的二叉树。</span></font></b></font></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:"Times New Roman";mso-hansi-font-family:"Times New Roman"">．</span><span lang="EN-US">13
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">对二叉树中结点进行按层次顺序（每一层自左至右）的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。现已知一棵二叉树的层次序列为</span><span lang="EN-US">ABCDEFGHIJ</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">，中序序列为</span><span lang="EN-US">DBGEHJACIF</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">，请画出该二叉树。</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:"Times New Roman";mso-hansi-font-family:"Times New Roman"">．</span><span lang="EN-US">14
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">试画出图</span><span lang="EN-US">6.30</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">所示各二叉树的前序、中序和后序线索树及相应的线索链表。</span></font></b></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span lang="EN-US">6</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">．</span><span lang="EN-US">15 </span></b></font><b><font size="5" color="#FFFFFF"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">下属编码哪一组不是前缀码？</span></font></b></p>
<p class="MsoNormal"><span lang="EN-US"><span style="mso-spacerun: yes"><b><font size="5" color="#FFFFFF"> 1.</font></b></span><b><font size="5" color="#FFFFFF">{00</font></b></span><b><font size="5" color="#FFFFFF"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">01</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">10</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">11}</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span></font></b></p>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span lang="EN-US"> 2.{0</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">1</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">00</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">11}</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span></font></b></p>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span lang="EN-US"> 3.{0</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">10</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">110</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">111}</span></font></b></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span lang="EN-US">6</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">．</span><span lang="EN-US">16 </span></b></font><span lang="EN-US"><b><font size="5" color="#FFFFFF"><span style="font-style: normal; font-variant: normal; font-family: Times New Roman"></span></font></b></span><b><font size="5" color="#FFFFFF"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman""> 假设用于通信的电子由字符集</span><span lang="EN-US">{a,b,c,d,e,f,g,h}</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">中的字母构成，这</span><span lang="EN-US">8</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">个字母在电文中出现的概率分别为</span><span lang="EN-US">{0.07</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">0.19</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">0.02</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">0.06</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">0.32</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">0.03</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">0.21</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">0.10}</span></font></b></p>
<p class="MsoNormal" style="margin-left:57.75pt;text-indent:-36.0pt;mso-list:
l25 level1 lfo11;tab-stops:list 57.75pt"><span lang="EN-US" style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman""><b><font size="5" color="#FFFFFF">(1<span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman" lang="EN-US">)</span><span style="font-style: normal; font-variant: normal; font-family: Times New Roman">
</span></font></b></span><b><font size="5" color="#FFFFFF"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">为这</span><span lang="EN-US">8</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">个字母设计哈夫曼编码。</span></font></b></p>
<p class="MsoNormal" style="margin-left:57.75pt;text-indent:-36.0pt;mso-list:
l25 level1 lfo11;tab-stops:list 57.75pt"><font size="5" color="#FFFFFF"><b><span lang="EN-US" style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">(2<span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman" lang="EN-US">)</span><span style="font-style: normal; font-variant: normal; font-family: Times New Roman">
</span></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">若用三位二进制数（</span><span lang="EN-US">0~7</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">）对这个</span><span lang="EN-US">8</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几？它使电文总长平均压缩多少？</span></b></font></p>
<p class="MsoNormal" style="margin-left:78.75pt;text-indent:-31.5pt;mso-list:
l6 level1 lfo12;tab-stops:list 78.75pt"><span lang="EN-US" style="font-family: 宋体"><o:p>
</o:p>
</span></p>
<!--mstheme--></font>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -