西北大學2002年C語言考研試題

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

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

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

一、簡答問題：[30分]

1．結構化程序設計（目的、構成與方法）

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

3．簡述面向對象方法的特點

4．線性結構與非線性結構的差別

5．算法特性與算法時間復雜度

二、選擇題： [20分]

1． 已知一算術表達式的中綴形式為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)對應的二叉排序樹以后，查找元素35要進行（    ）元素間的比較。

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

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

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

4． 若需在O（nlog2n）的時間內完成對數組的排序，且要求排序是穩定的，則可選擇的排序方法是:

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

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

      A. 存在       B. 不存在 

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

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

7． 下述二叉樹中，哪一種滿足性質：從任一節點出發到根的路徑上所經過的節點序列按其關鍵字有序 (     )

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

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

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

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

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

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

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

三、寫出要求結果：[50分]

1．    下列C與PASCAL函數的功能相同

有C函數定義如下：         有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

寫出此函數功能，并改寫它，使其執行速度僅可能的短。

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(3,a,b,c)時遞歸函數的實在參量變化及move的搬動過程。

3．在前序線索樹中，要找出X結點的后繼結點，請寫出相關語句

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

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

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

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

8．已知二叉排序樹，現要求得到結點的遞減有序的排列，請說明實現此要求應采用的方法思路。

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

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

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

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

六、編寫算法：

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

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

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

七、編寫算法：

樹采用孩子-兄弟方式存放，結點結構為

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

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

例：               A   

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

       E       F  G