}
{ }
int max=GetMax(p->next);
return p->data>=max ? p->data:max;
②
int GetLength(LinkList p) { }
if(!p->next) else { }
return GetLength(p->next)+1; return 1;
③
double GetAverage(LinkList p , int n) { }
if(!p->next) else { }
double ave=GetAverage(p->next,n-1); return (ave*(n-1)+p->data)/n; return p->data;
XXV
第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]=[（5-1）*100+（5-1）]*2+10=818。
（7）设有数组A[i,j]，数组的每个元素长度为3字节，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]=[（8-1）*8+（5-1）]*3+BA=BA+180。
（8）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。
XXVI
A．13 B．32 C．33 D．40 答案：C
（9）若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定aij（i A．i*(i-1)/2+j B．j*(j-1)/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按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。 A．A[8,5] B．A[3,10] C. A[5,8] D．A[0,9] 答案：B 解释：设数组从内存首地址M开始顺序存放，若数组按行先存储，元素A[8,5]的起 始地址为：M+[（8-0）*10+（5-1）]*1=M+84；若数组按列先存储，易计算出元素A[3,10]的起始地址为：M+[（10-1）*9+（3-0）]*1=M+84。故选B。 （11）设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（ ）。 A．(i-1)*n+j B．(i-1)*n+j-1 C．i*(j-1) D．j*m+i-1 答案：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 XXVII 解释：广义表的深度是指广义表中展开后所含括号的层数，广义表的长度是指广义表 中所含元素的个数。根据定义易知L的长度为1，深度为2。 2．应用题 （1）已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。 答案： 模式串t的next和nextval值如下： j t串 next[j] nextval[j] （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开始连续存放主存储器中，主存储器字长为16位。求： ① 存放该数组所需多少单元？ ② 存放数组第4列所有元素至少需多少单元？ ③ 数组按行存放时，元素A[7,4]的起始地址是多少？ ④ 数组按列存放时，元素A[4,7]的起始地址是多少？ 答案： 每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。 （1）242 （2）22 （3）s+182 （4）s+142 XXVIII 1 2 3 4 5 6 7 8 9 10 11 12 a b c a a b b a b c a b 0 1 1 1 2 2 3 1 2 3 4 5 0 1 1 0 2 1 3 0 1 1 0 5