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

1、第 11頁 共 12頁成績上海大學(xué)20122013學(xué)年度春季學(xué)期試卷A課程名: 數(shù)據(jù)結(jié)構(gòu)（二）課程號: 08305010 學(xué)分: 4 應(yīng)試人聲明： 我保證遵守上海大學(xué)學(xué)生手冊中的上海大學(xué)考場規(guī)則，如有考試違紀(jì)、作弊行為，愿意接受上海大學(xué)學(xué)生考試違紀(jì)、作弊行為界定及處分規(guī)定的紀(jì)律處分。應(yīng)試人 應(yīng)試人學(xué)號 應(yīng)試人所在院系 題號(分值)一(10)二(15)三(15)四(24)五(26)六(10)得分得分得分 一、判斷題,敘述正確的標(biāo)記T，錯誤的標(biāo)記F(每題1分，共10分）1. 任意一棵二叉樹都可以轉(zhuǎn)換為樹來表示 （ ）2. 折半查找進(jìn)行時間性能分析的判定樹不一定是完全二叉樹。（ ）3. 散列表的平均

2、查找長度只與采用的散列函數(shù)及處理沖突的方法有關(guān)。（ ）4. 對 B 樹刪除某一關(guān)鍵字值時，可能會引起結(jié)點的分裂。 （ ）5. 有e條邊的無向圖，在鄰接表中有e個結(jié)點。（ ）6. 十字鏈表是有向圖的一種存儲結(jié)構(gòu)。（ ）7. 不同的求最小生成樹的方法最后得到的生成樹是相同的。（ ）8. 若一個有向圖的鄰接矩陣對角線以下元素均為零，則該圖的拓?fù)溆行蛐蛄斜囟ù嬖?。?）9. 順序表上的直接選擇排序是一種穩(wěn)定的排序方法。（ ）10. 對長度為n的表作快速排序，最壞情況下，算法時間復(fù)雜度為O(n2)。（ ）二、選擇題（每題1分，共15分）1. 如果要求一個線性表既能較快的查找，又能適應(yīng)動態(tài)變化的要求，則可

3、采用( )法。A分塊查找 B順序查找 C 折半查找 D 基于屬性的查找2. 在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)（ ）倍。A1/2 B2 C1 D43. 用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時打印相應(yīng)的頂點，則輸出的頂點序列是( )。A逆拓?fù)溆行?B拓?fù)溆行?C無序的 4. 下列哪一種圖的鄰接矩陣是對稱矩陣？（ ）A有向圖 B無向圖 CAOV網(wǎng) DAOE網(wǎng)5. 用鄰接矩陣A表示圖，判定任意兩個頂點Vi和Vj之間是否有長度為m 的路徑相連，則只要檢查（ ）的第i行第j列的元素是否為零即可。AmA BA CAm DAm-16. 下面哪一方法可以判斷出一個有向圖是否有環(huán)（回路

4、）A深度優(yōu)先遍歷 B. 拓?fù)渑判?C. 求最短路徑 D. 求關(guān)鍵路徑7. 7. 在圖采用鄰接表存儲時，求最小生成樹的 Prim 算法的時間復(fù)雜度為( )。A. O(n) B. O(n+e) C. O(n2) D. O(n3)8. 8下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（ ）。A關(guān)鍵活動不按期完成就會影響整個工程的完成時間B任何一個關(guān)鍵活動提前完成，那么整個工程將會提前完成C所有的關(guān)鍵活動提前完成，那么整個工程將會提前完成D某些關(guān)鍵活動提前完成，那么整個工程將會提前完成9. 二叉查找樹在( )時其查找效率最低。A結(jié)點太多 B完全二叉樹 C呈單枝樹 D結(jié)點太復(fù)雜10. 設(shè)有一個用線性探測法解決沖突

5、得到的散列表：0123456789101325801617614散列函數(shù)為H(k)=k mod 11,若要查找元素14，探測的次數(shù)是( )。A18 B 9 C 3 D 611. 下列排序方法中，( )是穩(wěn)定的排序方法 A直接選擇排序 B折半插入排序 C希爾排序 D快速排序12. 下述排序方法中，比較次數(shù)與待排序記錄的初始狀態(tài)無關(guān)的是（ ）。 A. 插入排序和快速排序 B. 歸并排序和快速排序C. 選擇排序和基數(shù)排序 D.插入排序和歸并排序13. 設(shè)有5000個元素，希望用最快的速度挑選出前10個最大的，下列排序方法中采用（ ）方法最好。A. 快速排序 B. 堆排序 C. 希爾排序 D. 歸并排

