数据结构 数组和广义表

1、第五章数组和广义表：习题习    题 一、选择题 1假设以行序为主序存储二维数组A1100,1100，设每个数据元素占两个存储单元，基地址为10，则LOC(A5，5)=(  )。    A. 808    B. 818    C. 1010    D. 1020 2同一数组中的元素(  )。    A. 长度可以不同    B不限

2、0;  C类型相同       D. 长度不限 3二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中(  )内的正确答案。    (1)存放A至少需要(  )个字节。    (2)A的第8列和第5行共占(  )个字节。    (3)若A按行存放，元素A8【5的起始地址与A按列存放时的元素(  )的起始地

3、址一致。    供选择的答案：    (1)A. 90     B. 180    C. 240    D. 270   E.540    (2) A. 108    B. 114    C. 54     D. 60    E.150  

4、  (3)A.A85   B. A310    c.A58    D.AO9 4.数组与一般线性表的区别主要是(  )。    A.存储方面        B.元素类型方面    C.逻辑结构方面    D.不能进行插入和删除运算 5设二维数组A1m，1n按行存储在数组B1m×n中，则二维数组元素Ai，j在一

5、维数组B中的下标为(  )。    A.  (i-l)×n+j    B. (i-l)×n+j-l    Ci×(j-l)       D. j×m+i-l 6所谓稀疏矩阵指的是(  )。A.零元素个数较多的矩阵B.零元素个数占矩阵元素中总个数一半的矩阵C.零元素个数远远多于非零元素个数且分布没有规律的矩阵D.包含有零元素的矩阵7对稀疏矩阵进行压缩存储的目的是(

6、60; )。A.便于进行矩阵运算    B.便于输入和输出C.节省存储空间        D. 降低运算的时间复杂度8稀疏矩阵一般的压缩存储方法有两种，即(  )。A.二维数组和三维数组    B.三元组和散列C.三元组和十字链表      D.散列和十字链表9有一个100×90的稀疏矩阵，非0元素有10个，设每个整型数占两字节，则用三元组表示该矩阵时，所需的字节数是(  )。A. 60

