1. 誰有數據結構的期末試題，借我參考下馬上考試了
A：
06－07第一學期期末考試試卷
試卷代碼：03266A 授課課時：112
課程名稱：數據結構與演算法 適用對象：本科
一、單項選擇題(從下列各題四個備選答案中選出一個正確答案，並將其代號寫在答題紙相應位置處。答案錯選或未選者，該題不得分。每小題2分，共24分。)
1.數據結構被形式地定義為(K,R)，其中K是數據元素的有限集，R是K上的___有限集。
A.操作 B.映像 C.存儲 D.關系
2.線性表若採用鏈式存儲結構時，要求內存中可用存儲單元的地址____。
A.必須連續的 B.部分地址必須連續的 C.一定是不續的 D.連續不連續都可以
3.一個棧的入棧序列是a、b、c、d、e，則棧的不可能輸出序列是____。
A.edcba B.decba C.dceab D.abcde
4.一個隊列的入隊序列是1、2、3、4，則隊列輸出序列是____。
A.4、3、2、1 B.1、2、3、4 C.1、4、3、2 D.3、2、4、1
5.棧和隊列的共同點是____。
A.都是先進後出 B.都是先進先出
C.只允許在端點處插入、刪除元素 D.沒有共同點
6.在一個單鏈表中，已知q所指結點是p所指結點的前驅結點，若在q和p之間插入s結點，則執行____。
A. s->next = p->next; p->next=s; B. p->next = s->next; s->next = p;
C. q->next = s; s->next = p; D. p->next = s; s->next = q;
7.設串s1=『ABCDEFG』，s2=『PQRST』，函數con (x, y) 返回x與y串的連接串，函數subs (s, i, j) 返回串s的從序號i的字元開始的j個字元組成的子串，函數len (s) 返回串s的長度，則con (subs (s1, 2, len (s2)), subs (s1, len (s2), 2)) 的結果串是____。
A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF
8.設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數至少為____。
A. 2h B. 2h-1 C. 2h +1 D. h +1
9.某二叉樹的前序遍歷結點訪問順序是abdgcefh，中序遍歷結點訪問順序是dgbaechf，則其後序遍歷結點訪問順序是____。
A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca
10.具有6個頂點的無向圖至少應有____條邊才能確保是一個連通圖。
A. 5 B. 6 C. 7 D. 8
11.採用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為–。
A. n B. n/2 C. (n+1)/2 D. (n-1)/2
12.排序方法中，從未排序序列中挑選元素，並將其依次放入已排序序列(註：初始時為空)的一端的方法，稱為____。
A. 希爾排序 B. 歸並排序 C. 插入排序 D. 選擇排序
二、填空題(請在每小題的橫線上填入正確內容，每空1分，共7分。)
1.在樹形結構中，樹根結點沒有 結點，其餘每個結點有且只有 個前驅結點。
2.對n個元素的序列進行起泡排序時，最少的比較次數是 。
3.空串是 ，其長度等於0。
4.一棵有n個結點的滿二叉樹共有 個葉子結點。
5.在散列函數H(key)=key % p中，p應取 。
6.已知模式串t=『abcaabbabc』， 其用KMP法求得的每個字元對應的next函數值為 。
三、簡答題(本大題共3小題，每小題5分，共15分)
1.在對線性表的處理中一般使用兩種存儲結構，順序存儲結構和鏈式存儲結構。試敘述在什麼情況下使用順序表比鏈表好？
2.簡述什麼是穩定的排序，什麼是不穩定的排序。
3.下列中綴表達式對應的後綴形式是什麼？
(1) (A + B) * D + E / (F + A * D) + C
(2) A && B|| ! (E > F) {註：按C的優先順序)
四、判斷題(本大題共10小題，命題正確的在題後括弧內寫 「T」，錯誤的在題後括弧內寫「F」，每小題1分，共10分)
1.數據元素不是數據的最小單位( )。
2.已知一棵二叉樹的前序序列和後序序列可以唯一地構造出該二叉樹。( )
3.AOE網是一種帶權的無環連通圖。( )
4.對於同一組待輸入的關鍵碼集合，雖然各關鍵碼的輸入次序不同，但得到的二叉搜索樹都是相同的( )。
5.一棵樹中的葉子數一定等於與其對應的二叉樹的葉子數。( )
6.鄰接表只能用於有向圖的存儲，鄰接矩陣對於有向圖和無向圖的存儲都適用。( )
7.折半插入排序是穩定的。( )
8.在散列法中，使用雙散列函數可保證絕對不產生沖突。( )
9.消除遞歸不一定需要使用棧( )
10.堆排序是交換排序的一種。( )
五、分析應用題（本題共26分，1、4小題各6分，2、3小題各7分）
1．閱讀後分析下面程序段的功能是什麼? （6分）
SeqStack S1, S2, tmp;
DataType x; //設棧tmp和S2已做過初始化
while ( ! StackEmpty (S1))
{ x=Pop(S1) ;
Push(tmp,x);
}
while ( ! StackEmpty (tmp) )
{ x=Pop(tmp);
Push( S2, x);
}
2.某子系統在通信聯絡中只可能出現8種字元，其出現的概率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11試設計赫夫曼編碼。（7分）
3.設散列表為HT[13], 散列函數為 H (key) = key %13。用線性探測再散列法解決沖突, 對下列關鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。畫出相應的散列表, 並計算等概率下搜索成功的平均搜索長度。（7分）
4.設待排序的排序碼序列為{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 試寫出使用希爾排序(增量為5,2,1)方法每趟排序後的結果。（6分）
六、演算法設計題（本題共18分，第1小題10分，第2小題8分）
1.編寫一個演算法frequency，統計在一個輸入字元串中所含各個不同字元出現的頻度。用適當的測試數據來驗證這個演算法。(10分)
2.在一棵以二叉鏈表表示的二叉樹上，試寫出用按層次順序遍歷二叉樹的方法，並統計樹中具有度為1的結點數目的演算法。要求給出二叉鏈表的類型定義。(8分)
答案：
06－07第一學期
期末考試參考答案與評分標准
試卷代碼：03266A 授課課時：112
課程名稱：數據結構與演算法 適用對象：本科
一、單項選擇題(每小題2分，共24分。)
1. D 2. D 3. C 4. B 5. C 6. C
7. D 8. B 9. D 10. A 11. C 12. D
二、填空題(每空1分，共7分。)
1.父(或前驅)， 1
2. n-1
3. 不包含任何字元的串
4. (n+1)/2
5. 素數
6. 0111223123
三、簡答題(每小題5分，共15分)
1.答：① 順序存儲時，相鄰數據元素的存放地址也相鄰(邏輯與物理統一)；要求內存中可用存儲單元的地址必須是連續的。
優點：存儲密度大，存儲空間利用率高。缺點：插入或刪除元素時不方便。
②鏈式存儲時，相鄰數據元素可隨意存放，但所佔存儲空間分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針
優點：插入或刪除元素時很方便，使用靈活。缺點：存儲密度小(<1)，存儲空間利用率低。
順序表適宜於做查找這樣的靜態操作；鏈表宜於做插入、刪除這樣的動態操作。
若線性表的長度變化不大，且其主要操作是查找，則採用順序表；
若線性表的長度變化較大，且其主要操作是插入、刪除操作，則採用鏈表。
2.答：在排序序列中，任何兩個相等的關鍵字Ki=Kj,如果在排序前的序列中Ki領先於Kj，若在排序後的序列中Ki仍領先於Kj，則稱所用的排序方法是穩定的；反之，若可能使排序後的序列中Kj領先於Ki，則稱所用的排序方法是不穩定的。
3.答：各中綴表達式的後綴形式如下：
(1)AB+D*EFAD*+/+C+
(2)AB&&EF>!||
四、判斷題(本大題共10小題，命題正確的在題後括弧內寫 「T」，錯誤的在題後括弧內寫「F」，每小題1分，共10分)
1.T 2.F 3.T 4.F 5.F
6.F 7.T 8.F 9.T 10.F
五、分析應用題（1、4小題各6分，2、3小題各7分）
1．（6分）
答：程序段的功能是利用tmp棧將一個非空棧s1的所有元素按原樣復制到一個棧s2當中去。
2．（7分）
答：為方便起見，設各種字元的權值w={5,29,7,8,14,23,3,11}。因為n=8，所以要構造的赫夫曼樹共有m=2n-1=2*8-1=15個結點。生成的赫夫曼樹為下圖所示：
赫夫曼編碼為：概率為0.23的字元編碼為：00
概率為0.11的字元編碼為：010
概率為0.05的字元編碼為：0110
概率為0.03的字元編碼為：0111
概率為0.29的字元編碼為：10
概率為0.14的字元編碼為：110
概率為0.07的字元編碼為：1110
概率為0.08的字元編碼為：1111
3.（7分）
答：使用散列函數H(key)=key mod 13 有：
H（12）=12， H（23）=10，H（45）=6，H（57）=5，H（20）=7，H（03）=3，H（78）=0，H（31）=5，H（15）=2，H（36）=10
利用線性探查法造表：
0 1 2 3 4 5 6 7 8 9 10 11 12
78 15 03 57 45 20 31 23 36 12
1 1 1 1 1 1 4 1 2 1
搜索成功的平均搜索長度為：
ASL=1/10（1+1+1+1+1+1+4+1+2+1）=14/10
4.（6分）
答： 希爾排序(增量為5,2,1)
六、演算法設計題（第1小題10分，第2小題8分）
1. (10分)
include <iostream.h>
include」string.h」
int charnumber=128;
void frequency(string&s,int C[ ]){
for(int i=0;i< charnumber;i++) C[i]=0;
for( i=0;i< s.length();i++) C[atoi(s[i])]++;
for( i=0;i< charnumber;i++)
if(C[i]>0) cout<<」(」<<i<<」):\t」<<C[i]<<」\t」;
}
2. (8分)
類型定義（略）
int Level(BiTree bt) //層次遍歷二叉樹，並統計度為1的結點的個數
{
int num=0; //num統計度為1的結點的個數
if(bt){
QueueInit(Q); QueueIn(Q,bt)；//Q是以二叉樹結點指針為元素的隊列
while(!QueueEmpty(Q))
{ p=QueueOut(Q); printf(p->data); //出隊,訪問結點
if(p->lchild && !p->rchild ||!p->lchild && p->rchild)
num++;//度為1的結點
if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入隊
if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入隊
}
}
return(num); //返回度為1的結點的個數
}
B：
06－07第一學期期末考試試卷
試卷代碼：03266B 授課課時：112
課程名稱：數據結構與演算法 適用對象：本科
一、單項選擇題(從下列各題四個備選答案中選出一個正確答案，並將其代號寫在答題紙相應位置處。答案錯選或未選者，該題不得分。每小題2分，共24分。)
1.數據結構被形式地定義為 (K, R)，其中K是____的有限集，R是K上的關系有限集。
A.演算法 B.數據元素 C.數據操作 D.邏輯結構
2.在數據結構中，從邏輯上可以把數據結構分成____。
A.動態結構和靜態結構 B.緊湊結構和非緊湊結構
C.線性結構和非線性結構 D.內部結構和外部結構
3.以下的敘述中，正確的是____。
A.線性表的存儲結構優於鏈式存儲結構
B.二維數組是其數據元素為線性表的線性表
C.棧的操作方式是先進先出
D.隊列的操作方式是先進後出
4.若一個棧的入棧序列是1、2、3、… 、n，其輸出序列為p1、p2、p3、… 、pn，若p1=n，則pi為____。
A. i B. n = i C. n - i +1 D.不確定
5.判斷一個循環隊列QU (最多元素為m) 為空的條件是____。
A. QU->front == QU->rear B. QU->front != QU->rear
C. QU->front == (QU->rear+1)%m D. QU->front != (QU->rear+1)%m
6.在某單鏈表中，已知p所指結點不是最後結點，在p之後插入s所指結點，則執行____。
A. s->next = p; p->next=s; B. s->next = p->next; p->next = s;
C. s->next = p->next; p = s; D. p->next = s; s->next = p;
7.串是一種特殊的線性表，其特殊性體現在____。
A.可以順序存儲 B.數據元素是一個字元
C.可以鏈接存儲 D.數據元素可以是多個字元
8.已知某二叉樹的後序遍歷序列是dabec，中序遍歷序列是debac，前序遍歷序列是____。
A. acbed B. decab C. deabc D. cedba
9.對於一個滿二叉樹，m個樹葉，n個結點，深度為h，則____。
A. n = h + m B. h + m = 2n C. m = h-1 D. n = 2h -1
10.一個有n個頂點的無向圖最多有____條邊。
A. n B. n(n-1) C. n(n-1)/2 D. 2n
11.順序查找法適合於存儲結構為____的線性表。
A. 散列存儲 B. 順序存儲或鏈接存儲
C. 壓縮存儲 D. 索引存儲
12.在待排序的元素序列基本有序的前提下，效率最高的排序方法是____。
A. 插入排序 B.選擇排序 C.快速排序 D. 歸並排序
二、填空題(請在每小題的橫線上填入正確內容，每空1分，共7分。)
1.在線性結構中，第一個結點 前驅結點，其餘每個結點有且只有1個前驅結點。
2.在無權圖G的鄰接矩陣中，若A[i][j]等於1，則等於A[j][i] = 。
3.根據二叉樹的定義，具有三個結點的二叉樹有 種不同的形態。
4.空格串是指 ，其長度等於 。
5.在散列存儲中，裝填因子α的值越大，則存儲元素時發生沖突的可能性就 。
6.已知模式串t= 『abacabaaad』， 其用KMP法求得的每個字元對應的next函數值為 。
三、簡答題(本大題共3小題，每小題5分，共15分)
1.比較靜態查找與動態查找的主要區別，它們的基本運算有哪些不同？
2.邏輯結構分哪幾種，存儲結構有哪幾種？
3.在具有n(n>1)個結點的各棵不同形態樹中，其中深度最小的那棵樹的深度是多少？它共有多少葉子和非葉子結點？
四、判斷題(本大題共10小題，命題正確的在題後括弧內寫 「T」，錯誤的在題後括弧內寫「F」，每小題1分，共10分)
1.每種數據結構都應具備三種基本運算：插入、刪除、搜索( )。
2.滿二叉樹不一定是完全二叉樹。( )
3.帶權連通圖的最小生成樹的權值之和一定小於它的其它生成樹的權值之和。( )
4.任一棵二叉搜索樹的平均搜索時間都小於用順序搜索法搜索同樣結點的順序表的平均搜索時間。( )
5.線性鏈表中所有結點的類型必須相同。( )
6.用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所佔用的存儲空間大小隻與圖中頂點個數有關，而與圖的邊數無關( )。
7.在散列法中解決沖突時，其裝載因子的取值一定在(0，1)之間。( )
8.任何一個關鍵活動延遲，那麼整個工程將會延遲。( )
9.平衡二叉樹的左右子樹深度之差的絕對值不超過1。( )
10.n個結點的有向圖，若它有n(n－1)條邊，則它一定是強連通的。( )
五、分析應用題（本題共26分，1、4小題各6分，2、3小題各7分）
1.下述演算法的功能是什麼? （6分）
LinkList Demo(LinkList L)
{ // L 是無頭結點單鏈表
ListNode *Q,*P;
if(L&&L->next){
Q=L;
L=L->next;
P=L;
while (P->next) P=P->next;
P->next=Q; Q->next=NULL;
}
return L;
}
2.將給定的圖簡化為最小的生成樹，要求從頂點1出發。（7分）
3.設散列表為HT[13], 散列函數為 H (key) = key %13。用雙散列法解決沖突, 對下列關鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。再散列函數為 RH (key) = (7*key) % 10 + 1, 尋找下一個地址的公式為 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。畫出相應的散列表, 並計算等概率下搜索成功的平均搜索長度。（7分）
4.設待排序的排序碼序列為{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18},寫出使用快速排序法每趟排序後的結果。（6分）
六、演算法設計題（本題共18分，第1小題10分，第2小題8分）
1.試設計一個實現下述要求的查找運算函數Locate。設有一個帶表頭結點的雙向鏈表L， 每個結點有4個數據成員：指向前驅結點的指針llink、指向後繼結點的指針rlink，存放字元數據的成員data和訪問頻度freq。所有結點的freq 初始時都為0。每當在鏈表上進行一次Locate(L, x) 操作時，令元素值為x的結點的訪問頻度freq加1，並將該結點前移，鏈接到與它的訪問頻度相等的結點後面，使得鏈表中所有結點保持按訪問頻度遞減的順序排列，以使頻繁訪問的結點總是靠近表頭。(10分)
2.設一棵二叉樹以二叉鏈表為存貯結構，設計一個演算法將二叉樹中所有結點的左，右子樹相互交換。要求給出二叉鏈表的類型定義。(8分)
答案：
06－07第一學期
期末考試參考答案與評分標准
試卷代碼：03266B 授課課時：112
課程名稱：數據結構與演算法 適用對象：本科
一、單項選擇題(每小題2分，共24分。)
1. B 2. C 3. B 4. C 5. A 6. B
7. B 8. D 9. D 10.C 11. B 12. A
二、填空題(每空1分，共7分。)
1. 無
2. 1
3. 5
4. 串中字元全為空格 ， 空格的個數
5. 大
6. 0112123422 。
三、簡答題(本大題共5小題，每小題5分，共15分)
1．答：兩種查找方法最大的區別在於：
靜態查找方法不修改查找表；動態查找在查找不成功時，將結點插入查找表中，即有可能修改查找表；
靜態查找的基本運算有建表、查找和讀表元；動態查找除上述基本操作外還有初始化、插入和刪除操作；
2.答：根據數據元素之間關系的不同特性，通常有下列四類基本結構：(1)集合；(2)線性結構；(3)樹形結構；(4)圖狀結構或網狀結構。有兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。
3.答：深度最小的那棵樹的深度為2。對於這n個結點，除了一個根結點之外，其餘得n-1個結點均為葉子結點，故其深度為2。該樹葉子結點數為n-1，非葉子結點數為1。
四、判斷題(每小題1分，共10分)
1. (T) 2. (F) 3. (T) 4. (F) 5. (T)
6. (T) 7. (F) 8. (T) 9. (T ) 10.(T)
五、分析應用題（本題共26分，1、4小題各6分，2、3小題各7分）
1.（6分）
答：該演算法的功能是：將開始結點摘下鏈接到終端結點之後成為新的終端結點，而原來的第二個結點成為新的開始結點，返回新鏈表的頭指針。
2.（7分）
答:
3.（7分）
答：使用散列函數H(key)=key mod 13 有：
H（12）=12， H（23）=10，H（45）=6，H（57）=5，H（20）=7，H（03）=3，H（78）=0，H（31）=5，H（15）=2，H（36）=10
利用雙散列法造表：Hi =（Hi-1+RH(key)）%13, Hi =H(key)
0 1 2 3 4 5 6 7 8 9 10 11 12
78 15 03 57 45 20 31 36 23 12
1 1 1 1 1 1 3 5 1 1
搜索成功的平均搜索長度為：ASL =1/10（1+1+1+1+1+1+3+5+1+1）=16/10
4.（6分）
答：
六、演算法設計題（第1小題10分，第2小題8分）
1.(10分)
答：
(1) 定義鏈表結構
struct DoubleListNode {
char data ;
int freq;
DoubleListNode * llink, *rlink ;
};
初始時，所有結點的freq域的值都為0。
(2) 定義函數
DoubleListNode * locate ( DoubleListNode *f ; char &x ) {
DoubleListNode * p, *q;
p = f→rlink; /*跳過表頭結點*/
while ( p != NULL && p→data != x ) p = p→rlink; /*搜索*/
if ( p ) {
p→freq ++; q = p→llink;
p→rlink→llink = q; q→rlink = p→rlink; /*從鏈中摘下p*/
while ( q != f &&q→freq < p→freq ) q =q→llink;
p→llink = q;
p→rlink = q→rlink; q→rlink→llink = p;
q→rlink = p; /*在q後面插入p*/
}
return p;
}
2． (8分)
答：類型定義（略）
void exchange(BiTree bt)//將二叉樹bt所有結點的左右子樹交換
{
if(bt)
{ BiTree s；
s=bt->lchild; bt->lchild=bt->rchild; bt->rchild=s; //左右子女交換
exchange(bt->lchild); //交換左子樹上所有結點的左右子樹
exchange(bt->rchild); //交換右子樹上所有結點的左右子樹
}
}
2. 急需數據結構C語言版（清華大學出版社）的期末考試試題及答案
《數據結構》期末考試試卷（ A ）
一、 選擇題（每小題2分，共24分）
1．計算機識別、存儲和加工處理的對象被統稱為( A )
A.數據 B.數據元素
C.數據結構 D.數據類型
2．棧和隊列都是（ A ）
A．限制存取位置的線性結構 B．順序存儲的線性結構
C．鏈式存儲的線性結構 D．限制存取位置的非線性結構
3．鏈棧與順序棧相比，比較明顯的優點是( D )
A.插入操作更加方便 B.刪除操作更加方便
C.不會出現下溢的情況 D.不會出現上溢的情況
4．採用兩類不同存儲結構的字元串可分別簡稱為( B )
A.主串和子串 B.順序串和鏈串
C.目標串和模式串 D.變數串和常量串
5． 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是：B
A. 110 B .108
C. 100 D. 120
6．串是一種特殊的線性表，其特殊性體現在：B
A.可以順序存儲 B .數據元素是一個字元
C. 可以鏈接存儲 D. 數據元素可以是多個字元
7．設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數至少為： C
A. 2h B .2h-1
C. 2h+1 D. h+1
軟體開發網
8．樹的基本遍歷策略可分為先根遍歷和後根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和後序遍歷。這里，我們把 由樹轉化得到的二叉樹叫做這棵樹對應的二叉樹。下列結論哪個正確？ A
A. 樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同
B .樹的後根遍歷序列與其對應的二叉樹的後序遍歷序列相同
C. 樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同
D. 以上都不對
9．一個有n個頂點的無向圖最多有多少邊？C
A. n B .n(n-1)
C. n(n-1)/2 D. 2n
10．在一個圖中，所有頂點的度數之和等於所有邊數的多少倍?C
A. 1/2 B .1
C. 2 D. 4
11．當在二叉排序樹中插入一個新結點時，若樹中不存在與待插入結點的關鍵字相同的結點，且新結點的關鍵字小於根結點的關鍵字，則新結點將成為（ A ）
A．左子樹的葉子結點 B．左子樹的分支結點
C．右子樹的葉子結點 D．右子樹的分支結點
軟體開發網
12．對於哈希函數H(key)=key%13,被稱為同義詞的關鍵字是( D )
A.35和41 B.23和39
C.15和44 D.25和51
二、已知某棵二叉樹的前序遍歷結果為A,B,D,E,G,C,F,H,I,J，其中中序遍歷的結果為D,B,G,E,A,H,F,I,J,C。請畫出二叉的具體結構。（注意要寫出具體步驟）（10分）
原理見課本128頁
三、有圖如下，請寫出從頂點c0出發的深度優先及寬度優先遍歷的結果。(10分)
深度優先；C0-C1-C3-C4-C5-C2
寬度優先：C0-C1-C2-C3-C4-C5
四、有圖如下，按Kruskal演算法求出其最小生成樹。要求寫出完整的步驟。（10分）
原理見課本250頁
五、給定線性表（12，23，45，66，76，88，93，103，166），試寫出在其上進行二分查找關鍵字值12，93，166的過程。並寫出二分查找的演算法。（20分）
0 1 2 3 4 5 6 7 8
12 23 45 66 76 88 93 103 166
過程：
mid=(0+8)/2=4
high=3,low=0 mid=1
high=0,low=0 mid=0（找到12）
high=8,low=5,mid=6（找到93）
high=8,low=7,mid=7
high=8 low=8 mid=8
演算法：見課本84頁上
六、知單鏈表的結點結構為
Data next
下列演算法對帶頭結點的單鏈表L進行簡單選擇排序，使得L中的元素按值從小到大排列。
請在空缺處填入合適的內容，使其成為完整的演算法。 (可用文字說明該演算法的基本思想及執行的過程，10分)
void SelectSort(LinkedList L)
{
LinkedList p,q,min;
DataType rcd;
p= (1) ;
while(p!=NULL) {
min=p;
q=p->next;
while(q!=NULL){
if( (2) )min=q;
q=q->next;
}
if( (3) ){
rcd=p->data;
p->data=min->data;
min->data=rcd;
}
(4) ;
}
}
本題不會。嘿嘿。。。。
七、一個完整的演算法應該具有哪幾個基本性質？分別簡要說明每一性質的含意。(5分)
輸入：
四個基本性質：1.輸入：有零個或多個有外部提供的量作為演算法的輸入
2：輸出：演算法產生至少一個量作為輸出
3.：確定性：組成演算法的每條指令是清晰的，無歧異的。
4.：有限性：演算法中每條指令的執行次數是有限的，執行每條指令的時間也是有限的
八、何謂隊列的"假溢"現象？如何解決？（5分）
隊列的假溢現象是指數組實現的順序隊列中，隊尾指針已到達數組的下表上界產生上溢而隊頭指針之前還有若干 空間閑置的現象。解決的辦法之一是利用循環隊列技術使數組空間的首尾相連。
九、說明並比較文件的各種物理結構。（6分）
3. 中國海洋大學研一往年演算法分析與設計期末考試試題
中國海洋大學相關信息，
可詢問學校研究生院。
只要努力付出過，
就會有收獲。
4. 安徽工業大學 演算法設計與分析試卷
中華人民共和國教育部 頒發 的 < 國家獎學金榮譽證書> 教育部部長 簽章 ！！！ 另外大學 還用 水晶 做出 獎杯 刻上 人名！！！
5. 《演算法設計與分析》。求大神幫幫忙。選擇題
這個看上去就是普通的數學題吧，因為x(1)=0，根據條件可知x(2)=5，所以只有選項D符合題意。另外感覺這個題和演算法沒有太大關系。。。