第三章 稀疏矩阵

.
第三章 稀疏距阵和广义表2008-02-02 10:01习 题 三
一、单选题
1.在稀疏矩阵的带行指针指向量的链接存储中，每个行单链表中的结点都具有相同的
A 。
A 行号 B 列号 C 元素值 D 地址

2.设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通
转置算法的时间复杂度为 D 。
A O(m) B O(n) C O(n+t) D O(n*t)

3.设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为 B。
A O(1) B O(n) C O(n2) D O(log2n)

二、填空题
1.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的 行号 、 列号 、和
元素值 。

2.在稀疏矩阵所对应的三元组线性表中，每个三元组元素按 行号 为主序、 列号 为辅
助的次序排列。

3.在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为 引用 参数。

4.在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应 大于
等于 对应的三元线性表的长度。

5.在稀疏矩阵的带行指针向量的链接存储中，每个结点包含有 4 个域，在相应的
十字链接存储中，每个结点包含有 5 个域。

6.在稀疏矩阵的十字链接存储中，每个结点的down指针域指向 行号 相同的下一个结点，
right指针指向 列号 相同的下一个结点。

7.一个广义表中的元素为 单 元素和 表 元素两类。

8.一个广义表的深度等于 括号 嵌套的最大层数。

9.在广义表的存储结构中，每个结点均包含有 3 个域。

10.在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为
值 域和 子表指针域 。

11.若把整个广义表也看为一个表结点，则该结点的tag域的值为 true或1 、next域的值
为 NULL或0 。

三、普通题
1.已知一个稀疏矩阵如下图所示:

0 4 0 0 0 0 0
0 0 0 -3 0 0 1
8 0 0 0 0 0 0
0 0 0 5 0 0 0
0 -7 0 0 0 2 0
0 0 0 6 0 0 0
图3-1 具有6行×7列的一个稀疏矩阵

⑴写出它的三元组线性表；
解：((1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,,2,-7),(5,6,2),(6,4,6))


⑵给出它的顺序存储表示；
解：
下标 1 2 3 4 5 6 7 8 ... MaxTerms row(行号) 1 2 2 3 4 5 5 6 col(列号) 2 4 7 1 4 2 6 4 val(元素值) 4 -3 1 8 5 -7 2 6


⑶给出它的转置矩阵的三元组线性表和顺序存储表示；
解：((1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5),(4,6,6),(6,5,2),(7,2,1))


⑷给出对它进行快速转置时,num向量中各分量的值；
⑸给出对它进行快速转置前和转置后,pot向量中各分

量的值。
解：
Col 1 2 3 4 5 6 7 Num[col] 1 2 0 3 0 1 1 pot[col](前) 1 2 4 4 7 7 8 pot[col](后) 2 4 4 7 7 8 9

2.采用顺序存储方式实现稀疏矩阵M1和M2相加的运算，运算结果由变量M返回。
解：
void Add(SMatrix& M1,SMatrix& M2,SMatrix& M)
//采用顺序存储方式实现稀疏矩阵M1和M2相加的运算，运算结果由变量M返回
{
InitMatrix(M);
//若两个矩阵尺寸不同，则给出错误信息并停止运行
if ((M1.m!=M2.m)||(M1.n!=M2.n)){
cerr<<"tow matrix measurenents are different!"<exit(1);
}
M.m=M1.m;M.n=M1.n;
//若两个矩阵均为零矩阵，则无须计算
if(M1.t==0)&&(M2.t==0))
return;
int i=1,j=1; //用i，j 分别指示M1.smt M2.sm数组中待比较元素的下标,初值均
//为1
int k=1; //用k指示M.sm数组中待写入元素的下标，初值为1
while((i<=M1.t)&&(j<=M2.t))
{//把行号较小元素写入到结果矩阵中,若行号相同进行列号的比较,使列号
//较小的元素写入到结果矩阵中,若行、列号均相等，则当相应元素的
//和不为0时才把这个和写入到结果矩阵中
if(M1.sm[i].rowM.sm[k]=M1.sm[i];
i++;k++;
}
else
if(M1.sm[i].row>M2.sm[j].row){
M.sm[k]=M2.sm[j];
j++;k++;
}
else{
if(M1.sm[i].colM.sm[k]=M1.sm[i];
i++;k++;
}
else if(M1.sm[i].col>M2.sm[i].col{
M.sm[k]=M2.sm[j];
j++;k++;
}
else{//此时相应元素的行列号必然相等
if(M.sm[i].val+M2.sm[j].val!=0){
M.sm[k].row=M1.sm[i].row;
M.sm[k].col=M1.sm[i].col;
M.sm[k].val=M1.sm[i].val+M2.sm[j].val;
k++;
}
i++;j++;
}
}
}
while(i<=M1.t)
{ //把M1中的剩余元素写入到结果矩阵M中
M.sm[k]=M1.sm[i];
i++;k++;
}
while(j<=M2.t)
{ // 把M2中的剩余元素写入到结果矩阵M中
M.sm[k]=M2.sm[j];
j++;k++;
}
M.t=k-1;//把写入到结果矩阵M中元素的个数赋给M中保存元素个数的
//变量域
return;
}

3.画出下列每个广义表的带表头附加结点的链接存储结构图并分别计算出它们的长度和深度。
⑴ A=(())
⑵ B=(a,b,c)
⑶ C=(a,(b,(c)))
⑷ D=((a,b),(c,d))
⑸ E=(a,(b,(c,d)),(e))
⑹ F=((a,(b,(),c),((d)),e)))
解：每小题的长度和深度如下表示。
题号 1 2 3 4 5 6 长度 1 3 2 2 3 1 深度 2 1 3 2 3 4

4.编写一个建立广义表链接存储结构的算法，

假定广义表由字符串值提供。
解：
void Create(GLNode*&GL,char*a)
//根据在字符串a中保存的广义表生成其对应的存储结构
{
static int i=0;//定义静态变量i指示a中待处理的字符串位置，每处理一
//个字符后i值增1
if(a[i]=='\0')
return; //当字符串处理结束后返回
if(a[i]=='#'){
GL=NULL;
i++;
}
else if(a[i]=='('){
GL=new GLNode;
GL->tag=True;
i++;
Create(GL->sublist,a);
}
if(GL=new GLNode;
GL->tag=False;
GL->data=a[i];
i++;
}
else{
GL=new GLNode;
GL->tag=False;
GL->data=a[i];
i++;
}
if(GL==NULL) //此时的a[i]必然为')'字符
i++;
else if(a[i]==','){
i++;
Create(GL->next,a);
}
else if((a[i]==')')||(a[i]==',')){
i++;
GL->next=NULL;
}
}

5.编写一个广义表中查找元素字等于给定值的算法，若查找成功则返回数值1，
否则返回数值0。
解：
int Find(GLNode*GL,char ch)
//从广义表GL中查找单元素字符等于ch的算法，若查找成功，则返回数值1，
//否则返回数值0
{
while(GL!=NULL){
if(GL->tag==0){//处理单元素结点
if(GL->data==ch)
return 1;//查找成功返回1
else
GL=GL->next; //否则继续向后查找
}
else{//处理子表结点
int x=Find(GL->sublist,ch);//向子表中继续查找
if(x)//若在子表中查找成功则返回1，否则继续向后查找
return 1;
else
GL=GL->next;
}
}
return 0； //当查找到表为空时返回0
}


类别：数据结构 .