1．簡述順序存儲結構和鏈式存儲結構的特點
答：順序存儲結構的優點無需為表示元素間的邏輯關系而增加額外的指針空間；可以隨機存取表中的任壹元素。缺點是必須事先進行空間分配，表的容量難以擴充；插入和刪除操作時需移動大量結點，效率較低。
鏈式存儲結構的優點是結點的存儲采用動態存儲，表的容量很容易擴充；插入和刪除操作方便，不必移動結點，只要修改結點中的指針即可。缺點是每個結點中需要有指針空間，比順序存儲結構的存儲密度小；只能進行順序查找結點。
2．鏈表中為何要引入頭結點？
答：鏈表進行插入和刪除操作時要判斷是否在鏈表的首端操作，若在第壹結點前插入新結點和刪除第壹個結點則會引起首指針head值的改變；否則head的值不會改變。在鏈表前加壹個頭結點（只用指針域指向鏈表的首結點）就避免了兩種情況的判斷，使程序設計簡單了，程序的結構更清楚。
2． 簡述由二叉樹的前序、中序和後序遍歷序列確定二叉樹
答：在三種遍歷序列中，前序序列和中序序列、中序序列和後序序列能唯壹確定壹棵二叉樹，因為前序序列或後序序列能確定二叉樹的根結點而中序序列能確定根的左、右子樹。前序序列和後序序列不能唯壹確定壹棵二叉樹，但註意樹的先根序列和後根序列能唯壹的確定該樹，因為樹的後根序列就是二叉樹的中序序列。
4．快速排序最壞情況的改進
答：當待排序的序列為有序序列時快速排序的效率很低，蛻變為冒泡排序了，為了避免這種情況，選序列的首元素為樞軸元素（或稱基準元素）改為選序列的首元素、中間元素和末元素三個元素中中間大的元素為基準元素（簡單的就用中間元素為基準），這可大大改善快速排序的性能。例如：
8，0，4，9，6，3，5，2，7，1
以中間大元素6為基準，基準元素與最後元素交換後為：
8，0，4，9，1，3，5，2，7，6
↑ ↑
i j
將i,j指的內容比較，若i的內容比基準小，i推進，否則i停下，開始進行j的比較；若j的內容比基準大，j推進,，否則j停下，將i的內容與j的內容交換，重復上述過程，直至j<I< SPAN>止，將基準與i的內容交換，壹次分段完成。,如下所示：
8，0，4，9，1，3，5，2，7，6
2，0，4，9，1，3，5，8，7，6
2，0，4，5，1，3，9，8，7，6
2，0，4，5，1，3，6，8，7，9
5．簡述動態規劃法的基本思想
答：為了節約重復求相同子問題的時間，引入壹個表（數組），不管它們是否對最終解有用，把新的子問題的解答存於該表中，待以後遇到同樣子問題時，就不再重復求該子問題，而直接從表中取出該子問題的解答，這就是動態規劃法所采用的基本思想。
（四）選擇題
1．循環隊列用數組A[0…m-1]存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列中的元素個數是 。
A．(rear-front+m)% m B．read-front+1
C．read-front-1 D．read-front
n 參考答案 A
2．遞歸算法的執行過程壹般來說，可分成 (1) 和 (2) 兩個階段。
(1)A．試探 B．遞推 C．枚舉 D．分析
(2)A．回溯 B．回歸 C．返回 D．合成
n 參考答案 (1) B (2) B
3．設哈希表長m=11，哈希函數H（key）=key%11。表中已有4個結點：addr（15）=4， addr（38）=5，addr（61）=6，addr（84）=7，其余地址為空，如果二次探測再散列處理沖突，關鍵字為49的結點地址是 。
A．8 B．3 C．5 D．9
n 參考答案 D
4．m階B-樹中所有非終端（除根之外）節點中的關鍵字個數必須大於或等於 。
A． －1 B． +1 C． －1 D．m
n 參考答案 C
5．壹組記錄的關鍵碼為（46，79，56，38，40，84），則采用快速排序的方法，以第壹個記錄為基準得到的壹次劃分結果為 。
A．38，40，46，56，79，84 B．40，38，46，79，56，84
C．40，38，46，56，79，84 D．40，38，46，84，56，79
n 參考答案 C
6．若壹個問題的求解既可以用遞歸算法，也可以用遞推算法，則往往用 (1) 算法，因為 (2) 。
（1）A．先遞歸後遞推 B．先遞推後遞歸 C．遞歸 D．遞推
（2）A．遞推的效率比遞歸高 B．遞歸宜於問題分解
C．遞歸的效率比遞推高 D．遞推宜於問題分解
n 參考答案 （1）D （2）A
7．將壹棵有100節點的完全二叉樹從上到下、從左到右依次對結點進行編號，根結點的編號為1，則編號為49的結點的左孩子編號為 。
A． 99 B．98 C．50 D．48
n 參考答案 B
8．二叉樹在線索化後，仍不能有效求解的問題是 。
A．前序線索二叉樹中求前序後繼 B．中序線索二叉樹中求中序後繼
C．中序線索二叉樹中求中序前趨 D．後序線索二叉樹中求後序後繼
n 參考答案 D
9．判斷線索二叉樹中某結點P有左孩子的條件是 （1） 。若由森林轉化得到的二叉樹是非空的二叉樹，則二叉樹形狀是 （2） 。
（1）A．P！=null B．P->lchild！=null C．P->ltag=0 D．P->ltag=1
（2）A．根結點無右子樹的二叉樹 B．根結點無左子樹的二叉樹
C．根結點可能有左子樹和右子樹 D．各結點只有壹個孩子的二叉樹
n 參考答案 （1）C （2）C
10．在壹個單鏈表head中，若要在指針p所指結點後插入壹個q指針所指結點，則執行_____。
A． p->next=q->next; q->next=p;
B． q->next=p->next; p=q;
C． p->next=q->next; p->next=q;
D． q->next=p->next; p->next=q;
n 參考答案 D
11．設二維數組a[0…m-1][0…n-1]按列優先順序存儲在首地址為loc(a[0][0])的存儲區域中，每個元素占d個單元，則a[i][j]的地址為________。
A． loc(a[0][0]) +(j×n+i) ×d B． loc(a[0][0]) +(j×m+i) ×d
C．loc(a[0][0]) +((j-1)×n+i-1) ×d D． loc(a[0][0]) +((j-1)×m+i-1) ×d
n 參考答案 B
12．如果壹個棧的進棧序列是1,2,3,4且規定每個元素的進棧和退棧各壹次,那麽不可能得到的退棧序列_____。
A 4,3,2,1 B 4,2,1,3 C 1,3,2,4 D 3,4,2,1
n 參考答案 B
13．對n個元素進行快速排序時，最壞情況下的時間復雜度為 。
A．O（log2n） B．O（n） C．O（nlog2n） D．O（n2）
n 參考答案 D
14．任何壹個基於“比較”的內部排序的算法，若對6個元素進行排序，則在最壞情況下所需的比較次數至少為 。
A．10 B．11 C ．21 D．36
n 參考答案 A
四、模擬試題
1．二叉樹的前序、中序和後序遍歷法最適合采用 （1） 來實現。
查找樹中，由根結點到所有其它結點的路徑長度的總和稱為 （2） ，而使上述路徑長度總和達到最小的樹稱為 （3） 。它壹定是 （4） 。
在關於樹的幾個敘述中，只有 （5） 是正確的。
（1）A．遞歸程序 B．叠代程序 C．隊列操作 D．棧操作
（2）A．路徑和 B．內部路徑長度 C．總深度 D．深度和
（3）A．B-樹 B．B+樹 C．豐滿樹 D．穿線樹
（4）A．B-樹 B．平衡樹 C．非平衡樹 D．穿線樹
（5）A．用指針方式存儲有n個結點的二叉樹，至少要有n+1個指針
B．m階B-樹中，每個非葉子結點的後件個數≥
C．m階B-樹中，具有k個後件的結點，必含有k-1個鍵值
D．平衡樹壹定是豐滿樹
n 參考答案（1）A （2）B （3）C （4）B （5）C
2．壹棵查找二叉樹，其結點A、B、C、D、E、F依次存放在壹個起始地址為n（假定地址以字節為單位順序編號）的連續區域中，每個結點占4個字節：前二個字節存放結點值，後二個字節依次放左指針、右指針。若該查找二叉樹的根結點為E，則它的壹種可能的前序遍歷為 （1） ，相應的層次遍歷為 （2） 。在以上兩種遍歷情況下，結點C的左指針Lc的存放地址為 （3） ，Lc的內容為 （4） 。結點A的右指針Ra的內容為 （5） 。
（1）A．EAFCBD B．EFACDB C．EABCFD D．EACBDF
（2）A．EAFCBD B．EFACDB C．EABCFD D．EACBDF
（3）A．n+9 B．n+10 C．n+12 D．n+13
（4）A．n+4 B．n+8 C．n+12 D．n +16
（5）A．n+4 B．n+8 C．n+12 D．n +16
n 參考答案 （1）D （2）A （3）B （4）A （5）B
3．對於給定的壹組關鍵字（12，2，16，30，8，28，4，10，20，6，18），按照下列算法進行遞增排序，寫出每種算法第壹趟排序後得到的結果：希爾排序（增量為5）得到 （1） ，快速排序（選第壹個記錄為基準元素）得到 （2） ，基數（基數為10）排序得到 （3） ，二路歸並排序得到 （4） ，堆排序得到 （5） 。
（1）A．2,4,6,8,10,12,16,18,20,28,30 B．6,2,10,4,8,12,28,30,20,16,18
C．12,2,10,20,6,18,4,16,30,8,28 D．30,10,20,12,2,4,16,6,8,28,18
（2）A．10,6,18,8,4,2,12,20,16,30,28 B．6,2,10,4,8,12,28,30,20,16,18
C．2,4,6,8,10,12,16,18,20,28,30 D．6,10,8,28,20,18,2,4,12,30,16
（3）A．10,6,18,8,4,2,12,20,16,30,28 B．1,12,10,20,6,18,4,16,30,8,28
C．2,4,6,8,10,12,16,18,20,28,30 D．30,10,20,12,2,4,16,6,8,28,18
（4）A．2,12,16,8,28,30,4,6,10,18,20 B．2,12,16,30,8,28,4,10,6,20,18
C．12,2,16,8,28,30,4,6,10,28,18 D．12,2,10,20,6,18,4,16,30,8,28
（5）A．30,28,20,12,18,16,4,10,2,6,8 B．20,30,28,12,18,4,16,10,2,8,6
C．2,6,4,10,8,28,16,30,20,12,18 D．2,4,10,6,12,28,16,20,8,30,18
n 參考答案 （1）C （2）B （3）D （4）B （5）C
4．在所有排序方法中，關鍵字比較的次數與記錄的初始排列次序無關的是 （1） 。
從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為 （2） 。設有1000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最好選用 （3） 排序法。
（1）A．希爾排序 B．起泡排序 C．插入排序 D．選擇排序
（2）A．希爾排序 B．起泡排序 C．插入排序 D．選擇排序
（3）A．起泡排序 B．快速排序 C．堆排序 D．基數排序
n 參考答案 （1）D （2）C （3）C
5．用某種排序方法對線性表（25,84,21,47,15,27,68,35,20）進行排序時,元素序列的變化情況如下：
①25,84,21,47,15,27,68,35,20 ②20,15,21,25,47,27,68,35,84
③15,20,21,25,35,27,47,68,84 ④15,20,21,25,27,35,47,68,84
則所采用的排序方法是 （1） 。下列（2）中不穩定的排序是 （2） 。
外排序是指 （3） 。
（1）A．選擇排序 B．希爾排序 C．歸並排序 D．快速排序
（2）A．直接插入排序 B．冒泡排序 C．Shell排序 D．歸並排序
（3）A．用機器指令直接對硬盤中需排序數據排序
B． 把需排序數據，用其它大容量機器排序
C． 把外存中需排序數據壹次性調入內存，排好序後再存儲外存
D．對外存中大於內存允許空間的待排序的數據，通過多次內外間的交換實現排序。
n 參考答案 (1) D (2) C （3）D
6．在內部排序中，通常要對被排序數據進行多次掃描。各種排序方法有不同的排序實施過程和時間復雜性。對給定的整數數列（541,132,984,746,518,181,946,314,205,827）進行從小到大的排序時,采用冒泡排序和簡單選擇排序時,若先選出大元素,則第壹次掃描結果分別是 （1） 采用快速排序（以中間元素518為基準）的第壹次掃描結果是 （2） 。
設被排序的序列有n個元素，冒泡排序和簡單選擇排序的時間復雜度是 （3） ；快速排序的時間復雜度是 （4） 。
（1）
A．(181,132,314,205,541,518,946,827,746,984）和（541,132,827,746,518,181,946,314,205,984）
B．（132,541,746,518,181,946,314,205,827,984）和（541,132,827,746,518,181,946,314,205,984）
C．（205,132,314,181,518,746,946,984,541,827）和（132,541,746,518,181,946,314,205,827,984）
D．(541,132,984,746,827,181,946,314,205,518）和（132,541,746,518,181,946,314,205,827,984）
（2）A．（181,132,314,205,541,518,946,827,746,984）
B．（541,132,827,746,518,181,946,314,205,984）
C．（205,132,314,181,518,746,946,984,541,827）
D．(541,132,984,746,827,181,946,314,205,518）
（3）A．O(nlog2n) B．O(n) C．log2n D．O(n2)
（4）A．O(nlog2n) B．O(n2log2n) C．O(log2n) D．O(n2)
n 參考答案 （1）B （2）C （3）D （4）A
7．結定結點的關鍵字序列（F、B、J、G、E、A、I、D、C、H），對它按字母的字典順序進行排列，采用不同方法，其最終結果相同。但中間結果是不同的。
Shell排序的第壹趟掃描（步長為5）結果應為 （1） 。
冒泡排序（大數下沈）的第壹趟冒泡的效果是 （2） 。
快速排序的第壹次掃描結果是 （3）
二路歸並排序的第壹趟結局是 （4） 。
若以層次序列來建立對應的完全二叉樹後，采用篩選法建堆，其第壹趟建的堆是 （5） 。
（1）A．（B、F、G、J、A、D、I、E、H、C）
B．（B、F、G、J、A、E、D、I、C、H）
C．（A、B、D、C、E、F、I、J、G、H）
D．（C、B、D、A、E、F、I、G、J、H）
（2）A．（A、B、D、C、F、E、I、J、H、G）
B．（A、B、D、C、E、F、I、H、G、J）
C．（B、F、G、E、A、I、D、C、H、J）
D．（B、F、G、J、A、E、D、I、C、H）
（3）A．（C、B、D、A、F、E、I、J、G、H）
B．（C、B、D、A、E、F、I、G、J、H）
C．（B、A、D、E、F、G、I、J、H、C）
D．（B、C、D、A、E、F、I、J、G、H）
（4）A．（B、F、G、J、A、E、D、I、C、H）
B．（B、A、D、E、F、G、I、J、H、C）
C．（A、B、D、C、E、F、I、J、G、H）
D．（A、B、D、C、F、E、J、I、H、G）
（5）
n 參考答案 （1）C （2）C （3）B （4）A （5）B
8．二叉樹 （1） 。在完全二叉樹中，若壹個結點沒有 （2） ，則它必定是葉結點。每棵樹都能唯壹地轉換成與它對應的二叉樹。由樹轉換成的二叉樹裏，壹個結點N的左子樹是N在原樹裏對應結點的 （3） ，而N的右子樹是它在原樹裏對應結點的 （4） 。二叉排序樹的平均檢索長度為 （5） 。
（1）A．是特殊的樹 B．不是樹的特殊形式
C．是兩棵樹的總稱 D．是只有二個根結點的樹形結構
（2）A．左子樹 B．右子樹 C．左子樹或沒有右子樹 D．兄弟
（3）～(4)A．最左子樹 B．最右子樹 C．最鄰近的右兄弟 D．最鄰近的左兄弟
（5）A．O(n2) B．O(n) C．O(log2n) D．O(nlog2n)
n 參考答案 （1）B （2）A （3）A （4）C （5）C
9．哈希存儲的基本思想是根據 （1） 來決定 （2） ，沖突（碰撞）指的是 （3） ， __(4)___越大，發生沖突的可能性也越大。處理沖突的兩種主要方法是 （5） 。
（1）～（2）A．存儲地址 B．元素的序號 C．元素個數 D．關鍵碼值
（3） A．兩個元素具有相同序號 B．兩個元素的關鍵碼值不同，而非碼屬性相同
C．不同關鍵碼值對應到相同的存儲地址 D．數據元素過多
（4） A．非碼屬性 B．平均檢索長度 C．負載因子 D．哈希表空間
（5） A．線性探查法和雙散列函數法 B．建溢出區法和不建溢出區法
C．除余法和折疊法 D．拉鏈法和開放地址法
n 參考答案 （1）D （2）A （3）C （4）C （5）D
10． 設二維數組F的行下標為1至5，列下標為0至8，F的每個數據元素均占4個字節。在按行存儲的情況下，已知數據元素F[2，2]的第壹個字節的地址是1044，則F[3，4]和F[4，3]的第壹個字節的地址分別為 （1） 和 （2） ，而數組的第壹個數據元素的第壹個字節和數組最後壹個元素的最後壹個字節的地址分別為 （3） 和 （4） 。
對壹般的二維數組G而言，當 （5） 時，其按行存儲的G[I，J]的地址與按列存儲的G[J，I]的地址相同。
（1）A．1088 B． 1084 C．1092 D．1120
（2）A．1092 B． 1088 C．1120 D．1124
（3）A．1004 B． 1044 C．1000 D．984
（4）A．1183 B． 1179 C．1164 D．1187
（5）A．G的列數與行數相同
B．G的列的上界與G的行的上界相同
C．G的列的上界與G的行的下界相同
D．G的列的上下界與G的行的上下界相同
n 參考答案 （1）A （2）C （3）C （4）B （5）D
11．某順序存儲的表格，其中有90,000個元素，已按關鍵字遞增有序排列，現假定對各個元素進行查找的概率是相同的，並且各個元素的關鍵字皆不相同。
用順序查找法查找時，平均比較次數約為 (1) ，最大比較次數為 (2) 。
現把90,000個元素按排列順序劃分成若幹組，使每組有g個元素（最後壹組可能不足g個）。查找時，先從第壹組開始，通過比較各組的最後壹個元素的關鍵字，找到欲查找的元素所在的組，然後再用順序查找法找到欲查找的元素。在這種查找法中，使總的平均比較次數最小的g是 (3) ，此時的平均比較次數是 (4) 。當g的值大於等於90,000時，此方法的查找速度接近於 (5) 。
(1)～(2) A. 25,000 B. 30,000 C. 45,000 D. 90,000
(3)～(4) A. 100 B. 200 C. 300 D. 400
(5) A. 快速分類法 B. 斐波那契查找法 C. 二分法 D. 順序查找法
n 參考答案 （1）C （2）D （3）C （4）C （5）D
12．已知無向圖的鄰接表如圖2-35所示：
此鄰接表對應的無向圖為 (1) 。此圖從F開始的深度優先遍歷為 （2） 。從F開始的廣度優先遍歷為 （3） 。從F開始的深度優先生成樹為 （4） 。從F開始的廣度優先生成樹為 （5） 。
（1）
（2）A. F G I L J M K H B. F G I L J K H M
C. F G I L J K M H D. F G H M I L J K
（3）A. F G I L J K M H B. F G H M I L J K
C. F G H I L J K M D. F G H M K I L J
（4）
（5）
n 參考答案 （1）C （2）B （3）B （4）A （5）B
13．圖2-36是帶權的有向圖G的鄰接表。以結點V1出發深度遍歷圖G所得的結點序列為 （1） ；廣度遍歷圖G所得的結點序列為 （2） ；G的壹種拓撲序列是 （3） ；從結點V1到V8結點的最短路徑是 （4） ；從結點V1到V8結點的關鍵路徑是 （5） 。
（1）A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V3，V8，V4，V5，V6，V7
C. V1，V2，V3，V8，V4，V5，V7，V6 D. V1，V2，V3，V8，V5，V7，V4，V6
（2）A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V4，V6，V5，V3，V7，V8
C. V1，V2，V4，V6，V3，V5，V7，V8 D. V1，V2，V4，V6，V7，V3，V5，V8
（3）A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V4，V6，V5，V3，V7，V8
C. V1，V2，V4，V6，V3，V5，V7，V8 D. V1，V2，V4，V6，V7，V3，V5，V8
(4)～(5)A.( V1，V2，V4，V5，V3，V8) B. (V1，V6，V5，V3，V8)
C.( V1，V6，V7，V8) D. ( V1，V2，V5，V7，V8)
n 參考答案 （1）D （2）C （3）B （4）D （5）B
類似於這個吧 這也只是壹部分 全部已發到妳的郵箱