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

第 11頁(yè) 共 12頁(yè)成績(jī)上海大學(xué)20122013學(xué)年度春季學(xué)期試卷A課程名: 數(shù)據(jù)結(jié)構(gòu)（二）課程號(hào): 學(xué)分: 4 應(yīng)試人聲明： 我保證遵守上海大學(xué)學(xué)生手冊(cè)中的上海大學(xué)考場(chǎng)規(guī)則，如有考試違紀(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)記T，錯(cuò)誤的標(biāo)記F(每題1分，共10分）1. 任意一棵二叉樹(shù)都可以轉(zhuǎn)換為樹(shù)來(lái)表示 （ ）2. 折半查找進(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ù)溆行蛐蛄斜囟ù嬖?。?）9. 順序表上的直接選擇排序是一種穩(wěn)定的排序方法。（ ）10. 對(duì)長(zhǎng)度為n的表作快速排序，最壞情況下，算法時(shí)間復(fù)雜度為O(n2)。（ ）二、選擇題（每題1分，共15分）1. 如果要求一個(gè)線性表既能較快的查找，又能適應(yīng)動(dòng)態(tài)變化的要求，則可采用( )法。A分塊查找 B順序查找 C 折半查找 D 基于屬性的查找2. 在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（ ）倍。A1/2 B2 C1 D43. 用DFS遍歷一個(gè)無(wú)環(huán)有向圖，并在DFS算法退棧返回時(shí)打印相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是( )。A逆拓?fù)溆行?B拓?fù)溆行?C無(wú)序的 4. 下列哪一種圖的鄰接矩陣是對(duì)稱矩陣？（ ）A有向圖 B無(wú)向圖 CAOV網(wǎng) DAOE網(wǎng)5. 用鄰接矩陣A表示圖，判定任意兩個(gè)頂點(diǎn)Vi和Vj之間是否有長(zhǎng)度為m 的路徑相連，則只要檢查（ ）的第i行第j列的元素是否為零即可。AmA BA CAm DAm-16. 下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）A深度優(yōu)先遍歷 B. 拓?fù)渑判?C. 求最短路徑 D. 求關(guān)鍵路徑7. 7. 在圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹(shù)的 Prim 算法的時(shí)間復(fù)雜度為( )。A. O(n) B. O(n+e) C. O(n2) D. O(n3)8. 8下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（ ）。A關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成C所有的關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成D某些關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成9. 二叉查找樹(shù)在( )時(shí)其查找效率最低。A結(jié)點(diǎn)太多 B完全二叉樹(shù) C呈單枝樹(shù) D結(jié)點(diǎn)太復(fù)雜10. 設(shè)有一個(gè)用線性探測(cè)法解決沖突得到的散列表：0123456789101325801617614散列函數(shù)為H(k)=k mod 11,若要查找元素14，探測(cè)的次數(shù)是( )。A18 B 9 C 3 D 611. 下列排序方法中，( )是穩(wěn)定的排序方法 A直接選擇排序 B折半插入排序 C希爾排序 D快速排序12. 下述排序方法中，比較次數(shù)與待排序記錄的初始狀態(tài)無(wú)關(guān)的是（ ）。 A. 插入排序和快速排序 B. 歸并排序和快速排序C. 選擇排序和基數(shù)排序 D.插入排序和歸并排序13. 設(shè)有5000個(gè)元素，希望用最快的速度挑選出前10個(gè)最大的，下列排序方法中采用（ ）方法最好。A. 快速排序 B. 堆排序 C. 希爾排序 D. 歸并排序14. 并查集的結(jié)構(gòu)是（ ）A. 二叉鏈表存儲(chǔ)的二叉樹(shù) B. 雙親表示法存儲(chǔ)的樹(shù) C. 三叉鏈表存儲(chǔ)的二叉樹(shù) D. 線性鏈表15. 下列哪一個(gè)關(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是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有_個(gè)頂點(diǎn)。2. 已知一無(wú)向圖G=（V，E），其中V=a,b,c,d,e, E=(a,b),(a,d),(a,c),(d,c),(b,e)現(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è)有向圖有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,11,15,19,25,26,30,33,42,48,50）中，用折半法查找關(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，則寫出第一趟結(jié)束后，數(shù)組中數(shù)據(jù)的排列第三個(gè)元素是（從0開(kāi)始計(jì)數(shù) ） 。10. 對(duì)一組記錄（54, 38, 106, 21, 15, 72, 60, 45, 83）進(jìn)行直接插入排序，當(dāng)把元素60插入到有序表時(shí)，為尋找插入位置需比較 次。四、簡(jiǎn)答題（共24分）1. (8分)已知2棵2-3 樹(shù)（3階B-樹(shù)）如下： （1） 對(duì)樹(shù)（a）,請(qǐng)分別畫出先后插入26，85兩個(gè)新結(jié)點(diǎn)后的樹(shù)形；（2） 對(duì)樹(shù)（b）,請(qǐng)分別畫出先后刪除53，37兩個(gè)結(jié)點(diǎn)后的樹(shù)形。 (a)53 90452430 371261 7050100 【解答】：（1）（2）2. （8分）給定5個(gè)村莊(A、B、C、D、E)之間的交通圖如下所示，若村莊i到j(luò)有道路，則將頂點(diǎn)i到j(luò)用有向邊連接，邊上的Wij表示這條道路的長(zhǎng)度?，F(xiàn)在請(qǐng)回答以下問(wèn)題：（1）畫出該有向圖的鄰接表存儲(chǔ)結(jié)構(gòu) （2）求其它各村莊到村莊B的最短路徑和最短路徑長(zhǎng)度。（3）要從這5個(gè)村莊中選擇一個(gè)村莊建一所醫(yī)院，問(wèn)這所醫(yī)院應(yīng)建在哪個(gè)村莊，才能各村到醫(yī)院的來(lái)回路程最短?說(shuō)明解答上述問(wèn)題的算法?！窘獯稹浚海?）（2）（3）3. （8分）對(duì)初始序列(58，85，47，39，70，47*，101，68，10，66，34)按遞增方式進(jìn)行排序。（1）給出快速排序的第一趟排序結(jié)果（以第1個(gè)元素58為基準(zhǔn)元素）。（2）選取d = 5，3，1，給出希爾排序的第一趟排序結(jié)果。（3）寫出二路歸并的第一趟排序結(jié)果。（4）給出基數(shù)排序的第一趟的回收結(jié)果?！窘獯稹浚海?）快速排序的第一趟排序結(jié)果為：（2）希爾排序的第一趟排序結(jié)果為：（3）二路歸并的第一趟排序結(jié)果為：（4）基數(shù)排序的第一趟回收結(jié)果是：得分五、算法分析題（每空2分，共26分）1（8分）下列遞歸算法的功能是：從大到小輸出給定二叉排序樹(shù)中所有關(guān)鍵字不小于x的數(shù)據(jù)元素。該算法的時(shí)間復(fù)雜度為O(log2n+m)，其中n為二叉排序樹(shù)中的結(jié)點(diǎn)數(shù)，m為輸出的數(shù)據(jù)元素個(gè)數(shù)。請(qǐng)完善該算法。提示：算法可以借助逆中序遍歷二叉排序樹(shù)來(lái)實(shí)現(xiàn)。所謂逆中序遍歷二叉樹(shù)是指：如果當(dāng)前結(jié)點(diǎn)p非空，則先逆中序遍歷p的右二叉樹(shù)；然后訪問(wèn)p結(jié)點(diǎn)；最后再逆中序遍歷p的左二叉樹(shù)。在本算法中訪問(wèn)p結(jié)點(diǎn)時(shí)，如果p的值小于x，則算法結(jié)束，否則輸出p的值。void PrintNLT (BSTreeNode* p, const Type x ) if (p) (1) ；if (p-datax) /當(dāng)遇到小于x的元素時(shí)立即結(jié)束運(yùn)行 (2) ；; cout (3) endl;(4) ；/PrintNLT(1) _(2) _(3) _(4) _ 2 (10分) 在有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)中，為每個(gè)頂點(diǎn)v增加一個(gè)MPL域，其定義為圖中所有頂點(diǎn)到達(dá)頂點(diǎn)v的最長(zhǎng)路徑長(zhǎng)度(路徑上的邊數(shù))。下面算法完成對(duì)有向無(wú)環(huán)圖G中每個(gè)頂點(diǎn)的MPL值，如果g無(wú)回路，則求出各頂點(diǎn)的MPL，并返回SUCCESS；否則返回FAIL。template Status FillMPL(const AdjListDirGraph &g) / 初始條件：存在有向圖g/ 操作結(jié)果：如g無(wú)回路,則求出g中每個(gè)頂點(diǎn)的MPL,并返回SUCCESS,否則返回FAILint *indegree = new intg.GetVexNum();/ 頂點(diǎn)入度數(shù)組int v, u, mpl, count = 0, top = -1;for (v = 0; v g.GetVexNum(); v+) indegreev = 0; / 初始化頂點(diǎn)v的入度為0g.SetMPL(v, 0); / 初始化v頂點(diǎn)的MPL為0 for (v = 0; v g.GetVexNum(); v+) / 統(tǒng)計(jì)圖g各頂點(diǎn)的入度f(wàn)or (u = g.FirstAdjVex(v); u != -1; u = g.NextAdjVex(v, u)indegreeu+;for (v = 0; v g.GetMPL(u) (4) ；if (-indegreeu = 0)/ u入度為0,將u入棧 indegreeu = top; top = u; /end for /end whiledelete indegree;/ 釋放indegree所占用的存儲(chǔ)空間if ( (5) ) return FAIL;/ 圖g有回路else return SUCCESS;/ 求MPL成功(1) _(2)_ (3) _(4) _ (5) _ 3 (8分)折半插入排序的算法基本思想是：設(shè)在排序表中有n個(gè)數(shù)據(jù)元素Arr0，Arr1,Arrn-1。其中，Arr0,Arr1,Arri-1是已經(jīng)排好序的部分?jǐn)?shù)據(jù)元素序列，在插入Arri時(shí)，利用折半查找方法尋找Arri的插入位置。在下面算法的 處，填上適當(dāng)語(yǔ)句，實(shí)現(xiàn)上面的算法?！咀ⅰ浚宏P(guān)鍵字用成員函數(shù)getKey()獲取。template void BinaryInsertSort ( sortlist & table ) element temp； int low , high, mid ;for ( int i = 1; i table.CurrentSize; i+) low = 0; high = i-1; temp = table.Arri; while ( low = low; k- ) (3) ; (4) ； (1) _(2) _得分(3) _(4) _ 六、算法設(shè)計(jì)題(10分)在有向圖中頂點(diǎn)的度等于其入度與出度之和，現(xiàn)定義有向圖的度為其所有頂點(diǎn)度的最大值。試編寫算法CountDegree(g)，在有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)上求有向圖g的度。下面是有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)類模板的部分定義：template class AdjListDirGraphprotected:/ 鄰接表的數(shù)據(jù)成員:int vexNum, vexMaxNum, arcNum;/ 頂點(diǎn)數(shù)目、允許的頂點(diǎn)最大數(shù)目和邊數(shù)AdjListGraphVex *vexTable;/ 頂點(diǎn)表public:/ 抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明:AdjListDirGraph(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)的頂點(diǎn)個(gè)數(shù) int GetArcNum() const; / 求有向網(wǎng)的邊數(shù)個(gè)數(shù) int FirstAdjVex(int v) const; / 求有向網(wǎng)中頂點(diǎn)v的第一個(gè)鄰接點(diǎn)序號(hào)int NextAdjVex(int v1, int v2) ; / 求頂點(diǎn)v1的相對(duì)于v2的下一個(gè)鄰接點(diǎn)序號(hào) ;編寫的算法：template int CountDegree(const AdjListDirGraph &g)/ 返回有向圖g的度數(shù)值上海大學(xué)20122013學(xué)年度春季學(xué)期試卷A課程名: 數(shù)據(jù)結(jié)構(gòu)（二）課程號(hào): 學(xué)分: 4 參考答案和評(píng)分標(biāo)準(zhǔn) 數(shù)據(jù)結(jié)構(gòu)課程組：曹旻，滕中梅，沈俊，張景嶠，許慶國(guó)，鄭宇一、判斷題（10分）（答案惟一，每小題1分）題號(hào)12345678910答案FTFFFTFTFT二、選擇題（15分）（答案惟一，每小題1分）題號(hào)123456789101112131415答案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四、簡(jiǎn)答題（共24分）（答案的寫法不惟一，可酌情給分）1.2. 1)2,3)3. （1）快速排序的第一趟排序結(jié)果為：34,10,47,39,47*,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) Prin