📄 数据结构与程序设计1.htm
字号:
<html>
<head>
<title>中科院计算机技术研究所1999年硕士生入学试题 数据结构与程序设计___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>中科院计算机技术研究所1999年硕士生入学试题 数据结构与程序设计</strong></p><br><br><b>一、选择题 </b>(20 分 每空2分)<b><br> 1.___</b> 的遍历仍需要栈的支持。<br> 1.前序线索树 2.中序线索树 3.后序线索树</p> <p><b>2</b>.若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为___。<br> 1.n-1 2.[n/m]-1 3.[(n-1)/(m-1)] 4.[n/(m-1)]-1 5.[(n+1)/(m+1)]-1</p> <p><b>3</b>.最优二叉树(哈夫曼树)、最优查找树均为平均查找路径长度∑wh最小的树,其中对<br> 最优二叉树,n表示___,对最优查找树,n表示___; 构造这两种树均___。<br> 1.结点数 2.叶结点数 3.非叶结点数 4.度为二的结点数 5.需要一张n各关键字的有序<br> 表 6.需要对n个关键字进行动态插入 7.需要n个关键字的查找概率表 8.不许要任何前提</p> <p><b>4</b>.对于前序遍历与中序遍历结果相同的二叉树为___; 对于前序遍历与后序遍历结果相<br> 同的二叉树为___。<br> 1.一般二叉树 2.只有根结点的二叉树 3.根结点无左孩子的二叉树 4.根接点无右孩子的<br> 二叉树 5.所有结点只有左子树的二叉树 6所有结点只有右子树的二叉树</p> <p><b>5</b>.m路B+树是一棵___, 其结点中关键字最多为___个, 最少为___个。<br> 1.m路平衡查找树 2.m路平衡索引树 3.m路trie树 4.m路键树 5.m-1 6.m 7 m+1 8.[m/2]-1<br> 9.[m/2] 10.[m/2]+1</p> <p>二、<b>填空题</b>(10 分,每空一分)<br> <b>1</b>.对于给定的n个元素,可以构造出的逻辑结构有___,___,___,___四种。</p> <p><b>2</b>.具有n个关键字的B-树的查找路径长度不会大于___。</p> <p><b>3</b>.克鲁斯卡尔算法的时间复杂度为___, 他对___图较为适合。</p> <p><b>4.</b>深度为k(设根的层数为1)的完全二叉树至少有___个结点, 至多有___个结点, k和结点<br> 数n之间的关系是___。</p> <p>三、<b>问答题</b>(10 分,每题5分)</p> <p><b>1</b>.一棵非空的有向树中恰有一个顶点入度为0，其他顶点入度为1.但一个恰有一个顶点<br> 的入度为0， 其他顶点入度为一的有向图却不一定是一棵有向树。请举例说明之。</p> <p><b>2</b>.若有n个元素以构成一个小根堆，那么如果增加一个元素为K(n+1)，请用文字简要 说<br> 明你如何在log2(n) 的时间内将其重新调整为一个堆？</p> <p>四、<b>阅读下述程序,指出程序的输出。</b>(10 分)</p> <pre>void g(int**);main(){ int line[100],i; int *p=line; for(i=0;i<100;i++){ *p=i; g(&p); } for(i=0;i<100;I++)printf("%d\n",line[i]);}void g(int**p){ (**p)++; (*p)++;}</pre> <p>五、<b>编程题。</b>(共50分,要求写出设计思想和程序注解)</p> <p>1.设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法, 将<br> 此链表的记录按照key递增的次序进行就地排序.(10分)</p> <p>2.给定一个整数数组b[0..N-1], b中连续相等元素构成的子序列称为平台.试设计算法,求出<br> b中最长平台的长度.(20分)</p> <p>3.自由树(即无环连通图) T=(V,E)的直径是树中所有点对间最短路径长度的最大值,即T的<br> 直径定义为MAX d(u,v) 这里d(u,v)表示顶点u 到顶点v的最短路径长度(路径长度为路径中<br> 所含的边数).试写一算法求T的直径,并分析算法的时间复杂度(时间复杂度越小得分越高)<br> (20分)</p> <p>九、(14分)设正在处理器上执行的一个进程的页表如下.页表的虚页号和物理块号是十进<br> 制数,起始页号(块号)均为0.所有的地址均是存储器字节地址,页的大小为1024字节.</p> <p>A.详述在设有快表的请求分页存储管理系统中,一个虚地址转换成物理内存地址的过程.</p> <p>B.下列虚地址对应与什么物理地址: (1)5499; (2) 2221;</p> <table width="70%" border="1"> <tr> <td><font color="#0000ff">虚页号</font></td> <td><font color="0000ff">状态位</font></td> <td><font color="#0000FF">访问位</font></td> <td><font color="#0000FF">修改位</font></td> <td><font color="#0000FF">物理块号</font></td> </tr> <tr> <td height="22"><font color="#0000FF">0</font></td> <td height="22"><font color="0000ff">1</font></td> <td height="22"><font color="#0000FF">1</font></td> <td height="22"><font color="#0000FF">0</font></td> <td height="22"><font color="#0000FF">4</font></td> </tr> <tr> <td><font color="#0000FF">1</font></td> <td><font color="#0000FF">1</font></td> <td><font color="#0000FF">1</font></td> <td><font color="#0000FF">1</font></td> <td><font color="#0000FF">7</font></td> </tr> <tr> <td><font color="#0000FF">2</font></td> <td><font color="#0000FF">0</font></td> <td><font color="#0000FF">0</font></td> <td><font color="#0000FF">0</font></td> <td><font color="#0000FF">---</font></td> </tr> <tr> <td><font color="#0000FF">3</font></td> <td><font color="#0000FF">1</font></td> <td><font color="#0000FF">0</font></td> <td><font color="#0000FF">0</font></td> <td><font color="#0000FF">2</font></td> </tr> <tr> <td><font color="#0000FF">4</font></td> <td><font color="#0000FF">0</font></td> <td><font color="#0000FF">0</font></td> <td><font color="#0000FF">0</font></td> <td><font color="#0000FF">---</font></td> </tr> <tr> <td><font color="#0000FF">5</font></td> <td><font color="#0000FF">1</font></td> <td><font color="#0000FF">0</font></td> <td><font color="#0000FF">1</font></td> <td><font color="#0000FF">0</font></td> </tr> </table> <p>注释:访问位---当某页被访问时,其访问位被置为1.<br><br><a href=1999gong004a.htm target=_blank><font color=red><b>数据结构与程序设计 参考答案</b></font></a><br><br><br>※试卷提供：王敏<br>※来源：<a href=http://edu.yesky.com/jxzl/kaoyan/kaoyan.htm>天极网考研</a> http://edu.yesky.com/jxzl/kaoyan/kaoyan.htm</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><script
src="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 + -