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

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

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

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

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