question_5.htm

软件设计师模拟试卷,点击里面的Exe文件可以随机出题

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>char ch;/*</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>当前结点表示的字符，对于非叶子结点，此域不用</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>*/<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>int weight;/*</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>当前结点的权值</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>*/<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>int parent;/*</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>当前结点的父结点的下标，为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>0</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>时表示无父结点</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>*/<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>int lchild,rchild;<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>/*</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>当前结点的左、右孩子结点的下标，为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>0</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>时表示无对应的孩子结点</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>*/<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>}Ht</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>2*MAXLEAFNUM</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>;<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>②用′</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>0</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>′或′</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>1</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>′标识最优二叉树中分支的规则是：从一个结点进入其左</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>(</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>右</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>)</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>孩子结点，就用′</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>0</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>′</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>(</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>′</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>1</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>′</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>)</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>标识该分支</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>(</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>示例如图</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>3</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>所示</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>)</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>③若用上述规则标识最优二叉树的每条分支后，从根结点开始到叶子结点为止，按经过分支的次序，将相应标识依次排列，可得到由′</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>0</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>′、′</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>1</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>′组成的一个序列，称此序列为该叶子结点的前缀编码。例如图</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>3</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>所示的叶子结点</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>a</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>、</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>b</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>、</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>c</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>、</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>d</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>的前缀编码分别是</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>110</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>、</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>0</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>、</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>111</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>、</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>10</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>【函数</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>5</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>．</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>1</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>说明】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>函数</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>void LeafCode(int root,int n)</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>的功能是：采用非递归方法，遍历最优二叉树的全部叶子结点，为所有的叶子结点构造前缀编码。其中形参</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>root</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>为最优二叉树的根结点下标；形参</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>n</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>为叶子结点个数。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>在构造过程中</span><span
style='mso-bidi-font-size:10.5pt'> </span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，将</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>Ht</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］．</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>weight</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>域用作被遍历结点的遍历状态标志。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>【函数</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>5</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>．</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>1</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>char**Hc</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>；<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>void LeafCode(int root,int n)<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:
"Times New Roman"'>{</span><span lang=EN-US style='mso-bidi-font-size:10.5pt'>/*</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>为最优二叉树中的</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>n</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>个叶子结点构造前缀编码，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>root</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>是树的根结点下标</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>*/<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>int i,p=root,cdlen=0;char code</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>20</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>;<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>Hc=(char**)malloc((n+1)*sizeof(char*));/*</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>申请字符指针数组</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>*/<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>for(i=1;i</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>＜</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>=p;++i)<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>Ht</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>i</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］．</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>weight=0;/*</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>遍历最优二叉树时用作被遍历结点的状态标志</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>*/<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>while(p){/*</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>以非递归方法遍历最优二叉树，求树中每个叶子结点的编码</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>*/<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>if(Ht</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］．</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>weight==0){/*</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>向左</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>*/<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>Ht</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］．</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>weight=1;<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>if (Ht</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］．</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>lchild !=0) { p=Ht</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］．</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>lchild; code</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>cdlen++</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>=</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>′</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>0</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>′</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>;}<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>else if (Ht</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］．</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>rchild==0) {/*</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>若是叶子结</span><span
style='mso-bidi-font-size:10.5pt'> </span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体;mso-hansi-font-family:"Times New Roman"'>点，则保存其前缀编码</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>*/<o:p></o:p></span></p>