数组（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． 设有一个nn的对称矩阵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 令数组全部的值为0中存在这样的一个元素 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. 设二维数组, 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)}给定S，写一递归算法求 P(S)。
18. 数组 H[ 1：1000] 中存放着1000 个大小不同的正整数;   
  （1） 选择一分类算法使能最快地得到其中 10 个最大的数，简要说明理由；
  （2） 编写一程序 seek() ，执行该程序时，在命令行中提供二个参数；
          seek a n<enter> 表示需打印H[ ]中n 个最大数。
seek I n<enter> 表示需打印H[ ]中n 个最小数。
19．已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序（非降序）并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。例如，
第一个数组为：4,12,28
第二个数组为：1,7,9,29,45
输出结果为：1,4,7--------------第一个数组
9,12,28,29,45---------第二个数组   
20. 设数组 ]中，A[-k]和[]中元素各自从小到大排好序，试设计一个算法使A[]按从小到大次序排好序。并分析算法所需的计算时间。
21. 设A[1..100]是一个记录构成的数组，B[1..100]是一个整数数组，其值介于 1至 100 之间，现要求按B[1..100]的内容调整 A 中记录的次序，比如当 B[1]=ll 时，则要求将 A[1]的内容调整到 A[11]中去。规定可使用的附加空间为 O(1)。
22. 给定有m 个整数的递增有序数组 ]和有n 个整数的递减有序数组 ]，试写出算法:将数组a 和 b 归并为递增有序数组 +n]。(要求：算法的时间复杂度为 O(m+n))
23．在数组 ]中有 n 个数据，试建立一个带有头结点的循环链表，头指针为 h，要求链中数据从小到大排列，重复的数据在链中只保存一个。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。