jaysukh-I--a答案-期末復(fù)習(xí)-數(shù)據(jù)結(jié)構(gòu)-數(shù)據(jù)結(jié)構(gòu)參

1、網(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分鐘,試題難度:中等姓名:學(xué)號(hào):班級(jí):成績(jī):一、單項(xiàng)選擇題(210分1.下列說(shuō)明法中正確的是(。A.快速排序在最壞情況下退化為起泡排序,時(shí)間復(fù)雜度為O(n2。B.堆排序在最壞情況下的時(shí)間復(fù)雜度為O(n2。C.堆排序列是一種穩(wěn)定的排序方法。D.基數(shù)排序是一種不穩(wěn)定的排序方法。2.三維數(shù)組A456按行優(yōu)先存儲(chǔ)方法存儲(chǔ)在內(nèi)存中,若每個(gè)元素占2個(gè)存儲(chǔ)單元,且數(shù)組中第一個(gè)元素的存儲(chǔ)地址為120,則元素A345的存儲(chǔ)地址為(。A.356B.358C.360D.3623.n個(gè)頂點(diǎn)

2、的強(qiáng)連通有向完全圖中至少含有(條有向邊。A.n-1B.nC.n(n-1/2D.n(n-14.在需要經(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.8B.9C.10D.116.按照二叉樹(shù)的定義,具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有(種形式。A.3B.4C.5D.67.深度為5的二叉樹(shù)至多有(個(gè)結(jié)點(diǎn)。A.16B.32C.31D.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ò)該

3、頂點(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,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=”I am a worker”的長(zhǎng)度是_。2.進(jìn)行時(shí)間復(fù)雜度分析時(shí),一般主要考慮最壞

4、情況時(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ǔ)線性表(16,15,32,11,6,30用快速排序方法進(jìn)行由小到大排序,若排序下標(biāo)范圍為05,選擇元素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)課程主要

5、研究領(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,30A BCD EFG 3.若入棧元素序列為ABC,寫(xiě)出所有可能的出棧序列。4.二叉樹(shù)如下圖所示,寫(xiě)出先序、中序、后序遍歷結(jié)點(diǎn)訪問(wèn)次序并畫(huà)出中序穿線(線索二叉樹(shù)。5.求出下圖的關(guān)鍵路徑,結(jié)點(diǎn)的最早完成時(shí)間,結(jié)點(diǎn)的最晚完成時(shí)間及關(guān)鍵活動(dòng)。6.畫(huà)出下圖的一棵最小生成樹(shù)。四、算法設(shè)計(jì)(10 3分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ù)的深度。typedef struct node int data;struct node *lchild,*rchild;*b