1、第五章數(shù)組和廣義表：習(xí)題習(xí)    題 一、選擇題 1假設(shè)以行序為主序存儲二維數(shù)組A1100,1100，設(shè)每個數(shù)據(jù)元素占兩個存儲單元，基地址為10，則LOC(A5，5)=(  )。    A. 808    B. 818    C. 1010    D. 1020 2同一數(shù)組中的元素(  )。    A. 長度可以不同    B不限

2、0;  C類型相同       D. 長度不限 3二維數(shù)組A的元素都是6個字符組成的串，行下標i的范圍從0到8，列下標j的范圈從1到10。從供選擇的答案中選出應(yīng)填入下列關(guān)于數(shù)組存儲敘述中(  )內(nèi)的正確答案。    (1)存放A至少需要(  )個字節(jié)。    (2)A的第8列和第5行共占(  )個字節(jié)。    (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.數(shù)組與一般線性表的區(qū)別主要是(  )。    A.存儲方面        B.元素類型方面    C.邏輯結(jié)構(gòu)方面    D.不能進行插入和刪除運算 5設(shè)二維數(shù)組A1m，1n按行存儲在數(shù)組B1m×n中，則二維數(shù)組元素Ai，j在一

5、維數(shù)組B中的下標為(  )。    A.  (i-l)×n+j    B. (i-l)×n+j-l    Ci×(j-l)       D. j×m+i-l 6所謂稀疏矩陣指的是(  )。A.零元素個數(shù)較多的矩陣B.零元素個數(shù)占矩陣元素中總個數(shù)一半的矩陣C.零元素個數(shù)遠遠多于非零元素個數(shù)且分布沒有規(guī)律的矩陣D.包含有零元素的矩陣7對稀疏矩陣進行壓縮存儲的目的是(

6、60; )。A.便于進行矩陣運算    B.便于輸入和輸出C.節(jié)省存儲空間        D. 降低運算的時間復(fù)雜度8稀疏矩陣一般的壓縮存儲方法有兩種，即(  )。A.二維數(shù)組和三維數(shù)組    B.三元組和散列C.三元組和十字鏈表      D.散列和十字鏈表9有一個100×90的稀疏矩陣，非0元素有10個，設(shè)每個整型數(shù)占兩字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是(  )。A. 60

7、    B. 66   C18000    D3310. AN，N是對稱矩陣，將下面三角（包括對角線）以行序存儲到一維數(shù)組TN(N+I)/2中，則對任一上三角元素aij對應(yīng)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設(shè)廣義表L=(a，b，c)，則L的長度和深度分別為(  )。  A.1和1    B.1和3    C.1和2    D.2和315.下面說法不正確的是(  )。 A. 廣義表的表頭總是一個廣義表

10、60; B.廣義表的表尾總是一個廣義表 C.廣義表難以用順序存儲結(jié)構(gòu)     D.廣義表可以是一個多層次的結(jié)構(gòu)二、填空題1.數(shù)組的存儲結(jié)構(gòu)采用_存儲方式。     2.二維數(shù)組A1020每個元素占一個存儲單元，并且A0O的存儲地址是200，若采用行序為主方式存儲，則A612的地址是_ ，若采用列序為主方式存儲，則A612的地址是_。3.三維數(shù)組a456（下標從0開始計，a有4×5×6個元素），每個元素的長度是2，則a234的地址是_。（設(shè)a000的地址是1000，數(shù)據(jù)以行為主方式存儲）

11、4. n階對稱矩陣a滿足aij=aji，i,j=1n，用一維數(shù)組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.數(shù)組不適合作為任何二叉樹的存儲結(jié)構(gòu)。(  )    2.稀疏矩陣壓縮存儲后，必會失去隨機存取功能。(  )    3.數(shù)組是同類型值的集合。(  )    4

15、.數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對它進行插入，刪除等操作。(  )        5.一個稀疏矩陣Am*n采用三元組形式表示，若把三元組中有關(guān)行下標與列下標的值互換，并把m和n的值互換，則就完成了Am*n的轉(zhuǎn)置運算。(  )    6.廣義表的取表尾運算，其結(jié)果通常是個表，但有時也可是個單元素值。(  )    7.若一個廣義表的表頭為空表，則此廣義表亦為空表。(  )    8.廣義

16、表中的元素或者是一個不可分割的原子，或者是一個非空的廣義表。(  )    9.所謂取廣義表的表尾就是返回廣義表中最后一個元素。(  )    10.廣義表的同級元素（直屬于同一個表中的各元素）具有線性關(guān)系。(  )    11. 一個廣義表可以為其他廣義表所共享。(  )    四、簡答題    1.在以行序為主序的存儲結(jié)構(gòu)中，給出三維數(shù)組A2*3*4的地址計算公式（下標從0開始計數(shù)）。  &#

17、160; 2.數(shù)組A中，每個元素A嘶的長度均為32個二進位，行下標從-1到9，列下標從1到11，從首地址s開始連續(xù)存放主存儲器中，主存儲器字長為16位。 求：    (1)存放該數(shù)組所需多少單元？    (2)存放數(shù)組第4列所有元素至少需多少單元？    (3)數(shù)組按行存放時，元素A7，4的起始地址是多少？    (4)數(shù)組按列存放時，元素A4，7的起始地址是多少？ 3將數(shù)列1，2，3，n*n，依次按下列方式存放在二維數(shù)組A1n，1一n中。例如：n=5時，二維數(shù)組為

18、   4畫出下列廣義表的鏈接存儲結(jié)構(gòu)，并求其深度。    (),a,(b,c),(),d),(e) 5已知題圖5-1為廣義表的鏈接存儲結(jié)構(gòu)，寫出該圖表示的廣義表。       題圖5-1 6設(shè)有廣義表K1(K2(K5(a，K3(c，d，e)，K6(b，k)，K3，K4(K3，f)，要求：    (1)指出K1的各個元素及元素的構(gòu)成。    (2)計算表K1，K2，K3，K4，Ks，K6的長度和深度。 

19、60;  (3)畫出K1的鏈表存儲結(jié)構(gòu)。  五、算法設(shè)計題    1對于二維整型數(shù)組Am,n，分別編寫相應(yīng)函數(shù)實現(xiàn)如下功能：    (1)求數(shù)組A4邊元素之和。    (2)當m=n時分別求兩條對角線上的元素之和，否則顯示mn的信息。    2編寫子程序，將一維數(shù)組An*n(n<=10)中的元素按蛇形方陣存放在二維數(shù)組Bnn中，即：B00=A0；    B01=A1;B10= A2；  &#

20、160; B20=A3;B11=A4;B03=A6；    依此類推，如圖題5-2所示：    3編寫一個函數(shù)將兩個廣義表合并成一個廣義表。合并是指元素的合并，如兩個廣義表(a，b)，(c)與(a，(e，f)合并后的結(jié)果是(a，b)，(c)，a，(e，f第五章 數(shù)組與廣義表第5章數(shù)組與廣義表  一、選擇題  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由其余元素構(gòu)成的子表。  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廣義表的鏈接存儲結(jié)構(gòu)為：      5.(x,(y),(),(),(z)     

28、 6ki由k2, k3, k4構(gòu)成            k1   k2    k3   k4    k5      k6  長度：    3    2    3    2   

29、2    2  深度：    4    3    1    2    2    l  五、算法設(shè)計題  1  (1)  #define  M  5  #define  N  7  long   sum side (int aM N)  /計算四邊元素

30、之和，注意不要重復(fù)    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為奇數(shù)時中間元素加了兩遍    return  (sum);2#define NMAX  20    /最大N值int aNMAX*NMAX

33、，bNMAX  NMAX，cnt;  /定義全局變量利于通信void MakeLine (int  RowStart, int  ColStart, int  RowEnd)  /*功能：用數(shù)組A中的元素去填充數(shù)組B的一個對角線    參數(shù)含義：RowStart-斜線起始行號           ColStart-斜線起始列號         &#

34、160; RowEnd-斜線結(jié)束行號*/    int i，j，step;    if (RowStart<=RowEnd)    /求出數(shù)組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用于賦值計數(shù)，初值為O    void MakeArray (int n)    /給數(shù)組B的所有斜線賦值，n為數(shù)組大小      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;  /賦值計數(shù)    MakeArray (n);    for(i=O;i<n;i+)    /輸出結(jié)果        

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

40、0; *hb);    /函數(shù)原型：判別由ha和hb指向的廣義表元素是否相等相等返回1，否則返回o    void  GListInsertTail(GListNode  *h, GListNode  *s);    /函數(shù)原型：將s所指向的廣義表元素插入到廣義表h的末尾    GListNode*  GListMerge (GListNode  *ha, GListNode  *hb)  /*將廣義表hb

41、合并至廣義表ha中，并充分利用原有空間*/        GListNode  p,q，r;    if  (ha= =NULL)    /如果ha為空表，則hb即為合并結(jié)果        ha=hb;    return ha;        else     

42、60;  p=hb->val. sublist;    while(p!=NULL)   /循環(huán)將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結(jié)點的代碼          return  ha;    int   equal (GListNode  *ha, GlistNode  *hb)  /判別由ha和hb指向的廣義表元素是否相等，相等返回l，否則返回0    GListNode     *p，*q ;