春數(shù)據(jù)結構二試卷真題

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

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

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

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

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

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

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

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