6、序14. 并查集的結(jié)構(gòu)是（ ）A. 二叉鏈表存儲的二叉樹 B. 雙親表示法存儲的樹 C. 三叉鏈表存儲的二叉樹 D. 線性鏈表15. 下列哪一個關(guān)鍵碼序列不符合堆的定義?（ ）A. A,C,D,G,H,M,P,Q,R,X B. A,C,M,D,H,P,X,G,Q,RC. A,D,P,R,C,Q,X,M,H,G D. A,D,C,M,P,G,H,X,R,Q得分得分三、填空題（每空1分，共15分）1. G是一個非連通無向圖，共有28條邊，則該圖至少有_個頂點。2. 已知一無向圖G=（V，E），其中V=a,b,c,d,e, E=(a,b),(a,d),(a,c),(d,c),(b,e)現(xiàn)用某一種圖遍

7、歷方法從頂點a開始遍歷圖，得到的序列為abecd，則采用的是_ _遍歷方法。 3. 求圖的最小生成樹有兩種算法，其中_算法適合于求稀疏圖的最小生成樹。4. 求從某源點到其余各頂點的Dijkstra算法在圖的頂點數(shù)為10，用鄰接矩陣表示圖時計算時間約為10ms,則在圖的頂點數(shù)為40，計算時間約為_ms。5. 設(shè)有向圖有n個頂點和e條邊，進(jìn)行拓?fù)渑判驎r，總的計算時間復(fù)雜度為_。6. 設(shè)線性表(a1，a2，a500)元素的值由小到大排列。對一個給定的k值，在等概率情況下，用順序查找法查找一個記錄，查找成功的平均查找長度ASL為 ；用二分法檢索查找表中與k相等的元素，在查找不成功的情況下至多比較_次。

8、用分塊查找（索引表和各塊內(nèi)均用順序查找），若分成25塊，查找成功的其平均查找長度為_。7. 在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半法查找關(guān)鍵碼值8，需做的關(guān)鍵碼比較次數(shù)為_ _，查找關(guān)鍵碼值20，需做的關(guān)鍵碼比較次數(shù)為_ _.8. 對于一個高度為h（空樹的高度為-1）的AVL樹，其最少結(jié)點數(shù)是 。反之，對于一個有n個結(jié)點的AVL樹, 其最大高度是 ，最小高度是 。9. 設(shè)用希爾排序?qū)?shù)組98，36，19，5，47，23，1，8，10，7進(jìn)行排序，給出的步長（也稱增量序列）依次是5、3、1，則寫出第一趟結(jié)束后，數(shù)組中數(shù)據(jù)的排列第三個元素是（從0開始計

9、數(shù) ） 。10. 對一組記錄（54, 38, 106, 21, 15, 72, 60, 45, 83）進(jìn)行直接插入排序，當(dāng)把元素60插入到有序表時，為尋找插入位置需比較 次。四、簡答題（共24分）1. (8分)已知2棵2-3 樹（3階B-樹）如下： （1） 對樹（a）,請分別畫出先后插入26，85兩個新結(jié)點后的樹形；（2） 對樹（b）,請分別畫出先后刪除53，37兩個結(jié)點后的樹形。 (a)53 90452430 371261 7050100 【解答】：（1）（2）2. （8分）給定5個村莊(A、B、C、D、E)之間的交通圖如下所示，若村莊i到j(luò)有道路，則將頂點i到j(luò)用有向邊連接，邊上的Wij表

10、示這條道路的長度。現(xiàn)在請回答以下問題：（1）畫出該有向圖的鄰接表存儲結(jié)構(gòu) （2）求其它各村莊到村莊B的最短路徑和最短路徑長度。（3）要從這5個村莊中選擇一個村莊建一所醫(yī)院，問這所醫(yī)院應(yīng)建在哪個村莊，才能各村到醫(yī)院的來回路程最短?說明解答上述問題的算法?！窘獯稹浚海?）（2）（3）3. （8分）對初始序列(58，85，47，39，70，47*，101，68，10，66，34)按遞增方式進(jìn)行排序。（1）給出快速排序的第一趟排序結(jié)果（以第1個元素58為基準(zhǔn)元素）。（2）選取d = 5，3，1，給出希爾排序的第一趟排序結(jié)果。（3）寫出二路歸并的第一趟排序結(jié)果。（4）給出基數(shù)排序的第一趟的回收結(jié)果?！窘?/p>

