數(shù)據(jù)結(jié)構(gòu)試卷(A卷)2005.1

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

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

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

)比較合適。A.單鏈表

B.雙鏈表

C.順序表

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

)個(gè)葉子結(jié)點(diǎn)。A.8

B.9C.10

D.116.按照二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有(

)種形式。

A.3

B.4

C.5

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

)個(gè)結(jié)點(diǎn)。A.16

B.32

C.31

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

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

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

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

(1)畫(huà)出該二叉排序樹(shù)；

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

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