答案請答在答題紙上，答在本試題上的答案一律無效

[注] 編寫程序可選用pascal 或 c 語言

算法描述采用類語言，算法應(yīng)加上必要的注釋，所有答案均要求寫在答題紙上

一、簡答問題：[30分]

1．結(jié)構(gòu)化程序設(shè)計（目的、構(gòu)成與方法）

2．簡述棧、隊列、串、數(shù)組的共同點和不同點，它們屬于線性表原因

3．簡述面向?qū)ο蠓椒ǖ奶攸c

4．線性結(jié)構(gòu)與非線性結(jié)構(gòu)的差別

5．算法特性與算法時間復(fù)雜度

二、選擇題： [20分]

1． 已知一算術(shù)表達式的中綴形式為A＋B *C-D/E，后綴形式為ABC *+DE/-，其前綴形式為(    )。

     A. –A+B*C/DE    B. –A+B*CD/E   C.-+*ABC/DE    D.-+A*BC/DE

2． 利用逐點插入法建立序列(50，72，43，85，75，20，35，45，65，30)對應(yīng)的二叉排序樹以后，查找元素35要進行（    ）元素間的比較。

    A．4次     B．5次     C. 7次     D．10次

3．在有n個葉子結(jié)點的哈夫曼樹中，其結(jié)點總數(shù)為 (     )  。

    A、不確定 B、2n     C、2n+1    D、2n-1

4． 若需在O（nlog2n）的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是:

      A．快速排序    B.堆排序    C.歸并排序   D.直接插入排序

5．若一個有向圖的鄰接矩陣中，主對角線以下的元素均為零，則該圖的拓撲有序序列(     )

      A. 存在       B. 不存在 

6． 將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是 (     )

A. n         B. 2n－1      C. 2n        D. n-1

7． 下述二叉樹中，哪一種滿足性質(zhì)：從任一節(jié)點出發(fā)到根的路徑上所經(jīng)過的節(jié)點序列按其關(guān)鍵字有序 (     )

      A.二叉排序樹  B. 哈夫曼樹   C. AVL樹  D. 堆

8． 已知待排序的n個元素可分為n/k個組，每個組包含k個元素，且任一組內(nèi)的各元素均分別大于前一組內(nèi)的所有元素和小于后一組內(nèi)的所有元素，若采用基于比較的排序，其時間下界應(yīng)為(     )

   A. O（nlog2n）  B. O(nlog2k)  C. O(klog2n)   D. O(klog2k)

9．數(shù)組A[1..5,1..6]的每個元素占5個單元，將其按行優(yōu)先次序存儲在起始地址為1000的連續(xù)內(nèi)存單元中，則A[5，5]的地址是 (     )。

   A、1140    B、1145       C、1120       D、1125

10. 在有n個葉子結(jié)點的哈夫曼樹中，其結(jié)點總數(shù)為(     )。

  A、不確定   B、2n  C、2n+1       D、2n-1

三、寫出要求結(jié)果：[50分]

1．    下列C與PASCAL函數(shù)的功能相同

有C函數(shù)定義如下：         有PASCAL過程定義如下：

int gc(:int m, n)              FUNCTION GC(M,N:INTEGER);INTEGER

  {                          BEGIN

if (n==0 ) return(m);          I F N=0 THEN GC:=M

else retun (n，m /n);            ELSE GC:=GC(N，M MOD N)                          

   }                          END

寫出此函數(shù)功能，并改寫它，使其執(zhí)行速度僅可能的短。

2．給出求N階hanoi塔的函數(shù)定義如下：

  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)；

}

}

請寫出執(zhí)行hanoi(3,a,b,c)時遞歸函數(shù)的實在參量變化及move的搬動過程。

3．在前序線索樹中，要找出X結(jié)點的后繼結(jié)點，請寫出相關(guān)語句

Ltag   Lc    Data  Rtag   Rc
4．一棵非空的二叉樹其前序序列與后序序列正好相反，給出滿足條件的二叉樹。

5．在數(shù)軸上有n個彼此不交的相鄰區(qū)間，每個區(qū)間下、上界都是整數(shù)，按區(qū)間位置從左到右依次編號為1~N。試問：要查找某個給定值x所在區(qū)間，你認為應(yīng)選擇什么方法查找最快，簡述原因。

6．已知關(guān)鍵字序列為：（75, 33, 52, 41, 12, 88, 66, 27）哈希表長為10，哈希函數(shù)為： H(K)=K MOD 7, 解決沖突用線性探測再散列法，要求構(gòu)造哈希表，并求出等概率下查找成功與不成功的平均查找長度。

7．只想得到N個元素序列中第K個最大元素之前的部分遞減有序序列（K<<N），列出3種速度快的方法名稱與原因。

8．已知二叉排序樹，現(xiàn)要求得到結(jié)點的遞減有序的排列，請說明實現(xiàn)此要求應(yīng)采用的方法思路。

四、編寫程序，求字符串中的字符平臺。

一個字符串中的任意一個子序列，若子序列中各字符均相同則稱為字符平臺。編程要求；輸入任意一字符串S時，輸出S中長度最大的所有字符平臺的起始位置及所含字符，注意字符平臺有可能不止一個。[10分]

五、編寫算法，要求完成：

已知二叉樹采用二叉鏈表方式存放，要求對二叉樹從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左右孩子的編號，同一個結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，請回答采用什么次序的遍歷方式實現(xiàn)編號？并給出在二叉樹中結(jié)點的數(shù)據(jù)域部分填寫實現(xiàn)如上要求編號的非遞歸算法。[13分]

六、編寫算法：

（1）    要求二叉樹按二叉鏈表形式存儲，寫一個建立二叉樹的算法。

（2）編寫計算二叉樹最大寬度的算法。

二叉樹最大寬度指：二叉樹所有層中結(jié)點個樹的最大值[15分]

七、編寫算法：

樹采用孩子-兄弟方式存放，結(jié)點結(jié)構(gòu)為

fch    data   nsib level
其中fch 表示指向第一個孩子，nisib表示指向下一個兄弟, level表示結(jié)點層次。設(shè)根結(jié)點層次為1，其它以此類推，

編寫一算法，將樹中所有結(jié)點層次值置入相應(yīng)level域，并要求由根開始逐層輸出樹中的各條邊，邊輸出格式為（Ki,Kj）。 [12分]

例：               A   

 B      C     D           輸出為： AB,AC,AD,BE,BF,CG

       E       F  G