專項練習數組（4）

1.矩陣中的資料元素可以是不同的資料類型 ，這樣的說法正确嗎？(B)

A.正确

B.不正确

解析：矩陣中的資料元素可以是不同的資料類型；強調的是矩陣中的元素，而不是其中一個元素的構成，也就是說你舉的這個例子中，data[0],data[n]的資料元素類型一定是相同的，而不是把其中一個元素拿出來研究其中是不是存在不相同的資料元素。

2.一個稀疏矩陣Am*n 采用三元組形式表示,若把三元組中有關行下标與列下标的值互換,并把m和n的值互換,則就完成了Am*n 的轉置運算(B)。

A.對

B.錯

解析：三元組轉置： （1）将數組的行列值互相交換 （2）将每個三元組的i和j互相交換 （3）重排三元組的之間的次序便可實作矩陣的轉置。

3.數組A中，每個元素的長度為3個位元組，行下标i從1到8，列下标j從1到10，從首位址SA開始連續存放在存儲器内，該數組按行存放時，元素A[8][5]的起始位址為（C ）。

A.SA+141

B.SA+144

C.SA+222

D.SA+225

解析：首先，本題的數組是從A[1][1]開始的，也就是說和所謂的數組從零開始沒什麼關系。A[1][1]的起始位址為SA，那麼A[1][2]為SA+3.....A[2][1]為SA+3*10.....A[i][j]為SA+(（i-1）*10+(j-1))*3。那麼A[8][5]的起始位址就是SA+ （7*10+4）*3=SA+222.

4.循環隊列SQ的存儲空間是數組d[m]，隊頭、隊尾指針分别是front和rear，則執行出隊後其頭指針front值是（D）

A.front=front+1

B.front=(front+1)%(m-1)

C.front=(front-1)%m

D.front=(front+1)%m

解析：循環隊列  進隊：隊尾指針(rear+1)%m；出隊：對頭指針(front+1)%m；m為數組容量。

5.有一随機數組(25,84,21,46,13,27,68,35,20),采用某種方法對它們進行排序,其每趟排序結果如下,則該排序方法是（A）。

初 始:25,84,21,46,13,27,68,35,20 

第一趟:20,13,21,25,46,27,68,35,84

第二趟:13,20,21,25,35,27,46,68,84 

第三趟:13,20,21,25,27,35,46,68,84

A.基數排序

B.插入排序

C.快速排序

D.起泡排序

解析：快速排序：關鍵節點前面的元素都比它小，後面的元素都比它大；選擇排序：從剩餘元素後面找最小元素和目前元素交換；插入排序：關鍵元素前面的元素已經排好序。

6.在一個有8個int資料的數組中，随機給出數組的資料，找出最大和第二大元素一定需要進行（B）次比較：

A.8

B.9

C.10

D.11

解析：選擇問題的複雜度下界，已經有證明，可參考算法導論或屈婉玲的算法設計與分析技術這本書。對于選擇問題，找最大問題的下界是：n-1；找第二大問題的下界是：n+logn-2。是以，本題，n=8，代入下界公式：8+3-2 = 9，是以選擇B.

7.若下三角矩陣An×n，按列順序壓縮存儲在數組Sa[0…(n+1)n/2]中，則非零元素aij的位址為（A ）。（設每個元素占d個位元組，數組下标從0開始） 。

A.[(j-1)*n+i-1]*d

B.[(j-1)*n+i]*d

C.[(j-1)*n+i+1]*d

D.[(j-1)*n+i-2]*d

解析：(n - j + 2 +n) (j - 1) / 2 + i - j。

8.下列數組定義及指派，錯誤的是（B）

A.int intArray[ ];

B.int intArray=new int[3]; intArray[1]=1; intArray[2]=2;

C.int a[ ]={1, 2, 3, 4, 5};

D.int a[ ] [ ]=new int[2] [ ]; a[0]=new int[3]; a[1]=new int[3];

解析： A選項隻能算是一個數組的聲明，而非定義，也不是指派。B選項三條語句都是指派。C選項是定義。D選項是定義，然後兩條語句是指派。

9.已知一稀疏矩陣的三組元表為：（1，2，3），（1，6，1），（3，1，5）（3，2，-1），（5，4，5）（5，1，-3），則其轉置矩陣的三元組表中第3個三元組為（A）

A.(2, 1, 3)

B.(3, 1, 5)

C.(3, 2, -1)

D.(2, 3, -1)

解析：稀疏矩陣：矩陣中大多數元素為0元素，用一個三元組存放矩陣中的元素，形式為( i，j，e)，其中i表示行号，j表示列号，e表示元素值。第三個三元組為（2[第二行]，1[第一列]，3[元素值為3]）。

10.以下操作中，數組比連結清單速度更快的是（A、C、E)

A.原地逆序

B.頭部插入

C.傳回中間節點

D.傳回頭部節點

E.選擇随機節點

解析：A選項，如果是數組隻要周遊一半元素就可以了，翻轉的思想類似于字元串逆序，但連結清單如果要完成逆序，就算隻是修改指針也要把所有的元素周遊完，是以相比而言數組還是比連結清單快的。B連結清單隻需插入一個節點，數組需移動n個元素C選項的通路中間節點，數組可以通過array[length/2]通路，連結清單需要依次查找到中間節點。D頭結點都一樣。E 數組是順序存儲的線性表，相對于連結清單而言主要的優點就是可以通過下标随機通路數組中的任意元素。

11.矩陣不僅是表示多元數組，而且是表示圖的重要工具，這樣的說法正确嗎？（A）

