PAGEPAGE1網(wǎng)絡(luò)教育學(xué)院數(shù)據(jù)結(jié)構(gòu)試卷(A)說明：此試卷曾于2005年用于我校網(wǎng)絡(luò)教育學(xué)院高升本（脫產(chǎn)）計算機專業(yè)期末考試卷;點評:考試時間：150分鐘，試題難度：中等一、單項選擇題(210分)1.下列說明法中正確的是()。A.快速排序在最壞情況下退化為起泡排序，時間復(fù)雜度為O(n2)。B.堆排序在最壞情況下的時間復(fù)雜度為O(n2)。C.堆排序列是一種穩(wěn)定的排序方法。D.基數(shù)排序是一種不穩(wěn)定的排序方法。2.三維數(shù)組A[4][5][6]按行優(yōu)先存儲方法存儲在內(nèi)存中，若每個元素占2個存儲單元，且數(shù)組中第一個元素的存儲地址為120，則元素A[3][4][5]的存儲地址為()。

A.356B.358C.360D.3623.n個頂點的強連通有向完全圖中至少含有()條有向邊。

A.n-1B.nC.n(n-1)/2D.n(n-1)4.在需要經(jīng)常查找結(jié)點的前驅(qū)與后繼的場合中，使用(

)比較合適。A.單鏈表

B.雙鏈表

C.順序表

D.循環(huán)鏈表5.20個結(jié)點完全二叉樹共有(

)個葉子結(jié)點。A.8

B.9C.10

D.116.按照二叉樹的定義，具有3個結(jié)點的二叉樹有(

)種形式。

A.3

B.4

C.5

D.67.深度為5的二叉樹至多有(

)個結(jié)點。A.16

B.32

C.31

D.108.靜態(tài)查找表與動態(tài)查找表二者的根本差別在于(

)。A.它們的邏輯結(jié)構(gòu)不一樣

B.施加在其上的操作不同

C.所包含的數(shù)據(jù)元素的類型不一樣D.存儲實現(xiàn)不一樣9.無向圖中一個頂點的度是指圖中()。A.通過該頂點的簡單路徑數(shù) B.與該頂點相鄰接的頂點數(shù)C.通過該頂點的回路數(shù) D.與該頂點連通的頂點數(shù)10.已知一組關(guān)鍵字為{25,48,36,72,79,82,23,40,16,35}，其中每相鄰兩個為有序子序列。對這些子序列進行一趟兩兩歸并的結(jié)果是()。A.{25,36,48,72,23,40,79,82,16,35} B.{25,36,48,72,16,23,40,79,82,35}C.{25,36,48,72,16,23,35,40,79,82} D.{16,23,25,35,36,40,48,72,79,82}二、填空題(210分)1.串S=”Iamaworker”的長度是________。2.進行時間復(fù)雜度分析時，一般主要考慮最壞情況時間復(fù)雜度和時間復(fù)雜度。3.8層完全二叉樹結(jié)點數(shù)目范圍是。4.n個結(jié)點e條弧的有向圖鄰接表結(jié)構(gòu)中，有個表結(jié)點和個頭結(jié)點。5.字符串"ABC""A"。（填＜、＞或者者＝）6.隊列的基本操作原則是“先進先出”，棧的基本操作原則是。7．對數(shù)組存儲線性表(16,15,32,11,6,30)用快速排序方法進行由小到大排序，若排序下標范圍為0~5，選擇元素16作為支點，調(diào)用一趟快速排序算法后，元素16在數(shù)組中的下標位置是。8.基于關(guān)鍵字比較大小的排序算法中，排序算法的平均時間復(fù)雜度最優(yōu)。9．《計算方法》課程主要講授科學(xué)計算領(lǐng)域的程序設(shè)計方法；而《數(shù)據(jù)結(jié)構(gòu)》課程主要研究領(lǐng)域的程序設(shè)計方法。三、簡答題(56分)1.從空樹起，依次插入關(guān)鍵字40，8，90，15，62，95，12，23，56，32，構(gòu)造一棵二叉排序樹。

(1)畫出該二叉排序樹；

(2)畫出刪去該樹中元素值為90的結(jié)點之后的二叉排序樹。2.請把如下序列構(gòu)造成為一個堆并畫出對應(yīng)的二叉樹示意圖。23,76,47,53,41,12,85,303.若入棧元素序列為ABC,寫出所有可能的出棧序列。4.二叉樹如下圖所示，寫出先序、中序、后序遍歷結(jié)點訪問次序并畫出中序穿線(線索)二叉樹。s1s1s2s3s4s6s8s9s7s5545112974245.求出下圖的關(guān)鍵路徑，結(jié)點的最早完成時間，結(jié)點的最晚完成時間及關(guān)鍵活動。6.畫出下圖的一棵最小生成樹。四、算法設(shè)計(103分)

1.指針變量p指向循環(huán)單鏈表某結(jié)點，寫出一個函數(shù)DelPriou(p)，刪除結(jié)點指針p所指結(jié)點的前驅(qū)結(jié)點。（請對循環(huán)單鏈表數(shù)據(jù)結(jié)構(gòu)進行試當說明）2.已知二叉鏈表樹結(jié)點指針數(shù)據(jù)類型bitree定義如下，試寫出一個遞歸函數(shù)，求二叉樹的深度。typedefstructnode{intdata;structn