对矩阵进行行压缩存储的目的

㈠ 什么是压缩矩阵

在这里分开来给你解释
矩阵是许多科学计算、工程数学尤其是数值分析中经常研究的对象，矩阵也就是二维数组,所以它可以采用顺
序存储是来存储其中的元素。但有时矩阵的阶数很高，同时在矩阵中游很多值相同的元素，或大多数元素的值为
零，这时再采用严格的顺序存储显然是很浪费空间的，因为存储零元素或许多值相同的元素是没有意义的，因此为
了节省存储空间，对这类矩阵通常采用压缩存储。
压缩存储：为多个值相同的元素值分配一个存储空间，对零元素不分配存储空间。
特殊矩阵：各个元素的分布有一定规律
系数矩阵：矩阵中多数元素值为零。

㈡ 矩阵的压缩存储是什么

二维数组在形式上是矩阵，因此一般用二维数组来存储矩阵。在不压缩存储的情况下，矩阵采用按行优先或按列优先方式存储，占用的存储单元数等于矩阵的元素个数。在实际应用中，经常出现一些阶数很高的矩阵，同时在矩阵中非零元素呈某种规律分布或者矩阵中有大量的零元素，若仍然用常规方法存储，可能存储重复的非零元素或零元素，这将造成存储空间的大量浪费。因此对这类矩阵进行压缩存储，从而合理地利用存储空间。

为了节省存储空间，可以利用特殊矩阵的规律，对它们进行压缩存储，也就是说为多个值相同的元素只分配一个存储单元，对零元素不分配空间。适合压缩存储的矩阵一般是值相同的元素或者零元素在矩阵中分布有一定规律的特殊矩阵和稀疏矩阵。常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵。

㈢ 对稀疏矩阵进行压缩的目的

