數(shù)據(jù)結(jié)構(gòu)-數(shù)據(jù)結(jié)構(gòu)測試-2014計算機應(yīng)用技術(shù)用

1、數(shù)據(jù)結(jié)構(gòu)測試-2014計算機應(yīng)用技術(shù)用1-11每虎團4分,12-15每小題7分1含n個頂點的連通無向圖，其邊的個數(shù)至少為（）A. mlB. nC. ii+lD. 2n2有向圖頂點數(shù)為m弧數(shù)為e,采用鄰接矩陣存儲結(jié)構(gòu)，求所有結(jié)點出度的時間復(fù)雜度為（）A.。（用） B O（n3）C O（n+e）D O（n*e）3下圖對應(yīng)的最小生成樹中，各邊權(quán)值之和為：4. 關(guān)于拓撲排序說汐、錯誤的是（）A有向無壞圖一定存在覆蓋所有結(jié)點的拓撲序列B存在有向回路的冇向圖一定不存在覆蓋所冇結(jié)點的拓撲序列C有向圖存在覆蓋所月結(jié)點的拓撲序列，則其必然不存在有向回路D有向無壞圖的拓撲序列唯一5. 適用于折半查找的表的存儲方式

2、及元素排列要求為（）A鏈接方式存儲，元素?zé)o序 B.鏈接方式存儲，兀素有序C順序方式存儲，元素?zé)o序D.順序方式存儲，元素代序6. 下面關(guān)于哈希資找的說法正確的是（）A.哈希函數(shù)構(gòu)造的越復(fù)雜越好，因為這樣隨機性好，沖突小B除留余數(shù)法足所冇哈希函數(shù)中最好的C.不存在特別好與壞的哈希兩數(shù)，要視情況而定D若需在哈希表中刪去一個元素，不管用何種方法解決沖突都只要簡單的將該元索刪去即叮7. 對卞列四種排序方法，關(guān)鍵字比較次數(shù)與記錄初始排列狀態(tài)無關(guān)的是（）。A.直接插入排序 B.改進的冒泡排序C.快速排序D.直接選擇排序&下列排序算法中，其中（）是穩(wěn)定的A.堆排序，冒泡排序B快速排序，堆排序C.希爾排序，歸并

3、排序 D.山|并卅用，口泡排庁9冇向圖采用鄰接矩陣存儲結(jié)構(gòu)，計算結(jié)點出度的復(fù)雜度與計算入度相同。B.錯誤A.正確10哈希查找直接根據(jù)待查找記錄關(guān)鍵字的取值計算哈希地址，無需進行比較，平均查找長度為0oA.正確B錯誤11.時間復(fù)雜度為OElong?)的排序算法，其空間復(fù)雜度不可能是O(l)_A.正確B錯誤 12圖的鄰接矩陣如卜所示，假設(shè)鄰接點按照字典序排列A0 1B1 0C0 0D0 0E1 1F1 10 0 110 0 110 0 0 10 0 0 10 0 0 0110 0(1) 畫出從A開始進行廣度優(yōu)先遍歷對應(yīng)的廣度優(yōu)先生成樹(2) 畫出從A開始進行深度優(yōu)先遍歷對應(yīng)的深度優(yōu)先生成樹參考答案

4、：(1)廣度優(yōu)先生成樹為:深度優(yōu)先生成樹:13假設(shè)輸入記錄序列為(46,78,40,39,90,85,45),(1) 畫出由此得到的二叉排序樹(2) 假設(shè)查找成功，且設(shè)各記錄査找概率相同，計算平均査找長度。參考答案：(1)二叉排序樹為：46407839? U585(2)平均査找長度為:18/7 14已知待散列的線性表為(25, 17, 15, 27, 32, 68),哈希地址空間為0.7,假定選用的哈希函數(shù)是H(K) = K%7(1) 用線性探測再散列作為解決沖突的方法，給出對應(yīng)的哈希表(2) 用鏈地址法作為解決沖突的方法，給出對應(yīng)的哈希衷參考答案：(1)線性探測再散列對應(yīng)的哈希農(nóng)：15設(shè)初始記錄關(guān)鍵字序列為(40 49 73 27 98 8136),對其由小到人排序(1) 寫出快速排序時以40為樞軸進行趟快速排序后的結(jié)果(2