101資料結構期中考.doc

101資料結構 期中考 A卷 學號 姓名 回答下列各題： 1. 何謂「資料結構」「演算法」計算下列程式中變數被執行的次數為何？ (2) ( ) 次 (3) ( ) 次 sum=sum+1; for (i=1; i = n; i++) sum=sum+1; for (i=1; i = n; i++) for(j=1; j=n; j++) sum=sum+1; 請將下列三個有關陣列與矩陣運算的頻率次數，利用時間複雜度Big-O(陣列元素相加為2n+3= (矩陣相加為2n2+2n+2= (矩陣相乘為2n3+4n2+2n+2= 請比較上一題的時間複雜度 b. 用來表示有序串列之一種方式。 c. 各元素的資料型態可不同。 d. 各元素的資料型態必須相同 e. 支援隨機存取(Random Access) f. 支援循序存取循序存取(Sequential Access)。 g. 插入或刪除元素時較為麻煩。因為須挪移其他元素。 h. 加入、刪除及合併時，只須要改變指標即可。 i. 動態配置記憶體。 j. 靜態配置記憶體。 k. 比較節省記憶體空間。 l. 比較浪費記憶體空間。 7. 請依照下列指令完成堆疊，並將Top的值填入括弧中。 8. 請依照下列指令完成佇列，並將Rear及Front的值填入括弧中。 9. 環狀佇列(Circular Queue)，簡稱CQueue。以下兩個程序式(Procedure)是關於新增項目到CQueue(Procedure Add)及從CQueue刪除項目(Procedure Delete)的演算法。請依照下列指示完成CQueue項目內容的填寫及將Front、Rear、Tag的值填入括弧中。 10. 以下是鏈結堆疊新增(AddStack)及刪除(DelStack)節點的演算法。 Procedure AddStack (item, Procedure AddStack (item, Top) Begin X=newnode( ); X-data=item; X-link=Top; Top=X; End End Procedure Procedure DelStack (Top) Procedure DelStack (Top) Begin If Top=Null then STACK_EMPTY; X=Top; Top=Top-link; free(X); End End Procedure 請參考上述演算法並依照下列指令完成鏈結堆疊。請注意這些指令是連續的。必須將整個操作過程寫進下列表格的右方欄位才能得分。 指令 畫圖指令 1 Call AddStack(‘Data’, Top) 2 Call AddStack(‘Structure’, Top) 3 Call AddStack(‘Structure’, Top) 4 Call AddStack(‘Mid-term’, Top) 5 Call DelStack(Top) 6 Call AddStack(‘Midterm’,Top) 11. 請用虛擬碼(Pseudo Code)攥寫一個遞迴function。Function 名稱為factorial_fun，這個function 有一個參數 value，其資料型態為int。function factorial_fun會計算N! ，計算完成後會送回一個數值。N!的定義如下： 0!=1，1!=1，n!=n(n-1)!, n≧2 12. 請將A-B/(C+D) 用堆疊法轉成後序。必須將步驟寫清楚，否則不予計分。