数据结构(C语言版)课后习题答案 下载本文

}

{ }

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