期中考日期、題目與方式 (代複習)

本學期 112-2 期中考週 (4/13~4/19)
本課程安排於 4/21 08:20 考試
題目與方式如下。


期中考複習

一、術科口試部分題目與方式 (80%)

請同學按分配在此留言答案 (每位 數 題， PART X, Y, Z 各都有題目。)

二、筆試部分題目與方式 (20%)

112-2 資料結構 期中考試練習   NO:         Name:

PART X
I.           

時間複雜度的等級

O(log₂ n) < O(n) < O(n log₂ n) < O(n²)< O(n³)< O(2ⁿ)< O(n!)

時間最短(最少)                                                      時間最長(最多)

1.若一程式的執行時間是 60n²+20nlgn，則時間複雜度為何？
(A) O(60n²)        (B) O(nlog₂n)        (C) O(n²)      (D) O(20nlog₂n)

(分配到的學號末兩碼：4, 11,18, 21, 24, 27)

2.如果一個程式的時間複雜度為O(N²) ，其中N為輸入資料量, 則當資料量增加為原來的100倍時, 計算的時間增加為原來的幾倍？

(A) 10        (B) 10²        (C) 10³        (D) 10⁴ 


(分配到的學號末兩碼：7, 16, 19, 22, 25)

3.計算下面程式的時間複雜度(請使用Big-O表示)

for(i=0; i < n; ++i)

     printf(“%d\n”, i);

(A) O (n!)        (B) O (nlog₂n)         (C) O (n)        (D) O (log₂ n)


(分配到的學號末兩碼：9, 17, 20, 23, 26)

4.如果一個程式的頻率計數為3n³ +6n² + 4n + 9，則時間複雜度為何？    

(A) O(n)       (B) O(1)        (C) O(n²)        (D) O(n³)

(分配到的學號末兩碼：4, 11,18, 21, 24, 27)

5.若矩陣大小為n × n，則此矩陣轉置的時間複雜度為何？

(A) O(n)         (B) O(n²)          (C) O(n log n)         (D) O(n³)

(分配到的學號末兩碼：7, 16, 19, 22, 25)

6.若兩個矩陣大小均為n × n，則此二個矩陣相乘的時間複雜度為何？

(A) O(n)         (B) O(n²)          (C) O(n log n)         (D) O(n³)

(分配到的學號末兩碼：9, 17, 20, 23, 26)

II.        From Ex1

7. 8. 9. 10.
請計算下列程式中變數sum被執行的次數為何？

並請將上面三小題利用時間複雜度Big-O符號來表示頻率次數。
(1) (分配到的學號末兩碼：4, 11,18, 21, 24, 27)
(2) (分配到的學號末兩碼：7, 16, 19, 22, 25)
(3) (分配到的學號末兩碼：9, 17, 20, 23, 26)


PART Y

1. 2. 3. 4. 5. 
假設給予以下的程式片段，請統計出loop內執行次數及Big-O之時間複雜度。

求x=x+1之執行次數與Big-O.
(分配到的學號末兩碼：4, 11,18, 21, 24, 27)
(分配到的學號末兩碼：7, 16, 19, 22, 25)

6. 7. 8. 9. 10. 
假設給予以下的程式片段，請統計出loop內執行次數及Big-O之時間複雜度。

求x=x+1之執行次數與Big-O.
(分配到的學號末兩碼：9, 17, 20, 23, 26)

PART Z

III.     From Ex.2

1. 2. 3. 
三、有一整數陣列int A[50]; （假設sizeof(int)=2）

(1)此陣列共佔多少位元組？

(2)若A[0]在記憶體中的位址為200，則元素A[21] 的位址為何？

(3)若A[31]在記憶體中的位址為300，元素A[40] 的位址為何？
(1) (分配到的學號末兩碼：4, 11,18, 21, 24, 27)
(2) (分配到的學號末兩碼：7, 16, 19, 22, 25)
(3) (分配到的學號末兩碼：9, 17, 20, 23, 26)

4.  
四、假設有一個4×3的二維陣列[A_ij]，其中1≦i≦4, 1≦j≦3，若採取「以列為主(row-major)」的連續記憶體儲存方式，則元素A₃₂應儲存記憶體中的位址為何？(假設A₁₁的記憶體位址在A的位址)
(分配到的學號末兩碼：4, 11,18, 21, 24, 27)

