中國海洋大學(xué)數(shù)據(jù)結(jié)構(gòu)試題

中國海洋大學(xué)2007-2008學(xué)年第2學(xué)期期末考試試卷信息學(xué)院《數(shù)據(jù)結(jié)構(gòu)》課程試題(A卷)優(yōu)選專業(yè)年級學(xué)號姓名授課教師座號----------------裝----------------訂----------------線----------------共4頁第1頁考試說明：本課程為閉卷考試，可攜帶文具(或本課程為開卷考試，可攜帶文具和資料)，滿分為：100分。題號一二三四五六七總分得分要求：算法描述用C語言，對算法中用到的數(shù)據(jù)結(jié)構(gòu)要加以說明描述。一、單項選擇題（在每個小題的四個備選答案中，只有一個答案是正確的，請將正確答案的號碼填在題干后的括號內(nèi)，每空2分，共20分）1.用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址（）A．必須是不連續(xù)的C．必須是連續(xù)的B．連續(xù)與否均可D．和頭結(jié)點的存儲地址相連續(xù)2.設(shè)計一個判別表達(dá)式中左、右括號是否配對的算法，采用數(shù)據(jù)結(jié)構(gòu)最佳。A．線性表的順序存儲結(jié)構(gòu)()B．棧C．隊列3.廣義表是A．?dāng)?shù)組C．隊列4.在一非空二叉樹的中序遍歷序列中，根節(jié)點右邊的部分A．只有右子樹上所有的結(jié)點D．線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的推廣。()B．線性表D．樹（）B．只有右子樹上的部分結(jié)點C．只有左子樹上的部分節(jié)點D．只有左子樹上的所有節(jié)點5.深度為5的二叉樹至多有個結(jié)點()A．16C．31B．32D．10授課教師命題教師或命題負(fù)責(zé)人簽字年月日院系負(fù)責(zé)人簽?zāi)暝氯兆种袊Ｑ蟠髮W(xué)2007-2008學(xué)年第2學(xué)期期末考試試卷2．下圖是帶權(quán)有向圖G的鄰接矩陣表示，給出按Floyd算法求所有頂點對之間的最短距離的矩陣變化過程（只要求距離變化矩陣序列）。V1V2V3V4V101∞4V2∞092V33508V4∞∞603.對于輸入關(guān)鍵字序列48，70，65，33，24，56，12，92，建立堆排序的初始堆（小頂堆），要求畫出主要過程。4.設(shè)有一組關(guān)鍵字｛22，41，53，46，30，13，01，67｝，采用哈希函數(shù)：H(key)=3*keyMOD11，表長為0..10。（1）用線性探查再散列法來構(gòu)造散列表。（2）并求在等查找概率下查找成功的平均長度。5.已知一棵二叉樹的前序序列和中序序列分別為ABCDEFGHIJ，中序序列為BCDAFEHJIG，試給出該二叉樹的后序序列并繪出該二叉樹對應(yīng)的森林。三、（10分）設(shè)二叉排序樹已經(jīng)以二叉鏈表的形式存儲，使用遞歸方法，求各結(jié)點的平衡因子并輸出。要求：①用文字寫出實現(xiàn)上述過程的基本思想；②寫出算法。6.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（）A．1/2C．2倍7具有6個頂點的無向連通圖至少應(yīng)該有B．1倍D．4倍條邊。()A．5C．78.下列排序算法中，算法B．6D．8在進(jìn)行一趟相應(yīng)的排序處理結(jié)束后不一定能選出一個元素放到其最終位置上。A．直選擇排序B．冒泡排序C．歸并排序()D．堆排序9.一組記錄的關(guān)鍵碼（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為A．38，40，46，56，79，84（）B．40，38，46，79，56，84C．40，38，46，56，79，84D．40，38，46，84，56，7910.當(dāng)在一個有序的順序表上查找一個數(shù)據(jù)時，既可用折半查找，也可用順序()B.在大部分情況下要慢D.在大部分情況下要快查找，但前者比后者的查找速度A．必定快C.取決于表遞增還是遞減二、解答下列各題（60分，每小題12分）1、某通訊系統(tǒng)只可能有A,B,C,D,E,F6種字符，其出現(xiàn)的頻率分別為，0.1，0.4，0.04，0.16，0.19，0.11，試畫出相應(yīng)的哈夫曼樹及其編碼。2．下圖是帶權(quán)有向圖G的鄰接矩陣表示，給出按Floyd算法求所有頂點對之間的最短距離的矩陣變化過程（只要求距離變化矩陣序列）。V1V2V3V4V101∞4V2∞092V33508V4∞∞603.對于輸入關(guān)鍵字序列48，70，65，33，24，56，12，92，建立堆排序的初始堆（小頂堆），要求畫出主要過程。4.設(shè)有一組關(guān)鍵字｛22，41，53，46，30，13，01，67｝，采用哈希函數(shù)：H(key)=3*keyMOD11，表長為0..10。（1）用線性探查再散列法來構(gòu)造散列表。（2）并求在等查找概率下查找成功的平均長度。5.已知一棵二叉樹的前序序列和中序序列分別為ABCDEFGHIJ，中序序列為BCD