（2）若将A视为稀疏矩阵时,画出其三元组表形式压缩存储表。【北京科技大学1999 三（10分）】
??12000??10100???02100???00001??33. 设对角线矩阵A=??00035??（ 行列下标i ,j 满足：1≤i,j≤5）
（1）若将矩阵A压缩存储到数组S 中：
1 2 1 0 1 2 1 0 0 0 1 3 5 下标： 1 2 3 4 5 6 7 8 9 10 11 12 13
试求出A中已存储之元素的行列下标（i， j）与S中元素的下标K之间的关系 （2）若将A视为稀疏距阵时，请画出其行逻辑链接顺序表。【北京科技大学2000 三(10分)】
34．设有一个三维数组a[c1:d1,c2:d2,c3:d3]，其中ci:di是第i维的界偶，如该数组在内存中按行排列，且a[c1,c2,c3]的地址为a0，那么请导出下标变量a[i1,i2,i3]的地址，假设每个元素占L个单元。
【山东师范大学 1999 四、1 （5分）】 35．假定有下列nⅹn矩阵（n为奇数）
??a110.........0a1n??0a22.........a2,n?10??............??......???0......an?1n?1?2,...00..??.......2?????A=??an100ann???
如果用一维数组B按行主次序存储A的非零元素，问： （1）A中非零元素的行下标与列下标的关系；
（2）给出A中非零元素aij 的下标(i,j)与B中的下标R的关系; （3）假定矩阵中每个元素占一个存贮单元且B的起始地址为A0，给出利用aij的下标(i,j)定位在B中的位置公式。 【上海交通大学 1998 三(12分)】 36. 对于一个对称矩阵采用压缩存储，只存放它的上三角部分， ?A11A12A13并按列存放。例如对于一个n*n的对称矩阵A (如右图) ，用一 ???A个一维数组B来存放它的上三角部分：
?22A23B=[A，AA?A33...1112，A22，13，A23，A33，A14，?，A1n，A2n，?，Ann] ?同时有两个函数：MAX(i,j)和MIN(i,j)，分别计算下标i和 ?
...j中的大者与小者。试利用它们给出求任意一个Aij在B中存放 ? 位置的公式。（若式中没有MAX(I,j)和MIN（i，j）则不给分） ???【清华大学 1997 五 (10分)】
37. 用三元数组表示稀疏矩阵的转置矩阵,并简要写出解题步骤。【山东工业大学 1995 五 （10分）】
?A1n??A?2n...A?3n?......??......?A?nn????五 算法设计题
1. 设有大小不等的n 个数据组（n个数据组中数据的总数为m），顺序存放在空间区D内,每个数据占一个存储单元，数据组的首地址由数组S给出，（如下图所示），试编写将新数据x插入到第i个数据组的末尾且属于第i 个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。
【东北大学 2000 六 (15分)】
2. 以三元组表存贮的稀疏矩阵A，B非零元个数分别为m和n。试用类PASCAL语言编写时间复杂度为O（m+n）的算法将矩阵B加到矩阵A上去。A的空间足够大，不另加辅助空间。要求描述所用结构。
【北京工业大学 1997 三 (10分)】
3. 设整数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。 【山东大学 1992 五 (13分)】
类似本题的另外叙述有：
（1）题目基本相同，只是叙述不同，要求用PASCAL语言。【东南大学 2001 三 （10分）】 4．编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。
【中科院软件所 1996 】
5. 设原来将N个自然数1,2,?,N按某个顺序存于数组A中，经过下面的语句计算，使A[I]的值变为A[1]到A[I-1]中小于原A[I]值的个数。
FOR I:=N DOWNTO 1 DO BEGIN C：=0；
FOR J：=1 TO I-1 DO
IF A[J]
编程将经过上述处理后的A还原成原来的A。 【上海大学 1996 二 （16分）】
6．请编写完整的程序。如果矩阵A中存在这样的一个元素A[i,j]满足条件:A[i,j]是第i行中值最小的元素,且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。 【上海大学 2000 三 （20分）】【中科院自动化所 1997】 7．给定一个整数数组b[0..N-1]，b中连续的相等元素构成的子序列称为平台。试设计算法，求出b中最长平台的长度。【中科院计算所 1999 五、2 （20分）】
8. 给定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)。【东南大学2001六(13分)】 类似本题的另外叙述有：
（1）给定整型数组B[0..m,0..n] 。已知B中数据在每一维方向上都按从小到大的次序排列，且整型变量x在B中存在。试设计一个程序段找出一对满足B[i,j]=x的(i,j)值，要求比较次数不超过m+n.。
【清华大学 1998 六（10分）】
(2) 给定n×m矩阵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)。设计一算法以比O(n*m)小的最坏时间复杂性判定值x是否在A中。【东南大学1994三(17分)】 9. 编写算法，将自然数1～n按“蛇形”填入n×n矩阵中。例（1～4）如图所示：（用程序实现） 13410 25911
681215
7131416
【南京航空航天大学 1997 八 （12分）】 【中科院计算所 1996】 10. 设二维数组a[1..m, 1..n] 含有m*n 个整数。
(1) 写出算法(pascal过程或c函数)：判断a中所有元素是否互不相同?输出相关信息(yes/no)；
(2) 试分析算法的时间复杂度。【华中理工大学 1999 五 （10分）】
n
11. 二项式(a+b)展开式的系数为
C（n，0）=1，C（n，n）=1，对于n>=0 C（n，k）=C（n-1，k）+C（n-1，k-1），对于0 (1)试写一个递归算法，根据以上公式生成C（n,k）。（6分） (2)试画出计算C（6，4）的递归树。（4分） (3)试写一个非递归算法，既不用数组也不用栈，对于任意的0<=k<=n计算C(n,k)（6分） 1 n=0n=111 211n=23311n=3 64114n=4 15101051n=51615201561n=6 172135352171n=7 n=818285670562881 【清华大学 1999 五 （16分）】 12． 设任意n个整数存放于数组A(1:n)中，试编写程序，将所有正数排在所有负数前面（要求算法复杂性为0( n)）。 【山东大学 1993 三 (12分)】. 类似本题的另外叙述有： （1）已知数组A[1..n]的元素类型为整型，设计算法调整A，使其左边的所有元素小于零，右边的所有元素大于等于零。（要求算法的时间复杂度和空间复杂度均为0（n）） 【北京理工大学 2000 四、1 （4分）】 （2）设计一个算法，把整数数组中所有的偶数放到所有的奇数之前。要求时间、空间效率尽可能高。 【华南师范大学 1999 六、1 (10分)】 （3）设一系列正整数存放在一个数组中，试设计算法，将所有奇数存放在数组的前半部分，将所有的偶数存放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。请试着分析你实现的算法的时间复杂度和空间复杂度。 【南开大学 2000 三、2】 （4）设计算法将数组A[1..n]调整为左右两部分，使的左边所有的元素小于右边的所有元素，并给出这一划分的分界位置。要求算法的时间复度为O(n)。 【合肥工业大学 2001 五、3 （8分）】 13.若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)。 【东南大学 1993 五 （15分）】【东南大学 1997 五 （15分）】 14．编写算法打印出由指针Hm指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非 零元的个数。注意：行、列及总表头结点的形式为： row down col val right 它们已用val域链接成循环链表。非零元的结点形式也同上，每一行（列）的非零元由right（down）域把它们链接成循环链表，该行（列）的表头结点即为该行（列）循环链表的表头。 【上海大学 1998 五 （16分）】 18. 数组 H[ 1：1000] 中存放着1000个大小不同的正整数; （1） 选择一分类算法使能最快地得到其中10个最大的数，简要说明理由； （2） 编写一程序seek() ，执行该程序时，在命令行中提供二个参数； seek a n seek I n 分)】 19．已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序（非降序）并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。例如， 第一个数组为：4,12,28 第二个数组为：1,7,9,29,45 输出结果为：1,4,7--------------第一个数组 9,12,28,29,45---------第二个数组 【上海大学 1998 四 （20 分）】 20. 设数组A[1..n]中，A[n-2k+1..n-k]和[n-k+1..n]中元素各自从小到大排好序，试设计一个算法使A[n-2k+1..n]按从小到大次序排好序。并分析算法所需的计算时间。【福州大学 1998 四、3 (10分)】 21. 设A[1..100]是一个记录构成的数组，B[1..100]是一个整数数组，其值介于1至100之间，现要求按B[1..100]的内容调整A中记录的次序，比如当B[1]=ll时，则要求将A[1]的内容调整到A[11]中去。规定可使用的附加空间为O(1)。【中科院计算所 2000 七（15分）】 22. 给定有m个整数的递增有序数组a[1..m]和有n个整数的递减有序数组b[1..n]，试写出算法:将数组a和b归并为递增有序数组c[l..m+n]。(要求：算法的时间复杂度为O(m+n)) 【华中理工大学 2000 八、1（10分）】 23．在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个。【南京理工大学 1998 七、2 （7分）】