11、答】：（1）快速排序的第一趟排序結(jié)果為：（2）希爾排序的第一趟排序結(jié)果為：（3）二路歸并的第一趟排序結(jié)果為：（4）基數(shù)排序的第一趟回收結(jié)果是：得分五、算法分析題（每空2分，共26分）1（8分）下列遞歸算法的功能是：從大到小輸出給定二叉排序樹中所有關(guān)鍵字不小于x的數(shù)據(jù)元素。該算法的時間復(fù)雜度為O(log2n+m)，其中n為二叉排序樹中的結(jié)點數(shù)，m為輸出的數(shù)據(jù)元素個數(shù)。請完善該算法。提示：算法可以借助逆中序遍歷二叉排序樹來實現(xiàn)。所謂逆中序遍歷二叉樹是指：如果當(dāng)前結(jié)點p非空，則先逆中序遍歷p的右二叉樹；然后訪問p結(jié)點；最后再逆中序遍歷p的左二叉樹。在本算法中訪問p結(jié)點時，如果p的值小于x，則算法結(jié)束

12、，否則輸出p的值。void PrintNLT (BSTreeNode<Type>* p, const Type x ) if (p) (1) ；if (p->data<x) /當(dāng)遇到小于x的元素時立即結(jié)束運行 (2) ；; cout << (3) <<endl;(4) ；/PrintNLT(1) _(2) _(3) _(4) _ 2 (10分) 在有向圖的鄰接表存儲結(jié)構(gòu)中，為每個頂點v增加一個MPL域，其定義為圖中所有頂點到達(dá)頂點v的最長路徑長度(路徑上的邊數(shù))。下面算法完成對有向無環(huán)圖G中每個頂點的MPL值，如果g無回路，則求出各頂點的MPL，

13、并返回SUCCESS；否則返回FAIL。template <class ElemType>Status FillMPL(const AdjListDirGraph<ElemType> &g) / 初始條件：存在有向圖g/ 操作結(jié)果：如g無回路,則求出g中每個頂點的MPL,并返回SUCCESS,否則返回FAILint *indegree = new intg.GetVexNum();/ 頂點入度數(shù)組int v, u, mpl, count = 0, top = -1;for (v = 0; v < g.GetVexNum(); v+) indegreev =

14、 0; / 初始化頂點v的入度為0g.SetMPL(v, 0); / 初始化v頂點的MPL為0 for (v = 0; v < g.GetVexNum(); v+) / 統(tǒng)計圖g各頂點的入度for (u = g.FirstAdjVex(v); u != -1; u = g.NextAdjVex(v, u)indegreeu+;for (v = 0; v < g.GetVexNum(); v+)if (indegreev = 0) / 入度為0的頂點入棧 (1) ; top = v; while ( (2) )/ 棧非空v = top; (3) ; mpl = g.GetMPL(v)

15、 + 1;count+;/ 已求出MPL的頂點數(shù)累加for (u = g.FirstAdjVex(v); u != -1; u = g.NextAdjVex(v, u)/ 對v的每個后繼頂點u入度減1,并修改其MPL if (mpl > g.GetMPL(u) (4) ；if (-indegreeu = 0)/ u入度為0,將u入棧 indegreeu = top; top = u; /end for /end whiledelete indegree;/ 釋放indegree所占用的存儲空間if ( (5) ) return FAIL;/ 圖g有回路else return SUCCES

16、S;/ 求MPL成功(1) _(2)_ (3) _(4) _ (5) _ 3 (8分)折半插入排序的算法基本思想是：設(shè)在排序表中有n個數(shù)據(jù)元素Arr0，Arr1,Arrn-1。其中，Arr0,Arr1,Arri-1是已經(jīng)排好序的部分?jǐn)?shù)據(jù)元素序列，在插入Arri時，利用折半查找方法尋找Arri的插入位置。在下面算法的 處，填上適當(dāng)語句，實現(xiàn)上面的算法?！咀ⅰ浚宏P(guān)鍵字用成員函數(shù)getKey()獲取。template <class Type> void BinaryInsertSort ( sortlist<Type> & table ) element<Typ

17、e> temp； int low , high, mid ;for ( int i = 1; i < table.CurrentSize; i+) low = 0; high = i-1; temp = table.Arri; while ( low <= high ) (1) ; if (2) ) high = mid - 1; else low = mid + 1; for (int k = i-1; k >= low; k- ) (3) ; (4) ； (1) _(2) _得分(3) _(4) _ 六、算法設(shè)計題(10分)在有向圖中頂點的度等于其入度與出度之和，現(xiàn)

