4、-1=1；
fn= fn-1+ fn-2+……+ fn-k, n=k,k+1,……
試編寫求k階斐波那契序列的第m項值的函數(shù)算法，k和m均以值調(diào)用的形式在函數(shù)參數(shù)表中出現(xiàn)。
第二章 線性表
思考題：
2.1 描述以下三個概念的區(qū)別：頭指針、頭結點、首元結點。
2.2 描述以下幾個概念：順序存儲結構、鏈式存儲結構、順序表、有序表。
作業(yè)題：
2.3 已知順序表La中數(shù)據(jù)元素按非遞減有序排列。試寫一個算法，將元素x插到La的合適位置上，保持該表的有序性。
2.4 已知單鏈表La中數(shù)據(jù)元素按非遞減有序排列。按兩種不同情況，分別寫出算法，將元素x插到La的合適位置上，保持該
5、表的有序性：（1）La帶頭結點；（2）La不帶頭結點。
2.5 試寫一個算法，實現(xiàn)順序表的就地逆置，即在原表的存儲空間將線性表（a1,a2, ..., an-1,an）逆置為(an,an-1, ..., a2,a1)
2.6 試寫一個算法，對帶頭結點的單鏈表實現(xiàn)就地逆置。
2.7 已知線性表L采用順序存儲結構存放。對兩種不同情況分別寫出算法，刪除L中值相同的多余元素，使得L中沒有重復元素：(1)L中數(shù)據(jù)元素無序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。
2.8 將2.7題中L的存儲結構改為單鏈表，寫出相應的實現(xiàn)算法。
2.9 設有兩個非遞減有序的單鏈表A和B。請寫出算法，將A和B“就地
6、”歸并成一個按元素值非遞增有序的單鏈表C。
2.10 設有一個長度大于1的單向循環(huán)鏈表，表中既無頭結點，也無頭指針，s為指向表中某個結點的指針,如圖2-1所示。試編寫一個算法，刪除鏈表中指針s所指結點的直接前驅。
s
待刪結點
圖2-1
2.11 已知線性表用帶頭結點的單鏈表表示，表中結點由三類字符組成：字母、數(shù)字和其他字符。試編寫算法，將該線性鏈表分割成三個循環(huán)單鏈表，每個循環(huán)單鏈表中均只含有一類字符。
2.12 已知線性表用順序存儲結構表示，表中數(shù)據(jù)元素為n個正整數(shù)。試寫一算法，分離該表中的奇數(shù)和偶數(shù)，使得所有奇數(shù)集中放在左側，偶數(shù)集中放在右側。要求：(1)不借助輔助數(shù)組;
7、(2)時間復雜度為O(n)。
2.13 設以帶頭結點的雙向循環(huán)鏈表表示的線性表L=(a1,a2,a3,...,an)。試寫一時間復雜度為O(n)的算法，將L改造為L=(a1,a3,...,an,...,a4,a2)。
第三章 棧和隊列
思考題：
3.1 簡述棧和線性表的差別。
3.2 如果進棧序列為A、B、C、D，寫出所有可能的出棧序列。
3.3 簡述棧和隊列的相同點和差異。
3.4 已知棧S中存放了8個數(shù)據(jù)元素，自棧底至棧頂依次為(1,2,3,4,5,6,7,8)。（1）寫出在執(zhí)行了函數(shù)調(diào)用algo1(S)后，S中的元素序列。
（2）在（1）的基礎上，又執(zhí)行了函數(shù)調(diào)用al
8、go2(S,5)，寫出此時S中的元素序列。
void algo1(Stack &S){
int a[10], i, n=0;
while(!StackEmpty(S)){ n++; Pop(S, a[n]); }
for(i=1; i<=n; i++) Push(S, a[i]);
}
void algo2(Stack &S, int e){
Stack T;
int d;
InitStack(T);
while(!EmptyStack(S)){
Pop(S,d);
if(d!=e)
9、 Push(T,d);
}
while(!StackEmpty(T)){
Pop(T,d);
Push(S,d);
}
}
3.5已知隊列Q中自隊頭至隊尾依次存放著(1,2,3,4,5,6,7,8)。寫出在執(zhí)行了函數(shù)調(diào)用algo3(Q)后，Q中的元素序列。
void algo3(Queue &Q){
Stack S;
int d;
InitStack(S);
while(!QueueEmpty(Q)){
DeQueue(Q,d); Push(S,d);
}
10、 while(!StackEmpty(S)){
Pop(S,d); EnQueue(Q,d);
}
}
作業(yè)題：
3.6 試寫一個算法，識別依次讀入的一個以@為結束符的字符序列是否為形如“序列1&序列2”模式的字符序列。其中，序列1和序列2中都不包含字符‘&’,且序列2是序列1的逆序。例如，“a+b&b+a”是屬于該模式的字符序列，而“1＋3&3－1”則不是。
3.7 假設一個算術表達式中可以包含三種符號：圓括號“(”和“)”、方括號“[”和“]”、花括號“{”和“}”，且這三種括號可按任意次序嵌套使用。編寫判別給定表達式中所含的括號是否正確配對的
11、算法（已知表達式已存入數(shù)據(jù)元素為字符的順序表中）。
3.8 設表達式由單字母變量、雙目運算符和圓括號組成（如:“(a*(b+c)-d)/e）”。試寫一個算法，將一個書寫正確的表達式轉換為逆波蘭式。
3.9 試用類C寫一個算法，對逆波蘭式求值。
3.10 假設以帶頭結點的單循環(huán)鏈表表示隊列，只設一個尾指針指向隊尾元素，不設頭指針。試編寫相應的隊列初始化、入隊和出隊的算法。
3.11 假設將循環(huán)隊列定義為：以rear和length分別指示隊尾元素和隊列長度。試給出此循環(huán)隊列的隊滿條件，并寫出相應的入隊和出隊算法（在出隊算法中要傳遞回隊頭元素的值）。
3.12 試寫一個算法：判別讀入的一個
12、以‘@’為結束符的字符序列是否是“回文”（所謂“回文”是指正讀和反讀都相同的字符序列，如“xxyzyxx”是回文，而“abcab”則不是回文）。
第五章 多維數(shù)組
5.1 已知多維數(shù)組A[2][2][3][3]按行優(yōu)先方式存儲。試按存儲位置的先后次序，列出所有數(shù)組元素A[i][j][k][l]序列（為了簡化表達，可以只列出形如“i,j,k,l”的序列，如元素A[0][0][2][1]可表示為“0,0,2,1” ）。
5.2 假設有一個二維數(shù)組A[0..5][0..7]，每個元素占6個字節(jié)，首元素A[0][0]的地址為1000，求：
(1)A的體積；
(2)最后
13、一個元素A[5][7]的地址；
(3)按行主序方式存儲時，A[2][4]的地址；
(4)按列主序方式存儲時，A[2][4]的地址；
5.3 設有上三角矩陣Ann，
將其上三角的元素逐行存于數(shù)組B[0..m-1]中（m充分大），使得B[k]=aij且k＝f1(i)+f2(j)+c。試推導出函數(shù)f1、f2和常數(shù)c（要求f1和f2中不含常數(shù)項）。
5.4 設有一個準對角矩陣
按以下方式存于一維數(shù)組B[4m]中：
0
1
2
3
4
5
6
k
4m-2
4m-1
a11
a12
a21
a22
a33
a34
a43
14、...
aij
...
a2m-1,2m
a2m,2m
寫出由一對下標(i,j)求k的轉換公式。
5.5 已知稀疏矩陣A45如下：
(1)用三元組表作為存儲結構，繪出相應的三元組表示意圖；
(2)用十字鏈表作為存儲結構，繪出相應的十字鏈表示意圖。
5.6 設稀疏矩陣A和B均以三元組順序表作為存儲結構。試寫出計算矩陣相加C＝A＋B的算法，其中，C是另設的、存放結果的三元組表（提示：可用類似于兩個有序順序表歸并的處理方法）。
5.7 試編寫一個算法，實現(xiàn)以三元組的形式打印用十字鏈表表示的稀疏矩陣中所有非零元素及其下標。
5.8 試編寫一個算法，實現(xiàn)以矩形陣列的形式打印用十
15、字鏈表表示的稀疏矩陣。
第六章 樹和二叉樹
6.1 試分別繪出具有3個結點的樹和3個結點的二叉樹的所有不同形態(tài)。
6.2 設結點X是二叉樹上一個度為1的結點，X有幾個子樹？
6.3 描述滿足下列條件的二叉樹形態(tài)：
(1) 先序遍歷序列與中序遍歷序列相同；
(2) 后序遍歷序列與中序遍歷序列相同；
(3) 先序遍歷序列與后序遍歷序列相同；
6.4 一個深度為H的滿k叉樹有如下性質：第H層上所有結點都是葉子結點，其余各層上每個結點都有k棵非空子樹。如果從1開始按自上而下、自左向右的次序對全部結點編號，問：
(1) 各層的結點數(shù)目是多少？
16、(2) 編號為i的結點的父結點(若存在)的編號是多少？
(3) 編號為i的結點的第j個孩子(若存在)的編號是多少？
(4) 編號為i的結點有右兄弟的條件是什么？其右兄弟的編號是多少？
6.5 已知一棵度為k的樹中有n1個度為1的結點，n2個度為2的結點，...，nk個度為k的結點，問該樹中有多少個葉子結點？
6.6 已知在一棵含有n個結點的樹中，只有度為k的分支結點和度為0的葉子結點。試求該樹含有的葉子結點的數(shù)目。
6.7 設n和m為二叉樹中兩個結點，用“1”、“0”、和“”（分別表示肯定，否定和不一定）填寫下表：
已知 問
先序遍歷時
n在m之前？
中序遍歷
17、時
n在m之前？
后序遍歷時
n在m之前？
n在m左方
1
1
1
n在m右方
0
0
0
n是m祖先
1
0
n是m子孫
0
1
（注：如果離n和m的最近的共同祖先X存在，且n位于X的左子樹中，m位于X的右子樹中，則稱“n在m的左方”或“m在n的右方”。）
6.8已知一棵樹如圖6-1所示，畫出與該樹對應的二叉樹，并寫出該樹的先根遍歷序列和后根遍歷序列。
A
B
C
D
E
F
G
H
K
I
J
圖6-1
6.9 將如圖6-2所示的森林轉化為對應的二叉樹。
K
圖6-2
A
C
D
E
B
F
18、G
H
J
I
L
M
N
O
6.10 畫出和下列二叉樹（如圖6-3所示）相應的森林。
圖6-3
A
B
C
C
A
B
C
A
B
A
D
E
B
C
F
G
H
J
K
L
I
6.11已知某二叉樹的中序序列為DCBGEAHFIJK，后序序列為DCEGBFHKJIA。請畫出該二叉樹。
6.12 已知樹T的先根遍歷訪問序列為GFKDAIEBCHJ，后根遍歷訪問序列為DIAEKFCJHBG。請畫出樹T。
6.13 已知森林F的先根遍歷訪問序列為ABCDEFGHIJKL，中根遍歷訪問序列為CBEFDGAJIKLH
19、。請畫出這個森林F。
6.14 假設某個電文由(a,b,c,d,e,f,g,h)8個字母組成，每個字母在電文中出現(xiàn)的次數(shù)分別為(7,19,2,6,32,3,21,10)，試解答下列問題：
(1) 畫出出huffman樹；
(2) 寫出每個字母的huffman編碼；
(3) 在對該電文進行最優(yōu)二進制編碼處理后，電文的二進制位數(shù)。
6.15 寫出復制一棵二叉樹的算法。
6.16 試編寫算法，實現(xiàn)將二叉樹所有結點的左右子樹互換。
6.17 寫出按層次遍歷二叉樹的算法。
6.18 寫出判斷給定二叉樹是否為完全二叉樹的算法。
6.19 寫出判斷兩棵給
20、定二叉樹是否相似的算法。
(注：兩棵二叉樹B1和B2相似是指：B1和B2皆空，或者皆不空且B1的左、右子樹和B2的左、右子樹分別相似。)
6.20 利用棧的基本操作，寫出二叉樹先序遍歷的非遞歸算法。
6.21 寫出統(tǒng)計樹中葉子結點個數(shù)的算法，樹用孩子兄弟鏈表表示。
6.22 寫出計算樹的深度的算法，樹用孩子兄弟鏈表表示。
6.23 寫出計算二叉樹第K層結點數(shù)的算法。
6.24 寫出計算二叉樹深度的算法。
圖7-1
V5
V4
V2
V3
V1
V6
第七章 圖
7.1 已知有向圖如圖7-1所示，
請給出該圖的
(1)鄰接矩陣示意圖
(
21、2)鄰接表示意圖
(3)逆鄰接表
(4)所有強連通分量
7.2 已知圖G的鄰接矩陣如圖7-2所示。寫出該圖從頂點1出發(fā)的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列，并畫出相應的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。
1
2
3
4
5
6
7
8
9
10
1
0
0
0
0
0
0
1
0
1
0
2
0
0
1
0
0
0
1
0
0
0
3
0
0
0
1
0
0
0
1
0
0
4
0
0
0
0
1
0
0
0
1
0
5
0
0
0
0
0
22、
1
0
0
0
1
6
1
1
0
0
0
0
0
0
0
0
7
0
0
1
0
0
0
0
0
0
1
8
1
0
0
1
0
0
0
0
1
0
9
0
0
0
0
1
0
1
0
0
1
10
1
0
0
0
0
1
0
0
0
0
圖7-2
7.3 無向帶權圖如圖7-3所示，
(1)畫出它的鄰接矩陣，并按Prim算法求其最小生成樹。
(2)畫出它的鄰接表，并按Kruskal算法求其最小生成樹
圖7-3
A
B
C
E
H
23、
F
D
G
4
3
5
5
5
5
9
7
4
5
6
6
2
3
7.4 有向圖如圖7-4所示，試寫出其所有可能的拓撲序列。
圖7-4
V1
V5
V2
V3
V6
V4
7.5 試利用Dijkstra算法求圖7-5中頂點A到其他各頂點之間的最短路徑。要求寫出執(zhí)行算法過程中，數(shù)組D、P和S各步的狀態(tài)。
G
A
B
D
C
E
F
圖7-5
15
12
2
5
6
8
4
9
10
4
3
7.6 試在鄰接矩陣存儲結構上實現(xiàn)圖的基本操作：InsertVex(G,v)，
InsertArc
24、(G,v,w), DeleteVex(G,v)和DeleteArc(G,v,w)。
7.7 試在鄰接表存儲結構上實現(xiàn)圖的基本操作：InsertVex(G,v)，
InsertArc(G,v,w), DeleteVex(G,v)和DeleteArc(G,v,w)。
7.8 設具有n個頂點的有向圖用鄰接表存儲。試寫出計算所有頂點入度的算法，可將每個頂點的入度值分別存入一維數(shù)組int Indegree[n]中。
7.9 假設有向圖以鄰接表作為存儲結構。試基于圖的深度優(yōu)先搜索策略寫一算法，判斷有向圖中是否存在由頂點Vi至頂點Vj(i!=j)的路徑。
7.10 假設有向圖以鄰接表作為存儲結構。
25、試基于圖的廣度優(yōu)先搜索策略寫一算法，判斷有向圖中是否存在由頂點Vi至頂點Vj(i!=j)的路徑。
7.11 以鄰接表作為存儲結構，實現(xiàn)求單源最短路徑的Dijkstra算法。
第九章 查找
9.1 若對大小均為n的有序順序表和無序順序表分別進行順序查找，試在下列三種情況下分別討論兩者在等概率時平均查找長度是否相同？
(1)查找不成功，即表中沒有關鍵字等于給的值K的記錄；
(2)查找成功，且表中只有一個關鍵字等于給定值K的記錄；
(3)查找成功，且表中有若干個關鍵字等于給定值K的記錄，要求找出所有這些記錄。
9.2 試分別寫出在對有序線性表(a,b,c,d,e
26、,f,g)中進行折半查找，查值等于e、f和g的元素時，先后與哪些元素進行了比較。
9.3 畫出對長度為13的有序表進行折半查找的判定樹，并分別求其等概率時查找成功和查找失敗的ASL。
9.4 已知如下所示長度為12的表：
(Jan, Feb, Mar, Apr, May, Jun, July, Aug, Sep, Oct, Nov, Dec)
表中，每個元素的查找概率分別為：
(0.1,0.25,0.05,0.13,0.01,0.06,0.11,0.07,0.02,0.03,0.1,0.07)
(1)若對該表進行順序查找，求查找成功的平均查找長度；
27、 (2)畫出從初態(tài)為空開始，依次插入結點，生成的二叉排序樹；
(3)計算該二叉排序樹查找成功的平均查找長度；
(4)將二叉排序樹中的結點Mar刪除，畫出經(jīng)過刪除處理后的二叉排序樹。
9.5已知關鍵字序列{10,25,33,19,06,49,37,76,60}，哈希地址空間為0～10，哈希函數(shù)為H (Key)=Key % 11, 求：
（1） 用開放定址線性探測法處理沖突，構造哈希表HT1，分別計算在等概率情況下HT1查找成功和查找失敗的ASL；
（2） 用開放定址二次探測法處理沖突，構造哈希表HT2，計算在等概率情況下HT2查找成功的ASL；
（3） 用拉鏈法解決沖
28、突，構造哈希表HT3，計算HT3在等概率情況查找成功的ASL。
9.6 寫出折半查找的遞歸算法。
9.7 寫出判別一棵二叉樹是否為二叉排序樹的算法，設二叉排序樹中不存在關鍵字值相同的結點。
9.8 假設哈希表長為m， 哈希函數(shù)為H(x)，用鏈地址法解決沖突。編寫輸入一組關鍵字，建造哈希表的算法。
第十章 內(nèi)部排序
10.1 以關鍵字序列（5，1，6，0，9，2，8，3，7，4）為例，手工執(zhí)行下列排序算法，寫出每一趟排序結束時關鍵字序列狀態(tài)
(1) 直接插入排序 (2) 希爾排序（取增量為5，3，1）
(3) 快速排序 (4) 冒泡排序
(5) 歸并排序 (6) 堆排序
10.2 10.1題中哪些排序方法是穩(wěn)定的，哪些是不穩(wěn)定的？并為每種不穩(wěn)定的排序方法舉一個不穩(wěn)定的實例。
10.3 判別以下序列是否為堆（小頂堆或大頂堆），若不是，則吧它調(diào)整為堆
(1) (96,86,48,73,35,39,42,57,66,21);
(2) (12,70,33,65,24,56,48,92,86,33);
10.4 編寫一個雙向起泡的排序算法，即相鄰兩遍向相反方向起泡。
10.5 試以單鏈表為存儲結構，實現(xiàn)簡單選擇排序算法。
數(shù)據(jù)結構習題集
