?? 數(shù)據(jù)結構與程序設計3.htm
字號:
<html>
<head>
<title>中科院計算機技術研究所1998年碩士生入學試題 數(shù)據(jù)結構和程序設計___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>中科院計算機技術研究所1998年碩士生入學試題 數(shù)據(jù)結構和程序設計</strong></p><br><br>要求：算法題目寫注解<br> <br> 一.填空(15分,每空一分)<br> 1.用循環(huán)鏈表表示的隊列長度為n,若只設頭指針,則出隊和入隊的時間復雜度分別是__和__; 若只設尾指針,則出隊和入隊的時間復雜度分別是__和__.<br> 2.設廣義表L=( (),() ) ,則head(L)是___;tail(L)是___;L的長度是___;深度是___.<br> 3.深度為h的完全二叉樹至少有__個結點;至多有__個結點;h和結點總數(shù)n之間的關系是__.<br> 4.在n個記錄的有序順序表中進行折半查找,最大的比較次數(shù)是___.<br> 5.在一棵m階B+樹中,若在某結點中插入一個新關鍵字而引起該結點分裂,則此結點中原有的關鍵字的個數(shù)是___.<br> 6.n個頂點的連通圖用鄰接矩陣表示時,該矩陣至少有__個非零元素.<br> <br> 二.請在下列各題中選擇一個正確的答案(20分 ,每題2分)<br> 1.算法的時間復雜度取決于<br> a.問題的規(guī)模<br> b.待處理數(shù)據(jù)的初態(tài)<br> c.both a and b<br> <br> 2.消除遞歸不一定需要使用棧,此說法<br> a.true<br> b.false<br> <br> 3.假定有k個關鍵字互為同義詞,若用線性探測法把這k個關鍵字存入散列表中,至少要進行多少次探測?<br> a.k-1<br> b.k<br> c.k=1<br> d.k(k+1)/2<br> <br> 4.若需要在O(nlog2(n))的時間內完成對數(shù)組的排序,且要求排序是穩(wěn)定的,則可選擇的排序方法是:<br> a.快速排序 b.堆排序 c.歸并排序 d.直接插入排序<br> <br> 5.用ISAM和VSAM組織文件屬于:<br> a.順序文件<br> b.索引文件<br> c.散列文件<br> <br> 6.若一個有向圖的鄰接矩陣中,主對角線以下的元素均為零,則該圖的拓撲有序序列<br> a.存在<br> b.不存在<br> <br> 7.將兩個各有n個元素的有序表歸并成一個有序表,其最少的比較次數(shù)是<br> a.n<br> b.2n-1<br> c.2n<br> d.n-1<br> <br> 8下述二叉樹中,那一種滿足性質:從任意結點出發(fā)到根的路徑上所經(jīng)過的結點序列<br> 按其關鍵字有序:<br> a.二叉排序樹<br> b.哈夫曼樹<br> c.AVL樹<br> d.堆<br> <br> 9.以知待排序的n個元素可分為n/k個組,每個組包含k個元素,且任一組內的個元素均分別大于前一組內的所有元素和小于后一組內的所有元素,若采用基于比較的排序,其時間下限應為:<br> a.O(klog2(k)) <br> b.O(klog2(n))<br> c.O(nlog2(k))<br> d.O(nlog2(n))<br> <br> 10.在葉子數(shù)目和權值相同的所有二叉樹中,最優(yōu)二叉樹定是完全二叉樹,該說法:<br> a.正確<br> b.錯誤<br> <br> 三.設二叉排序樹T中各結點關鍵字互不相同,x^是T的葉子,y^是x^的雙親.證明y^.key是T中大于x^.key的所有關鍵字中的最小者,或是小于x^.key的所有關鍵字的最大者.(10分)<br> <br> 四.(共15分)設數(shù)組A的長度為2N,前N個元素A[1..N]遞減有序,后N個元素A[N+1..2N]遞增有序,且2N是2的整數(shù)次冪,即k=log2(2N) 為整數(shù).例如A[1..8]=[90,85,50,10,30,65,80,100] 滿足上述要求,這里N=4,k=3,A的前4個元素和后4個元素分別遞減和遞增有序.用次例調用如下的Demo過程,并要求:<br> (1).給出for循環(huán)中每次執(zhí)行 PerfectShuffle(A,N)和CompareExchange(A,N)的結果.(10分)<br> (2)解釋Demo的功能.(2分)<br> (3)給出Demo的時間復雜度.(3分)<br> Procedure PerfectShuffle (Var A:arraytype; N:integer){<br> i:=1; j:=1;<br> while i<=N do {<br> B[j]:=A[i];<br> B[j+1]:=A[i+N];<br> i:=i+1;<br> j:=j+2;<br> }<br> A[1..2N]:=B[1..2N];//B copy to A<br> }<br> <br> Procedure CompareExchange(Var A:arraytype; N:integer){<br> j:=1;<br> while j<2N do{<br> if A[j]>A[j+1] then<br> A[j]<->A[j+1];//exchange A[j] and A[j+1]<br> j:=j+2;<br> }<br> }<br> <br> Procedure Demo(Var A:arraytype; N:integer){<br> //the length of A is 2N,k=log2(N) is integer<br> for i:=1 to log2(2N) do <br> {PerfectShuffle(A,N);<br> CompareExchange(A,N);<br> }<br> }<br> <br> 五.(共20分)<br> (1).設二叉排序中關鍵字由1至1000的整數(shù)構成,現(xiàn)要檢索關鍵字為363的結點,下述關鍵字序列中那些可能是二叉排序樹上搜索到的序列,那些不可能是二叉排序樹上搜索到的序列?(5分)<br> (a)2,252,401,393,330,344,397,363<br> (b)924,220,911,244,898,258,362,363<br> (c)925,202,911,240,912,245,363<br> (d)2,399,387,219,266,382,381,278,363<br> (2).通過對(1)的分析,寫一個算法判定給定的關鍵字序列(假定關鍵字互不相同)是否可能是二叉排序樹的搜索序列.若可能是返回真,否則返回假.可假定被判定的序列已存入數(shù)組中.(15分)<br> <br> 六.(共20分)圖的D-搜索類似于BFS,不同之處在于使用棧代替BFS中的隊列,入出隊列的操作改為入出棧的操作.即當一個頂點的所有鄰接點被搜索后,下一個搜索的出發(fā)點應該是最近入棧(棧頂)的頂點.<br> (1)用鄰接表做存儲結構,寫一個D-搜索算法(15分)<br> (2)用 D-搜索方法搜索右圖,設初始出發(fā)點為1,寫出頂點的訪問次序和響應的生成樹,<br> 當從某頂點出發(fā)搜索他的鄰接點是，請按鄰接點序號遞增序搜索,以使答案唯一.(5分) <br> <img src="1998gong003.gif" width="100" height="120"><br><br><br>※試卷提供：王敏<br>※來源：<a href=http://edu.yesky.com/jxzl/kaoyan/kaoyan.htm>天極網(wǎng)考研</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 + -