春數(shù)據(jù)結(jié)構(gòu)二試卷真題

1、第1頁(yè)共12頁(yè)注：教師應(yīng)使用計(jì)算機(jī)處理試題的文字、公式、圖表等；學(xué)生應(yīng)使用水筆或圓珠筆答題。答題時(shí)不注：教師應(yīng)使用計(jì)算機(jī)處理試題的文字、公式、圖表等；學(xué)生應(yīng)使用水筆或圓珠筆答題。答題時(shí)不得用鉛筆，否則查卷有誤，閱卷者概不負(fù)責(zé)。得用鉛筆，否則查卷有誤，閱卷者概不負(fù)責(zé)。上海大學(xué)2012～2013學(xué)年度春季學(xué)期試卷A課程名:數(shù)據(jù)結(jié)構(gòu)（二）課程號(hào):08305010學(xué)分:4應(yīng)試人聲明：我保證遵守《上海大學(xué)學(xué)生手冊(cè)》中的《上海大學(xué)考場(chǎng)規(guī)則》，如有考

2、試違紀(jì)、作弊行為，愿意接受《上海大學(xué)學(xué)生考試違紀(jì)、作弊行為界定及處分規(guī)定》的紀(jì)律處分。應(yīng)試人應(yīng)試人學(xué)號(hào)應(yīng)試人所在院系題號(hào)(分值)一(10)二(15)三(15)四(24)五(26)六(10)得分—————————————————————————————————————一、判斷題一、判斷題敘述正確的標(biāo)記敘述正確的標(biāo)記T，錯(cuò)誤的標(biāo)記，錯(cuò)誤的標(biāo)記F(F(每題每題1分，共分，共1010分）分）1.任意一棵二叉樹(shù)都可以轉(zhuǎn)換為樹(shù)來(lái)表示（）2.折半查找

3、進(jìn)行時(shí)間性能分析的判定樹(shù)不一定是完全二叉樹(shù)。（）3.散列表的平均查找長(zhǎng)度只與采用的散列函數(shù)及處理沖突的方法有關(guān)。（）4.對(duì)B樹(shù)刪除某一關(guān)鍵字值時(shí)，可能會(huì)引起結(jié)點(diǎn)的分裂。（）5.有e條邊的無(wú)向圖，在鄰接表中有e個(gè)結(jié)點(diǎn)。（）6.十字鏈表是有向圖的一種存儲(chǔ)結(jié)構(gòu)。（）7.不同的求最小生成樹(shù)的方法最后得到的生成樹(shù)是相同的。（）8.若一個(gè)有向圖的鄰接矩陣對(duì)角線以下元素均為零，則該圖的拓?fù)溆行蛐蛄斜囟ù嬖?。（?.順序表上的直接選擇排序是一種穩(wěn)定的排

4、序方法。（）10.對(duì)長(zhǎng)度為n的表作快速排序，最壞情況下，算法時(shí)間復(fù)雜度為O(n2)。（）二、選擇題（每題二、選擇題（每題1分，共分，共1515分）分）1.如果要求一個(gè)線性表既能較快的查找，又能適應(yīng)動(dòng)態(tài)變化的要求，則可采用()法。A分塊查找B順序查找C折半查找D基于屬性的查找2.2.在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（）倍。A12B2C1D43.用DFS遍歷一個(gè)無(wú)環(huán)有向圖，并在DFS算法退棧返回時(shí)打印相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序

5、列是()。成績(jī)得分得分第3頁(yè)共12頁(yè)注：教師應(yīng)使用計(jì)算機(jī)處理試題的文字、公式、圖表等；學(xué)生應(yīng)使用水筆或圓珠筆答題。答題時(shí)不注：教師應(yīng)使用計(jì)算機(jī)處理試題的文字、公式、圖表等；學(xué)生應(yīng)使用水筆或圓珠筆答題。答題時(shí)不得用鉛筆，否則查卷有誤，閱卷者概不負(fù)責(zé)。得用鉛筆，否則查卷有誤，閱卷者概不負(fù)責(zé)。三、填空題（每空三、填空題（每空1分，共分，共1515分）分）1.G是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有______個(gè)頂點(diǎn)。2.已知一無(wú)向圖G

6、=（V，E），其中V=abcdeE=(ab)(ad)(ac)(dc)(be)現(xiàn)用某一種圖遍歷方法從頂點(diǎn)a開(kāi)始遍歷圖，得到的序列為abecd，則采用的是________遍歷方法。3.求圖的最小生成樹(shù)有兩種算法，其中______________算法適合于求稀疏圖的最小生成樹(shù)。4.求從某源點(diǎn)到其余各頂點(diǎn)的Dijkstra算法在圖的頂點(diǎn)數(shù)為10，用鄰接矩陣表示圖時(shí)計(jì)算時(shí)間約為10ms則在圖的頂點(diǎn)數(shù)為40，計(jì)算時(shí)間約為_(kāi)_____ms。5.設(shè)有向

7、圖有n個(gè)頂點(diǎn)和e條邊，進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間復(fù)雜度為_(kāi)___________。6.設(shè)線性表(a1，a2，…，a500)元素的值由小到大排列。對(duì)一個(gè)給定的k值，在等概率情況下，用順序查找法查找一個(gè)記錄，查找成功的平均查找長(zhǎng)度ASL為；用二分法檢索查找表中與k相等的元素，在查找不成功的情況下至多比較_________次。用分塊查找（索引表和各塊內(nèi)均用順序查找），若分成25塊，查找成功的其平均查找長(zhǎng)度為_(kāi)__________。7.在順序

8、表（811151925263033424850）中，用折半法查找關(guān)鍵碼值8，需做的關(guān)鍵碼比較次數(shù)為_(kāi)___，查找關(guān)鍵碼值20，需做的關(guān)鍵碼比較次數(shù)為_(kāi)___.8.對(duì)于一個(gè)高度為h（空樹(shù)的高度為1）的AVL樹(shù)，其最少結(jié)點(diǎn)數(shù)是。反之，對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的AVL樹(shù)其最大高度是，最小高度是。9.設(shè)用希爾排序?qū)?shù)組98，36，19，5，47，23，1，8，10，7進(jìn)行排序，給出的步長(zhǎng)（也稱增量序列）依次是5、3、1，則寫(xiě)出第一趟結(jié)束后，數(shù)組中數(shù)據(jù)