數(shù)據(jù)結(jié)構(gòu)與算法40講浙大春試題ds本研

1、浙江大學(xué)94題一、完成下列各題（每題 5 分）（1）已知a,b為TRUE ,X=60,i=3,j=5. 求PASCAL表達(dá)式a AND NOT (X5) AND (ij +5) OR ab AND b 的值。寫出計(jì)算設(shè)計(jì)一數(shù)據(jù)結(jié)構(gòu)，用來表示某一的PASCAL 或C語言的相應(yīng)語句。儲(chǔ)戶的基本信息：賬號(hào)、年月日、儲(chǔ)蓄類型 、存入累加數(shù)、利息、帳面總數(shù)。二、（7分）設(shè)計(jì)-PASCAL 或C語言的函數(shù) atoi(x).其中X 為字符串，由0-910個(gè)數(shù)字符和表示正負(fù)數(shù)的-組成，返回值為整型樹值三、（8分）對于-組 a (ARRAY 1.20 OFEGER ) 有下列PASCAL 程序：PROCEDUR

2、E S(x,t,b:EGER);VARm: BEGINEGERIF t=THEN BEGIN m:=(t+b) DIV 2IF x=am THEN wrin (x,m)ELSEIF xAm THEN S (x,m+1,b)ENDELSEwrin (NO)END.試說明該過程S（x,t,b）的功用，若已知a 的內(nèi)容為：11 14 15 18 19 21 24 33 45 55 49 55 62 71 78 83 85 91 94 97請S（33，1，20）和S（35，1，20）調(diào)用時(shí)輸出結(jié)果。四、（20分）設(shè)有大小為mxm的二維數(shù)組（方陣），試設(shè)計(jì)下列程序（PASCAL或C）；（1） 作出該數(shù)組

3、的統(tǒng)計(jì)（即統(tǒng)計(jì)各種數(shù)值出現(xiàn)的次數(shù)）。（2） 變換該方陣，中每一元素被它的8個(gè)鄰域的平均數(shù)所代替。（附：元素A的8個(gè)鄰域定義為a0-a7 見下圖五、（8分） 一帶權(quán)無向圖的鄰接矩陣如右圖 ， 試畫出它的一棵最小生成樹。六、（12分） 廣義表的結(jié)點(diǎn)定義如下：TYPEpo= node;node=RECORDtag: 0.1;tp:po;CASEtag OF0: (data: daype);1: (hp:po)END;lists= po;說明下列算法的功能，并畫出執(zhí)行該算法后，P（算法中p, t, m, n, r, q 均為指針）所指向的廣義表結(jié)構(gòu)。A(p,t)beginq:=NIL;while pN

4、IL do beginif p.tag 0 then beginm:=p.hp;A(m,n);pp:=nend; r:=p.tp;p.tp:=q; q:=p;p:=r end;t :=q;end.七、(12分)一棵二叉樹的結(jié)點(diǎn)定義如下：typedefstructstructnode node; node kind key:node *link 2;typedef structframe frame; structframe left;* ptr;node;frame nodepath4;# define path(j)nodepath (j)&4試畫出執(zhí)行如下程序后右圖所示的二叉樹形狀，其中p

5、ath(j) 的初值為： ji-1 i i+1path(j).ptr abdpath(j).left-falsefalsei+2etruevoid R (i)ipath (i+1).ptr-link path(i+2).left=path(i+2) .ptr -link path (i+2).left; path (i-2) .ptr- linkpath(i+2) .left=path (i-1) .ptr ;path (i).ptr - linkpath (i+1).left =path (i+2) .ptr; path (i+1).ptr =path(i+2).ptr;八、（18分）數(shù)組 H 1：1000 中存放著1000個(gè)大小不同的正整數(shù);（1） 選擇一分類算法使能最快的得到其中10個(gè)最大的數(shù)，簡明理由；（