我给你源码记得顶我啊！！最主要的是把分给我哦！！
include<time.h>/*用于下面的srand((unsigned)time(NULL));函数的头文件*/
#include<stdio.h>
#include<stdlib.h>
#define MAX_ARRAY_DIM 2
#define MAXSIZE 100
typedef struct
{
int aa[MAX_ARRAY_DIM];
int dim;
int *base;
}array;
typedef struct
{
int i,j;/*记录非零元的行与列坐标*/
int e;/*记录非零原的数值*/
}triple;/*构成非零元素*/
typedef struct
{
triple data[MAXSIZE];/*预期非零原最大个数*/
int *rpos;/*记录各行第一个非零原的位置表*/
int mu,nu,tu;/*记录稀疏矩阵的行列和非零原个数*/
}tsmatrix;
main()
{
void initarray(array *a);/*数组初始化*/
void createsMatrix(array *a);/*创建稀疏矩阵*/
void inittsmatrix(array *a,tsmatrix *m);/*初始化稀疏矩阵三元组*/
void outputtsmatrix(tsmatrix *m);/*输出稀疏矩阵*/
void destroysmatrix(array *a);/*销毁稀疏矩阵*/
void outputarray(array *a);/*输出数组*/
void subtmatrix(tsmatrix *m,tsmatrix *n,tsmatrix *q);/*系数矩阵相减*/
void addsmatrix(tsmatrix *m,tsmatrix *n,tsmatrix *q);/*系数矩阵相加*/
void multsmatrix(tsmatrix *m,tsmatrix *n,tsmatrix *q);/*稀疏矩阵相乘*/
array a;
tsmatrix m,n,q;
int flag1=1,i;
srand((unsigned)time(NULL));
initarray(&a);/*初始化数组*/
createsMatrix(&a);/*创建稀疏矩阵*/
inittsmatrix(&a,&m);/*初始化稀疏矩阵三元组*/
outputtsmatrix(&m);/*输出稀疏矩阵*/
outputarray(&a);/*输出数组*/
destroysmatrix(&a);/*销毁原数组*/
initarray(&a);/*初始化数组*/
createsMatrix(&a);/*创建稀疏矩阵*/
inittsmatrix(&a,&n);/*初始化稀疏矩阵三元组*/
outputtsmatrix(&n);/*输出稀疏矩阵*/
outputarray(&a);/*输出数组*/
destroysmatrix(&a);/*销毁原数组*/
printf("2个三元数组已经创建成功，您要进行什么操作？\n1.(m+n)\n2.(m-n)\n3.(m*n)\n4.(n-m)\n");
while(flag1)
{
fflush(stdin);
scanf("%d",&i);
switch(i)
{
case 1:addsmatrix(&m,&n,&q);flag1=0;break;
case 2:subtmatrix(&m,&n,&q);flag1=0;break;
case 3:multsmatrix(&m,&n,&q);flag1=0;break;
case 4:subtmatrix(&n,&m,&q);flag1=0;break;
default:printf("输入错误请重新输入\n您要进行什么操作？1.(m+n)\n2.(m-n)\n3.(m*n)\n4.(n-m)\n\n");
}
}
printf("运算结果为\n");
outputtsmatrix(&q);/*输出运算结果*/
}
void initarray(array *a)/*创建数组*/
{
int i,j;
printf("请输入要创建的维数,(由于这里的作用是创建稀疏矩阵，建议输入2)\n");
scanf("%d",&a->dim);
if(a->dim!=MAX_ARRAY_DIM)
{
printf("输入维数超过界限\n");
exit(1);
}
for(i=0;i<a->dim;i++)
{
printf("请输入第%d维的数据",i+1);
scanf("%d",&a->aa[i]);
if(a->aa[i]<1)
{
printf("输入超过范围\n");
exit(1);
}
}
j=1;
for(i=0;i<a->dim;i++)
j*=a->aa[i];
if(!(a->base=(int *)malloc(j*sizeof(int))))
{
printf("开辟空间失败\n");
exit(1);
}
printf("数组创建成功\n");
}
void createsMatrix(array *a)/*创建稀疏矩阵*/
{
int i,j,k,l,m,n,flag1;
printf("是手动输入还是电脑自行创建？\n选1.电脑自行创建\n选0.手动创建\n");
scanf("%d",&i);
if(i!=1&&i!=0)
{
printf("输入格式错误\n");
exit(1);
}
if(i==0)/*手动输入*/
{
printf("请输入\n");
for(j=0;j<a->aa[0];j++)
{
for(k=0;k<a->aa[1];k++)
scanf("%d",&a->base[j*a->aa[1]+k]);
printf("\n");
}
}
else/*电脑自动输入*/
{
l=rand()%(a->aa[0]*a->aa[1]/4)+1;/*预期计算要输入多少个非零元*/
for(j=0;j<a->aa[0];j++)/*先将程序中所有的元素赋予0*/
for(k=0;k<a->aa[1];k++)
a->base[j*a->aa[1]+k]=0;
m=0;
while(m<l)/*输入l个非零元*/
{
flag1=1;
while(flag1)/*被赋予的元素原本必须是零*/
{
i=rand()%a->aa[0];/*自动选择行*/
j=rand()%a->aa[1];/*自动选择列*/
if(a->base[i*a->aa[1]+j]==0)/*所选择的元素是0*/
flag1=0;/*推出循环，否则继续循环直到，是零为止*/
}
flag1=1;
a->base[i*a->aa[1]+j]=rand()%10;/*赋值10以内*/
n=rand()%10;
if(n<5)
a->base[i*a->aa[1]+j]*=-1;/*输入正负*/
m++;
}
}
}
void inittsmatrix(array *a,tsmatrix *m)/*稀疏矩阵非零原初始化*/
{
int i,j,k=0,*num;
for(i=0;i<a->aa[0];i++)/*输入非零原坐标及数据*/
for(j=0;j<a->aa[1];j++)
if(a->base[i*a->aa[1]+j]!=0)
{
m->data[k+1].i=i+1;
m->data[k+1].j=j+1;
m->data[k+1].e=a->base[i*a->aa[1]+j];
k++;
}
m->mu=a->aa[0];/*记录行*/
m->nu=a->aa[1];/*记录列*/
m->tu=k;/*记录非零原数量*/
if(!(num=(int *)malloc((m->mu+1)*sizeof(int))))/*num用于记录每行的非零原的个数*/
{
printf("空间开辟失败\n");
exit(1);
}
if(!(m->rpos=(int *)malloc((m->mu+1)*sizeof(int))))/*本人认为数据结构上的rpos定义有错误，如果某一行全都是非零元那m->rpos[i]=0并不是m->rpos[i-1]+num[i-1]所以以下的rpos操作可能与书上的原意不符*/
{
printf("空间开辟失败\n");
exit(1);
}
for(i=0;i<=m->mu;i++)/*初始化num*/
num[i]=0;
for(i=1;i<=m->tu;i++)/*记录每行非零原的个数*/
++num[m->data[i].i];
if(num[1]==0)/*如果第一行没有非零原的话那m->rops[1]=0，这就是我修改的原因，如果按照书上写的话，那应该是1，对以后的操作有麻烦*/
{
m->rpos[1]=0;
j=0;
}
else/*否则记1*/
{
m->rpos[1]=1;
j=num[1];
}
for(i=2;i<=m->mu;i++)/*运算*/
{
if(num[i]==0)
m->rpos[i]=0;/*当前这一行并没有非零元所以记录1*/
else/*否则记录所对应的序列号*/
{
m->rpos[i]=j+1;
j+=num[i];
}
if(j>=m->tu)/*如果j的数量已经等于所有非零原的数量,那就应该退出循环*/
break;
}
while(i<=m->mu)/*如果半路退出循环，那么剩下的每行，都没有非零原*/
i++,m->rpos[i]=0;
}
void outputtsmatrix(tsmatrix *m)/*输出稀疏矩阵*/
{
int i;
printf("三元组表为\n");
for(i=1;i<=m->tu;i++)
printf("%d行 %d列 %d\n",m->data[i].i,m->data[i].j,m->data[i].e);
printf("行为%d列为%d\n",m->mu,m->nu);
for(i=1;i<=m->mu;i++)
printf("%d行的第一个元素所在位置表的位置是%d\n",i,m->rpos[i]);

}
void destroysmatrix(array *a)/*销毁稀疏矩阵*/
{
if(!a->base)exit(1);
free(a->base);a->base=NULL;
printf("\n稀疏矩阵数组销毁成功(*^__^*) \n\n");
}
void outputarray(array *a)/*输出数组*/
{
int i,j;
for(i=0;i<a->aa[0];i++)
{
for(j=0;j<a->aa[1];j++)
printf("%2d ",a->base[i*a->aa[1]+j]);
printf("\n");
}
}
void smatrix(tsmatrix *m,tsmatrix *t)/*复制稀疏矩阵*/
{
int i;
t->mu=m->mu,t->nu=m->nu,t->tu=m->tu;
if(!(t->rpos=(int *)malloc((t->mu+1)*sizeof(int))))
{
printf("开辟控件失败\n");
exit(1);
}
if(t->tu)
{
for(i=1;i<=m->tu;i++)
{
t->data[i].i=m->data[i].i;
t->data[i].j=m->data[i].j;
t->data[i].e=m->data[i].e;
}
}
for(i=1;i<=t->mu;i++)
t->rpos[i]=m->rpos[i];
}
void subtmatrix(tsmatrix *m,tsmatrix *n,tsmatrix *q)/*稀疏矩阵相减*/
{
int i,j,k,a,b,c,x,y,z,*num;
q->mu=m->mu>n->mu?m->mu:n->mu;
q->nu=m->nu>n->nu?m->nu:n->nu;
q->tu=0;
if(!(num=(int *)malloc((q->mu+1)*sizeof(int))))
{
printf("创建空间失败\n");
exit(1);
}
if(!(q->rpos=(int *)malloc((q->mu+1)*sizeof(int))))
{
printf("创建空间失败\n");
exit(1);
}
for(i=1;i<=q->mu;i++)
num[i]=0;
if(m->tu==0)
smatrix(n,q);
else if(n->tu==0)
smatrix(m,q);
else
{
i=j=k=1;
while(i<=m->tu&&j<=n->tu)
{
a=m->data[i].i;
b=m->data[i].j;
c=m->data[i].e;/*分别记录m的3元组的数据*/
x=n->data[j].i;
y=n->data[j].j;
z=n->data[j].e;
if(a==x)/*如果m,n行相等*/
{
if(b==y)/*如果行列都相等*/
{
if(c-z!=0)/*如果m-n!=0*/
{
num[a]++;
q->data[k].i=a;
q->data[k].j=b;
q->data[k].e=c-z;
k++;
}
i++,j++;/*无论是否m-n==0i,j都要+1*/
}
else if(b<y)/*如果行相等但是列不相等q下一个三元组应该取坐标相对较小的*/
{
num[a]++;
q->data[k].i=a;
q->data[k].j=b;
q->data[k].e=c;
k++;
i++;
}
else if(b>y)
{
num[x]++;
q->data[k].i=x;
q->data[k].j=y;
q->data[k].e=-z;
k++;j++;
}
else
printf("不可能出现的事情\n");
}
else if(a>x)
{
num[x]++;
q->data[k].i=x;
q->data[k].j=y;
q->data[k].e=-z;
k++;j++;
}
else if(a<x)
{
num[a]++;
q->data[k].i=a;
q->data[k].j=b;
q->data[k].e=c;
k++;i++;
}
else
printf("不可能发生的事情\n");
}
if(i>m->tu&&j<=n->tu)/*如果m的三元组记录完了但是n的三元组没有记录完那么剩下的应该全复制*/
{
while(j<=n->tu)
{
num[n->data[j].i]++;
q->data[k].i=n->data[j].i;
q->data[k].j=n->data[j].j;
q->data[k++].e=-n->data[j++].e;
}
}
else if(j>n->tu&&i<=m->tu)/*如果n的三元组记录完了但是m的三元组没有记录完那么剩下的应该全复制*/
{
while(i<=m->tu)
{
n->data[m->data[i].i].i;
q->data[k].i=m->data[i].i;
q->data[k].j=m->data[i].j;
q->data[k++].e=m->data[i++].e;
}
}
q->tu=k-1;
if(num[1]==0)/*如果第一行没有非零原的话那m->rops[1]=0，这就是我修改的原因，如果按照书上写的话，那应该是1，对以后的操作有麻烦*/
{
q->rpos[1]=0;
j=0;
}
else/*否则记1*/
{
q->rpos[1]=1;
j=num[1];
}
for(i=2;i<=q->mu;i++)/*运算*/
{
if(num[i]==0)
q->rpos[i]=0;/*当前这一行并没有非零元所以记录1*/
else/*否则记录所对应的序列号*/
{
q->rpos[i]=j+1;
j+=num[i];
}
if(j>=q->tu)/*如果j的数量已经等于所有非零原的数量,那就应该退出循环*/
break;
}
while(i<=q->mu)/*如果半路退出循环，那么剩下的每行，都没有非零原*/
{
i++;
q->rpos[i]=0;
}
}
}
void addsmatrix(tsmatrix *m,tsmatrix *n,tsmatrix *q)/*稀疏矩阵相加*/
{
int i,j,k,a,b,c,x,y,z,*num;
q->mu=m->mu>n->mu?m->mu:n->mu;
q->nu=m->nu>n->nu?m->nu:n->nu;
q->tu=0;
if(!(num=(int *)malloc((q->mu+1)*sizeof(int))))
{
printf("创建空间失败\n");
exit(1);
}
if(!(q->rpos=(int *)malloc((q->mu+1)*sizeof(int))))
{
printf("创建空间失败\n");
exit(1);
}
for(i=1;i<=q->mu;i++)
num[i]=0;
if(m->tu==0)
smatrix(n,q);
else if(n->tu==0)
smatrix(m,q);
else
{
i=j=k=1;
while(i<=m->tu&&j<=n->tu)
{
a=m->data[i].i;
b=m->data[i].j;
c=m->data[i].e;/*分别记录m的3元组的数据*/
x=n->data[j].i;
y=n->data[j].j;
z=n->data[j].e;
if(a==x)/*如果m,n行相等*/
{
if(b==y)/*如果行列都相等*/
{
if(c+z!=0)/*如果m+n!=0*/
{
num[a]++;
q->data[k].i=a;
q->data[k].j=b;
q->data[k].e=c+z;
k++;
}
i++,j++;/*无论是否m+n==0i,j都要+1*/
}
else if(b<y)/*如果行相等但是列不相等q下一个三元组应该取坐标相对较小的*/
{
num[a]++;
q->data[k].i=a;
q->data[k].j=b;
q->data[k].e=c;
k++;
i++;
}
else if(b>y)
{
num[x]++;
q->data[k].i=x;
q->data[k].j=y;
q->data[k].e=z;
k++;j++;
}
else
printf("不可能出现的事情\n");
}
else if(a>x)
{
num[x]++;
q->data[k].i=x;
q->data[k].j=y;
q->data[k].e=z;
k++;j++;
}
else if(a<x)
{
num[a]++;
q->data[k].i=a;
q->data[k].j=b;
q->data[k].e=c;
k++;i++;
}
else
printf("不可能发生的事情\n");
}
if(i>m->tu&&j<=n->tu)/*如果m的三元组记录完了但是n的三元组没有记录完那么剩下的应该全复制*/
{
while(j<=n->tu)
{
num[n->data[j].i]++;
q->data[k].i=n->data[j].i;
q->data[k].j=n->data[j].j;
q->data[k++].e=n->data[j++].e;
}
}
else if(j>n->tu&&i<=m->tu)/*如果n的三元组记录完了但是m的三元组没有记录完那么剩下的应该全复制*/
{
while(i<=m->tu)
{
n->data[m->data[i].i].i;
q->data[k].i=m->data[i].i;
q->data[k].j=m->data[i].j;
q->data[k++].e=m->data[i++].e;
}
}
q->tu=k-1;
if(num[1]==0)/*如果第一行没有非零原的话那m->rops[1]=0，这就是我修改的原因，如果按照书上写的话，那应该是1，对以后的操作有麻烦*/
{
q->rpos[1]=0;
j=0;
}
else/*否则记1*/
{
q->rpos[1]=1;
j=num[1];
}
for(i=2;i<=q->mu;i++)/*运算*/
{
if(num[i]==0)
q->rpos[i]=0;/*当前这一行并没有非零元所以记录1*/
else/*否则记录所对应的序列号*/
{
q->rpos[i]=j+1;
j+=num[i];
}
if(j>=q->tu)/*如果j的数量已经等于所有非零原的数量,那就应该退出循环*/
break;
}
while(i<=q->mu)/*如果半路退出循环，那么剩下的每行，都没有非零原*/
{
i++;
q->rpos[i]=0;
}
}
}
void multsmatrix(tsmatrix *m,tsmatrix *n,tsmatrix *q)/*稀疏矩阵相乘*/
{
int i,j,k,l,o,p,x,y,*a,*num;
if(!(a=(int *)malloc(((m->mu+1)*(n->nu+1))*sizeof(int))))/*创建一个跟q相同大小的空间用来记录此坐标是否已经输入一个数*/
{
printf("开辟空间失败\n");
exit(1);
}
if(m->nu!=n->mu)
{
printf("不匹配\n");
exit(1);
}
q->mu=m->mu,q->nu=n->nu,q->tu=0;/*初始化*/
if(!(num=(int *)malloc((m->mu+1)*sizeof(int))))
{
printf("开辟空间失败\n");
exit(1);
}
if(!(q->rpos=(int *)malloc((q->mu+1)*sizeof(int))))
{
printf("空间开辟失败");
exit(1);
}
for(i=1;i<=q->mu;i++)
num[i]=0;
if(m->tu*n->tu!=0)
{
for(i=1;i<=m->mu;i++)/*初始化a数组*/
for(j=1;j<=n->nu;j++)
a[i*n->nu+j]=0;
for(i=1;i<=m->tu;i++)
{
o=m->data[i].i;
p=m->data[i].j;
if(n->rpos[p]==0)
continue;
l=p+1;
while(n->rpos[l]==0&&l<=n->mu)
l++;
if(l>n->mu)
j=n->tu+1;
else
j=n->rpos[l];
for(k=n->rpos[p];k<j;k++)/*k-j的范围是本行非零远的个数*/
{
x=n->data[k].i;/*x,y分别是n->data[k]的行和列*/
y=n->data[k].j;
if(a[o*n->nu+y]!=0)
q->data[a[o*n->nu+y]].e+=m->data[i].e*n->data[k].e;/*如果此空间已经输入一个数了，那么在相应的位置累加*/
else
{
q->data[++q->tu].e=m->data[i].e*n->data[k].e;
q->data[q->tu].i=o;
q->data[q->tu].j=y;
a[o*n->nu+y]=q->tu;/*此位置记录q->tu*/
num[o]++;
}
}
}
for(i=1;i<=q->mu;i++)
printf("%d ",num[i]);
if(num[1]==0)/*如果第一行没有非零原的话那m->rops[1]=0，这就是我修改的原因，如果按照书上写的话，那应该是1，对以后的操作有麻烦*/
{
q->rpos[1]=0;
j=0;
}
else/*否则记1*/
{
q->rpos[1]=1;
j=num[1];
}
for(i=2;i<=q->mu;i++)/*运算*/
{
if(num[i]==0)
q->rpos[i]=0;/*当前这一行并没有非零元所以记录1*/
else/*否则记录所对应的序列号*/
{
q->rpos[i]=j+1;
j+=num[i];
}
if(j>=q->tu)/*如果j的数量已经等于所有非零原的数量,那就应该退出循环*/
break;
}
while(i<=q->mu)/*如果半路退出循环，那么剩下的每行，都没有非零原*/
i++,q->rpos[i]=0;
}
}

