文档详情

数据结构(张惠涛)第五章习题答案及解析.docx

发布:2025-06-05约1.33千字共2页下载文档
文本预览下载声明

一、选择题

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。

显示全部
相似文档