數(shù)據(jù)結(jié)構(gòu)課后習題及解析第五章

1、第五章習題5.1 假設(shè)有6行8列的二維數(shù)組A，每個元素占用6個字節(jié)，存儲器按字節(jié)編址。已知A的基地址為1000，計算：數(shù)組A共占用多少字節(jié)；數(shù)組A的最后一個元素的地址；按行存儲時元素A36的地址；按列存儲時元素A36的地址；5.2 設(shè)有三對角矩陣Ann ,將其三條對角線上的元素逐行地存于數(shù)組B(1:3n-2)中，使得Bk= aij ，求：（1） 用i,j表示k的下標變換公式；（2） 用k表示i,j的下標變換公式。5.3假設(shè)稀疏矩陣A和B均以三元組表作為存儲結(jié)構(gòu)。試寫出矩陣相加的算法，另設(shè)三元組表C存放結(jié)果矩陣。5.4在稀疏矩陣的快速轉(zhuǎn)置算法5.2中，將計算positioncol的方法稍加改動，

2、使算法只占用一個輔助向量空間。5.5寫一個在十字鏈表中刪除非零元素aij的算法。5.6畫出下面廣義表的兩種存儲結(jié)構(gòu)圖示： (a), b), ( ), d), (e, f)5.7求下列廣義表運算的結(jié)果：（1） HEAD(a,b),(c,d);（2） TAIL(a,b),(c,d);（3） TAILHEAD(a,b),(c,d);（4） HEADTAILHEAD(a,b),(c,d);（5） TAILHEADTAIL(a,b),(c,d);實習題若矩陣Amn中的某個元素aij是第i行中的最小值，同時又是第j列中的最大值，則稱此元素為該矩陣中的一個馬鞍點。假設(shè)以二維數(shù)組存儲矩陣，試編寫算法求出矩陣中

3、的所有馬鞍點。第五章答案5.2設(shè)有三對角矩陣Ann,將其三條對角線上的元素逐行的存于數(shù)組B1.3n-2中，使得Bk=aij，求：（1）用i,j表示k的下標變換公式；（2）用k表示i、j的下標變換公式。【解答】（1）k=2(i-1)+j(2) i=k/3+1, j=k/3+k%3 （ 取整，%取余）5.4在稀疏矩陣的快速轉(zhuǎn)置算法5.2中，將計算positioncol的方法稍加改動，使算法只占用一個輔助向量空間?！窘獯稹克惴ǎㄒ唬?FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) /*把矩陣A轉(zhuǎn)置到B所指向的矩陣中去，矩陣用三元組表表示*/int co

4、l,t,p,q;int positionMAXSIZE;B-len=A.len; B-n=A.m; B-m=A.n;if(B-len0) position1=1; for(t=1;t=A.len;t+) positionA.datat.col+1+; /*positioncol存放第col-1列非零元素的個數(shù), 即利用poscol來記錄第col-1列中非零元素的個數(shù)*/*求col列中第一個非零元素在B.data 的位置，存放在positioncol中*/for(col=2;col=A.n;col+) positioncol=positioncol+positioncol-1; for(p=1;

5、pdataq.row=A.datap.col; B-dataq.col=A.datap.row; B-dataq.e=A.datap.e; Positioncol+;算法(二)FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) int col,t,p,q;int positionMAXSIZE;B-len=A.len; B-n=A.m; B-m=A.n;if(B-len0) for(col=1;col=A.n;col+) positioncol=0; for(t=1;t0;col-) t=t-positioncol; positioncol=t+1;

6、for(p=1;pdataq.row=A.datap.col; B-dataq.col=A.datap.row; B-dataq.e=A.datap.e; Positioncol+;5.6畫出下面廣義表的兩種存儲結(jié)構(gòu)圖示： (a), b), ( ), d), (e, f)【解答】第一種存儲結(jié)構(gòu) 第二種存儲結(jié)構(gòu)5.7求下列廣義表運算的結(jié)果：（1） HEAD(a,b),(c,d); (a,b)（2） TAIL(a,b),(c,d); (c,d) （3） TAILHEAD(a,b),(c,d); (b)（4） HEADTAILHEAD(a,b),(c,d); b（5） TAILHEADTAIL(a,

7、b),(c,d); (d)提示：第五章 數(shù)組和廣義表習 題1 假設(shè)有6行8列的二維數(shù)組A，每個元素占用6個字節(jié)，存儲器按字節(jié)編址。已知A的基地址為1000，計算：（1） 數(shù)組A共占用多少字節(jié)； （288）（2） 數(shù)組A的最后一個元素的地址； （1282）（3） 按行存儲時，元素A36的地址； （1126）（4） 按列存儲時，元素A36的地址； （1192）注意：本章自定義數(shù)組的下標從1開始。2 設(shè)有三對角矩陣（aij）nn ,將其三條對角線上的元素逐行地存于數(shù)組B(1:3n-2)中，使得Bk= aij ，求：（1） 用i,j表示k的下標變換公式；（2） 用k表示i,j的下標變換公式。 i =

8、k/3 + 1, j = k%3 + i - 1 = k%3 + k/3 或：i = k/3 + 1, j = k - 2( k/3 )2 假設(shè)稀疏矩陣A和B均以三元組表作為存儲結(jié)構(gòu)。試寫出矩陣相加的算法，另設(shè)三元組表C存放結(jié)果矩陣。提示：參考P.28例、P.47例。4在稀疏矩陣的快速轉(zhuǎn)置算法5.2中，將計算positioncol的方法稍加改動，使算法只占用一個輔助向量空間。提示：（1） position k 中為第k列非零元素個數(shù)，k = 1, 2, , n（2） position 0 = 1; （第1列中第一個非零元素的正確位置）（3） position k = position k 1

9、+ position k , k = 1, 2, , n（4） position k = position k 1 , k = n, n 1 , ,15寫一個在十字鏈表中刪除非零元素aij的算法。提示：“刪除”兩次，釋放一次。6畫出下面廣義表的兩種存儲結(jié)構(gòu)圖示： (a), b), ( ), d), (e, f)第一種存儲結(jié)構(gòu)（自底向上看）7求下列廣義表運算的結(jié)果：（1） HEAD(a,b),(c,d);（2） TAIL(a,b),(c,d);（3） TAILHEAD(a,b),(c,d);（4） HEADTAILHEAD(a,b),(c,d); b（5） TAILHEADTAIL(a,b),(c,d); (d)參考題8試設(shè)計一個算法，將數(shù)組A（0:n-1）中的元素循環(huán)右移k位，并要求只用一個元素大小的附加存儲，元素移動或交換次數(shù)為O(n)。9假設(shè)按低下標優(yōu)先（以最左的下標為主序）存儲整數(shù)數(shù)組A（1:8, 1:2, 1:4, 1:7）時，第一個元素的字節(jié)地址是100，每個整數(shù)占4個字節(jié)，問元素A(4, 2, 3, 5)的存儲地址是什么？10. 高下標優(yōu)先（以最右的下標為主序）存儲整數(shù)數(shù)組A（1:8, 1:2,