㈣ 数据结构2

第11题 (2.0) 分
(B )存储方式适用于折半查找。

A、键值有序的单链表
B、键值有序的顺序表
C、键值有序的双链表
D、键值无序的顺序表

第12题 (2.0) 分
在顺序表中，数据元素之间的逻辑关系用( B)。

A、数据元素的相邻地址表示
B、数据元素在表中的序号表示
C、指向后继元素的指针表示
D、数据元素的值表示

第13题 (2.0) 分
若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用( )存储方式最节省运算时间(B )。

A、单链表
B、顺序表
C、双链表
D、单循环链表

第14题 (2.0) 分
若只在线性表的首、尾两端进行插入操作，宜采用的存储结构为(B )。

A、顺序表
B、用头指针表示的单循环链表
C、用尾指针表示的单循环链表
D、单链表

第15题 (2.0) 分
算法分析是指(D )。

A、分析算法的正确性
B、分析算法的可读性
C、分析算法的健壮性
D、分析算法的时空性能

第16题 (2.0) 分
算法的时间复杂度取决于(A )。

A、问题的规模
B、数据的初始状态
C、A和B
D、以上都不是

第17题 (2.0) 分
若进栈序列为a,b,c，则通过入出栈操作能得到的a,b,c的不同排列个数为(B )。

