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

寫出要求結果[45分]
1. 有函數定義如下,
FUNCTIONGC(M ,N:INTEGERG):INTEGER;
BEGIN
IF N:=0 THEN GC:=M
ELSE GC:=GC(N,M MOD N)
END
寫出此函數功能,并改寫它,使其執行速度僅可能的短.
2.設T. M為全程量,有函數定義如下,
FUNTIONA(N:INTEGER)INTEGER
BEGIN
M:=N+M;FA=M;
END
在上程序段中,有如下語句:
M:=10;T:=(M+2)*FA(10); WRILELN(T)
M:=10;T:=FA(10)*(M+2); WRILELN(T)
寫出程序輸出結果,說明為什么T的輸出結果不同的原因.
3.. 對以下關鍵宇序列建立哈希表;(SUN,MON,TUE,WED,THE,FRI,SAT),哈希函數為H(K)=(關鍵宇中第一個字母在字母表中的序號)MOD7線性探測法處理沖突,耍求構造一個裝填因子為0.7的哈希表;并分別計算出在等概率情況下查找成功與不成功的平均查找長度.
4..在數軸上有N個彼此相臨不交的區間,每個區間下界上界都是整數.N個區間順序為1一N.要查找給定的X落入的區間號,您認為應怎樣組織數據結構,選擇什么方法最快,簡述原因.
5..對N個元素組成的線性表進行快速排序時,所需進行的比較次數依賴于這N
個元素的初始排列.對N=7,給出快速排序的一個最好椿情況的初始排列實
例(7個元素可取自集合{l,2,3,4,5,6,7}).
6.在前序線索樹上,要找出結點p的直接后繼結點,請寫出相關浯句
ltag lc data rtag rc
7.給出循環隊列中元素個數的計算式(設隊最大長度為N,隊首指針FROUNT,隊尾指針REAR)
8.有向圖的拓撲排序能否用圖的深度搜索模式來查找
若能,請簡述方法,若不能,請簡述原因.
9.寫三個形如A=B的語句,完成將單鏈表LA整表釋放的功能.可利用堆棧指針AV.
一,簡答問題:(15分)
1.結構化程序設計.
2.簡述面向對象開發方法的特點.
3.何謂程序中的千年蟲問題,簡述一種解決問題的方法.
4. 給出抽象數據類型的特征,并舉例說明.
5. 簡述廣義表屬于線性結構的理由.
第 1 頁
四.編寫程序,統計在輸入宇符串中各個不同字符出現的頻度并將結果存入文
件(字符串中的合法字符為A-Z這26個字母和0-9這10個數字). [10分]
五.己知兩個線性表A ,B均以帶頭結點的單鏈表作存儲結構,且表中元索按值遞增有序排列.設計算法求出A與B的交集C,要求C另開辟存儲空間,要求C同樣以元素值的遞增序的單鏈表形式存貯[8分]
六,要求二叉樹按二叉鏈表形式存儲,
(1)寫一個建立二叉樹的算法.
(2)寫一個判別給定的二叉樹是否是完全二叉樹的算法.
完全二又樹定義力:深度為K.具有N個結點的二又樹的每--個結點都與深
度為K的滿二叉樹中編號從1至N的結點一一對應.此題以此定義為準.[l2分]
七.給定一公園的導游圖,自給適當的數據結構,編寫算法實現下列要求:
游客從大門進入,選擇以一條最佳路線,使游客可以不重復的游覽各景點,最后
回到大門. [l0分] "