{
int i;
for(i=0;s[i]!='\\0';i++) t[i]=s[i]; t[i]=s[i]; }
10．编写一个实现串通配符匹配的函数，其中的通配符只有'?'，它可以和任何一个字符匹配成功。
【算法分析】
本题基本思想与模式匹配的基本思想相似，只是增加了'?'的处理功能。因为'?'可以与任何字符匹配成功，所以当字串中遇到'?'时，可以直接让主串和子串同时后移。 【算法源代码】
int pattern(SString s,SString t) {
int i=1,j=1;
while(i<=s[0]&&j<=t[0]) {if(s[i]==t[j]) {i++;j++; }
else if(t[j]=='?') /*若字串中遇到'?'时，主串和子串同时后移*/ {i++;j++; } else
{i=i-j+2;j=1; }
if(j>t[0]) return(i-t[0]); else return 0; }
第5章 多维数组和广义表
5.1 选择题
1．数组A中，每个元素的长度为3个字节，行下标I从1到8，列下标J从1到10，从首地址SA开始连续存放在存储器内，该数组占用的字节数为（ ） A）80 B）100 C）240 D）270 【答案】C
2．数组A中，每个元素的长度为3个字节，行下标I从1到8，列下标J从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（ ） A）SA＋141 B）SA＋144 C）SA＋222 D）SA＋225 【答案】C 【解析】数组A有8行10列，按行存放时，LOC（A[8][5]）=SA+（（8-1）*10+（5-1））*3=SA+222。
3．一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为（ ） A）n*n B）n*n／2 C）（n+1）*n／2 D）（n+1）*（n+1）／2 【答案】C
【解析】对称矩阵可用上（或下）三角矩阵存储，第一行存1个，第二行存2个，?，第n行存n个，共1+2+?+n=（n+1）*n/2。
4．稀疏矩阵一般的压缩存储方法有两种，即（ ） A）二维数组和三维数组 B）三元组和散列
25
C）三元组和十字链表 D）散列和十字链表 【答案】C
5．设有广义表D=（a,b,D），则其长度为（ ），深度为（ ） A）1 B）3 C）∞ D）5 【答案】B C
6．广义表运算式（Tail（（a，B），（c，d）））的操作结果是（ ） A）（c，d） B）c,d C）（（c，d）） D）d 【答案】C
【解析】由于表中共2个元素，分别是两个广义表（a,b），（c,d），（a,B）是表头，因此Tail求得除表头外的元素构成的表即（（c,d））。
5.2 填空题
1．一维数组的逻辑结构是_____________，存储结构是_____________。 【答案】（1）线性结构 （2）顺序结构
2．对于二维数组或多维数组，分为按_____________和按_____________两种不同的存储方式存储。 【答案】（1）以行为主序 （2）以列为主序
3．二维数组A[c1..d1,c2..d2]共含有_____________个元素。 【答案】（d1-c1+1）*（d2-c2+1）
4．二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，且A[0][0]的地址是200，则A[6][12]的地址是 。 【答案】326
【解析】采用列主序时，LOC（A[6][12]）=LOC（A[0][0]+（12*10+6）*1=326
5．有一个10阶对称矩阵A，采用以行为主序的压缩存储方式，A[0][0]的地址为1，则A[8][5]的地址是 。 【答案】42
【解析】A[8][5]前有8行，第0行1个元素，第1行2个元素，?，第7行8个元素，共（1+8）*8/2=36个元素，第8行前有5个元素，所以A[8][5]的地址为36+5+1=42。
6．广义表运算式HEAD（TAIL（（a，b，c），（x，y，z）））的结果为_____________。 【答案】（x,y,z）
5.3 判断题
1．数组中存储的数可是任意类型的任何数据（ ） 【答案】×
【解析】同一数组中数据元素的类型应该相同（ ）
2．N*N对称矩阵的经过压缩存储后占用的存储单元是原先的1/2。 【答案】×
【解析】应为（N＋1）*N/2个存储单元。
3．稀疏矩阵在用三元组表示法时，可节省空间，但对矩阵的操作会增加算法的难度及耗费更多的时间（ ） 【答案】√
4．广义表不是线性表（ ）
26
【答案】×
【解析】广义表是特殊的线性表，其特殊性在于表中的数据元素还可以是广义表。
5．tail（a,b,c,d）得到的是（b,c,d）（ ） 【答案】√
5.4 应用题
1．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？
【答案】设数组元素A[i][j]存放在起始地址为Loc （ i, j ） 的存储单元中。 ∵ Loc （ 2, 2 ） = Loc （ 0, 0 ） + 2 * n + 2 = 644 + 2 * n + 2 = 676. ∴ n = （ 676 - 2 - 644 ） / 2 = 15
∴ Loc （ 3, 3 ） = Loc （ 0, 0 ） + 3 * 15 + 3 = 644 + 45 + 3 = 692.
2．设有一个n?n的对称矩阵A，为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，称之为对称矩阵A的压缩存储方式。试问：
（1） 存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？
（2） 若在一维数组B中从0号位置开始存放，则对称矩阵中的任一元素aij在只存下三角部分的情形下应存于一维数组的什么下标位置？给出计算公式。 【答案】
（1） 数组B共有1＋2 + 3 +?????? + n= （ n+1 ）*n / 2个元素。
（2） 只存下三角部分时，若i ? j，则数组元素A[i][j]前面有i-1行（1?i-1，第0行第0列不算），第1行有1个元素，第2行有2个元素，??????，第i-1行有i-1个元素。在第i行中，第j号元素排在第j个元素位置，因此，数组元素A[i][j]在数组B中的存放位置为： 1 + 2 + ?????? + （i-1） + j = （ i-1）*i / 2 + j
若i < j，数组元素A[i][j]在数组B中没有存放，可以找它的对称元素A[j][i]。在数组B的第 （j-1）*j / 2 + i位置中找到。
如果第0行第0列也计入，数组B从0号位置开始存放，则数组元素A[i][j]在数组B中的存放位置可以改为： 当i ? j时，= i*（i+1） / 2 + j 当i < j时，= j*（j+1） / 2 + i
3．利用广义表的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来： （1） L1（apple, pear, banana, orange） （2） L2（（apple, pear）, （banana, orange）） （3） L3（（（apple）, （pear）, （bananA）, （orange））） （4） L4（（（（apple）））, （（pear））, （bananA）, orange） （5） L5（（（（apple）, pear）, bananA）, orange） （6） L6（apple, （pear, （bananA）, orange）） 【答案】 （1） Head （Tail （Tail （L1） ） ） （2） Head （Head （Tail （L2） ） ） （3） Head （Head （Tail （Tail （Head （L3） ） ） ） ） （4） Head （Head （Tail （Tail （L4） ） ） ） （5） Head （Tail （Head（L5） ） ） （6） Head （Head （Tail （Head （Tail （L6） ） ） ） ）
3．一个稀疏矩阵为 ，则对应的三元组线性表是什么？其对应的十字链表是什么？ 【答案】由于线性表中的每个结点对应稀疏矩阵的一个非零元素，其中包括3个字段，分别为该元素的行下标、列下标和值，结点间的次序按矩阵的行优先顺序排列，这个线性表用顺序的方法存储在连续的存储区，则对应的三元组为
27
其十字链表形式为：
5.5 算法设计题
1．假定数组A[n]的n个元素中有多个零元素，编写算法将A中所有的非零元素依次移到A的前端。 【算法分析】从前向后找零元素A[i]，从后向前找非零元素A[j]，将A[i]与A[j]交换。 【算法源代码】
void move(int A[],int n) {int i=0,j=n-1; int temp; while(i while(A[i]!=0) i++; while(A[j]==0) j--; if(i {temp=A[i];A[i]=A[j];A[j]=temp;} } } 2．给定有m个整数的递增有序数组A[1..m]和有n个整数的递减有序数组B[1..n]。试写出算法：将数组A和B归并为递增有序数组C[1..m+n]。（要求：算法的时间复杂度为O（m+n）。） 【算法分析】为保证算法的时间复杂度为O（m+n），即需要对数组A和B的数据元素仅扫描一次就能生成C数组，我们可采用设三个下标指针i,j,k初始时分别指向A数组的最后一个元素（A数组的最大值）、B数组的第一个元素（B数组的最大值）、C数组将存放最大值的位置，然后比较A与B数组的最大值大者放C数组k所指单元；在上述比较中若A数组i所指单元数大，则送完后i前移，否则j所指单元数送完后j后移，同时k前移，直到把A与B数组的所有元素扫描完。 【算法源代码】 #define m 3 #define n 4 void Merge(int A[],int B[],int C[]) {int i,j,k; i=m-1; j=0; k=m+n-1; while((i>=0)&&(j<=n-1)) {if(A[i]>B[j]) {C[k]=A[i]; i--;} else {C[k]=B[j]; j++; } k--; } while(i>=0) {C[k]=A[i];i--;k--;} while(j<=n-1) {C[k]=B[j];j++;k--; } } 3．假设稀疏矩阵A采用三元组表示，编写一个函数计算其转置矩阵B，要求B也用三元组表示。 28