羅德興老師的教學歷程檔案 - 112-2 資料結構 (2024年) - 112-2 資料結構 期中考試題
 

企業資訊與管理系
助理教授/日導
羅德興

 歷程檔案 Portfolio

    112-2 資料結構 期中考試題

    本課程安排於 4/21 08:20 考試


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

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

    請同學在答案紙上  寫下 你所完成的作業。

    Unit 1~Unit 4 的作業 (平時)


    二、筆試部分題目共 15 題  (20%)

    請同學在答案紙上  標明題號  寫下 以下各題的演算過程。

    可使用手機、電腦或網路。  

    PART X
    I.           

    時間複雜度的等級

    O(log2 n) < O(n) < O(n log2 n) < O(n2)< O(n3)< O(2n)< O(n!)

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

     

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


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

    (A) 10        (B) 102        (C) 103        (D) 104 

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

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

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

    (A) O (n!)        (B) O (nlog2n)         (C) O (n)        (D) O (log2 n)

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

    (A) O(n)       (B) O(1)        (C) O(n2)        (D) O(n3)



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

    (A) O(n)         (B) O(n2)          (C) O(n log n)         (D) O(n3)



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

    (A) O(n)         (B) O(n2)          (C) O(n log n)         (D) O(n3)


     

    II.        From Ex1

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

    (1)

    (2)

    (3)

    sum=sum+1;    

     

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

    sum=sum+1;

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

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

    sum=sum+1;

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

    PART Y

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

    For i = 1 to n

         For j = 1 to i

             x = x+1

         End

    End

    求 程式片段中     x=x+1   之執行次數與Big-O.

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

    i = n;           (n>=1)

    While (i >0)

       x = x+1

       i = i/2

    Loop

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

    PART Z

    III.     From Ex.2

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

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

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

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

     

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


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

     

    13. 

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

     

    14. 
    假設某一個二維陣列    (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

    15.
    以下例求出 (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則留言
    登入帳號密碼代表遵守學術網路規範

    		文章分類 Labels

    		最新文章 Top10

    中華科技大學數位化學習歷程 - 意見反應