数据结构课程第二章部分习题解答

《数据结构课程第二章部分习题解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程第二章部分习题解答第二章数组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,……

2、,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是无效的参数！"<

3、;/*报名起始位置*/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;j

4、9第5人出局,i=4k=8123467895第1人出局,i=0k=7234678915第7人出局,i=4k=6234689715第4人出局,i=2k=5236894715第3人出局,i=1k=4268934715第6人出局,i=1k=3289634715第9人出局,i=2k=2289634715第2人出局,i=0829634715第8人出局,i=0逆置517436928最终出局顺序例：n=9,s=1,m=0报错信息m=0是无效的参数！例：n=9,s=1,m=10012345678k=9123456789第1人出局,i

5、=0k=8234567891第3人出局,i=1k=7245678931第6人出局,i=3k=6245789631第2人出局,i=0k=5457892631第9人出局,i=4k=4457892631第5人出局,i=1k=3478592631第7人出局,i=1k=2487592631第4人出局,i=0847592631第8人出局,i=0逆置136295748最终出局顺序当m=1时，时间代价最大。达到(n-1)+(n-2)+∙∙∙∙∙∙+1=n(n-1)/2»O(n2)。2-3设有一个线性表(e0,e1,…,en-2,en

6、-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]存放

7、位置在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)所示。为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者

8、称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，如图(b)和图(c)所示。并称之为对称矩阵A的压缩存储方式。试问：(1)存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？(2)若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存上三角部分的情形下(图(b))应存于一维数组的什