2011秋算法與數(shù)據(jù)結(jié)構(gòu)試卷A

石家莊鐵道大學(xué)2011-2012學(xué)年第1學(xué)期2010級本科期末考試試卷（A）課程名稱：算法與數(shù)據(jù)結(jié)構(gòu) 仟課教師考試時(shí)間：分鐘學(xué)號：姓名：班級：考試性質(zhì)（學(xué)生填寫）：正?？荚嚕ǎ┚徔迹ǎ┭a(bǔ)考（）重修（）提前修讀（）題號一二三四五六七總分滿分206020100得分閱卷人、單項(xiàng)選擇題（每小題2分，共20分）數(shù)據(jù)結(jié)構(gòu)從邏輯上分為（）。B.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)DB.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D.線性結(jié)構(gòu)和非線性結(jié)構(gòu)B.都是后進(jìn)先出D.沒有共同點(diǎn)C.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)棧和隊(duì)列的共同點(diǎn)是（）。A.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素在一個(gè)單鏈表中，若q結(jié)點(diǎn)是p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q與p之間插入結(jié)點(diǎn)s,則執(zhí)行（）。A.s—link=pTlink；p—link=s； B.p—link=s；s—link=q；C.p—link=s—link；s—link=p； D.q—link=s；s—link=p；在數(shù)組A8x10中，行列下標(biāo)從0開始，每一個(gè)數(shù)組元素占用3個(gè)字節(jié)存儲，所有數(shù)據(jù)元素相繼存放在一個(gè)地址連續(xù)的存儲空間中，則存放該數(shù)組至少需要的字節(jié)數(shù)是（）。A.240 B.100 C.80D.270中綴表達(dá)式A*（B+C）/（D-E+F）的后綴表達(dá)式為（ ）。A.A*B+C/D-E+F B.AB*C+D/E-F+C.ABC+*DE-F+/ D.ABCDEF*+/-+將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根開始，每層從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)編號為1，則編號最大的非葉子結(jié)點(diǎn)的編號為（）。A.48 B.49C.50 D.51已知一個(gè)有向圖的鄰接矩陣表示，要?jiǎng)h除所有從第i個(gè)結(jié)點(diǎn)發(fā)出的邊，應(yīng)該（ ）。A.將鄰接矩陣的第i行刪除 B.將鄰接矩陣的第i行元素全部置為0C.將鄰接矩陣的第i列刪除 D.將鄰接矩陣的第i列元素全部置為0對線性表進(jìn)行折半搜索時(shí)，要求線性表必須( )。A.以數(shù)組的方式存儲且結(jié)點(diǎn)按關(guān)鍵碼有序排列 B.以數(shù)組方式存儲C.以鏈接的方式存儲且結(jié)點(diǎn)按關(guān)鍵碼有序排列 D.以鏈接方式存儲如果某二叉樹的先根次序遍歷結(jié)果為stuwv,中序遍歷為uwtvs，那么該二叉樹的后序?yàn)?)。A.uwvts B.vwutsC.wuvtsD.wutsv不可能生成圖所1-1示的二叉排序樹的關(guān)鍵字序列為( )。A.42135B.45213C.45123D.42531)圖1-1二、簡答題(共60分)設(shè)一組關(guān)鍵字為(7,15,20,31,48,53,64,19,82,91),Hash函數(shù)H(key)=keyMOD11,Hash表表長m=11，用線性探測法解決沖突，試構(gòu)造Hash表。(10分)并：(1)給出構(gòu)造過程(2)求出平均查找長度ASL某子系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，其出現(xiàn)的概率分別為0.06,0.28.0.07,0.08,0.14,0.23,0.03,0.11。(10分)請：(1)畫出赫夫曼樹設(shè)計(jì)赫夫曼編碼計(jì)算其帶權(quán)路徑長度WPL已知一個(gè)圖的頂點(diǎn)集V和邊集G如下：V={0,1,2,3,4,5,6,7,8,9}；E={(0,1),(0, 4), (1,2),(1,7),(2,8),(3, 4),(3,8), (5,6), (5,8),(5,9),(6,7), (7, 8),(8,9)}。(12分)請：(1)畫出此圖給出此圖的鄰接表寫出從頂點(diǎn)0出發(fā)的深度優(yōu)先搜索遍歷的頂點(diǎn)序列寫出從頂點(diǎn)0出發(fā)的廣度優(yōu)先搜索遍歷的頂點(diǎn)序列如圖2-1所示(8分)請：(1)給出圖2-1所示的二叉樹的中序遍歷序列給出圖2-1所示的二叉樹的后序遍歷序列畫出與圖2-1所示的二叉樹對應(yīng)的森林>4G 圖1/^已知有一個(gè)數(shù)據(jù)表為{30,18,20,15,38,12,44,53,46,18*,26,86},請給出進(jìn)行2路歸并排序的過程中每一趟排序后的數(shù)據(jù)表變化。（說明：從小到大排序）（8分）已知長度為10的表（xal,wan,wil,zol,yo,xul,yum,wam,wim,zr）,按表中元素順序依次插入一棵初始為空的平衡二叉排序樹，請畫出每插入一個(gè)結(jié)點(diǎn)完成后的平衡二叉排序樹，若做了某種旋轉(zhuǎn)，給出旋轉(zhuǎn)類型。（12分）三、算法分析與設(shè)計(jì)（每小題10分，共20分）說明：用類C語言編寫算法；對算法中使用