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

1、第1頁共12頁注：教師應(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)（二）課程號:08305010學(xué)分:4應(yīng)試人聲明：我保證遵守《上海大學(xué)學(xué)生手冊》中的《上海大學(xué)考場規(guī)則》，如有考

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

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

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

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

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

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

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