哈爾濱工程大學(xué)考研數(shù)據(jù)結(jié)構(gòu)真題9

1、班級： 學(xué)號(hào)： 姓名： 裝 訂 線哈爾濱工程大學(xué)試卷考試科目: 數(shù)據(jù)結(jié)構(gòu)a 卷 題號(hào)一二三四五總分分?jǐn)?shù)評卷人一、 單項(xiàng)選擇題（每空1分，共15分）1.以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（ ）a廣義表b二叉樹c稀疏矩陣d串2.有六個(gè)元素按6，5，4，3，2，1 的順序進(jìn)棧，下列哪一個(gè)是合法的出棧序列？（ ）a6 4 2 5 3 1b4 5 1 3 2 6 c3 4 6 5 2 1d4 3 1 2 5 63.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)單元的地址（ ）。a一定連續(xù)b一定不連續(xù)c不一定連續(xù)d部分連續(xù)，部分不連續(xù)4.對于棧，操作數(shù)據(jù)的原則是（ ）。a先進(jìn)先出b不分順序c后進(jìn)后出d后進(jìn)先出5、有一個(gè)二維數(shù)組a1:

2、6，0:7 ，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址，若按列存儲(chǔ)，則a5，7的第一個(gè)字節(jié)的地址是（ ）。a42b276c282d2346、廣義表（a,(b,c),d,e）的表頭是（ ）。aaba,（b, c）c（a, （b, c）d（a）7、算術(shù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（ ）。aab+cde/*babcde/+*+cabcde/*+dabcde*/+8、一棵二叉樹高度為h，所有結(jié)點(diǎn)的度或?yàn)?或?yàn)?，則這棵二叉樹最少有( )個(gè)結(jié)點(diǎn)。a2hb2h-1c2h+1dh+19、對二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩

3、子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用( )次序的遍歷實(shí)現(xiàn)編號(hào)。a先序b中序c后序d按層次遍歷10、一棵二叉樹的先序遍歷序列為abcdefg，它的中序遍歷序列可能是（ ）。acabdefgbabcdefgcdacefbgdadbcfeg 11、一棵有n個(gè)結(jié)點(diǎn)的二叉樹，按層次從上到下，同一層從左到右順序存儲(chǔ)在一維數(shù)組a1.n中，則二叉樹中第i個(gè)結(jié)點(diǎn)（i從1開始用上述方法編號(hào)）的右孩子在數(shù)組a中的位置是（ ）aa2i(2i<=n)ba2i+1(2i+1<=n)cai-2d條件不充分，無法確定12、一個(gè)n個(gè)頂點(diǎn)的連通無向圖，其邊的個(gè)數(shù)至少為（ ）。an-1bncn+1dnlogn

4、13、下列關(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ì)提前完成14、下面關(guān)于折半查找的敘述正確的是( )。a表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ)c表必須有序，而且只能從小到大排列b表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型 d表必須有序，且表只能以順序方式存儲(chǔ)15、在下列排序算法中，（ ）算法的時(shí)間復(fù)雜度與初始排序無關(guān)。a直接插入排序b起泡排序c快速排序d直接選擇排序二、 判斷題（每空1分，共10

5、分）1、數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系，它依賴于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu)。( ) 2、對任何數(shù)據(jù)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。( )3、棧與隊(duì)列是一種特殊操作的線性表。( )4、若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表。( )5、二叉樹是度為2的有序樹。( )6、非空的二叉樹一定滿足：某結(jié)點(diǎn)若有左孩子，則其中序前驅(qū)一定沒有右孩子。( )7、一棵哈夫曼樹的帶權(quán)路徑長度等于其中所有分支結(jié)點(diǎn)的權(quán)值之和。( )8、一個(gè)網(wǎng)（帶權(quán)圖）都有唯一的最小生成樹。( )9、就平均查找長度而言，分塊查找最小，折半查找次之，順序查找最大。( )10、快速排序和歸并排序在最壞情況下的比較次數(shù)都是o(nl

6、og2n)。( )三、 填空題（每空1分，共10分）1、已知指針p指向單鏈表l中的某結(jié)點(diǎn)，則刪除其后繼結(jié)點(diǎn)的語句是：_。2、循環(huán)隊(duì)列用數(shù)組a0.m-1存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列的元素個(gè)數(shù)是_。3、兩個(gè)字符串相等的充分必要條件是_。4、設(shè)二維數(shù)組a0.30,1.20，每個(gè)元素占有4 個(gè)存儲(chǔ)單元，存儲(chǔ)起始地址為200。如按行優(yōu)先順序存儲(chǔ)，則元素 a25,18的存儲(chǔ)地址為_。5、若a=1，b=2，c=3，d=4，則后綴式db/cc*a-b*+的運(yùn)算結(jié)果為_。6、設(shè)只含根結(jié)點(diǎn)的二叉樹的高度為0，則高度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為_。7、g是一個(gè)非連通無向圖，共有2

7、8條邊，則該圖至少有_個(gè)頂點(diǎn)。8、在有序表a1.12中，采用二分查找算法查等于a5的元素，所比較的元素下標(biāo)依次為_。9、一棵4階4層（根為第一層，葉子為第四層）的b-樹，最多有個(gè)_關(guān)鍵字。10、快速排序法在_情況下最不利于發(fā)揮其長處。四、 應(yīng)用題（每題7分，共35分）1、設(shè)有正文aadbaacaccdacacaad，字符集為a,b,c,d，設(shè)計(jì)一套二進(jìn)制編碼，使得上述正文的編碼最短。要求：畫出其哈夫曼樹并給出字符的編碼。2、已知一棵二叉樹的先序、中序和后序序列如下，其中空缺了部分，請畫出該二叉樹。先序：_ b c _ e f g _ i j k _中序：c b e d _ g a j _ h

8、_ l后序：_ e _ f d _ j _ l _ h a3、已知一個(gè)無向圖如下圖所示，要求用kruskal算法生成最小樹（假設(shè)以為起點(diǎn)，試畫出構(gòu)造過程）。4、設(shè)哈希函數(shù)h（k）=3*k mod 11，散列地址空間為010，對關(guān)鍵字序列（32,13,49,24,38,21,4,12）按線性探測再散列處理沖突的方法構(gòu)造哈希表，并求出等概率下查找成功時(shí)的平均查找長度asl。5、判斷序列（22，85，40，77，80，60，66，98，82，10，20）是否是大頂堆，若不是，寫出建堆的過程。五、算法設(shè)計(jì)題（每題15分，共30分）1、假設(shè)有兩個(gè)按元素值遞增次序排列的線性表，均以單鏈表形式存儲(chǔ)。請編寫算法將這兩個(gè)單鏈表歸并為一個(gè)按元素值遞減次序排列的單鏈表，并要求利用原來兩個(gè)單鏈表的結(jié)點(diǎn)存放歸