答案請(qǐng)答在答題紙上，答在本試題上的答案一律無(wú)效

[注] 編寫程序可選用pascal 或 c 語(yǔ)言

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

一、簡(jiǎn)答問題：[30分]

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

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

3．簡(jiǎn)述面向?qū)ο蠓椒ǖ奶攸c(diǎn)

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

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

二、選擇題： [20分]

1． 已知一算術(shù)表達(dá)式的中綴形式為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． 利用逐點(diǎn)插入法建立序列(50，72，43，85，75，20，35，45，65，30)對(duì)應(yīng)的二叉排序樹以后，查找元素35要進(jìn)行（    ）元素間的比較。

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

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

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

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

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

5．若一個(gè)有向圖的鄰接矩陣中，主對(duì)角線以下的元素均為零，則該圖的拓?fù)溆行蛐蛄?     )

      A. 存在       B. 不存在 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

}

}

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

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

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

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

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

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

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

四、編寫程序，求字符串中的字符平臺(tái)。

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

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

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

六、編寫算法：

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

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

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

七、編寫算法：

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

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

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

例：               A   

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

       E       F  G