2. 计算机
  3. 阅读以下说明和C函数，将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 若一个矩阵中的非零元素数目很少且分布没有规律，则称之为稀疏矩阵。对于m行 n列的稀疏矩阵M，进行转置运算后得到n行m列的矩阵MT，如图2-3所示。 为了压缩稀疏矩阵的

阅读以下说明和C函数，将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 若一个矩阵中的非零元素数目很少且分布没有规律，则称之为稀疏矩阵。对于m行 n列的稀疏矩阵M，进行转置运算后得到n行m列的矩阵MT，如图2-3所示。 为了压缩稀疏矩阵的

admin2008-05-15  149
问题 阅读以下说明和C函数，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
   若一个矩阵中的非零元素数目很少且分布没有规律，则称之为稀疏矩阵。对于m行 n列的稀疏矩阵M，进行转置运算后得到n行m列的矩阵MT，如图2-3所示。
   为了压缩稀疏矩阵的存储空间，用三元组(即元素所在的行号、列号和元素值)表示稀疏矩阵中的一个非零元素，再用一维数组逐行存储稀疏矩阵中的所有非零元素(也
称为三元组顺序表)。例如，图2-3所示的矩阵M相应的三元组顺序表如表2-1所示，其转置矩阵MT的三元组顺序表如表2-2所示。
   
    表2-1
   
   表2-1
   
函数TransposeMatrix(Matrix M)的功能是对用三元组顺序表表示的稀疏矩阵M进行转置运算。
   对M实施转置运算时，为了将M中的每个非零元素直接存入其转置矩阵MT三元组顺序表的相应位置，需先计算M中每一列非零元素的数目(即MT中每一行非零元素的数目)，并记录在向量num中；然后根据以卞关系，计算出矩阵M中每列的第一个非零元素在转置矩阵MT三元组顺序表中的位置。
   cpot[0]=0
   cpot[j]=cpot[j-1)+num[j-1]/*j为列号*/

   类型ElemType、Triple和Matnx定义如下：

   typedef int ElemType；
   typedef struct{    /*三元组类型*/
         int r，c；    /*矩阵元素的行号、列号*/
         ElemType e；    /*矩阵元素的值*/
   }Triple；
   typedef struct{    /*矩阵的三元组顺序表存储结构*/
         int rows，cols，elements；/*矩阵的行数、列数和非零元素数目*/
                 Triple data [MAXSIZE];
       }Matrix;
【C函数】
      int TransposeMatrix (Matrix M)
    {
           int j,q,t;
           int *num,  *spot;
          Matrix MT;            /* MT是M的转置矩阵*/
           num= (int *)malloc(M.cols*sizeof(int));
           cpot= (int *)malloc(M.cols*sizeof(int));
           if (!num ||  !cpot)
               return ERROR;
          MT.rows =(1);     /* 设置转置矩阵MT行数、列数和非零元数目*/
          MT.cols =(2);
          MT. elements = M. elements;
          if (M.elements ＞ 0)  {
               for(q = 0; q ＜ M.cols; q++)
                    num[q] = 0;
               for(t = 0; t < M.elements; ++t)    /*计算机阵M中每一列非零元素数目 */
                   num.[M.data [t] . c] ++;
           /*计算矩阵M中第列第一个非零元素在其转置矩阵三元组顺序表中的位置*/
         (3);
               for(j = 1;j ＜ M.cols; j++)
                     spot [j] =(4);
     for(t = 0; t < M.elements;t++){
                     j =(5);        /* 取矩阵M的一个非零元素的列号存入j*/
                   q = cpot[j];
                   MT.data[q].r = M.data[t].c;
                   MT.data[q].c = M.data[t].r;
                   MT.data[q].e = M.data[t] .e;
                   ++cpot[j];          /* 计算M中第j列的下一个非零元素的目的位置*/
     }/* for */
     }/* if */
    free(num)；free(cpot)；
   /*此处输出矩阵元素，代码省略*/
   return OK；
   )/*TransposeMatrix*/
选项
答案(1)M.cols (2)M.rows (3)cpot[0]=0，或其等价形式 (4)cpot[j-1]+num[j-1]，或其等价形式 (5)M.data[t].c，或其等价形式
解析 本题考查稀疏矩阵的压缩存储及转置运算在压缩存储结构上的实现。虽然从题干部分的描述来看，有一定的难度，但代码中要求完善的部分却很简单，因此，题目要求的是以对应于算法描述的方式机械地实现程序。
   转置矩阵的行数、列数分别等于原矩阵的列数、行数，转置矩阵第i行第j列的元素就是原矩阵第j行第i列的元素。
   若采用二维数组存储矩阵元素，则矩阵的转置运算是及其简单的。例如，已知有m行n列的矩阵M矩阵，求其转置矩阵MT，则常见的代码形式如下：
   for(i=0；  i＜m；  i++  )
   for(j=0；j＜n；j++)
   MT[j，i)  ；M[i，j]；
   当采用三元组表顺序存储稀疏矩阵中的非零元素时，简单交换每个元素的行号和列号即可实现转置运算，但是转置后元素的存储顺序发生了变化，原矩阵的非零元素按行存储，转置以后则按列存储，如下表所示。

  因此，还需要对转置矩阵MT的三元组表按行号进行排序。
   本题目中给出的方法是：在进行转置运算时就安排好每个元素在其转置矩阵中按行存储时的位置，这样就需要一些辅助运算，即先计算M中每一列非零元素的数目(即 MT中每一行非零元素的数目)，并记录在向量num中，然后计算元素在转置矩阵中三元组表的位置。
   在程序中以下代码计算矩阵M每列的元素数目：
   for(q=0；  q＜M．cols；q++)  /*初始化向量num*/
   num[q]=0；
   for(t=0；t＜N．elements；++t)/*计算矩阵M中每一列非零元素数目*/
   num[M.data[t]．c]++；    /*M.data[t).c为M中第t个非零元素的列号*/
   以题中所给的矩阵为例，经计算后，向量num[]={1,2,0,1,2)，即第0列有一个非零元素，第1列有两个非零元素，第2列没有非零元素，依此类推。
   计算出向量num[]后，根据以下关系，可计算出矩阵M中每列的第一个非零元素在转置矩阵MT三元组顺序表中的位置。
   cpot[0]=0   /*设置M的第0列的第一个非零元素在MT三元组表中的位置*/
   cpot[j]=cpot[j-1]+  num[j-1l    /*j为列号*/
   第j-1列第一个非零元素的位置加上本列非零元素的个数即是第j列的第一个非零元素在MT三元组表中的位置。
转载请注明原文地址:https://kaotiyun.com/show/WsjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

相关试题推荐
随机试题
最新回复(0)