数据结构习题(95页)

{

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

联系客服:779662525#qq.com(#替换为@)