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