對矩陣進行行壓縮存儲的目的

㈠ 什麼是壓縮矩陣

在這里分開來給你解釋
矩陣是許多科學計算、工程數學尤其是數值分析中經常研究的對象，矩陣也就是二維數組,所以它可以採用順
序存儲是來存儲其中的元素。但有時矩陣的階數很高，同時在矩陣中游很多值相同的元素，或大多數元素的值為
零，這時再採用嚴格的順序存儲顯然是很浪費空間的，因為存儲零元素或許多值相同的元素是沒有意義的，因此為
了節省存儲空間，對這類矩陣通常採用壓縮存儲。
壓縮存儲：為多個值相同的元素值分配一個存儲空間，對零元素不分配存儲空間。
特殊矩陣：各個元素的分布有一定規律
系數矩陣：矩陣中多數元素值為零。

㈡ 矩陣的壓縮存儲是什麼

二維數組在形式上是矩陣，因此一般用二維數組來存儲矩陣。在不壓縮存儲的情況下，矩陣採用按行優先或按列優先方式存儲，佔用的存儲單元數等於矩陣的元素個數。在實際應用中，經常出現一些階數很高的矩陣，同時在矩陣中非零元素呈某種規律分布或者矩陣中有大量的零元素，若仍然用常規方法存儲，可能存儲重復的非零元素或零元素，這將造成存儲空間的大量浪費。因此對這類矩陣進行壓縮存儲，從而合理地利用存儲空間。

為了節省存儲空間，可以利用特殊矩陣的規律，對它們進行壓縮存儲，也就是說為多個值相同的元素只分配一個存儲單元，對零元素不分配空間。適合壓縮存儲的矩陣一般是值相同的元素或者零元素在矩陣中分布有一定規律的特殊矩陣和稀疏矩陣。常見的特殊矩陣有對稱矩陣、三角矩陣和對角矩陣。

㈢ 對稀疏矩陣進行壓縮的目的

我給你源碼記得頂我啊！！最主要的是把分給我哦！！
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裡面的起始偏移位置。