《數(shù)據(jù)結(jié)構(gòu)》試卷七

1、數(shù)據(jù)結(jié)構(gòu)試卷七一、填空題：(共20分)1、數(shù)據(jù)對(duì)象指具有的數(shù)據(jù)元素集合。2、TAIL(HEAD(a,b),(c,d)=。3、二維數(shù)組存儲(chǔ)地址計(jì)算公式(以行序?yàn)橹?為(b為基地址，每個(gè)元素占存儲(chǔ)單元數(shù)為l,下標(biāo)取值范圍為(cl,dl),(c2,d2)。4、一個(gè)連通圖的生成樹(shù)是一個(gè).5、順序存儲(chǔ)結(jié)構(gòu)下，當(dāng)時(shí)表示?？铡?、二叉樹(shù)結(jié)點(diǎn)的度2,且樹(shù)中子樹(shù)有左右之分，不能顛倒，故二叉樹(shù)是一棵樹(shù)。7、高度為K的二叉樹(shù)中至多有個(gè)結(jié)點(diǎn)。8、對(duì)樹(shù)的遍歷有兩種。9、對(duì)長(zhǎng)度為12的有序表進(jìn)行折半查找,等概率時(shí)查找成功的平均查找長(zhǎng)度為10、O如圖，樹(shù)中葉子結(jié)點(diǎn)中的數(shù)值即該結(jié)點(diǎn)的權(quán)值，樹(shù)的帶權(quán)路徑長(zhǎng)度、樹(shù)的/路徑長(zhǎng)度分別

2、為。O/O/二、選擇題：(共20分)1、下面關(guān)于線性表的敘述中，錯(cuò)誤的是()線性表采用順序存儲(chǔ)，必順占用一片連續(xù)的存儲(chǔ)單元。線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。2、編號(hào)為1,2,3,4的四輛列車，順序開(kāi)進(jìn)一個(gè)棧式結(jié)構(gòu)棧臺(tái)，則開(kāi)出棧臺(tái)順序有()種。1(B)3(C)5(D)73、將n個(gè)元素的順序表倒置，則至少需要的附加空間為()0(B)1(C)n(D)n+14、n=1000，要求最快，且最省內(nèi)存的排序方法為()快速排序(B)shell排序(C)歸并排序(D)堆排序5、在構(gòu)造散列表時(shí)，下面能采用的處理沖突的

3、方法為()(A)開(kāi)放定址法(B)鏈地址法(C)直接定址法(D)再hash法6、設(shè)森林F中有三棵樹(shù)，第一、第二和第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為M1、M2和M3。與森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是(A)M1(B)M1+M2(C)M3(D)M2+M37、在下列存儲(chǔ)形式中，哪一個(gè)不是樹(shù)的存儲(chǔ)形式雙親表示法B)孩子鏈表表示法孩子兄弟示法D)順序存儲(chǔ)表示法8、以下哪一個(gè)不是隊(duì)列的基本運(yùn)算?()(A)從隊(duì)尾插入一個(gè)新元素從隊(duì)列中刪除第i個(gè)元素判斷一個(gè)隊(duì)列是否為空讀取隊(duì)頭元素的值9、下面關(guān)于圖的存儲(chǔ)的敘述中正確的是()用相鄰矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)用相鄰矩陣法

4、存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)10、對(duì)線性表進(jìn)行二分法查找，其前提條件是線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序三、簡(jiǎn)答題：(共40分)1、把圖所示樹(shù)表示成二元組形式和廣義表形式：a/bc/def/ghI2、畫(huà)出下列無(wú)向圖的鄰接表存儲(chǔ)結(jié)構(gòu)，并由鄰接表寫(xiě)出廣度優(yōu)先搜索序列和深度優(yōu)先搜索序列：A3、用快速排序法對(duì)下列整數(shù)序列進(jìn)行排序，寫(xiě)出中間與最后結(jié)果。89,27,52,80,15,28,100,724、如圖所示的5階B-樹(shù)，試畫(huà)出插入96后B-樹(shù)的形狀。3050709035405560687275808510159295981005、如圖所示，對(duì)圖G用prim算法構(gòu)造一棵最小生成樹(shù)，（由頂點(diǎn)a開(kāi)始）要求能反映出樹(shù)中頂點(diǎn)與邊加入的順序：3be655ad65146cf2四、設(shè)計(jì)或分析題：（共20分）1、已知n個(gè)數(shù)據(jù)存入數(shù)組Al.n中，使用