???????????????????? ?第 4? 章? 數組和廣義表

一、選擇題

1. 將一個A[1..100，1..100]的三對角矩陣，按行優先存入一維數組B[1‥298]中，A中元素A6665（即該元素下標i=66，j=65），在B數組中的位置K為（ B?? ）。供選擇的答案：

A. 198??????????? B. 195?????????????? C. 197??

2. 二維數組A的元素都是6個字符組成的串，行下標i的范圍從0到8，列下標j的范圈從1到10。從供選擇的答案中選出應填入下列關于數組存儲敘述中（??? ）內的正確答案。

（1）存放A至少需要（??E ）個字節；

（2）A的第8列和第5行共占（? A? ）個字節；

（3）若A按行存放，元素A[8，5]的起始地址與A按列存放時的元素（ B?? ）的起始地址一致。

供選擇的答案：

（1）A. 90?????? B. 180??????? C. 240?????? D. 270?????? E. 540????

（2）A. 108????? B. 114??????? C. 54??????? D. 60??????? E. 150????

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

3. 設A是n*n的對稱矩陣，將A的對角線及對角線上方的元素以列為主的次序存放在一維數組B[1..n(n+1)/2]中，對上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置為( B )。

A. i(i-l)/2+j???? B. j(j-l)/2+i?????? C. j(j-l)/2+i-1??? D. i(i-l)/2+j-1

4. A[N，N]是對稱矩陣，將下面三角（包括對角線）以行序存儲到一維數組T[N（N+1）/2]中，則對任一上三角元素a[i][j]對應T[k]的下標k是（B ）。

A. i（i-1）/2+j??? B. j（j-1）/2+i???? C. i（j-i）/2+1????D. j（i-1）/2+1

5. 設二維數組A[1.. m，1..n]（即m行n列）按行存儲在數組B[1.. m*n]中，則二維數組元素A[i，j]在一維數組B中的下標為( A? )。

A.（i-1）*n+j???? B.（i-1）*n+j-1????? C. i*（j-1）? ??????D. j*m+i-1

6. 有一個100*90的稀疏矩陣，非0元素有10個，設每個整型數占2字節，則用三元組表示該矩陣時，所需的字節數是（B?? ）。

A. 60???????????? B. 66??????????????? C. 18000???????????? D. 33???

7. 數組A[0..4,-1..-3,5..7]中含有元素的個數（ B?? ）。

A. 55??????????? B. 45?????????????? C. 36??????????? D. 16?? ?????????????

8.? 廣義表A=(a,b,(c,d),(e,(f,g))),則下面式子的值為（ D? ）。

Head(Tail(Head(Tail(Tail(A)))))

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

9. 已知廣義表: A=(a,b), B=(A,A), C=(a,(b,A),B),求下列運算的結果:

?tail(head(tail(C))) =(? F? )。

A.（a）????? B. A???????C. a??????? D. (b)???????? E. b?????????? F. (A)

10. 廣義表運算式Tail(((a,b),(c,d)))的操作結果是（?? C ）。

A. (c,d)????????? B. c,d??????????????? C. ((c,d))??????? D. d

11. 廣義表L=（a，（b，c）），進行Tail（L）操作后的結果為（D??）。

A. c???????? B. b，c?????????? C.（b，c）????????????? ??D.（（b，c））

12. 廣義表（（a,b,c,d））的表頭是（ A?? ），表尾是（D??? ）。

A. a???????????? B.（）???????????? C.（a,b,c,d）????D.（b,c,d）

二、判斷題

1. 數組不適合作為任何二叉樹的存儲結構。（ ×?? ）

2. 從邏輯結構上看，n維數組的每個元素均屬于n個向量。（ √?? ）

3. 稀疏矩陣壓縮存儲后，必會失去隨機存取功能。（ √?? ）

4. 數組是同類型值的集合。（ ×? ?）

5. 數組可看成線性結構的一種推廣，因此與線性表一樣，可以對它進行插入，刪除等操作。（? ×? ??）