A.正确

B.不正确

解析：圖的表示方法有鄰接矩陣和鄰接表。

12.下列哪些不是線性表？（C）

A.隊列

B.棧

C.關聯數組

D.連結清單

解析：1. 隊列（Queue）是隻允許在一端進行插入，而在另一端進行删除的運算受限的線性表； 2. 棧（stack）在計算機科學中是限定僅在棧頂進行插入或删除操作的線性表。3. “關聯數組”是一種具有特殊索引方式的數組。不僅可以通過整數來索引它，還可以使用字元串或者其他類型的值（除了NULL）來索引它。 關聯數組和數組類似，由以名稱作為鍵的字段和方法組成。 它包含标量資料，可用索引值來單獨選擇這些資料，和數組不同的是， 關聯數組的索引值不是非負的整數而是任意的标量。這些标量稱為Keys，可以在以後用于檢索數組中的數值。 關聯數組的元素沒有特定的順序，你可以把它們想象為一組卡片。每張卡片上半部分是索引而下半部分是數值。

13.下列叙述中正确的是（ A ）。

A.順序存儲結構的存儲一定是連續的，鍊式存儲結構的存儲空間不一定是連續的

B.順序存儲結構隻針對線性結構，鍊式存儲結構隻針對非線性結構

C.順序存儲結構能存儲有序表，鍊式存儲結構不能存儲有序表

D.鍊式存儲結構比順序存儲結構節省存儲空間

解析： 1.順序表的特點是邏輯上相鄰的資料元素，其實體存儲位置也相鄰，并且順序表的存儲空間需要預先配置設定；2.鍊式存儲中邏輯上相鄰的資料元素其實體存儲位置不一定相鄰，是因為連結清單通過指針實作元素間的邏輯關系；3.順序存儲結構适合頻繁的查詢時使用，鍊式存儲結構适合頻繁的插入，删除和更新元素時使用。

14.假設要存儲一個資料集，資料維持有序，對其的操作隻有插入、删除和順序周遊，綜合存儲效率和運作速度，下列哪種資料結構是最适合的是？（B）

A.數組

B.連結清單

C.哈希表

D.隊列

解析： 數組插入、删除需要移動數組元素，平均移動n/2。哈希表難以實作順序周遊。隊列插入删除效率低下。

15.判斷下列說法是否正确：一個n階對稱矩陣，矩陣元為Aij将其下三角部分以行序為主序存放在一維數組M[0,n(n+1)/2-1]中，設矩陣最左上角矩陣元為A00，則矩陣元A64對應的位置為M[25]。( A)

A.正确

B.正确

解析：A00的n為1放在M[0] A11的n為2放在M[2] 以此類推A55的n為6放在M[20] A64為第七行的第5個數，是以在M[25] 或者A66放在M[27]，往前數兩個就是A64的位置。

16.稀疏矩陣一般的壓縮存儲方式有兩種，即 。（C）

A.二維數組和三維數組

B.三元組和散列

C.三元組和十字連結清單

D.散列和十字連結清單

解析：所謂三元組就是一個元素存放三個資訊，矩陣中的行号，列号以及值，這樣就可以不存放值為0的元素，實作壓縮。 十字連結清單相當于是鄰接表和逆鄰接表的合集，在一個元素裡面存放了值以及出度表和入度表，這樣也不需要像鄰接矩陣那樣存放大量0元素，而且找一個節點的入節點和找出節點一樣快。

17.有一個二維數組A[10][5]，每個資料元素占1個位元組，且A[0][0]的存儲位址是1000，則A[i][j]的位址是多少 ？（A)

A.1000+10i+j

B.1000+i+j

C.1000+5i+j

D.1000+10i+5j

解析：因為是5列10行的數組，而且配置設定記憶體位址是連續的，如果按行存儲的，則每增加1行位址就會增加5，然後加上所在的列就是目前的位址，是以就是1000+5i+j。

18.在定義 int a[3][4][2]; 後，第 20 個元素是（  A ）

A.a[2][1][1]

B.a[1][0][1]

C.a[2][0][1]

D.a[2][2][1]

解析：三維數組可以看成是一本書！int a[3][4][2]; 就是有3頁每頁4行2列.

19.若有定義:int c[4][5],( *pc)[5];pc=c;那麼，下列對數組C的元素引用正确的是(D )。

A.pc+1

B.* (pc+3)

C.* (pc+1) +3

D.* (*pc+2)

解析：pc是一個數組指針（指向數組的指針），指向列數為5的二維數組，pc = c，表示pc指向二維數組的第一行，pc+1偏移一行，一行5個元素。*pc得到二維數組c的第一行數組的首位址，+2偏移到c[0][2]的位址，解引用就得到資料2。c[4][5]可以了解為4個長度為5的一位數組，這四個一維數組的位址要用數組指針存放。

20.二維數組和多元數組均不是線性結構。（ A ）

A.正确

B.不正确

解析：線性結構是一個有序資料元素的集合。 其中資料元素之間的關系是一對一的關系，即除了第一個和最後一個資料元素之外，其它資料元素都是首尾相接的。常用的線性結構有：線性表，棧，隊列，雙隊列，數組，串。非線性結構中各個資料元素不再保持在一個線性序列中，每個資料元素可能與零個或者多個其他資料元素發生聯系。根據關系的不同，可分為層次結構和群結構。常見的非線性結構有：二維數組，***數組，廣義表，樹(二叉樹等)，圖。（其中***數組是由多個一維數組組成的，是以不再是線性結構）。