数据结构课程第二章部分习题解答.docx
《数据结构课程第二章部分习题解答.docx》由会员分享，可在线阅读，更多相关《数据结构课程第二章部分习题解答.docx（10页珍藏版）》请在冰点文库上搜索。
数据结构课程第二章部分习题解答
数据结构课程第二章部分习题解答
第二章数组
2-1设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。
下面要解决的Josephus问题是：
对于任意给定的n,s和m，求出这n个人的出局序列。
请以n=9,s=1,m=5为例，人工模拟Josephus的求解过程以求得问题的解。
【解答】
出局人的顺序为5,1,7,4,3,6,9,2,8。
2-2试编写一个求解Josephus问题的函数。
用整数序列1,2,3,……,n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。
然后使用n=9,s=1,m=5，以及n=9,s=1,m=0，或者n=9,s=1,m=10作为输入数据，检查你的程序的正确性和健壮性。
最后分析所完成算法的时间复杂度。
【解答】函数源程序清单如下：
voidJosephus（intA[],intn,s,m）{
inti,j,k,tmp;
if（m==0）{
cout<<"m=0是无效的参数！
"<return;
}
for（i=0;ii=s-1;/*报名起始位置*/
for（k=n;k>1;i--）{/*逐个出局，执行n-1次*/
if（i==k）i=0;
i=（i+m-1）%k;/*寻找出局位置*/
if（i!
=k-1）{
tmp=A[i];/*出局者交换到第k-1位置*/
for（j=i;jA[k-1]=tmp;
}
}
for（k=0;ktmp=A[k];A[k]=A[n-k+1];A[n-k+1]=tmp;
}
}
例：
n=9,s=1,m=5
0
1
2
3
4
5
6
7
8
k=9
1
2
3
4
6
7
8
9
第5人出局,i=4
k=8
2
3
4
6
7
8
9
5
第1人出局,i=0
k=7
2
3
4
6
8
9
1
5
第7人出局,i=4
k=6
2
3
6
8
9
7
1
5
第4人出局,i=2
k=5
2
6
8
9
4
7
1
5
第3人出局,i=1
k=4
2
8
9
3
4
7
1
5
第6人出局,i=1
k=3
2
8
6
3
4
7
1
5
第9人出局,i=2
k=2
8
9
6
3
4
7
1
5
第2人出局,i=0
8
2
9
6
3
4
7
1
5
第8人出局,i=0
逆置
5
1
7
4
3
6
9
2
8
最终出局顺序
例：
n=9,s=1,m=0
报错信息m=0是无效的参数！
例：
n=9,s=1,m=10
0
1
2
3
4
5
6
7
8
k=9
2
3
4
5
6
7
8
9
第1人出局,i=0
k=8
2
4
5
6
7
8
9
1
第3人出局,i=1
k=7
2
4
5
7
8
9
3
1
第6人出局,i=3
k=6
4
5
7
8
9
6
3
1
第2人出局,i=0
k=5
4
5
7
8
2
6
3
1
第9人出局,i=4
k=4
4
7
8
9
2
6
3
1
第5人出局,i=1
k=3
4
8
5
9
2
6
3
1
第7人出局,i=1
k=2
8
7
5
9
2
6
3
1
第4人出局,i=0
8
4
7
5
9
2
6
3
1
第8人出局,i=0
逆置
1
3
6
2
9
5
7
4
8
最终出局顺序
当m=1时，时间代价最大。
达到（n-1）+（n-2）+∙∙∙∙∙∙+1=n（n-1）/2≈O（n2）。
2-3设有一个线性表（e0,e1,…,en-2,en-1）存放在一个一维数组A[arraySize]中的前n个数组元素位置。
请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为（en-1,en-2,…,e1,e0）。
【解答】
templatevoidinverse（TypeA[],intn）{
Typetmp;
for（inti=0;i<=（n-1）/2;i++）{
tmp=A[i];A[i]=A[n-i-1];A[n-i-1]=tmp;
}
}
2-7设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，问A[3][3]（10）存放在什么位置？
脚注（10）表示用10进制表示。
【解答】
设数组元素A[i][j]存放在起始地址为Loc（i,j）的存储单元中。
∵Loc（2,2）=Loc（0,0）+2*n+2=644+2*n+2=676.
∴n=（676-2-644）/2=15
∴Loc（3,3）=Loc（0,0）+3*15+3=644+45+3=692.
2-9设有一个n⨯n的对称矩阵A，如图（a）所示。
为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。
前者称为上三角矩阵，后者称为下三角矩阵。
我们把它们按行存放于一个一维数组B中，如图（b）和图（c）所示。
并称之为对称矩阵A的压缩存储方式。
试问：
（1）存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？
（2）若在一维数组B中从0号位置开始存放，则如图（a）所示的对称矩阵中的任一元素aij在只存上三角部分的情形下（图（b））应存于一维数组的什么下标位置？
给出计算公式。
（3）若在一维数组B中从0号位置开始存放，则如图（a）所示的对称矩阵中的任一元素aij在只存下三角部分的情形下（图（c））应存于一维数组的什么下标位置？
给出计算公式。
【解答】
（1）数组B共有n+（n-1）+∙∙∙∙∙∙+1=n*（n+1）/2个元素。
（2）只存上三角部分时，若i≤j，则数组元素A[i][j]前面有i-1行（1~i-1，第0行第0列不算），第1行有n个元素，第2行有n-1个元素，∙∙∙∙∙∙，第i-1行有n-i+2个元素。
在第i行中，从对角线算起，第j号元素排在第j-i+1个元素位置（从1开始），因此，数组元素A[i][j]在数组B中的存放位置为
n+（n-1）+（n-2）+∙∙∙∙∙∙+（n-i+2）+j-i+1
=（2n-i+2）*（i-1）/2+j-i+1
=（2n-i）*（i-1）/2+j
若i>j，数组元素A[i][j]在数组B中没有存放，可以找它的对称元素A[j][i]。
在
数组B的第（2n-j）*（j-1）/2+i位置中找到。
如果第0行第0列也计入，数组B从0号位置开始存放，则数组元素A[i][j]在数组B中的存放位置可以改为
当i≤j时，=（2n-i+1）*i/2+j-i=（2n-i-1）*i/2+j
当i>j时，=（2n-j-1）*j/2+i
（3）只存下三角部分时，若i≥j，则数组元素A[i][j]前面有i-1行（1~i-1，第0行第0列不算），第1行有1个元素，第2行有2个元素，∙∙∙∙∙∙，第i-1行有i-1个元素。
在第i行中，第j号元素排在第j个元素位置，因此，数组元素A[i][j]在数组B中的存放位置为
1+2+∙∙∙∙∙∙+（i-1）+j=（i-1）*i/2+j
若i在
数组B的第（j-1）*j/2+i位置中找到。
如果第0行第0列也计入，数组B从0号位置开始存放，则数组元素A[i][j]在数组B中的存放位置可以改为
当i≥j时，=i*（i+1）/2+j
当i2-10设A和B均为下三角矩阵，每一个都有n行。
因此在下三角区域中各有n（n+1）/2个元素。
另设有一个二维数组C，它有n行n+1列。
试设计一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中。
要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。
并给出计算A的矩阵元素aij和B的矩阵元素bij在C中的存放位置下标的公式。
【解答】
计算公式
2-14字符串的替换操作replace（String&s,String&t,String&v）是指：
若t是s的子串，则用串v替换串t在串s中的所有出现；若t不是s的子串，则串s不变。
例如，若串s为“aabbabcbaabaaacbab”，串t为“bab”，串v为“abdc”，则执行replace操作后，串s中的结果为“aababdccbaabaaacabdc”。
试利用字符串的基本运算实现这个替换操作。
【解答】
String&String:
:
Replace（String&t,String&v）{
if（（intid=Find（t））==-1）//没有找到，当前字符串不改，返回
{cout<<"The（replace）operationfailed."<Stringtemp（ch）;//用当前串建立一个空的临时字符串
ch[0]='\0';curLen=0;//当前串作为结果串，初始为空
intj,k=0,l;//存放结果串的指针
while（id!
=-1）{
for（j=0;j//摘取temp.ch中匹配位置id前面的元素到结果串ch。
curLen+=id+v.curLen;//修改结果串连接后的长度
if（curLen<=maxLen）l=v.curLen;//确定替换串v传送字符数l
else{l=curLen-maxLen;curLen=maxLen;}
for（j=0;j//连接替换串v到结果串ch后面
if（curLen==maxLen）break;//字符串超出范围
for（j=id+t.curLen;jtemp.ch[j-id-t.curLen]=temp.ch[j];//删改原来的字符串
temp.curLen-=（id+t.curLen）;
id=temp.Find（t）;
}
return*this;
}
2-15编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。
用适当的测试数据来验证这个算法。
【解答】
统计算法
include
include"string.h"
voidfrequency（String&s,char&A[],int&C[],int&k）{
//s是输入字符串，数组A[]中记录字符串中有多少种不同的字符，C[]中记录每
//一种字符的出现次数。
这两个数组都应在调用程序中定义。
k返回不同字符数。
inti,j,len=s.length（）;
if（!
len）{cout<<"Thestringisempty."<else{A[0]=s[0];C[0]=1;k=1;/*语句s[i]是串的重载操作*/
for（i=1;ifor（i=1;ij=0;
while（j=s[i]）j++;/*检查s[i]是否已在A[]中*/
if（j==k）{A[k]=s[i];C[k]++;k++}/*s[i]从未检测过*/
elseC[j]++;/*s[i]已经检测过*/
}
}
}
测试数据s="castcastsatatatasa\0"
测试结果
A
c
a
s
t
b
C
2
7
4
5
5
【另一解答】
include
include"string.h"
constintcharnumber=128;/*ASCII码字符集的大小*/
voidfrequency（String&s,int&C[]）{
//s是输入字符串，数组C[]中记录每一种字符的出现次数。
for（inti=0;ifor（i=0;iC[atoi（s[i]）]++；/*出现次数累加*/
for（i=0;iif（C[i]>0）cout<<"（"<\t"<}
升级会员 