國立空中大學

台北學習指導中心

【資料結構】科

87年度下學期 期中考考題 解答參考

簡答題 30% @6	1.一個功能定義，一個儲存結構和 一組對應於每一功能的演算法。 2.O(n2) 演算式： f(n) =3+6+9....+3n =3(1+2+3+...+n)=3* n(n+1)/2 =3/2n2+3/2n O(3/2n2+3/2n)=O(3/2n2)=O(n2) 3.陣列、堆疊、佇列、串列 （任舉三項） 4.堆疊是一個有序的串列，插入及刪除的運算都發生在 有序串列的某一端。 佇列也是一個有序的串列（相同點），但其元素的插入和刪除則 發生在不同端。 5. ab/c-de*+ac*-
填充題30%	O(0)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)
問答題 40% @10	1.一個程式的空間複雜度取決於它所使用的記憶體大小， 而時間複雜度則決定於程式完全執行所需的時間。 2.程式無止境的呼叫自己，由於基礎事例不存在或永不被執行， 造成程序無止境的執行，直到記憶體空間耗盡，通常會造成 當機。 3. (1)取得一個新節點，位址為Temp。 (2)將Temp的next指標指向node1的next指標所指的位址（node2） (3)將node1的next指標指向Temp。 4. read N; I:=1; result:=1; /*初始條件*/ if N=1 then print N else while I<N result:=result*I; I:=I+1;/*迴圈中的變數*/ end while print result*N;

回資料結構課程主畫面