2015年南京郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)初試真題

2015年南京郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)考研初試題目判斷題（共15題*2分）1.消除遞歸不一定需要使用棧，此說法()2.稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能()3.完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是葉結(jié)點(diǎn)()4.連通分量是無向圖的極大強(qiáng)連通子圖()5.在9階B-樹中，除葉子以外的任意結(jié)點(diǎn)的分支數(shù)介于5和9之間()6.在平衡二叉樹中，向某個(gè)平衡因子不為零的結(jié)點(diǎn)的樹中插入一新結(jié)點(diǎn)，必引起平衡旋轉(zhuǎn)()7.10個(gè)葉子結(jié)點(diǎn)的哈弗曼樹，其高度最小為58.隊(duì)列和棧不可以使用散列存儲(chǔ)()選擇題（共15題*2分）1.以下屬于邏輯結(jié)構(gòu)的是（）。A．順序表B.哈希表C.有序表D.單鏈表2.下列數(shù)據(jù)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)。A．棧B.隊(duì)列C.完全二叉樹D.堆3.某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（）儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A．單鏈表B．僅有頭指針的單循環(huán)鏈表C．雙鏈表D．僅有尾指針的單循環(huán)鏈表4.循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，則入隊(duì)時(shí)的操作為（）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)5.二叉樹在線索后，仍不能有效求解的問題是（）。A.先序線索二叉樹中求先序后繼B．中序線索二叉樹中求中序后繼C．中序線索二叉樹中求中序前驅(qū)D．后序線索二叉樹中求后序后繼6.下面幾個(gè)符號串編碼集合中，不是前綴編碼的是（）。A．{0,10,110,1111}B．{11,10,001,101,0001}C．{00,010,0110,1000}D．{b,c,aa,ac,aba,abb,abc}7.用有向無環(huán)圖描述表達(dá)式(A+B)*（（A+B）/A），至少需要頂點(diǎn)的數(shù)目為()。A．5B．6C．8D．98.下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（）。A．關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B．任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成C．所有的關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成D．某些關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成9.m階B-樹是一棵()A.m叉排序樹B.m叉平衡排序樹C.m-1叉平衡排序樹D.m+1叉平衡排序樹10.關(guān)于雜湊查找說法不正確的有幾個(gè)()【南京理工大學(xué)2000一、16（1.5分）】A.采用鏈地址法解決沖突時(shí)，查找一個(gè)元素的時(shí)間是相同的B.采用鏈地址法解決沖突時(shí)，若插入規(guī)定總是在鏈?zhǔn)?，則插入任一個(gè)元素的時(shí)間是相同的C.用鏈地址法解決沖不易引起聚集現(xiàn)象D.再哈希法不易產(chǎn)生聚集11.在下列排序算法中,哪一個(gè)算法一趟不能確定一個(gè)元素的最終位置（）。A．直接插入B.冒泡排序C.快速排序D.簡單選擇排序簡答題（共5題*10分）1.舉例說明順序隊(duì)的“假溢出”現(xiàn)象，并給出解決方案2.什么是算法?算法有哪些特征?在程序設(shè)計(jì)算法中引入“程序步”，是不是"程序步"越少執(zhí)行效率越高?3.設(shè)T是具有n個(gè)內(nèi)結(jié)點(diǎn)的擴(kuò)充二叉樹，I是它的內(nèi)路徑長度，E是它的外路徑長度。（1）試?yán)脷w納法證明E=I+2n,n>=0.（2）利用（1）的結(jié)果試說明：成功查找的平均比較次數(shù)s與不成功查找的平均比較次數(shù)u之間的關(guān)系可用公式表示s=(1+1/n)u-1,n>=1。4.一個(gè)圖有0,1,2,3,4,5共6個(gè)結(jié)點(diǎn),插入邊(1,0)(1,3)(2,1)(2,3)(3,0)(3,2)(3,4)(4,1)(4,5)（1）畫出對應(yīng)的鄰接矩陣（2）寫出所有強(qiáng)連通分量5.試畫出從空樹開始，由字符序列(t,d,e,s,u,g,b,j,a,k)構(gòu)成的二叉平衡樹，并為每一次的平衡處理指明旋轉(zhuǎn)類型。再次插入字符a，畫出此時(shí)的平衡二叉樹編程題（共4題*10分）1.實(shí)現(xiàn)利用隊(duì)列將棧中元素逆置并說明算法2.已知無向圖采用鄰接表存儲(chǔ)方式，試寫出刪除邊（i，j）的算法。3.有線性表(a1,a2,…,an),采用單鏈表存儲(chǔ)，頭指針為H，每個(gè)結(jié)點(diǎn)中存放線性表中一個(gè)元素，現(xiàn)查找某個(gè)元素值等于X的結(jié)點(diǎn)。分別寫出下面三種情況的查找語句。要求時(shí)間盡量少。