精华内容
下载资源
问答
  • 数据结构-栈队列串数组和广义表习题 一选择 1 一个栈的输入序列为1 2 3 4 5则下列序列中不可能是栈的输出序列的是 B A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 2 若已知一个栈的入栈序列是1,2,3,n其...
  • - PAGE PAGE 3 欢迎下载 第五章数组和广义表习题 习? ?一选择 ?1假设以行序为主序存储二维数组A[1100,1100]设每个数据元素占两个存储单元基地址为10则LOC(A[55])=? ) ? ?A. 808? B. 818? C. 1010? D. 1020 ?2...
  • 数据结构练习(含答案):第五章数组和广义表.doc
  • 数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用...系列课程包含11个部分,本课为第5部分串,介绍数组的基本概念,特殊矩阵的压缩存储及基本运算的实现,以及广义表及其存储相关的算法。
  • 现有一n*n的稀疏矩阵,其非零元素的个数为P,假设在上述三种表示法中,每个域(值指针)都占4个字节的空间,而且头结点非头结点有相同的结构。请给出三种表示法表示该矩阵各自所需的空间数(以字节为单位)。 ...

    一 基础知识题:

    (一)关于稀疏矩阵的存储

    1.有三种存储稀疏矩阵的方法:a.十字链表法b.二维数组表示法c.三元组表示法

    现有一n*n的稀疏矩阵,其非零元素的个数为P,假设在上述三种表示法中,每个域(值和指针)都占4个字节的空间,而且头结点和非头结点有相同的结构。请给出三种表示法表示该矩阵各自所需的空间数(以字节为单位)。

    解:这道题主要考察稀疏矩阵的三种存储方法,需要对各方法有较深入的认识。

    (1)对于一个n*n矩阵,该矩阵有P个非零元素,在十字链表表示法中,零元素不分配空间,但每行每列都应有各自的头指针,所以共有头指针2n个,共占用2n*4=8n个字节。对于非零元素,需要3个数据域(i,j,e)和2个指针域(right,down)。所以共有(3+2)P个域,共需5P*4=20P个字节。于是,采用该表示法共需20P+8n个字节。

    (2)若采用二维数组表示法,则共有n^2元素,因此共需4n^2个字节。

    (3)三元组表示法,零元素同样不占用空间,每个三元组需要3个数据域。除此之外,还需要一个数据域来存放存储矩阵的行数、列数以及非零元素的个数。所以共需要(P+1)*3*4=12P+12个字节。

    2.设m*n阶稀疏矩阵A有t个非零元素,其三元组表表示为LTMA[1:(t+1),1:3],试问:非零元素的个数t达到什么程度时用LTMA表示A才有意义?

    解:如果选用二维数组表示法来表示稀疏矩阵A,则需要m*n个存储单元。三元组表表示法的优点在于不需要存储零元素,节约了存储空间。而该三元组表共有3*(t+1)个存储单元,所以只有当3*(t+1)<m*n时,用LTMA表示A才有意义。

    展开全文
  • 串的特殊性体现在数据元素是一个字符,即是内容受限的线性表,数组广义表的特殊性为线性表的数据元素自身又是一个数据结构。 对于应试,本章内容较为容易掌握,相对于其他章节所占比分较少,往往以选择或填空...

    第四章 串、数组和广义表

         本章对串、数组和广义表这几类特殊的线性表进行讨论,也可看做为线性表的扩充。串的特殊性体现在数据元素是一个字符,即是内容受限的线性表,数组与广义表的特殊性为线性表的数据元素自身又是一个数据结构。

        对于应试,本章内容较为容易掌握,相对于其他章节所占比分较少,往往以选择或填空题出现,对算法题目主要出现在对BF算法和KMP算法理解上。

    【考点】①串的重点考点为串的模式匹配算法;

                 ②数组的主要考点为数组下标与存储地址计算和特殊矩阵的压缩存储方法;

                 ③广义表的定义、性质及其GetHead和GetTail的操作。

    【本章大纲】

    【目录】

    第四章 串、数组和广义表

    一、串

    1.1  串的相关概念

    1.2  串的模式匹配算法

    1.2.1 BF算法(⭐⭐)

    1.2.2 KMP算法(难)

    二、数组

    2.1 一维数组

    2.2 二维数组

    2.3 三维数组

    2.4 矩阵的压缩存储

    2.4.1 对称矩阵

    2.4.2 三角矩阵

    2.4.3 对角矩阵(带状矩阵)

    2.4.4 稀疏矩阵

    三、广义表

    3.1 广义表的相关概念

    3.2 广义表与线性表的区别

    3.3 广义表的基本运算

    3.3.1 求表头、表尾方法

    3.3.2 例题

    3.4 广义表的特点


    一、串

    1.1  串的相关概念

           【定义】由零个或多个字符组成的有限序列, 一般记为 s= "a1 a2 … an" (n≥O)

           【串名】s就是串的名字。

           【串值】由双引号括起来的字符序列就是串的值

           【串长】串中字符的数目n即为串长

           【空串】零个字符的串,其长度为零。注意空格串与空串的区别。

           【子串】串中任意个连续的字符组成的子序列称为该串的子串。

           【主串】包含子串的串相应地称为主串。

    1.2  串的模式匹配算法

           串的模式匹配也称为子串定位运算或串匹配,其目的在于确定主串中所含子串第一次出现的位置(定位)。在串匹配中,一般将主串称为目标串,子串称之为模式串。 

           同时,模式匹配不一定是从主串的第一个位置开始, 可以指定主串中查找的起始位置 pos。该算法主要分为两种:①BF算法(又称穷尽算法或暴力算法);  ②KMP算法(拥有速度快的特点)。

    1.2.1 BF算法(⭐⭐)

    【算法思想】BF算法作为暴力算法,其特点为未比较失败,当出现不匹配时,主串返回到模式后移一位字符进行比较。具体过程如下:

          ①分别利用计数指针i 和j指示主串S和模式T中当前正待比较的字符位置,初值为pos, j初值为1。

          ②如果两个串均未比较到串尾, 即i和j均分别小于等于S和T的长度时,则循环执行以下 操作:

              ● S[i].ch和T[i].ch比较,若相等,则i和j分别指示串中下个位置,继续比较后续字符;

              ●若不等,指针后退重新开始匹配, 从主串的下一个字符 (i=i-j+2) 起再重新和模式的第一个字符 (j=1) 比较。

         ③如果j> T.length, 说明模式T中的每个字符依次和主串S中的一个连续的字符序列相等, 则匹配成功,返回和模式T中第一个字符相等的字符在主串S中的序号(i-T.length); 否则称匹配不成功,返回0。

    【算法分析】    如下例:主串为“000000000002”,子串为“002”,i=1开始比较,每趟都比较3次后发现不相等,指针都要回溯。

         因此,若n为主串长度,m为模式串长度, 最坏情况是主串前面n-m个位置都部分匹配到子串的最后一位,即这n-m位各比较了m次,最后m位也各比较了1次,总次数为:(n-m)*m+m=(n-m+1)*m,若m<<n,则算法复杂度O(n*m)。

    【算法描述】

    int  Index(Sstring S,Sstring T,int pos){
       i=pos;   j=1;          //主串从第pos位置开始
       while (i<=S.length && j <=T.length){
           if (S[i]==T[j]) { //相同时继续后移比较
              ++i;
              ++j; }
           else{            //不相等,指针回溯比较,回宿到主串的下一个字符
              i=i-j+2;
              j=1; }
    }
       if ( j>T.length)   
          return   i-T.length;  //返回字串位置
       else 
         return 0;
    }
    

    1.2.2 KMP算法(难)

    【算法思想】

         在BF算法中每次失败都是从模式后移一位再从头开始比较,这时就产生一个问题,某趟已匹配相等的字符序列是模式的某个前缀,这种重复比较相当于模式串在不断地进行自我比较,这种自我比较是非常低效的。

        KMP算法就是为解决此问题应运而生,其改进在千:每当一趟匹配过程中出现字符比较不等时,不需回溯i指针,而是利用已经得到的‘部分匹配’的结果将模式向右‘滑动’尽可能远的一段距离后,继续进行比较。即主串i指针无须回溯,并从该位置开始继续比较,而模式向后滑动位数的计算仅与模式本身的结构有关,与主串无关。

        如下图的例子中,在BF算法思想中,在第三趟的匹配中,当i=7、j=5字符比较不等时,又从i=4、j=1重新开始比较。然后,经仔细观察可发现,i=4和j=1, i=5和j=1,以及i=6和j=1这3次比较都是不必进行的。因为从第三趟部分匹配的结果就可得出,主串中第4个、第5个和第6个字符必然是“b"、 “c”和“a”(即模式串中第2个、第3个和第4个字符)。

         又因模式中的第一个字符是“a”, 因此它无需再和这3个字符进行比较,而仅需将模式向右滑动3个字符的位置继续进行i=7、j=2时的字符比较即可。

         同理,在第一趟匹配中出现字符不等时,仪需将模式向右移动两个字符的位置继续进行i=3、j=1时的字符比较。由此,在整个匹配的过程中,i指针没有回溯,如图4.5所示。

    【前缀后缀】①前缀:除去最后一个字符以外的子串

                         ②后缀:除去第一个字符以外的尾部子串

                         ③部分匹配值:前缀和后缀的最长相等前后缀长度。

          eg:在字符串S={abab}中,前缀为{a}、{ab}、{abc},后缀为{b}、{ab}、{bab},其最长相等前后缀长度为2(即部分匹配值为2)。

    【next数组】根据上面的理论,不禁让人想到在比较不相同时,主串中第 i个字符应与模式中哪个字符再比较?此时就引出了next[j]函数来指导正确的右滑位置,计算当模式串中第j个字符与主串中相应字符“失配”时,在模式中需重新和主串中该字符进行比较的字符的位置 k 的值。next数组确定方法:①通过最长前后缀值确定;

              ②将前一位元素与其next值所对应的字符进行比较

                 相等:前一位元素的next值+1,即为此字符的next值;

                 不相等:继续向前寻找与next值对应的元素进行比较,直到某一位置的next值所对应的元素与此前一位字符相同,则此字符的next值为这个位置的next+1;若前移至第一位都没有相同的,则将其next=1。<注意>初始状态下,默认next[1]=0,next[2]=1。

    (关于KMP算法不太好理解,具体计算过程例题可参考练习题中例子)

    【算法优化】

          前面定义的next 函数在某些情况下尚有缺陷;例如模式"aaaab" 在和主串"aaabaaaab"匹配 时,当i=4、j=4 时s.ch[4]≠t.ch[4],由next[j]的指示还需进行i=4、j=3, i=4、j=2,i=4、j=l这3次比较。实际上,因为模式中第1~3个字符和第4个字符都相等,因此不需要再和主串中第4个字符相比较,而可以将模式连续向右滑动4个字符的位置直接进行i=5、j=l时的字符比较。

        由上述定义可得,当next[j] = k,而pj=pk,则 主串中si和j不等时,不需再和pk进行比较,而直接和pnext[k]进行比较。因此,产生了对next数组值进行修正的nextval[ ]数组,其主要计算方法是将next值与其所对应字符进行比较:

           ①若相等,nextval[ ]值=原next对应的值

           ②若不相等,nextval[ ]值=前一个相等元素的next所对应的值,即为next[ j ]=next[.. next[ j ]..]

    【算法分析】

          设主串s的长度为n,模式串t长度为m,在KMP算法中求next数组的时间复杂度为O(m),在后面的匹配中因主串s的下标不减即不回溯,比较次数可记为n,所以KMP算法总的时间复杂度为O(n+m)。

    【算法描述】(统考不要求KMP算法代码,但是通过代码更好理解KMP算法的思想)

    /*next数组求法*/
    void get_next(SString T, int &next[])
    {
         i= 1; next[1]=0;j=0;   //初始化
         while(i<T[0]){
              if(j==0||T[i]==T[j]){
                  ++i; ++j; 
                  next[i]=j;    //若pi=pj,则next[j+1]=next[j]+1
              }
              else
                  j=next[j];   //若pi≠pj,继续循环
         }
    }                             
    
    /*KMP算法*/
    int Index_KMP (SString S,SString T, int pos) 
    {      
           i= pos,j =1;
           while (i<S[0]&&j<T[0]) {     
                 if (j==0||S[i]==T[j]){ //第一个位置匹配失败
                     i++;j++;  
                  }
                 else 
                     j=next[j];         //i不变,j后退
           }
           if (j>T[0])  return i-T[0];  //匹配成功
           else   return 0; 	         //返回不匹配标志
    } 
    
    /*nextval数组求法*/
    void get_nextval(SString T, int &nextval[])
    {
         i=1;nextval[1]=0;j=0;   
         while(i<T[0]){
              if(j==0||T[i]==T[j]){
                    ++i; ++j; 
                    if(T[i]!=T[j]) 
                       nextval[i]=j;
                    else  
                       nextval[i]=nextval[j];
              }
              else  j=nextval[j];
         }
    }                             
    

    二、数组

    2.1 一维数组

          一维数组可以看成是一个线性表,如图所示,假设数组起始地址为a(A[0]),则求第i个位置的地址为LOC(i) = LOC(i-1) = a+i*L(L指每个存储单元的大小)

    2.2 二维数组

          二维数组分为以行序优先进行存储和以列序优先进行存储,①行序优先表示:主要存储过程如下图所示

          设数组开始存放位置Loc(0,0) =a ,每个数组元素所占存储单元为L,二维数组的行下标范围为[0,n],列下标为[0,m],则求某一数组元素的开始存储位置为Loc(i, j) = a+ [ i*(m +1)+j ]*L

         ②以列序优先存储:主要存储过程如下图所示

           设数组开始存放位置Loc(0,0) =a ,每个数组元素所占存储单元为L,二维数组的行下标范围为[0,n],列下标为[0,m],则求某一数组元素的开始存储位置为Loc(I,j) = a+[ j*(n+1)+I ]*L。

    2.3 三维数组

          设数组开始存放位置Loc(0,0,0) =a ,每个维度存储元素个数为m1, m2, m3,则求某一数组元素的开始存储位置为Loc( i1, i2, i3 ) = a+i1*m2*m3+i2* m3+i3

    2.4 矩阵的压缩存储

         压缩存储的主要目的是若多个数据元素的值都相同,则只分配一个元素值的存储空间,且零元素不占存储空间,依次来减少空间的浪费。

    2.4.1 对称矩阵

      【特点】在n´n的矩阵a中,满足如下aij=aji  (1 £ i, j £ n),被称为对称矩阵。

     【存储】只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个元素空间。

    【规律】求位置aji的位置k,满足以下规律:

    2.4.2 三角矩阵

    【特点】对角线以下(或者以上)的数据元素(不包括对角线)全部为常数c。

    【存储】重复元素c共享一个元素存储空间,共占用n(n+1)/2+1个元素空间.

    【规律】①上三角矩阵(行优先存储)中求位置aji的位置k,满足以下规律:

                ②下三角矩阵(行优先存储)中求位置aji的位置k,满足以下规律:

    2.4.3 对角矩阵(带状矩阵)

     【特点】在n´n的方阵中,非零元素集中在主对角线及其两侧共L(奇数)条对角线的带状区域内 — L对角矩阵。

      【存储方式】以对角线的顺序存储。

      【规律】求位置aji的位置k,满足以下规律:k=(i1+2)*n+j1=(i-j+2)*n+j

    2.4.4 稀疏矩阵

    【特点】一般情况下,将存储非零元素的个数较少的矩阵称为稀疏矩阵。

     【存储方式】只记录每一非零元素(i,j,aij ),以此来节省空间,同时也会丧失随机存取功能。

              ①对于顺序存储常使用三元组表方式。三元组的表示方式(行标,列标,值);

              ②对于链式存储常使用十字链表(正交链表法)

    三、广义表

    3.1 广义表的相关概念

    【定义】广义表:n ( ³ 0 )个表元素组成的有限序列, 记作LS = (a0, a1, a2, …, an-1)。

    【表名】LS是表名。

    【表元素】ai是表元素,它可以是表 (称为子表),可以是数据元素(称为原子)。

    【表长】n为表的长度。

    【空表】n = 0 的广义表为空表。

    【深度】广义表中括号嵌套的最大层数。

    【注意】习惯上用大写字母表示广义表的名称,用小写字母表示原子。

    3.2 广义表与线性表的区别

              ①线性表的元素都是结构上不可分的单元素;

              ②广义表的元素可以是单元素,也可以是有结构的表;

              ③广义表不一定是线性表。

    3.3 广义表的基本运算

    3.3.1 求表头、表尾方法

          ①求表头GetHead(L):非空广义表的第一个元素,可以是一个原子,也可以是一个子表;

          ②求表尾GetTail(L):非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表。

    3.3.2 例题

          A=()---A是一个空表,其长度为0;

          B=(e)---B只有一个原子,其长度为1,表头为e,表尾为空表();

          C=(a,(b,c,d))---长度为2,表头是原子a,表尾是子表((b,c,d));

          D=(A,B,C)---其长度为3,表头是A,表尾是子表(B,C);

          E=(a,E)---递归表,长度为2,表头是原子a,表尾是子表(E)。

    3.4 广义表的特点

         ①有次序性:一个直接前驱和一个直接后继;

         ②有长度: 表中元素个数;

         ③有深度:表中括号的重数;

         ④可递归:自己可以作为自己的子表;

         ⑤可共享:可以为其他广义表所共享。

    展开全文
  • 自考02331数据结构第四章练习题 一. 单项选择题 对称矩阵的压缩存储是为了(B)。 A. 方便运算 B . 节省空间 C . 方便存储 D . 提高运算速度 在书的P91中有提到。 二维数组M的元素是4个字符(字符占一个存储...

    自考02331数据结构第四章练习题

    一. 单项选择题

    1. 对称矩阵的压缩存储是为了(B)。

      A. 方便运算

      B . 节省空间

      C . 方便存储

      D . 提高运算速度

    在书的P91中有提到。

    1. 二维数组M的元素是4个字符(字符占一个存储单元)组成的串,行下标i的范围是07,列下标j的范围是09,则存放M需要存储单元数为 (D)。

      A. 360

      B. 480

      C. 240

      D. 320

    参考书的P90,可以用公式带入,不过直接可以算出有多少数组元素,一共8行,10列,算得有80个数组元素,然后一个数组元素占4个字符,再乘4得320。所以选D。

    1. N是一个5*8的二维数组,当N按行优先方式存储时,表示该数组的第10个元素的是:(C)。

      A. N [ 2 ][2]

      B. N [ 2 ][1]

      C. N [ 1][1]

      D. N [ 1 ][2]

    参考书的P90,可以用公式带入,i*8+j=10,可得i=1,j=2。说明在第二行的第二个,也就是N[*1][1]

    1. 二维数组M[i][j]的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围是04,列下标j的范围是05,M按行存储时元素M[*3][5]的起始地址与M按列存储时起始地址相同的元素是:(B)。

      A. M[2][4]

      B. M[3][4]

      C. M[3][5]

      D. M[4][4]

    M[3][5]是第24个数组元素,可用公式得出:3*(5+1)+(5+1)=24

    如果是地址一样的话,那按列存储也应该是第24个数组元素,从上往下,从左往右数,找到后发现是M[3][4]

    1. 稀疏矩阵一般的压缩存储方法有两种,即(D)。

      A. 二维数组和三维数组

      B. 三元组和散列

      C. 顺序表和十字链表

      D. 三元组和十字链表

    参考书的P94

    1. 设矩阵A是一个对称矩阵,为了节省存储空间,将其下三角部分按行存放在一维数组SA[n*(n+1)/2]中,对任一下三角部分元素
      a i j ( i ≥ j ) a_{ij}(i≥j) aij(ij)
      在一维数组SA的下标位置k的值是(B)。

      A. j* (j-1)/2+i-1

      B. i*(i+1)/2+j

      C. j*(j+1)/2+i-1

      D. i*(i-1)/2+j

    参考书的P92

    二、填空题

    1. 将三角矩阵A*[8][8]的下三角部分逐行地存储在起始地址为1000的内存单元中,已知每个元素占4个单元,则A[6][4]地址为______1100___。

    参考书的P94
    k = { n ∗ ( n + 1 ) / 2          i < j , i ∗ ( i + 1 ) / 2 + j        i ≥ j , k=\begin{cases} \end{cases} ^{i*(i+1)/2+j\ \ \ \ \ \ i≥j,} _{n*(n+1)/2\ \ \ \ \ \ \ \ i<j,} k={n(n+1)/2        i<ji(i+1)/2+j      ij
    带入到公式中,6 *(6+1)/2+4=25。再乘以4得100,起始位置是1000,所以A[*6][4]地址为1100。

    1. 已知数组A*[10][10]表示对称矩阵,其中每个元素占5个单元,现将其下三角部分按行优先次序存储在起始位置为1000的连续的存储单元中,则A[*4][5]对应的地址为______1075_______。

    参考书的P92

    在以上的下三角矩阵中,第i行(0≤i≤m-1)恰好有i+1个元素,所以元素总数为
    ∑ i = 0 n − 1 ( i + 1 ) = n ( n + 1 ) / 2 \sum_{i=0}^{n-1}(i+1)=n(n+1)/2 i=0n1(i+1)=n(n+1)/2
    A[*4][5]恰好是下三角部分第5行最后一个,所以5 *(5+1)/2=15

    所以A[*4][5]对应的地址是:1000+15 * 5=1075

    1. 广义表((a),a)的表头是_(a)______,表尾是______a___。

    参考书的P99

    表头是:(a),表尾是:a

    1. 广义表( ( a ) )的表头是___(a),表尾是_()_。

    参考书的P99

    表头是:(a)表尾是:()

    1. 广义表(((a)))的表头是___((a)),表尾是___()_。

    参考书的P99

    表头是:((a))表尾是:()

    1. 取出广义表A=((x,y,z),(a,b,c,d))中原子b的函数是: head(tail(head(tail(A))) )

    tail(A) : (a,b,c,d)
    head(tail(A)) : a,b,c,d
    tail(head(tail(A))) : b,c,d
    head(tail(head(tail(A))) ) : b

    1. 取出广义表A=((x,(a,b,c,d) ))的原子c的函数是: head(tail(tail(head(tail(head(A)) ))) )

    head(A) : x,(a,b,c,d)
    tail(head(A)) : (a,b,c,d)
    head(tail(head(A)) ) : a,b,c,d

    tail(head(tail(head(A)) )) : b,c,d
    tail(tail(head(tail(head(A)) ))) : c,d

    head(tail(tail(head(tail(head(A)) ))) ) : c

    1. A=(x,((a,b),c,d)),函数head(head(tail(A)))的运算结果是: (a,b)

    参考书的P99

    三、 解答题

    1. 已知二维数组A_{m*n} 按“行优先顺序”存储在内存中,假设每个元素占d各存储单元,第一个元素的存储地址表示为LOC(A[0][0]),写出计算数组A的任一个元素A[*i][j]的存储地址公式。

    参考书的P90
    L O C ( A i j ) = L O C ( a 00 ) + ( i ∗ n + j ) ∗ d LOC(A_{ij})=LOC(a_{00})+(i*n+j)*d LOC(Aij)=LOC(a00)+(in+j)d

    1. 已知二维数组A*[5][10]按“行优先顺序”存储在内存中,假设每个元素占3各存储单元,第一个元素的存储地址即LOC(a[0][0])=1000,计算出LOC(A[*3][4])的值。

    根据公式:
    L O C ( A i j ) = L O C ( a 00 ) + ( i ∗ n + j ) ∗ d LOC(A_{ij})=LOC(a_{00})+(i*n+j)*d LOC(Aij)=LOC(a00)+(in+j)d
    LOC(A[3][4])=1000+(310+4) * 3=1102

    1. 已知有一个10阶对称矩阵A,采用压缩存储方式存储(以行序为主,每个元素占1个单元),其起始地址为1000,写出A*[*4][5]的地址。

    参考书的P92
    k = { j ∗ ( j + 1 ) / 2 + i        i < j , i ∗ ( i + 1 ) / 2 + j        i ≥ j ,           0 ≤ k < n ( n + 1 ) / 2 k=\begin{cases} \end{cases} ^{i*(i+1)/2+j\ \ \ \ \ \ i≥j,} _{j*(j+1)/2+i\ \ \ \ \ \ i<j,} \ \ \ \ \ \ \ \ \ 0≤k<n (n+1) / 2 k={j(j+1)/2+i      i<ji(i+1)/2+j      ij         0k<n(n+1)/2

    L O C ( a i j ) = L O C ( s a [ k ] ) = L O C ( s a [ 0 ] ) + k ∗ d LOC(a_{ij})=LOC(sa[k])=LOC(sa[0])+k*d LOC(aij)=LOC(sa[k])=LOC(sa[0])+kd

    LOC(A*[4][5])=LOC(A[0][0])+(j(j+1)/2+i) * d=1000+19*1=1019

    1. 求下列各广义表的表头和表尾

      1. ((a,b),c,d)

        参考书的P99

        表头:(a,b)

        表尾:(c,d)

      2. (a,b,c)

        参考书的P99

        表头:a

        表尾:b,c

      3. ((a,b,c))

        参考书的P99

        表头:(a,b,c)

        表尾:()

      4. (a,(b,c),d)

        参考书的P99

        表头:a

        表尾:(b,c),d

      5. ((a,b),(c,(d,())))

        参考书的P99

        表头:(a,b)

        表尾:(c,(d,()))

    2. 求下列广义表的长度和深度:

      1. ( (a) , ( (b) , c ) , ( ((d)) ) )

        参考书的P99

        长度:3

        深度:4

      2. ( a , (a,b) , d , e , ( (i,j ), k ) )

        参考书的P99

        长度:5

        深度:3

      3. (( (a,b) , (c , (d,e) ) )

        你们说,这个是不是少了一个右括号。参考答案 长度是:2 深度是:3

        这样说的话就是表头少了一个右括号,就是:((a,b))

    3. 写出下列稀疏矩阵对应的三元组表。

    [ 0 0 1 0 0 − 5 0 2 0 3 0 0 4 0 − 2 0 ] \begin{bmatrix} 0&0&1&0 \\ 0&-5&0&2\\ 0&3&0&0\\ 4&0&-2&0 \end{bmatrix} 0004053010020200

    解:

    ijv
    021
    11-5
    132
    213
    304
    32-2

    这一章看练习题的话倒是蛮简单的,不过真涉及里面的程序算法,哎,不管了。学习下一章,学完后再做试卷,抓紧!抓紧!抓紧!!!!

    展开全文
  • 第五章数组和广义表习题 一选择 1 假设以行序为主序存储二维数组 A[1 100,1 100] 设每个数据元素占两个存储单 元基地址为 10 则 LOC(A[55])=( ) A. 808 B. 818 C. 1010 D. 1020 2 同一数组中的元素 ( ) A. ...
  • 四川大学计算机学院游洪跃老师数据结构与算法分析课程的平时作业习题4-数组和广义表.rar (含编程源代码) 都是自己非常认真完成的,每一个要点都实现到位,程序全部跑通且符合要求。 最后得到的分数也很好
  • 习题数组和广义表 一单项选择 1常对数组进行的两种基本操作是 A. 建立与删除 B. 索引与修改 C. 2对于 C 语言的二维数组 DataType A[m][n], 任意元素 a[i,j] 的存储位置可由 ( ) 式确定 . 查找与修改 每个数据...
  • 第四章 串、数组和广义表练习题 本章考点较少易于掌握,对于串的重点考点为串的模式匹配算法;数组的主要考点为数组下标与存储地址计算特殊矩阵的压缩存储方法;针对广义表的考点主要为在广义表中取原子项(表)...

    第四章 串、数组和广义表练习题

        本章考点较少易于掌握,对于串的重点考点为串的模式匹配算法;数组的主要考点为数组下标与存储地址计算和特殊矩阵的压缩存储方法;针对广义表的考点主要为在广义表中取原子项(表)的操作、求表的长度和深度。同时,应注意相关概念的区分。


    一、选择题

    1. 串的长度是指( )。

            A.串中所含不同字母的个数    B.串中所含字符的个数

            C.串中所含不同字符的个数    D.串中所含非空格字符的个数

         【答案】B。串中字符的数目称为串的长度

    2. 设有数组A[i,j],数组的每个元素长度为3字节, i的值为1到 8,j的值为1到10 ,数组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A[5,8]的存储首地址为( )。

             A.BA+141   B.BA+180   C.BA+222    D.BA+225

         【答案】B 。以列序为主,则LOC[5,8]=[(8-1)*8+(5-1)]*3+BA=BA+180

    3. 设有一个10阶的对称矩阵A ,采用压缩存储方式,以行序为主存储, a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为( )

            A.13        B.32        C.33        D.40

        【答案】C. 以列序为主,则LOC[8,5]=[8*(8-1)/2+5-1]+1=33

    4. 维数组A的每个元素是由10个字符组成的串,其行下标 i=0,1, , ,8, 列下标 j=1,2, , ,10 。若A按行先存储,元素A[8,5]的起始地址与当A按列先存储时的元素( )的起始地址相同。设每个字符占一个字节。

            A.A[8,5]     B.A[3,10]    C . A[5,8]      D.A[0,9]

         【答案】B。设数组从内存首地址M开始顺序存放,若数组按行先存储,元素 A[8,5]的起始地址为:M+[(8-0) *10+( 5-1)]*1=M+84;若数组按列先存储,易计算出元素 A[3,10]的起始地址为:M+[ (10-1)*9+(3-0)]*1=M+84。

    5. 设二维数组 A[1.. m ,1.. n](即m行n列)按行存储在数组 B[1.. m*n] 中,则二维数组元素A[i,j] 在一维数组B中的下标为( )。

            A.(i-1)*n+j   B.(i-1)*n+j-1   C.i*(j-1)    D.j*m+i-1

         【答案】A。 本题可采用特殊值法。取i=j=1,易知A[1,1]的下标为1,四个选项中仅有 A 选项能确定的值为 1故选 A 。

    6. 对n阶对称矩阵压缩存储时,需要表长为( )的顺序表。

            A. n/2       B. n*n/2        C. n(n+ 1)/2   D. n(n- 1)/2

         【答案】C。对对称矩阵的存储只需要存储其上三角或下三角部分(含对角线),元素个数为n +(n-1)+ (n -2) +..*+ 1 =n(n+ 1)/2。

    7. 若将n阶下三角矩阵A按列优先顺序压缩存放在一维敏组B[1..n(n+1)/2+1]中,则存

    放到B[k]中的非零元素aij(1≤i,j≤n)的下标j与k的对应关系是( )。

           A. (- 1)(2n-j+ 1)/2+i-j         B. (j-1)(2n-j+2)/2+i-j+ 1

           C. (j- 1)(2n-j+2)2+i-j          D. (j- 1)(2n-j+ 1)/2+i-j- 1.

         【答案】B。按列优先存储,故元素aij之前有j-1列,共有n+(n-1)+..+(n-j+2)=(j-1)(2n-j+ 2)/2个元素,元素aij是第j列上第i-j+1个元素,数组B下标从1开始,k=(j-1)(2n-j+ 2)/2+i-j+1。

    8. 适用于压缩存储稀疏矩阵的两种存储结构是( ).

           A.三元组表和十字链表        B.三元组表和邻接矩阵

           C.十字链表和二叉链表        D.邻接矩阵和十宇链表

         【答案】A。三元组表的结点存储了行row、列col、值value三种信息,是主要用来存储稀疏矩阵的一种数据结构。十字链表将行单链表和列单链表结合起来存储稀疏矩阵。邻接矩阵空间复杂度达0(n2),不适合于存储稀疏矩阵。而二叉链表又名左孩子右兄弟表示法,可用于表示树或森林。

    9. 设有一个12x12的对称矩阵M,将其上三角部分的元素m/(1≤i≤j≤12)按行优先存入C语言的一维数组N中,元素m6,6在N中的下标是( )。

           A.50        B.51           C.55        D. 66

         【答案】A。在C语言中,数组N的下标从0开始。第一个元素m,对应存入no,矩阵M的第一行有12个元素,第二行有11个,第三行有10个,第四行有9个,第五行有8个,所以m6..是第12+ 11+10+9+8+1=51个元素,下标应为50。

    10. 串“ ababaaababaa ”的 next 数组为( )。

         A.012345678999          B.012121111212

         C.011234223456          D.0123012322345

       【答案】C。具体过程如下:

    11. 串“ ababaabab ”的 nextval 为( )。

           A. 010104101           B.010102101

           C. 010100011           D.010101011

         【答案】A。nextval数组的确认:首先要确定next数组,在确定next数组后按照第10题中方法确定nextval数组。其结果如图所示:

    12.广义表 A=(a,b,(c,d),(e,(f,g))) ,则 Head(Tail(Head(Tail(Tail(A))))) 的值为( )。

            A. (g)         B.(d)         C.c       D.d

       【答案】D。过程如下:

    13. 广义表 ((a,b,c,d)) 的表头是( ),表尾是( )。

            A.a     B.( )     C.(a,b,c,d)     D.(b,c,d)

         【答案】C、B。表头为非空广义表的第一个元素,可以是一个单原子,也可以是一个子表,((a,b,c,d)) 的表头为一个子表(a,b,c,d);表尾为除去表头之外,由其余元素构成的表,表为一定是个广义表,((a,b,c,d))的表尾为空表 ( ) 。

    14. 设广义表 L=((a,b,c)) ,则 L 的长度和深度分别为( )。

            A.1和1   B.1和3    C.1和2   D.2和3

         【答案】C 。广义表的深度是指广义表中展开后所含括号的层数,广义表的长度是指广义表中所含元素的个数。根据定义易知L的长度为1,深度为2。

    二、填空题

    1. 将整型数组 A[1..8,1..8]按行优先次序存储在起始地址为 1000 的连续的内存单元 中,则元素 A[7,3]的地址是:______。

         【答案】1100。注意,整形一般情况下占用两个字节大小,计算过程为1000+[(7-1)*8+(3-1)]*2=1100

    2. 三维数组 a[4][5][6](下标从 0 开始计,a 有 4*5*6 个元素),每个元素的长度是 2,则 a[2][3][4]的地址是_____。(设 a[0][0][0]的地址是 1000,数据以行为主方式存储)

         【答案】1164。具体计算如下:[(2-0)*5*6+(3-0)*6+(4-0)]*2+1000=1164。

    3. 设二维数组 A[-20..30,-30..20], 每个元素占有 4 个存储单元, 存储起始地址为 200. 如按行优先顺序存储,则元素 A[25,18]的存储地址为____;如按列优先顺序存储,则元素 A[-18,-25]的存储地址为______。

         【答案】①9572;②1228。

                        具体计算如下:①[(20+25)*51+(18+30)*4]+200=9572;

                                                ②[(-25+30)*51+(-18+20)*4]+200=1228;

    4. 己知三对角矩阵A[1..9,1..9]的每个元素占2个单元,现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中,则元素A[7,8]的地址为___。

         【答案】1038。具体计算过程如下:[(i-1)*3+(j-i)]+1000=1038。

    5. 数组 A[1..8,-2..6,0..6]以行为主序存储,设第一个元素的首地址是 78,每个元 素的长度为 4,试求元素 A[4,2,3]的存储首地址。

         【答案】958。具体计算过程如下:78+4*(3*9*7+4*7+3)=958。

    6. 给出字符串‘abacabaaad’在 KMP 算法中的 next 和 nextval 数组

         【答案】 ①0112123422;②01020101422

    7.令 t=‘abcabaa’,求其 next 函数值和 nextval 函数值。

         【答案】①0111232;②0110132

    展开全文
  • 第五章 数组和广义表 计算 知识点 明确数组数据结构的特点,掌握数组地址计算方法,了解几种特殊矩阵的压缩存储方法。 数组 数组数据结构特点 数组既可以是顺序的,也可以是链式结构,用户可根据需要选择。...
  • 数据结构串、数组和广义表

    千次阅读 2020-11-08 23:16:28
    文章目录四、串、数组和广义表4.1、串的定义4.2、案例引入4.3、串的类型定义、存储结构及其运算4.3.1、串的抽象类型定义4.3.2、串的存储结构4.3.3、串的模式匹配算法4.4、数组4.5、广义表第四章小结第四章习题 ...
  • 数据结构与算法-Chapter5-数组广义表-练习题
  • 数组和广义表习题

    千次阅读 2019-12-05 20:29:59
    设有数组 A[i,j],数组的每个元素长度为 3 字节,i 的值为 1 到 8 ,j 的值为 1 到 10,数组从内存首地址 BA 开始顺序存放,当用以列为主存放时,元素 A[5,8] 的存储首地址为? 答案: BA + 180。画出矩阵图,先算...
  • 练习3 # include using namespace std ; const int MAXSIZE = 2000 ; typedef long long ll ; struct Triple { ll i , j ; int e ; } ; struct RLSMatrix { Triple ...
  • 第4章 串、数组和广义表 下标从1开始 一、填空 1. 零个字符的串 称为空串; 由一个或多个空格组成的串 称为空白串。 2. 设S=“A;/document/Mary.doc”,则strlen(s)= 20 , “/”的字符定位的位置为 3 。 3. ...
  • 欢迎下载 欢迎下载 PAGE # 第五章数组和广义表习题 习题 一选择 1假设以行序为主序存储二维数组 A[1 100,1 100] 设每个数据元素占两个存储单 元基地址为 10则 LOC(A[5 5])=( ) 808 B. 818 C. 1010 D. 1020 2同一...
  • 数据结构》第4章 串、数组和广义表第4章 串、数组和广义表 第4章 串、数组和广义表 第一块:引入 什么叫数据结构?为什么这是一门问题驱动型学科? 第二块:问题 逻辑结构+存储结构+操作 第三块:应用 到底...
  • 数据结构习题之多维数组和广义表

    千次阅读 2015-07-01 15:45:33
    第五章 多维数组和广义表 一、基本要求、重点、难点  本章目的是介绍多维数组的逻辑结构特征及其存储方式,特殊矩阵稀疏矩阵的压缩存储方法。本章重点是熟悉多维数组的存储方式、矩阵的压缩存储方式,难点是...
  • 目录一、串二、KMP算法三、矩阵四、广义表五、作业习题 本系列博客为《数据结构》(C语言版)的学习笔记(上课笔记),仅用于学习交流自我复习 数据结构合集链接: 《数据结构》C语言版(严蔚敏版) 全书知识...
  • 最近在复习数据结构,所以想把平时上课做的习题做个总结,如果大家有遇到这方面的问题就可以参考一下了,废话不多说,直接开始吧。 1、单选 稀疏矩阵一般的压缩存储方法有两种,即( D) A. 二维数组和三维数组 B....
  • 5.1 数组的基本概念 5.2 稀疏矩阵的三元组存储 5.3 稀疏矩阵的十字链表存储 5.4 广义表 5.5 迷宫问题 习题
  • 数据结构 第五章 数组广义表作业

    千次阅读 2019-08-05 19:57:06
    数组广义表作业(50分) 答案链接链接 一、选择(每 2 分,共 20 分)。 1.两个串相等的充要条件是( )。 A.串长度相等 B.串长度任意 C.串中各位置字符任意 D.串中各位置字符均对应相等 2...
  • 摘选了部分客观。嘿咻,加油! 1.稀疏矩阵一般的压缩存储方法有两种,即( C ) A.二维数组和三维数组 B.三元组散列 C.三元组十字链 D.散列十字链 基础知识,记忆一下。 2.数组与一般线性表的区别主要是...
  • #include<bits/stdc++.h> using namespace std; int main() { int a[21][21]={0}; int n,m,x,y,z; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&...i&l...
  • 第4章 数组和广义表 【例4-1】二维数组A的每一个元素是由6个字符组成的串,其行下标i=0,1,…,8,列下标j=1,2,…,10。若A以行为主序存储元素,A[8][5]的物理地址与当A按列为主序存储时的元素( )的物理地址...
  • 第 4 章 数组和广义表 一、选择 1. 将一个A[1..100,1..100]的三对角矩阵,按行优先存入一维数组B[1‥298]中,A中元素A6665(即该元素下标i=66,j=65),在B数组中的位置K为( B )。供选择的答案: A. 198...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,281
精华内容 512
关键字:

数据结构数组和广义表习题

数据结构 订阅