A、4
B、5
C、6
D、7

第18题 (2.0) 分
下列关于串的叙述中，正确的是(A )。

A、一个串的字符个数即该串的长度
B、一个串的长度至少是1
C、空串是由空格字符组成的串
D、两个串若长度相同，则它们相等

第19题 (2.0) 分
下列叙述错误的是( )。

A、多维数组是向量的推广。
B、多维数组是非线性结构。
C、如果将二维数组看成由若干个行向量组成的一维数组，则为线性结构。
D、对矩阵进行压缩存储的目的是为了数据加密。

第20题 (2.0) 分
若下图表示某广义表，则它是一种(A )。

A、线性表
B、纯表
C、再入表
D、递归表

有一题不清楚，你再想想

㈤ 对矩阵压缩存储是为了( ). a方便运算 b节省空间 c方便存储 d提高运算速度

大多数情况下目的是b，有时也会兼顾a,c,d

㈥ 数据结构题

第1题 (2.0) 分 某二叉树的先根遍历序列和后根遍历序列相同，则该二叉树的特征是( )。A、高度等于其结点数B、任一结点无左孩子C、任一结点无右孩子D、空或只有一个结点第2题 (2.0) 分 关于哈夫曼树，下列叙述正确的是( )。A、可能有度为1的结点B、总是完全二叉树C、有可能是满二叉树D、WPL是深度最大叶子的带权路径长度第3题 (2.0) 分 给定整数集合{3,5,6,9,12}，与之对应的哈夫曼树是( )。第4题 (2.0) 分 在n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素个数为( )。A、nB、n*eC、eD、2*e第5题 (2.0) 分 对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为( )。A、求顶点的邻接点B、求顶点的度C、深度优先遍历D、广度优先遍历第6题 (2.0) 分 为便于判别有向图中是否存在回路，可借助于( )。A、广度优先搜索算法B、最小生成树算法C、最短路径算法D、拓扑排序算法第7题 (2.0) 分 在待排关键字序列基本有序的前提下，效率最高的排序方法是( )。A、直接插入排序B、快速排序C、直接选择排序D、归并排序第8题 (2.0) 分 对n个元素进行冒泡排序，最好情况下的只需进行( )对相邻元素之间的比较。A、nB、n-1C、n+1D、n/2第9题 (2.0) 分 对包含n个关键字的散列表进行检索，平均检索长度是( )。A)O(log2n)B)O(n)C)不直接依赖于n D)O(nlog2n)A、AB、BC、CD、D第10题 (2.0) 分 下列查找方法中，不属于动态的查找方法是( )。A、二叉排序树法B、平衡树法C、散列法D、二分查找法第11题 (2.0) 分 ( )存储方式适用于折半查找。A、键值有序的单链表B、键值有序的顺序表C、键值有序的双链表D、键值无序的顺序表第12题 (2.0) 分 在顺序表中，数据元素之间的逻辑关系用( )。 A、数据元素的相邻地址表示B、数据元素在表中的序号表示C、指向后继元素的指针表示D、数据元素的值表示第13题 (2.0) 分 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用( )存储方式最节省运算时间( )。A、单链表B、顺序表C、双链表D、单循环链表第14题 (2.0) 分 若只在线性表的首、尾两端进行插入操作，宜采用的存储结构为( )。A、顺序表B、用头指针表示的单循环链表C、用尾指针表示的单循环链表D、单链表第15题 (2.0) 分 算法分析是指( )。A、分析算法的正确性B、分析算法的可读性C、分析算法的健壮性D、分析算法的时空性能第16题 (2.0) 分 算法的时间复杂度取决于( )。A、问题的规模B、数据的初始状态C、A和BD、以上都不是第17题 (2.0) 分 若进栈序列为a,b,c，则通过入出栈操作能得到的a,b,c的不同排列个数为( )。A、4B、5C、6D、7第18题 (2.0) 分 下列关于串的叙述中，正确的是( )。A、一个串的字符个数即该串的长度B、一个串的长度至少是1C、空串是由空格字符组成的串D、两个串若长度相同，则它们相等第19题 (2.0) 分 下列叙述错误的是( )。A、多维数组是向量的推广。B、多维数组是非线性结构。C、如果将二维数组看成由若干个行向量组成的一维数组，则为线性结构。D、对矩阵进行压缩存储的目的是为了数据加密。第20题 (2.0) 分 若下图表示某广义表，则它是一种( )。 A、线性表B、纯表C、再入表D、递归表第21题 (2.0) 分某完全二叉树有7个叶子，则其结点总数为( )。A、14B、13C、13或14D、以上都不是第22题 (2.0) 分 在二叉链表上交换所有分支结点左右子树的位置，则利用( )遍历方法最合适。A、前序B、中序C、后序D、按层次第23题 (2.0) 分 线索二叉树中某结点为叶子的条件是( )。 A、p-> lchild!=NULL || p-> rchild!=NULLB、p-> ltag==0 || p-> rtag==0C、p-> lchild!=NULL & & p-> rchild!=NULLD、p-> ltag==1 & & p-> rtag==1第24题 (2.0) 分 连通图是指图中任意两个顶点之间( )。A、都连通的无向图B、都不连通的无向图C、都连通的有向图D、都不连通的有向图第25题 (2.0) 分 在n个顶点和e条边的无向图的邻接表中，边结点的个数为( )。A、nB、n*eC、eD、2*e第26题 (2.0) 分 图的深度遍历必须借助( )作为辅助空间。A、栈B、队列C、查找表D、数组第27题 (2.0) 分 下列排序方法中，稳定的是( )。A、直接选择排序B、冒泡排序C、快速排序D、希尔排序第28题 (2.0) 分 在不完全排序的情况下，就可以找出前几个最大值的方法是( )。A、快速排序B、直接插入排序C、堆排序D、归并排序第29题 (2.0) 分 n个记录直接选择排序时所需的记录最多交换次数是( )。A、n-1B、nC、n(n-1)/2D、n(n+1)/2第30题 (2.0) 分 从理论上讲，将数据以( )结构存放，查找一个数据的时间不依赖于数据的个数n。A、二叉查找树 B、链表C、散列表D、顺序表第31题 (2.0) 分 静态查找表与动态查找表二者的根本差别在于( )。A、它们的逻辑结构不一样B、施加在其上的操作不同C、所包含的数据元素的类型不一样D、存储实现不一样第32题 (2.0) 分 单链表中增加头结点的目的是为了( )。A、使单链表至少有一个结点B、标识表结点中首结点的位置C、方便运算的实现D、说明单链表是线性表的链式存储第33题 (2.0) 分 设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是( )。s->next=p->next;p->next=s;t=p->data;p->data=s->data;s->data=t;A、结点*p与结点*s的数据域互换B、在p所指结点的元素之前插入元素C、在p所指结点的元素之后插入元素D、在结点*p之前插入结点*s第34题 (2.0) 分 若结点的存储地址与结点内容有某种确定的关系，则相应的存储结构应为( )。A、顺序存储结构B、链式存储结构C、索引存储结构D、散列存储结构第35题 (2.0) 分 下列各式中，按增长率由小至大的顺序正确排列的是( )。 A．n1/2，n!，2n，n3/2B．n3/2，2n，nlogn，2100C．2n，logn，nlogn，n3/2D．2100，logn, 2n, nn第36题 (2.0) 分 栈和队列的共同特点是( )。A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点第37题 (2.0) 分 引起循环队列队头位置发生变化的操作是( )。A、入队B、出队C、取队头元素D、取队尾元素第38题 (2.0) 分 设S=”abc”;T=”xyz”，则strcmp(S,T)的值为( )。A、正数 B、负数C、零D、不确定第39题 (2.0) 分 关于十字链表中的叙述，错误的是( )。A、便于查找每一行或列的非零元素B、每行、每列的非零元素分别组成行链表、列链表C、C．十字链表是一种多重链表D、行链表、列链表的头结点不能共用第40题 (2.0) 分若下图表示某广义表，则它是一种( )。A、线性表ì再入表ì纯表ì递归表B、线性表ì纯表ì递归表ì再入表C、纯表ì线性表ì再入表ì递归表D、线性表ì纯表ì再入表ì递归表第41题 (1.0) 分 在数据结构中，算法的空间耗费包括代码和数据两部分。对错第42题 (1.0) 分顺序表不需存放指针，链表要存放指针，故链表的存储空间要求总是比顺序表大。对错第43题 (1.0) 分 开散列表和闭散列表的装填因子都可大于、等于或小于1对错第44题 (1.0) 分 任何树或林都可转化为二叉树，反之，二叉树可转化为任何树或林。对错第45题 (1.0) 分 在线索二叉树上，求结点的(遍历)前趋和后继时可利用线索得到，即不必进行遍历了。对错第46题 (1.0) 分 无向图中边数等于邻接矩阵中1的个数的一半；也等于邻接表中的边表结点数的一半对错第47题 (1.0) 分 直接插入排序是稳定的，而Shell排序就是调用若干趟直接插入排序，故也是稳定的。对错第48题 (1.0) 分 图G的生成树T是G的子图。对错第49题 (1.0) 分 设串的长度为n，则其子串个数为n(n+1)/2。对错第50题 (1.0) 分 广义表不仅是线性表的推广，也是树的推广。对错第51题 (1.0) 分 数组各元素在内存中连续存放，故前后相邻的两元素物理地址相差为1或-1。对错第52题 (1.0) 分 算法的时间复杂性是指在计算机上的实际运行时间。对错第53题 (1.0) 分 单链表中取第i个元素的时间与i成正比。对错第54题 (1.0) 分 在二叉排序树中，即使删除一个结点后马上再插入该结点，该二叉排序树的形态也可能不同。对错第55题 (1.0) 分 不可能有二叉树的任何遍历次序是相同的。对错第56题 (1.0) 分 不管树的深度和形态如何，也不可能构造出一棵有100个结点的哈夫曼树。对错第57题 (1.0) 分 如果n个顶点的无向图有n条边，则图中肯定有回路。对错第58题 (1.0) 分 有向图中顶点i的出度等于邻接矩阵中第i行中1的个数；入度等于第i列中1的个数。对错第59题 (1.0) 分 堆排序是一种巧妙的树型选择排序。对错
希望对你能有所帮助。

