15.对于一个对称矩阵采用压缩存储，只存放它的上三角部分，并按列存放。例如对于一个n*n的对称矩阵A(如右图)，用一个一维数组B来存放它的上三角部分：B=[A 11 ,A 12 ，A 22 ，A 13 ，A 23 ，A 33 ，A 14 ，…，A 1n ，A 2n ，…，A nn ]同时有两个函数：MAX(i，j)和MIN(i，j)，分别计算下标i和j中的大者与小者。试利用它们给出求任意一个A 在B中存放位置的公式。(若式中没有MAX(i，j)和MIN(i，j)则不给分。)ij 【清华大学1997五(10分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：由于对称矩阵采用压缩存储，上三角矩阵第一列一个元素，第二列两个元素，第j列j个元素。上三角矩阵共有n(n+1)／2个元素。我们将这些元素存储到一个向量B[n(n+1)／2+1]中。可以看到B[k]和矩阵中的元素a ij 之间存在着一一对应关系： 解析：
16.用三元数组表示稀疏矩阵的转置矩阵，并简要写出解题步骤。【山东工业大学1995五(10分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：设用mu、nu和tu表示稀疏矩阵行数、列数和非零元素个数，则转置矩阵的行数、列数和非零元素的个数分别是mu、肌和tu。 转置可按转置矩阵的三元组表中的元素顺序进行，即按稀疏矩阵的列序，从第1列到第肌列，每列中按行值递增顺序，找出非零元素，逐个放入转置矩阵的三元组表中，转置时行列值互换，元素值复制。 按这种方法，第1列的第1个非零元素一定是转置后矩阵的三元组表中的第1个元素，第1列非零元素在第2列非零元素的前面。这种方法时间复杂度是O(n*p)，其中p是非零元素个数，当p和m*n同量级时，时间复杂度为O(n )。另一种转置方法称作快速转置，使时间复杂度降为O(m*n)。 思想是按稀疏矩阵三元组表中元素的顺序取出元素，并放到其在转置矩阵三元组表的相应位置。这就需要求出每列非零元素个数和每列第一个非零元素在转置矩阵三元组表中的位置，设置了两个附加向量：用number数组记录矩阵a中每列的非零元素个数，用position数组记录A中每列第一个非零元素在三元组表中的位置。可用下述公式求出矩阵A中每列第一个非零元素的位置： 法可参见下面算法设计题的21题。) 解析：
快速转置算3
则其对应关系可表示为： ) 二、 设计题(总题数：9，分数：18.00)
17.设有大小不等的n个数据组(n个数据组中数据的总数为m)，顺序存放在空间区D内，每个数据占一个存储单元，数据组的首地址由数组S给出(如右图所示)，试编写将新数据x插入第i个数据组的末尾且属于第i个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。【东北大学2000六(15分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：在向量D内插入元素，首先要查找插入位置，数据x插入第i个数据组的末尾，即第i+1个数据组的开始，而第i(1≤i≤n)个数据组的首地址由数组S(即数组元素S[i])给出。其次，数据x插入后，还要维护数组S，以保持空间区D和数组S的正确的相互关系。if(i==n)D[m]=x； ／／在第n个数据组末尾插入元素i>=l＆＆i=s[i+1]；j—一)D[j+1]=D[j]； ／／第i+1个数据组及以后元素后移 D[s[i+1\\]\\]=x； ／／将新数据x插入 for(j=i+1；j<=nj j++)s[j]++； ／／维护空间区D和数组s的关系 } ／／结束元素插入 m++； ／／空间区D的数据元素个数增1) 解析：
18.以三元组表存储的稀疏矩阵A、B非零元个数分别为m和n。试用类Pascal语言编写时间复杂度为O(m+n)的算法将矩阵B加到矩阵A上去。A的空间足够大，不另加辅助空间。要求描述所用结构。【北京工业大学1997三(10分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：设稀疏矩阵的非零元素的三元组以行序为主存储在三元组表中。为使时间复杂度为O(m+n)。因此需从两个三元组表的最后一个元素开始相加，结果非零元素放在A矩阵三元组表的第m+n一1位置上。矩阵的相加是对应元素的相加：若行号不等，则行号大者是结果矩阵中的元素；若行号相同，则列号大者是结果矩阵中的元素；若行号列号相同，但对应元素值之和为零，不予存储，否则，作为新三元组存到三元组表中。结果的三元组至多是m+n个非零元素。最后若发生对应元素相加和为零的情况，对三元组表中元素要进行整理，以便使第一个三元组存放在下标0的位置上。) 解析：
19.设整数x 1 ，x 2 ，…，x n 已存放在数组A中，编写一Pascal递归过程，输出从这n个数中取出所有k个数的所有组合(k≤n)。例：若A中存放的数是1，2，3，4，5，k为3，则输出结果应为：543，542，541，532，531，52l，432，431，421，321。【东南大学2001三(10分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：请参见第3章算法设计题第10题，只是与本题叙述不同，本质相同。) 解析：
20.编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。【中科院软件所1996】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。) 解析：
21.请编写完整的程序。如果矩阵A中存在这样的一个元素A[i，j]满足条件：A[i，j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵a的所有马鞍点。【上海大学2000三(20分)】【中科院自动化所1997】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：寻找马鞍点最直接的方法是在一行中找出一个最小值元素，然后检查该元素是否是其所在列的最大元素。如是，则输出一个马鞍点，时间复杂度是O(m*(m+n))。另一算法是使用两个辅助数组max和min，存放每列中最大值元素的行号和每行中最小值元素的列号，时间复杂度为O(m*n+m)，但比较次数比前种算法会增加，也多使用向量空间。核心语句段如下： max[n]=(0)； ／／max数组存放各列最大值元素的行号，初始化为行号0 min[m]={0)； ／／min数组存放各行最小值元素的列号，初始化为列号0 for(i=0 ； icm；i++) ／／选各行最小值元素和各列最大值元素 for(j=0；jA[i][j])min[i]=j；}／／修改第i行最小元素的列号 for(i=0；i 解析：
22.给定一个整数数组b[0．N-1]，6中连续的相等元素构成的子序列称为平台。试设计算法，求出b中最长平台的长度。【中科院计算所1999五、2(20分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：用longest代表最长平台的长度，用K指示最长平台在数组b中的起始位置(下标)。用j记住局部平台的起始位置，用i指示扫描b数组的下标，i从0开始，依次和后续元素比较，若局部平台长度(i-j)大于longest时，则修改最长平台的长度(10ngest=i-j)和其在b中的起 始位置(k=j)，直到b数组结束，longest即为所求。核心语句段如下： longest=1；k=0；J=0；i=0； while(i
23.给定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，f] (a≤i≤b一1，c≤j≤d)。设计一算法判定x的值是否在A中，要求时间复杂度为O(m+n)。【东南大学2005
四(10分)2001六(13分) 1994三(17分)】【清华大学1998六(10分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：要求查找时间复杂度为O(m+n)，不能采用常规的二层循环的查找。可以先从右上角(i=a，j=d)元素与x比较，只有三种情况：一是A[i][j]＞x，这种情况下向j小的方向继续查找；二是A[i][j]＜x，下步应向i大的方向查找；三是A[i][j]=x，查找成功。否则，若下标已超出范围，则查找失败。核心语句段如下： while(i<=b&&j>=C&&!flag) ／／初始值：i=a； j=d； flag=0；
if(A[i][j]==x)flag=l； ／／fla9=1是成功查到x的标志 else if(A[i][j]>x)j一一；else i++；) 解析：
24.编写算法，将自然数1～n 按“蛇形”填入n×n矩阵中。例(1～4 )如图所示(用程序实现)。 【南京航空航天大学1997八(12分)】【中科院计算所1996】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：本题的一种算法前面已讨论(请参见本章填空题32题)。这里给出另一种解法。分析数的填法，是按“从右上到左下”的”蛇形”，沿平行于副对角线的各条对角线上，将自然数从小到大填写。当从右上到左下时，坐标i增加，坐标j减小，当j减到小于0时结束，然后j从0开始增加，而i从当前值开始减少，到in一1时，j=j+2，开始从左下向右上填数；而当j>n一1时，i=i+2，开始从右上向左下填数，直到n*n个数填完为止。核心语句段如下： while(i
25.设二维数组a[1一m，1.n]含有m*n个整数。(1)写出算法(Pascal过程或c函数)：判断a中所有元素是否互不相同，输出相关信息(yes／no)；(2)试分析算法的时间复杂度。【华中理工大学1999五(10分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：判断二维数组中元素是否互不相同，只有逐个比较，找到一对相等的元素，就可结论为不是互不相同。如何达到每个元素同其他元素比较一次且只一次?在当前行，每个元素要同本行后面的元素比较一次(下面第一个循环控制变量p的for循环)，然后同第i+1行及以后各行元素比较一次，这就是循环控制变量k和P的二层for循环。 for(i=0 ； i 2)。) 解析：
2
2