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

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

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

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

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