㈦ 稀疏矩阵的压缩存储思想

为了节省存储空间并且加快处理速度，需要对这类矩阵进行压缩存储，压缩存储的原则是：不重复存储相同元素；不存储零值元素。稀疏矩阵，有三元组表示法、带辅助行向量的二元组表示法（也即行逻辑链表的顺序表），十字链表表示法等。算法基本思想：num[col]:第col列的非零元素个数；cpot[col]:第col列第一个非零元在b.data中的恰当位置；在转置过程中，指示该列下一个非零元在b.data中的位置。

㈧ 对稀疏矩阵压缩存储的目的是什么 A 便于进行矩阵预算 B 便于输入和输出C节省存储空间 D降低运算世间复杂度

对稀疏矩阵压缩存储的目的是：C节省存储空间和D降低预算时间复杂度，如果是单选题，那么应该选C节省存储空间。

矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素的分布没有规律，则称该矩阵为稀疏矩阵(sparse matrix)；与之相区别的是，如果非零元素的分布存在规律（如上三角矩阵、下三角矩阵、对角矩阵），则称该矩阵为特殊矩阵。
稀疏矩阵的计算速度更快,因为M AT L A B只对非零元素进行操作,这是稀疏矩阵的一个突出的优点.假设矩阵A,B中的矩阵一样.计算2*A需要一百万次的浮点运算,而计算2*B只需要2 0 0 0次浮点运算.因为M AT L A B不能自动创建稀疏矩阵,所以要用特殊的命令来得到稀疏矩阵.
对于一个用二维数组存储的稀疏矩阵Amn,如果假设存储每个数组元素需要L个字节,那么存储整个矩阵需要m*n*L个字节.但是,这些存储空间的大部分存放的是0元素,从而造成大量的空间浪费.为了节省存储空间，可以只存储其中的非0元素.

