数据结构习题数组.doc

《数据结构习题数组.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数组（23）1．设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n,s和m，求出这n个人的出局序列。请以n=9,s=1,m=5为例，人工模拟Josephus的求解过程以求得问题的解。2．试编写一个求解Josephus问题的函数。用整数序列1,2,3,……,n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数

2、据结构。然后使用n=9,s=1,m=5，以及n=9,s=1,m=0，或者n=9,s=1,m=10作为输入数据，检查你的程序的正确性和健壮性。3．设有一个线性表(e0,e1,…,en-2,en-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为(en-1,en-2,…,e1,e0)。4．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一

3、个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。5．设有一个n´n的对称矩阵A，如图(a)所示。为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，如图(b)和图(c)所示。并称之为对称矩阵A的压缩存储方式。试问：(1)存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？(2)若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素

4、aij在只存上三角部分的情形下(图(b))应存于一维数组的什么下标位置？给出计算公式。(3)若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存下三角部分的情形下(图(c))应存于一维数组的什么下标位置？给出计算公式。6．设A和B均为下三角矩阵，每一个都有n行。因此在下三角区域中各有n(n+1)/2个元素。另设有一个二维数组C，它有n行n+1列。试设计一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中

5、，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素aij和B的矩阵元素bij在C中的存放位置下标的公式。7．编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。8.设有大小不等的n个数据组（n个数据组中数据的总数为m），顺序存放在空间区D内,每个数据占一个存储单元，数据组的首地址由数组S给出，（如下图所示），试编写将新数据x插入到第i个数据组的末尾且属于第i个数据组的算法，插入后，空间区D和数组S的相互关系仍保持

6、正确。9.设整数x1,x2,…,xN已存放在数组A中，编写一PASCAL递归过程，输出从这n个数中取出所有k个数的所有组合（k<=n）。例：若A中存放的数是1，2，3，4，5，k为3，则输出结果应为：543，542，541，532，531，521，432，431，421，321。10．编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。11．请编写完整的程序。如果矩阵A中存在这样的一个元素A[i,j]满足条件:A[i,j]是第i行中值最小的元素,且又是第j列中值最大的

7、元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。12．给定一个整数数组b[0..N-1]，b中连续的相等元素构成的子序列称为平台。试设计算法，求出b中最长平台的长度。13.给定nxm矩阵A[a..b,c..d],并设A[i,j]≤A[i,j+1](a≤i≤b,c≤j≤d-1)和A[i,j]≤A[i+1,j](a≤i≤b-1,c≤j≤d).设计一算法判定X的值是否在A中,要求时间复杂度为O(m+n)。14.编写算法，将自然数1～n按“蛇形”填入n×n矩阵中。如图所示：（用

8、程序实现）1341025911681215713141615.设二维数组a[1..m,1..n]含有m*n个整数。(1)写出算法：判断a中所有元素是否互不相同?输出相关信息(yes/no)；(2)试分析算法的时间复杂度。16．设计一个算法，把整数数组中所有的偶数放到所有的奇数之前。要求时间、空间效率尽可能高。17.若S是n个元素的集合，则S的幂集P(S)定义为S所有子集的集合。例如，S=(a,b,c),P(S)={(),(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)}