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

1、網(wǎng)絡(luò)教育學(xué)院數(shù)據(jù)結(jié)構(gòu)試卷(A)說明：此試卷曾于2005年用于我校網(wǎng)絡(luò)教育學(xué)院高升本（脫產(chǎn)）計(jì)算機(jī)專業(yè)期末考試卷;評(píng)論:考試時(shí)間：150分鐘，試題難度：中等一、單項(xiàng)選擇題(210分)1.以下說明法中正確的選項(xiàng)是()。A.迅速排序在最壞狀況下退化為起泡排序，時(shí)間復(fù)雜度為O(n2)。B.堆排序在最壞狀況下的時(shí)間復(fù)雜度為O(n2)。堆排序列是一種穩(wěn)固的排序方法?；鶖?shù)排序是一種不穩(wěn)固的排序方法。2.三維數(shù)組A456按行優(yōu)先儲(chǔ)存方法儲(chǔ)存在內(nèi)存中，若每個(gè)元素占2個(gè)儲(chǔ)存單元，且數(shù)組中第一個(gè)元素的儲(chǔ)存地點(diǎn)為120，則元素A345的儲(chǔ)存地點(diǎn)為()。A.356B.358C.360D.3623.n個(gè)極點(diǎn)的強(qiáng)連通有向完

2、整圖中起碼含有()條有向邊。A.n-1B.nC.n(n-1)/2D.n(n-1)4.在需要常常查找結(jié)點(diǎn)的前驅(qū)與后繼的場(chǎng)合中，使用()比較適合。A.單鏈表B.雙鏈表C.次序表D.循環(huán)鏈表5.20個(gè)結(jié)點(diǎn)完整二叉樹共有()個(gè)葉子結(jié)點(diǎn)。A.8B.9C.10D.116.依據(jù)二叉樹的定義，擁有3個(gè)結(jié)點(diǎn)的二叉樹有()種形式。A.3B.4C.5D.67.深度為5的二叉樹至多有()個(gè)結(jié)點(diǎn)。A.16B.32C.31D.108.靜態(tài)查找表與動(dòng)向查找表兩者的根本差異在于()。A.它們的邏輯結(jié)構(gòu)不同樣B.施加在其上的操作不同C.所包括的數(shù)據(jù)元素的種類不同樣D.儲(chǔ)存實(shí)現(xiàn)不同樣9.無向圖中一個(gè)極點(diǎn)的度是指圖中()。1A.經(jīng)

3、過該極點(diǎn)的簡(jiǎn)單路徑數(shù)B.與該極點(diǎn)相毗鄰的極點(diǎn)數(shù)C.經(jīng)過該極點(diǎn)的回路數(shù)D.與該極點(diǎn)連通的極點(diǎn)數(shù)10.已知一組重點(diǎ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,35B.25,36,48,72,16,23,40,79,82,35C.25,36,48,72,16,23,35,40,79,82D.16,23,25,35,36,40,48,72,79,82二、填空題(210分)1.串S=”Iamaworker的長”度是_。2.進(jìn)行時(shí)間復(fù)雜度剖析時(shí)，一般主要考慮最

4、壞狀況時(shí)間復(fù)雜度和時(shí)間復(fù)雜度。3.8層完整二叉樹結(jié)點(diǎn)數(shù)量范圍是。4.n個(gè)結(jié)點(diǎn)e條弧的有向圖毗鄰表結(jié)構(gòu)中，有個(gè)表結(jié)點(diǎn)和個(gè)頭結(jié)點(diǎn)。5.字符串ABCA。（填、或許者）6.行列的基本操作原則是“先進(jìn)先出”，棧的基本操作原則是。7對(duì)數(shù)組儲(chǔ)存線性表(16,15,32,11,6,30)用迅速排序方法進(jìn)行由小到大排序，若排序下標(biāo)范圍為05，選擇元素16作為支點(diǎn)，調(diào)用一趟迅速排序算法后，元素16在數(shù)組中的下標(biāo)位置是。8.鑒于重點(diǎ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分)從空樹起，挨次插入重

5、點(diǎn)字40，8，90，15，62，95，12，23，56，32，結(jié)構(gòu)一棵二叉排序樹。畫出該二叉排序樹；畫出刪去該樹中元素值為90的結(jié)點(diǎn)以后的二叉排序樹。請(qǐng)把以下序列結(jié)構(gòu)成為一個(gè)堆并畫出對(duì)應(yīng)的二叉樹表示圖。23,76,47,53,41,12,85,303.若入棧元素序列為ABC,寫出全部可能的出棧序列。24.二叉樹以以下圖所示，寫出先序、中序、后序遍歷結(jié)點(diǎn)接見序次并畫出中序穿線(線索)二叉樹。ABCDEFG求出以下圖的重點(diǎn)路徑，結(jié)點(diǎn)的最早達(dá)成時(shí)間，結(jié)點(diǎn)的最晚達(dá)成時(shí)間及重點(diǎn)活動(dòng)。ss2751921435s9s7154ss6s4824畫出以下圖的一棵最小生成樹。四、算法設(shè)計(jì)(103分)1.指針變量p指向循環(huán)單鏈表某結(jié)點(diǎn)，寫出一個(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)說明）已知二叉鏈表樹結(jié)點(diǎn)指針數(shù)據(jù)種類bitree定義以下，試寫出一個(gè)遞歸函數(shù)，求二叉樹的深度。typedefstructnodeintdata;structnode*lchild,*rchild;*