1、數據結構精選考研試題注:編寫程序可選用任一 種高語言,算法描述可采用類語言,必 要時加上注釋 一、答復以下問題：20 分1、算法的定義和性質2、為什么說數組與廣義表是線性表的推廣 3、什么是結構化程序設計4、哈希方法的根本思想 5、給出一不 穩定排序方法名稱與實例 二、構 造結果：24分 確定x:=x+1語句 在下面程序段中的頻率,要求寫出分析 過程. for i:=1 to n do for j:=1to I do畫出對長度為for k:=1 to j do x:=x+1的有序表進行折半查找的判定樹,并求其在等概率時查找成功 的平均查找長度.一棵二叉樹如右圖,給出對這棵二叉樹進行前序、 中序

2、、后序遍歷的結果序列.假設用于通訊的電文僅個字母組成,字母在電文中出現的頻率分別為2, 3, 5, 7, 11, 4, 13, 15,試為這個字母設計哈夫曼編碼.在地址空間為015的散列區中,對以下關鍵字序列構G造哈希表, 關鍵字序列為,H(x)=i/2,其中i為關 鍵字中第一字母在字母表中的序號.要 求用線性探測開放定址法處理沖突,并 求出在等概率情況下查找成功的平均查 找長度.構造有7個元素組成的線性表一實例,是進行快速排序時比較次 數最少的初始排序.三、寫一算法,完成對這棵二叉樹的左右子樹的交換, 設二叉樹以二叉鏈表作存儲結構.15分 四、編寫一非遞歸算法,對一棵二叉排 序樹實現中序遍歷

3、.15分 五、編 寫程序,完成以下功能：15分1.讀入整數序列,以整數0作為序列 的結束標志,建立一個單鏈表.2.實現單鏈表原地逆轉,即單鏈表中結點指 針方向反轉,反轉操作不使用額外的鏈表結點,可使用臨時工作單元.例:輸入序列為:1,8, 4, 3, 0六、給出有向圖G的鄰接表表示.找出其一 棵最小生成樹.11分注:編寫程序可選用任一種高語言,算法描 述可采用類語言,必要時加上注釋 一、 答復以下問題：20分1、算法的定義 和性質2、為什么說數組與廣義表是線性表的推廣 3、什么是結構化程 序設計 4、哈希方法的根本思想 5、給出一不穩定排序方法名稱與實例 二、構造結果：24分確定x:=x+1語

4、句在下面程序段中的頻率,要求寫出 分析過程. for i:=1 to n do forj:=1 to I do畫出對長度為for k:=1 to j do x:=x+1 的有序表進行折半查找的判定樹,并求其在等概率時查找成功的平均查找長度.一棵二叉樹如右圖,給出對這棵二叉樹進行前序、 中序、后序遍歷的結果序列.假設用于通訊的電文僅個字母組成,字母在電文中出現的頻率分別為2, 3, 5, 7, 11, 4, 13, 15,試為這個字母設計哈夫曼編碼.在地址空間為015的散列區中,對以下關鍵字序列構G造哈希表, 關鍵字序列為,H(x)=i/2,其中i為關 鍵字中第一字母在字母表中的序號.要 求用線

5、性探測開放定址法處理沖突,并 求出在等概率情況下查找成功的平均查 找長度.構造有7個元素組成的線性表一實例,是進行快速排序時比較次 數最少的初始排序.三、寫一算法,完成對這棵二叉樹的左右子樹的交換, 設二叉樹以二叉鏈表作存儲結構.15分 四、編寫一非遞歸算法,對一棵二叉排 序樹實現中序遍歷.15分 五、編 寫程序,完成以下功能：15分1.讀入整數序列,以整數0作為序列 的結束標志,建立一個單鏈表. 2.實 現單鏈表原地逆轉,即單鏈表中結點指 針方向反轉,反轉操作不使用額外的鏈表結點,可使用臨時工作單元.例: 給出有向圖G的鄰接表表示.找出其一輸入序列為:1,8, 4, 3, 0六、棵最小生成樹

6、.11分注編精選公文范文,治理類,工作總結類,工作方案類文檔,感謝閱讀下載 4 寫程序可選用PASCAL或 C語言 算法描述采用類語言,應加上必要的注 釋所有答案均要求寫在做題紙上 一、答復以下問題15分1.結構化程序設計2.面向對象開發方法與面向過程開發方法的不同之處 3.數據 類型含義與作用4.穩定排序與不穩定 排序 二、簡述方法與原因20分 1.分別采用堆排序、快速排序、直接插 入排序、歸并排序算法對初始狀態為遞 增序列的表按遞增順序排序,給出最省 時間與最費時間的算法名稱,簡述原因. 2.實現有向圖的拓撲排序能否用圖的深 度搜索模式來查找假設能請簡述方法, 假設不能,請簡述原因.3.有

7、n個非零的數,僅要求將負數排列在正數 的前面,但并不要求對其排序,簡述處 理方法.4.說明在圖的遍歷中,設置訪問標志數組的作用.5.在一個連通無向圖上,欲求從一點 VI 到另一點VJ所經結點數目最少的路徑, 在深度優先搜索、廣度優先搜索、從一 精選公文范文,治理類,工作總結類,工作方案類文檔,感謝閱讀下載 5 點到其余各頂點的最短路徑或圖的其它 算法中,你認為最好選擇那種方法為基 礎,簡述原因.三、構造結果25分1.二叉樹按二叉鏈表方式存放,其中的data域為char類型,已 有按前序方式構造二叉樹的算法,假設輸 入序列為AEOCEDEEGDC,口青給出 構造的相應二叉樹.2.Ackerman

8、函數定義如下：n+1當m=0 時 akm(m,n) = akm(m-1,1) 當0,n=0 時 akm(m-1, akm(m,n-1) 當0,n #時寫出akm(2,1)時調用時變 化過程與執行結果.3.對于正整數A、B,說明下面程序段定義了什么 函數功能,要求重寫程序段,使之完成 原函數功能,且執行時間僅可能短. Unsigned int f(a,b) int a,b; if (a*b=0) return (a+b)elsereturn(f(b-(b/a)*a,a);(注：b/a相當整除) 4.寫出在中序線索樹BT中找結點X的 精選公文范文,治理類,工作總結類,工作方案類文檔,感謝閱讀下載

9、6 后繼結點的函數過程.5.對以下關鍵字序列建立哈希表,哈希函數為 H=關鍵字中第一個字母在字母表中的序 號MOD 7,用線性探測再散列法或鏈 地址法之一處理沖突,要求構造一個裝 填因子為的哈希表,并求出等概率情況 下查找成功與不成功的平均查找長度. 四、有二叉排序樹采用二叉鏈表方式存 放,樹中結點值各不相同,欲 得到 一個大到小的結點值遞減序列,簡述處 理方法思路,用非遞歸形式寫出算法.10分1. 一棵樹采用孩子-兄弟方式存放,結點結構為fch dansletaib vel 其中fch表示指向第一個孩 子,nisib表示指向下一個兄弟,level表 示結點層次. 設根結點層次為1, 其它以此

10、類推,編寫一算法,將樹中所 有結點層次值置入相應level域.10分 六、以順序存儲結構表示串,設計算法, 求串S中出現的第一個最長重復子串及其位置并分析算法的時間復雜度.10分七、編寫程序,要求精選公文范文,治理類,工作總結類,工作方案類文檔,感謝閱讀下載 7 完成：建立一個帶頭結點的線性鏈表,用以存放輸入的二進制數,鏈表中 每個結點的data域存放一個二進制位.在此鏈表上實現對二進制數加1的運算, 并輸出運算結果.分10注:編寫程序可用PASCAL或C語 言；算法描述可采用類語言,加上必要 注釋；一、解釋和簡答以下問題： 1算法的定義和特性2抽象數據類 型 3廣義表與字符串屬于線性表 的理

11、 4封裝5排序算法的穩定性6結構化程序設計二、寫 出要求結果： 1.一二叉樹中序序列為DBGEAFC ,后序序列為DGEBFCA ,給出其對應的二叉樹.2.給定權值8, 12, 4, 5, 26,16, 9,構造一棵帶權路徑長度最短的二叉樹,并計算其帶權路徑長度性表,要求重新排列,使所有的正數均 在非正數之前,要求用最小交換次數 實現,你認為應采用什么方法4.只想得到N個元素序列中第K個最精選公文范文,治理類,工作總結類,工作方案類文檔,感謝閱讀下載 8 大元素之前的局部遞減有序序列,列出3 種速度快的方法名稱與原因.5.在地址空間為012的散列區中,對以下關 鍵字序列建哈希表：.用線性探測法

12、處理 沖突,求出在等概率的情況下查找成功 與不成功的平均查找長度.6.下面給出求N價hanoi塔的過程： PROCEDURE hanoi(n： integer,； x,y,z： char);begin if n=1 thenmove(x,1,z) else hanoi(n-1,x,z,y);move(x,n,z); hanoi(n-1,y,x,z) end 請寫由執行hanoi(3,a,b,c)0寸遞歸過程的 實在參量變化過程及move的搬動過程. 三、數學歸納法證實非空滿 K叉樹的葉 子結點數目為(K-1)N+1 ,其中N為分支 結點數目. 四、編寫程序,判斷一 帶頭結點的雙向鏈表是否對稱,

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

14、質 6 ,二、寫出要求結果1. PROGRAM PF(OUTPUT); VER T,M:INTEGER;FUNCTIONF(N:INTEGER):INTEGER; BEGIN M:=N+M;F:=M ENDBEGINM:=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.寫出程序輸出結果,說明為什么T的樹出結果不同.2.有過程定義如下：PROCEDUREPRIT(N:INTEGER); BEGIN VAR N1:INTEGER;N1:=TRU

15、NC(N/10);TRUNC(x)表示取 x 的整數局部 S:=S*10+(N MOD 10); IF N10 THEN PRIT(N1); WRITELN(N MOD 10) END; 問：置S初值 為0,用PRIT調用此過程,寫出打印結 果；當執行完此次調用后,S值是多少 3.給定一組權值,構造 一棵哈夫 曼樹,并計算帶權路徑長度. 4.將 樹轉換成二叉樹 5.對給定以下關 鍵字序列(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug),哈希函數 H 為Key的第一字母表中序號MOD7,采用線性探測再散列方法處理沖突, 要求：構造一個裝填因子為的哈希表 求出等概率情況下查找成功

16、與查找不 成功的平均查找長度 6.在m行n列的 稀疏矩陣中,有七個非零元素,假設用十 字鏈 表表示,共 需要多少個結點 精選公文范文,治理類,工作總結類,工作方案類文檔,感謝閱讀下載 11 三、編寫一程序,要求打印以下的楊輝 三角形10分11 11 21 n行 1 3 3 11 4 6 4 1 1 5 1010 5 12 1 6 15 20 15 1 :四、一個數組中元素為正數或負數,編寫一程 序,完成在On時間內原地重排數組, 不要求整個排序,只要求負數排在正數 之前.10分五、二叉樹按二叉鏈表方式存放：編寫統計任一二叉樹中非終端結點數目的非遞歸算法 10分編寫求一二叉樹高度的遞歸算法.5分

17、六、設有向圖以鄰接表方式存儲,請利用隊列技術編寫一 個判別圖中是否存在頂點 Vi到頂點Vj 路徑的算法.12分七、有如下 單鏈表,n為偶數.要求寫出一個時間復雜度為On,輔助空間為0(1) 的算法,將上述鏈表轉換成：即注:編寫程序可選用任一種高級語言 一、簡答問題：15分1.結構化程序設計；2.簡述面向對象開發方法的特點；3.何謂程序中的千年蟲問題,簡述一種解決問題的方法；4.給出抽象數據類型和特征,并舉例說明； 5.簡述廣義表屬于線性結構的理. 二、寫出要求結果45分1.有函數定義如下：FUNCTIONGC(M,N:INTEGER);INTEGER BEGIN IF N=0 THEN GC:

18、=MELSEGC:=GC(N , M MOD N) END 寫出此函數功能,并改寫它,使其執行 速度僅可能地短.2.設T、M為全程量, 有函數定義如下： FUNCTIONFA(N:INTEGER) :INTEGERBEGINM:=N+M;FA:=M;END在主程序段中,有如下語句：M:=10;T:=(M+2)*FA(10);WRITELN(T);M:=10;T:=FA(10)*(M+2);WRITELN(T);寫出程序輸出結果,說明為什么 T的輸 出結果不同的原因.3.對以下關鍵字序列建立哈希表：,哈希函數為 H(K尸MOD 7.用線性探測法處理沖突, 要求構造一個裝填因子為的哈希表,并 分別

19、計算出在等概率情況下查找成功與不成功的平均查找長度.4.在數軸上有N個彼此相鄰不交的區間,每個區 間的下界和上界都是整數.N個區間順序為1N.要查找給定的X落入的區 間號,你認為應怎樣組織數據結構,選 擇什么方法最快,并簡述原因5.對N個元素組成的線性表進行快速排序 時,所需進行的比較次數依賴于這 N個 元素的初始排列,對N=7,給出快速排序的一個最好情況的初始排列實 例.6.在前序線索樹上,要找出結點P的直接后繼結點,請寫出相關語句. ltag lc data rtag rc 7.給出循環隊列中元 素個數的計算式.8.有向圖的拓撲排序能否用圖的深度搜索模式來查找 假設能,請簡述方法,假設不能

20、,請簡述原 因. 9.寫出三個形如A:=B的語句, 完成將單鏈表LA整表釋放的功能,可 利用鏈棧指針AVo 三、編寫程序,統計在輸入字符串中各個不同字 符出現的頻度并將結果存入文件10分 四、兩個線性表A、B,均以帶頭結點的單鏈表作存儲結構,且表中元素按 值遞增有序排列.設計算法,求出A與B的交集C,要求C另開辟存儲空 間,要求C同樣以元素值的遞增有序的樹按二叉鏈表形式存儲. 寫一個建 立二叉樹的算法. 答案請答在做題 紙上,答在本試題上的答案一律無效 注編寫程序可選用PASCAL或C語 言 算法描述采用類語言,算法應加 上必要的注釋,所有答案均要求寫在答 題紙上一、簡答問題：30分1.結構化

21、程序設計 2.面向對象程 序設計與面向過程程序設計各自的特點 與區別3.簡述隊列與廣義表屬于線性 表的理4.簡述不穩定排序含義、并給出證實某一種排序方法是不穩定的 排序方法 5 .函數的副作用 二、選擇題：20分1 .下面方法可以判斷出一個有向圖中是否有環 A.深度優先遍歷 B.拓撲排序C.最短 路徑D.關鍵路徑2.一算術表 達式的中綴形式為 A+B *C-D/E ,后綴 形式為ABC *+DE/-,其前綴形式為. A, 小+B*C/DE B. 八+B*CD/E C.-+*ABC/DE D.-+A*BC/DE 3.假設二 叉樹采用二叉鏈表存儲結構,要交換其 所有分支結點左右子樹的位置,利用遍

22、歷方法最適宜. A.前序B.中序 C.后序D.按層次 4.排序趟數與 序列的原始狀態有關的排序方法是 排 序法.A.插入B.選擇C.冒泡D.快 速5.下面給出的四種排序法中排序法是不穩定性排序法.A.插入B.冒 泡C.二路歸并D.堆 6.假設需在 O的時間內完成對數組的排序,且要求 排序是穩定的,那么可選擇的排序方法是： A .快速排序B.堆排序C.歸并排序D. 直接插入排序7.下述二叉樹中,滿足性質：從任一結點出發到根的路徑 上所經過的結點序列按其關鍵字有序A.二叉排序樹 B.哈夫曼樹 C. AVL樹 D.堆 8.以下排序算法中, 算法 可能會出現下面情況：初始數據有序時,花費時間反而最多.

23、A、堆排序B、冒泡排序C、快速排序 D、SHELL排 序 9.設循環隊列中數組的下標范 圍是1n,其頭尾指針分別為f, r,假設隊 列中元素個數為.A、r-f B、r-f+1C、mod n D、mod n10.假設一個有向圖的鄰接矩陣中,主對角線以下的元素 均為零,那么該圖的拓撲有序序列 A、存在B、不存在三、寫出要求結果：50分1 .以下C與PASCAL函數的功能相同有如下C函數定義：有如下PASCAL過程定義：void bin(int b , int n) PROCEDURE bin BEGIN if (n=1) b1=1; b2=1; if (n=1) b1=1; b2=1; else

24、bin(b, n-1); else bin(b, n-1);bn+1=1;bn+1=1; For (i=n; i>=2; i-) For i=n downto 2 do bi= bi+ bi-1 bi= bi+ bi-1 END 假設調用 bin(A, 5),給出A數組中第1個至第6個 數組元素的輸出結果.2.給出求N階hanoi塔的函數定義如下：hanoi(int n, char x, char y, char z); if (n=1) move(x,1,z)else hanoi(n-1,x,z,y); move(x,n,z); hanoi(n-1,y,x,z) 請寫出執行hanoi(

25、3,a,b,c對遞歸函數的實在參量變 化及move的搬動過程.3.已知一個循環單鏈表la,av是可利用棧的頭 指針,請用3個賦值語句,完成將整個 循環單鏈表釋放的功能.4.在地址空間為0-12的散列區中,對以下關鍵字 序列：建哈希表,設哈希函數為H=i/2,其中i為關鍵字中的第一個字母在字母 表中的序號,處理沖突可選用線性探測 法或鏈地址法之一,要求構造哈希表, 并求出在等概率的情況下查找成功與不 成功的平均查找長度.5.在排序連續順序文件中采用折半查找方法 查找記錄存在與否的過程可以借助 于一棵折半判定樹來模擬,樹中結點的 值為記錄在文件中的位置序號.假設文件中有l 7個記錄,請畫出這棵折半

26、 判定樹；當文件中有n個記錄時,給出該判定樹的深度.6.設某城市有N個車站,并有M條公交線路 連接這些車站,設這些公交車都是 單向的,這N個車站順序編號為0至 N-1 ,要求輸入該城市的公交線路數、車 站個數以及各公交線路上各站編號,要 求從站0出發乘公交車至站N-1的最少 換車次數,簡述應如何設置數據結構、 應當采用的根本處理方法.注編寫程序可選用PASCAL或C語言算法描述采用類語言,應加上必要的注釋 所有答案 均要求寫在做題紙上 一、答復問 題15分1 .結構化程序設計 2.面 向對象開發方法與面向過程開發方法的 不同之處3.數據類型含義與作用4.穩 定排序與不穩定排序二、簡述方法與原

27、因20分1.分別采用堆排序、快速排序、直接插入排序、歸并排序算 法對初始狀態為遞增序列的表按遞精選公文范文,治理類,工作總結類,工作方案類文檔,感謝閱讀下載 19增順序排序,給出最省時間與最費時間 的算法名稱,簡述原因.2.實現有向圖的拓撲排序能否用圖的深度搜索 模式來查找假設能請簡述方法,假設不能, 請簡述原因.3.有n個非零的數,僅要求將負數排列在正數的前面, 但并不要求對其排序,簡述處理方法.4.說明在圖的遍歷中,設置訪問標志數 組的作用.5.在一個連通無向圖上,欲求從一點VI到另一點VJ所經 結點數目最少的路徑,在深度優先搜索、 廣度優先搜索、從一點到其余各頂點的 最短路徑或圖的其它算

28、法中,你認為最 好選擇那種方法為根底,簡述原因.三、構造結果25分1.二叉樹按二叉鏈表方式存放,其中的data域為char 類型,已有按前序方式構造二叉樹的算法,假設輸入序列為 AEO CCD口 EDD G口港給出構造的相 應二叉樹.2. Ackerman函數定義如下：n+1當m=0時akm(m,n) = akm(m-1,1)當 0,n=0 時 精選公文范文,治理類,工作總結類,工作方案類文檔,感謝閱讀下載 akm(m-1, akm(m,n-1)當 m 0,n w 田寸 寫出akm(2,1)時調用時變化過程與執行 結果. 3.對于正整數A、B,說 明下面程序段定義了什么函數功能,要 求重寫程序

29、段,使之完成原函數功能, 且執行時間僅可能短.Unsigned intf(a,b) int a,b;if (a*b=0)return (a+b) else return(f(b-(b/a)*a,a); (注：b/a相當整除)4.寫出在中序線索樹BT中找結點X的后繼結點的函 數過程.5.對以下關鍵字序列建立哈希表,哈希函數為H=關鍵字中第 一個字母在字母表中的序號)MOD 7,用線性探測再散列法或鏈地址法之一處 理沖突,要求構造一個裝填因子為的哈 希表,并求出等概率情況下查找成功與 不成功的平均查找長度.四、有二叉排序樹采用二叉鏈表方式存放, 樹中結點值各不相同,欲得到一個大到 小的結點值遞減序

30、列,簡述處理方法思 路,用非遞歸形式寫出算法.10分五、一棵樹采用孩子-兄弟方式存放,結點結構為 fch data nsib level 其中fch表示指向第一個孩子,nisib表 示指向下一個兄弟,level表示結點層次. 設根結點層次為1,其它以此類推,編寫 一算法,將樹中所有結點層次值置入相 應level域.10分六、 以順序存儲結構表示串,設計算法,求串S中 出現的第一個最長重復子串及其位置并 分 析算法的時間復雜度.10分七、 編寫程序,要求完成： 建立一個帶 頭結點的線性鏈表,用以存放輸入的二 進制數,鏈表中每個結點的data域存放 一個二進制位.在此鏈表上實現對二進制數加1的運算

31、,并輸出運算結果.10分注編寫程序可選用 Pascal或C語言,算法描述采用類語言1997 年一、 簡答以下問題：15分 1.結構化程序設計目的、結構、方法 2. 面向對象程序設計語言的特征 3.程序測試目的及程序可能存在的錯 誤類型 4.常用的參數傳遞方式的 名稱與作用 5.為什么說數組和廣義表是線性表的推廣二、寫出要求結果31.給定權值7, 3,6, 12,15,構造相應哈夫曼樹,并計算其帶權路徑長度.2.有一組關鍵碼49, 397, 76, 13, 27,43,采用堆排序方法,請寫出每趟排 序結果.3.在后序線索樹中,要找出結點P的前趨結點,請寫出有關語 句 Ltag Lc data Rtag Rc 4. 快速 排序方法中,能否用隊列代替棧,請簡 要說明理. 5.設有關鍵字序列32, 53, 78,12, 25, 62, 43,哈希函數H(K)=K mod