数据结构(张惠涛)第五章习题答案及解析.docx
一、选择题
1.正确答案:C.a[3-1][3]
解析:数组?a?定义为?inta[3][4],表示有3行(行下标范围0到2)和4列(列下标范围0到3)。数组下标从0开始,最大值为n-1。
2.正确答案:B.1032
解析:根据元素?a[i][j]?的地址计算公式为:基地址+(i*列数+j)*元素大小。
在a[2][4]之前,总计12+4=16个元素。偏移量16*2=32,地址1000+32=1032。
因此,地址为1032。
3.正确答案:D.n(n+1)/2
解析:根据对称矩阵压缩存储的特点,数组B中总元素数=1+2+...+n=n(n+1)/2。
4.正确答案:B.随机存储
解析:稀疏矩阵压缩存储(如三元组)通常只存储非零元素及其位置(如(行,列,值)),元素存储非连续,失去随机存储特性。
二、应用题
参考答案:
压缩存储原理:利用连续相同元素重复出现的特性,用(元素值,重复次数)的二元组序列代替原数组。
存储结构:创建一个新的结构数组B[],每个元素包含:
value:原始数组中的元素值。
count:该值连续重复的次数。
示例:
原数组A=[5,5,5,8,8,3,3,3,3]
压缩后B=[(5,3),(8,2),(3,4)]。
空间节省:
原数组空间:O(n)。
压缩后空间:O(k)(k为连续重复段的段数)。
当重复段远少于n时(如全相同元素时k=1),空间大幅优化。
参考答案:
x;
分析:Head操作取第一个元素x(原子元素)。
(2)((x,y),z)
分析:Tail操作移除广义表第一个元素(a,b),剩余元素组成的子表为((x,y),z)。
参考答案:
算法步骤:
初始化累加器sum=0。遍历三元组表中的每个元素:若当前三元组的行号row等于列号col:将value加入sum。返回sum。
代码实现(C/C++):
typedefstruct{//三元组结构
introw,col;
floatvalue;//假设元素为浮点型
}Triple;
typedefstruct{//三元组表
Tripledata[MAXSIZE];
intlen;//非零元素个数
}TSMatrix;
floatdiagonalSum(TSMatrixM){
floatsum=0.0;
for(inti=0;iM.len;i++){
Triplet=M.data[i];
if(t.row==t.col){//判断是否在对角线上
sum+=t.value;
}
}
returnsum;
}
时间复杂度:O(len),其中len为非零元素个数,远小于n2。