算法与数据结构（C 语言版）（冯广慧第2版）课后习题答案 第5、6章.docx

习题答案5

选择题

DABBBAAC

填空题

三元组表，链式存储结构

（1）288

（2）282

（3）72

（4）276

（5）A[2][3]

判断题

对错错错对

应用题

1、[题目分析]三对角矩阵第一行和最后一行各有两个非零元素，其余每行均有三个非零元素，所以共有3n-2个元素。

（1）主对角线左下对角线上的元素下标间有i=j+1关系，k与i和j的关系为k=3(i-1);

主对角线上元素下标间有关系i=j，k与i和j的关系为k=3(i-1)+1;

主对角线上右上那条对角线上元素下标间有关系i=j-1，k与i和j的关系为k=3(i-1)+2。

综合以上三等式，有k=2(i-1)+j(1=i，j=n，|i-j|=1)

（2）i=k/3+1；（1≤k≤3n-2） //k/3取k被3除所得结果的最大整数。下同

j=k-2(i-1)=k-2(k/3)=k%3+k/3

2、特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配单元（对值相同元素只分配一个单元），将非零元素存储在向量中，元素的下标i和j和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小（tm*n），且分布没有规律。用十字链表作存储结构自然失去了随机存取的功能。即使用三元组表的顺序存储结构，存取下标为i和j的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为O(1)，最差情况下是O(n)，因此也失去了随机存取的功能。

算法设计

1、（1）

#includeiostream

#includeiomanip

usingnamespacestd;

intmain()

{

while(1)

{

intn,a[1000];

cinn;

cout请输入n*(n+1)/2个数:;

for(inti=0;in*(n+1)/2;i++)

cina[i];

for(inti=0;in;i++)

{

for(intj=0;jn;j++)

{

if(i=j)

coutsetw(3)a[i*(i+1)/2+j];

else

coutsetw(3)a[j*(j+1)/2+i];

}

coutendl;

}

cout节约n*n-n*(n+1)/2个空间.endl;

}

return0;

}

（2）

#includeiostream

#includeiomanip

usingnamespacestd;

intmain()

{

while(1)

{

intn,a[1000];

cinn;

cout请输入n*(n+1)/2+1个数:;

for(inti=0;in*(n+1)/2+1;i++)

cina[i];

//上三角

for(inti=0;in;i++)

{

for(intj=0;jn;j++)

{

if(i=j)

coutsetw(3)a[(2*n-i+1)*i/2+(j-i)];

else

coutsetw(3)a[n*(n+1)/2];

}

coutendl;

}

cout节约n*n-n*(n+1)/2-1个空间.endl;

}

//下三角

/*for(inti=0;in;i++)

{

for(intj=0;jn;j++)

{

if(i=j)

coutsetw(3)a[i*(i+1)/2+j];

else

coutsetw(3)a[n*(n+1)/2];

}

coutendl;

}*/

return0;

}

（3）

#includeiostream

#includecmath

#includeiomanip

usingnamespacestd;

intmain()

{