7、    B. 66   C18000    D3310. AN，N是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组TN(N+I)/2中，则对任一上三角元素aij对应Tk的下标k是(  )。A. i(i-l)/2+j    B. j(j-l)/2+iC. i(j-i)/2+1    D. j(i-l)/2+111已知广义表L=(x，y,z)，a，(u，t，w)，从L表中取出原子项t的运算是(  ) A. head(tai

8、l(tail(L)          B. tail(head(head(taiI(L) C. head(tail(head(taiI(L)    D. head(tail(head(tail(tail(L)12.广义表A=(a，b，(c，d)，(e，(f,g)，则下面式子的值为(  )。Head(TaiI(Head(TaiI(Tail(A) A(g)    B(d)C.c    D.d13广义表

9、(a，b，c，d)的表头是(  )，表尾是(  )。A.a    B.(  )    C.(a,b,c,d)    D.(b,c,d)14设广义表L=(a，b，c)，则L的长度和深度分别为(  )。  A.1和1    B.1和3    C.1和2    D.2和315.下面说法不正确的是(  )。 A. 广义表的表头总是一个广义表

10、60; B.广义表的表尾总是一个广义表 C.广义表难以用顺序存储结构     D.广义表可以是一个多层次的结构二、填空题1.数组的存储结构采用_存储方式。     2.二维数组A1020每个元素占一个存储单元，并且A0O的存储地址是200，若采用行序为主方式存储，则A612的地址是_ ，若采用列序为主方式存储，则A612的地址是_。3.三维数组a456（下标从0开始计，a有4×5×6个元素），每个元素的长度是2，则a234的地址是_。（设a000的地址是1000，数据以行为主方式存储）

11、4. n阶对称矩阵a满足aij=aji，i,j=1n，用一维数组t存储时，t的长度为_，    glist p；       glist q，h，t，s；    if (p=NULL)  q=NULL;    else       if_q= (glist)malloc( sizeof (gnode);q->tag=0;    q->val.data=p-

12、>val.data;      elsef    _；    if_      t=reverse (p->val. ptr. tp);    s=t;    while( s->val. ptr.tp! =NULL)    s=s->val .ptr.tp;    s->val .ptr. tp=( gli

13、st) malloc( sizeof (gnode);    s=s->val .ptr.tp; s->tag=l;    s->valptr.tp=NULL;    s->val.ptr.hp=h;_;        else       q=( glist) malloc( sizeof( gnode);q->tag=l;    q-

14、>val.ptr.tp=NULL;_;                return (q)；      三、判断题    1.数组不适合作为任何二叉树的存储结构。(  )    2.稀疏矩阵压缩存储后，必会失去随机存取功能。(  )    3.数组是同类型值的集合。(  )    4

15、.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。(  )        5.一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。(  )    6.广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。(  )    7.若一个广义表的表头为空表，则此广义表亦为空表。(  )    8.广义

16、表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。(  )    9.所谓取广义表的表尾就是返回广义表中最后一个元素。(  )    10.广义表的同级元素（直属于同一个表中的各元素）具有线性关系。(  )    11. 一个广义表可以为其他广义表所共享。(  )    四、简答题    1.在以行序为主序的存储结构中，给出三维数组A2*3*4的地址计算公式（下标从0开始计数）。  &#

17、160; 2.数组A中，每个元素A嘶的长度均为32个二进位，行下标从-1到9，列下标从1到11，从首地址s开始连续存放主存储器中，主存储器字长为16位。 求：    (1)存放该数组所需多少单元？    (2)存放数组第4列所有元素至少需多少单元？    (3)数组按行存放时，元素A7，4的起始地址是多少？    (4)数组按列存放时，元素A4，7的起始地址是多少？ 3将数列1，2，3，n*n，依次按下列方式存放在二维数组A1n，1一n中。例如：n=5时，二维数组为

18、   4画出下列广义表的链接存储结构，并求其深度。    (),a,(b,c),(),d),(e) 5已知题图5-1为广义表的链接存储结构，写出该图表示的广义表。       题图5-1 6设有广义表K1(K2(K5(a，K3(c，d，e)，K6(b，k)，K3，K4(K3，f)，要求：    (1)指出K1的各个元素及元素的构成。    (2)计算表K1，K2，K3，K4，Ks，K6的长度和深度。 

19、60;  (3)画出K1的链表存储结构。  五、算法设计题    1对于二维整型数组Am,n，分别编写相应函数实现如下功能：    (1)求数组A4边元素之和。    (2)当m=n时分别求两条对角线上的元素之和，否则显示mn的信息。    2编写子程序，将一维数组An*n(n<=10)中的元素按蛇形方阵存放在二维数组Bnn中，即：B00=A0；    B01=A1;B10= A2；  &#

20、160; B20=A3;B11=A4;B03=A6；    依此类推，如图题5-2所示：    3编写一个函数将两个广义表合并成一个广义表。合并是指元素的合并，如两个广义表(a，b)，(c)与(a，(e，f)合并后的结果是(a，b)，(c)，a，(e，f第五章 数组与广义表第5章数组与广义表  一、选择题  1.B   2.C     3.E, A,B    4.B    5.A 

21、60;     6.C     7.C    8.C  9.B   10.B    11.D        12.D   13.C,B    14.C    15.A  二、填空题  1顺序存储方式。      

22、;    2. 313, 327。  3. 1166。                  4.n*(n+1)/2,i*(i+l)/2。  5线性表。            6由其余元素构成的子表。  7深度。       

23、;           8()，()，2，2。  9.  head (head (tail(L).    10.  (i= =k) break,  i+l,  i-l,  i!=k。  11. p->tag=0, h=p->val.ptr.hp, p->next!=NULL, q=t, reverse(h)。  三、判断题  1× 

24、0;  2×    3   4×     5×    6×  7×    8×    9×   10.     11.   四、简答题  1. LOC(Aijk=LOC(A000+i*12+j*4+k.  2  

25、0; (1) 12l*32/16=242。    (2) 11*32/16=22    (3) LOC(A00)+(8*11+3)*32/16=LOC(A00)+182.    (4) LOC(A00)+182。  3程序如下所示：  #define NMAX 10  #include  <stdioh>  main()      int i,j，n，k，m;    int

26、a  NMAX NMAX;    scanf( "%d", &n);    m=l;    for  (i=O;  i<n;  i+)      for  (j=i*n,k=O;  j<(i+1)*n;  j+,k+)        aik=m+;    &#

27、160;   for(i=O;  i<n;  i+)    for(j=O;j<n;j+)    printf ("%4d",a ij);    printf(¨n");        4深度为4广义表的链接存储结构为：      5.(x,(y),(),(),(z)     

28、 6ki由k2, k3, k4构成            k1   k2    k3   k4    k5      k6  长度：    3    2    3    2   

29、2    2  深度：    4    3    1    2    2    l  五、算法设计题  1  (1)  #define  M  5  #define  N  7  long   sum side (int aM N)  /计算四边元素

30、之和，注意不要重复    long sum=0;  int  i;   for(i=0;  i<M;  i+)    sum+=ai0;   for(i=1;  i<N;  i+)    sum+=aOi;   for  (i=1;  i<M;  i+)    sum+=ai N-1;   for (

31、i=l;  i<N-1;  i+)    sum+=aM-1 i;   return sum;     (2)  long  sum tilt (int aMN)  /计算两条对角线元素之和    long   sum=0;  int i，j ;if  (M!=N)    printf ("nM不等于Nn”);    return&

32、#160; O;for  (i=O;  i<M;  i+)    sum+=aii;for  (i=M-1; i>=0; i-)    sum+=aiM-i-l;if  (M%2!=0)    sum-= aM/2 M/2;/M为奇数时中间元素加了两遍    return  (sum);2#define NMAX  20    /最大N值int aNMAX*NMAX

33、，bNMAX  NMAX，cnt;  /定义全局变量利于通信void MakeLine (int  RowStart, int  ColStart, int  RowEnd)  /*功能：用数组A中的元素去填充数组B的一个对角线    参数含义：RowStart-斜线起始行号           ColStart-斜线起始列号         &#

34、160; RowEnd-斜线结束行号*/    int i，j，step;    if (RowStart<=RowEnd)    /求出数组B的下标i的增量，j的增量与之相反       step=l;    else       step=-l;    for   (i=RowStart,

35、j=ColStart;  (RowEnd-i) *step>=0  ;i+-.s tep,j -=step)       bij=acnt+;    /斜线赋值，cnt用于赋值计数，初值为O    void MakeArray (int n)    /给数组B的所有斜线赋值，n为数组大小      int d：    for  (d=O;d<2*

36、n;  d+)    if(d<n)    /上三角赋值     if  (d%2=0)      MakeLine(d，O，O);     else      MakeLine(O，d，d);    else    /下三角赋值   

37、60;if  ( d%2=0)      Makeline (n-l, d-n+l, d-n+l);     else      MakeLine (d-n+l, n-l, n-l);    main()      int i,j,n;    printf ("nPlease input n:  ¨);  &

38、#160; scanf(¨%d"，&n);    for  (i=O  ;i<n*n;  i+)     ai=i+1;    cnt=0;  /赋值计数    MakeArray (n);    for(i=O;i<n;i+)    /输出结果        

39、0; printf(¨n”);      for  (j=0;  j<n;  j+)       printf(¨%5d¨,bij);             3.    int   equal(GListNode  *ha, GListNode

40、0; *hb);    /函数原型：判别由ha和hb指向的广义表元素是否相等相等返回1，否则返回o    void  GListInsertTail(GListNode  *h, GListNode  *s);    /函数原型：将s所指向的广义表元素插入到广义表h的末尾    GListNode*  GListMerge (GListNode  *ha, GListNode  *hb)  /*将广义表hb

41、合并至广义表ha中，并充分利用原有空间*/        GListNode  p,q，r;    if  (ha= =NULL)    /如果ha为空表，则hb即为合并结果        ha=hb;    return ha;        else     

42、60;  p=hb->val. sublist;    while(p!=NULL)   /循环将hb中的各个元素合并至ha中         q=ha->valsublist;     while  (q! =NULL)           if  (equal (p,q)  

43、0; /相等元素不合并      break;      q=q->link;           if  (q= =NULL)          r=p->link;      GListInsertTail (ha,p);  /若ha中无相同元

44、素，则插入到末尾      p=r;         else       p=p->link;    /请读者在此处添加释放hb结点的代码          return  ha;    int   equal (GListNode  *ha, GlistNode  *hb)  /判别由ha和hb指向的广义表元素是否相等，相等返回l，否则返回0    GListNode     *p，*q ;