5. 
七、假設有一個(2×3)矩陣A，請將它轉置為(3×2)的B矩陣。其矩陣A的內容如下 (ㄑㄧ：


(分配到的學號末兩碼：7, 16, 19, 22, 25)
 

6. 
八、假設A,B都是(2×3)矩陣，請將A矩陣加上B矩陣以得到一個(2×3)的C矩陣。其矩陣A，B的內容如下  (請自行舉例)：

(分配到的學號末兩碼：9, 17, 20, 23, 26)

7. 8. 
八、假設某一個二維陣列(Array)「以列為主」的順序，存放在記憶體中，並且每個陣列佔用4byte的記憶體空間。若起始位置是100，下列宣告中所列元素存放位置為何？

  Var A：array[-100…1, 1...100]，求A[1,12]的位址？
(分配到的學號末兩碼：4, 11,18, 21, 24, 27)
 

  Var A：array[5…10, -10...20]，求A[5,-5]的位址？

(分配到的學號末兩碼：7, 16, 19, 22, 25)
(分配到的學號末兩碼：9, 17, 20, 23, 26)

IV.      From the Quiz

9.  10.
以下例求出 (1) Call by value (以 值 傳遞 ), (2) Call by address  (以 址 傳遞 ) 的值

(1) (分配到的學號末兩碼：4, 11,18, 21, 24, 27, 9, 17, 20)

(2) (分配到的學號末兩碼：7, 16, 19, 22, 25, 23, 26)

Main {

X←1

Y←2

F (X, Y, X+Y, Y)

Print X, Y

}

Procedure F (A, B, C, D) {

B ← A+D

A ← C

D ← D+1

Return

}

全部共 15則留言 04-10 10:14: 留言格式 (須加上您的學號): 第 ? 題 PART X: ...... PART Y: ...... PART Z: ...... PART X: ...... 04-10 10:15: 留言格式 (須加上您的學號): 第 ? 題 PART X: ...... PART Y: ...... PART Z: ...... 李學業04-10 10:20: 第 9 題 PART X: O(1) O(n) O(n2) PART Y: O(logn) PART Z: (1) X=1 Y=2 (2) X=3 Y=4 阮氏梅香04-10 10:21: 第 9 題 PART X: O(1) O(n) O(n2) PART Y: O(logn) PART Z: (1) X=1 Y=2 (2) X=3 Y=4 周育賢04-10 10:26: 11014D031 第一題 PART X:C PART Y :執行次數1次 O(n2) PART Z :100位元組 武氏萱04-10 10:28: 11014d043 武氏萱 partX 3:C PartY 3:程式碼中 x = x + 1 的執行次數為 O(n^2)。 partZ3:1:100 2:242 3:318 周凱琪04-10 10:48: 11014D033第3題PART X:(C)O(N) 第8題PART Y:O(n^2) 第三題PART Z(1):50 x 2 = 100 個位元組 (2)200 + 21 x 2 = 242 (3)300 + 9 x 2 = 318 廖翊如04-10 10:48: 11014D002第2題PART X (D) PART Y 第8題執行次數為(N+1)*N/2次，Big-O= O(n2) PART Z 第2題 242 金欣華04-10 10:52: s11014f011金欣華PART X第(1)題: (C) O(n2) PART Y :O(n^2) PART Z: (1):50 x 2 = 100 個位元組 (2)200 + 21 x 2 = 242 (3)300 + 9 x 2 = 318 04-10 11:08: 11014D042:第2題 PART X:D PART Y:(n+1)/2次 ,O(n^2) PART Z:242 董澤庭04-10 11:09: 測試 金欣華04-10 11:14: s11014f011金欣華PART X第(1)題: 60n^2 的影響遠大於對數項 20nlog2n 的影響，因為n^2 的增長速度遠快於 nlog2n PART Y :O(n^2) PART Z: (1):50 x 2 = 100 個位元組 (2)200 + 21 x 2 = 242 (3)300 + 9 x 2 = 318 林彩香04-10 11:21: 留言...11014f012第2題PART X (D) PART Y 第8題執行次數為(N+1)*N/2次，Big-O= O(n2) PART Z (1):50 x 2 = 100 個位元組 (2)200 + 21 x 2 = 242 (3)300 + 9 x 2 = 318 04-14 10:07: 1081AD023 第 3 題 PART X:(C) O(n) PART Y:x = n(n+1)/2 , O(n^2) PART Z: 100 個位元組 , 242 , 318 04-23 13:56: PART X1. 答案是 (C) O(n^2) 60n^2 和 20nlog2n 的常數係數 60 和 20 PART Y1. 2. 3. 4. 5答案是. x=x+1 的執行次數為 n*(n+1)/2 次，而 Big-O 時間複雜度為 O(n^2)。 PART Z 1. 2. 3. 答案是(1) 由於 int 的大小為 2 位元組 (16 bits)，而 int A[50] 定義了一個陣列，有 50 個 int 元素，因此陣列 A 共佔用的位元組數為 2 * 50 = 100 位元組。 (2) 根據資訊 A[0] 在記憶體中的位址為 200，且每個 int 元素佔用 2 位元組，因此 A[21] 的位址為 200 + (21 * 2) = 242。 (3) 根據資訊 A[31] 在記憶體中的位址為 300，且每個 int 元素佔用 2 位元組，因此 A[40] 的位址為 300 + (40 * 2) = 380。
留言...
登入帳號密碼代表遵守學術網路規範