1、姓名：報考專業(yè)：準(zhǔn)考證號碼：密封線內(nèi)不要寫題二O 一四年招收碩士研究生入學(xué)考試試題考試科目代碼及科目名稱：856 數(shù)據(jù)結(jié)構(gòu)(C語言版)答題內(nèi)容寫在答題紙上，寫在試卷或草稿紙上一律無效考完后試題隨答題紙交回?？荚嚂r間3小時，總分值 150 分。一、選擇題（10小題，每題2分，共20分）1. 算法分析的主要內(nèi)容是（ ）。A）正確性 B）可讀性和穩(wěn)定性 C）簡單性 D）空間復(fù)雜性和時間復(fù)雜性2. 線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（ ）。A）必須是連續(xù)的 B）部分地址必須是連續(xù)的C）一定是不連續(xù)的 D）連續(xù)或不連續(xù)都可以3. 設(shè)有6個元素按1、2、3、4、5、6的順序進棧，下列

2、不合法的出棧序列是（ ）。A）234165 B）324651 C）431256 D）5463214. 設(shè)有二維數(shù)組A1.12,1.10，其每個元素占4個字節(jié)，數(shù)據(jù)按行優(yōu)先順序存儲，第一個元素的存儲地址為100，那么元素A5,5的存儲地址為（ ）。A）76 B）176 C）276 D）3765. 已知一棵二叉樹的先序序列為ABDGCFK，中序序列為DGBAFCK，則后序序列為（ ）。A）ACFKDBG B）GDBFKCA C）KCFAGDB D）ABCDFKG6. 在二叉樹結(jié)點的先序，中序和后序序列中，所有葉子結(jié)點的先后順序（ ）。A）都不相同 B）完全相同C）先序和中序相同，而與后序不同 D）

3、中序和后序相同，而與先序不同7. 圖的深度優(yōu)先遍歷類似于二叉樹的（ ）。A）先序遍歷 B）中序遍歷 C）后序遍歷 D）層次遍歷8. 下面（ ）算法適合構(gòu)造一個稠密圖G的最小生成樹。A） Prim算法 B）Kruskal算法 C）Floyd算法 D）Dijkstra算法9. 對關(guān)鍵碼46,79,56,38,40,84采用堆排序,則初始化堆(小堆)后最后一個元素是（ ）。A）84 B）46 C）56 D）3810.在Hash函數(shù)H(k)=k MOD m中，一般來講m應(yīng)?。?）。A）奇數(shù) B）偶數(shù) C）素數(shù) D）充分大的數(shù)二、填空題（10小題，每題2分，共20分）1. 在單向鏈表某P結(jié)點之后插入S結(jié)

4、點的操作是（ ）。2. 線性表用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是（ ）。3. 一個棧的輸入序列是：1，2，3則不可能的棧輸出序列是（ ）。4. 一棵二叉樹高度為h,所有結(jié)點的度或為0，或為2，則該二叉樹最少有（ ）結(jié)點。5. 在完全二叉樹中，編號為i和j的兩個結(jié)點處于同一層的條件是（ ）。6. 若無向圖G=（V,E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)，現(xiàn)采用圖的（ ）遍歷方法從頂點a開始遍歷圖，得到的序列為abecd。7. 求最短路徑的Dijkstra算法的時間復(fù)雜度為（ ）。8. 假定有

5、k個關(guān)鍵字互為同義詞，若用線性探測再散列法把這k個關(guān)鍵字存入散列表中，至少要進行（ ）次探測。9. 設(shè)在已排序的線性表中共有元素n個，若用二分法查找表中的元素。若查找成功，至少要比較（ ）次10.對一組記錄（54,38,96,23,15,2,60,45,83）進行直接插入排序，當(dāng)把第7個記錄60插入到有序表時，為尋找插入位置需比較（ ）次。三、綜合應(yīng)用題（7小題，每題10分，共70分）1. 已知A1.N是一棵順序存儲的完全二叉樹，如何求出Ai和Aj的最近的共同祖先？2. 請給出一棵哈夫曼樹中分支數(shù)B與葉子節(jié)點數(shù)n0所滿足關(guān)系式，并證明你的結(jié)論。3. 下面的排序算法的思想是：第一趟比較將最小的元

6、素放在r0中，最大的元素放在rn-1中，第二趟比較將次小的放在r1中，將次大的放在rn-2中，,依次下去，直到待排序列為遞增序。（注：<-> 代表兩個變量的數(shù)據(jù)交換）。void sort(SqList &r,int n) i=0;while( (1) ) min=max=i; for (j=i+1; (2) ;+j) if( (3) ) min=j; else if(rj.key>rmax.key) max=j; if( (4) ) rmin<->ri; if(max!=n-i-1) if( (5) ) rmin<->rn-i-1; else

7、rmax<->rn-i-1; i+;/sort4. 如下圖所示的AOE網(wǎng)（1）寫出所有的拓撲序列（2）求各頂點代表的事件的最早發(fā)生時間和最遲發(fā)生時間（3）求各條弧代表的活動的最早開始時間和最遲開始時間（4）給出其關(guān)鍵路徑5. 設(shè)哈希函數(shù)H（K）=3 K mod 11，哈希地址空間為010，對關(guān)鍵字序列（32，13，49，24，38，21，4，10），按下述兩種解決沖突的方法構(gòu)造哈希表，并分別求出等概率下查找成功時和查找失敗時的平均查找長度ASLsucc和ASLunsucc。（1）線性探測法 （2）鏈地址法6. 全國有10000人參加競賽，只錄取成績優(yōu)異的前10名，并將他們從高分到低

8、分輸出。而對落選的其他考生，不需排出名次，問此種情況下，用何種排序方法速度最快？為什么？7. 假定對有序表(3,4,5,17,24,35,40,54,58,72,80,123)進行折半查找，試回答問題：（1）畫出描述折半查找過程的判定樹；（2）若查找元素54，需依次與那些元素比較?（3）若查找元素20，需依次與那些元素比較?（4）分別求等概率情況下查找成功和不成功時的平均查找長度。四、算法設(shè)計與編程（4小題，每題10分，共40分）1. 設(shè)有一頭指針為L的帶有表頭結(jié)點的非循環(huán)雙向鏈表，其每個結(jié)點中除有pred（前驅(qū)指針），data（數(shù)據(jù)）和next（后繼指針）域外，還有一個訪問頻度域freq。在鏈表被啟用前，其值均初始化為零。每當(dāng)在鏈表中進行一次Locate(L,x)運算時，令元素值為x的結(jié)點中freq域的值增1，并使此鏈表中結(jié)點保持按訪問頻度非增（遞減）的順序排列，同時最近訪問的結(jié)點排在頻度相同的結(jié)點的最后，以便使頻繁訪問的結(jié)點總是靠近表頭。試編寫符合上述要求的Locate(L,x)運算的算法，該運算為函數(shù)過程，返回找到結(jié)點的地址，類型為指針型。2. 已知二叉樹用下面的順序存儲結(jié)構(gòu)，寫出先序遍歷該二叉樹的算法。123456789 data ABCDEFGHI Lc240008000 Rc3560790003. 編寫在后序線索二叉樹中求任一結(jié)點直接前驅(qū)的算法（結(jié)點結(jié)構(gòu)包括數(shù)據(jù)