㈨ 怎样压缩矩阵元素的存储空间

AC
稀疏矩阵(SparseMatrix):是矩阵中的一种特殊情况,其非零元素的个数远小于零元素的个数.
压缩存储:为多个值相同的元素只分配一个存储空间;对0元素不分配空间.目的是节省大量存储空间.
当使用三元组顺序表（又称有序的双下标法）压缩存储稀疏矩阵时,对矩阵中的每个非零元素用三个域分别表示其所在的行号,列号和元素值.它的特点是,非零元在表中按行序有序存储,因此便于进行依行顺序处理的矩阵运算.当矩阵中的非0元素少于1/3时即可节省存储空间.

㈩ 对稀疏矩阵进行压缩存储目的是() A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运

对稀疏矩阵进行压缩存储目的是节省存储空间。

稀疏矩阵的存储方式：

存储矩阵的一般方法是采用二维数组，其优点是可以随机地访问每一个元素，因而能够较容易地实现矩阵的各种运算。但对于稀疏矩阵而言，若用二维数组来表示，会重复存储了很多个0了，浪费空间，而且要花费时间来进行零元素的无效计算。所以必须考虑对稀疏矩阵进行压缩存储。

(10)对矩阵进行行压缩存储的目的扩展阅读：

最常用的稀疏矩阵存储格式主要有：三元组（i,j,a(i,j)）和CSR（Compressed Sparse Row）。

（1） 三元组（i,j,a(i,j)）（也叫COO（Coordinate Format））

三元组（i,j,a(i,j)）很简单，就是使用3个数组，分别存储全部非零元的行下标（row index）、列下标（column index）和值（value）

（2） CSR存储（Compressed Sparse Row，压缩稀疏的行）

CSR是比较标准的一种，也需要三类数据来表达：数值，列号，以及行偏移。数值和列号与COO一致，表示一个元素以及其列号，行偏移表示某一行的第一个元素在values里面的起始偏移位置。