中南大學(xué)20102011學(xué)年一學(xué)期《數(shù)據(jù)結(jié)構(gòu)》考試試卷

中南大學(xué)考試一試卷2010 --2011 學(xué)年一學(xué)期 時(shí)間100 分鐘數(shù)據(jù)結(jié)構(gòu) 課程48 學(xué)時(shí)2學(xué)分考試形式： 閉卷專業(yè)年級(jí)： 信息、通訊09 總分100 分，占總評(píng)成績(jī) 70%注：此頁(yè)不作答題紙，請(qǐng)將答案寫在答題紙上，考試時(shí)間 2011 年01月12號(hào)印刷不清楚時(shí)請(qǐng)發(fā)問，思疑題目有錯(cuò)誤請(qǐng)直接在答題紙上指出并說明。一、填空題( 每題2分，共20 分)1、在單鏈表p結(jié)點(diǎn)以后插入s結(jié)點(diǎn)的操作是： _ ； 。2、一個(gè)棧的輸入序列是：3、一棵深度為k 且有

1，2，3則不行能的棧輸出序列是 個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。4、已知二叉樹有 50個(gè)葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)起碼是 。5、廣義表(a,(a,b),d,e,((i,j),k))6n個(gè)極點(diǎn)的無向圖最多有

的長(zhǎng)度是__ 條邊。

，深度_ 。7、對(duì)廣義表A=(x,((a,b),c,d)) 作運(yùn)算head(head(tail(A))) 后的結(jié)果 。8、用某種排序方法對(duì)重點(diǎn)字序列（ 25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化狀況以下：20 ，15，21，25，47，27，68，35，8415 ，20，21，25，35，27，47，68，8415 ，20，21，25，27，35，47，68，84則所采納的排序方法是 。9、將兩個(gè)或兩個(gè)以上的有序表歸并成一個(gè)新的有序表采納 排序算法較好。10、設(shè)數(shù)組Data[0..m] 作為循環(huán)行列SQ的儲(chǔ)存空間，front 為隊(duì)頭指針，rear 為隊(duì)尾指針，則履行出隊(duì)操作的語(yǔ)句為 。二、問答及運(yùn)算題（第 1、4題各10分，第2、3題各5分，共30分）1AOE網(wǎng)以下圖，a=31V

V2a2 =6

a5=2

a4

a=18

V a59=31 aa3=2 a=6V3

V4a =37

4 V70=a1V6（1）請(qǐng)分別計(jì)算出各事件的最早發(fā)生時(shí)間、各活動(dòng)的最晚開始時(shí)間、各活動(dòng)的廢弛時(shí)間；活動(dòng)。

各事件的最晚發(fā)生時(shí)間、 各活動(dòng)的最早開始時(shí)間、（2）用極點(diǎn)序列表示出重點(diǎn)路徑，并給出重點(diǎn)2、下邊是用c語(yǔ)言編寫的對(duì)不帶頭結(jié)點(diǎn)的單鏈表進(jìn)行就地逆置的算法， 該算法用L返回逆后的鏈表的頭指針，試在空缺處填入適合的語(yǔ)句。voidreverse （linklist&L ）{p=null；q=L；while（q！=null）{ ; q->next=p ；p=q ； ;};}3前序序列：A，B，C，D，E，F(xiàn)，G，H，I，J中序序列：C，B，A，E，F(xiàn)，D，I，H，J，G4{v1，v2，v3v4v5，v6組表示形式見下表。

v7，

v8}

，已知其毗鄰矩陣的三元88201212152211226328534835236443845104785125325410623634677748767825請(qǐng)畫出該無向圖的毗鄰表；請(qǐng)畫出全部可能的最小花銷生成樹；v1出發(fā)進(jìn)行深度優(yōu)先遍歷與廣度優(yōu)先遍歷的極點(diǎn)序列；v1到v2的最短路徑是什么？長(zhǎng)度為多少？（不要求推導(dǎo)過程三、剖析題（每題 10分，共50分）1、試各舉一個(gè)例，用表示圖和簡(jiǎn)要說明論述棧和行列在程序設(shè)計(jì)中所起的作用。2、鑒別下邊的每個(gè)結(jié)點(diǎn)序列能否表示一個(gè)堆，假如是，請(qǐng)給出判斷原因；假如不是堆，請(qǐng)它調(diào)整為堆(最大值為堆頂)，要求畫出堆的調(diào)整變化過程。 241,8.22（1）100，90，80，60，85，75，20，25，10，70，65，50（2）100，70，50，20，90，75，60，25，10，85，65，803、給定權(quán)值[5,10,12,15,30,40], 結(jié)構(gòu)相應(yīng)的哈夫曼樹， 并給每個(gè)權(quán)值定義一個(gè)哈夫曼編碼，要求詳細(xì)步驟。4、已知一棵完整二叉樹共