数据结构习题数组23.docVIP

数组（23） 1．设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n, s和m，求出这n个人的出局序列。请以n = 9, s = 1, m = 5为例，人工模拟Josephus的求解过程以求得问题的解。 2． 试编写一个求解Josephus问题的函数。用整数序列1, 2, 3, ……, n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用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)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 5． 设有一个n?n的对称矩阵A，如图(a)所示。为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，如图(b)和图(c)所示。并称之为对称矩阵A的压缩存储方式。试问： (1) 存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？ (2) 若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素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的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素aij和B的矩阵元素bij在C中的存放位置下标的公式。 7． 编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。 8. 设有大小不等的 n 个数据组（n 个数据组中数据的总数为 m） ，顺序存放在空间区 D内,每个数据占一个存储单元，数据组的首地址由数组 S 给出， （如下图所示） ，试编写将新数据 x 插入到第 i 个数据组的末尾且属于第 i 个数据组的算法，插入后，空间区 D 和数组 S 的相互关系仍保持正确。 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 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出 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 矩阵中。如图所示： （用程序实现） 1 3 4 10 2 5 9 11 6 8 12 15 7 13 14 16 15. 设二维数组a[1..m, 1..n] 含有m*n 个整数。 (1) 写出算法：判断 a