习题五  数组和广义表
一、单项选择题
1．常对数组进行的两种基本操作是（    ）
A.建立与删除  B. 索引与修改        C. 查与修改        D. 查与索引
2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由(  )式确定.
[i,j]=A[m,n]+[(n+1)*i+j]*k
[i,j]=loc[0,0]+[(m+n)*i+j]*k
[i,j]=loc[0,0]+[(n+1)*i+j]*k
[i,j]=[(n+1)*i+j]*k
3．稀疏矩阵的压缩存储方法是只存储                                      (  )
A.非零元素          B. 三元祖（i,j, aij）      C. aij          D. i,j
4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是(    )。
A. 1175          B. 1180          C. 1205          D. 1210
5. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（    ）。
A. i（i-1）/2+j    B. j（j-1）/2+i    C. i（j-i）/2+1    D. j（i-1）/2+1
6. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为(    )。
    A. j=r[j].next    B. j=j+1          C. j=j->next    D. j=r[j]-> next
7. 对稀疏矩阵进行压缩存储目的是（    ）。
A．便于进行矩阵运算             B．便于输入和输出 
C．节省存储空间                   D．降低运算的时间复杂度
8. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是(    )。
    A. head(tail(LS))                    B. tail(head(LS))
C. head(tail(head(tail(LS)))          D. head(tail(tail(head(LS))))
9. 广义表（（a,b,c,d））的表头是（    ），表尾是（    ）。
数组和链表A. a            B.（）            C.（a,b,c,d）    D.（b,c,d）
10. 设广义表L=（（a,b,c）），则L的长度和深度分别为（    ）。
    A. 1和1        B. 1和3            C. 1和2        D. 2和3
11. 下面说法不正确的是(    )。
A. 广义表的表头总是一个广义表        B. 广义表的表尾总是一个广义表
C. 广义表难以用顺序存储结构          D. 广义表可以是一个多层次的结构
二、填空题
1．通常采用___________存储结构来存放数组 。对二维数组可有两种存储方法：一种是以___________为主序的存储方式，另一种是以___________为主序的存储方式。
2. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A 中的第_            _行，第_          _列的元素。
3．设n行n列的下三角矩阵A已压缩到一维数组*（n+1）/2]中，若按行为主序存储，则A[i,j]对应的B中存储位置为_______。
4. 所谓稀疏矩阵指的是_                                  。
5. 广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于____            。为了区分原子和表，一般用          ____表示表，用    _____表示原子。一个表的长度是指        __，而表的深度是指__        __
6．设广义表L=((),()), 则head(L)是                    ；tail(L)是          ；L的长度是                  ；深度是        __。
7．基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置，请在___________处用适当的句子用以填充。
Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b)
  {  (*b).mu=;(*b).nu=;(*b).tu=;
      if
        {  q=1;
            for(col=1; ___________;col++)
              for(p=1;p<=;p++)
                  if(___________==col)
                    {(*b).data[q].i=[p].j;
                      (*b).data[q].j=[p].i;
                      (*b).data[q].v=[p].v;
                      ___________;
          }
  }
8. 完善下列程序。下面是一个将广义表逆置的过程。例如原来广义表为（（a,b）,c,（d,e）），经逆置后为：（（e,d）,c,（b,a））。
typedef  struct  glistnode 
{int  tag;
struct  glistnode *next;
union{char data;
      struct{struct glistnode *hp,*tp;}ptr;
      }val;
}*glist,gnode;
glist  reverse(p)
glist p;
{glist  q,h,t,s;
if(p==NULL)  q=NULL;
else
{if(1)            { q=(glist)malloc(sizeof(gnode));  q->tag=0; 
            q->=p->;  }
  else {(2)              
        if (3)                
{t=reverse(p-> s=t;
            while(s->  s=s->            s->            s-> (4)              __ }
else {q=(glist)malloc(sizeof(gnode));q->tag=1;
                q-> (5)                  ; }
}
}
return(q);
}
三、应用题
1. 数组A[1..8，-2..6，0..6]以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A[4,2,3]的存储首地址。
2. 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能为什么
3. 数组，广义表与线性表之间有什么样的关系
4. 设有三对角矩阵(aij)n*n，将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]=aij，求：
（1）用i,j表示k的下标变换公式；
（2）用k表示i,j的下标变化公式。
5．画出下面广义表的两种存储结构图示：
  ((((a), b)), ((( ), d), (e, f)))
6．求下列广义表运算的结果：
（1）      HEAD[((a,b),(c,d))];         
（2）      TAIL[((a,b),(c,d))];             
（3）      TAIL[HEAD[((a,b),(c,d))]];       
（4）      HEAD[TAIL[HEAD[((a,b),(c,d))]]];
（5）      TAIL[HEAD[TAIL[((a,b),(c,d))]]]; 
7. 利用广义表的Head和Ｔail运算，把原子d分别从下列广义表中分离出来，L1＝(((((a),b),d),e))；L2＝（a,(b,((d)),e)）。
四、算法设计题
1. 给定nxm矩阵A[a..b,c..d],并设A[i,j]≤A[i,j+1](a≤i≤b,c≤j≤d-1)和A[i,j]≤A[i+1,j](a≤i≤b-1,c≤j≤d).设计一算法判定X的值是否在A中,要求时间复杂度为O(m+n)。
2. 设二维数组, 1..n] 含有m*n 个整数。
(1) 写出算法：判断a中所有元素是否互不相同输出相关信息(yes/no)；
(2) 试分析算法的时间复杂度。
3. 设A[1..100]是一个记录构成的数组，B[1..100]是一个整数数组，其值介于1至100之间，现要求按B[1..100]的内容调整A中记录的次序，比如当B[1]=ll时，则要求将A[1]的内容调整到A[11]中去。规定可使用的附加空间为O(1)。
4．稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示。
5. 试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义表按如下形式输入（a1,a2,a3,…,an） n>=0，其中ai或为单字母表示的原子或为广义表，n=0时为只含空格字符的空表。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。