計概15-06陣列－公職試題

【選擇題】

【B】01.對於一個存有n個數字並排好順序的一維陣列(one-dimensional array)，下列何者能在O(1)時間內完成？①計算平均值(mean)②計算中位數(median)③計算眾數(mode) (A)只有① (B)只有② (C)只有③ (D)①②③。[109地方四等電子]

O(1)不管序列大小，計算中位數的速度都一樣。

 

【C】02.程式在執行時，不同程序(procedures)在呼叫時必須遵循程序的呼叫慣例(procedure calling conventions)，即利用一個統一的方式使用暫存器，以避免可能造成的潛在錯誤。下列那一個時間點不需要遵守上述的程序呼叫慣例？ (A)呼叫者(caller)呼叫被呼叫者(callee)的過程 (B)被呼叫者即將開始執行之前的起始過程 (C)不再呼叫其他程序的被呼叫者的執行時期 (D)被呼叫者返回呼叫者之前的還原暫存器的過程。[109普考資處]

(A)(B)(D)會改變暫存器中的資料。(C)不再呼叫就不會改變資料，可避免造成錯誤。

 

【A】03.應用程式使用系統呼叫(System Call)時，若欲傳送參數給作業系統，通常不會透過下列那一種途徑？ (A)檔案儲存裝置(File Storage) (B)堆疊(Stack) (C)暫存器(Register) (D)記憶體區塊(Memory Block)以及一個指向此記憶體的指標(Pointer)。[109普考資處]

System Call的參數傳遞：1.堆疊參數(By Stack)。2.暫存器參數(By Register)。3.地址參數(By Address)。

 

【C】04.若一個以行為主(Column-Major)，5列(Row)8行(Column)的二維陣列A，每個陣列元素占用一個記憶體位址空間，已知A[2][2]的記憶體位址為1000₁₀，則A[4][7]的記憶體位址為何？ (A)1021₁₀ (B)1023₁₀ (C)1027₁₀ (D)1032₁₀。[110普考資處]

A[3][0]~A[7][0]、A[3][1]~A[7][1]、A[3][2]~A[7][2]、A[2][3]~A[7][3]、A[2][4]~A[7][4]共27個元素，A[4][7]的記憶體位址=1000 + 1 * 27 = 1027

 

【A】05.A和B皆是有100個元素的一維陣列，且每個元素中的數字皆以32位元(Bits)存放。在執行下列迴圈運算後，需要多少記憶體空間才能將陣列A完整存放？

For (i=0~99)

  A[i]=A[i]+B[i] (A)400個位元組(Bytes) (B)800個位元組(Bytes) (C)3200個位元組(Bytes) (D)6400個位元組(Bytes)。[110普考電子]

32bits * 100 / 8bits = 400Bytes

 

【C】06.假設陣列A有n個整數的元素，讀取(或寫入)陣列A的第i個元素的值，i≦n，電腦所需要的時間 (A)與n的一次方成正比 (B)與n的二次方成正比 (C)常數時間，與n的大小無關 (D)與n的三次方成正比。[110鐵路員級]

直接讀取A[i]的時間為常數時間，與n的大小無關。

 

【B】07.某個以列為主(row-major)儲存的三維陣列A[3][4][5]，若A[0][2][4]的位址是2048₁₀，A[1][2][2]的位址是2084₁₀，則A[2][1][2]的位址為何？ (A)2112₁₀ (B)2114₁₀ (C)2122₁₀ (D)2124₁₀。[111初考資處]

A[0][2][4] = 2048 → A0 + (0*4*5 + 2*5 + 4)d = 2048 → A0 = 2048 - 14d

A[1][2][2] = 2084 → A0 + (1*4*5 + 2*5 + 2)d = 2084 → A0 = 2084 - 32d

求解：A0 = 2020，d = 2

A[2][1][2] = 2020 + (2*4*5 + 1*5 + 2)*2 = 2114

 

【C】08-1.當二維陣列M是以行主序(Column-major)的方式排列資料，若存放M[6,4]的記憶體位置始於600，而存放M[15,10]的記憶體位置始於1500，則存放M[12,8]時應該始於那個記憶體位置？ (A)300 (B)900 (C)1200 (D)1800。

設B為一個變數的所占位元組數，C為總行數

M[15][10]=600+B(15-6)+B(10-4)C=1500 → 3B+2BC=300

M[12][8]=600+B(12-6)+B(8-4)C=600+6B+4BC=600+2(3B+2BC)=600+2×300=1200

【C】08-2.承上題，若改以列主序(Row-major)的方式排列二維陣列M中的資料，則M[12,8]應存在記憶體中何處？ (A)300 (B)900 (C)1200 (D)1800。[111普考電子]

設B為一個變數的所占位元組數，R為總列數

M[15][10]=600+B(10-4)+B(15-6)R=1500 → 2B+3BR=300

