計算機數(shù)據(jù)結(jié)構(gòu)今年考研真題及答案_第1頁
計算機數(shù)據(jù)結(jié)構(gòu)今年考研真題及答案_第2頁
計算機數(shù)據(jù)結(jié)構(gòu)今年考研真題及答案_第3頁
計算機數(shù)據(jù)結(jié)構(gòu)今年考研真題及答案_第4頁
計算機數(shù)據(jù)結(jié)構(gòu)今年考研真題及答案_第5頁
已閱讀5頁,還剩20頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、20091.為解決計算機與打印機之間速度不匹配的問題,通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū),主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū),而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是A.棧 B.隊列 C.樹 D.圖2.設(shè)棧S和隊列Q的初始狀態(tài)均為空,元素abcdefg依次進入棧S。若每個元素出棧后立即進入隊列Q,且7個元素出隊的順序是bdcfeag,則棧S的容量至少是 A1 B.2 C.3 D.43.給定二叉樹圖所示。設(shè)N代表二叉樹的根,L代表根結(jié)點的左子樹,R代表根結(jié)點的右子樹。若遍歷后的結(jié)點序列為3,1,7,5,6,2,4,則其遍歷方式是 ALRN B.NRL C.RLN D.RNL4.下列二

2、叉排序樹中,滿足平衡二叉樹定義的是5.已知一棵完全二叉樹的第6層(設(shè)根為第1層)有8個葉結(jié)點,則完全二叉樹的結(jié)點個數(shù)最多是A39 B.52 C.111 D.1196.將森林轉(zhuǎn)換為對應(yīng)的二叉樹,若在二叉樹中,結(jié)點u是結(jié)點v的父結(jié)點的父結(jié)點,則在原來的森林中,u和v可能具有的關(guān)系是I父子關(guān)系 II.兄弟關(guān)系 III.u的父結(jié)點與v的父結(jié)點是兄弟關(guān)系A(chǔ).只有II B.I和II C.I和III D.I、II和III7.下列關(guān)于無向連通圖特性的敘述中,正確的是I所有頂點的度之和為偶數(shù) II.邊數(shù)大于頂點個數(shù)減1 III.至少有一個頂點的度為1A.只有I B.只有II C.I和II D.I和III8.下列

3、敘述中,不符合m階B樹定義要求的是A根節(jié)點最多有m棵子樹 B.所有葉結(jié)點都在同一層上C各結(jié)點內(nèi)關(guān)鍵字均升序或降序排列 D.葉結(jié)點之間通過指針鏈接9.已知關(guān)鍵序列5,8,12,19,28,20,15,22是小根堆(最小堆),插入關(guān)鍵字3,調(diào)整后得到的小根堆是A3,5,12,8,28,20,15,22,19B.3,5,12,19,20,15,22,8,28C3,8,12,5,20,15,22,28,19D.3,12,5,8,28,20,15,22,1910.若數(shù)據(jù)元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的結(jié)果,則該排序算法只能是A起泡排序 B.插入

4、排序 C.選擇排序 D.二路歸并排序41.(10分)帶權(quán)圖(權(quán)值非負,表示邊連接的兩頂點間的距離)的最短路徑問題是找出從初始頂點到目標頂點之間的一條最短路徑。假定從初始頂點到目標頂點之間存在路徑,現(xiàn)有一種解決該問題的方法:設(shè)最短路徑初始時僅包含初始頂點,令當前頂點u為初始頂點;選擇離u最近且尚未在最短路徑中的一個頂點v,加入到最短路徑中,修改當前頂點u=v;重復(fù)步驟,直到u是目標頂點時為止。請問上述方法能否求得最短路徑?若該方法可行,請證明之;否則,請舉例說明。42.(15分)已知一個帶有表頭結(jié)點的單鏈表,結(jié)點結(jié)構(gòu)為datalink假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下,請設(shè)計

5、一個盡可能高效的算法,查找鏈表中倒數(shù)第k個位置上的結(jié)點(k為正整數(shù))。若查找成功,算法輸出該結(jié)點的data值,并返回1;否則,只返回0。要求:(1)描述算法的基本設(shè)計思想(2)描述算法的詳細實現(xiàn)步驟(3)根據(jù)設(shè)計思想和實現(xiàn)步驟,采用程序設(shè)計語言描述算法(使用C或C+或JAVA語言實現(xiàn)),關(guān)鍵之處請給出簡要注釋。20101、若元素a,b,c,d,e,f依次進棧,允許進棧、退棧操作交替進行。但不允許連續(xù)三次進行退棧工作,則不可能得到的出棧序列是( )A:dcebfa B:cbdaef C:dbcaef D:afedcb2、某隊列允許在其兩端進行入隊操作,但僅允許在一端進行出隊操作,則不可能得到的順

6、序是( )A:bacde B:dbace C:dbcae D:ecbad3、下列線索二叉樹中(用虛線表示線索),符合后序線索樹定義的是( )4、在下列所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹,在新平衡二叉樹中,關(guān)鍵字37所在結(jié)點的左、右子結(jié)點中保存的關(guān)鍵字分別是( )A:13,48 B:24,48 C:24,53 D:24,905、在一棵度為4的樹T中,若有20個度為4的結(jié)點,10個度為3的結(jié)點,1個度為2的結(jié)點,10個度為1的結(jié)點,則樹T的葉節(jié)點個數(shù)是( )A:41 B:82 C:113 D:1226、對n(n大于等于2)個權(quán)值均不相同的字符構(gòu)成哈夫曼樹,關(guān)于該樹的敘述中,錯誤

7、的是( )A:該樹一定是一棵完全二叉樹B:樹中一定沒有度為1的結(jié)點C:樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點D:樹中任一非葉結(jié)點的權(quán)值一定不小于下一任一結(jié)點的權(quán)值7、若無向圖G-(V.E)中含7個頂點,則保證圖G在任何情況下都是連通的,則需要的邊數(shù)最少是( )A:6 B:15 C:16 D:218、對下圖進行拓補排序,可以得到不同的拓補序列的個數(shù)是( )A:4 B:3 C:2 D:19、已知一個長度為16的順序表L,其元素按關(guān)鍵字有序排列,若采用折半查找法查找一個不存在的元素,則比較次數(shù)最多是( )A:4 B:5 C:6 D:710、采用遞歸方式對順序表進行快速排序,下列關(guān)于遞歸次數(shù)的敘述中,正

8、確的是( )A:遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)B:每次劃分后,先處理較長的分區(qū)可以減少遞歸次數(shù)C:每次劃分后,先處理較短的分區(qū)可以減少遞歸次數(shù)D:遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān)11、對一組數(shù)據(jù)(2,12,16,88,5,10)進行排序,若前三趟排序結(jié)果如下( )第一趟:2,12,16,5,10,88第二趟:2,12,5,10,16,88第三趟:2,5,10,12,16,88則采用的排序方法可能是:A:起泡排序 B:希爾排序 C:歸并排序 D:基數(shù)排序41.(10分)將關(guān)鍵字序列(7、8、11、18、9、14)散列存儲到散列列表中,散列表的存儲空間是一個下標從0開始的一個一維數(shù)組散

9、列函數(shù)維:H(key)=(key×3)MODT,處理沖突采用線性探測再散列法,要求裝填(載)因子為0.7問題:(1)請畫出所構(gòu)造的散列表; (2)分別計算等概率情況下,查找成功和查找不成功的平均查找長度。42.(13分)設(shè)將n(n,1)個整數(shù)存放到一維數(shù)組R中,試設(shè)計一個在時間和空間兩方面盡可能有效的算法,將R中保有的序列循環(huán)左移P(0Pn)個位置,即將R中的數(shù)據(jù)由(X0X1Xn-1)變換為(XpXp+1Xn-1X0X1Xp-1)要求:(1)給出算法的基本設(shè)計思想。 (2)根據(jù)設(shè)計思想,采用C或C+或JAVA語言表述算法關(guān)鍵之處給出注釋。 (3)說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜

10、度20111.設(shè)n是描述問題規(guī)模的非負整數(shù),下面程序片段的時間復(fù)雜度是x = 2;while ( x < n/2 )x = 2*x;A.O(log2n) B.O(n) C.O(n log2n) D.O(n2)2.元素a, b, c, d, e依次進入初始為空的棧中,若元素進棧后可停留、可出棧,直到所有元素都出棧,則在所有可能的出棧序列中,以元素d開頭的序列個數(shù)是 A.3 B.4 C.5 D.63.已知循環(huán)隊列存儲在一維數(shù)組A0.n-1 中,且隊列非空時front和rear分別指向隊頭元素和隊尾元素。若初始時隊列為空,且要求第1個進入隊列的元素存儲在A0處,則初始時front和rear的值

11、分別是A.0, 0 B.0, n-1 C.n-1, 0 D.n-1, n-14.若一棵完全二叉樹有768個結(jié)點,則該二叉樹中葉結(jié)點的個數(shù)是A.257 B.258 C.384 D.3855.若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1, 2, 3, 4和4, 3, 2, 1,則該二叉樹的中序遍歷序列不會是A.1, 2, 3, 4 B.2, 3, 4, 1 C.3, 2, 4, 1 D.4, 3, 2, 16.已知一棵有2011個結(jié)點的樹,其葉結(jié)點個數(shù)為116,該樹對應(yīng)的二叉樹中無右孩子的結(jié)點個數(shù)是A.115 B.116 C.1895 D.18967.對于下列關(guān)鍵字序列,不可能構(gòu)成某二叉排序樹

12、中一條查找路徑的序列是A.95, 22, 91, 24, 94, 71 B.92, 20, 91, 34, 88, 35C.21, 89, 77, 29, 36, 38 D.12, 25, 71, 68, 33, 348.下列關(guān)于圖的敘述中,正確的是I. 回路是簡單路徑II. 存儲稀疏圖,用鄰接矩陣比鄰接表更省空間III.若有向圖中存在拓撲序列,則該圖不存在回路A.僅II B.僅I、II C.僅III D.僅I、III9.為提高散列(Hash)表的查找效率,可以采取的正確措施是I. 增大裝填(載)因子II. 設(shè)計沖突(碰撞)少的散列函數(shù)III.處理沖突(碰撞)時避免產(chǎn)生聚集(堆積)現(xiàn)象A.僅I

13、 B.僅II C.僅I、II D.僅II、III10.為實現(xiàn)快速排序算法,待排序序列宜采用的存儲方式是A.順序存儲 B.散列存儲 C.鏈式存儲 D.索引存儲11.已知序列25, 13, 10, 12, 9是大根堆,在序列尾部插入新元素18,將其再調(diào)整為大根堆,調(diào)整過程中元素之間進行的比較次數(shù)是A.1 B.2 C.4 D.541.(8分)已知有6個頂點(頂點編號為0 5)的有向帶權(quán)圖G,其鄰接矩陣A為上三角矩陣,按行為主序(行優(yōu)先)保存在如下的一維數(shù)組中。要求:(1)寫出圖G的鄰接矩陣A。(2)畫出有向帶權(quán)圖G。(3)求圖G的關(guān)鍵路徑,并計算該關(guān)鍵路徑的長度。42.(15分)一個長度為L(L1)

14、的升序序列S,處在第éL/2ù個位置的數(shù)稱為S的中位數(shù)。例如,若序列S1=(11, 13, 15, 17, 19),則S1的中位數(shù)是15。兩個序列的中位數(shù)是含它們所有元素的升序序列的中位數(shù)。例如,若S2=(2, 4, 6, 8, 20),則S1和S2的中位數(shù)是11?,F(xiàn)有兩個等長升序序列A和B,試設(shè)計一個在時間和空間兩方面都盡可能高效的算法,找出兩個序列A和B的中位數(shù)。 要求:(1)給出算法的基本設(shè)計思想。(2)根據(jù)設(shè)計思想,采用C或C+或JAVA語言描述算法,關(guān)鍵之處給出注釋。(3)說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。20121、求整數(shù)n(n0)階乘的算法如下,其時間

15、復(fù)雜度是()intfact(intn)if(n<=1)return1;returnn*fact(n-1);A.O(log2n) B.O(n) C.(nlog2n) D.O(n2)2、已知操作符包括+、-、*、/、(和)。將中綴表達式a+b-a*(c+d)/e-f)+g轉(zhuǎn)換為等價的后綴表達式ab+acd+e/f-*-g+時,用棧來存放暫時還不能確定運算次序的操作符,若棧初始時為空,則轉(zhuǎn)換過程中同時保存棧中的操作符的最大個數(shù)是()A.5 B.7 C.8 D.113、若一顆二叉樹的前序遍歷序列為a,e,b,d,c,后續(xù)遍歷序列為b,c,d,e,a,則根節(jié)點的孩子節(jié)點()A.只有e B.有e、b

16、 C.有e、c D.無法確定4、若平衡二叉樹的高度為6,且所有非葉節(jié)點的平衡因子均為1,則該平衡二叉樹的節(jié)點總數(shù)為()A.10 B.20 C.32 D.335、對有n個節(jié)點、e條邊且使用鄰接表存儲的有向圖進行廣度優(yōu)先遍歷,其算法時間復(fù)雜度()A.O(n) B.O(e) C.O(n+e) D.O(n*e)6、若用鄰接矩陣存儲有向圖,矩陣中主對角線以下的元素均為零,則關(guān)于該圖拓撲序列的結(jié)構(gòu)是()A.存在,且唯一 B.存在,且不唯一C.存在,可能不唯一 D.無法確定是否存在7、如下有向帶權(quán)圖,若采用迪杰斯特拉(Dijkstra)算法求源點a到其他各頂點的最短路徑,得到的第一條最短路徑的目標頂點是b,

17、第二條最短路徑的目標頂點是c,后續(xù)得到的其余各最短路徑的目標頂點依次是()A.d,e,f B.e,d,f C.f,d,e D.f,e,d8、下列關(guān)于最小生成樹的說法中,正確的是()、最小生成樹的代價唯一、所有權(quán)值最小的邊一定會出現(xiàn)在所有的最小生成樹中、使用普里姆(Prim)算法從不同頂點開始得到的最小生成樹一定相同、使用普里姆算法和克魯斯卡爾(Kruskal)算法得到的最小生成樹總不相同A.僅 B.僅 C.僅、 D.僅、9、已知一棵3階B-樹,如下圖所示。刪除關(guān)鍵字78得到一棵新B-樹,其最右葉結(jié)點中的關(guān)鍵字是()A.60 B.60,62 C.62,65 D.6510、在內(nèi)部排序過程中,對尚未

18、確定最終位置的所有元素進行一遍處理稱為一趟排序。下列排序方法中,每一趟排序結(jié)束都至少能夠確定一個元素最終位置的方法是().簡單選擇排序 .希爾排序 .快速排序 .堆排序 .二路歸并排序A.僅、 B.僅、C.僅、 D.僅、11對一待排序序列分別進行折半插入排序和直接插入排序,兩者之間可能的不同之處是()A.排序的總趟數(shù) B.元素的移動次數(shù)C.使用輔助空間的數(shù)量 D.元素之間的比較次數(shù)二、問答題。41、(10分)設(shè)有6個有序表A、B、C、D、E、F,分別含有10、35、40、50、60和200個數(shù)據(jù)元素,各表中元素按升序排列。要求通過5次兩兩合并,將6個表最終合并成1個升序表,并在最壞情況下比較的

19、總次數(shù)達到最小。請回答下列問題。(1)給出完整的合并過程,并求出最壞情況下比較的總次數(shù)。(2)根據(jù)你的合并過程,描述N(N2)個不等長升序表的合并策略,并說明理由。42、(13分)假定采用帶頭結(jié)點的單鏈表保存單詞,當兩個單詞有相同的后時綴,則可共享相同的后綴存儲空間,例如,“l(fā)oaging”和“being”,如下圖所示。設(shè)str1和str2分別指向兩個單詞所在單鏈表的頭結(jié)點,鏈表結(jié)點結(jié)構(gòu)為(data,next),請設(shè)計一個時間上盡可能高效的算法,找出由str1和str2所指向兩個鏈表共同后綴的起始位置(如圖中字符i所在結(jié)點的位置p)。要求:(1)給出算法的基本設(shè)計思想。(2)根據(jù)設(shè)計思想,采用

20、C或C+或java語言描述算法關(guān)鍵之處給出注釋。(3)說明你所設(shè)計算法的時復(fù)雜度。20131. 已知兩個長度分別為m 和n 的升序鏈表,若將它們合并為一個長度為m+n 的降序鏈表,則最壞情況下的時間復(fù)雜度是A. O(n) B. O(m*n) C. O(min(m,n) D. O(max(m,n)2. 一個棧的入棧序列為1, 2,3, ,n ,其出棧序列是 p1, p2, p3, pn。若p2 = 3,則p3 可能取值的個數(shù)是:A. n-3 B. n- 2 C. n-1 D. 無法確定3. 若將關(guān)鍵字1,2,3,4,5,6,7 依次插入到初始為空的平衡二叉樹T 中,則T 中平衡因子為0 的分支結(jié)

21、點的個數(shù)是A. 0 B. 1 C. 2 D. 34. 已知三叉樹T 中6 個葉結(jié)點的權(quán)分別是2,3,4,5,6,7,T 的帶權(quán)(外部)路徑長度最小是A. 27 B. 46 C. 54 D. 565. 若X 是后序線索二叉樹中的葉結(jié)點,且X 存在左兄弟結(jié)點Y,則X 的右線索指向的是A. X 的父結(jié)點 B. 以Y 為根的子樹的最左下結(jié)點C. X 的左兄弟結(jié)點Y D. 以Y 為根的子樹的最右下結(jié)點6. 在任意一棵非空二叉排序樹T1 中,刪除某結(jié)點v 之后形成二叉排序樹T2,再將v 插入T2 形成二叉排序樹T3。下列關(guān)于T1 與T3 的敘述中,正確的是I. 若v 是T1 的葉結(jié)點,則T1 與T3 不同

22、II. 若v 是T1 的葉結(jié)點,則T1 與T3 相同III. 若v 不是T1 的葉結(jié)點,則T1 與T3 不同IV. 若v 不是T1 的葉結(jié)點,則T1 與T3 相同A. 僅I、III B. 僅I、IV C. 僅II、III D. 僅II、IV7. 設(shè)圖的鄰接矩陣A 如下所示。各頂點的度依次是A. 1,2,1,2 B. 2,2,1,1 C. 3,4,2,3 D. 4,4,2,28. 若對如下無向圖進行遍歷,則下列選項中,不是廣度優(yōu)先遍歷序列的是A. h,c,a,b,d,e,g,f B. e,a,f,g,b,h,c,dC. d,b,c,a,h,e,f,g D. a,b,c,d,h,e,f,g9、下列

23、的AOE網(wǎng)表示一項包含8個活動的工程。通過同時加快若干活動的進度可以縮短整個工程的工期。下列選項中,加快其進度就可以縮短整個工程的工期的是:A c和e B d和e C f 和d D f和h10、在一棵高為2 的5階B樹中,所含關(guān)鍵字的個數(shù)最少是A 5 B 7 C 8 D14A= ( 0,5,5,3,5,7,5,5 ),側(cè)5為主元素;又如A= ( 0,5,5,3,5,1,5,7 ),則A中沒有主元素。假設(shè)A中的n個元素保存在一個一維數(shù)組中,請計一個盡可能高效的算法,找出A的主元素。若存在主元素,則輸出該元素;否則輸出-1。要求:

24、0;    (1)給出算法的基本設(shè)計思想。 (2)根據(jù)設(shè)計思想,采用C或C+或Java語言描述算法,關(guān)鍵之處給出釋。   (3)說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。42.(10分)設(shè)包含4個數(shù)據(jù)元素的集合S= "do","for"," repeat"," while",各元素查找概率依次為:p1=0.35,p2 = 0.15,p3=0. 15,p4=0.35。將S保存在一

25、個長度為4的順序表中,采用折半查找法,查找成功時的平均查找長度為2.2。請回答:(1)若采用順序存儲結(jié)構(gòu)保存S,且要求平均查找長度更短,則元素應(yīng)如何排列?應(yīng)使用何種查找方法?查找成功時的平均查找長度是多少?(2)若采用鏈式存儲結(jié)構(gòu)保存S,且要求平均查找長度更短,則元素應(yīng)如何排列?應(yīng)使用何種查找方法?查找成功時的平均查找長度是多少?20141. 下列程常段的時間復(fù)雜度是count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j+1)count+;A.O(log2n) B.O(n) C.O(nlog2n) D.O(n2)2. 假設(shè)棧初始為空,將中綴表達式轉(zhuǎn)換為等價

26、后綴表達式的過程中,當掃描到f時,棧中的元素依次是A B. C. D. 3. 循環(huán)兩列放在一維數(shù)組A0M-1中,end1指向隊頭元素,end2指向隊尾元素的后一個位置。假設(shè)隊列兩端均可進行入隊和出隊操作,隊列中最多能容納M-1個元素。初始時為空,下列判斷隊空和隊滿的條件中,正確的是A.隊空:end1=end2; 隊滿:end1=(end2+1)modMB.隊空:end1=end2; 隊滿:end2=(end1+1)mod(M-1)C.隊空:end2=(end1+1)modM ; 隊滿:end1=(end2+1)modMD.隊空:end1=(end2+1)modM; 隊滿:end2=(end1+

27、1)mod(M-1)4. 若對如下的二叉樹進行中序線索化,則結(jié)點x的左、右線索指向的結(jié)點分別是A.e,c B.e,a C.d,c D.b,abdxeac5. 將森林F轉(zhuǎn)換為對應(yīng)的二叉樹T,F(xiàn)中葉結(jié)點的個數(shù)等于A.T中葉結(jié)點的個數(shù) B.T中度為1的結(jié)點個數(shù) C.T中左孩子指針為空的結(jié)點個數(shù) D.T中右孩子指針為空的結(jié)點個數(shù)6. 5個字符有如下4種編碼方案,不是前綴編碼的是A.01,0000,0001,001,1 B.011,000,001,010,1C.000,001,010,011,100 D.000,001,010,011,1007. 對如下所示的有向圖進行拓撲排序,得到的拓撲序列可能是A.

28、3,1,2,4,5,6 B.3,1,2,4,6,5 C.3,1,4,2,5,6 D.3,1,4,2,6,51254638. 用哈希(散列)方法處理沖突(碰撞)時可能出現(xiàn)堆積(聚集)現(xiàn)象,下列選項中,會受堆積現(xiàn)象直接影響的是A.存儲效率 B.數(shù)列函數(shù) C.裝填(裝載)因子 D.平均查找長度9.在一棵具有15個關(guān)鍵字的4階B樹中,含關(guān)鍵字的結(jié)點數(shù)最多是A.5 B.6 C.10 D.1510. 用希爾排序方法對一個數(shù)據(jù)序列進行排序時,若第1趟排序結(jié)果為9,1,4,13,7,8,20,23,15,則該趟排序采用的增量(間隔)可能是A.2 B.3 C.4 D.511. 下列選項中,不可能是快速排序第2趟

29、排序結(jié)果的是A.2,3,5,4,6,7,9 B.2,7,5,6,4,3,9 C.3,2,5,4,7,6,9 D.4,2,3,5,7,6,941.(13分)二叉樹的帶權(quán)路徑長度(WPL)是二叉樹中所有葉結(jié)點的帶權(quán)路徑長度之和,給定一棵二叉樹T,采用二叉鏈表存儲,節(jié)點結(jié)構(gòu)為:leftweightright其中葉節(jié)點的weight域保存該結(jié)點的非負權(quán)值。設(shè)root為指向T的根節(jié)點的指針,設(shè)計求T的WPL的算法。要求:(1)給出算法的基本設(shè)計思想;(2)使用C或C+語言,給出二叉樹結(jié)點的數(shù)據(jù)類型定義;(3)根據(jù)設(shè)計思想,采用C或C+語言描述算法,關(guān)鍵之處給出注釋。20151已知程序如下: i

30、nt s(int n)  return (n<=0) ? 0 : s(n-1) +n;  void main()  cout<< s(1);   程序運行時使用棧來保存調(diào)用過程的信息,自棧底到棧頂保存的信息一次對應(yīng)的是  Amain()->S(1)->S(0)   BS(0)->S(1)->main() Cmain()->S(0)

31、->S(1)  DS(1)->S(0)->main() 2先序序列為a,b,c,d的不同二叉樹的個數(shù)是 A13  B14  C15  D163下列選項給出的是從根分別到達兩個葉節(jié)點路徑上的權(quán)值序列,能屬于同一棵哈夫曼樹的是 A24,10,5和 24,10,7  B24,10,5和24,12,7 C24,10,10和 24,14,11  D24,10,5和 24,14,6 4現(xiàn)在有一顆無重復(fù)關(guān)鍵字的平衡二叉樹(AVL樹)

32、,對其進行中序遍歷可得到一個降序序列。下列關(guān)于該平衡二叉樹的敘述中,正確的是A根節(jié)點的度一定為2  B樹中最小元素一定是葉節(jié)點C最后插入的元素一定是葉節(jié)點 D樹中最大元素一定是無左子樹5設(shè)有向圖G=(V,E),頂點集V=V0,V1,V2,V3,邊集E=<v0,v1>,<v0,v2>,<v0,v3>,<v1,v3>,若從頂點V0 開始對圖進行深度優(yōu)先遍歷,則可能得到的不同遍歷序列個數(shù)是 A2  B3   C4   D5 6 求下面帶權(quán)圖的最?。ù鷥r)

33、生成樹時,可能是克魯斯卡(kruskal)算法第二次選中但不是普里姆(Prim)算法(從V4開始)第2次選中的邊是 A(V1,V3)   B(V1,V4)    C(V2,V3)   D(V3,V4) 7下列選項中,不能構(gòu)成折半查找中關(guān)鍵字比較序列的是 A500,200,450,180  B500,450,200,180  C180,500,200,450  D180,200,500,450 8已知字符串S為“abaabaab

34、acacaabaabcc”. 模式串t為“abaabc”, 采用KMP算法進行匹配,第一次出現(xiàn)“失配”(si != ti) 時,i=j=5,則下次開始匹配時,i和j的值分別是 Ai=1,j=0   Bi=5,j=0  Ci=5,j=2  Di=6,j=2  9下列排序算法中元素的移動次數(shù)和關(guān)鍵字的初始排列次序無關(guān)的是 A直接插入排序  B起泡排序  C基數(shù)排序  D快速排序10

35、已知小根堆為8,15,10,21,34,16,12,刪除關(guān)鍵字8之后需重建堆,在此過程中,關(guān)鍵字之間的比較數(shù)是 A1   B2  C3  D4  11希爾排序的組內(nèi)排序采用的是() A直接插入排序  B折半插入排序 C快速排序  D歸并排序41.  用單鏈表保存m個整數(shù),節(jié)點的結(jié)構(gòu)為(data,link),且|data|<n(n為正整數(shù))?,F(xiàn)要求設(shè)計一個時間復(fù)雜度盡可能高效地算法,對于鏈表中絕對值相等的節(jié)點,僅保留第一次

36、出現(xiàn)的節(jié)點而刪除其余絕對值相等的節(jié)點。  例如若給定的單鏈表head如下刪除節(jié)點后的head為 要求:(1) 給出算法的基本思想  (2) 使用c或c+語言,給出單鏈表節(jié)點的數(shù)據(jù)類型定義。  (3) 根據(jù)設(shè)計思想,采用c或c+語言描述算法,關(guān)鍵之處給出注釋。  (4) 說明所涉及算法的時間復(fù)雜度和空間復(fù)雜度。42. 已知有5個頂點的圖G如下圖所示請回答下列問題 (1) 寫出圖G的鄰接矩陣A(行、列下標從0開始)  (2)

37、60;求A2,矩陣A2中位于0行3列元素值的含義是什么? (3) 若已知具有n(n>=2)個頂點的鄰接矩陣為B則,Bm(2<=m<=n)非零元素的含義是什么?2009 1-5:BCDBC6-10:BADBA41.該方法求得的路徑不一定是最短路徑。例如,對于下圖所示的帶權(quán)圖,如果按照題中的原則,從A到C的最短路徑為ABC,事實上其最短路徑為  ADC。  42.(1)算法的基本設(shè)計思想:定義兩個指針變量p和q,初始時均指向頭結(jié)點的下一個結(jié)點。P指針沿鏈表移動;當p指針移動到第k個結(jié)點時,q指針開始與p指針同步移動;當p指針移動到

38、鏈表最后一個結(jié)點時,q指針所指元素為倒數(shù)第k個結(jié)點。以上過程對鏈表僅進行一遍掃描。 (2)算法的詳細實現(xiàn)步驟: count=0,p和q指向鏈表表頭結(jié)點的下一個結(jié)點; 若p為空,轉(zhuǎn); 若count等于k,則q指向下一個結(jié)點;否則,count=count+1; p指向下一個結(jié)點,轉(zhuǎn)步驟; 若count等于k,則查找成功,輸出該結(jié)點的data域的值,返回1;返回; 查找失敗,返回0; 算法結(jié)束。(3)算法實現(xiàn):typedef struct LNode int data; struct LNode * link; * LinkList;int SearchN(LinkList list,int k)L

39、inkList p,q;int count=0; /*計數(shù)器賦初值*/p=q=list->link; /*p和q指向鏈表表頭結(jié)點的下一個結(jié)點*/while(p!=NULL)if(count<k) count+; /*計數(shù)器+1*/else q=q->link;/*q移到下一個結(jié)點*/ p=p->link; /*p移到下一個結(jié)點*/if(count<k)return(0);/*如果鏈表的長度小于k,查找失敗*/ else printf("%d",q->data); /*查找成功*/ return (1);/else/SearchN 2010

40、 1-5:DCDCB 6-11:ACBBDA41.(1)構(gòu)造的散列表如下下標0123456789關(guān)鍵字71481130189(2)查找成功的平均查找長度:ASL成功=12/7。 查找不成功的平均查找長度:ASL不成功=18/7。42.(1)給出算法的基本設(shè)計思想:先將n個數(shù)據(jù)x0x1xpxn-1原地逆置,得到xn-1xpxp-1x0,然后再將前n-p個和后p個元素分別原地逆置,得到最終結(jié)果:xpxp+1xn-1x0x1xp-1。(2)算法實現(xiàn): void reverse(int r,int left,int right) int k=left,j=right,temp; /k等于左邊界left

41、,j等于右邊界right while(k<j)/交換rk和rj temp=rk; rk=rj; rj=temp; k+;/k右移一個位置 j-;/j左移一個位置 void leftShift(int r,int n,int p)if(p>0&&p<n)reverse(r,0,n-1);/將全部數(shù)據(jù)逆置reverse(r,0,n-p-1);/將前n-p個元素逆置reverse(r,n-p,n-1);/將后p個元素逆置(3)說明算法復(fù)雜性:上述算法的時間復(fù)雜度為O(n),空間復(fù)雜度為O(1)。2011 1-5:ABBCC 6-10:DACBA 41.高分筆記 圖

42、最后一題42. (1)算法的基本設(shè)計思想:(5分) 1) 比較笨的方法:將兩升序序列歸并排序,然后求其中位數(shù),時間復(fù)雜度是O(n),空間復(fù)雜度O(n)。 2) 高效的方法:分別求兩個升序序列A和B的中位數(shù),設(shè)為a和b。如果a=b,則a或者b即為所求的中位數(shù)。原因:如果將兩序列歸并排序,則最終序列中,排在子序列ab前邊的元素為先前兩序列中排在a和b前邊的元素;排在子序列ab后邊的元素為先前兩序列a和b后邊的元素。所以子序列ab一定位于最終序列的中間,有因為a=b,顯然a就是中位數(shù)。如果ab(假設(shè)a< p>原因:同樣可以用歸并排序后的序列來驗證,歸并后排序后必然有形如ab的序列出現(xiàn),中

43、位數(shù)必然出現(xiàn)在(a,b)范圍內(nèi)。因此可以做如下處理:舍棄a所在序列A之中比較小的一半,同時舍棄b所在序列B之中比較大的一半。在保留的兩個升序序列中求出新的中位數(shù)a和b,重復(fù)上述過程,直到兩個序列只含一個元素為止,則較小者即為所求中位數(shù)。(2)算法實現(xiàn)(高效方法):(8分)int Search(int A, int B, int n) int s1,e1,mid1,s2,e2,mid2; s1=0;e1=n-1;s2=1;e2=n-1; while(s1!=e1|s2!=e2)mid1=(s1+e1)/2;mid2=(s2+e2)/2;if(Amid1=Bmid2) return Amid1;i

44、f(Amid1< p)/分別考慮奇數(shù)和偶數(shù),保持兩個子數(shù)組元素個數(shù)相等 if(s1+e1)%2=0)/若元素個數(shù)為奇數(shù) s1=mid1;/舍棄A中間點以前部分且保留中間點 e2=mid2; /舍棄B中間點以后部分且保留中間點 /if else/若元素個數(shù)為偶數(shù) s1=mid1+1;/舍棄A中間點以前部分且保留中間點 e2=mid2; /舍棄B中間點以后部分且保留中間點 /else/ifelse if(s1+e1)%2=0)/若元素個數(shù)為奇數(shù)個 e1=mid1;/舍棄A中間點以后部分且保留中間點 s2=mid2;/舍棄B中間點以前部分且保留中間點 /if else /若元素個數(shù)為偶數(shù)個 e

45、1=mid1+1;/舍棄A中間點以后部分且保留中間點 s2=mid2;/舍棄B中間點以前部分且保留中間點 /else/else /while return (As1) /search (3)上述所給算法的時間、空間復(fù)雜度分別是O(log2n)和O(1)。(2分)因為每次總的元素個數(shù)變?yōu)樵瓉淼囊话?,所以有:第一次:元素個數(shù)為n/2=n/(21) 第二次:元素個數(shù)為n/4=n/(22)第k次:元素個數(shù)為n/(2k)最后元素個數(shù)為2則有n/(2k)=2解得k= log2n 1因此:時間復(fù)雜度為O(log2n),而空間復(fù)雜度從上述程序中可看出為O(1)。2012 1-5:BAABC 6-11:CCAD

46、AD41. 高分筆記 排序 最后一題42.(1)算法思想:順序遍歷兩個鏈表到尾結(jié)點時,并不能保證兩個鏈表同時到達尾結(jié)點。這是因為兩個鏈表的長度不同。假設(shè)一個鏈表比另一個鏈表長k個結(jié)點,我們先在長鏈表上遍歷k個結(jié)點,之后同步遍歷兩個鏈表。這樣我們就能夠保證它們同時到達最后一個結(jié)點了。由于兩個鏈表從第一個公共結(jié)點到鏈表的尾結(jié)點都是重合的。所以它們肯定同時到達第一個公共結(jié)點。于是得到算法思路: 遍歷兩個鏈表求的它們的長度L1,L2; 比較L1,L2,找出較長的鏈表,并求L=|L1-L2|;先遍歷長鏈表的L各結(jié)點;同步遍歷兩個鏈表,直至找到相同結(jié)點或鏈表結(jié)束。(2)算法的C語言代碼

47、描述 LinkList Search_First_Common(LinkList L1,LinkList L2)/本算法實現(xiàn)線性時間內(nèi)找到兩個單鏈表的第一個公共結(jié)點  int len1=Length(L1),len2=Length(L2);  LinkList longList,shortlist;/分別指向較長和較短的鏈表  if(len1>len2)  longList=L1->next;  shortlist=L2->next;  L=len1-len

48、2;/表長之差 /if else  longList=L2->next;  shortlist=L1->next;  L=len2-len1;/表長之差  /else  While(L-)  longList=longList->next;  while(longList!=NULL)  if(longList=shortList)/同步尋找共同結(jié)點  return longList;  else  longList=longList->next;&#

