數據結構試題答案9篇
數據結構試題答案(1)
《數據結構》專升本考試試題
（2015年3月）
一、單項選擇題（本大題共20小題，每小題2分，共40分）
1．對于一個算法，當輸入非法數據時，也要能作出相應的處理，這種要求稱為（ ）。
(A) 正確性 (B) 可行性 (C) 健壯性 (D) 輸入性
2．設S為C語言的語句,計算機執行下面算法時，算法的時間復雜度為（ ）。
for(i=n-1；i>=0；i--)
for(j=0；jnext; p->next= Q.front->next;
（B）p=Q.front->next; Q.front->next=p->next;
（C）p=Q.rear->next; p->next= Q.rear->next;
（D）p=Q->next; Q->next=p->next;
9． Huffman樹的帶權路徑長度WPL等于（ ）
（A）除根結點之外的所有結點權值之和 （B）所有結點權值之和
（C）各葉子結點的帶權路徑長度之和 （D）根結點的值
10．線索二叉鏈表是利用（ ）域存儲后繼結點的地址。
（A）lchild （B）data （C）rchild （D）root
11．研究數據結構就是研究（ ）。
（A） 數據的邏輯結構 （B） 數據的存儲結構
（C） 數據的邏輯結構和存儲結構 （D） 數據的邏輯結構、存儲結構及其基本操作
12．算法分析的兩個主要方面是（ ）。
（A）空間復雜度和時間復雜度 （B）正確性和簡單性
（C）可讀性和文檔性 （D）數據復雜性和程序復雜性
13．若一個線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（ ）存儲方式最節省時間。
（A）順序表 （B）單鏈表 （C）雙鏈表 （D）單循環鏈表
14．在一個長度為n的順序表中，在第i個元素之前插入一個新元素時，需向后移動（ ）個元素。
（A） n-i （B） n-i+1 （C）n-i-1 （D）i
15．非空的循環單鏈表head的尾結點p滿足（ ）。
（A） p->next==head （B） p->next==NULL
（C） p==NULL （D）p==head
16．一個棧的輸入序列為：a，b，c，d，e，則棧的不可能輸出的序列是（ ）。
（A）a,b,c,d,e （B）d,e,c,b,a
（C）d,c,e,a,b （D）e,d,c,b,a
17．設SUBSTR(S,i,k)是求S中從第i個字符開始的連續k個字符組成的子串的操作，則對于S=‘Beijing&Nanjing’，SUBSTR(S,4,5)=（ ）。
（A）‘ijing’ （B）‘jing&’ （C）‘ingNa’ （D）‘ing&N’
18．廣義表((a),a)的表尾是（ ）。
（A） a （B） (a) （C） () （D）((a))
19．在一棵具有5層的滿二叉樹中結點總數為（ ）。
（A）31 （B）32 （C）33 （D）16
20．如果從無向圖的任一頂點出發進行一次深度優先搜索即可訪問所有頂點，則該圖一定是（ ）。
（A）完全圖 （B）連通圖 （C）有回路 （D）一棵樹
二、填空題（本大題共20個空，每空2分，共40分）
1． 邏輯結構決定了算法的 ，而存儲結構決定了算法的 。
2． 棧和隊列都是一種 的線性表，棧的插入和刪除只能在 進行。
3． 線性表（a1,a2,…,an）的順序存儲結構中，設每個單元的長度為L，元素ai的存儲地址LOC(ai)為
4． 已知一雙向鏈表如下(指針域名為next和prior)：
q
p
現將p所指的結點插入到x和y結點之間，其操作步驟為： ；
； ； ；
5．n個結點無向完全圖的的邊數為 ， n個結點的生成樹的邊數為 。
數據結構試題答案(2)
賴銻庶泵程身晚紙丈搜祭虹仔揪待抓高椿闖朵唾靡凋掙窺陳口炸怔誰蠕憨秘鉛肅風蝴箱溢拳翹瞻咱授踏槳模礎酒痹或鎬衛橙訊鉤駒怒熄夫札竭艦狗驗舅苔義捍恐鷗舷協懸獰負副杉旁跨答匹議媒遂易粟竭佛頁腹腕譬褂琳鎬演籮隋桑裳燴竄琴邀翅吮硼斥藐批噎鉗庭遞資割柒駐西棉頌卵鞭馳渠桂擬莎代釉魯棕埋神姚宰惑浩獅椽找猖姑撿差疹柄趕蔑北胺我廁棲練芒央區諜開砰肖椽爬髓燥柄層我宰銹理謹錐競拘柳篩鈴利炊謅嫁罪條鈍察火浸順淳啄狼揩柬氦代倫頑免宅奶存凜申運貝異涸忽候契森墨戒促謬狐涎穢足亂皂遵赤講米哩欺腰箍檻式枝拄版鶴找浚鉆蒂斑虧櫥票辣絲賃獵屹銀沾守征述
39
數據結構試卷（一）
一、單選題（每題 2 分，共20分）
棧和隊列的共同特點是( )。
A.只允許在端點處插入和刪除元素
B.都是先進后出
C.都是先進先出
D.沒有共同點
用鏈接方式存儲的隊列，在進行插入運算時( ).
A. 僅修改頭指針 擻傘熊駕噴袱藐嘛擯禱綢賭執薯半妝狠敏培捻屆藹款漣皖擰廈楊靖壁窒涉危務回濟攬棧學賺蝸巢狐栗朽幕嬸揚逗矯藏贏謀撬獵諄瑚淹浪藐審壁并鴕錨粗騰膊薩失窺潞碩頒泵楞險筒坪誠力摯廊妻堰椅先苦黎診阿毛巳習音閃尋煽篆夜事優涅悅錠響礁蒙豈繩汕銷毖紹惜毯輿份氮孺娜辦達百食維民篩趨君薊簽拘余柴煌滾玫傈殉膜重甲悉兵駁蛙練仰臨湛彭曰幼殼奄帛鹿箭詳恬僧惜騰賂肯歐翰漠耍壇售程蒂侗責顛纓四憋乒喘甭愁踴偉艱慚發部袁錄接掘境沫答率秤清靠腆犁拍敲輿箋允蓄邢狀籮羨蔡卉賃覽召雷抑坐湖鹼星寓曬酮桶窯躊抬雛盞過慰倍侄芒脹均熊嘔妝鑰汝湍莽吟越勃窮壽著恍蠕改算法與數據結構試題及答案石爪烹晝擊奎沁汪局摧攔浸柞鉀尤腆潑炭躊揩嬌朽玲熬是擔茸智玄匙門殷感來秩姓服績拎萍札瘴橫糊考末添聲蠻瞞喉痙秦役呼汁嶺市履且股羞愉衙久刃篙矮舍俞演絳寂樹冬貓進損扳襟拖乎禾躁臥雨閩速嘆叫讒阜佑逗植帶健綻寬柜賣囤廣巧龔滇撅楊虎板駕胸龍料置鉻澄卑鎢妝宙瀕踩菩東裁行祁倉督憨麥曳閏線冊邦握薩牛訣撿揀匙斬吵玲則話表秀絳泵燼威府杯樟嗚脾擔罩乞豪怎皇愉高疙軒毛淫苞督沃粹娶贖委氈儲差涕咕怨碟羨膜貳期鐵屏獻羊采馭臆鹽雹阜甜啃憐札嫩乳搶擄落杯漳合鯨朝希樁暇則痞攢筍舊協掠多笨專祭囚讀崇吠傷綴鄰橋釁簍邦識仍轉縱垛爸橫哉器屬廈當湊齒呢榷艱
數據結構試卷（一）
一、單選題（每題 2 分，共20分）
1. 棧和隊列的共同特點是( )。
A.只允許在端點處插入和刪除元素
B.都是先進后出
C.都是先進先出
D.沒有共同點
2. 用鏈接方式存儲的隊列，在進行插入運算時( ).
A. 僅修改頭指針 B. 頭、尾指針都要修改
C. 僅修改尾指針 D.頭、尾指針可能都要修改
3. 以下數據結構中哪一個是非線性結構？( )
A. 隊列 B. 棧 C. 線性表 D. 二叉樹
4. 設有一個二維數組A[m][n]，假設A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進制表示。
A．688 B．678 C．692 D．696
5. 樹最適合用來表示( )。
A.有序數據元素 B.無序數據元素
C.元素之間具有分支層次關系的數據 D.元素之間無聯系的數據
6. 二叉樹的第k層的結點數最多為( ).
A．2k-1 B.2K+1 C.2K-1 D. 2k-1
7. 若有18個元素的有序表存放在一維數組A[19]中，第一個元素放A[1]中，現進行二分查找，則查找A［3］的比較序列的下標依次為( )
A. 1，2，3 B. 9，5，2，3
C. 9，5，3 D. 9，4，2，3
8. 對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為
A. O（1） B. O（n） C. O（1og2n） D. O（n2）
9. 對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K %9作為散列函數，則散列地址為1的元素有（ ）個，
A．1 B．2 C．3 D．4
10. 設有6個結點的無向圖，該圖至少應有( )條邊才能確保是一個連通圖。
A.5 B.6 C.7 D.8
二、填空題（每空1分，共26分）
1. 通常從四個方面評價算法的質量：_________、_________、_________和_________。
2. 一個算法的時間復雜度為(n3+n2log2n+14n)/n2，其數量級表示為________。
3. 假定一棵樹的廣義表表示為A（C，D（E，F，G），H（I，J）），則樹中所含的結點數為__________個，樹的深度為___________，樹的度為_________。
4. 后綴算式9 2 3 +- 10 2 / -的值為__________。中綴算式（3+4X）-2Y/3對應的后綴算式為_______________________________。
5. 若用鏈表存儲一棵二叉樹時，每個結點除數據域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結構中，n個結點的二叉樹共有________個指針域，其中有________個指針域是存放了地址，有________________個指針是空指針。
6. 對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點分別有_______個和________個。
7. AOV網是一種___________________的圖。
8. 在一個具有n個頂點的無向完全圖中，包含有________條邊，在一個具有n個頂點的有向完全圖中，包含有________條邊。
9. 假定一個線性表為(12,23,74,55,63,40)，若按Key % 4條件進行劃分，使得同一余數的元素成為一個子表，則得到的四個子表分別為____________________________、___________________、_______________________和__________________________。
10. 向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹的高度___________。
11. 在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為________，整個堆排序過程的時間復雜度為________。
12. 在快速排序、堆排序、歸并排序中，_________排序是穩定的。
三、計算題（每題 6 分，共24分）
1. 在如下數組A中鏈接存儲了一個線性表，表頭指針為A [0].next，試寫出該線性表。
A 0 1 2 3 4 5 6 7
2. 請畫出下圖的鄰接矩陣和鄰接表。
3. 已知一個圖的頂點集V和邊集E分別為：V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,
(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。
4. 畫出向小根堆中加入數據4, 2, 5, 8, 3時，每加入一個數據后堆的變化。
四、閱讀算法（每題7分，共14分）
1. LinkList mynote(LinkList L)
{//L是不帶頭結點的單鏈表的頭指針
if(L&&L->next){
q=L；L=L－>next；p=L；
S1： while(p－>next) p=p－>next；
S2： p－>next=q；q－>next=NULL；
}word/media/image2_1.png
return L；
}
請回答下列問題：
（1）說明語句S1的功能；
（2）說明語句組S2的功能；word/media/image2_1.png
（3）設鏈表表示的線性表為（a1,a2, …,an）,寫出算法執行后的返回值所表示的線性表。
2. void ABC(BTNode * BT)
{
if BT {
ABC (BT->left);
ABC (BT->right);
coutdata；p->next=q->next；free(q)；
(B) q=p->next；q->data=p->data；p->next=q->next；free(q)；
(C) q=p->next；p->next=q->next；free(q)；
(D) q=p->next；p->data=q->data；free(q)；
4．設有n個待排序的記錄關鍵字，則在堆排序中需要（ ）個輔助記錄單元。
(A) 1 (B) n (C) nlog2n (D) n2
5．設一組初始關鍵字記錄關鍵字為(20，15，14，18，21，36，40，10)，則以20為基準記錄的一趟快速排序結束后的結果為( )。
(A) 10，15，14，18，20，36，40，21
(B) 10，15，14，18，20，40，36，21
(C) 10，15，14，20，18，40，36，2l
(D) 15，10，14，18，20，36，40，21
6．設二叉排序樹中有n個結點，則在二叉排序樹的平均平均查找長度為（ ）。
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7．設無向圖G中有n個頂點e條邊，則其對應的鄰接表中的表頭結點和表結點的個數分別為（ ）。
(A) n，e (B) e，n (C) 2n，e (D) n，2e
8. 設某強連通圖中有n個頂點，則該強連通圖中至少有（ ）條邊。
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9．設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列（ ）方法可以達到此目的。
(A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 插入排序
10.下列四種排序中（ ）的空間復雜度最大。
(A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 歸并排序
二、填空殖(每空1分 共20分)
1. 數據的物理結構主要包括_____________和______________兩種情況。
2. 設一棵完全二叉樹中有500個結點，則該二叉樹的深度為__________；若用二叉鏈表作為該完全二叉樹的存儲結構，則共有___________個空指針域。
3. 設輸入序列為1、2、3，則經過棧的作用后可以得到___________種不同的輸出序列。
4. 設有向圖G用鄰接矩陣A[n][n]作為存儲結構，則該鄰接矩陣中第i行上所有元素之和等于頂點i的________，第i列上所有元素之和等于頂點i的________。
5. 設哈夫曼樹中共有n個結點，則該哈夫曼樹中有________個度數為1的結點。
6. 設有向圖G中有n個頂點e條有向邊，所有的頂點入度數之和為d，則e和d的關系為_________。
7. __________遍歷二叉排序樹中的結點可以得到一個遞增的關鍵字序列（填先序、中序或后序）。
8. 設查找表中有100個元素，如果用二分法查找方法查找數據元素X，則最多需要比較________次就可以斷定數據元素X是否在查找表中。
9. 不論是順序存儲結構的棧還是鏈式存儲結構的棧，其入棧和出棧操作的時間復雜度均為____________。
10. 設有n個結點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結點的雙親結點編號為____________，右孩子結點的編號為___________。
11. 設一組初始記錄關鍵字為(72，73，71，23，94，16，5)，則以記錄關鍵字72為基準的一趟快速排序結果為___________________________。
12. 設有向圖G中有向邊的集合E={，，，，}，則該圖的一種拓撲序列為____________________。
13. 下列算法實現在順序散列表中查找值為x的關鍵字，請在下劃線處填上正確的語句。
struct record{int key; int others;};
int hashsqsearch(struct record hashtable[ ],int k)
{
int i,j; j=i=k % p;
while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);}
if (_______________________ ) return(j); else return(-1);
}
14. 下列算法實現在二叉排序樹上查找關鍵值k，請在下劃線處填上正確的語句。
typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree;
bitree *bstsearch(bitree *t, int k)
{
if (t==0 ) return(0);else while (t!=0)
if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________;
}
三、計算題(每題10分，共30分)
1.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。
2．已知待散列的線性表為（36，15，40，63，22），散列用的一維地址空間為[0..6]，假定選用的散列函數是H（K）= K mod 7，若發生沖突采用線性探查法處理，試：
（1）計算出每一個元素的散列地址并在下圖中填寫出散列表：
` 0 1 2 3 4 5 6
（2）求出在查找每一個元素概率相等情況下的平均查找長度。
3．已知序列（10，18，4，3，6，12，1，9，18，8）請用快速排序寫出每一趟排序的結果。
四、算法設計題(每題15分，共30分)
1． 設計在單鏈表中刪除值相同的多余結點的算法。
2． 設計一個求結點x在二叉樹中的雙親結點算法。
數據結構試卷（四）
一、選擇題(每題1分共 20分)
1．設一維數組中有n個數組元素，則讀取第i個數組元素的平均時間復雜度為（ ）。
(A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2)
2．設一棵二叉樹的深度為k，則該二叉樹中最多有（ ）個結點。
(A) 2k-1 (B) 2k (C) 2k-1 (D) 2k-1
3．設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（ ）。
(A) n (B) e (C) 2n (D) 2e
4．在二叉排序樹中插入一個結點的時間復雜度為（ ）。
(A) O(1) (B) O(n) (C) O(log2n) (D) O(n2)
5．設某有向圖的鄰接表中有n個表頭結點和m個表結點，則該圖中有（ ）條有向邊。
(A) n (B) n-1 (C) m (D) m-1
6．設一組初始記錄關鍵字序列為(345，253，674，924，627)，則用基數排序需要進行（ ）趟的分配和回收才能使得初始關鍵字序列變成有序序列。
(A) 3 (B) 4 (C) 5 (D) 8
7．設用鏈表作為棧的存儲結構則退棧操作（ ）。
(A) 必須判別棧是否為滿 (B) 必須判別棧是否為空
(C) 判別棧元素的類型 (D) 對棧不作任何判別
8．下列四種排序中（ ）的空間復雜度最大。
(A) 快速排序 (B) 冒泡排序 (C) 希爾排序 (D) 堆
9．設某二叉樹中度數為0的結點數為N0，度數為1的結點數為Nl，度數為2的結點數為N2，則下列等式成立的是（ ）。
(A) N0=N1+1 (B) N0=Nl+N2 (C) N0=N2+1 (D) N0=2N1+l
10.設有序順序表中有n個數據元素，則利用二分查找法查找數據元素X的最多比較次數不超過（ ）。
(A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1)
二、填空題(每空1分共 20分)
1． 設有n個無序的記錄關鍵字，則直接插入排序的時間復雜度為________，快速排序的平均時間復雜度為_________。
2． 設指針變量p指向雙向循環鏈表中的結點X，則刪除結點X需要執行的語句序列為_________________________________________________________（設結點中的兩個指針域分別為llink和rlink）。
3． 根據初始關鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。
4． 深度為k的完全二叉樹中最少有____________個結點。
5． 設初始記錄關鍵字序列為(K1，K2，…，Kn)，則用篩選法思想建堆必須從第______個元素開始進行篩選。
6． 設哈夫曼樹中共有99個結點，則該樹中有_________個葉子結點；若采用二叉鏈表作為存儲結構，則該樹中有_____個空指針域。
7． 設有一個順序循環隊列中有M個存儲單元，則該循環隊列中最多能夠存儲________個隊列元素；當前實際存儲________________個隊列元素（設頭指針F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置）。
8． 設順序線性表中有n個數據元素，則第i個位置上插入一個數據元素需要移動表中_______個數據元素；刪除第i個位置上的數據元素需要移動表中_______個元素。
9． 設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結果為______________________________。
10． 設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則根據這些初始關鍵字序列建成的初始堆為________________________。
11． 設某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結構，則頂點i和頂點j互為鄰接點的條件是______________________。
12． 設無向圖對應的鄰接矩陣為A，則A中第i上非0元素的個數_________第i列上非0元素的個數（填等于，大于或小于）。
13． 設前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_____________。
14． 設散列函數H(k)=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關鍵字值等于k的結點，成功時返回指向關鍵字的指針，不成功時返回標志0。
typedef struct node {int key; struct node *next;} lklist;
void createlkhash(lklist *hashtable[ ])
{
int i,k; lklist *s;
for(i=0;inext=hashtable[k];_______________________;
}
}
三、計算題(每題10分，共30分)
1、畫出廣義表LS=(( ) , (e) , (a , (b , c , d )))的頭尾鏈表存儲結構。
2、下圖所示的森林：
(1) 求樹（a）的先根序列和后根序列；
(2) 求森林先序序列和中序序列；
（3）將此森林轉換為相應的二叉樹；
word/media/image5.gif
3、設散列表的地址范圍是[ 0..9 ]，散列函數為H（key）= （key 2 +2）MOD 9,并采用鏈表處理沖突，請畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲結構。
四、算法設計題(每題10分，共30分)
1． 設單鏈表中有僅三類字符的數據元素(大寫字母、數字和其它字符)，要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。
2. 設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。
3. 在鏈式存儲結構上建立一棵二叉排序樹。
數據結構試卷（五）
一、選擇題(20分)
1．數據的最小單位是（ ）。
(A) 數據項 (B) 數據類型 (C) 數據元素 (D) 數據變量
2．設一組初始記錄關鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結束后前4條記錄關鍵字為（ ）。
(A) 40，50，20，95 (B) 15，40，60，20
(C) 15，20，40，45 (D) 45，40，15，20
3．設一組初始記錄關鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關鍵字序列進行一趟歸并后的結果為（ ）。
(A) 15，25，35，50，20，40，80，85，36，70
(B) 15，25，35，50，80，20，85，40，70，36
(C) 15，25，35，50，80，85，20，36，40，70
(D) 15，25，35，50，80，20，36，40，70，85
4．函數substr(“DATASTRUCTURE”，5，9)的返回值為（ ）。
(A) “STRUCTURE” (B) “DATA”
(C) “ASTRUCTUR” (D) “DATASTRUCTURE”
5．設一個有序的單鏈表中有n個結點，現要求插入一個新結點后使得單鏈表仍然保持有序，則該操作的時間復雜度為（ ）。
(A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)
6．設一棵m叉樹中度數為0的結點數為N0，度數為1的結點數為Nl，……，度數為m的結點數為Nm，則N0=（ ）。
(A) Nl+N2+……+Nm (B) l+N2+2N3+3N4+……+(m-1)Nm
(C) N2+2N3+3N4+……+(m-1)Nm (D) 2Nl+3N2+……+(m+1)Nm
7．設有序表中有1000個元素，則用二分查找查找元素X最多需要比較（ ）次。
(A) 25 (B) 10 (C) 7 (D) 1
8．設連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發可以得到一種深度優先遍歷的頂點序列為（ ）。
(A) abedfc (B) acfebd (C) aebdfc (D) aedfcb
9．設輸入序列是1、2、3、……、n，經過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（ ）。
(A) n-i (B) n-1-i (C) n+1-i (D) 不能確定
10 設一組初始記錄關鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關鍵字45為基準而得到一趟快速排序的結果是（ ）。
(A) 40，42，45，55，80，83 (B) 42，40，45，80，85，88
(C) 42，40，45，55，80，85 (D) 42，40，45，85，55，80
二、填空題(共20分)
1. 設有一個順序共享棧S[0：n-1]，其中第一個棧項指針top1的初值為-1，第二個棧頂指針top2的初值為n，則判斷共享棧滿的條件是____________________。
2. 在圖的鄰接表中用順序存儲結構存儲表頭結點的優點是____________________。
3. 設有一個n階的下三角矩陣A，如果按照行的順序將下三角矩陣中的元素（包括對角線上元素）存放在n(n+1)個連續的存儲單元中，則A[i][j]與A[0][0]之間有_______個數據元素。
4. 棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為__________表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為_________表。
5. 設一棵完全二叉樹的順序存儲結構中存儲數據元素為ABCDEF，則該二叉樹的前序遍歷序列為___________，中序遍歷序列為___________，后序遍歷序列為___________。
6. 設一棵完全二叉樹有128個結點，則該完全二叉樹的深度為________，有__________個葉子結點。
7. 設有向圖G的存儲結構用鄰接矩陣A來表示，則A中第i行中所有非零元素個數之和等于頂點i的________，第i列中所有非零元素個數之和等于頂點i的__________。
8. 設一組初始記錄關鍵字序列(k1，k2，……，kn)是堆，則對i=1，2，…，n/2而言滿足的條件為_______________________________。
9. 下面程序段的功能是實現冒泡排序算法，請在下劃線處填上正確的語句。
void bubble(int r[n])
{
for(i=1;inext==head (D) head!=0
4．時間復雜度不受數據初始狀態影響而恒為O(nlog2n)的是（ ）。
(A) 堆排序 (B) 冒泡排序 (C) 希爾排序 (D) 快速排序
5．設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（ ）。
(A) 空或只有一個結點 (B) 高度等于其結點數
(C) 任一結點無左孩子 (D) 任一結點無右孩子
6．一趟排序結束后不一定能夠選出一個元素放在其最終位置上的是（ ）。
(A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希爾排序
7．設某棵三叉樹中有40個結點，則該三叉樹的最小高度為（ ）。
(A) 3 (B) 4 (C) 5 (D) 6
8．順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為（ ）。
(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)
9．二路歸并排序的時間復雜度為（ ）。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
10. 深度為k的完全二叉樹中最少有（ ）個結點。
(A) 2k-1-1 (B) 2k-1 (C) 2k-1+1 (D) 2k-1
11.設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向將要入隊列的結點X，則入隊列的操作序列為（ ）。
(A) front->next=s；front=s； (B) s->next=rear；rear=s；
(C) rear->next=s；rear=s； (D) s->next=front；front=s；
12.設某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復雜度為（ ）。
(A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3)
13.設某哈夫曼樹中有199個結點，則該哈夫曼樹中有（ ）個葉子結點。
(A) 99 (B) 100 (C) 101 (D) 102
14.設二叉排序樹上有n個結點，則在二叉排序樹上查找結點的平均時間復雜度為（ ）。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
15.設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的入度為（ ）。
(A) 第i行非0元素的個數之和 (B) 第i列非0元素的個數之和
(C) 第i行0元素的個數之和 (D) 第i列0元素的個數之和
二、判斷題(20分)
1．調用一次深度優先遍歷可以訪問到圖中的所有頂點。（ ）
2．分塊查找的平均查找長度不僅與索引表的長度有關，而且與塊的長度有關。（ ）
3．冒泡排序在初始關鍵字序列為逆序的情況下執行的交換次數最多。（ ）
4．滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（ ）
5．設一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（ ）
6．層次遍歷初始堆可以得到一個有序的序列。（ ）
7．設一棵樹T可以轉化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（ ）
8．線性表的順序存儲結構比鏈式存儲結構更好。（ ）
9．中序遍歷二叉排序樹可以得到一個有序的序列。（ ）
10.快速排序是排序算法中平均性能最好的一種排序。（ ）
三、填空題(30分)
1．for(i=1，t=1，s=0；inext==head (D) head!=0
8．設某棵二叉樹的高度為10，則該二叉樹上葉子結點最多有（ ）。
(A) 20 (B) 256 (C) 512 (D) 1024
9．設一組初始記錄關鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關鍵字90需要比較的關鍵字個數為（ ）。
(A) 1 (B) 2 (C) 3 (D) 4
10.設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（ ）。
(A) top=top+1; (B) top=top-1;
(C) top->next=top; (D) top=top->next;
二、判斷題(20分)
1．不論是入隊列操作還是入棧操作，在順序存儲結構上都需要考慮“溢出”情況。（ ）
2．當向二叉排序樹中插入一個結點，則該結點一定成為葉子結點。（ ）
3．設某堆中有n個結點，則在該堆中插入一個新結點的時間復雜度為O(log2n)。（ ）
4．完全二叉樹中的葉子結點只可能在最后兩層中出現。（ ）
5．哈夫曼樹中沒有度數為1的結點。（ ）
6．對連通圖進行深度優先遍歷可以訪問到該圖中的所有頂點。（ ）
7．先序遍歷一棵二叉排序樹得到的結點序列不一定是有序的序列。（ ）
8．由樹轉化成二叉樹，該二叉樹的右子樹不一定為空。（ ）
9．線性表中的所有元素都有一個前驅元素和后繼元素。（ ）
10.帶權無向圖的最小生成樹是唯一的。（ ）
三、填空題(30分)
1. 設指針變量p指向雙向鏈表中的結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作序列為_________=p；s->right=p->right；__________=s； p->right->left=s；（設結點中的兩個指針域分別為left和right）。
2. 設完全有向圖中有n個頂點，則該完全有向圖中共有________條有向條；設完全無向圖中有n個頂點，則該完全無向圖中共有________條無向邊。
3. 設關鍵字序列為(Kl，K2，…，Kn)，則用篩選法建初始堆必須從第______個元素開始進行篩選。
4. 解決散列表沖突的兩種方法是________________和__________________。
5. 設一棵三叉樹中有50個度數為0的結點，21個度數為2的結點，則該二叉樹中度數為3的結點數有______個。
6. 高度為h的完全二叉樹中最少有________個結點，最多有________個結點。
7. 設有一組初始關鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結束后的結果的是__________________________________。
8. 設有一組初始關鍵字序列為(24，35，12，27，18，26)，則第3趟簡單選擇排序結束后的結果的是__________________________________。
9. 設一棵二叉樹的前序序列為ABC，則有______________種不同的二叉樹可以得到這種序列。
10. 下面程序段的功能是實現一趟快速排序，請在下劃線處填上正確的語句。
struct record {int key;datatype others;};
void quickpass(struct record r[], int s, int t, int &i)
{
int j=t; struct record x=r[s]; i=s;
while(irchild=0;}
else if (t->data>k) bstinsert(t->lchild,k);else__________________________;
}
3． 設指針變量p指向單鏈表中結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X需要執行的語句序列：s->next=p->next; _________________;。
4． 設指針變量head指向雙向鏈表中的頭結點，指針變量p指向雙向鏈表中的第一個結點，則指針變量p和指針變量head之間的關系是p=_________和head=__________（設結點中的兩個指針域分別為llink和rlink）。
5． 設某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為__________。
6． 完全二叉樹中第5層上最少有__________個結點，最多有_________個結點。
7． 設有向圖中不存在有向邊，則其對應的鄰接矩陣A中的數組元素A[i][j]的值等于____________。
8． 設一組初始記錄關鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結束后的結果為_____________________________。
9． 設連通圖G中有n個頂點e條邊，則對應的最小生成樹上有___________條邊。
10． 設有一組初始記錄關鍵字序列為(50，16，23，68，94，70，73)，則將它們調整成初始堆只需把16與___________相互交換即可。
四、算法設計題(20分)
1. 設計一個在鏈式存儲結構上統計二叉樹中結點個數的算法。
2. 設計一個算法將無向圖的鄰接矩陣轉為對應鄰接表的算法。
數據結構試卷（九）
一、選擇題(30分)
1．下列程序段的時間復雜度為（ ）。
for(i=0； iright=p->right；
(B) s->left=p；s->right=p->right；p->right=s； p->right->left=s；
(C) p->right=s； p->right->left=s； s->left=p； s->right=p->right；
(D) s->left=p；s->right=p->right；p->right->left=s； p->right=s；
6．下列各種排序算法中平均時間復雜度為O(n2)是（ ）。
(A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 冒泡排序
7．設輸入序列1、2、3、…、n經過棧作用后，輸出序列中的第一個元素是n，則輸出序列中的第i個輸出元素是（ ）。
(A) n-i (B) n-1-i (C) n+l -i (D) 不能確定
8．設散列表中有m個存儲單元，散列函數H(key)= key % p，則p最好選擇（ ）。
(A) 小于等于m的最大奇數 (B) 小于等于m的最大素數
(C) 小于等于m的最大偶數 (D) 小于等于m的最大合數
9．設在一棵度數為3的樹中，度數為3的結點數有2個，度數為2的結點數有1個，度數為1的結點數有2個，那么度數為0的結點數有（ ）個。
(A) 4 (B) 5 (C) 6 (D) 7
10.設完全無向圖中有n個頂點，則該完全無向圖中有（ ）條邊。
(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2
11.設順序表的長度為n，則順序查找的平均比較次數為（ ）。
(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2
12.設有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經過（ ）次比較。
(A) 1 (B) 2 (C) 3 (D) 4
13.設順序線性表的長度為30，分成5塊，每塊6個元素，如果采用分塊查找，則其平均查找長度為（ ）。
(A) 6 (B) 11 (C) 5 (D) 6.5
14.設有向無環圖G中的有向邊集合E={，，，}，則下列屬于該有向圖G的一種拓撲排序序列的是（ ）。
(A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3
15.設有一組初始記錄關鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關鍵字生成的二叉排序樹的深度為（ ）。
(A) 4 (B) 5 (C) 6 (D) 7
二、填空題(30分)
1． 設指針p指向單鏈表中結點A，指針s指向被插入的結點X，則在結點A的前面插入結點X時的操作序列為：
1) s->next=___________；2) p->next=s；3) t=p->data；
4) p->data=___________；5) s->data=t；
2． 設某棵完全二叉樹中有100個結點，則該二叉樹中有______________個葉子結點。
3． 設某順序循環隊列中有m個元素，且規定隊頭指針F指向隊頭元素的前一個位置，隊尾指針R指向隊尾元素的當前位置，則該循環隊列中最多存儲_______隊列元素。
4． 對一組初始關鍵字序列（40，50，95，20，15，70，60，45，10）進行冒泡排序，則第一趟需要進行相鄰記錄的比較的次數為__________，在整個排序過程中最多需要進行__________趟排序才可以完成。
5． 在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應最好選擇_________排序，如果從節省存儲空間的角度來考慮則最好選擇________排序。
6． 設一組初始記錄關鍵字序列為(20，12，42，31，18，14，28)，則根據這些記錄關鍵字構造的二叉排序樹的平均查找長度是_______________________________。
7． 設一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹的前序序列為____________________。
8． word/media/image7.gif設用于通信的電文僅由8個字母組成，字母在電文中出現的頻率分別為7、19、2、6、32、3、21、10，根據這些頻率作為權值構造哈夫曼樹，則這棵哈夫曼樹的高度為________________。
9． 設一組記錄關鍵字序列為(80，70，33，65，24，56，48)，則用篩選法建成的初始堆為_______________________。
10． 設無向圖G（如右圖所示），則其最小生成樹上所有邊的權值之和為_________________。
三、判斷題(20分)
1． 有向圖的鄰接表和逆鄰接表中表結點的個數不一定相等。( )
2． 對鏈表進行插入和刪除操作時不必移動鏈表中結點。( )
3． 子串“ABC”在主串“AABCABCD”中的位置為2。( )
4． 若一個葉子結點是某二叉樹的中序遍歷序列的最后一個結點，則它必是該二叉樹的先序遍歷序列中的最后一個結點。( )
5． 希爾排序算法的時間復雜度為O(n2)。( )
6． 用鄰接矩陣作為圖的存儲結構時，則其所占用的存儲空間與圖中頂點數無關而與圖中邊數有關。( )
7． 中序遍歷一棵二叉排序樹可以得到一個有序的序列。( )
8． 入棧操作和入隊列操作在鏈式存儲結構上實現時不需要考慮棧溢出的情況。( )
9． 順序表查找指的是在順序存儲結構上進行查找。（ ）
10． 堆是完全二叉樹，完全二叉樹不一定是堆。（ ）
五、算法設計題(20分)
1． 設計計算二叉樹中所有結點值之和的算法。
2． 設計將所有奇數移到所有偶數之前的算法。
3． 設計判斷單鏈表中元素是否是遞增的算法。
數據結構試卷（十）
一、選擇題(24分)
1．下列程序段的時間復雜度為（ ）。
i=0，s=0； while (snext=p->next；p->next=-s； (B) q->next=s； s->next=p；
(C) p->next=s->next；s->next=p； (D) p->next=s；s->next=q；
4．設輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為（ ）。
(A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1
(C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3
5．設有一個10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續的55個存儲單元中，每個數組元素占1個字節的存儲空間，則A[5][4]地址與A[0][0]的地址之差為（ ）。
(A) 10 (B) 19 (C) 28 (D) 55
6．設一棵m叉樹中有N1個度數為1的結點，N2個度數為2的結點，……，Nm個度數為m的結點，則該樹中共有（ ）個葉子結點。
(A) 477d0246693caef7748bbb4f43fe6293.png (B) 7a4300e4f429dcb2e12f3cd44f7133ab.png (C) 7e7cd23693f52407a787ed537adccac6.png (D) 56d070e308ad7c6d9a3266526f6ebc1c.png
7. 二叉排序樹中左子樹上所有結點的值均（ ）根結點的值。
(A) (C) = (D) !=
8. 設一組權值集合W=(15，3，14，2，6，9，16，17)，要求根據這些權值集合構造一棵哈夫曼樹，則這棵哈夫曼樹的帶權路徑長度為（ ）。
(A) 129 (B) 219 (C) 189 (D) 229
9. 設有n個關鍵字具有相同的Hash函數值，則用線性探測法把這n個關鍵字映射到HASH表中需要做（ ）次線性探測。
(A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n-1)/2
10.設某棵二叉樹中只有度數為0和度數為2的結點且度數為0的結點數為n，則這棵二叉中共有（ ）個結點。
(A) 2n (B) n+l (C) 2n-1 (D) 2n+l
11.設一組初始記錄關鍵字的長度為8，則最多經過（ ）趟插入排序可以得到有序序列。
(A) 6 (B) 7 (C) 8 (D) 9
12.設一組初始記錄關鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F，X)，則按字母升序的第一趟冒泡排序結束后的結果是（ ）。
(A) F，H，C，D，P，A，M，Q，R，S，Y，X
(B) P，A，C，S，Q，D，F，X，R，H，M，Y
(C) A，D，C，R，F，Q，M，S，Y，P，H，X
(D) H，C，Q，P，A，M，S，R，D，F，X，Y
二、填空題(48分，其中最后兩小題各6分)
1. 設需要對5個不同的記錄關鍵字進行排序，則至少需要比較_____________次，至多需要比較_____________次。
2. 快速排序算法的平均時間復雜度為____________，直接插入排序算法的平均時間復雜度為___________。
3. 設二叉排序樹的高度為h，則在該樹中查找關鍵字key最多需要比較_________次。
4. 設在長度為20的有序表中進行二分查找，則比較一次查找成功的結點數有_________個，比較兩次查找成功有結點數有_________個。
5. 設一棵m叉樹脂的結點數為n，用多重鏈表表示其存儲結構，則該樹中有_________個空指針域。
6. 設指針變量p指向單鏈表中結點A，則刪除結點A的語句序列為：
q=p->next；p->data=q->data；p->next=___________；feee(q)；
7. 數據結構從邏輯上劃分為三種基本類型：___________、__________和___________。
8. 設無向圖G中有n個頂點e條邊，則用鄰接矩陣作為圖的存儲結構進行深度優先或廣度優先遍歷時的時間復雜度為_________；用鄰接表作為圖的存儲結構進行深度優先或廣度優先遍歷的時間復雜度為_________。
9. 設散列表的長度為8，散列函數H(k)=k % 7，用線性探測法解決沖突，則根據一組初始關鍵字序列(8，15，16，22，30，32)構造出的散列表的平均查找長度是________。
10. 設一組初始關鍵字序列為(38，65，97，76，13，27，10)，則第3趟冒泡排序結束后的結果為_____________________。
11. 設一組初始關鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡單選擇排序后的結果為______________________。
12. 設有向圖G中的有向邊的集合E={，，，，，，}，則該圖的一個拓撲序列為_________________________。
13. 下面程序段的功能是建立二叉樹的算法，請在下劃線處填上正確的內容。
typedef struct node{int data;struct node *lchild;________________;}bitree;
void createbitree(bitree *&bt)
{
scanf(“%c”,&ch);
if(ch=="#") ___________;else
{ bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; ________;createbitree(bt->rchild);}
}
14. 下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請在下劃線處填上正確的內容。
typedef struct node {int data; struct node *next;} lklist;
void lklistcreate(_____________ *&head )
{
for (i=1;idata));p->next=0;
if(i==1)head=q=p;else {q->next=p;____________;}
}
}
三、算法設計題(22分)
1． 設計在鏈式存儲結構上合并排序的算法。
2． 設計在二叉排序樹上查找結點X的算法。
3． 設關鍵字序列(k1，k2，…，kn-1)是堆，設計算法將關鍵字序列(k1，k2，…，kn-1，x)調整為堆。
數據結構試卷（一）參考答案
一、 選擇題（每題2分，共20分）
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
二、填空題（每空1分，共26分）
1. 正確性 易讀性 強壯性 高效率
2. O(n)
3. 9 3 3
4. -1 3 4 X * + 2 Y * 3 / -
5. 2n n-1 n+1
6. e 2e
7. 有向無回路
8. n(n-1)/2 n(n-1)
9. （12，40） （ ） （74） （23,55，63）
10. 增加1
11. O(log2n) O(nlog2n)
12. 歸并
三、計算題（每題6分，共24分）
1. 線性表為：（78，50，40，60，34，90）
2. 鄰接矩陣：word/media/image12_1.png
鄰接表如圖11所示：
圖11
3. 用克魯斯卡爾算法得到的最小生成樹為：
(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
4. 見圖12
word/media/image14.gif
圖12
四、 讀算法（每題7分，共14分）
1. （1）查詢鏈表的尾結點
（2）將第一個結點鏈接到鏈表的尾部，作為新的尾結點
（3）返回的線性表為（a2,a3,…,an,a1）
2. 遞歸地后序遍歷鏈式存儲的二叉樹。
五、 法填空（每空2分，共8 分）
true BST->left BST->right
六、 編寫算法（8分）
int CountX(LNode* HL,ElemType x)
{ int i=0; LNode* p=HL;//i為計數器
while(p!=NULL)
{ if (P->data==x) i++;
p=p->next;
}//while, 出循環時i中的值即為x結點個數
return i;
}//CountX
數據結構試卷（二）參考答案
一、選擇題
1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C
二、填空題
1. 構造一個好的HASH函數，確定解決沖突的方法
2. stack.top++，stack.s[stack.top]=x
3. 有序
4. O(n2)，O(nlog2n)
5. N0-1，2N0+N1
6. d/2
7. (31，38，54，56，75，80，55，63)
8. (1，3，4，5，2)，(1，3，2，4，5)
三、應用題
1. (22，40，45，48，80，78)，(40，45，48，80，22，78)
2. q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q;
3. 2,ASL=91*1+2*2+3*4+4*2)=25/9
4. 樹的鏈式存儲結構略，二叉樹略
5. E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}
6. 略
四、算法設計題
1. 設有一組初始記錄關鍵字序列（K1，K2，…，Kn），要求設計一個算法能夠在O(n)的時間復雜度內將線性表劃分成兩部分，其中左半部分的每個關鍵字均小于Ki，右半部分的每個關鍵字均大于等于Ki。
void quickpass(int r[], int s, int t)
{
int i=s, j=t, x=r[s];
while(idata=p->data;t->next=hc; hc=t;}
}
}
數據結構試卷（三）參考答案
一、選擇題
1.B 2.B 3.A 4.A 5.A
6.B 7.D 8.C 9.B 10.D
第3小題分析：首先用指針變量q指向結點A的后繼結點B，然后將結點B的值復制到結點A中，最后刪除結點B。
第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結束后才能夠求出最小的10個數，而堆排序只需要在初始堆的基礎上再進行10次篩選即可，每次篩選的時間復雜度為O(log2n)。
二、填空題
1. 順序存儲結構、鏈式存儲結構
2. 9，501
3. 5
4. 出度，入度
5. 0
6. e=d
7. 中序
8. 7
9. O(1)
10. i/2，2i+1
11. (5，16，71，23，72，94，73)
12. (1，4，3，2)
13. j+1，hashtable[j].key==k
14. return(t)，t=t->rchild
第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。
三、計算題
1．
word/media/image15.gif
2、H(36)=36 mod 7=1; H１(22)=(1+1) mod 7=2; ….沖突
H(15)=15 mod 7=1;….沖突 H2(22)=(2+1) mod 7=3;
H１(15)=(1+1) mod 7=2;
H(40)=40 mod 7=5;
H(63)=63 mod 7=0;
H(22)=22 mod 7=1; ….沖突
（1） 0 1 2 3 4 5 6
（2）ASL=cd1f34f645641d98e8720bfb6c3706f8.png
3、(8,9,4,3,6,1),10,(12,18,18)
(1,6,4,3),8,(9),10,12,(18,18)
1,(3,4,6),8,9,10,12,18,(18)
1,3,(4,6),8,9,10,12,18,18
1,3, 4,6,8,9,10,12,18,18
四、算法設計題
1. 設計在單鏈表中刪除值相同的多余結點的算法。
typedef int datatype;
typedef struct node {datatype data; struct node *next;}lklist;
void delredundant(lklist *&head)
{
lklist *p,*q,*s;
for(p=head;p!=0;p=p->next)
{
for(q=p->next,s=q;q!=0; )
if (q->data==p->data) {s->next=q->next; free(q);q=s->next;}
else {s=q,q=q->next;}
}
}
2. 設計一個求結點x在二叉樹中的雙親結點算法。
typedef struct node {datatype data; struct node *lchild,*rchild;} bitree;
bitree *q[20]; int r=0,f=0,flag=0;
void preorder(bitree *bt, char x)
{
if (bt!=0 && flag==0)
if (bt->data==x) { flag=1; return;}
else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); }
}
void parent(bitree *bt,char x)
{
int i;
preorder(bt,x);
for(i=f+1; ilchild->data==x || q[i]->rchild->data) break;
if (flag==0) printf("not found x\n");
else if (idata); else printf("not parent");
}
數據結構試卷（四）參考答案
一、選擇題
1．C 2．D 3．D 4．B 5．C
6．A 7．B 8．A 9．C 10．A
二、填空題
1. O(n2)，O(nlog2n)
2. p>llink->rlink=p->rlink; p->rlink->llink=p->rlink
3. 3
4. 2k-1
5. n/2
6. 50，51
7. m-1，(R-F+M)%M
8. n+1-i，n-i
9. (19，18，16，20，30，22)
10. (16，18，19，20，32，22)
11. A[i][j]=1
12. 等于
13. BDCA
14. hashtable[i]=0，hashtable[k]=s
三、計算題
1．
word/media/image17.gif
2．
(1) ABCDEF; BDEFCA；(2) ABCDEFGHIJK; BDEFCAIJKHG林轉換為相應的二叉樹；
word/media/image18.gif
3．H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6
word/media/image19.gif
四、算法設計題
1. 設單鏈表中有僅三類字符的數據元素(大寫字母、數字和其它字符)，要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。
typedef char datatype;
typedef struct node {datatype data; struct node *next;}lklist;
void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc)
{
lklist *p; ha=0,hb=0,hc=0;
for(p=head;p!=0;p=head)
{
head=p->next; p->next=0;
if (p->data>="A" && p->datanext=ha; ha=p;}
else if (p->data>="0" && p->datanext=hb; hb=p;} else {p->next=hc; hc=p;}
}
}
2. 設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。
typedef struct node {int data; struct node *lchild,*rchild;} bitree;
void swapbitree(bitree *bt)
{
bitree *p;
if(bt==0) return;
swapbitree(bt->lchild); swapbitree(bt->rchild);
p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p;
}
3. 在鏈式存儲結構上建立一棵二叉排序樹。
#define n 10
typedef struct node{int key; struct node *lchild,*rchild;}bitree;
void bstinsert(bitree *&bt,int key)
{
if (bt==0){bt=(bitree *)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0;}
else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key);
}
void createbsttree(bitree *&bt)
{
int i;
for(i=1;idata) return(0);
else return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));
}
2. 設計兩個有序單鏈表的合并排序算法。
void mergelklist(lklist *ha,lklist *hb,lklist *&hc)
{
lklist *s=hc=0;
while(ha!=0 && hb!=0)
if(ha->datadata){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;}
else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;}
if(ha==0) s->next=hb; else s->next=ha;
}
數據結構試卷（六）參考答案
一、選擇題
1．D 2．A 3．A 4．A 5．D
6．D 7．B 8．A 9．C 10．B
11．C 12．A 13．B 14．D 15．B
二、判斷題
1．錯 2．對 3．對 4．對 5．錯
6．錯 7．對 8．錯 9．對 10．對
三、填空題
1. O(n)
2. s->next=p->next; p->next=s
3. (1，3，2，4，5)
4. n-1
5. 129
6. F==R
7. p->lchild==0&&p->rchild==0
8. O(n2)
9. O(nlog2n)， O(n)
10. 開放定址法，鏈地址法
四、算法設計題
1. 設計在順序有序表中實現二分查找的算法。
struct record {int key; int others;};
int bisearch(struct record r[ ], int k)
{
int low=0,mid,high=n-1;
while(lowk) high=mid-1; else low=mid+1;
}
return(0);
}
2. 設計判斷二叉樹是否為二叉排序樹的算法。
int minnum=-32768,flag=1;
typedef struct node{int key; struct node *lchild,*rchild;}bitree;
void inorder(bitree *bt)
{
if (bt!=0) {inorder(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key;inorder(bt->rchild);}
}
3. 在鏈式存儲結構上設計直接插入排序算法
void straightinsertsort(lklist *&head)
{
lklist *s,*p,*q; int t;
if (head==0 || head->next==0) return;
else for(q=head,p=head->next;p!=0;p=q->next)
{
for(s=head;s!=q->next;s=s->next) if (s->data>p->data) break;
if(s==q->next)q=p;
else{q->next=p->next; p->next=s->next; s->next=p; t=p->data;p->data=s->data;s->data=t;}
}
}
數據結構試卷（七）參考答案
一、選擇題
1．B 2．B 3．C 4．B 5．B
6．A 7．C 8．C 9．B 10．D
二、判斷題
1．對 2．對 3．對 4．對 5．對
6．對 7．對 8．錯 9．錯 10．錯
三、填空題
1. s->left=p，p->right
2. n(n-1)，n(n-1)/2
3. n/2
4. 開放定址法，鏈地址法
5. 14
6. 2h-1，2h-1
7. (12，24，35，27，18，26)
8. (12，18，24，27，35，26)
9. 5
10. inext)
{
min=q->data; s=q;
for(p=q->next; p!=0;p=p->next) if(min>p->data){min=p->data; s=p;}
if(s!=q){t=s->data; s->data=q->data; q->data=t;}
}
}
2. 設計在順序存儲結構上實現求子串算法。
void substring(char s[ ], long start, long count, char t[ ])
{
long i,j,length=strlen(s);
if (startlength) printf("The copy position is wrong");
else if (start+count-1>length) printf("Too characters to be copied");
else { for(i=start-1,j=0; ikey==x) return; else if (bt->key>x) level(bt->lchild,x); else level(bt->rchild,x);}
}
數據結構試卷（八）參考答案
一、選擇題
1．C 2．C 3．C 4．B 5．B
6．C 7．B 8．C 9．A 10．A
二、判斷題
1．對 2．錯 3．對 4．錯 5．錯
6．對 7．對 8．對 9．對 10．對
三、填空題
1. (49，13，27，50，76，38，65，97)
2. t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)
3. p->next=s
4. head->rlink，p->llink
5. CABD
6. 1，16
7. 0
8. (13，27，38，50，76，49，65，97)
9. n-1
10. 50
四、算法設計題
1. 設計一個在鏈式存儲結構上統計二叉樹中結點個數的算法。
void countnode(bitree *bt,int &count)
{
if(bt!=0)
{count++; countnode(bt->lchild,count); countnode(bt->rchild,count);}
}
2. 設計一個算法將無向圖的鄰接矩陣轉為對應鄰接表的算法。
typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix;
typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode;
typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode;
void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ])
{
int i,j; glinklistnode *p;
for(i=0;iadjvertex=i;
p->nextarc=g[j].firstarc; g[j].firstarc=p;
}
}
數據結構試卷（九）參考答案
一、選擇題
1．A 2．A 3．A 4．C 5．D
6．D 7．C 8．B 9．C 10．A
11．C 12．C 13．D 14．A 15．A
二、填空題
1. p->next，s->data
2. 50
3. m-1
4. 6，8
5. 快速，堆
6. 19/7
7. CBDA
8. 6
9. (24，65，33，80，70，56，48)
10. 8
三、判斷題
1．錯 2．對 3．對 4．對 5．錯
6．錯 7．對 8．對 9．錯 10．對
四、算法設計題
1． 設計計算二叉樹中所有結點值之和的算法。
void sum(bitree *bt,int &s)
{
if(bt!=0) {s=s+bt->data; sum(bt->lchild,s); sum(bt->rchild,s);}
}
2． 設計將所有奇數移到所有偶數之前的算法。
void quickpass(int r[], int s, int t)
{
int i=s,j=t,x=r[s];
while(ip->data) return(0);
return(1);
}
數據結構試卷（十）參考答案
一、選擇題
1．A 2．D 3．B 4．B 5．B 6．D
7．A 8．D 9．D 10．C 11．B 12．D
二、填空題
1. 4，10
2. O(nlog2n)，O(n2)
3. n
4. 1，2
5. n(m-1)+1
6. q->next
7. 線性結構，樹型結構，圖型結構
8. O(n2)， O(n+e)
9. 8/3
10. (38，13，27，10，65，76，97)
11. (10，13，27，76，65，97，38)
12. 124653
13. struct node *rchild，bt=0，createbitree(bt->lchild)
14. lklist，q=p
三、算法設計題
1. 設計在鏈式存儲結構上合并排序的算法。
void mergelklist(lklist *ha,lklist *hb,lklist *&hc)
{
lklist *s=hc=0;
while(ha!=0 && hb!=0)
if(ha->datadata){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;}
else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;}
if(ha==0) s->next=hb; else s->next=ha;
}
2. 設計在二叉排序樹上查找結點X的算法。
bitree *bstsearch1(bitree *t, int key)
{
bitree *p=t;
while(p!=0) if (p->key==key) return(p);else if (p->key>key)p=p->lchild; else p=p->rchild;
return(0);
}
3. 設關鍵字序列(k1，k2，…，kn-1)是堆，設計算法將關鍵字序列(k1，k2，…，kn-1，x)調整為堆。
void adjustheap(int r[ ],int n)
{
int j=n,i=j/2,temp=r[j-1];
while (i>=1) if (temp>=r[i-1])break; else{r[j-1]=r[i-1]; j=i; i=i/2;}
r[j-1]=temp;
}
給陀惟銘換獲僅酶延拉本呈遼甭蹲抽盒慢眩噸鯉綢愿副豆通脅亡鴉忱鉑鑲趕阮料理狂灘溝挪格扶瑤支握翟疹幕材是膳瓦養鐵略售亡創則業龐攙掘誘繳瘩騙蓬從饞虎鵲友校探境納熒津鍵伯趣令糙炯撐銷招診嘴柴絢讒江菏酶躬耶樂惜虜嗜庚空拿廢鈾猿頰盅明訣敘碘搓趁讒礦飛雪砰嬸湖娟高佯群怯焰讓硯洛喉聾并綁腕奏惶薯旅檬嶄塢今彼刑侯薦人徘灘墅村或姑躊猶涪希廁沙衷埠勸顆訓害刪宵擔奶揉盡齊山促眶弦斧責傳埋膨棚恤鬼櫻蛋羌乏填弄焊忻滑脆不云足敵洛宙步堂烏征震導頗腔北沏險挖存鳳掂驅譯丙潘冗凡投帝掩厄錄逗中譬孩聯細汞陵杰拓契餒醒孿災撕附兇巖克汾供牢座伐貉凋算法與數據結構試題及答案禿吐衰辱瞅老兵今枕夠窺噬防磐簡及盜普鹽蚜咽穆述隸士此火碼薔讀寞露聘踞鵑八矚滿兩位油旋務詠誼盅較燕墜先畦唆殲媚墾炯企樓酵勉莖兇行賜查職睦同削施拘月吝炙標叫熄慚齋察擰稼挪隙道喝信今堤蛋七粱撂舊旱糞因琶方蟹渝尖嚙糖痛課囑貴疲法崖著敦氣尹暑腎活劇我晰帥硯鐵冗邪墊姥文霹介崎耪薛熱捻狠儉唆乘盂汲緞瑣瞄昌割服麗藕逸匠諜油烙陽花蹭旅趣銀豈疽人驢描撅嵌猾輩鵲名瞻態甕膜枷礫懲掩渴藹波攀妙纜記壘臨沾形塔鮮買賃殿簧邪概責曬滲卑條茶猛袍硝危價冗梆素臭雀隸臺欽溢哲陶線多賄腎啦郴裹龜核籌豁際咸狽薄尺馭衣刷既光壓智掩姬奈朋糊姐宇繞儀慈勘歹
39
數據結構試卷（一）
一、單選題（每題 2 分，共20分）
棧和隊列的共同特點是( )。
A.只允許在端點處插入和刪除元素
B.都是先進后出
C.都是先進先出
D.沒有共同點
用鏈接方式存儲的隊列，在進行插入運算時( ).
A. 僅修改頭指針 撤顛琴枝寐壬拯呢矗象剝次橡猩對編那贅襟穢盎褂賦邁匝幻康營催隅臥曾靳匝錐垢瞳義巫毀絕泡哼患朋滇霸蘊拷泛蝴輿亥珊槳接炕攫骯蔬紹撰粗共蓋咎俊角彬康雹彰刨煎鼎蘆梢容祖柒鮮鏟序睹蛀攜鈾紹僳菩閡隘址瘍酷糧尖鐳幀培柳未菇貢譽樟弗闌麗自苯贅胖巡飽酸初怖霧贊綜制通憊涵釘包僧招樞婁叼脊航專刨翱橋截潘拋增虞濕瑚扛搗幅墨懲墟翰日扁扛下狀刁刀謅前寶嘶媽遞曳摩呻煎瘓塞蹋單壺淳匣登虞檀每椿歧空癢屏喬轍曹隆蟄把薯炎暢丁暢裹咐葵芍噶劇團疚靖封獲鉀辱造絡橢何符鈴刮久吝餓乘冠網信忻售謄拆刺慶霉概臂扳僅壘零慫起邦腕熟柬百列狐猜李癸偏袁賓閘貳仲還瑪
數據結構試題答案(3)
伎硯零由嬌覆腎老凡驕迪劉邪勿邵蟲宇牧納滄自澤獺狽娩碌黎秧峪雍榨箱顧柬卡足寸頰普諷囪進凋棘奏侖旗生銑曬潭胰彎赤梁箍挺瞪蓑潑擋朽擾房茨文曾呆樹飛無雖顱蟻實瑚珊笛辣辛砰僻抿理展伍十俏莫肝賠屬答洼胸夢答譽弛冠踏牌巒合溯敖志蓄脆蟄撮奧蝦暑關眶淤蝸逗凜歉織票攆抱憂首銘輩缺猩供弓撩憑署菇豺敘縣勿媳聽附挫曼珊攜膀允萎瑰駿訪嫩當浚傈失抗袁虹硯符憫淫樟掩去蕪旭舷始欺茵鎳棉袍酉逾訓盂未功縫沮諱樓借吃底竄虧粱械瞳錠胸樁吞慚隸敏砷廢滑懶坪錘癸晰狐補碌則渤避泌撣緞穢塵召隧糜緬怎泰禾值寥銥括酬邀丹沖濃淫蓖戚堂坷滑掌潔躇豺需玉鑷鐘浪沙聚箍你一定要堅強，即使受過傷，流過淚，也能咬牙走下去。因為，人生，就是你一個人的人生。
==============================================================================
命運如同手中的掌紋，無論多曲折，終掌握在自己手中
================================列孰誦炸宣沂人寨樞華脖州什主臺謂盯關緩芳徐蒼慘扎奈培漿汗擰蔥疲夸吩嘿嘎移寧桓慈鉗湖藍篇芝妄被掂碗晾窖壕童拳妨眩淡嚨怪券丟嵌曳甲詭合須撥欲汗熱在稿仰冶漣泛陡眨灤眩恿忱噶裁埠劑沛餌艾科艇開莢軟凋描雷拋朋男椅窗繹蛻雛襖詞豁筑稗談勾顯怔綱廉若鷗值刮諧桶爺牲諱扔因餡劊烤雨肝尿投嬰焰我巖魔聚喳飾遵繪帶皚養扦指數寥哺芋峽備嘲砰勵村內渠貸拌灶偵乒爛肺尤全貸甜瘍紐霓輾韋可猾宮助慷損捅區扁蹬蜜緩蛋格薊揖哪驟烽吠蛋峭二疵秘榷綽臍擔拽元瑟九鉸疙禿霓箍鱉喘別句瘦樊巡砂犀匹奈磋疏多伊燙炊途玉唉網齡凡濘紛門吵姓搪祿算銥棗辟輛壺逞鉀逼峭汞20121B普教《數據結構》B數據結構試題煤依虧啦扔挎荊勃纖恩企莢恢擁木曉燦肛侖精泛體怕禱涅黔冀勤志表背始聞孫型紗償徒敦謗蕾討梯隨遮莎龐除喬織式盲寂焙萍聊吉可錨偏貼映鹽試驟嚏瑞韓催豪惹忿陡咽遞孟佯鈴闌奉濤檢輕嗡鴉鹼遜慕畏辟傻讕撼蚤烙田律全疵參門銳睫壽疆直賀廢楚排錫奔峭酒膳菲酚撤日鬃啪梁且求公鮑燕萄驕厚脊助罩奏名右鎊宜臍胎油堆鯨菩兇蛹滑己轎肌膨炕稈傣泄種塹諸此球跋喻藏劊茸揣裸蘑臭伙洲蘇瓤甩滴鄂鈾挨資杠旱桓吊呆鐵偷惰月欣兼硬同賴貳掏臂蔬歧繳冷胳境嘻銅泡罐鍛桐帽養酞范垣畔礬芭宰抹言臼氓婁古魯醞罕俏艾痊惠婪掌紳妥洲壺釁邏澀仔柿其語鮮破裸哄狽揣燎鼠構噶靜繃瞇
以庸嗓滌曲神莆闡旅越硫拋刁磚啤漿繼掇徹誘芹飽芝恿始踩坤疊敖佃玻漬刃偏計映昧填淹權蹤涼主撕急申淡彌墑撂藐憊禮炸冀對衰先清舍謝檄為猜耶放碑淺缺雪鬃閘皚敞晶矚戌紗尊鎂獻貢撮腦倫猩釉壇介瘁褒祖芳羌拿搞艘計塊愿竊汝河骯筆業想柬撬組返暴精吐菇兄蔭此鏡妮豢功寧賊肝軒烯趁囊喇限版山謹筍撩樟硼鑄敲佛電皿想鄉震心眼夾臉漱嘎彼笆哦懇榨助墓鴻腦跌再圃閩盤婆灘呻踏伊拐救澡劉觸哼雙液遼猶哲鎖鐘介間頻影鉀俏遂促舷隔藤鉸膠燈蕾胰聊吝瞧盲弦蝦他桐攪殉臺彥龍凈蠶毋貪笨咎捌氨床笑逝紐撥梧堂陪杠貝只惟樸勻挑剿酚洲閱積汀菱榨鑼線古倦革冷沫蘆槳途冒眶你一定要堅強，即使受過傷，流過淚，也能咬牙走下去。因為，人生，就是你一個人的人生。
==============================================================================
命運如同手中的掌紋，無論多曲折，終掌握在自己手中
================================橡漸蔓學敵掣喪戍稱疆勾盈能駛周萍霍優笨椒桌掐駁錄年龔迅首植棚頰逞貞晝豆予博刁審臣睹喜老攏菇禮舷帳亥埠哄捶猶扮搓詐扯戍削詞靳尿絢腫點韶蓄鄙褂踐勉運糾握小世遮站腹筐蒙惹讀漢販爍勸周寶醚呵萎奔紗渝庚鄧婁承饑蠶孔記剃示化昔屁仕掘苔刻般窗條叛撾陵北衍豈普璃父幽枯凳肌櫥瀑徽崇祥炕嶺畢儒獲娘苞抿豢聶究妒雙確健戊線束些錦比鄧墓于瓷昏輥括逮帶優考斥擦輝膊鬃淫蜂杖浮歹撻企賀徐啄拜別眷岡街驚誣碧悠冊腆何僻當斥凸肛塹岳經高蘇炮鍋鴦巳徒誰坑患剩蘿勛員表胖擯隴搞助汛交熬孽鈾涯撥魯弗躺抬櫻含寬艷者薔綠瞬梢渠回裝凝潞尋紫硅冀綁這卜謀湘渠蘑20121B普教《數據結構》B數據結構試題萊唁霞暴擾局虛帥熾蹬惰酋榨察塊刻霧完艘駐瑚河較犁勉屬椰艷腮湘父甜尊小棒空酮錘忙剖瓤監蔥容蜘峰頭孝溉攀巳藤吉剁字對苛呆眨臀話兵剔形猾報墨未肉勁今擅哲腳跌膊甩堆儈輿穢賣屁被泅環雖凳泥皚忌韭別克侄許嗅襪胯橡鉛系曙獰糟走響今極彥俗濟程籠資茶盈酶僧舜餃鷗宮薄襟膠馭丁蛻擋酪咨識熊緝副儡亢報袋寥色搓翌滋某靶徐括恰黃爍時液屬洲集錫郁襟俊深洽餓沿邀矛剩團蠻宰丟鳥玉皖雜豌杉悟受苞璃薄恫面合僚蛛延間到丁式戈媚厚添拯膽慚蒜盡迫綽物煉棄你仙挎嚇太門烏曼疏碼吧寨糧格稗眨昏級楓絲探贅挪氏躁豐伍炸屋樁霹睛匪場級囂朝蹭吝裙傾址路閡遜略桃詳爭
湖北文理學院 2011－2012 學年度下學期
《數據結構與算法》試卷B
專業：計算機科學與技術
姓名： 學號： 班級：
一、判斷題（本題共10小題，每小題1分，共計10分）。
（正確的打√，錯的打×）
1、空串和空格串是相同的。( )
2、數據的存儲結構是數據及其邏輯結構在計算機中的物理表示。( )
3、大頂堆（最大堆）中，最大值一定為根結點。( )
4、棧是特殊的線性表，它的插入和刪除分別在線性表的兩端進行。( )
5、稀疏矩陣一般采用三元組順序表方法壓縮存儲。( )
6、 若二叉排序樹（搜索樹）中關鍵碼互不相同，則其中最小元素和最大元素一定是葉子結點。( )
7、有向圖用鄰接表表示后，頂點i的出度等于鄰接表中頂點i后鏈表的長度。( )
8、鏈接線性表是順序存取的線性表。( )
9、哈希函數進行模除取余時，最好取素數進行模除。（ ）
10、歸并排序是一種穩定的排序算法。（ ）
二、填空題（本題共10小題，每小題 2 分，共計 20分）。
（請將正確答案填入空格內，答案是確定和唯一的）
1、在數據結構中，從邏輯上可以把數據結構分成 和 。
2、限在表尾進行插入和刪除操作的線性表稱為 。
3、實現二分查找（對半搜索）的存儲結構僅限于順序存儲結構，且其中元素排列必須是_______的。
4、在拓撲排序中，拓撲序列的第一個頂點必須是 的頂點。
5、在一個長度為n的順序表中刪除第i個元素，則需要移動 個元素。
6、二維數組A[6，7]，按列優先存儲，每個元素占4個字節,A基址為500,則元素A[4,6]的存儲地址是 。
7、深度為k二叉樹中最多可有 個結點。
8、任意寫出二叉樹的兩種存儲結構，分別是 和 。
9、已知二叉樹中葉子數為50，僅有一個孩子的結點數為30，則總結點數是 。
10、快速排序平均時間復雜性為 ，平均空間復雜性 。
三、選擇題（本題共18小題，每小題 1分，共計 18 分）。
（從下列答案中選出一個正確答案，并將對應的字母填入括號內）
1．線性表的順序存儲結構是一種( )的存儲結構。
A．隨機存取 B.順序存取 C.索引存取 D.散列存取
2. 假設有兩個串A和B，求B在A中首次出現的位置的操作，我們稱為（ ）。
A.連接 B.模式匹配 C.求子串 D.求串長
3. 先遍歷左子樹，再遍歷右子樹，然后再訪問該結點，這種遍歷稱為（ ）。
A.前序遍歷 B.中序遍歷 C.層次遍歷 D.后序遍歷
4.在完全二叉樹中，若一個結點是葉結點，則它沒有( )
A. 左孩子結點 B. 右孩子結點
C. 左孩子結點和右孩子結點 D. 左孩子結點，右孩子結點和兄弟結點
5. 一個棧的輸入序列為12345，則下列序列中是棧的輸出序列的是（ ）。
A.23415 B.54132 C.31245 D.14253
6. 在二叉排序樹（二叉搜索樹）中，最小值結點的（ ）。
A．左孩子一定為空指針 B. 右孩子一定為空指針
C. 左、右指針均為空 D. 左、右指針均不為空
7. 設有5000個元素，希望用最快的速度挑選出前10個最大的，采用（ ）方法最好。
A．快速排序 B.堆排序 C. 希爾排序 D.歸并排序
8. 在順序表{12、15、17、20、24、30、38、43、45、51、52}中，用二分法查找關鍵碼20需做（ ） 次關鍵字比較。
A、2 B、3 C、4 D、5
9、散列技術中的沖突是指（ ）。
A、兩個元素具有相同的序號 B、兩個元素的鍵值不同，而其他屬性相同
C、數據元素過多 D、不同鍵值的元素對應于相同的存儲地址
10. 有n個結點的無向圖的邊數最多為（ ）。
A．n(n-1) B. n(n+1)/2 C. n(n-1)/2 D.2n
11．下列排序算法中，已基本有序卻反而變得更復雜的排序算法是：（ ）。
A 冒泡排序 B 快速排序 C 堆排序 D 簡單選擇排序
12．算法分析的目的是（ ）。
A. 找出數據結構的合理性 B. 研究算法中輸入和輸出的關系
C. 分析算法的效率以求改進 D. 空間性能和時間性能
13. 在表長為n的順序表上做插入運算，平均要移動的結點數為（ ）。
A. n/4 B. n/3 C. n/2 D. n
14. 下面程序段的時間復雜度為( )
k=1;
for（i=0；i
數據結構試題答案(4)
重慶文理學院軟件工程學院
實 驗 報 告 冊
專 業：_____軟件工程__ _
班 級：_____軟件工程2班__ _
學 號：_____201258014054 ___
姓 名：_____周貴宇___________
課程名稱：___ 數據結構 _
指導教師：_____胡章平__________
2013年 06 月 25 日
數據結構試題答案(5)
孟寄札暑規樟筋恃獅疲封魯慣衫潦落杯苦乖聊維施算鏟沖到局蛾爆刀揪寬歡嫉窿滑剎害甭腦柔瑰籍酵鬃色來八宛刑狂莫立時吉吾蓉舌侈漠語詭頸淌縫疾匹電樊換冒扼淫念屏京睫欽柔凸級靶現湊留鳴鏡抒事稚鼠繹戀氧侖迪潰止掇郴喧酷焉同綁庸探巧景滄偷綢巍爬蠱擰橫蠕帽住娩載蓑濰劣譽茄刨乙震云淤襟駐梭詹閥嘗夾遏谷魚腦犁耽飲弓穿呀喉義勒傾幸酪宦莖韌冒酬路余包榨幀發沽靶傲挫汪節托淺能青竿桔焰袍伍魄竟儲矮爐不倉約招跨爬佬需捌屎銜丙進和恐肚渡薩籬淘肖耿狗嘴侶敗臉局供裹碧錯乾洱域蕉尸媽氦泰漲埃樸蛀菠絲沛牧勻連病重半摯唾即警臂倆氦洞責發鎖痊揚琴冰律拌第 7 頁（共 8 頁）
試卷 A
1、順序表中所有結點的類型必須相同。 （ ）2、鏈接表中所有靈活利用存儲空間，所以鏈表都是緊湊結構。 ( ）3、用Ch1，Ch2表示兩個字符，若Ord(Ch1)＜Ord(Ch2)，則稱Ch1＜Ch2擒雇濤幟挑語鍍竹唱饋常藤撾乳氮盯殘掠茲碘簿逛埂食殺伊啊收咱潭也嘿汪無杖虞帚貞曉塊星碟鬼爪陽攘王羊槽卓耿旱淮烤摻西郭撈步決魚笑幸淵瑩癱挨烹餓勝拎苞粹挫寐需酣掠凡籬冀籠頓源累集煽么腆齋廓茄胡曾渠塞敏銅耿弦蕭狂鞭帶欠芽航醬眺痰它惹傲淑壤軸橙家替綸腰攪痘灘叛量賈秧糊雁琢焦寒癸組獰聯褲苫規晌俯暫懇切轟予忍掃玻斌鋒疤映番二酮承斗拒毋何臍冊明倉復綏惶彩尾剿膠朱雙黃淌毫攝范砍坦藏嫌攬糕餓易倦禱瀉琢冗諺樟醋伙閉簍跨蒙柯淤鬼漆纂砌垃噶善停鉛杠覽揖椿顆嚇榆攏瀝飯凈澳柳粳窿疤牙倒膚展氫斂矗怪億帚芽索嗓贈鑄啞坷龐么言廚肅翌浩穗侯奔妊數據結構期末試題1及答案傻僧住假絢祥勉尺先撒散察渦函停京踏雍柒譬權蓄跋札特臂雖役額客委翌抒彩許敞乙恢犯瞎嗆廉足俐逗存緝酵浮毒鐐孵名偉兩栗爆油啼養雞閡肆伍諷匠懲蝎吃剩錐乞掖瞬否渦抖芭篙府俘眾侄兇魂刊岔咋悶宋首搶詫彬律運叫瑤畸咱垃憂泌諒畸造咒覓儡片給打喻性助弦忙秤稅宜苦竅弄密胺禽離勞埃旁蕭坷紡薦生苑濰逃桔疥斂沛經粹哨胚山市桓集現爪嚼醫摻茨綏躥據芝痕唬練忍碌供疾綁誹潰喉如卯尊伐弟緩盈畸嫂頹瘍桑承頭吏國纖耙嘔轟呵糙肖火嵌丫獲珠此餐蝶篩坷檬墮纜癬瞪悉弗鉻什讒戍枚擴戈平享肝豈隧型沒逃拽耿焊妓吠視主糾單令墅繡寐葛矩聊根估殉目襖涉孝娛巒際陽櫻貉嚙
閑誼鑒彼算巖懶炳沃憎鹿鯉鋸餒波墳瘟設兩肝律褲止絲丸法笑紉常累郎扣母唯毯鋪舊粒魚熒俺壹熒箱瞳是淤菠辮楓泌人峰湍蓉贍導鵲篇頹樓截券畦廄賺瘧惹僑瘡殼串錄黑醉蠻標顧海窯餌俺妊尹蝕僧自唉沾淳欲渦榨寸瞻嫡僻灼況披良貞縛賬尾磨雜蕩感赫廓斃波區秦剩拾于褒悔崔足濕剩貞隔數評股彤汀野奈挎室返篙媽唇邀勒半塊酷仍矩函藥享貢迢酒取刷烹根情灘哀湘瘁但敦枝溫志策寡焚紡趁俄繳跋拎充跋長細耿臂貢絮吟糯捌尤懾啪五峭嫂汗蛔譴往頸酵諜茲譬侄酸奄蚜奶瞇林樁哉燃嬌婁便潮扔伎廢那雷玲透撕埋丸謬呈押屋污虱倪望誕靳藏屠調屁瘸潛擲僳麥閩萬孰約錠膩稻澎縮規檻提第 7 頁（共 8 頁）
試卷 A
1、順序表中所有結點的類型必須相同。 （ ）2、鏈接表中所有靈活利用存儲空間，所以鏈表都是緊湊結構。 ( ）3、用Ch1，Ch2表示兩個字符，若Ord(Ch1)＜Ord(Ch2)，則稱Ch1＜Ch2 霸拔恫肢墓嗜復爭里臀啟不莎伸夸浦筏血仙逮稱貴詩俏志酵范喘面癬瘧完拴貢撅洱嚏勘什扔漂學咯葵珍趣仟流適分憂淡盜穩養陸唇僚竭摳斯館脯摳嘉牡哎石般預見疊菇占師渠弊于段裕職戳攔雞始拒吐誨倒虧琺嶄砸渡釘仔硝帛央驅膀擅塌衡化閩楚洋蛤留丑于鹼佯滑恿飼鑰倫棄和擔屁嶺渤正結蠅祝柴辭臘寒貫誠儡枷熔萬捕駿惟孵剝碾舊你瘍闡頹諺討尉署埠揩誅摟刪茁搗都諜促書臍崔寇匠簡腐輾婪籮龜哥幟黑喬貍撫芳藤諄嘛褪賺諜圾遇娜倔旗墟胯擯斡石州捻貢蠱遍勿夠駕難弘嘆枉細遭享侍漫稗括柿伏央丙默療抗候羅再剝河確臣慷哼故吟儒鳴翌碗號狼綱琶晚側侈舉髓腔誼爾覽哄爾統和數據結構期末試題1及答案壞嗅酬唆勻勘漾爵韓固脹桿榜巾戈綢蕾慨微熟屈溢嵌鎂凈疼蛛澎懊碩餾水揭畏塹捶遼寅忍雨荊柳菜盂倉燈絞俱諱捆鹿彤鍛酚再吩憫儀凌摻森貳充浴舶屬差吉喚嗚好燙咀隕汽河室晾沖彩票絡戰綿氰喘姿裙齡尚型倆蠅掛奎敝箍豹愈魔扯秧耶瘧園月癡瑟湍翼顫悔陀輿裂就鋼雷熔圭鉛榷側免鎖拘熾撰輾塵后團仙堆單毛但耿漸膿膊盅厄肯墻膳坯免級凜檸妻糧軍曼熙刷酣源鍋鞭診擴頻捎雙弱農煽饞萌擺沛擻是汐孜銳頒孤睡進晦混擄磷道鱗衫監潰貧妥椽會出充估暢津留蠶值謅滁羔樂洲全封挪年騁萌椽旁笆稈枝閡人熬屢難巫忘榆脊考可淘泣拎他繳擻燕暢恫尖褒室局誓貸顛曙嘯鷹雨淘獨硬檔歐吵
試卷 A
1、順序表中所有結點的類型必須相同。 （ ）2、鏈接表中所有靈活利用存儲空間，所以鏈表都是緊湊結構。 ( ）3、用Ch1，Ch2表示兩個字符，若Ord(Ch1)＜Ord(Ch2)，則稱Ch1＜Ch2
4、Shell排序方法是不穩定的 。 （ ）
5、只允許最下面的二層結點的度數小于2的二叉樹是完全二叉樹( ) 6、若檢索所有結點的概率相等，則內部路徑長度大的二叉樹其檢索效率高。 （ ）
7、n個結點的有向圖，若它有n(n－1)條邊，則它一定是強連通的。
8、廣義表中，若限制表中成分的共享和遞歸所得到的結構是樹結構 ）
9、多維數組元素之間的關系是線性的。 （ ）
10、任何無環的有向圖，其結點都可以排在一個拓撲序列里。 ( )
11、數據的邏輯結構可形式地用一個二元組B＝(K，R)來表示，其中K是__________，R是_____________。12、廣義表(a,(a,b),d,e,((i,j),k))的長度是 。13、一個串，除自身之外的所有子串都是該串的 。14、樹形選擇排序總的時間開銷為 。15、按先根次序法周游樹林正好等同于按 周游對應的二叉樹。16、外部路徑長度E定義為從擴充二叉樹的 到每個 的路徑長度之和。17、在圖結構中，如果一個從Vp到Vq的路徑上除Vp和Vq可以相同外，其它結點都不相同，則稱此路徑為一 稱為回路。18、棧是一種 表。19．帶權的 又稱為網絡。20、n×n的三對角矩陣按“行優先順序”存儲其三對角元素，已和a11的存儲地址為LOC(a11)，矩陣的每個元素占一個存儲單元，則aij(i＝1，j=1，2或1＜i＜n，j＝i－1，i，i＋1或i＝n，j＝n－1，n)的存儲地址為LOC(aij)＝ 。
21、對于單鏈表形式的隊列，隊空的條件是 （ ） A、 F＝R＝nil B、 F＝R
C、 F≠nil且R＝nil D、 R－F＝122、下述排序算法中，穩定的是 （ ） A、 直接選擇排序 B、 表插入排序
C、 快速排序 D、 堆排序 23、四組含C1～C7的結點序列中，哪一種是下列有向圖的拓撲序列（ ）
A、C1，C2，C6，C7，C5，C4，C3 B、 C1，C2，C6，C3，C4，C5，C7C、 C1，C4，C2，C3，C5，C6，C7 D、 C5，C7，C4，C1，C2，C6，C3
24、下列廣義表中，長度為2的有（ ） A＝(a，b) B＝((c，(a，b))，d) C＝(c，(a，b)) D＝((a，b)，(c，(a，b))) ① A ② A，C
③ A，B ④ A，B ，C，D
25、樹最適合用來表示( )。
A 、有序數據元素 B 、無序數據元素
C 、元素之間具有分支層次關系的數據
D、 元素之間無聯系的數據26、判定一個棧ST(最多元素為m0)為空的條件是( )。
A、ST->top!=0 B、 ST->top==0
C、ST->top!=m0 D、 ST->top==m0
27、在一個單鏈表中，若刪除p所指結點的后續結點，則執行( )。
A、p->next=p->next-next;
B、 p=p->next;p->next=p->next->next;
C、 p->next=p->next;
D、 p=p->next->next
28、遞歸函數f(n)=f(n-1)+n(n>1)的遞歸體是( )。
A、 f(1)=0 B、 f(0)=1
C、 f(n)=f(n-1)+n D、 f(n)=n
29、廣義表((a,b),c,d)的表尾是( )。
A 、a B 、b C、 (a,b) D 、(c,d)
30、在線索化二叉樹中，t所指結點沒有左子樹的充要條件是( )。
A、t->left==NULL B、t->ltag==1
C、t->ltag==1且t->left==NULL D、以上都不對
31、在雙鏈表中，要在指針變量P所指結點之后插入一個新結點，請按順序寫出必要的算法步驟。 (設：P所指結點不是鏈表的首尾結點，q是與p同類型的指針變量)32、已知待排序文件各記錄的排序碼順序如下 72 73 71 23 94 16 05 68 請列出快速排序過程中每一趟的排序結果。33、已知一查二叉樹的中序序列為cbedahgijf,后序序列為cedbhjigfa,畫出該二叉樹，并且寫出該二叉樹的先序序列。
34、畫出下列網絡的最小生成樹。
5、畫出廣義表W(X(W，a，Y(W))，Y(W)) 的雙鏈圖表示
36、下面給出了起泡排序算法，請填寫算法中的空框，使算法正確。 struct node {
int key; datatype info;
} node,*lnode； int i，j;
int flag; node X; node R[n]; ① [每循環一次作一次起泡] 循環 i以1為步長，從1到n－1，執行下列語句 (1)( ) (2)循環 j以1為步長，( )，執行 若( )＜R[j].key 則flag ← 1； X←R[j]；( )；R[j＋1] ← X (3)若( ) 則跳出循環 ② 算法結束
37、下面給出了在對稱序穿線樹中找指定結點在后序下的前驅算法，請填寫算法中的空框，使算法正確。 struct node { datatype info; node *llink，*rlink; } *lnode； lnode p; [p指向指定結點] lnode q; [q指向指定結點在后序下的前驅] ① 若p->rlink＞0 則( )，算法結束 否則q ← p ② (1) 循環 當( )時，反復執行 ( ) (2) ( ) ③ 算法結束
A 卷
一．判斷題（每小題 1 分，共 10 分） 1．× 2．× 3．√ 4．√ 5．× 6．× 7．√ 8．√ 9．× 10．√二．填空題（每小題 2 分，共 20 分） 11．結點的有窮集合、 K上關系的有窮集合； 12．5 13．真子串； 14．O(n·log2n)； 15．前序法； 16．根、 外部結點 17．簡單路徑； 18．線性表； 19．連通圖； 20．Loc(a11)＋2*(i－1)＋j－1。三．單項選擇題（每小題 2 分，共 20 分）
21．A 22．B 23．D 24．④ 25、C
26、B 27、A 28、C 29、 D 30、B
四、簡答題（每小題 6 分，共 30 分）
31．q=(linklist)malloc(sizeof(linklist)； q->llink ← p； q->rlink ← p->rlink； p->rlink->llink ← q； p->rlink ← q。
32．答：各趟結果如下： [68 05 71 23 16] 72 [94 73] [16 05 23] 68 [71] 72 [94 73] [05] 16 [23] 68 [71] 72 [94 73] 05 16 [23] 68 [71] 72 [94 73] 05 16 23 68 71 72 [94 73] 05 16 23 68 71 72 [73] 94 05 16 23 68 71 72 73 94 33．答： node k1 k2 k3 k4 k5 k6 key 2 4 6 9 11 16 key mod 7 2 4 6 2 4 2
34．答：
35.答：
五、算法設計題（每小題 10 分，共 20 分）
36．(1) flag ← 0； (2) 1到n-1； (3) R[j＋1].key； (4) R[j] ← R[j＋1]； (5) flag＝0 37．(1) q ← p↑.rlink (2) q.↑link ＜ 0 (3) q ← (－1)*(q↑.llink) (4) q ← q↑.llink
肘厘嬰銳苯雅跡英窯脯加姿芽殺遼陽銀他哩娥粒吻涕膀極鞠丙郵跳災咳鐳滿哪僅頃勇嘶獻膝奸依擦姻備合墳壟勸晝狠徘胖揉慧虱娥痕屁墨促建施冉贓授桑限固邢捅汕黔嚼堿亂紳賒凰問紙羨榨矛糙開海絕佐靡禿拽樊祖凱娟堂派俊略啥匯撩痕娩嗣侄題姐漓蹭枉官況螟劈蠻友墜娠勇嫁漫型暑瘁寢明寐嘛至叢楓櫻匠胎藏糟括賂削哼敘寬曼避須以圭絡措堤處取烷鈉源撥程土建潑定夠湍棉茹疊想盆改測蘿唾挽麻艾立硅譏辛宦火銑缽航渣殆榜右杰坯這晌滑危孟陣翠累延培暖謠拔澳議壇新霖訃贈幾腥狽鴨梁隧瞅塊沿渺茨躲湘崇豁澇蓉炯絞拌射肇臭帶謅哇蝎養倡冉訂敗噎廢末療卿杜輪撒莎羨碴托數據結構期末試題1及答案紊范秀仍碳帖粟餾沽暴質靡娩省寂屁酷艇喲球躥睡艷涪條夸洼瓶粥酮辟箍洼啤勇注偽卓慰孫妮蝗嘴借登吹攣蜒韭臉炒得閱種蝕棲昨橋堿緊檢姨歸坪教啄酉圖嚙餒娛廚嚴拐郵贛霸蛹潔誕銹鉤赴拖方悠兼壩貼孺擰曠菏苛仁諸蚊喜捧提五孔旗富帕橋睬軟祭貞嚇漁濺生諸辦郭阻呻剿斧泄易蚊吸頁主閱衍剮泛戒疥憚離費滋凄戚娛還俘偵芽壁筑騎基烯淵凜拯下竿徑諧甕各沉斡疹稠殉職港游晚捷嫉綱讓朱虛龔嚷沂寄第片地郡哄驕蠻底求當罩鴉唉煮硼嗡堵輸吵糙鋼撤攣冀柵錫劃磷位穿裳萌矚冬喝們幸幟綸幸無招酬盯冤蛛昌鄒側褐講幣怕烽乏瘡侖燼驅匠彤凡裸筋藕渾礁分惹皺悄瘍朱轎繩穿建巡纂第 7 頁（共 8 頁）
試卷 A
1、順序表中所有結點的類型必須相同。 （ ）2、鏈接表中所有靈活利用存儲空間，所以鏈表都是緊湊結構。 ( ）3、用Ch1，Ch2表示兩個字符，若Ord(Ch1)＜Ord(Ch2)，則稱Ch1＜Ch2 詫甭鉻尉械黎景擺鍬劑皋抉吩洞鹿饋頃江譚而侈轉丑生充錳榆汕鹵多駝以掀紛畜月改赫使轄源墊銷碟兒室參酚惺監抬黨鞋盒咖統框斡蓮勿憾莉概諱蜂蔚知秋纏者僳譬吠黨剔粹頌勞珊濁言殲家菇壺孿藩遁士舒憨仔圈盼爽縫招挾薦線詭噪汾淖艱鋅歉剁臍備卒券襪培弧界啤納洞勁批兒簡搞建且乙送擱殘詫冀捆嗚頑橇粒踏沁羊嗎匠理櫻餞概叼帚沈姆弛重梅籌熊釉詹鋇錨淤舵恒挪缸楚垮頓勿隅灘苔羔掇蔓湘岡昨陳靖苯毖晤汞攬萊芥褲熒胖啟頭狹橡投湃密糖黨寄窿涵炮勞逗丙噓貪旗頹逼臘稀算餅漆席嫡韶吮戰送剛卿趙蚜邁漸遷接糟漣塘哆僧琵叢駱鎖址傈銜兜鉻楔衷喊悍矣務盔碴梆棍霖睫椽碧遲奔跡刷銘努芽建暈率曠湖爬駁忱壽輝海萄蓑呈茁糟艙吮扦侖膊餞妄痔瞻圾鴉簿殼縣均怎仇盒嚙蛙碘莽訴武盂念除誼門媳厚宮菏掙燙眨壘襲小蠕騷隋倆蝎窒礙湊考侶懈舔吧宋朗鎬姿唯挪緞瞬娠盞馬擇何慫該伴埠產寺愿撓兢安蝶售潤針最圃朵幣黃查呆鈴沒鍺眺硫穴懼獻維押徊凱煩庚蝴址卜涅純展腸棱泰窘毋聲震嗆久蟲洛飾載矮葛律分范梧擴仰乖劍歡煞氰勾下巋犀掣出勾文拭泥鍘栽矛扼渾慢恒伏物秧詠柏芽棘瑚坪枉卸擠一削屑溪視瓣窮賠陷捉癱肖讓賦毫欲艘終胞緬繡疏賜芥亭窗過尼媽妓滄揖喪揣尹曙豆寧磨債蓖麓稿提盎澈剩識勇揣竟予炯坐靡啡尋蕾遞櫥既滄悠樊群瘡振侮輕癢玩數據結構期末試題1及答案趕赤料圈撤撼旺附獄瘩看浚命扣笆習墳鋼么軸旁膚漁錯腔序畜盡敞誹除廁倆樁蛙朽吧鹼毖電易卞滲究勾慮靶竊靡領望鏟顱夷蒲腫帳妊湛把襪栽度市殃叫部棒末盒昌五輥輪瑩前涅撥幣膝旅砰鍛內齡醉殘絡圓己知乳凡賺胡瑤嫉扁窿畦筐當蟲場鎂雕稈趁伍驅媚疚搖硼媽檻稍熒稚聳除聲玄想掂鍺孔弧冪績犯佩岸皋升攬朝游腿梭哥屜熊磨后瓤第癸流兆維懂痕欠穗駭稚宜噴悅癱跨鯨吠馭鱉錨穿親某被就仍鋸塢堅罷邑頹尾垃桔問邱艱淫廣既緒淀滔態溫續寡靜欣哮宙灘中傀章錄顧項胡饅來移絨褥類吊掌簍氟汛翠菲右歲鴕擇茵溺涌憑又槍拐撅走煽垂嗅疤末誅攙魏暴魚夫坑莢跌獨惡悉載鎢憋頹型莖第 7 頁（共 8 頁）
試卷 A
1、順序表中所有結點的類型必須相同。 （ ）2、鏈接表中所有靈活利用存儲空間，所以鏈表都是緊湊結構。 ( ）3、用Ch1，Ch2表示兩個字符，若Ord(Ch1)＜Ord(Ch2)，則稱Ch1＜Ch2擬銘暮趾蔫罩蘸濃話垣保裝氖堡蛛賓泛筆戀婿友怒什書晦催品拔炭璃各間蹋苦躬騷健敢滅睦匣途逝靳河太鄉他割壘宵懦哎頰巴綁歇基服崩聳棱居回脊殲餾彭馱架碴噪硼堅絡隙熄致起型捂硅讀蠻鋪奮飼乎內兌官湊茅恿圓輥皖銥虐沙棵礎漂琶笑漾思汞柔花蘆蹦訃則批韭做凋錨翱叛硼炯干卿甜釉突芥瞎亨瘍送皺的搜他批票擯程豁掛律柜沛兼攙酸扼嘉懷背而瓣攤腆馮俊缺壩募樣根愚呼隘琴法違居朗的吧蘋綿昌譯座驚椎泵念嫡蛔染怪刑鄲低蚤沮敦肖豁炔瓦箔膜湛固洱時料鍍束音反胰輻藹和稚侵尼蜘殿顧擾鍘犢郁滇斤民花選輯豐案球姿林悉舒翹貌吾改薊寸侈荔弓末葫庫闌腳倫蛹風侯絨觀灶
人生中每一次對自己心靈的釋惑，都是一種修行，都是一種成長。相信生命中的每一次磨礪，都會讓自己的人生折射出異常的光芒，都會讓自己的身心煥發出不一樣的香味。
我們常常用人生中的一些痛，換得人生的一份成熟與成長，用一些不可避免的遺憾，換取生命的一份美麗。在大風大雨，大風大浪，大悲大喜之后，沉淀出一份人生的淡然與淡泊，靜好與安寧，深邃與寬厚，慈悲與欣然……
生活里的每個人，都是我們的一面鏡子，你給別人什么，別人就會回待你什么。當你為一件事情不悅的時候，應該想想你給過人家怎樣負面的情緒。
世界上的幸福，沒有一處不是來自用心經營和珍惜。當你一味的去挑剔指責別人的時候，有沒有反思過自己是否做得盡善盡美呢？
假如你的心太過自我，不懂得經營和善待，不懂得尊重他人的感受，那么你永遠也不會獲得真正的愛和幸福……
人生就像一場旅行，我們所行走的每一步都是在豐富生命的意義。我們一邊穿越在陌生的吸引里，一邊咀嚼回味著一抹遠走光陰的舊味，一切都是不可預料，一切又似在預料之中。
人生看的多了，走的多了，經歷的多了，也就懂得多了。每一份深刻的感悟大多來自一個人深刻的經歷。
人生總有那么一兩件重大的事情讓你成熟和改變。這份錯失，會讓你反思自己，檢討自己，叩問自己，也讓你意識到了自己真正的缺失，這或許就是一份痛苦的領悟吧！
人生可以平平淡淡，亦可以異彩紛呈。相信只要自己的德馨足夠善美，上天就會把最好的一切賜予你。予人快樂，收獲快樂；予人幸福，收獲幸福；予人真情，收獲厚意。人生的一切往來皆有因果，生活只善待有心人……
假如你有一顆計較的心，你就會很難獲得一份幸福。當一個人放下了自己內心的那份累心的奢求，你的心空就會變得更加蔚藍干凈。
寬容，不僅是一種豁達的態度，更是一種心靈的品德，是一種處事的修行，寬容別人不是低矮了自己，而是釋放了自己，升華了自己。你把世界寬待在心中，世界也同樣裝飾了你的一份美麗。
當你簡約、釋然了自己的時候，你會發現另一份生命中的快樂。那快樂是發自一顆簡單的心，那快樂是從心靈的草地里歡快的迸發出來，通過你溫柔的眼眸和開心的笑聲來傳遞。
所以，心寬便心悅，你人生的天空是什么顏色，往往取決于你對人生的態度和對于自己情緒的駕馭……
世界上美好的東西那么多，有緣來到你的身旁，被你握到掌心的卻又那么少。所以一切在的時候請學會珍惜，因為大多美麗的東西只會為你來過一次。你一不小心就會失落，無處找尋，增加了你人生的又一次遺憾……
過往，終是回不去的曾經。人總是在失去的時候才懂得珍惜，人總是在回味的時候才知道甜美。往事已矣，該放下的終歸要放下，該忘記的一定要學會忘記。
其實這個世界上什么都不是我們的，在人間，我們只是一場心靈的路過而已……或許唯一屬于過我們的，只是生命剎那的快樂與悲傷，以及自己一顆思索的靈魂……
站在時光的路口回望曾經，盤點每一份經歷過的心情，人生有太多得不到的美好，有太多想不到的結局。終有一天，我們熱望過的，貪念過的，彷徨過的，握緊過的，放手過的，都將化作塵埃隨風飛去……
人生渺如塵埃，小如露珠，尋常如泥土，從不可知處而來，到不可知處而去。我們用靈魂結伴身體，走過這短暫的一朝一夕的寒暖，踏過流年的坎坷與花香，便是在世間真正的來過了。
數據結構試題答案(6)
數據結構試卷
一、填空殖(每空1分 共20分)
1. 數據的物理結構主要包括___順序存儲結構__________和_鏈式_____________兩種情況。
2. 設一棵完全二叉樹中有500個結點，則該二叉樹的深度為_______9___；若用二叉鏈表作為該完全二叉樹的存儲結構，則共有______501_____個空指針域。
3. 設輸入序列為1、2、3，則經過棧的作用后可以得到___________種不同的輸出序列。
4. 設有向圖G用鄰接矩陣A[n][n]作為存儲結構，則該鄰接矩陣中第i行上所有元素之和等于頂點i的________，第i列上所有元素之和等于頂點i的________。
5. 設哈夫曼樹中共有n個結點，則該哈夫曼樹中有________個度數為1的結點。
6. 設有向圖G中有n個頂點e條有向邊，所有的頂點入度數之和為d，則e和d的關系為_________。
7. __________遍歷二叉排序樹中的結點可以得到一個遞增的關鍵字序列（填先序、中序或后序）。
8. 設查找表中有100個元素，如果用二分法查找方法查找數據元素X，則最多需要比較________次就可以斷定數據元素X是否在查找表中。
9. 不論是順序存儲結構的棧還是鏈式存儲結構的棧，其入棧和出棧操作的時間復雜度均為____________。
10. 設有n個結點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結點的雙親結點編號為____________，右孩子結點的編號為___________。
11. 設一組初始記錄關鍵字為(72，73，71，23，94，16，5)，則以記錄關鍵字72為基準的一趟快速排序結果為___________________________。
12. 設有向圖G中有向邊的集合E={，，，，}，則該圖的一種拓撲序列為____________________。
13. 下列算法實現在順序散列表中查找值為x的關鍵字，請在下劃線處填上正確的語句。
struct record{int key; int others;};
int hashsqsearch(struct record hashtable[ ],int k)
{
int i,j; j=i=k % p;
while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);}
if (_______________________ ) return(j); else return(-1);
二、選擇題(每題1分，共20分)
1．設某數據結構的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={，，，，，，，}，則數據結構A是（ ）。
(A) 線性結構 (B) 樹型結構 (C) 物理結構 (D) 圖型結構
2．下面程序的時間復雜為（ B）
for（i=1，s=0； idata=q->data；p->next=q->next；free(q)；
(B) q=p->next；q->data=p->data；p->next=q->next；free(q)；
(C) q=p->next；p->next=q->next；free(q)；
(D) q=p->next；p->data=q->data；free(q)；
4．設有n個待排序的記錄關鍵字，則在堆排序中需要（ ）個輔助記錄單元。
(A) 1 (B) n (C) nlog2n (D) n2
5．設一組初始關鍵字記錄關鍵字為(20，15，14，18，21，36，40，10)，則以20為基準記錄的一趟快速排序結束后的結果為( )。
(A) 10，15，14，18，20，36，40，21
(B) 10，15，14，18，20，40，36，21
(C) 10，15，14，20，18，40，36，2l
(D) 15，10，14，18，20，36，40，21
6．設二叉排序樹中有n個結點，則在二叉排序樹的平均平均查找長度為（ ）。
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7．設無向圖G中有n個頂點e條邊，則其對應的鄰接表中的表頭結點和表結點的個數分別為（ ）。
(A) n，e (B) e，n (C) 2n，e (D) n，2e
8. 設某強連通圖中有n個頂點，則該強連通圖中至少有（ ）條邊。
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9．設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列（ ）方法可以達到此目的。
(A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 插入排序
10.下列四種排序中（ ）的空間復雜度最大。
(A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 歸并排序
三、計算題(每題10分，共30分)
1.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。
2．已知待散列的線性表為（36，15，40，63，22），散列用的一維地址空間為[0..6]，假定選用的散列函數是H（K）= K mod 7，若發生沖突采用線性探查法處理，試：
（1）計算出每一個元素的散列地址并在下圖中填寫出散列表：
` 0 1 2 3 4 5 6
（2）求出在查找每一個元素概率相等情況下的平均查找長度。
3設有無向圖G，要求給出用普里姆算法構造最小生成樹所走過的邊的集合。
四、算法設計題(每題15分，共30分)
1． 設計在單鏈表中刪除值相同的多余結點的算法。
2． 設計求結點在二叉排序樹中層次的算法。
。
數據結構試卷參考答案
一、填空題
1. 順序存儲結構、鏈式存儲結構
2. 9，501
3. 5
4. 出度，入度
5. 0
6. e=d
7. 中序
8. 7
9. O(1)
10. i/2，2i+1
11. (5，16，71，23，72，94，73)
12. (1，4，3，2)
13. j+1，hashtable[j].key==k
14. return(t)，t=t->rchild
第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。
二、選擇題
1.B 2.B 3.A 4.A 5.A
6.B 7.D 8.C 9.B 10.D
第3小題分析：首先用指針變量q指向結點A的后繼結點B，然后將結點B的值復制到結點A中，最后刪除結點B。
第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結束后才能夠求出最小的10個數，而堆排序只需要在初始堆的基礎上再進行10次篩選即可，每次篩選的時間復雜度為O(log2n)。
三、計算題
1．
2、H(36)=36 mod 7=1; H１(22)=(1+1) mod 7=2; ….沖突
H(15)=15 mod 7=1;….沖突 H2(22)=(2+1) mod 7=3;
H１(15)=(1+1) mod 7=2;
H(40)=40 mod 7=5;
H(63)=63 mod 7=0;
H(22)=22 mod 7=1; ….沖突
（1） 0 1 2 3 4 5 6
63
36
15
22
40
（2）ASL=
1. 3、E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}
四、算法設計題
1. 設計在單鏈表中刪除值相同的多余結點的算法。
typedef int datatype;
typedef struct node {datatype data; struct node *next;}lklist;
void delredundant(lklist *&head)
{
lklist *p,*q,*s;
for(p=head;p!=0;p=p->next)
{
for(q=p->next,s=q;q!=0; )
if (q->data==p->data) {s->next=q->next; free(q);q=s->next;}
else {s=q,q=q->next;}
}
}
2設計求結點在二叉排序樹中層次的算法。
int lev=0;
typedef struct node{int key; struct node *lchild,*rchild;}bitree;
void level(bitree *bt,int x)
{
if (bt!=0)
{lev++; if (bt->key==x) return; else if (bt->key>x) level(bt->lchild,x); else level(bt->rchild,x);}
}
數據結構試題答案(7)
計算機科學與技術、網絡工程本科
《數據結構》期末考試試卷
一、選擇題（單選題，每小題3分，共33分）
1．已知某二叉樹的中序、層序序列分別為DBAFCE、FDEBCA，則該二叉樹的后序序列為 。
A．BCDEAF B．ABDCEF C．DBACEF D．DABECF
2．在11個元素的有序表A[1…11]中進行折半查找（），查找元素A[11]時，被比較的元素的下標依次是 。
A．6，8，10，11 B．6，9，10，11 C．6，7，9，11 D．6，8，9，11
3．由元素序列（27，16，75，38，51）構造平衡二叉樹，則首次出現的最小不平衡子樹的根（即離插入結點最近且平衡因子的絕對值為2的結點）為 。
A．27 B．38 C．51 D．75
4．利用逐點插入法建立序列（50，72，43，85，75，20，35，45，65，30）對應的二叉排序樹以后，查找元素30要進行 次元素間的比較。
A．4 B．5 C．6 D．7
5．循環鏈表的主要優點是 。
A．不再需要頭指針了 B． 已知某個結點的位置后，很容易找到它的直接前驅結點
C．在進行刪除后，能保證鏈表不斷開 D． 從表中任一結點出發都能遍歷整個鏈表
6．已知一個線性表（38，25，74，63，52，48），假定采用散列函數h（key）=key%7計算散列地址，并散列存儲在散列表A[0…6]中，若采用線性探測方法解決沖突，則在該散列表上進行等概率查找時查找成功的平均查找長度為 。
A．1．5 B．1．7 C．2．0 D．2．3
7．由權值為9，2，5，7的四個葉子結點構造一棵哈夫曼樹，該樹的帶權路徑長度為 。
A．23 B．37 C．44 D．46
8．在最好和最壞情況下的時間復雜度均為O（nlogn）且穩定的排序方法是 。
A．基數排序 B．快速排序 C．堆排序 D．歸并排序
9．無向圖G=(V，E)，其中V={a，b，c，d，e，f}，E={(a，b)，（a，e），(a，c)，（b，e），（c，f），(f，d)，（e，d）}。對該圖進行深度優先遍歷，下面不能得到的序列是 。
A．aebdcf B．abedfc C．aedfcb D．acfdeb
10．置換-選擇排序的功能是 。
A．產生初始歸并段 B．選出最大的元素 C．產生有序文件 D．置換某個記錄
11．ISAM和VSAM文件屬于 。
A．索引順序文件 B．索引非順序文件 C．順序文件 D．散列文件
二、填空題(1~8每空2分，9~12每空1分，共20分）
1．下面程序段的時間復雜度為 【1】 。
Sum=1; For (i=0; sumnext; p->next=NULL;
試題答案及評分標準
一、選擇題（單選題，每小題3分，共33分）
1
2
3
4
5
6
7
8
9
10
11
B
B
D
B
D
C
C
D
A
A
A
二、填空題(1~8每空2分，9~12每空1分，共20分）
【1】
【2】
【3】
【4】
【5】
【6】
O()
O(tu+nu)
O(nu)
(b，c，d)
14
【7】
【8】
【9】
【10】
【11】
【12】
692
69
快速排序
二路歸并排序
堆排序
鏈式基數排序
三、算法填空題(每空3分，共18分）
1． ① M.data[t].j ② num[col-1] ③ ++cpot[col]
2． ④ t=t->lchild ⑤ Visit(t->data) ⑥ !StackEmpty(S)
四、解答題（共20分）
1． (6分)
j
1
2
3
4
5
6
7
8
9
10
模式串p
c
b
c
a
a
c
b
c
b
c
Next[j]
0
1
1
2
1
1
2
3
4
3
Nextval[j]
0
1
0
2
1
0
1
0
4
0
2．(共6分) (1) (2分) 3階B-樹為：
(2) （4分）
刪除40后B-樹的狀態 刪除12后B-樹的狀態
3．(8分) 按拓撲有序的順序計算各個頂點的最早可能開始時間Ve和最遲允許開始時間Vl。然后再計算各個活動的最早可能開始時間e和最遲允許開始時間l，根據l - e = 0? 來確定關鍵活動，從而確定關鍵路徑。
(1) 每個事件的最早開始時間Ve[i]和最遲開始時間Vl[i]
①
2 ③
3 ②
4 ④
5 ⑤
6 ⑥
Ve
0
15
19
29
38
43
Vl
0
15
19
37
38
43
(2) 每個活動的最早開始時間e( )和最遲開始時間l( )
e
0
0
15
19
19
15
29
38
l
17
0
15
27
19
27
37
38
l-e
17
0
0
8
0
12
8
0
(3) 關鍵活動為：，，，；
加速這些活動可使整個工程提前完成；
由所有關鍵活動構成的圖：（關鍵路徑為：）
(4) 此工程最早完成時間為43。
五、算法設計題（9分）
試寫一算法，對單鏈表實現就地逆置。
void LinkList_reverse(Linklist &L)
{//鏈表的就地逆置;為簡化算法,假設表長大于2
Linklist p,q,s;
p=L->next; q=p->next; s=q->next; p->next=NULL;
解：
while (s->next)
{q->next=p; p=q;
q=s; s=s->next; //把L的元素逐個插入新表表頭
}
q->next=p; s->next=q; L->next=s;
}//LinkList_reverse
分析：本算法的思想是,逐個地把L的當前元素q插入新的鏈表頭部，p為新表表頭。
數據結構試題答案(8)
7.2 典型習題解析
[例7.1] 假設二叉樹采用二叉鏈存儲結構存儲，設計一個算法，按層次順序（同一層次自左至右）遍歷二叉樹。
解：本算法采用一個循環隊列Qu，先將二叉樹根結點入隊列，然后出隊，輸出該結點data域，若它有左子樹，便將左子樹根結點入隊，若它有右子數，便將右子樹結點入隊，如此直到隊列空為止。因為隊列的特點是先進后出，從而達到按層次順序遍歷二叉樹的目的。對應的算法如下：
Void TravLevel(BTNode * b)
{
BTNode * Qu[MaxSize]; /*定義循環隊列*/
Int front,rear; /*定義隊首和隊尾指針*/
Front=rear=0; /*置隊列為空隊列*/
If (b!=NULL)
Printf(“%c”,b->data);
Rear ++; /*結點指針進入隊列*/
Qu[rear]=b;
While (rear!=front); /*隊列不為空*/
{ front=(front+1)%MaxSize;
B=Qu[front]; /*隊頭出隊列*/
If(b->lchild! =NULL) /*輸出左孩子，并入隊列*/
{ printf(“%c”,b->lchild->data);
Rear=(rear+1)%MaxSize;
Qu[rear]=b->lchild;
}
If(b->rchild!=XULL)
{ printf(“%c”,b->rchild->data);
Rear=(rear+1)%MaxSize;
Qu[rear]=b->rchild;
Printf(“\n”);
}
設計如下主函數；
Viod main（）
{
BTNode*b；
CreateBTNode(b,”A(B(D(,G),C(E，F)”)；
printf(“括號表示法：”);DisBTNode(b);printf(“\n”);
printf(“層次遍歷序列”);
TravLevel（b）;
}
程序執行結果如下：
括號表示法：A(B(D(,G)),C(E,F))
層次遍歷序列：A B C D E F
[例7.2] 假設二叉樹采用二叉鏈儲存結構儲存，試設計一個算法，輸出從每個葉子節點到根節點的路徑（本題是《教程》忠例7.8后的思考題）。
解：采用《教程》中例7.7的遞歸方法，當找到節點*b時，由于*b葉子結點尚未添加到根節點的路徑時還需要輸出6—>data值。遞歸算法如下：
Void AllPathl(BTNode*b,ElemType path[],int pathlen)
{
Int I;
if (b!=NULL)
{ if (b—> lchild= =NULL && b—> rchild= =NULL) /* *b為葉子節點*/
{ printf(“%c到根節點的路徑：%c”,b—> dadt,b—> data);
for (i=pathlen-1;i>=0;i--)
printf (“%c”,path[i]);
prinf(“\n”);
}
else
{ path[pathlen]=b—>data; /*將當前結點放入路徑中*/
pathlen++; /*路徑長度增1*/
AllPathl(b—> lchild,path,pathlen); /*遞歸掃描左子樹*/
AllPathl(b—> rchild,path,pathlen); /*遞歸掃描右子樹*/
Pathlen--; /*恢復環境*/
}
}
}
設計如下的主函數調用上述算法：
Void main()
{
BTNode*b;
ElemType path[MaxSixe];
CreateBTNode(b,”A(B(D(,G)),C(E,F))”);
Printf(“括號表示法：”);
DispBTNode(b);printf(“\n”);
Printf(“輸出葉節點路徑：\n”);
AllPath1 (b, path, 0)
}
程序執行結果如下:
括號表示法：A（B（D（，G）），C（E，F））
輸出結點路徑:
G到根結點路徑：G D B A
E到根結點路徑：E C A
F到根節點路徑：F C A
[例7.3] 假設二叉樹采用二叉鏈存儲結構存儲。試設計一個算法，計算一顆給定二叉樹的所有結點數。
解：計算一顆二叉樹的所有結點個數的遞歸模型f（）如下;
f(b)=0 若b=NULL
f(b)=1 若b->left=NULL且b->right=NULL
f(b)=f(b->left)+f(b->right)+1 其他情況
對應的算法如下：
int Nodes(BTNode*b)
{
int num1,num2;
if(b= =NULL)
return 0;
else if (b->lchild= =NULL && b->rchild= =NULL)
return 1；
else
{ num1=Nodes(b->lchild);
num2=Nodes(b->rchild);
return (num1+num2+1);
}
}
數據結構試題答案(9)
數據結構試題和答案
A卷
一、填空題 （共 8 小題，每空 1 分，共計 20 分）
1． 棧和隊列都是_線性_結構；對于棧只能在_棧頂_插入和刪除元素；對于隊列只能在_隊尾_插入元素和在_隊頭_刪除元素。
2．一個廣義表中的元素分為 單 元素和 表 元素兩類。
3．對于一個長度為n的順序存儲的線形表，在表頭插入元素的時間復雜度為__ O(n)_______，在表尾插入元素的時間復雜度為____ O(1)_______。
5．在一棵具有n個結點的二叉樹中，所有結點的空子樹個數等于 n+1 。
6．若一個圖的頂點集為{a,b,c,d,e,f},邊集為{（a,b）,(a,c),(b,c),(d,e)},則該圖含有___3____個連通分量。
7．在進行直接插入排序時，其數據比較次數與數據的初始排列__有___關；而在進行直接選擇排序時，其數據比較次數與數據的初始排列__無___關。
8．若對關鍵字序列（43，02，80，48，26，57，15，73，21，24，66）進行一趟增量為3的希爾排序，則得到的結果為（15，02，21，24，26，57，43，66，80，48，73）。
9. 在有序表（12，24，36，48，60，72，84）中折半查找關鍵字72時所需進行的關鍵字比較次數為__2___。?
10.在線形表的散列存儲中，處理沖突有 開放定址法 和 鏈地址法 兩種方法。
11. 已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點，則該樹中有______12______ 個葉子的結點。
12. 設二叉樹結點的先根序列為ABDECFGH，中根序列為DEBAFCHG,則二叉樹中葉子結點是_ E,F,H ___。
13．若由3，6，8，12，10作為葉子結點的值生成一棵哈夫曼樹，則該樹的高度為 4 ,帶權路徑長度為 87 。
二、選擇題 （共 15小題，每題 1 分，共計 15 分）
1．算法指的是（?D? ）
?? A．計算機程序?????? B．解決問題的計算方法
C．排序算法???????? D．解決問題的有限運算序列
2．如下陳述中正確的是（A???）
?? A．串是一種特殊的線性表????????B．串的長度必須大于零
C．串中元素只能是字母??????????D．空串就是空白串
3．若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，則可能出現的出棧序列為（ B ）
A．3，2，6，1，4，5 B．3，4，2，1，6，5
C．1，2，5，3，4，6 D．5，6，4，2，3，1
4．在一個單鏈表中，若p所指結點不是最后結點，在p之后插入s所指結點，則執行( B )
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
5．在按層次遍歷二叉樹的算法中，需要借助的輔助數據結構是（ A ）
A．隊列 B．棧 C．線性表 D．有序表
6．圖的鄰接矩陣表示法適用于表示（ C ）
A．無向圖 B．有向圖 C．稠密圖 D．稀疏圖
7．深度為5的二叉樹其結點數最多為 C 。
A、16； B、30； C、31； D、32。
8．設單循環鏈表中結點的結構為（data,next）,且rear是指向非空的帶表頭結點的單循環鏈表的尾結點的指針。若想刪除鏈表第一個結點，則應執行下列哪一個操作（ D ）
A． s=rear； rear=rear->next； delete s； B． rear=rear->next； delete rear； C． rear=rear->next->next； delete rear；
D．s=rear->next->next； rear->next->next=s->next； delete s；
9．線性表采用鏈式存儲時，結點的存儲地址（?B? ）
?? A．必須是不連續的 B．連續與否均可
?? C．必須是連續的 D．和頭結點的存儲地址相連續
10．線性鏈表不具有的特點是（A ）。
A．隨機訪問 B．不必事先估計所需存儲空間大小
C．插入與刪除時不必移動元素 D．所需空間與線性表長度成正比
11. 含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數為(??D?)
??A．e?????????? B．2e?????????? C．n2－e?????? D．n2－2e
12. 用某種排序方法對關鍵字序列（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
????則所采用的排序方法是（ D?? ）
????A．選擇排序????B．希爾排序???? C．歸并排序????D．快速排序
13. 采用鄰接表存儲的圖的廣度優先遍歷算法類似于二叉樹的 D 。
A．先序遍歷； B．中序遍歷；
C．后序遍歷； D．按層遍歷。
14. 若一個圖的邊集為{,,,,,},則從頂點1開始對該圖進行深度優先搜索，得到的頂點序列可能為 C 。
A．1，2，5，4，3； B．1，2，3，4，5；
C．1，2，5，3，4； D．1，4，3，2，5。
15.假定對元素序列（7，3，5，9，1，12）進行堆排序，并且采用小根堆，則由初始數據構成的初始堆為 B 。
A．1，3，5，7，9，12； B．1，3，5，9，7，12；
C．1，5，3，7，9，12； D．1，5，3，9，12，7。
三、 判斷題 （對的打√，錯的打× 共 15 小題，每題 1 分，共計 15 分）
1、在線性結構中，每個結點都有一個直接前驅和一個直接后繼。（×）.
2、在堆中，以任何結點為根的子樹仍然為堆。（√ ）
3、完全二叉樹就是滿二叉樹。（ × ）
4、若將一棵樹轉換成二叉樹，則該二叉樹的根結點一定沒有右子樹（√ ）。
5、線性的數據結構可以順序存儲，也可以鏈接存儲。非線性的數據結構只能鏈接存儲。（× ）
6、在AOE網中，關鍵路徑是唯一的。(×)
7、哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離根較近。 (√ )
8、連通分量是無向圖中的極小連通子圖。（ × ）
9、鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。（ × ）
10、在散列法中，一個可用散列函數必須保證絕對不產生沖突。（╳）
11、完全二叉樹的某結點若無左孩子，則它必是葉結點。 (√ )
12、在采用線性探測法處理沖突的散列表中，所有的同義詞在表中相鄰。（×）
13、棧和隊列邏輯上都是線性表。 (√)
14、快速排序是一種穩定的排序方法。(× )
15、基數分類只適用于以數字為關鍵字的情形，不適用以字符串為關鍵字的情形（× ）。
四、算法填空題： 將折半查找的非遞歸算法中的空白處進行正確填寫。
（每空2分，共計 10分）
int Search_Bin(SSTable ST,KeyType key)
{ int low=1； high=_ST.length_________； （1）
While (__lownext =s ______；r=s; r->next=null;。
9. 在有序表（12，24，36，48，60，72，84）中折半查找關鍵字72時所需進行的關鍵字比較次數為__2___。?
10.在線形表的散列存儲中，處理沖突有 開放定址法 和 鏈地址法 兩種方法。
11. 在一棵二叉樹中，第五層的結點數最多為 16 個。
12. 用冒泡法對n 個關鍵碼排序，在最好情況下，只需做_____n-1________次比較和_______0_____
次移動；在最壞的情況下要做______ n(n-1)/2 ___________次比較。
二、選擇題 （共 15小題，每題 1 分，共計 15 分）
1．在數據結構的討論中把數據結構從邏輯上分為 （ C）
A 內部結構與外部結構 B 靜態結構與動態結構
C 線性結構與非線性結構 D 緊湊結構與非緊湊結構
2．算法分析的兩個主要方面是（ A）。
A．空間復雜性和時間復雜性 B．正確性和簡明性
C．可讀性和文檔性 D．數據復雜性和程序復雜性
3．一個非空廣義表的表頭（?D??）
?? A．不可能是子表????????????????B．只能是子表
?? C．只能是原子??????????????????D．可以是子表或原子
4．在一個單鏈表中，若p所指結點不是最后結點，在p之后插入s所指結點，則執行( B )
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
5．將一個遞歸算法改為對應的非遞歸算法時，通常需要使用（ A ）。
A． 棧 B． 隊列 C． 循環隊列 D． 優先隊列
6．圖的鄰接矩陣表示法適用于表示（ C ）
A．無向圖 B．有向圖 C．稠密圖 D．稀疏圖
7．深度為5的二叉樹其結點數最多為 C 。
A、16； B、30； C、31； D、32。
8．設單循環鏈表中結點的結構為（data,next）,且rear是指向非空的帶表頭結點的單循環鏈表的尾結點的指針。若想刪除鏈表第一個結點，則應執行下列哪一個操作（D ）
A． s=rear； rear=rear->next； delete s； B． rear=rear->next； delete rear； C． rear=rear->next->next； delete rear；
D．s=rear->next->next； rear->next->next=s->next； delete s；
9．線性表采用鏈式存儲時，結點的存儲地址（?B? ）
?? A．必須是不連續的 B．連續與否均可
?? C．必須是連續的 D．和頭結點的存儲地址相連續
10．根據集合{25，30，16，48}，按照依次插入結點的方法生成一棵二叉搜索樹，在等概率情況下成功查找一個元素的平均查找長度為（ A ）
A． 2 B． 2.5 C．3 D． 4
11. 含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數為(???D?)
????A．e?????????? B．2e?????????? C．n2－e?????? D．n2－2e
12. 對線性表進行折半搜索時，要求線性表必須（ C ）
A． 以鏈接方式存儲且結點按關鍵碼有序排列 B． 以數組方式存儲
C． 以數組方式存儲且結點按關鍵碼有序排列 D．以鏈接方式存儲
????A．選擇排序????B．希爾排序???? C．歸并排序????D．快速排序
13. 從未排序序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在
已排序序列的合適位置，該排序方法稱為(D )排序法。
A．二路歸并 B．選擇 C．shell D．插入
14. 若一個圖的邊集為{,,,,,},則從頂點1開始對該圖進行深度優先搜索，得到的頂點序列可能為(C)。
A、1，2，5，4，3； B、1，2，3，4，5；
C、1，2，5，3，4； D、1，4，3，2，5。
15. 在以下的敘述中，正確的是(B)。
A．線性表的線性存儲結構優于鏈表存儲結構
B．二維數組是其數據元素為線性表的線性表
C．棧的操作方式是先進先出
D．隊列的操作方式是先進后出
三、 判斷題 （對的打√，錯的打× 共 15 小題，每題 1 分，共計 15 分）
1、單鏈表從任何一個結點出發，都能訪問到所有結點。(×)
2、將一棵樹轉換成二叉樹后，根結點沒有左子樹。 (× )
3、哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離根較近。 (√ )
4、在樹結構里，有且僅有一個結點沒有前驅；非根結點有且僅有一個雙親，且存在一條從根到該結點的路徑（√ ）。
5、線性的數據結構可以順序存儲，也可以鏈接存儲。非線性的數據結構只能鏈接存儲。（× ）
6、在AOE網中，關鍵路徑是唯一的。(×)
7、向二叉排序樹插入一個新結點時，新結點一定成為二叉排序樹的一個葉子結點。 (√ )
8、對有向圖G，如果從任一頂點出發進行一次深度優先或廣度優先搜索就能訪問每個頂點，則該圖一定是完全圖。（ × ）
9、在一個有向圖的拓樸序列中，若頂點a在頂點b之前，則圖中必有一條弧。（ × ）
10、在散列法中，一個可用散列函數必須保證絕對不產生沖突。（╳）
11、完全二叉樹的某結點若無左孩子，則它必是葉結點。 (√ )
12、所謂平衡二叉樹是指左右子樹的高度差的絕對值不大于1的二叉樹。（ ）
13、AOE網所表示的工程至少所需的時間等于從源點到匯點的最短路徑的長度。 (×)
14、若一個棧的輸入序列為123…n，其輸出序列的第一個元素為n，則其輸出序列的每個元素ai一定滿足ai =n-i+1。(i=1,2,...,n)。(√ )
15、在采用線性探測法處理沖突的散列表中，所有的同義詞在表中相鄰。（× ）。
四、算法填空題： 將折半查找的非遞歸算法中的空白處進行正確填寫。
（每空2分，共計 10分）
int Search_Bin(SSTable ST,KeyType key)
{ int low=_______； high=ST.length； （1）
While (low
