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