18、定義有向圖的度為其所有頂點度的最大值。試編寫算法CountDegree(g)，在有向圖的鄰接表存儲結(jié)構(gòu)上求有向圖g的度。下面是有向圖的鄰接表存儲結(jié)構(gòu)類模板的部分定義：template <class ElemType>class AdjListDirGraphprotected:/ 鄰接表的數(shù)據(jù)成員:int vexNum, vexMaxNum, arcNum;/ 頂點數(shù)目、允許的頂點最大數(shù)目和邊數(shù)AdjListGraphVex<ElemType> *vexTable;/ 頂點表public:/ 抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明:AdjListDirGraph

19、(ElemType es, int vertexNum, int vertexMaxNum = DEFAULT_SIZE);/ 構(gòu)造函數(shù)AdjListDirGraph(int vertexMaxNum = DEFAULT_SIZE);/構(gòu)造函數(shù)AdjListDirGraph(); / 析構(gòu)函數(shù) int GetVexNum() const; / 求有向網(wǎng)的頂點個數(shù) int GetArcNum() const; / 求有向網(wǎng)的邊數(shù)個數(shù) int FirstAdjVex(int v) const; / 求有向網(wǎng)中頂點v的第一個鄰接點序號int NextAdjVex(int v1, int v2) ;

20、/ 求頂點v1的相對于v2的下一個鄰接點序號 ;編寫的算法：template <class ElemType> int CountDegree(const AdjListDirGraph<ElemType> &g)/ 返回有向圖g的度數(shù)值上海大學(xué)20122013學(xué)年度春季學(xué)期試卷A課程名: 數(shù)據(jù)結(jié)構(gòu)（二）課程號: 08305010 學(xué)分: 4 參考答案和評分標(biāo)準(zhǔn) 數(shù)據(jù)結(jié)構(gòu)課程組：曹旻，滕中梅，沈俊，張景嶠，許慶國，鄭宇一、判斷題（10分）（答案惟一，每小題1分）題號12345678910答案FTFFFTFTFT二、選擇題（15分）（答案惟一，每小題1分）題號12

21、3456789101112131415答案ABABCBBBCDBCBBC三、填空題（15分）（答案的寫法不惟一，意思正確即可）1 9 ；2入深度優(yōu)；3 克魯斯卡爾（Kruskal）；4 160 ；5 O(n+e）； 6 501/2 , 9 , 21/2+26/2 = 47/2； 7 3, 4 ；8 Nh = Fh+3 1, Fh是斐波那契數(shù), 3 / 2 * log2 (n + 1) , élog2 ( n+1)ù -1；95；103四、簡答題（共24分）（答案的寫法不惟一，可酌情給分）1.2. 1)2,3)3. （1）快速排序的第一趟排序結(jié)果為：34,10,47,39,4

22、7*,58,101,68,70,66,85.（2）希爾排序的第一趟排序結(jié)果為：34,85,47,10,66,47*,101,68,39,70,58.（3）二路歸并的第一趟排序結(jié)果為：58,85,39,47,47*,70,68,101,10,66,34.（4）基數(shù)排序的第一趟回收結(jié)果是：70,10,101,34,47,47*,66,58,85,68,39.五、算法分析題（每空2分，共26分）（答案的寫法不惟一，可酌情給分）1. (1) PrintNLT ( p->rightChild, x); (2) exit() or return;(3) p->data; (4) PrintNLT ( p->leftChild, x);2. (1): indegreev = top (2): top != -1 (3): top = indegreev(4): g.SetMPL(u, mpl) (5): c