2012貴州大學(xué)數(shù)據(jù)結(jié)構(gòu)A卷(共5頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上貴州大學(xué)2011-2012學(xué)年第二學(xué)期考試試卷 A數(shù)據(jù)結(jié)構(gòu)注意事項：1. 請考生按要求在試卷裝訂線內(nèi)填寫姓名、學(xué)號和年級專業(yè)。2. 請仔細(xì)閱讀各種題目的回答要求，在規(guī)定的位置填寫答案。3. 不要在試卷上亂寫亂畫，不要在裝訂線內(nèi)填寫無關(guān)的內(nèi)容。4. 滿分100分，考試時間為120分鐘。題 號一二三四總 分統(tǒng)分人得 分得 分評分人一、單項選擇題（共20分,每小題2分）1不是四類基本邏輯結(jié)構(gòu)之一的是（ ）A、集合B、鏈表結(jié)構(gòu)C、樹形結(jié)構(gòu)D、網(wǎng)狀結(jié)構(gòu)2關(guān)于隊列的描述，錯誤的是（ ）A、隊列的頭指針指下一個入隊的位置B、普通隊列要求滿足“先進(jìn)先出”C、使用一個隊列可以模擬一個銀

2、行的多個同性質(zhì)服務(wù)窗口的排隊狀況D、循環(huán)隊列可以采用順序表實現(xiàn)3在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O（1）的操作是 （ ）A、訪問第i個結(jié)點（1in）和求第i個結(jié)點的直接前驅(qū)（2in）B、在第i個結(jié)點后插入一個新結(jié)點（1in）C、刪除第i個結(jié)點（1in）D、將n個結(jié)點從小到大排序4下列關(guān)于串的敘述中，正確的是（ ）A、一個串的字符個數(shù)即該串的長度B、一個串的長度至少是1C、空串是由一個空格字符組成的串D、兩個串S1和S2若長度相同，則這兩個串相等5稀疏矩陣一般的壓縮存儲方法有兩種，即（ ）A、二維數(shù)組和三維數(shù)組B、三元組和散列C、三元組和十字鏈表D、散列和十字鏈表6按照二叉樹的定義,具有

3、3個結(jié)點的二叉樹有（ ）A、3種B、4種C、5種B、6種7不是圖的存儲結(jié)構(gòu)的是 （ ）A、鄰接多重表B、十字鏈表C、關(guān)聯(lián)矩陣 D、可利用空間表8在關(guān)于動態(tài)存儲管理，錯誤的說法是（ ）A、未被占用的連續(xù)地址空間稱為空閑塊B、可利用空間表一般采用鏈表C、針對內(nèi)存申請塊的大小范圍較廣時，應(yīng)該采用首次擬合法D、針對內(nèi)存申請塊的大小較均勻時，應(yīng)該采用最差擬合法9理想情況下，速度最快的查找結(jié)構(gòu)的是（ ）A、分塊索引B、二叉排序樹C、二叉平衡樹D、哈希表10. 關(guān)于各種排序方法，錯誤的說法是（ ）A、關(guān)鍵字大小相同的記錄，排序后先后順序不改變，則稱為此排序為穩(wěn)定的B、內(nèi)部排序算法的性能由關(guān)鍵字比較次數(shù)和記錄

4、移動次數(shù)決定C、冒泡排序的時間復(fù)雜度為O(nlogn)D、堆排序使用的堆對應(yīng)一棵完全二叉樹得 分評分人二、概念填空題（共20分,每空2分）1若使用伙伴系統(tǒng)進(jìn)行動態(tài)存儲管理，若申請32個字，選中的空閑塊有128個字，則這個空閑塊會被分裂為_個塊（最小塊大小可以為4）。2在邏輯上相關(guān)的元素，在物理存儲地址上不一定相鄰，兩種不同的存儲結(jié)構(gòu)分別稱為：_存儲結(jié)構(gòu)和_存儲結(jié)構(gòu)。3快速排序在最壞情況下算法復(fù)雜度為_；在哈希表中，不同關(guān)鍵字得到相同哈希地址稱為_。4數(shù)據(jù)結(jié)構(gòu)可以形式化定義為一個二元組，Data_Structure=(D，S)，其中D是_的集合，S是_的集合。5進(jìn)行深度優(yōu)先搜索需要用到輔助數(shù)據(jù)結(jié)

5、構(gòu)是_。 6已知中綴表達(dá)式為(a+b)/(c-d)，對應(yīng)的前綴表達(dá)式為_。7稀疏矩陣的行鏈表存儲中，每行單鏈表的結(jié)點具有相同的_。得 分評分人三、數(shù)據(jù)操作和表示題（共40分,每小題5分）1 設(shè)待排序記錄集合的關(guān)鍵字為（45,27,18,67,13,76,38,90,27,25），采用希爾排序算法，間隔增量d分別取5、3、1，請寫出第一趟和第二趟希爾排序之后的結(jié)果。 2從一棵空的平衡二叉樹開始，將以下關(guān)鍵碼值依次插入：41,27,10,65,45,36,29，請畫出插入每一個元素且調(diào)整平衡之后的平衡二叉樹。3. 畫出用Prim算法求出下圖的最小生成樹4畫出下面稀疏矩陣的三元存儲法表示。（行列下標(biāo)

6、從1開始）5順序棧初始狀態(tài)如下左圖所示，經(jīng)過入下入隊和出隊操作之后，請在右圖中畫出棧內(nèi)容、top和base所指。操作順序為：元素A、B相繼壓棧；然后出棧一個元素；又有元素C、 D、E入棧；然后出棧兩個元素； 6已知一棵二叉樹的先序遍歷為：A B F D F F C E F F F G F F F，其中F表示葉子結(jié)點，請畫出這棵二叉樹。7假定一組記錄的關(guān)鍵字為50,27,16,67,14,36,38,29,26,24，采用HASH表存儲，HASH地址空間為HT15，若采用除留余數(shù)法構(gòu)造HASH函數(shù)h(key)=key mod 13，用線性再探測法處理沖突，線性再探測序列為1,2,3,4,5n，請

7、畫出最后得到的HASH表，求出平均查找長度。8. 使用Floyd算法求出下圖中頂點之間的最短路徑，請?zhí)顚懬蠼膺^程鄰接矩陣和路徑矩陣。DD(0)D(1)D(2)D(3)ABCABCABCABCA0000B0000C0000PP(0)P(1)P(2)P(3)ABCABCABCABCA-B-C-得 分評分人四、程序題（共20分,每題10分）1請完成如下函數(shù)：void BInsertSort(SqList &L)/對順序表L作折半插入排序for (i=2;i=L.length;+i)_;/設(shè)置觀察哨L.r0left=1;_right=_;/設(shè)置搜索范圍while(left =right+1;-j) _;/向后移動記錄L.r