回資料結構主畫面
國立空中大學
台北學習指導中心
【資料結構】科
國立空中大學八十七學年度下學期期中考試試題（正）
考試科目：資料結構
一、簡答題（30%，每題6分）
1.一個資料結構正式的定義包含那三部分
2.假設某演算法的執行布驟可用f(n)=3+6+9+12+...+3n來表示，請以漸
近式來表示其時間複雜度（time complexity）
3.請說明堆疊（stack）與佇列（queue）的異同
4.試任舉3項至目前為止學過的資料結構的名稱
5.請將下列以中序表示法顯示的運算式轉換成後序表示法
a/b-c+d*e-a*c
二、填充題（30%，每格5分）
請依漸近式表示法的大小順序排列以下的漸近式：
n 2 3
O(1),O(2 ),O(n ),O(nlogn),O(n),O(logn),O(n )
O(1)<(1)<(2)<(3)<(4)<(5)<(6)
三、問答題（40%，每題10分）
1.請說明時間複雜度（time complexity）與空間複雜度（space
complexity）的定義
2.何謂無限回歸（infinite regression），通常會造成甚麼結果？
3.請描述插入一個節點到鏈結串列中的程序
插入前 插入點
Node1 ↙ Node2
→┌─┬─┐→┌─┬─┐→ ┌─┬─┐→
└─┴─┘ └─┴─┘ └─┴─┘
temp
┌─┬─┐
插入後 └─┴─┘
Node1 ↗ ↘ Node2
→ ┌─┬─┐ ┌─┬─┐→ ┌─┬─┐→
└─┴─┘ └─┴─┘ └─┴─┘
4.請改良下列用遞迴法計算N階乘的程式，並說明修改的理由：
read N;
while I<N do result:=result*I;
print N;
國立空中大學八十七學年度下學期期中考試試題（副）
考試科目：資料結構
一 簡答題（36%，每題6分）
1. 請說明時間複雜度（time complexity）與空間複雜度（space
complexity）的定義
2. 一個資料結構正式的定義包含那三部分
3. 何謂同位組合（Union），請從資料結構的觀點說明
4. 何謂轉置矩陣，可用那種資料結構來表示
5. 請說明堆疊（stack）與佇列（queue）的異同
6. 試任舉3項至目前為止學過的資料結構的名稱
二 問答題（64%）
1.(10%)假設某演算法的執行布驟可用f(n)=3+6+9+12+...+3n 來表示，請
以漸近式來表示其時間複雜度（time complexity）
2.(6%)何謂無限回歸（infinite regression），通常會造成甚麼結果？
3.(16%)請描述插入一個節點到鏈結串列中的程序
插入前 插入點
Node1 ↙ Node2
→ ┌─┬─┐→ ┌─┬─┐→ ┌─┬─┐→
└─┴─┘ └─┴─┘ └─┴─┘
temp
┌─┬─┐
插入後 └─┴─┘
Node1 ↗ ↘ Node2
→┌─┬─┐ ┌─┬─┐→ ┌─┬─┐→
└─┴─┘ └─┴─┘ └─┴─┘
4.(14%)請改良下列用遞迴法計算 N 階乘的程式，並說明修改的理由：
read N;
while I<N do result:=result*I;
print N;
n 2
5.(12%)請依漸近式表示的大小順序排列以下的漸近式：O(2 ), O(n ),
3
O(nlogn), O(n), O(logn), O(n )
6.(6%)請將下列以中序表示法顯示的運算式轉換成後序表示法
a/b-c+d*e-a*c
國立空中大學八十七學年度下學期期末考試試題（正）
科目：資料結構
請橫式書寫
一、簡答題（40%，每題8分）
1.請說明最大堆積（Max Heap）與最小堆積（Min Heap）的定義，並各舉
一實例
2.何謂雜湊函數，如何設計一個良好的雜湊函數？
3.課本中介紹了圖形結構（graph），這種結構和樹（tree）結構有何異
同？請就課文中所學的或自己的經驗舉兩個例子說明圖形結構的用途
4.試任舉8項至目前為止在課本上學過的資料結構的名稱
5.請計算選擇排序法的執行時間複雜度
二、問答題（60%，每題15分）
1.請用氣泡排序法的演算法將以下的陣列由小到大排列，並計算氣泡排序
法的執行時間複雜度
a(0) a(1) a(2) a(3) a(4) a(5) a(6)
36 67 53 11 7 87 45
2.何謂2-3樹？試說明其優點與特徵
3.期中考曾描述插入一個節點到下列鏈結串列中的程序
插入前 插入點
Node1 ↙ Node2
→ ┌─┬─┐→ ┌─┬─┐→ ┌─┬─┐→
└─┴─┘ └─┴─┘ └─┴─┘
temp
插入後 ┌─┬─┐
└─┴─┘
Node1 ↗ ↘ Node2
→┌─┬─┐ ┌─┬─┐→ ┌─┬─┐→
└─┴─┘ └─┴─┘ └─┴─┘
假如我們把上面這個鏈結串列看成是樹（tree），在的表示法上應做何
改變，再插入一個節點temp2後可能變成甚麼樣的結構？
4.請將下列的樹林改成二元樹，並分別做的中序，前序與後序追蹤
（圖略）
國立空中大學八十七學年度下學期期末考試試題（副）
考試科目：資料結構
一、簡答題（40%，每題8分）
1. (1) 請說明樹狀排序法的原理，並計算平均執行時間複雜度
(2) 請計算選擇排序法的執行時間複雜度
2. 請說明最大堆積（Max Heap）與最小堆積（Min Heap）的定義，並各
舉一實例
3. 何謂雜湊函數，如何設計一個良好的雜湊函數？
4. 課本中介紹了圖形結構（graph），這種結構和樹（tree）結構有何異
同？請就課文中所學的或自己的經驗舉兩個例子說明圖形結構的用途
5. 何謂2-3樹？試說明其優點與特徵
二、問答題（60%，每題15分）
1. 請稍微改變氣泡排序法的演算法將以下的陣列由大小排列，並計算氣
泡排序法的執行時間複雜度
a(0) a(1) a(2) a(3) a(4) a(5) a(6)
36 67 53 11 7 87 45
2. 試任舉5項至目前為止在課本上學過的資料結構的名稱
3. 期中考曾描述插入一個節點到下列鏈結串列中的程序
插入前 插入點
Node1 ↙ Node2
→ ┌─┬─┐→ ┌─┬─┐→ ┌─┬─┐→
└─┴─┘ └─┴─┘ └─┴─┘
temp
插入後 ┌─┬─┐
└─┴─┘
Node1 ↗ ↘ Node2
→┌─┬─┐ ┌─┬─┐→ ┌─┬─┐→
└─┴─┘ └─┴─┘ └─┴─┘
假如我們把上面這個鏈結串列看成是圖形結構（graph），在表示法
上應做何改變，再插入一個節點temp2後可能變成甚麼樣的結構？
4. 請將下列的樹林改成二元樹，並分別做樹與樹林的中序，前序與後序
追蹤
（圖略）
.
回資料結構主畫面