國立空中大學 資料結構 課程參考資料 本網頁內容是由課程面授講師張志燦，為選修本課程同學自行修習所設計與製作；其相關版權分屬國立空中大學與張志燦。 歡迎各方指教並提供相關資訊。

資料結構 部份作業 參考解答

附記：茲因個人工作目前較為吃重，目前只能做這些解答，敬請各位同學見諒！
希望同學能多努力，尤其作業應繳交，祝考試順利！

第一章題目

階乘函數，當n≦1時，其值為1，當n＞1時，其值為 n*(n-1)!，分別利用迴圈與遞迴兩種方式來計算n!。

題解：

●迴圈
long int factorial (int n)
{ int a;
long int b;
b=1;
for (a=n; a>0; a--)
b*=a;
return(b)
}

●遞迴
long int factorial (int n)
{ if n=1;
return (1);
else
return n*factorial(n-1);
}

設計一種結構來表示太陽系的行星，每一行星中的欄位包含行星名稱，距離太陽系的距離（公里），擁有的衛星個數。針對地球及火星，分別在它們的各欄位中填入適當的值。

題解：

/* define the data structure of a planet in the solar system*/
struct {
char *name;
int no_satellite;
long int distance; /* measured in kilometer */
} planet;

void main(void)
{ planet earth, mars;

earth.name = 'earth';
earth.no_satellite = 1;
earth.distance = 150000000;

mars.name = 'mars';
mars.no_satellite = 3; /* not so sure */
mars.distance = 90000000; /* not so sure */

/* .. other code .. */
}

第三章題目

請寫出下列運算式的後序表示法
(1) a + b * c
(2) a/b + c*d
(3) (a+b)*c/(d-e)

題解：
(1) a + b * c → abc*+
(2) a/b + c*d → ab/cd*-
(3) (a+b)*c/(d-e) → ab+c*de-/

第四章題目

●什麼情況是無限回歸？

解：
無止境的呼叫自己和令遞迴停止的基礎事例永不被執行的情況，即為無限回歸。

●那二種程式錯誤會造成無限回歸的情形？
解：
(1) 遞迴程式裡沒有基礎事例。
(2) 基礎事例永不被執行。

第五章題目

●有一鏈串列結構如下表，串列頭指向Ｂ，若將Ｆ節點插入Ｄ和Ｃ之間，則下表會如何變化？

解：
此表展開後如下圖所示：
header→Ｂ→Ａ→Ｄ→Ｃ→Ｅ→Null
將Ｆ節點插入Ｄ和Ｃ之間,則如下圖所示：
header→Ｂ→Ａ→Ｄ→Ｆ→Ｃ→Ｅ→Null
所以此表會成為如下圖所示，斜體字為增修過的指標與資料內容。：
資料
指標

資料	指標
Ｃ	Ｅ
Ｂ	Ａ
Ｄ	Ｆ
Ｅ	Null
Ａ	Ｄ
Ｆ	Ｃ

●承上題，若將節點Ａ刪除，該表將如何變化？

解：
將Ａ節點刪除，則展開之串列成為：
header→Ｂ→Ｄ→Ｆ→Ｃ→Ｅ→Null
所以此表會成為如下圖所示，斜體字為增修過的指標與資料內容。：
資料
指標

資料	指標
Ｃ	Ｅ
Ｂ	Ｄ
Ｄ	Ｆ
Ｅ	Null
Ａ	Null
Ｆ	Ｃ

回資料結構課程主畫面