6. 一個稀疏矩陣A_m*n采用三元組形式表示，? 若把三元組中有關行下標與列下標的值互換，并把m和n的值互換，則就完成了A_m*n的轉置運算。（ ×? ???）

7. 二維以上的數組其實是一種特殊的廣義表。（? √ ??）

8. 廣義表的取表尾運算，其結果通常是個表，但有時也可是個單元素值。（ ×?? ）

9. 若一個廣義表的表頭為空表，則此廣義表亦為空表。（ ×?? ）

10. 廣義表中的元素或者是一個不可分割的原子，或者是一個非空的廣義表。（×??? ）

11. 所謂取廣義表的表尾就是返回廣義表中最后一個元素。（ ×? ）

12. 廣義表的同級元素（直屬于同一個表中的各元素）具有線性關系。（? √ ??）

13. 對長度為無窮大的廣義表，由于存儲空間的限制，不能在計算機中實現。（? √ ??）

14. 一個廣義表可以為其它廣義表所共享。（ √ ???）

?

三、 填空題

1．設廣義表L=((),()), 則head(L)是(1) () ___；tail(L)是(2) （()_）__；L的長度是(3)2_ _；深度是?? (4)_2 _。

2. 已知廣義表A=(9,7,( 8,10,(99)),12)，試用求表頭和表尾的操作Head( )和Tail( )將原子元素99從A中取出來。

head（head（tail（tail（head（tail（tail（A）））））））

3. 廣義表的深度是__表展開后所含括號的層數 ____。

4. 廣義表(a,(a,b),d,e,((i,j),k))的長度是（1）?? 5，深度是（2）? 3 _。

5. 已知廣義表LS=(a，(b，c，d)，e),運用head和tail函數取出LS中原子b的運算是_head(head(tail(LS)))_____。

6. 廣義表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是: __head(tail(tail(head(tail(head(A))))))__。

四? 應用題

1．數組A中，每個元素A[i,j]的長度均為32個二進位,行下標從-1到9，列下標從1到11，從首地址S開始連續存放主存儲器中，主存儲器字長為16位。求：

（1）存放該數組所需多少單元？

（2）存放數組第4列所有元素至少需多少單元？

（3）數組按行存放時，元素A[7,4]的起始地址是多少？

（4）數組按列存放時，元素A[4,7]的起始地址是多少？

（1）242 （2）22 （3）s+182 （4）s+142

?

2. 三維數組A[1..10,-2..6,2..8]的每個元素的長度為4個字節，試問該數組要占多少個字節的存儲空間？如果數組元素以行優先的順序存貯，設第一個元素的首地址是100，試求元素A[5,0,7] 的存貯首地址。

數組占的存儲字節數=10*9*7*4=2520；A[5,0,7]的存儲地址=100+[4*9*7+2*7+5]*4=1184

?

3. 數組，廣義表與線性表之間有什么樣的關系？

數組是具有相同性質的數據元素的集合，同時每個元素又有唯一下標限定，可以說數組是值和下標偶對的有限集合。n維數組中的每個元素，處于n個關系之中，每個關系都是線性的，且n維數組可以看作其元素是n-1維數組的一個線性表。

?

4. 什么是廣義表？請簡述廣義表和線性表的主要區別。

線性表中的元素可以是各種各樣的，但必須具有相同性質，屬于同一數據對象。廣義表中的元素可以是原子，也可以是子表。

廣義表中的元素，可以是原子，也可以是子表，即廣義表是原子或子表的有限序列，滿足線性結構的特性：在非空線性結構中，只有一個稱為“第一個”的元素，只有一個成為“最后一個”的元素，第一元素有后繼而沒有前驅，最后一個元素有前驅而沒有后繼，其余每個元素有唯一前驅和唯一后繼。從這個意義上說，廣義表屬于線性結構

轉載于:https://www.cnblogs.com/springside5/archive/2011/12/22/2486319.html

總結

以上是生活随笔為你收集整理的数据结构之【数组和广义表】复习题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。