📄 数据结构与程序设计6.htm
字号:
<html><head><title>上海交通大学1992年研究生考试数据结构及程序设计技术试题___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>上海交通大学1992年研究生考试数据结构及程序设计技术试题</strong></p><br><br><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></b></p> <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>试用</span><spanlang=EN-US>PASCAL</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 style='margin-left:36.0pt;text-indent:-36.0pt;mso-list:l0 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>ABDCEFGH;</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>中序遍历次序为：</span><span lang=EN-US>DBAECFHG</span><spanstyle='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:l0 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></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:153.75pt; height:205.5pt'> <v:imagedata src="./上海交通大学数据结构1992.files/image001.gif" o:title="1"/></v:shape><![endif]--><![if !vml]><img width=205 height=274src="../school/image01.gif" v:shapes="_x0000_i1025"><![endif]></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>root</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>指向树根。每个结点的类型为：</span></p> <p class=MsoNormal><span lang=EN-US>type node=record data:integer;</span></p> <p class=MsoNormal><span lang=EN-US><span style='mso-tab-count:2'> </span><spanstyle="mso-spacerun: yes"> </span>left,right:pointer;</span></p> <p class=MsoNormal><span lang=EN-US><span style='mso-tab-count:2'> </span><spanstyle="mso-spacerun: yes"> </span>lfag,rflag:boolean</span></p> <p class=MsoNormal><span lang=EN-US><span style='mso-tab-count:1'> </span>end;</span></p> <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>其中，</span><spanlang=EN-US>left</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>和</span><spanlang=EN-US>right</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>分别为指向它的左右子树的指针，在存贮时已有值。试用</span><spanlang=EN-US>PASCAL</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 style='margin-left:36.0pt;text-indent:-36.0pt;mso-list:l1 level1 lfo4;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></p> <p class=MsoNormal style='margin-left:36.0pt;text-indent:-36.0pt;mso-list:l1 level1 lfo4;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></p> <p class=MsoNormal><span lang=EN-US><!--[if gte vml 1]><v:shape id="_x0000_i1026" type="#_x0000_t75" style='width:174.75pt;height:177pt'> <v:imagedata src="./上海交通大学数据结构1992.files/image002.gif" o:title="2"/></v:shape><![endif]--><![if !vml]><img width=233 height=236src="../school/image02.gif" v:shapes="_x0000_i1026"><![endif]><!--[if gte vml 1]><v:shape id="_x0000_i1027" type="#_x0000_t75" style='width:138.75pt;height:177pt'> <v:imagedata src="./上海交通大学数据结构1992.files/image003.gif" o:title="3"/></v:shape><![endif]--><![if !vml]><img width=185 height=236src="../school/image03.gif" v:shapes="_x0000_i1027"><![endif]></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></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></b><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>root</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>指向树根，结点的类型如下：</span></p> <p class=MsoNormal><span lang=EN-US>type pointer=node</span></p> <p class=MsoNormal><span lang=EN-US><span style='mso-tab-count:1'> </span>node=record key;integer;</span></p> <p class=MsoNormal><span lang=EN-US><span style='mso-tab-count:2'> </span>left,right:pointer</span></p> <p class=MsoNormal><span lang=EN-US><span style='mso-tab-count:1'> </span>end;</span></p> <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>试用</span><spanlang=EN-US>PASCAL</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>10</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><spanlang=EN-US>V1</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>）到其它各顶点的最短路程（</span><spanlang=EN-US>DIJKSTRA</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>算法），并且说明该算法是正确的。<br><br><br>※来源：<a href="http://edu.yesky.com/jinxiu/kaoyan">天极网考研 http://edu.yesky.com/jinxiu/kaoyan</font></a></p><p align=right>-<a href="javascript:window.close()"><font color="#000000">关闭窗口</font></a>-<font color="#ffffff">.....</font></p><br><br><DIV align=center><IFRAME frameBorder=0 height=60 marginHeight=0 marginWidth=0 scrolling=no src="../../ad2.htm" width=468 bordercolor="#000000"></IFRAME></DIV><br></td> </tr></table></center></div><div align=center><table width=100%><tr bgcolor=blue><td></td></tr><td class=unnamed1 width=1%></td><tr><td width=100%><p align=center><code><span style=font-size:9pt>© 2000 雅舍资讯 版权所有 转载请注明出处<br>All rights reserved</span></code></td></tr></table></div><div id="Layer01" style="position:absolute; left:14px; top:85px; width:100px; height:15px; z-index:5; background-color: #FFFFFF; layer-background-color: #FFFFFF; border: 1px none #FFFFFF;><font color="red"><font color=blue>当前在线</font></font><scriptsrc="http://61.139.59.105/mssoft/online/online.asp?id=yasee"></script><font color=blue>人</DIV></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -