【正文】 Ａ．16902 Ｂ．16904 Ｃ．14454 Ｄ．答案A, B, C均不對(duì)答：（57列60行＋31行）2字節(jié)＋10000=16902(A)( B )5. 設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角部分（如下圖所示）按行序存放在一維數(shù)組B[ 1, n(n1)/2 ]中，對(duì)下三角部分中任一元素ai,j(i≤j), 在一維數(shù)組B中下標(biāo)k的值是：Ａ．i(i1)/2+j1 Ｂ．i(i1)/2+j Ｃ．i(i+1)/2+j1 Ｄ．i(i+1)/2+j解：注意B的下標(biāo)要求從1開始。先用第一個(gè)元素去套用，可能有B和C；再用第二個(gè)元素去套用B和C，B=2而C＝3（不符）；所以選B6. 【91初程P78】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。有一個(gè)二維數(shù)組A，行下標(biāo)的范圍是0到8，列下標(biāo)的范圍是1到5，每個(gè)數(shù)組元素用相鄰的4個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址。假設(shè)存儲(chǔ)數(shù)組元素A[0,1]的第一個(gè)字節(jié)的地址是0。存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是 A 。若按行存儲(chǔ)，則A[3,5]和A[5,3]的第一個(gè)字節(jié)的地址分別是 B 和 C 。若按列存儲(chǔ)，則A[7,1]和A[2,4]的第一個(gè)字節(jié)的地址分別是 D 和 E 。供選擇的答案A～E：①28 ② 44 ③ 76 ④ 92 ⑤ 108⑥ 116 ⑦ 132 ⑧ 176 ⑨ 184 ⑩ 188答案：ABCDE=8, 3, 5, 1, 67.【94程P12】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。有一個(gè)二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是0到7，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的體積是 A 個(gè)字節(jié)。假設(shè)存儲(chǔ)數(shù)組元素A[1,0]的第一個(gè)字節(jié)的地址是0，則存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是 B 。若按行存儲(chǔ)，則A[2,4]的第一個(gè)字節(jié)的地址是 C 。若按列存儲(chǔ)，則A[5,7]的第一個(gè)字節(jié)的地址是 D 。供選擇的答案A～D：①12 ② 66 ③ 72 ④ 96 ⑤ 114 ⑥ 120 ⑦ 156 ⑧ 234 ⑨ 276 ⑩ 282 （11）283 （12）288答案：ABCD=12, 10, 3, 9三、簡(jiǎn)答題（每小題5分，共15分）1. KMP算法的設(shè)計(jì)思想是什么？它有什么優(yōu)點(diǎn)？2. （軟件技術(shù)？）已知二維數(shù)組Am,m采用按行優(yōu)先順序存放，每個(gè)元素占K個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址為Loc(a11)，請(qǐng)寫出求Loc(aij)的計(jì)算公式。如果采用列優(yōu)先順序存放呢？解：公式教材已給出，此處雖是方陣，但行列公式仍不相同；按行存儲(chǔ)的元素地址公式是： Loc(aij)= Loc(a11) +[ (i1)*m+(j1) ] * K按列存儲(chǔ)的元素地址公式是： Loc(aij)= Loc(a11) +[ (j1)*m+(i1) ] * K3.【全國專升本資格考試】遞歸算法比非遞歸算法花費(fèi)更多的時(shí)間，對(duì)嗎？為什么？答：不一定。時(shí)間復(fù)雜度與樣本個(gè)數(shù)n有關(guān)，是指最深層的執(zhí)行語句耗費(fèi)時(shí)間，而遞歸算法與非遞歸算法在最深層的語句執(zhí)行上是沒有區(qū)別的，循環(huán)的次數(shù)也沒有太大差異。僅僅是確定循環(huán)是否繼續(xù)的方式不同，遞歸用棧隱含循環(huán)次數(shù)，非遞歸用循環(huán)變量來顯示循環(huán)次數(shù)而已。四、計(jì)算題（每題5分，共20分）1. 設(shè)s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’, 求Replace(s,’STUDENT’,q) 和Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))。解：① Replace(s,’STUDENT’,q)＝’I AM A WORKER’② 因?yàn)? SubString(s,6,2)＝‘A ’；SubString(s,7,8)＝‘ STUDENT’Concat(t,SubString(s,7,8))＝’GOOD STUDENT’所以Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))＝‘A GOOD STUDENT’2. 【②】 已知主串s=’ADBADABBAABADABBADADA’,模式串pat=’ADABBADADA’。寫出模式串的nextval函數(shù)值，并由此畫出KMP算法匹配的全過程。解：（由演示程序得知）nextval函數(shù)值為0 1 0 2 1 0 1 0 4 0 在第12個(gè)字符處發(fā)現(xiàn)匹配！s=’ADBADABBAABADABBADADA’pat=’ADABBADADA’3. （P60 418）用三元組表表示下列稀疏矩陣： 解：參見填空題4. 三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的 行下標(biāo) 、 列下標(biāo) 和 元素值 。所以（1）可列表為： （2）可列表為：8866416225943565353233685467858124. （P60 419）下列各三元組表分別表示一個(gè)稀疏矩陣，試寫出它們的稀疏矩陣。 解：（1）為64矩陣，非零元素有6個(gè)，但其中一數(shù)下標(biāo)有誤？（2）為45矩陣，非零元素有5個(gè)1 0 0 0 00 0 0 9 00 8 0 0 60 0 7 0 00 2 0 0 12 0 0 0 改為2,1,123 0 0 0 0 0 0 4 0 0 6 0 16 0 0 0 五、算法設(shè)計(jì)題（每題10分，共30分）1. 【③】 編寫一個(gè)實(shí)現(xiàn)串的置換操作Replace(amp。S, T, V)的算法。解：int Replace(Stringtype amp。S,Stringtype T,Stringtype V)。//將串S中所有子串T替換為 V,并返回置換次數(shù) { for(n=0,i=1。i=Strlen(S)Strlen(T)+1。i++) //注意i的取值范圍 if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了與T匹配的子串 { //分別把T的前面和后面部分保存為head和tail StrAssign(head,SubString(S,1,i1))。 StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)iStrlen(T)+1))。 StrAssign(S,Concat(head,V))。 StrAssign(S,Concat(S,tail))。 //把head,V,tail連接為新串 i+=Strlen(V)。 //當(dāng)前指針跳到插入串以后 n++。 n++。 }//if return n。 }//Replace分析:i+=Strlen(V)。這一句是必需的,則在某些情況下, 會(huì)引起不希望的后果,:設(shè)S=39。place39。, T=39。ace39。, V=39。face39。,則省掉i+=Strlen(V)。運(yùn)行時(shí)會(huì)出現(xiàn)什么結(jié)果?2. 【全國專升本資格考試】寫出將字符串反序的遞歸或遞推算法，例如字符串為“abcsxw”，反序?yàn)椤皐xscba”(注：③ 編寫對(duì)串求逆的遞推算法)算法思路：① 假定用單鏈表結(jié)構(gòu)存儲(chǔ)字符串；if沒有到尾部字符就不停調(diào)用自身函數(shù)，直至到達(dá)末尾，再從尾部返回并打印字符；遞歸算法的一般形式：（殷人凱題集P102）void p(參數(shù)表){if （遞歸結(jié)束條件）可直接求解步驟； 基本項(xiàng)else p（較小的參數(shù)）； 歸納項(xiàng)}DLR(x*root){if(!root)return(0)。printf(“%d”,rootdata)。DLR(rootlchild)。DLR(rootrchild)。}否則就打印當(dāng)前字符并返回。Invert(stringlistnode *p){if(!p)return(0)。else Invert(pnext)。printf(“%c”, pdata)}如果當(dāng)前串長為0,則return(1)否則開始遞歸：if 串沒有到末尾，則P=Pnext。 再調(diào)用invert(s)。else printf(pdata)。return void String_Reverse(Stringtype s,Stringtype amp。r)//求s的逆串r { StrAssign(r,39。39。)。 //初始化r為空串 for(i=Strlen(s)。i。i) { StrAssign(c,SubString(s,i,1))。 StrAssign(r,Concat(r,c))。 //把s的字符從后往前添加到r中 /這是遞推算法？ } }//String_Reverse3. 【⑤】試設(shè)計(jì)一個(gè)算法，將數(shù)組An 中的元素A[0]至A[n1]循環(huán)右移k位，并要求只用一個(gè)元素大小的附加存儲(chǔ)，元素移動(dòng)或交換次數(shù)為O(n)解： 分析:要把A的元素循環(huán)右移k位,則A[0]移至A[k],A[k]移至A[2k]......直到最終回到A[ 0].然而這并沒有全部解決問題,因?yàn)橛锌赡苡械脑卦诖诉^程中始終沒有被訪問過,當(dāng)n和k的最大公約數(shù)為p時(shí),只要分別以A[0],A[1],...A[p1]為起點(diǎn)執(zhí)行上述算法,就可以保證每一個(gè)元素都被且僅被右移一次,A的所有元素分別處在p個(gè)循環(huán)鏈: n=15,k=6,則p=3. 第一條鏈:A[0]A[6],A[6]A[12],A[12]A[3],A[3]A[9],A[9]A[0]. /已“順便”移動(dòng)了A[6]、A[12]…第二條鏈:A[1]A[7],A[7]A[13],A[13]A[4],A[4]A[10],A[10]A[1]. 第三條鏈:A[2]A[8],A[8]A[14],A[14]A[5],A[5]A[11],A[11]A[2]. 恰好使所有元素都右移一次. 雖然未經(jīng)數(shù)學(xué)證明,但作者相信上述規(guī)律應(yīng)該是正確的. 程序如下：void RSh(int A[n],int k)//把數(shù)組A的元素循環(huán)右移k位,只用一個(gè)輔助存儲(chǔ)空間 { for(i=1。i=k。i++) if(n%i==0amp。amp。k%i==0) p=i。//求n和k的最大公約數(shù)p for(i=0。ip。i++) { j=i。l=(i+k)%n。temp=A[i]。 while(l!=i) { A[j]=temp。 temp=A[l]。 A[l]=A[j]。 j=l。l=(j+k)%n。 }// 循環(huán)右移一步 A[i]=temp。 }//for}//RSh 附加題： 利用C的庫函數(shù)strlen, strcpy（或strncpy）寫一個(gè)算法void StrDelete(char *S,int t,int m) ，刪除串S中從位置i開始的連續(xù)的m個(gè)字符。若i≥strlen(S)，則沒有字符被刪除；若i+m≥strlen(S)，則將S中從位置i開始直至末尾的字符均被刪去。提示：strlen是求串長(length)函數(shù)：int strlen(char s)。 //求串的長度strcpy是串復(fù)制(copy)函數(shù)：char *strcpy(char to,char from)。 //該函數(shù)將串from復(fù)制到串to中，并且返回一個(gè)指向串to的開始處的指針。第6章 樹和二叉樹 自測(cè)卷解答 姓名 班級(jí) 題號(hào)一二三四五六總分題分101511202024100得分一、下面是有關(guān)二叉樹的敘述，請(qǐng)判斷正誤（每小題1分，共10分）（ √ ）1. 若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有n—1個(gè)非空指針域。（ ）。 （ √ ）。 （ ）。 （ ）（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。 （應(yīng)當(dāng)是二叉排序樹的特點(diǎn)）（ ），其中k是樹的深度。 （ ），如果不存在非空左子樹，則不存在非空右子樹。 （ ），它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2i—1個(gè)結(jié)點(diǎn)。（應(yīng)2i1）（ √ ）（linkrlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。（正確。用二叉鏈表存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)共有2n個(gè)鏈域。由于二叉樹中，除根結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)有且