📄 数据结构与程序设计7.htm
字号:
<html><head><title>上海交通大学1996年研究生考试数据结构及程序设计技术试题___www.yasee.net/ky</title><style type="text/css"><!-td{font-size:12px;line-height:17px;color:blue}body{font-size:12px;line-height:17px;color:black}A:link{text-decoration:none;color:6530EF}A:visited{text-decoration:none;color:6530EF}A:active{text-decoration:none}A:hover{text-decoration:underline;color:orange}-></style></head><body BGCOLOR="#FFFFFF" TOPMARGIN="5" MARGINHEIGHT="5"><div align="center"><center><table WIDTH="660" BORDER="0" CELLSPACING="0" CELLPADDING="0"> <tr> <td width="243"><p align="center"><a href="../index.htm" target="_blank"><img src=../../image/kaoyan.gif width=160 height=60 border=0 alt=雅舍考研之路></a></td> <td valign="bottom" align="right" width="517"><DIV align=center><IFRAME frameBorder=0 height=60 marginHeight=0 marginWidth=0 scrolling=no src="../../ad1.htm" width=468 bordercolor="#000000"></IFRAME></DIV></td><td width=136 valign="middle" align="right" height=60><a href=../index.htm target=_blank><img src=../../image/yasee02.gif width=120 border=0 height=60 alt=雅舍首页></a></td> </tr></table></center></div><div align=center><table width=100%><tr bgcolor=blue><td></td></tr></table><center><table WIDTH="750" BORDER="0" CELLSPACING="0" CELLPADDING="0"> <tr> <td colspan="2" height="20" width="660"></td> </tr> <tr valign="top"> <td width="69" align="center" valign="top"></td> <td width="591" valign="top"><p align="center"><strong>上海交通大学1996年研究生考试数据结构及程序设计技术试题</strong></p><br><br><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>一（</span><spanlang=EN-US>7</span></b><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>分）</span><span lang=EN-US><o:p></o:p></span></b></p> <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>设加权树</span><spanlang=EN-US>G=(V,E)</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>是一连通图，回答：</span></p> <p class=MsoNormal style='margin-left:36.0pt;text-indent:-36.0pt;mso-list:l2 level1 lfo2;tab-stops:list 36.0pt'><![if !supportLists]><span lang=EN-US style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>（1）<spanstyle='font:7.0pt "Times New Roman"'> </span></span><![endif]><spanstyle='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>何谓图</span><spanlang=EN-US>G</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>的最小生成树？</span></p> <p class=MsoNormal style='margin-left:36.0pt;text-indent:-36.0pt;mso-list:l2 level1 lfo2;tab-stops:list 36.0pt'><![if !supportLists]><span lang=EN-US style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>（2）<spanstyle='font:7.0pt "Times New Roman"'> </span></span><![endif]><spanstyle='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>设</span><spanlang=EN-US>G</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>为</span></p> <p class=MsoNormal><span lang=EN-US><!--[if gte vml 1]><v:shapetype id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f"> <v:stroke joinstyle="miter"/> <v:formulas> <v:f eqn="if lineDrawn pixelLineWidth 0"/> <v:f eqn="sum @0 1 0"/> <v:f eqn="sum 0 0 @1"/> <v:f eqn="prod @2 1 2"/> <v:f eqn="prod @3 21600 pixelWidth"/> <v:f eqn="prod @3 21600 pixelHeight"/> <v:f eqn="sum @0 0 1"/> <v:f eqn="prod @6 1 2"/> <v:f eqn="prod @7 21600 pixelWidth"/> <v:f eqn="sum @8 21600 0"/> <v:f eqn="prod @7 21600 pixelHeight"/> <v:f eqn="sum @10 21600 0"/> </v:formulas> <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"/> <o:lock v:ext="edit" aspectratio="t"/></v:shapetype><v:shape id="_x0000_i1025" type="#_x0000_t75" style='width:287.25pt; height:118.5pt'> <v:imagedata src="./上海交通大学数据结构1996.files/image001.gif" o:title="1"/></v:shape><![endif]--><![if !vml]><img width=383 height=158src="../school/image1.gif" v:shapes="_x0000_i1025"><![endif]></span></p> <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>试找出所有的最小生成树。</span></p> <p class=MsoNormal><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>二（</span><spanlang=EN-US>8</span></b><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>分）</span><span lang=EN-US><o:p></o:p></span></b></p> <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>已知一棵五次树，其结点数据场为一英文字母，现给出该五次树的前序周游结果（按前序打印数据场之值）及每个结点的次数如下：</span></p> <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>前序：</span><spanlang=EN-US>A,X,B,C,F,G,D,H,J,K,L,M,N,E,I</span></p> <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>次数：</span><spanlang=EN-US>5,0,0,2,0,0,1,1,3,0,0,1,0,1,0</span></p> <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>试画出表示该五次树的示意图。</span></p> <p class=MsoNormal><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>三（</span><spanlang=EN-US>8</span></b><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>分）</span><span lang=EN-US><o:p></o:p></span></b></p> <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>哈希（</span><spanlang=EN-US>hashing</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>）查找法有何特点？何谓冲突？试给出两种解决冲突的方法。</span></p> <p class=MsoNormal><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>四（</span><spanlang=EN-US>8</span></b><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>分）</span><span lang=EN-US><o:p></o:p></span></b></p> <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别。</span></p> <p class=MsoNormal><span lang=EN-US>T(n)=<span style="mso-spacerun:yes"> </span>1 (if n=1)</span></p> <p class=MsoNormal><span lang=EN-US><span style='mso-tab-count:1'> </span><spanstyle="mso-spacerun: yes"> </span>2T(n/2)+n<spanstyle="mso-spacerun: yes"> </span>n>1</span></p> <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>其中：</span><spanlang=EN-US>n</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>是问题的规模，为简单起见，设</span><spanlang=EN-US>n</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>是</span><spanlang=EN-US>2</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>的整数幂。</span></p> <p class=MsoNormal><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>五（</span><spanlang=EN-US>8</span></b><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>分）</span><span lang=EN-US><o:p></o:p></span></b></p> <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>已知</span><spanlang=EN-US>a,b,c,d,e,f,g,,h</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>字符出现的百分比分别为</span><span lang=EN-US>45%,15%,10%,8%,5%,5%,4%;</span><spanstyle='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>试给出它们的</span><spanlang=EN-US>huffuman</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>编码。</span></p> <p class=MsoNormal><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>六（</span><spanlang=EN-US>8</span></b><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>分）</span><span lang=EN-US><o:p></o:p></span></b></p> <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>从额外空间使用，平均情况下的时间复杂性，最坏情况下的时间复杂性三个方面来分析堆分类法和快速分类法的各自特性。若分裂对象已排好序，采用堆分类法还是快速分类法进行排序快？为什么？</span></p> <p class=MsoNormal><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>七（</span><spanlang=EN-US>8</span></b><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>分）</span><span lang=EN-US><o:p></o:p></span></b></p> <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>在进行磁带文件分类时，通常用置换一选择分类法生成最初合并段。若内存缓冲区只能存放</span><spanlang=EN-US>m</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>个记录，则平均情况下的最初合并段长度为多少？并请进行简单的分析。有无可能只生成一个最初合并段，即该合并段的记录总数和被分类的磁带文件记录总数相等？为什么？</span></p> <p class=MsoNormal><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>八（</span><spanlang=EN-US>15</span></b><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>分）</span><span lang=EN-US><o:p></o:p></span></b></p> <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>编写一个非递归的过程，将</span><spanlang=EN-US>r</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>数组整理为一个合乎最大化要求的堆。其中，</span><spanlang=EN-US>r</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>的说明为</span></p>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -