數(shù)據(jù)結(jié)構(gòu)精選考研試題

1、數(shù)據(jù)結(jié)構(gòu)精選考研試題注:編寫程序可選用任一種高語言,算法描述可采用類語言,必要時加上注釋一、答復(fù)以下問題：20分1、算法的定義和性質(zhì)2、為什么說數(shù)組與廣義表是線性表的推廣？3、 什么是結(jié)構(gòu)化程序設(shè)計？4、哈希方法的根本思想5、給出一不穩(wěn)定排序方法名稱與實例二、構(gòu)造結(jié)果：24分確定x:=x+1語句在下面程序段中的頻率,要求寫出分析過程.fori:=1tondoforj:=1的判定樹,并求其在等概率時查找成功的平均查找長度.一棵二叉樹如右圖,給出對這棵二叉樹進行前序、中序、后序遍歷的結(jié)果序個字母組成,字母在電文中出現(xiàn)的頻率toIdo畫出對長度為fork:=1tojdox:=x+1的有序表進行折半查

2、找列假設(shè)用于通訊的電文僅輸入序列為:1,8,4,3,0六、分別為2,3,5,7,11,4,13,15,碼.在地址空間為015的散列區(qū)中,對以下關(guān)鍵字序列構(gòu)G造哈希表,關(guān)鍵字序列為,H(x尸i/2,其中i為關(guān)鍵字中第一字母在字母表中的序號.要求用線性探測開放定址法處理沖突,并求出在等概率情況下查找成功的平均查找長度.構(gòu)造有7個元素組成的線性表一實例,是進行快速排序時比擬次數(shù)最少的初始排序.三、寫一算法,完成對這棵二叉樹的左右子樹的交換,設(shè)二叉樹以二叉鏈表作存儲結(jié)構(gòu).15分四、編寫一非遞歸算法,對一棵二叉排序樹實現(xiàn)中序遍歷.15分五、編寫程序,完成以下功能：15分1.讀入整數(shù)序列,以整數(shù)0作為序列

3、的結(jié)束標(biāo)志,建立一個單鏈表.2.實現(xiàn)單鏈表原地逆轉(zhuǎn),即單鏈表中結(jié)點指針方向反轉(zhuǎn),反轉(zhuǎn)操作不使用額外的鏈表結(jié)點,可使用臨時工作單元.例:試為這個字母設(shè)計哈夫曼編給出有向圖G的鄰接表表示.找出其一棵最小生成樹.11分注:編寫程序可選用任一種高語言,算法描述可采用類語言,必要時加上注釋一、 答復(fù)以下問題：20分1、算法的定義和性質(zhì)2、為什么說數(shù)組與廣義表是線性表的推廣？3、什么是結(jié)構(gòu)化程序設(shè)計？4、哈希方法的根本思想5、給出一不穩(wěn)定排序方法名稱與實例二、構(gòu)造結(jié)果：24分 確定x:=x+1語句在下面程序段中的頻率,要求寫出分析過程.fo門:=1tondoforfork:=1tojdox:=x+1的有序

4、表進行折半查找的判定樹,并求其在等概率時查找成功的平均查找長度.一棵二叉樹如右圖,給出對這棵二叉樹進行前序、中序、后序遍歷的結(jié)果序個字母組成,字母在電文中出現(xiàn)的頻率j:=1toIdo畫出對長度為列假設(shè)用于通訊的電文僅分別為2,3,5,7,11,4,13,15,試為這個字母設(shè)計哈夫曼編碼.在地址空間為015的散列區(qū)中,對以下關(guān)鍵字序列構(gòu)G造哈希表,關(guān)鍵字序列為,H(x尸i/2,其中i為關(guān)鍵字中第一字母在字母表中的序號.要求用線性探測開放定址法處理沖突,并求出在等概率情況下查找成功的平均查找長度.構(gòu)造有7個元素組成的線性表一實例,是進行快速排序時比擬次數(shù)最少的初始排序.三、寫一算法,完成對這棵二叉

5、樹的左右子樹的交換,設(shè)二叉樹以二叉鏈表作存儲結(jié)構(gòu).15分四、編寫一非遞歸算法,對一棵二叉排序樹實現(xiàn)中序遍歷.15分五、編寫程序,完成以下功能：15分1.讀入整數(shù)序列,以整數(shù)0作為序列的結(jié)束標(biāo)志,建立一個單鏈表.2.實現(xiàn)單鏈表原地逆轉(zhuǎn),即單鏈表中結(jié)點指針方向反轉(zhuǎn),反轉(zhuǎn)操作不使用額外的鏈表結(jié)點,可使用臨時工作單元.例:給出有向圖G的鄰接表表示.找出其一輸入序列為:1,8,4,3,0六、棵最小生成樹.11分注編寫程序可選用PASCAL或C語言算法描述采用類語言,應(yīng)加上必要的注釋所有答案均要求寫在做題紙上一、答復(fù)以下問題15分1.結(jié)構(gòu)化程序設(shè)計2.面向?qū)ο箝_發(fā)方法與面向過程開發(fā)方法的不同之處3.數(shù)據(jù)類

6、型含義與作用4.穩(wěn)定排序與不穩(wěn)定排序二、簡述方法與原因20分1.分別采用堆排序、快速排序、直接插入排序、歸并排序算法對初始狀態(tài)為遞增序列的表按遞增順序排序,給出最省時間與最費時間的算法名稱,簡述原因.2.實現(xiàn)有向圖的拓?fù)渑判蚰芊裼脠D的深度搜索模式來查找？假設(shè)能請簡述方法,假設(shè)不能,請簡述原因.3.有n個非零的數(shù),僅要求將負(fù)數(shù)排列在正數(shù)的前面,但并不要求對其排序,簡述處理方法.4.說明在圖的遍歷中,設(shè)置訪問標(biāo)志數(shù)組的作用.5.在一個連通無向圖上,欲求從一點VI到另一點VJ所經(jīng)結(jié)點數(shù)目最少的路徑,在深度優(yōu)先搜索、廣度優(yōu)先搜索、從一精選公文范文,治理類,工作總結(jié)類,工作方案類文檔,感謝閱讀下載5點到

7、其余各頂點的最短路徑或圖的其它算法中,你認(rèn)為最好選擇那種方法為基礎(chǔ),簡述原因.三、構(gòu)造結(jié)果25分1.二叉樹按二叉鏈表方式存放,其中的data域為char類型,已有按前序方式構(gòu)造二叉樹的算法,假設(shè)輸入序列為ABOCEEDEDZGDC,Di青給出構(gòu)造的相應(yīng)二叉樹.2.Ackerman函數(shù)定義如下：n+1當(dāng)m=0時akm(m,n)=akm(m-1,1)當(dāng) 廿0,n=0時akm(m-1,akm(m,n-1)當(dāng)0,n#時寫出akm(2,1)時調(diào)用時變化過程與執(zhí)行結(jié)果.3.對于正整數(shù)A、B,說明下面程序段定義了什么函數(shù)功能,要求重寫程序段,使之完成原函數(shù)功能,且執(zhí)行時間僅可能短.Unsignedintf(

8、a,b)inta,b;if(a*b=0)return(a+b)elsereturn(f(b-(b/a)*a,a);(注：b/a相當(dāng)整除)4.寫出在中序線索樹BT中找結(jié)點X的精選公文范文,治理類,工作總結(jié)類,工作方案類文檔,感謝閱讀下載6后繼結(jié)點的函數(shù)過程.5.對以下關(guān)鍵字序列建立哈希表,哈希函數(shù)為H=關(guān)鍵字中第一個字母在字母表中的序號MOD7,用線性探測再散列法或鏈地址法之一處理沖突,要求構(gòu)造一個裝填因子為的哈希表,并求出等概率情況下查找成功與不成功的平均查找長度.四、有二叉排序樹采用二叉鏈表方式存放,樹中結(jié)點值各不相同,欲得到一個大到小的結(jié)點值遞減序列,簡述處理方法思路,用非遞歸形式寫出算法

9、.10分1.一棵樹采用孩子-兄弟方式存放,結(jié)點結(jié)構(gòu)為fchdansletaibvel其中fch表示指向第一個孩子,nisib表示指向下一個兄弟,level表示結(jié)點層次.設(shè)根結(jié)點層次為1,其它以此類推,編寫一算法,將樹中所有結(jié)點層次值置入相應(yīng)level域.10分六、以順序存儲結(jié)構(gòu)表示串,設(shè)計算法,求串S中出現(xiàn)的第一個最長重復(fù)子串及其位置并分析算法的時間復(fù)雜度.10分七、編寫程序,要求精選公文范文,治理類,工作總結(jié)類,工作方案類文檔,感謝閱讀下載7完成：建立一個帶頭結(jié)點的線性鏈表,用以存放輸入的二進制數(shù),鏈表中每個結(jié)點的data域存放一個二進制位.在此鏈表上實現(xiàn)對二進制數(shù)加1的運算,并輸出運算結(jié)果

10、.分10注:編寫程序可用PASCAL或C語言；算法描述可采用類語言,加上必要注釋；一、解釋和簡答以下問題：1算法的定義和特性2抽象數(shù)據(jù)類型3廣義表與字符串屬于線性表的理4封裝5排序算法的穩(wěn)定性6結(jié)構(gòu)化程序設(shè)計二、寫出要求結(jié)果：1.一二叉樹中序序列為DBGEAFC,后序序列為DGEBFCA,給出其對應(yīng)的二叉樹.2.給造一棵帶權(quán)路徑長度最短的二叉樹,并性表,要求重新排列,使所有的正數(shù)均在非正數(shù)之前,要求用最小交換次數(shù)實現(xiàn),你認(rèn)為應(yīng)采用什么方法？定權(quán)值8,12,4,5,26,16,9,構(gòu)計算其帶權(quán)路徑長度4.只想得到N個元素序列中第K個最大元素之前的局部遞減有序序列,列出3種速度快的方法名稱與原因.

11、5.在地址空間為012的散列區(qū)中,對以下關(guān)鍵字序列建哈希表：.用線性探測法處理沖突,求出在等概率的情況下查找成功與不成功的平均查找長度.6.下面給出求N價hanoi塔的過程：PROCEDUREhanoi(n：integer；x,y,z：char);beginifn=1thenmove(x,1,z)elsehanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z)end請寫由執(zhí)行hanoi(3,a,b,c)0寸遞歸過程的實在參量變化過程及move的搬動過程.三、數(shù)學(xué)歸納法證實非空滿K叉樹的葉子結(jié)點數(shù)目為(K-1)N+1,其中N為分支結(jié)點數(shù)目.四、 編寫程序,判斷一

12、帶頭結(jié)點的雙向鏈表是否對稱,對稱是指表中各元素滿足ai=an-i+1結(jié)點結(jié)構(gòu)為如下：(10分)nextdadaprior五、有一個英文書目構(gòu)成的文件；讀入該文件,對這一書目單按字典排序,將結(jié)果以文件方式存儲.編程實現(xiàn)之.六、二叉樹按鏈表方式存放,且樹中結(jié)點的關(guān)鍵字均不同.寫一個判別給定二叉樹是否為二叉排序樹的非遞歸算法.寫一個算法,確定一個N個頂點的無向圖是否包含回路,此算法的時間代價應(yīng)為O注:編寫程序可選用盤Pascal或C語言,算法描述可選用類語言,必要時加上注釋一、簡答以下問題：1.結(jié)構(gòu)化程序設(shè)計2.參數(shù)傳遞的常用方式及含義3.數(shù)據(jù)類型4.幾種根本數(shù)據(jù)結(jié)構(gòu)的名稱及特征5.算法定義與性質(zhì)6

13、.二、寫出要求結(jié)果1.PROGRAMPF(OUTPUT);VERT,M:INTEGER;FUNCTIONF(N:INTEGER):INTEGER;BEGINM:=N+M;F:=MENDBEGINM:=10;T:=(M+1)*F(10);WRITELN(T);M:=10;T:=F(10)*(M+1);WRITELN(T);M:=10;T:=M*F(10)+F(10);WRITELN(T);END.寫出程序輸出結(jié)果,說明為什么T的樹出結(jié)果不同.2.有過程定義如下：PROCEDUREPRIT(N:INTEGER);BEGINVARN1:INTEGER;N1:=TRUNC(N/10);TRUNC(x)

14、表示取x的整數(shù)局部 S:=S*10+(NMOD10);IFN10THENPRIT(N1);WRITELN(NMOD10)END;問：置S初值為0,用PRIT調(diào)用此過程,寫出打印結(jié)果； 當(dāng)執(zhí)行完此次調(diào)用后,S值是多少？3.給定一組權(quán)值,構(gòu)造一棵哈夫曼樹,并計算帶權(quán)路徑長度.4.將樹轉(zhuǎn)換成 二叉 樹5.對給 定以 下關(guān)鍵 字序列(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug),哈希函數(shù)H為Key的第一字母表中序號MOD7,采用線性探測再散列方法處理沖突,要求：構(gòu)造一個裝填因子為的哈希表求出等概率情況下查找成功與查找不成功的平均查找長度6.在m行n列的稀疏矩陣中,有七個非零元素,假

15、設(shè)用十字鏈表表示,共需要多少個結(jié)點？精選公文范文,治理類,工作總結(jié)類,工作方案類文檔,感謝閱讀下載11三、編寫一程序,要求打印以下的楊輝三角形10分111121n行133114641151010512161520151:四、一個數(shù)組中元素為正數(shù)或負(fù)數(shù),編寫一程序,完成在On時間內(nèi)原地重排數(shù)組,不要求整個排序,只要求負(fù)數(shù)排在正數(shù)之前.10分五、二叉樹按二叉鏈表方式存放：編寫統(tǒng)計任一二叉樹中非終端結(jié)點數(shù)目的非遞歸算法10分編寫求一二叉樹高度的遞歸算法.5分六、設(shè)有向圖以鄰接表方式存儲,請利用隊列技術(shù)編寫一個判別圖中是否存在頂點Vi到頂點Vj路徑的算法.12分七、有如下單鏈表,n為偶數(shù).要求寫出一個

16、時間復(fù)雜度為On,輔助空間為0(1)的算法,將上述鏈表轉(zhuǎn)換成：即注:編寫程序可選用任一種高級語言一、簡答問題：15分1.結(jié)構(gòu)化程序設(shè)計；2.簡述面向?qū)ο箝_發(fā)方法的特點；3.何謂程序中的千年蟲問題,簡述一種解決問題的方法；4.給出抽象數(shù)據(jù)類型和特征,并舉例說明；5.簡述廣義表屬于線性結(jié)構(gòu)的理.二、寫出要求結(jié)果45分1.有函數(shù)定義如下：FUNCTIONGC(M,N:INTEGER);INTEGERBEGINIFN=0THENGC:=MELSEGC:=GC(N,MMODN)END寫出此函數(shù)功能,并改寫它,使其執(zhí)行速度僅可能地短.2.設(shè)T、M為全程量,有函數(shù)定義如下：FUNCTIONFA(N:INTE

17、GER):INTEGERBEGINM:=N+M;FA:=M;END在主程序段中,有如下語句：M:=10;T:=(M+2)*FA(10);WRITELN(T);M:=10;T尸F(xiàn)A(10)*(M+2);WRITELN(T);寫出程序輸出結(jié)果,說明為什么T的輸出結(jié)果不同的原因.3.對以下關(guān)鍵字序列建立哈希表： ,哈希函數(shù)為H(K尸MOD7.用線性探測法處理沖突,要求構(gòu)造一個裝填因子為的哈希表,并分別計算出在等概率情況下查找成功與不成功的平均查找長度.4.在數(shù)軸上有N個彼此相鄰不交的區(qū)間,每個區(qū)間的下界和上界都是整數(shù).N個區(qū)間順序為1No要查找給定的X落入的區(qū)間號,你認(rèn)為應(yīng)怎樣組織數(shù)據(jù)結(jié)構(gòu),選擇什么

18、方法最快,并簡述原因5.對N個元素組成的線性表進行快速排序時,所需進行的比擬次數(shù)依賴于這N個元素的初始排列,對N=7,給出快速排序的一個最好情況的初始排列實例.6.在前序線索樹上,要找出結(jié)點P的 直 接 后 繼 結(jié) 點 , 請 寫 出 相 關(guān) 語句.ltaglcdatartagrc7.給出循環(huán)隊列中元素個數(shù)的計算式.8.有向圖的拓?fù)渑判蚰芊裼脠D的深度搜索模式來查找？假設(shè)能,請簡述方法,假設(shè)不能,請簡述原因.9.寫出三個形如A:=B的語句,完成將單鏈表LA整表釋放的功能,可利用鏈棧指針AVo三、編寫程序,統(tǒng)計在輸入字符串中各個不同字符出現(xiàn)的頻度并將結(jié)果存入文件10分四、兩個線性表A、B,均以帶頭

19、結(jié)點的單鏈表作存儲結(jié)構(gòu),且表中元素按值遞增有序排列.設(shè)計算法,求出A與B的交集C,要求C另開辟存儲空間,要求C同樣以元素值的遞增有序的樹按二叉鏈表形式存儲.寫一個建立二叉樹的算法.答案請答在做題紙上,答在本試題上的答案一律無效注編寫程序可選用PASCAL或C語言算法描述采用類語言,算法應(yīng)加上必要的注釋,所有答案均要求寫在答題紙上一、簡答問題：30分1.結(jié)構(gòu)化程序設(shè)計2.面向?qū)ο蟪绦蛟O(shè)計與面向過程程序設(shè)計各自的特點與區(qū)別3.簡述隊列與廣義表屬于線性表的理4.簡述不穩(wěn)定排序含義、并給出證實某一種排序方法是不穩(wěn)定的排序方法5.函數(shù)的副作用二、選擇題：20分1.下面方法可以判斷出一個有向圖中是否有環(huán)A

20、.深度優(yōu)先遍歷B.拓?fù)渑判駽.最短路徑D.關(guān)鍵路徑2.一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E,后綴形式為ABC*+DE/-,其前綴形式為.A.小+B*C/DEB.八+B*CD/EC.-+*ABC/DED.-+A*BC/DE3.假設(shè)二叉樹采用二叉鏈表存儲結(jié)構(gòu),要交換其所有分支結(jié)點左右子樹的位置,利用遍歷方法最適宜.A.前序B.中序C.后序D.按層次4.排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是排序法.A.插入B.選擇C.冒泡D.快速5.下面給出的四種排序法中排序法是不穩(wěn)定性排序法.A.插入B.冒泡C.二路歸并D.堆6.假設(shè)需在O的時間內(nèi)完成對數(shù)組的排序,且要求排序是穩(wěn)定的,那么可選擇的排序方法

21、是：A.快速排序B.堆排序C.歸并排序D.直接插入排序7.下述二叉樹中,滿足性質(zhì)： 從任一結(jié)點出發(fā)到根的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字有序A.二叉排序樹B.哈夫曼樹C.AVL樹D.堆8.以下排序算法中,算法可能會出現(xiàn)下面情況：初始數(shù)據(jù)有序時,花費時間反而最多.A、堆排序B、冒泡排序C、快速排序D、SHELL排序9.設(shè)循環(huán)隊列中數(shù)組的下標(biāo)范圍是1n,其頭尾指針分別為f,r,假設(shè)隊列中元素個數(shù)為.A、r-fB、r-f+1C、modnD、modn10.假設(shè)一個有向圖的鄰接矩陣中,主對角線以下的元素均為零,那么該圖的拓?fù)溆行蛐蛄蠥、存在B、不存在三、寫出要求結(jié)果：50分1.以下C與PASCAL函數(shù)的

22、功能相同有如下C函數(shù)定義：有如下PASCAL過程定義：voidbin(intb,intn)PROCEDUREbinBEGINif(n=1)b1=1;b2=1;if(n=1)b1=1;b2=1;elsebin(b,n-1);elsebin(b,n-1);bn+1=1;bn+1=1;For(i=n;i=2;i-)Fori=ndownto2dobi=bi+bi-1bi=bi+bi-1END假設(shè)調(diào)用bin(A,5),給出A數(shù)組中第1個至第6個數(shù)組元素的輸出結(jié)果.2.給出求N階hanoi塔的函數(shù)定義如下：hanoi(intn,charx,chary,charz);if(n=1)move(x,1,z)el

23、sehanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z)請寫出執(zhí)行hanoi(3,a,b,c對遞歸函數(shù)的實在參量變化及move的搬動過程.3.已知一個循環(huán)單鏈表la,av是可利用棧的頭指針,請用3個賦值語句,完成將整個循環(huán)單鏈表釋放的功能.4.在地址空間為0-12的散列區(qū)中,對以下關(guān)鍵字序列：建哈希表,設(shè)哈希函數(shù)為H=i/2,其中i為關(guān)鍵字中的第一個字母在字母表中的序號,處理沖突可選用線性探測法或鏈地址法之一,要求構(gòu)造哈希表,并求出在等概率的情況下查找成功與不成功的平均查找長度.5.在排序連續(xù)順序文件中采用折半查找方法查找記錄存在與否的過程可以借助于一棵折

24、半判定樹來模擬,樹中結(jié)點的值為記錄在文件中的位置序號.假設(shè)文件中有l(wèi)7個記錄,請畫出這棵折半判定樹；當(dāng)文件中有n個記錄時,給出該判定樹的深度.6.設(shè)某城市有N個車站,并有M條公交線路連接這些車站,設(shè)這些公交車都是單向的,這N個車站順序編號為0至N-1,要求輸入該城市的公交線路數(shù)、車站個數(shù)以及各公交線路上各站編號,要求從站0出發(fā)乘公交車至站N-1的最少換車次數(shù),簡述應(yīng)如何設(shè)置數(shù)據(jù)結(jié)構(gòu)、應(yīng)當(dāng)采用的根本處理方法.注編寫程序可選用PASCAL或C語言算法描述采用類語言,應(yīng)加上必要的注釋所有答案均要求寫在做題紙上一、答復(fù)問題15分1.結(jié)構(gòu)化程序設(shè)計2.面向?qū)ο箝_發(fā)方法與面向過程開發(fā)方法的不同之處3.數(shù)據(jù)

25、類型含義與作用4.穩(wěn)定排序與不穩(wěn)定排序二、簡述方法與原因20分1.分別采用堆排序、快速排序、直接插入排序、歸并排序算法對初始狀態(tài)為遞增序列的表按遞精選公文范文,治理類,工作總結(jié)類,工作方案類文檔,感謝閱讀下載19增順序排序,給出最省時間與最費時間的算法名稱,簡述原因.2.實現(xiàn)有向圖的拓?fù)渑判蚰芊裼脠D的深度搜索模式來查找？假設(shè)能請簡述方法,假設(shè)不能,請簡述原因.3.有n個非零的數(shù),僅要求將負(fù)數(shù)排列在正數(shù)的前面,但并不要求對其排序,簡述處理方法.4.說明在圖的遍歷中,設(shè)置訪問標(biāo)志數(shù)組的作用.5.在一個連通無向圖上,欲求從一點VI到另一點VJ所經(jīng)結(jié)點數(shù)目最少的路徑,在深度優(yōu)先搜索、廣度優(yōu)先搜索、從一

26、點到其余各頂點的最短路徑或圖的其它算法中,你認(rèn)為最好選擇那種方法為根底,簡述原因.三、構(gòu)造結(jié)果25分1.二叉樹按二叉鏈表方式存放,其中的data域為char類型,已有按前序方式構(gòu)造二叉樹的算法,假設(shè)輸入序列為ABDCDEEDDG口誦給出構(gòu)造的相應(yīng)二叉樹.2.Ackerman函數(shù)定義如下：n+1當(dāng)m=0時akm(m,n)=akm(m-1,1)當(dāng)廿0,n=0時精選公文范文,治理類,工作總結(jié)類,工作方案類文檔,感謝閱讀下載20akm(m-1,akm(m,n-1)當(dāng)m0,nw 田寸寫出akm(2,1)時調(diào)用時變化過程與執(zhí)行結(jié)果.3.對于正整數(shù)A、B,說明下面程序段定義了什么函數(shù)功能,要求重寫程序段,使

27、之完成原函數(shù)功能,且執(zhí)行時間僅可能短.Unsignedintf(a,b)inta,b;if(a*b=0)return(a+b)elsereturn(f(b-(b/a)*a,a);(注：b/a相當(dāng)整除)4.寫出在中序線索樹BT中找結(jié)點X的后繼結(jié)點的函數(shù)過程.5.對以下關(guān)鍵字序列建立哈希表,哈希函數(shù)為H=關(guān)鍵字中第一個字母在字母表中的序號)MOD7,用線性探測再散列法或鏈地址法之一處理沖突,要求構(gòu)造一個裝填因子為的哈希表,并求出等概率情況下查找成功與不成功的平均查找長度.四、有二叉排序樹采用二叉鏈表方式存放,樹中結(jié)點值各不相同,欲得到一個大到小的結(jié)點值遞減序列,簡述處理方法思路,用非遞歸形式寫出算

28、法.10分五、一棵樹采用孩子-兄弟方式存放,結(jié)點結(jié)構(gòu)為fchdatansiblevel其中fch表示指向第一個孩子,nisib表示指向下一個兄弟,level表示結(jié)點層次.設(shè)根結(jié)點層次為1,其它以此類推,編寫一算法,將樹中所有結(jié)點層次值置入相應(yīng)level域.10分六、以順序存儲結(jié)構(gòu)表示串,設(shè)計算法,求串S中出現(xiàn)的第一個最長重復(fù)子串及其位置并分析算法的時間復(fù)雜度.10分七、編寫程序,要求完成：建立一個帶頭結(jié)點的線性鏈表,用以存放輸入的二進制數(shù),鏈表中每個結(jié)點的data域存放一個二進制位.在此鏈表上實現(xiàn)對二進制數(shù)加1的運算,并輸出運算結(jié)果.10分注編寫程序可選用Pascal或C語言,算法描述采用類語言1997年 一、簡答以下問題：15分1.結(jié)構(gòu)化程序設(shè)計目的、結(jié)構(gòu)、方法2.面向?qū)ο蟪绦蛟O(shè)計語言的特征3.程序測試目的及程序可能存在的錯誤類型4.常用的參數(shù)傳遞方式的名稱與作用5.為什么說數(shù)組和廣義表是線性表的推廣二、寫出要計算其帶權(quán)路徑長度.2.有一組43,采用堆排序方法,請寫出每趟排序結(jié)果.3.在后序線索樹中,要找出結(jié)點P的前趨結(jié)點,請寫出有關(guān)語句LtagLcdataRtagRc4.快速排序方法中,能否用隊列代替棧,請簡要說明理.5.設(shè)有關(guān)鍵字序列函數(shù)H(K尸Kmod7,用線性探測再散列方法處理沖突,要求構(gòu)造一個裝填因子為的哈希表,并分別計算出在等概率情況下查找成功與查找不成功的平均查找