M[12][8]=600+B(8-4)+B(12-6)R=600+4B+6BR=600+2(2B+3BR)=600+2×300=1200

 

【B】09.在作業系統中，存取矩陣(access matrix)是用來描述系統保護(protection)的一個通用的模型。下列何者不是存取矩陣的實作方式？ (A)全域表格(global table) (B)反轉式分頁表(inverted page table) (C)物件的存取清單(access lists for objects) (D)領域的能力清單(capability lists for domains)。[111關務四等]

反轉式分頁表用於虛擬記憶體系統中，儲存虛擬位址到實體位址間的對映。

 

【A】10.有關陣列(Array)結構，下列敘述何者錯誤？ (A)陣列的元素無法隨機存取(Random Access) (B)陣列的元素可以循序存取(Sequential Access) (C)是適於儲存相似型態物件的一種結構 (D)可用以實現堆疊(Stack)結構。[112身心五等]

(A)陣列中的每個元素都有一個對應的索引(index)位置，可透過索引值進行隨機存取。

 

【D】11.陣列(Array)Cars[50]的每個元素占用2個位元組(Bytes)。若陣列Cars之起始元素Cars[0]在記憶體中的位址(Address)為1200，則元素Cars[20]的位址為何？ (A)1219 (B)1220 (C)1238 (D)1240。[112身心五等]

元素Cars[20]的位址=1200+2×20=1240

 

【D】12.因為陣列的資料在記憶體存放的位置是連續的，所以若是知道陣列第一個元素的位址及該陣列每一個元素資料儲存位址的大小(占幾個Byte)，就可以根據排放的方式，算出某一個特定元素在記憶體中的位址。假設有一個三維陣列A[-3:5, -4:2, 1:5]，且其起始位置為A[-3, -4, 1]=100，陣列每一元素占記憶體大小2Bytes，以列為主排列(Row Major)，請計算A[1, 1, 3]所在的位置？ (A)1345 (B)2826 (C)267 (D)434。[112初考資處]

A[0,0,0]=x

A[-3,-4,1]=x+2*((-3)*7*5+(-4)*5+1)=100，x=348

A[1,1,3]=348+2*(1*7*5+1*5+3)=434

 

【A】13.有一種矩陣(Matrix)稱為上三角或是下三角矩陣，裡面每一個元素可用a_i,j(i=1..n, j=1..n)表示。因為這種2維的矩陣，在對角線以上或以下的元素都是零(考題沒有暗示上三角或下三角到底是對角線以上或以下是零)。若有一個下三角矩陣，如果零的元素不想浪費記憶體的位置來儲存，我們可以用一個一維的陣列來儲存這些非零的元素，也就是D[1:n(n+1)/2]=[a_1,1, …, a_n,n]。若n=6，且是以列為主(Row Major)的排列方式，請問D[14]=？ (A)a_5,4 (B)a_6,2 (C)a_4,2 (D)a_6,5。[112初考資處]

	1	2	3	4	5
1	1
2	2	3
3	4	5	6
4	7	8	9	10
5	11	12	13	14	15

 

【C】14.下列關於陣列(array)與連結串列(linked list)的敘述何者正確？ (A)連結串列需存放在記憶體上的一塊連續的位置 (B)陣列裡的資料存取需透過指標循序存取 (C)我們一般稱陣列為直接存取資料結構 (D)連結串列裡的資料可透過定址直接存取。[112國安五等]

(A)連結串列，透過指標連接在記憶體中的任何位置的節點。

(B)陣列裡的資料，透過索引直接存取。

(D)連結串列裡的資料，透過指標連結節點來存取資料。

 

【D】15.有關陣列(Array)與鏈結串列(Linked List)的敘述，下列何者錯誤？ (A)陣列占用連續的記憶體空間 (B)鏈結串列不必占用連續的記憶體空間 (C)鏈結串列在插入資料(Insertion)與刪除資料(Deletion)上比陣列容易 (D)陣列在隨機存取(Random Access)上一般會比鏈結串列慢。[112普考資處]

(D)陣列在隨機存取上一般會比鏈結串列快

 

【D】16.若宣告下列2維整數陣列

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

則下列那個元素為0？ (A)a[0][1] (B)a[1][0] (C)a[1][2] (D)a[2][1]。[112普考電子]

a[3][3] = {{1,2,0},{3,4,5},{6,0,0}};

a[0][1] = 2

a[1][0] = 3

a[1][2] = 5

a[2][1] = 0

 

【D】17.假設有一陣列A，以主行順序(Column major order)儲存資料，若A[5,1]位置為1234，A[7,5]位置為1260，則A[6,4]位置為何？ (A)1248 (B)1249 (C)1252 (D)1253。[112普考電子]

A[7,5]：1260=1234+[(5-1)*m+(7-5)]*d

→ 13=2md+d

假設d=1，則m=6

A[6,4]：1234+[(4-1)*m+(6-5)]*d

→ 1234+[3*6+1]*1=1253