期中考試題目與方式

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

I.           From the Quiz

時間複雜度的等級

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

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

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

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

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

6.計算下面程式的時間複雜度(請使用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)

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

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

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

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

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

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

II.        From Ex1

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

並請將上面三小題利用時間複雜度Big-O符號來表示頻率次數。

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

求x=x+1之執行次數與Big-O.

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

求x=x+1之執行次數與Big-O.

III.     From Ex.2

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

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

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

(3)若A[31]在記憶體中的位址為300，元素A[40] 的位址為何？

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

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

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

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

  Var A：array[-100…1, 1...100]，求A[1,12]的位址？

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

IV.      From the Quiz

14. 以下例求出 (1) Call by value, (2) Call by address 的值

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

}

全部共 0則留言
留言...
登入帳號密碼代表遵守學術網路規範