49、160; shortlist=shortlist->next;   /else /while  return NULL; /Search_First_Common (3)算法的時間復(fù)雜度為O(len1+len2),空間復(fù)雜度為 O(1)。2013 1-5:DCDBA 6-10:CCDCA 41.(1)給出算法的基本設(shè)計思想:(4分)算法的策略是從前向后掃描數(shù)組元素,標記出一個可能成為主元素的元素Num。然后重新計數(shù),確認Num是否是主元素。算法可分為以下兩步:選取候選的主元素:依次掃描所給數(shù)組中的每個整數(shù),將第一個遇到

50、的整數(shù)Num保存到c中記錄Num的出現(xiàn)次數(shù)為1;若遇 到 的下一個 整 數(shù) 仍 等 于Num則計數(shù)加一,否則計數(shù)減一;當計數(shù)減到0時,將遇到的下一個整數(shù)保存到c中,計數(shù)重新記為1,開始新一輪計數(shù),即從當前位置開始重復(fù)上述過程,直到掃描完全部數(shù)組元素。判斷c中元素是否是真正的主元素:再次掃描該數(shù)組,統(tǒng)計c中元素出現(xiàn)的次數(shù),若大于n/2,則為主元素;否則,序列中不存在主元素。(2)算法實現(xiàn):(7分) int Majority ( int A , int n )   int i,&

51、#160;c, count=1; / / c用來保存候選主元素,count用來計數(shù)  c = A0;  / / 設(shè)置A0為候選主元素  for ( i=1; i<n; i+ )   / / 查找候選主元素 if ( Ai = = c ) count+; / / 對A中的候選主元素計數(shù)

52、 else if ( count > 0)  count-;/ / 處理不是候選主元素的情況 else  / / 更換候選主元素,重新計數(shù) c = Ai; count = 1; /else /for  if ( count>0 )  for ( i=count=0; i<n; i+ ) / / 統(tǒng)計候

53、選主元素的實際出現(xiàn)次數(shù) if ( Ai = = c )  count+;  if ( count> n/2 ) return c; / / 確認候選主元素  else return -1; / / 不存在主元素/Majority42.(1)采用順序存儲結(jié)構(gòu),數(shù)據(jù)元素按其查找概率降序排列。(2分)采用順序查找方法。(1分)查找成功時的平均查找長度= 0.

54、35×1+0.35×2+0.15×3+0.15×4=2.1。(2分)  (2)【答案一】采用鏈式存儲結(jié)構(gòu),數(shù)據(jù)元素按其查找概率降序排列,構(gòu)成單鏈表。(2分)采用順序查找方法。(1分)查找成功時的平均查找長度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。(2分)【答案二】采用二叉鏈表存儲結(jié)構(gòu),構(gòu)造二叉排序樹,元素存儲方式見下圖。(2分)2014 1-5:CBADC 6-11:DDDDBC41解答:考查二叉樹的帶權(quán)路徑長度,二叉樹的帶權(quán)路徑長度為每個葉子結(jié)點的深度與權(quán)值之積的總和

55、,可以使用先序遍歷或?qū)哟伪闅v解決問題。1)算法的基本設(shè)計思想:基于先序遞歸遍歷的算法思想是用一個static變量記錄wpl,把每個結(jié)點的深度作為遞歸函數(shù)的一個參數(shù)傳遞,算法步驟如下:若該結(jié)點是葉子結(jié)點,那么變量wpl加上該結(jié)點的深度與權(quán)值之積;若該結(jié)點非葉子結(jié)點,那么若左子樹不為空,對左子樹調(diào)用遞歸算法,若右子樹不為空,對右子樹調(diào)用遞歸算法,深度參數(shù)均為本結(jié)點的深度參數(shù)加一;最后返回計算出的wpl即可?;趯哟伪闅v的算法思想是使用隊列進行層次遍歷,并記錄當前的層數(shù),當遍歷到葉子結(jié)點時,累計wpl;當遍歷到非葉子結(jié)點時對該結(jié)點的把該結(jié)點的子樹加入隊列;當某結(jié)點為該層的最后一個結(jié)點時,層數(shù)自增1;

56、隊列空時遍歷結(jié)束,返回wpl2)二叉樹結(jié)點的數(shù)據(jù)類型定義如下:typedef struct BiTNode int weight; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;3)算法代碼如下:基于先序遍歷的算法:intWPL(BiTreeroot) return wpl_PreOrder(root,0);/intintwpl_PreOrder(BiTreeroot,intdeep) static int wpl=0;/定義一個static變量存儲wpl if(root->lchild=NULL&&root->lchild=NULL)/若為葉子結(jié)點,累積wpl wpl+=deep*root->weight; if(root->lchild!=NULL)/若左子樹不空,對左子樹遞歸遍歷 wpl_PreOrder(root->lchild,deep+1); if(root->rchild!=NULL)/若右子樹不空,對右子樹遞歸遍歷 wpl_PreOrder(root->rchild,deep+1); return wpl;/wpl_PreOrder基于層次遍歷的算法:#defineMaxSize100 /設(shè)置隊列的最大容量int wpl_Le

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論