数据结构（C语⾔）第⼆版第四章课后答案
数据结构(C语⾔)第⼆版第四章课后答案
1~5 B B C A B
6~10 B B C B B
11~15 A B D (C,B) C
1．选择题
（1）串是⼀种特殊的线性表，其特殊性体现在（B） 。
A．可以顺序存储 B．数据元素是单个字符
C．可以链式存储 D．数据元素可以是多个字符若
字符串简称串，是⼀种特殊的线性表，它的数据元素仅由⼀个字符组成。
（2）串下⾯关于串的的叙述中，（B）是不正确的。
A．串是字符的有限序列
B．空串是由空格构成的串
C．模式匹配是串的⼀种重要运算
D ．串既可以采⽤顺序存储，也可以采⽤链式存储
零个字符的串称为空串，其长度为零。
空格是串的字符集合中的⼀个元素。
（3）串“ ababaaababaa ”的 next 数组为（C） 。
A ． 012345678999 B． 012121111212
C． 011234223456 D． 0123012322345
计算字符串的next函数值，可以参考"KMP模式匹配算法".
计算过程:
下标 j : 1 2 3 4 5 6 7 8 9 10 11 12
字符串: a b a b a a a b a b a a
next[ j ] 0 1 1 2 3 4 2 2 3 4 5 6
1)当j=1时，固定就是next[1]=0;
2)当j=2时，由1到j-1的字符串是"a"，属于其他情况，固定就是next[2]=1;
3)当j=3时，由1到j-1的字符串是"ab"，前缀字符"a"与后缀字符"b"不相等, 属于其他情况，所以,next[3]=1;
4)当j=4时，由1到j-1的字符串是"aba"，前缀字符"a"与后缀字符"a"相等, 也就是有1个字符相等，所以,next[4]=1+1=2;
5)当j=5时，由1到j-1的字符串是"abab"，前缀字符"ab"与后缀字符"ab"相等，也就是有2个字符相等，所以,next[5]=2+1=3;
6)当j=6时，由1到j-1的字符串是"ababa"，前缀字符"aba"与后缀字符"aba"相等，也就是有3个字符相等，所以,next[6]=3+1=4;
7)当j=7时，由1到j-1的字符串是"ababaa"，前缀字符"a"与后缀字符"a"相等，也就是有1个字符相等，所以,next[7]=1+1=2;
8)当j=8时，由1到j-1的字符串是"ababaaa"，前缀字符"a"与后缀字符"a"相等，也就是有1个字符相等，所以,next[8]=1+1=2;
9)当j=9时，由1到j-1的字符串是"ababaaab"，前缀字符"ab"与后缀字符"ab"相等，也就是有2个字符相等，所以,next[9]=2+1=3;
10)当j=10时，由1到j-1的字符串是"ababaaaba"，前缀字符"aba"与后缀字符"aba"相等, 也就是有3个字符相等，所
以,next[10]=3+1=4;
11)当j=11时，由1到j-1的字符串是"ababaaabab"，前缀字符"abab"与后缀字符"abab"相等，也就是有4个字符相等，所
以,next[11]=4+1=5;
12)当j=12时，由1到j-1的字符串是"ababaaababa"，前缀字符"ababa"与后缀字符"ababa"相等，也就是有5个字符相等，所
以,next[12]=5+1=6;
（4）串“ ababaabab ”的nextval 为（A）。
A ． 010104101 B． 010102101
C ． 010100011
D ． 010101011
下标 i : 1 2 3 4 5 6 7 8 9
字符串s: a b a b a a b a b
next [ i ]: 0 1 1 2 3 4 2 3 4
nextval[i]: 0 1 0 1 0 4 1 0 1
先计算前缀next[i]的值：
计算字符串的next函数值，可以参考"KMP模式匹配算法".
next [ i ]: 0 1 1 2 3 4 2 3 4
接下来计算nextval[i]的值：
第⼀位的nextval 值必定为0，第⼆位如果于第⼀位相同则为0，如果不同则为1。
第三位的next 值为1，那么将第三位和第⼀位进⾏⽐较，均为a，相同，则第三位的nextval 值为0。
第四位的next 值为2，那么将第四位和第⼆位进⾏⽐较，相同，第⼆位的next 值为1，则继续将第⼆位与第⼀位进⾏⽐较，不同，则第四位的nextval 值为第⼆位的next 值，为1。
第五位的next 值为3，那么将第五位和第三位进⾏⽐较，相同，第三位的next 值为1，则继续将第三位与第⼀位进⾏⽐较，相同，则第五位的nextval 值为第⼀位的next 值，为0。
第六位的next 值为4，那么将第六位和第四位进⾏⽐较，不同，则第六位的nextval 值为其next 值，为4。
第七位的next 值为2，那么将第七位和第⼆位进⾏⽐较，相同，第⼆位的next 值为1，则继续将第⼆位与第⼀位进⾏⽐较，不同，则第七位的nextval 值为第⼆位的next 值，为1。
第⼋位的next 值为3，那么将第⼋位和第三位进⾏⽐较，相同，第三位的next 值为1，则继续将第三位与第⼀位进⾏⽐较，相同，则第⼋位的nextval 值为第⼀位的next 值，为0。
第九位的next 值为4，那么将第九位和第四位进⾏⽐较，相同，第四位的next 值为2，则继续将第四位与第⼆位进⾏⽐较，相同，则第⼋位的nextval 值为第⼆位的next 值，为1。
nextval为0,1,0,1,0,4,1,0,1
（5）串的长度是指（B） 。
A ．串中所含不同字母的个数
B ．串中所含字符的个数
C．串中所含不同字符的个数
D ．串中所含⾮空格字符的个数
串中字符的数⽬称为串的长度。
（6）假设以⾏序为主序存储⼆维数组A=array[1…100,1…100] ，设每个数据元素占2 个存储单元，基
地址为10，则LOC[5,5]=（B）。
A． 808 B． 818 C． 1010 D ． 1020
LOC ( i , j ) = 基地址 + ( ( i - 1 ) * m + j ) * L (L为每个元素占的存储单元)
以⾏序为主，则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] 的存储⾸地址为（B）。
A． BA+141 B ． BA+180
C． BA+222 D． BA+225
LOC ( i , j ) = 基地址 + ( ( j - 1 ) * m + i ) * L (L为每个元素占的存储单元)
以列序为主，则LOC[5,8]=[ （ 8-1 ） *8+ （ 5-1 ） ]*3+BA=BA+180 。
（8）设有⼀个10 阶的对称矩阵A ，采⽤压缩存储⽅式，以⾏序为主存储， a11 为第⼀元素，其存储地址为1，每个元素占⼀个地址空间，则a85 的地址为（C） 。
A． 13 B． 32 C． 33 D． 40ascii共有多少个字符
这个是从k=0，1…开始计算的，题中储存的第⼀个元素a11的地址为1，所以将所得的结果加1
（9）若对n 阶对称矩阵 A 以⾏序为主序⽅式将其下三⾓形的元素(包括主对⾓线上所有元素) 依次存放于⼀维数组B[1…(n(n+1))/2] 中，则在B 中确定aij（ i<j ）的位置k 的关系为（B）。
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[1…(n(n+1))/2] 中，可知k从1开始，故将下列公式的结果加1，⼜因为i<j，所以k =j * ( j - 1 ) / 2 + i 。
（10）⼆维数组A 的每个元素是由10 个字符组成的串，其⾏下标i=0,1, , ,8, 列下标j=1,2, , ,10 。若A 按⾏先存储，元素A[8,5] 的起始地址与当A 按列先存储时的元素（B）的起始地址相同。设每个字符占⼀个字节。
A． A[8,5] B． A[3,10] C. A[5,8] D． A[0,9]
设数组从内存⾸地址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 。
（11）设⼆维数组A[1… m ， 1… n] （即m ⾏n 列）按⾏存储在数组B[1… m*n] 中，则⼆维数组元素A[i,j] 在⼀维数组B 中的下标为（A） 。
A ． (i-1)n+j B． (i-1)n+j-1 C． i(j-1) D ． j m+i-1
按⾏存储, ⼀共有( i - 1) ⾏存满，再加 j 个元素就是了。
（12）数组A[0…4,-1…-3,5…7] 中含有元素的个数（B） 。
A． 55 B ． 45 C． 36 D． 16
三维数组，共有533=45 个元素。
（13）⼴义表A=(a,b,(c,d),(e,(f,g))) ，则Head(Tail(Head(Tail(Tail(A))))) 的值为（D） 。
A． (g) B ． (d) C． c 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)) 的表头是（C） ，表尾是（B） 。
A． a B ． ( ) C ． (a,b,c,d) D ． (b,c,d)
表头为⾮空⼴义表的第⼀个元素，可以是⼀个单原⼦，也可以是⼀个⼦表，((a,b,c,d)) 的表头为⼀个⼦表(a,b,c,d) ；表尾为除去表头之外，由其余元素构成的表，表为⼀定是个⼴义表， ((a,b,c,d)) 的表尾为空表( ) 。
（15）设⼴义表L=((a,b,c)) ，则L 的长度和深度分别为（C） 。
A． 1 和1 B． 1 和3 C． 1 和2 D． 2 和3
⼴义表的深度是指⼴义表中展开后所含括号的层数，⼴义表的长度是指⼴义表中所含元素的个数。根据定义易知L 的长度为1，深度为2。
2．应⽤题
（1）已知模式串t=‘ abcaabbabcab ’写出⽤KMP法求得的每个字符对应的next 和nextval函数值。
/*
模式串t 的next 和nextval 值如下：
下标j      1 2 3 4 5 6 7 8 9 10 11 12
模式串t    a b c a a b b a b c  a  b
next[j]  0 1 1 1 2 2 3 1 2 3  4  5
nextval[j]  0 1 1 0 2 1 3 0 1 1  0  5
*/
（2）设⽬标为t= “ abcaabbabcabaacbacba ” , 模式为p= “ abcabaa ”
①计算模式p 的naxtval 函数值；
②不写出算法, 只画出利⽤KMP算法进⾏模式匹配时每⼀趟的匹配过程。
/*
1.p 的nextval 函数值为0110132 (p 的next 函数值为0111232)
2.利⽤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
(4) 请将⾹蕉banana ⽤⼯具 H( ) — Head( ) ， T( ) — Tail( ) 从L 中取出。
L=(apple,(orange,(strawberry,(banana)),peach),pear)
答案： H（ H（ T（ H（ T（ H（ T（ L）））））））
3．算法设计题
（1）写⼀个算法统计在输⼊字符串中各个不同字符出现的频度并将结果存⼊⽂件（字符串中的合法字符为A-Z 这26 个字母和0-9 这10 个数字）。
[ 题⽬分析]
由于字母共26 个，加上数字符号10 个共36 个，所以设⼀长36 的整型数组，前10 个分量存放数字字符出现的次数， 余下存放字母出现的次数。从字符串中读出数字字符时，字符的ASCII 代码值减去数字字符‘0’的ASCII 代码值，得出其数值(0…9) ，字母的ASCII 代码值减去字符‘ A’的ASCII 代码值加上10 ，存⼊其数组的对应下标分量中。遇其它符号不作处理，直⾄输⼊字符串结束。
[ 算法描述]
void Count (){// 统计输⼊字符串中数字字符和字母字符的个数。
int i, num[36];
char ch ;
for( i ＝0; i<36; i++) num[i]＝0;// 初始化
while((ch ＝getchar())!='#'){// ‘ # ’表⽰输⼊字符串结束。
if('0'<=ch<=' 9'){ i=ch －48;num[i]++;}// 数字字符
else if('A'<=ch<='Z'){ i=ch-65+10;num[i]++;}// 字母字符
}
for(i=0; i<10;i++)// 输出数字字符的个数
cout<<"数字"<<i<<"的个数="<<num[i]<<endl;
for(i ＝10; i<36; i++)// 求出字母字符的个数
cout<<"字母字符"<<i+55<<"的个数="<<num[i]<<endl;
}
（2）写⼀个递归算法来实现字符串逆序存储，要求不另设串存储空间。
[ 题⽬分析]
实现字符串的逆置并不难，但本题“要求不另设串存储空间”来实现字符串逆序存储，即第⼀个输⼊的字符最后存储，最后输⼊的字符先存储，使⽤递归可容易做到。
[ 算法描述]
void InvertStore(char A[]){// 字符串逆序存储的递归算法。
char ch;
static int i =0;// 需要使⽤静态变量
cin>>ch;
if(ch!='.'){// 规定'.' 是字符串输⼊结束标志
InvertStore(A);
A[i++]= ch;// 字符串逆序存储
}
A[i]='\0';// 字符串结尾标记
}
（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;
//p ， q 分别为字符串s 和t 的⼯作指针
char*p=s,*q=t;
if(pos<1){cout<<"pos 参数位置⾮法"<<endl;exit(0);}
while(*p!='0'&&i<pos){p++;i++;}// 查pos 位置
// 若pos ⼩于串s 长度，则查到pos 位置时， i=pos 。
if(*p =='/0'){cout<<pos<<" 位置⼤于字符串s 的长度";exit(0);}
else// 查字符串的尾
while(*p!='/0'){p++; i++;}// 查到尾时， i 为字符‘ \0 ’的下标， p 也指向‘ \0 ’。
while(*q!='\0'){q++; x++;}// 查字符串t 的长度x，循环结束时q 指向'\0' 。
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 位置上
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。