《数据结构习题数组23》由会员分享，可在线阅读，更多相关《数据结构习题数组23（4页珍藏版）》请在金锄头文库上搜索。
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 表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用 n=9,s=1,m =5，以及 n=9,s=1,m =0，或
2、者 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，假设 A00存放位置在 644(10)，A22存放位置在 676(10)，每个元素占一个空间，问A33(10)存放在什么位置？脚注(10)表示用 10 进制表示。5 设有一个 n n 的对称矩阵 A，如图(a)所示。为了节约存储，可以只存对角线及对角线以上的元
3、素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，如图(b)和图(c)所示。并称之为对称矩阵A的压缩存储方式。试问：(1)存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？(2)若在一维数组B 中从 0 号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存上三角部分的情形下(图(b)应存于一维数组的什么下标位置？给出计算公式。(3)若在一维数组B 中从 0 号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存下三角部分的情形下(图(c)应存于一维数组的什么下标位置？给出计算公式。6 设 A
4、和 B 均为下三角矩阵，每一个都有n 行。因此在下三角区域中各有n(n+1)/2 个元素。另设有一个二维数组C，它有 n 行 n+1 列。试设计一个方案，名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 4 页 -将两个矩阵 A和 B中的下三角区域元素存放于同一个C中。要求将 A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算 A的矩阵元素 aij和 B的矩阵元素 bij在 C中的存放位置下标的公式。7 编写一个算法 frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。8.设有大
5、小不等的 n 个数据组（n 个数据组中数据的总数为 m），顺序存放在空间区 D 内,每个数据占一个存储单元，数据组的首地址由数组 S 给出，（如下图所示），试编写将新数据 x 插入到第 i 个数据组的末尾且属于第 i 个数据组的算法，插入后，空间区 D 和数组 S 的相互关系仍保持正确。Sn,.S2S1未用空间S1.nLU9.设整数 x1,x2,xN 已存放在数组 A 中，编写一 PASCAL 递归过程，输出从这 n 个数中取出所有 k 个数的所有组合（k=n）。例：若 A 中存放的数是 1，2，3，4，5，k 为 3，则输出结果应为：543，542，541，532，531，521，432，4
6、31，421，321。10编写一个过程，对一个 n n 矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。11请编写完整的程序。如果矩阵 A 中存在这样的一个元素 Ai,j满足条件:Ai,j是第 i 行中值最小的元素,且又是第 j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出 m*n 的矩阵 A 的所有马鞍点。12 给定一个整数数组 b0.N-1，b 中连续的相等元素构成的子序列称为平台。试设计算法，求出 b 中最长平台的长度。13.给定 nxm 矩阵 Aa.b,c.d,并设 Ai,jAi,j+1(ai b,c j d-1)和 Ai,jAi+1,j(ai b-1,c j d)
7、.设计一算法判定 X 的值是否在名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 4 页 -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.设二维数组 a1.m,1.n 含有 m*n 个整数。(1)写出算法：判断 a 中所有元素是否互不相同?输出相关信息(yes/no)；(2)试分析算法的时间复杂度。16设计一个算法，把整数数组中所有的偶数放到所有的奇数之前。要求时间、空间效率尽可能高。17.若 S 是 n 个元素的集合，
8、则 S 的幂集 P(S)定义为 S 所有子集的集合。例如，S=(a,b,c),P(S)=(),(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)给定 S，写一递归算法求 P(S)。18.数组 H 1：1000 中存放着 1000 个大小不同的正整数;（1）选择一分类算法使能最快地得到其中 10 个最大的数，简要说明理由；（2）编写一程序 seek()，执行该程序时，在命令行中提供二个参数；seek a n 表示需打印 H 中 n 个最大数。seek I n 表示需打印 H 中 n 个最小数。19已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列
9、中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序（非降序）并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。例如，第一个数组为：4,12,28 第二个数组为：1,7,9,29,45 输出结果为：1,4,7-第一个数组9,12,28,29,45-第二个数组20.设数组 A1.n中，An-2k+1.n-k和n-k+1.n中元素各自从小到大排好名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 4 页 -序，试设计一个算法使An-2k+1.n按从小到大次序排好序。并分析算法所需的计算时间。21.设 A1.100是一
10、个记录构成的数组，B1.100是一个整数数组，其值介于 1 至 100 之间，现要求按B1.100的内容调整 A 中记录的次序，比如当B1=ll 时，则要求将 A1 的内容调整到 A11 中去。规定可使用的附加空间为 O(1)。22.给定有m 个整数的递增有序数组 a1.m和有 n 个整数的递减有序数组b1.n，试写出算法:将数组 a 和 b 归并为递增有序数组 cl.m+n。(要求：算法的时间复杂度为 O(m+n)23在数组 A1.n中有 n 个数据，试建立一个带有头结点的循环链表，头指针为 h，要求链中数据从小到大排列，重复的数据在链中只保存一个。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 4 页 -
