【正文】 inkList p){ if(!pnext) return 1。 else { return GetLength(pnext)+1。 }}③double GetAverage(LinkList p , int n){ if(!pnext) return pdata。 else { double ave=GetAverage(pnext,n1)。 return (ave*(n1)+pdata)/n。 }}第4章 串、數(shù)組和廣義表1．選擇題（1）串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）。 A．可以順序存儲(chǔ) B．?dāng)?shù)據(jù)元素是一個(gè)字符 C．可以鏈?zhǔn)酱鎯?chǔ) D．?dāng)?shù)據(jù)元素可以是多個(gè)字符若 答案：B（2）串下面關(guān)于串的的敘述中，（ ）是不正確的？ A．串是字符的有限序列 B．空串是由空格構(gòu)成的串C．模式匹配是串的一種重要運(yùn)算 D．串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)答案：B解釋：空格常常是串的字符集合中的一個(gè)元素，有一個(gè)或多個(gè)空格組成的串成為空格串，零個(gè)字符的串成為空串，其長度為零。 （3）串“ababaaababaa”的next數(shù)組為（ ）。A．012345678999 B．012121111212 C．011234223456 D．0123012322345答案：C（4）串“ababaabab”的nextval為（ ）。A．010104101 B．010102101 C．010100011 D．010101011 答案：A（5）串的長度是指（ ）。A．串中所含不同字母的個(gè)數(shù) B．串中所含字符的個(gè)數(shù)C．串中所含不同字符的個(gè)數(shù) D．串中所含非空格字符的個(gè)數(shù)答案：B解釋：串中字符的數(shù)目稱為串的長度。（6）假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[1..100,1..100]，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為10，則LOC[5,5]=（ ）。A．808 B．818 C．1010 D．1020答案：B解釋：以行序?yàn)橹?，則LOC[5,5]=[（51）*100+（51）]*2+10=818。（7）設(shè)有數(shù)組A[i,j]，數(shù)組的每個(gè)元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時(shí)，元素A[5,8]的存儲(chǔ)首地址為（ ）。A．BA+141 B．BA+180 C．BA+222 D．BA+225答案：B解釋：以列序?yàn)橹?，則LOC[5,8]=[（81）*8+（51）]*3+BA=BA+180。（8）設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（ ）。A．13 B．32 C．33 D．40答案：C（9）若對(duì)n階對(duì)稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對(duì)角線上所有元素)依次存放于一維數(shù)組B[1..(n(n+1))/2]中，則在B中確定aij（ij）的位置k的關(guān)系為（ ）。A．i*(i1)/2+j B．j*(j1)/2+i C．i*(i+1)/2+j D．j*(j+1)/2+i答案：B（10）二維數(shù)組A的每個(gè)元素是由10個(gè)字符組成的串，其行下標(biāo)i=0,1,…,8,列下標(biāo)j=1,2,…,10。若A按行先存儲(chǔ)，元素A[8,5]的起始地址與當(dāng)A按列先存儲(chǔ)時(shí)的元素（ ）的起始地址相同。設(shè)每個(gè)字符占一個(gè)字節(jié)。A．A[8,5] B．A[3,10] C. A[5,8] D．A[0,9]答案：B解釋：設(shè)數(shù)組從內(nèi)存首地址M開始順序存放，若數(shù)組按行先存儲(chǔ)，元素A[8,5]的起始地址為：M+[（80）*10+（51）]*1=M+84；若數(shù)組按列先存儲(chǔ)，易計(jì)算出元素A[3,10]的起始地址為：M+[（101）*9+（30）]*1=M+84。故選B。（11）設(shè)二維數(shù)組A[1.. m，1.. n]（即m行n列）按行存儲(chǔ)在數(shù)組B[1.. m*n]中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為（ ）。A．(i1)*n+j B．(i1)*n+j1 C．i*(j1) D．j*m+i1答案：A解釋：特殊值法。取i=j=1，易知A[1,1]的的下標(biāo)為1，四個(gè)選項(xiàng)中僅有A選項(xiàng)能確定的值為1，故選A。（12）數(shù)組A[0..4,1..3,5..7]中含有元素的個(gè)數(shù)（ ）。A．55 B．45 C．36 D．16答案：B解釋：共有5*3*3=45個(gè)元素。（13）廣義表A=(a,b,(c,d),(e,(f,g)))，則Head(Tail(Head(Tail(Tail(A)))))的值為（ ）。A．(g) B．(d) C．c D．d答案：D解釋：Tail(A)=(b,(c,d),(e,(f,g)))；Tail(Tail(A))=( (c,d),(e,(f,g)))； Head(Tail(Tail(A)))= (c,d)；Tail(Head(Tail(Tail(A))))=(d)；Head(Tail(Head(Tail(Tail(A)))))=d。（14）廣義表((a,b,c,d))的表頭是（ ），表尾是（ ）。A．a(chǎn) B．( ) C．(a,b,c,d) D．(b,c,d)答案：C、B解釋：表頭為非空廣義表的第一個(gè)元素，可以是一個(gè)單原子，也可以是一個(gè)子表，((a,b,c,d))的表頭為一個(gè)子表(a,b,c,d)；表尾為除去表頭之外，由其余元素構(gòu)成的表，表為一定是個(gè)廣義表，((a,b,c,d))的表尾為空表( )。（15）設(shè)廣義表L=((a,b,c))，則L的長度和深度分別為（ ）。A．1和1 B．1和3 C．1和2 D．2和3 答案：C解釋：廣義表的深度是指廣義表中展開后所含括號(hào)的層數(shù)，廣義表的長度是指廣義表中所含元素的個(gè)數(shù)。根據(jù)定義易知L的長度為1，深度為2。2．應(yīng)用題 （1）已知模式串t=‘a(chǎn)bcaabbabcab’寫出用KMP法求得的每個(gè)字符對(duì)應(yīng)的next和nextval函數(shù)值。答案：模式串t的next和nextval值如下：j1 2 3 4 5 6 7 8 9 10 11 12 t串a(chǎn) b c a a b b a b c a bnext[j]0 1 1 1 2 2 3 1 2 3 4 5nextval[j]0 1 1 0 2 1 3 0 1 1 0 5（2）設(shè)目標(biāo)為t=“abcaabbabcabaacbacba”,模式為p=“abcabaa”① 計(jì)算模式p的naxtval函數(shù)值；② 不寫出算法,只畫出利用KMP算法進(jìn)行模式匹配時(shí)每一趟的匹配過程。答案：① p的nextval函數(shù)值為0110132。（p的next函數(shù)值為0111232）。② 利用KMP(改進(jìn)的nextval)算法，每趟匹配過程如下： 第一趟匹配： abcaabbabcabaacbacba abcab(i=5,j=5) 第二趟匹配： abcaabbabcabaacbacba abc(i=7,j=3) 第三趟匹配： abcaabbabcabaacbacba a(i=7,j=1) 第四趟匹配： abcaabbabcabaac bacba (成功) abcabaa(i=15,j=8)（3）數(shù)組A中，每個(gè)元素A[i,j]的長度均為32個(gè)二進(jìn)位,行下標(biāo)從1到9，列下標(biāo)從1到11，從首地址S開始連續(xù)存放主存儲(chǔ)器中，主存儲(chǔ)器字長為16位。求：① 存放該數(shù)組所需多少單元？② 存放數(shù)組第4列所有元素至少需多少單元？③ 數(shù)組按行存放時(shí)，元素A[7,4]的起始地址是多少？④ 數(shù)組按列存放時(shí)，元素A[4,7]的起始地址是多少？答案：每個(gè)元素32個(gè)二進(jìn)制位，主存字長16位，故每個(gè)元素占2個(gè)字長，行下標(biāo)可平移至1到11。（1）242 （2）22 （3）s+182 （4）s+142(4)請(qǐng)將香蕉banana用工具 H( )—Head( )，T( )—Tail( )從L中取出。L=(apple,(orange,(strawberry,(banana)),peach),pear)答案：H（H（T（H（T（H（T（L）））））））3．算法設(shè)計(jì)題（1）寫一個(gè)算法統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符出現(xiàn)的頻度并將結(jié)果存入文件（字符串中的合法字符為AZ這26個(gè)字母和09這10個(gè)數(shù)字）。[題目分析] 由于字母共26個(gè)，加上數(shù)字符號(hào)10個(gè)共36個(gè)，所以設(shè)一長36的整型數(shù)組，前10個(gè)分量存放數(shù)字字符出現(xiàn)的次數(shù)，余下存放字母出現(xiàn)的次數(shù)。從字符串中讀出數(shù)字字符時(shí)，字符的ASCII代碼值減去數(shù)字字符 ‘0’的ASCII代碼值，得出其數(shù)值(0..9)，字母的ASCII代碼值減去字符‘A’的ASCII代碼值加上10，存入其數(shù)組的對(duì)應(yīng)下標(biāo)分量中。遇其它符號(hào)不作處理，直至輸入字符串結(jié)束。[算法描述]void Count（）//統(tǒng)計(jì)輸入字符串中數(shù)字字符和字母字符的個(gè)數(shù)。｛int i，num[36]；char ch；　for（i＝0；i36；i++）num[i]＝０；// 初始化　while（（ch＝getchar（））!=‘’） //‘’表示輸入字符串結(jié)束?！　　f（‘0’=ch=‘9’）｛i=ch－48。num[i]++；｝ // 數(shù)字字符　　 else　if（‘A’=ch=‘Z’）｛i=ch65+10。num[i]++；｝// 字母字符　for（i=0；i10；i++） // 輸出數(shù)字字符的個(gè)數(shù) cout“數(shù)字”i “的個(gè)數(shù)=”num[i]endl?！or（i＝10；i36；i++）// 求出字母字符的個(gè)數(shù) cout“字母字符”i+55 “的個(gè)數(shù)=”num[i]endl。｝（2）寫一個(gè)遞歸算法來實(shí)現(xiàn)字符串逆序存儲(chǔ)，要求不另設(shè)串存儲(chǔ)空間。[題目分析]實(shí)現(xiàn)字符串的逆置并不難，但本題“要求不另設(shè)串存儲(chǔ)空間”來實(shí)現(xiàn)字符串逆序存儲(chǔ)，即第一個(gè)輸入的字符最后存儲(chǔ)，最后輸入的字符先存儲(chǔ)，使用遞歸可容易做到。[算法描述]void InvertStore(char A[])//字符串逆序存儲(chǔ)的遞歸算法。{char ch。static int i = 0。//需要使用靜態(tài)變量cinch。if (ch!= 39。.39。) //規(guī)定39。.39。是字符串輸入結(jié)束標(biāo)志 {InvertStore(A)。 A[i++] = ch。//字符串逆序存儲(chǔ) }A[i] = 39。\039。 //字符串結(jié)尾標(biāo)記}（3）編寫算法，實(shí)現(xiàn)下面函數(shù)的功能。函數(shù)void insert(char*s,char*t,int pos)將字符串t插入到字符串s中，插入位置為pos。假設(shè)分配給字符串s的空間足夠讓字符串t插入。（說明：不得使用任何庫函數(shù)）[題目分析]本題是字符串的插入問題，要求在字符串s的pos位置，插入字符串t。首先應(yīng)查找字符串s的pos位置，將第pos個(gè)字符到字符串s尾的子串向后移動(dòng)字符串t的長度，然后將字符串t復(fù)制到字符串s的第pos位置后。對(duì)插入位置pos要驗(yàn)證其合法性，小于1或大于串s的長度均為非法，因題目假設(shè)給字符串s的空間足夠大，故對(duì)插入不必判溢出。[算法描述]void insert(char *s,char *t,int pos)//將字符串t插入字符串s的第pos個(gè)位置。{int i=1,x=0。 char *p=s,*q=t。 //p，q分別為字符串s和t的工作指針 if(pos1) {cout“pos參數(shù)位置非法”endl。exit(0)。}while(*p!=’\0’amp。amp。ipos) {p++。i++。} //查pos位置 //若pos小于串s長度，則查到pos位置時(shí)，i=pos。 if(*p == 39。/039。) { coutpos位置大于字符串s的長度。exit(0)。} else //查找字符串的尾 while(*p!= 39。/039。) {p++。 i++。} //查到尾時(shí)，i為字符‘\0’的下標(biāo)，p也指向‘\0’。 while(*q!= 39。\039。) {q++。 x++。 } //查找字符串t的長度x，循環(huán)結(jié)束時(shí)q指向39。\039。 for(j=i。j=pos 。j){*(p+x)=*p。 p。}//串s的pos后的子串右移，空出串t的位置。 q。 //指針q回退到串t的最后一個(gè)字符 for(j=1。j=x。j++) *p=*q。 //將t串插入到s的pos位置上 [算法討論] 串s的結(jié)束標(biāo)記(39。\039。)也后移了，而串t的結(jié)尾標(biāo)記不應(yīng)插入到s中。（4）已知字符串S1中存放一段英文，寫出