數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題及答案3

1、第1章 緒論1、填空題1.常見的數(shù)據(jù)結(jié)構(gòu)有_線性_結(jié)構(gòu)，_樹形_結(jié)構(gòu)，_圖形_結(jié)構(gòu)等三種。2.常見的存儲結(jié)構(gòu)有_順序存儲_結(jié)構(gòu)，_鏈?zhǔn)酱鎯結(jié)構(gòu)等兩種。3.數(shù)據(jù)的基本單位是_數(shù)據(jù)元素_，它在計算機(jī)中是作為一個整體來處理的。4.數(shù)據(jù)結(jié)構(gòu)中的結(jié)構(gòu)是指數(shù)據(jù)間的邏輯關(guān)系，常見的結(jié)構(gòu)可分為兩大類，_線性結(jié)構(gòu)_和_非線性結(jié)構(gòu)_。2、應(yīng)用題1、給出以下算法的時間復(fù)雜度.void fun(int n)int i=1,k=100;while(i<n)k=k+1;i=i+2; 時間復(fù)雜度為_O（n）_。2、給出以下算法的時間復(fù)雜度.void fun2(int n)int i=1,k=100;while(i&

2、lt;n)i=i*10;k=k+1;時間復(fù)雜度為_O（log n）_。第2章 線性表1、填空題1. 線性表按照存儲結(jié)構(gòu)不同主要有兩種實(shí)現(xiàn)方式，一種是_順序_表，另一種是_鏈_表。2.順序表采用_隨機(jī)_訪問機(jī)制對數(shù)據(jù)元素進(jìn)行訪問。3.若在單鏈表結(jié)點(diǎn)p的后面插入一個新的結(jié)點(diǎn)s，則其操作序列為:_s->next=p->next_；_p->next=s_；4.在單向鏈表中，若要刪除某個結(jié)點(diǎn)p，一般要找到_p的前趨_結(jié)點(diǎn)，才能實(shí)現(xiàn)該操作。2、選擇題1. 將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是 A 。(A)n    (B)2n1

3、60;  (C)2n    (D)n-12. 在單鏈表中，如果在結(jié)點(diǎn)p之后插入一個新結(jié)點(diǎn)s，其操作為 A 。（A）s->next=p->next; p->next=s;（B）p->next=s; s->next=p->next;（C）s->next=p; p->next=s->next;（D）p->next=s; s->next=p;3.若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置刪除一個元素的算法的平均時間復(fù)雜度為(  C  )。(1in)A

4、O(0)    BO(1)    C.O(n)    DO(n2)4. 若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素需要移動的元素個數(shù)為(  B  )。(1in+1)An-i   Bn-i+1    C. i    Dn-i-13、判斷題1.線性表中每一個元素都有一個前驅(qū)和一個后繼。（ × ）4、程序設(shè)計題1、單鏈表的結(jié)點(diǎn)結(jié)構(gòu)定義如下：struct LinkNodeL

5、inkNode *next;int data;請根據(jù)述函數(shù)的功能寫程序。void Insert(LinkNode *h,LinkNode *s)/h指向鏈表的頭結(jié)點(diǎn)（即使鏈表中沒有元素，頭結(jié)點(diǎn)也存在。）/鏈表中元素已經(jīng)遞增有序/函數(shù)功能為將結(jié)點(diǎn)s插入到鏈表h中。插入后鏈表仍然保持遞增的順序LinkNode *p,*q;/q指向p的前驅(qū)q=h;p=h->next; while(p)if(p->data>s->data) /尋找到插入點(diǎn)位置，插入sq->next=s; s->next=p; return;elseq=p; (1分)p=p->next; (1

6、分)/當(dāng)表中沒有比s大的結(jié)點(diǎn)時，插入到表尾s->next=q->next; (2分)q->next=s; (2分)2、設(shè)順序表L是一個遞增有序表，試寫一算法，將x插入L中，并使L仍是一個有序表。順序表的結(jié)構(gòu)定義如下：#define ListSize 100 / 假定表空間大小為100struct SqList    int elemListSize; / 數(shù)組elem用于存放表中的數(shù)據(jù)   int length; / 當(dāng)前的表長度;/以上為順序表的結(jié)構(gòu)/函數(shù)頭定義如下void InsertIncreaseList(

7、SqList &L ,int x ) int i;if ( L.length>=ListSize) cout<<”O(jiān)VERFLOW”; /判斷是否溢出 for ( i=L.length ; i>0 && L.elem i-1 > x ; i-) L.elem i =L.elem i-1 ; / 比較并移動元素 L.elem i =x; /插入x L.length+; /表長增1 /3、單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)如下所示： typedef struct node int data; struct node *next;node;請設(shè)計滿足下述功能的函

8、數(shù)。要求： 建立帶頭結(jié)點(diǎn)的單鏈表H，要求函數(shù)從屏幕上讀入m個整數(shù)，每讀入一個，便生成相應(yīng)的結(jié)點(diǎn)，并且把它插入到鏈表H的尾部。函數(shù)形式為void CreateLinkList(node *H)。參考程序：void CreateList(node *H)/H指向頭指針int m,temp;cout<<"輸入數(shù)據(jù)的個數(shù)："cin>>m;/int i=1;node *tail; H->next=NULL;tail=H;while(i<=m)cout<<"please input your number:"<&

9、lt;endl;cin>>temp;node *t=new node ;t->data=temp;t->next=tail->next;tail->next=t;tail=t;i+;第3章 棧和隊列1、填空題1.棧和隊列在本質(zhì)上都是_線性表_。2.棧的操作特點(diǎn)是_后進(jìn)先出_。隊列的操作特點(diǎn)是_先進(jìn)先出_。2、選擇題1.消除遞歸不一定需要使用棧，此說法_A_。 A. 正確    B. 錯誤2.對于棧，輸入序列為（1，2，3，4），不可能得到的輸出序列有_D_。(A)（1，2，3，4） (B)（4，3，2，1） 

10、(C)（1，3，4，2） (D)（3，1，2，4）3.用單循環(huán)鏈表表示隊列，正確的說法是 B 。 (A)可設(shè)一個頭指針使入隊、出隊都方便；(B)可設(shè)一個尾指針使入隊、出隊都方便；(C)必須設(shè)頭尾指針才能使入隊、出隊都方便；(D)無論如何,只可能使入隊方便。3、判斷題1.棧的特點(diǎn)是先進(jìn)先出。（ × ）2.可以在隊列的任意位置插入元素。（ ×）3.遞歸程序化非遞歸程序必須用到棧。（ × ）4.如果進(jìn)棧的序列為（1，2，3，4），則（4，2，3，1）不可能是出棧序列。（） 5.在用順序表表示的循環(huán)隊列中，可用標(biāo)志位來區(qū)分隊空或隊滿的條件。（） 第4章 串1、選

11、擇題1. 設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作（ B ）A連接 B模式匹配 C求子串 D求串長2、判斷題1.空串和空格串是同一個概念，二者沒有區(qū)別。（ × ）第5章 數(shù)組和廣義表1、填空題1.二維數(shù)組在內(nèi)存中存儲可以有兩種存儲方式，一種是_行_優(yōu)先存儲，一種是 列 優(yōu)先存儲。2.設(shè)廣義表L(（），（），（）)。則head(L)是  （）   ；tail(L)是  (（），（）) ；L的長度是  3  ；L的深度是 3 。3.設(shè)廣義表L(（a），（b），（c）)  則he

12、ad(L)是_（a）_；tail(L)是_(（b），（c）)_。2、選擇題1.在C語言中，如果有數(shù)組定義 int A89；假定每個整型數(shù)據(jù)占2字節(jié)，則數(shù)組元素A44的地址是（ A ）。A. A+80 B. A+76 C.A+82 D.以上都不對2.廣義表A=（a,b,(c,d),(e,(f,g)）,則下面式子的值為( D   )；    Head(Tail(Head(Tail(Tail(A)A（g）    B.(d)    C.c    D.d3

13、、判斷題1.在C語言中，多維數(shù)組的存儲采取的是行優(yōu)先的方式。（ ）2.廣義表在本質(zhì)上也是線性表。（ × ）3.可以用三元組存儲法來壓縮存儲稀疏矩陣。（ ）4.已知廣義表A=(a,b,c),(d,e,f),從A中取出原子e的運(yùn)算是head(tail(head(tail(A)。 ( )第6章 樹和二叉樹1、填空題1.一棵62個葉結(jié)點(diǎn)的完全二叉樹,最多有_62*2=124_個結(jié)點(diǎn)。2.若規(guī)定僅有根的二叉樹的高度為1，那么高為h的完全二叉樹最多有_2h-1_個結(jié)點(diǎn)，最少有_2(h-1)_個結(jié)點(diǎn)。3.設(shè)只包含有根結(jié)點(diǎn)的二叉樹的高度為0，則高度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為_2(k+1)-1_，最小

14、結(jié)點(diǎn)數(shù)為_k+1_。4.設(shè)僅包含根結(jié)點(diǎn)的二叉樹的高度為1，則高度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為_2k-1_，最小結(jié)點(diǎn)數(shù)為_k_。2、選擇題1.具有N個結(jié)點(diǎn)的完全二叉樹的深度是_B_。(A) log2N (B) log2N +1 (C) log2(N) (D) log2N -12.設(shè)二叉樹的樹根為第一層，則第i層上至多有_C_結(jié)點(diǎn)。(A)1  (B)2  (C)2i-1  (D)2i-13、判斷題1.二叉樹的左右子樹次序是嚴(yán)格的，不能夠任意改變。（ ）2.若根為第一層，則深度為k的滿二叉樹的結(jié)點(diǎn)為2k-1 。 （ ）3.二叉樹的三叉鏈表存儲結(jié)構(gòu)可以方便的訪問到雙親結(jié)點(diǎn)。

15、 （ ）4、應(yīng)用題1.在一段文字中，共出現(xiàn)a、b、c、d、e、f六種字符，每種字符出現(xiàn)的頻率分別為7,9,12,22,23,27。請回答下列問題：（1）什么是哈夫曼樹？（3分）（2）根據(jù)題目所給頻率值，畫出相應(yīng)的哈夫曼樹。（11分）（3）給出各個字符對應(yīng)的哈夫曼編碼。（6分）（4）該段文字經(jīng)過哈夫曼編碼后，長度是多少。（4分）參考答案如下：（1）答案為：帶權(quán)路徑長度最小的二叉樹稱為哈夫曼樹。（3分）（2）根據(jù)題目所給頻率值，畫出相應(yīng)的哈夫曼樹。（11分，每個結(jié)點(diǎn)1分）（3）給出各個字符對應(yīng)的哈夫曼編碼。（6分）a:1110 b:1111 c:110 d:00 e:01 f:10（4）該段文字經(jīng)

16、過哈夫曼編碼后，長度是多少。（4分）(7+9)*4+12*3+(22+23+27)*2=244或者100+45+55+28+16=244fc287912222355162745100abed10000011112. 設(shè)一棵二叉樹的先序遍歷序列為abcde，中序遍歷序列為badce，請畫出對應(yīng)的二叉樹，并寫出對應(yīng)后序遍歷序列。（15分）參考答案如下：(1)畫出二叉樹（10分）錯一個結(jié)點(diǎn)扣2分。 abcde（2）后序遍歷序列為：bdeca （5分）3. 通信報文中出現(xiàn)的字符A、B、C、D、E，在報文中出現(xiàn)的頻率分別為0.23、0.2、0.32、0.12、0.13，分別給出相應(yīng)字符的哈夫曼編碼（要求

17、畫出哈夫曼樹，并且把權(quán)值小的結(jié)點(diǎn)放在左邊）。（共14分）參考答案如下：為處理方便，關(guān)鍵字都乘以100，為23，20，32，12，13構(gòu)造哈夫曼樹為：（9分,每個結(jié)點(diǎn)1分）ABDEC010001111004357202325321213所以編碼為：A：01 B：00 C：11 D：100 E：101 （5分，每個編碼1分）4. 某二叉樹結(jié)點(diǎn)的中序序列為H，B，C，D，E，F(xiàn)，G，后序序列為B，D，C，H，F(xiàn)，G，E，請據(jù)此畫出該二叉樹，再給該樹加上中序線索。（共15分）CFBDGHE對應(yīng)的二叉樹為：（7分,每個結(jié)點(diǎn)1分）對應(yīng)中序線索樹為：（8分，每條線索1分）CFBDGHE55.請證明對于任何一

18、棵二叉樹，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。（10分）證明：令樹中結(jié)點(diǎn)總數(shù)為N，度為1的結(jié)點(diǎn)個數(shù)為n1。則樹中結(jié)點(diǎn)數(shù)滿足下列公式：n0+n1+n2=N從度的角度來考慮，滿足下列公式：2n2+n1+1=N從而得證：n0=n2+15. 請按照孩子-兄弟表示法，將圖1所示樹轉(zhuǎn)化為二叉樹。（共14分）解：（每個結(jié)點(diǎn)2分）ACBDEFGACBDEFG圖1 ABECFGDHIJ圖26. 設(shè)二叉樹如圖2所示。分別寫出它的先序遍歷、中序遍歷、后序遍歷序列。（共15分）8. （1）寫出如圖所示二叉樹的中序遍歷結(jié)果。（8分）（2）畫出二叉樹的中序后繼線索。（10分）（1）中

19、序遍歷結(jié)果：ADBCHFEG 共8分，每個字符1分（2）二叉樹的中序后繼線索如圖 共10分，每個后繼線索2分DACFGEHBDACFGEHBBCDFGAE9.已知某二叉樹的前序遍歷序列為：A B C D E F G和中序遍歷序列為：C B E D A F G。請畫出該二叉樹。答案如下：10.已知通信聯(lián)絡(luò)中只可能出現(xiàn)A、B、C、D、E、F、G、H共8種字符，其出現(xiàn)次數(shù)分別為5，28，7，9，14，23，3，11次。（1）請畫出赫夫曼樹（權(quán)值小的結(jié)點(diǎn)在左邊）。（15分）（2）計算該樹的帶權(quán)路徑長度。（3分）答案：此答案錯誤?。?）赫夫曼樹構(gòu)造如下。樹中結(jié)點(diǎn)位置正確者，每個1分，共15分。30141

20、679100422319118355828（2）該樹的帶權(quán)路徑長度為 （5+3+7+8）*4+（11+14）*3+（23+29）*2=271 3分5、讀程序?qū)懡Y(jié)果ABCDE已知二叉樹的結(jié)點(diǎn)結(jié)構(gòu)如下： struct Nodeint data; Node *lchild,*rchild;某棵二叉樹的形態(tài)如右圖：根據(jù)要求解答下題：1、 (共5分)int fun1(Node *root)if(root=0) return 0; int l,r;l=fun1(root->lchild); r=fun1(root->rchild); if(l>=r) return l+1; else r

21、eturn r+1; （1）當(dāng)root是指向結(jié)點(diǎn)A的指針時，函數(shù)fun1的返回值是多少？(2分)函數(shù)fun1的返回值是3。（2）函數(shù)fun1的功能是什么？(3分)函數(shù)fun1的功能是求二叉樹的高度。2、 (共6分)int fun2(Node *root)if(root=0) return 0; int l=fun2(root->lchild ); int r=fun2(root->rchild ); return l+r+1; （1）當(dāng)root是指向結(jié)點(diǎn)A的指針時，函數(shù)fun1的返回值是多少？(2分)函數(shù)fun1的返回值是5。（2）函數(shù)fun1的功能是什么？(4分)函數(shù)fun1的功

22、能是求二叉樹中所有結(jié)點(diǎn)的個數(shù)第7章 圖1、填空題1. 有n個頂點(diǎn)的有向連通圖最多有 n(n-1) 條邊，最少有 n-1 條邊。2.具有n個頂點(diǎn)的完全無向圖有_2/n(n-1)_條邊，完全有向圖有_n(n-1)_條邊。2、選擇題1. _b_方法可以判斷出一個有向圖中是否有環(huán)（回路）。(A)深度優(yōu)先遍歷 (B)拓?fù)渑判?#160; (C)求最短路徑  (D)求關(guān)鍵路徑2.關(guān)鍵路徑是指_b_。(A)從開始事件到終止事件路徑長度最短的路徑(B)從開始事件到終止事件路徑長度最長的路徑(C)從開始事件到終止事件活動最少的路徑   (D)從開始事件到終止事件

23、活動最多的路徑 7. 方法 b 可以判斷出一個有向圖中是否有環(huán)（回路）。(A)深度優(yōu)先遍歷 (B)拓?fù)渑判?#160; (C)求最短路徑  (D)求關(guān)鍵路徑3、判斷題1.具有n個頂點(diǎn)的有向圖最多有n*(n-1)條邊。 （t ）2.在AOV-網(wǎng)中，不應(yīng)該出現(xiàn)有向環(huán)，因為存在環(huán)就意味著活動可以以自己為先決條件。（ t ）4、應(yīng)用題1、已知某圖的存儲結(jié)構(gòu)如下，試寫出該圖從頂點(diǎn)A開始的深度優(yōu)先遍歷序列。(11分)ABCDEFGHIJKA01111100000B00000010000C00000001000D00000000100E00000000010F000000000

24、01G01000000000H00100000000I00010000000J00001000000K00000100000答案為：ABGCHDIEJFK (對一個1分)2. 請給出圖1的所有最小生成樹。（10分）aebdfc1238665圖1 共兩棵。第一棵為：(5分)錯一條邊扣1分。aebdfc12365aebdfc123665 第二棵為：(5分)錯一條邊扣1分。3. 請給出圖2的所有拓?fù)渑判蛐蛄?。?6）圖2abdfgceh答案如下：僅有兩個第一個：abcdefgh (錯一個字符扣1分)第二個：abcdegfh (錯一個字符扣1分)4、對于有向無環(huán)圖（如圖2），寫出它的所有不同的拓?fù)溆行?/p>

25、序列。(共16分)12435678圖2序列為：1、3、2、4、5、6、7、86. 已知某圖采取如圖2所示的鄰接矩陣表示法，請回答下列問題。（共12分） 01234561A10110002B21001103C31000114D40100005E50110006F6001000圖2(1) 請畫出該圖。（6分）（2）對其從頂點(diǎn)A開始進(jìn)行深度優(yōu)先遍歷，寫出遍歷序列。（6分）（1） 請畫出該圖。（6分）錯一個結(jié)點(diǎn)扣1分。ABCEFD（2）對其從頂點(diǎn)A開始進(jìn)行深度優(yōu)先遍歷，寫出遍歷序列。（6分, 錯一個字符扣1分）序列為：ABDECF7、（本題總計 7 分）構(gòu)造該圖的最小生成樹。 aefgdbhc2111

26、1222243圖的最小生成樹如下 每條邊1分，共7分 aefgdbhc2111122第9章 查找1、選擇題1.若在線性表中采用二分查找法查找元素，該線性表應(yīng)該(  a   )。A元素按值有序    B采用順序存儲結(jié)構(gòu)C元素按值有序，且采用順序存儲結(jié)構(gòu)D元素按值有序，且采用鏈?zhǔn)酱鎯Y(jié)構(gòu)2.對二叉排序樹進(jìn)行_b_遍歷，可以得到該二叉樹所有結(jié)點(diǎn)構(gòu)成的有序序列。(A) 前序   (B)中序   (C)后序   (D)按層次3.利用逐點(diǎn)插入法建立序列(51

27、，71，43，81，74，20，34，45，64，30)對應(yīng)的二叉排序樹以后，查找元素34要進(jìn)行( a   )元素間的比較。 A4次    B5次    C. 7次    D104.對二叉排序樹進(jìn)行_b_遍歷，可以得到該二叉樹所有結(jié)點(diǎn)構(gòu)成的有序序列。(A) 前序   (B)中序   (C)后序   (D)按層次5.散列函數(shù)有一個共同性質(zhì)，即函數(shù)值應(yīng)按(   

28、c )取其值域的每一個值。A.最大概率   B.最小概率   C.同等概率   D.平均概率6.一個哈希函數(shù)被認(rèn)為是“好的”，如果它滿足條件_d_。(A)哈希地址分布均勻(B)保證不產(chǎn)生沖突(C)所有哈希地址在表長范圍內(nèi)(D)滿足(B)和(C)7.哈希表的平均查找長度是_d_的函數(shù)。（A）哈希表的長度 （B）表中元素的多少（C）哈希函數(shù) （D）哈希表的裝滿程度8.平均查找長度最短的查找方法是_c_。（A）折半查找 （B）順序查找 （C）哈希查找 （4）其他2、判斷題1.在有序表的查詢過程中，設(shè)立“哨兵”的作用是為了提高效率。（ t ）

29、2.對于折半查找，其前提條件是待查找序列只要是有序的即可。 （f ）3、應(yīng)用題1.輸入一個正整數(shù)序列（53,17,12,66,58,70,87,25,56,60），試完成下列各題。(1)按輸入次序構(gòu)造一棵二叉排序樹（只要求畫出最終二叉排序樹）。(2)依此二叉排序樹，如何得到一個從小到大的有序序列？2、若一棵排序二叉樹的關(guān)鍵字輸入序列為80，6，10，7，8，25，100，90，請畫出該二叉樹。解：二叉排序樹為： （16分，每個結(jié)點(diǎn)2分）806100901072583.已知一組關(guān)鍵字為1,14,27,29,55,68,10,11,23，則按哈希函數(shù)H(key)=key MOD 13和鏈地址法處理

30、沖突來構(gòu)造哈希表。（1）畫出所構(gòu)造的哈希表。（2）在記錄的查找概率相等的前提下，計算該表查找成功時的平均查找長度。（1）畫出所構(gòu)造的哈希表。 9個結(jié)點(diǎn)，每個1分011142723295568456789101023111112（2）在記錄的查找概率相等的前提下，該表查找成功時的平均查找長度，ASL（1×42×33×2）/9=16/9 2分4、程序設(shè)計題1.二叉排序樹的結(jié)點(diǎn)結(jié)構(gòu)如下所示：typedef struct node int data; struct node *lchild,*rchild; node；請編寫在二叉排序樹T中查找值為x的結(jié)點(diǎn)的非遞歸算法，如

31、果查到，返回指向該結(jié)點(diǎn)的指針，否則返回空。函數(shù)形式為：node* Search(node *T, int x)。（10分）/2.已知整型數(shù)組A，從第一個單元（即A1）開始存儲數(shù)據(jù)，且一共存儲了n個元素。要求編寫折半查找元素e的過程。當(dāng)數(shù)組中存在元素e時，返回其下標(biāo)，否則返回0。（10分）int BinarySearch(int *A,int n,int e)/參考程序如下：int BinarySearch(int *A,int n,int e)int low,high,mid;low=1;high=n; （1分）while(low<high)mid=(low+high)/2; （2分）i

32、f (e =Amid) （1分） return mid; （1分）else if(e <Amid) （1分）high=mid-1; （1分）else low=mid+1; （1分）return 0; （1分）3.已知整型數(shù)組A101，其中從A1到A100存儲了100個整數(shù)，試編寫函數(shù)int Find(int A101,int x)，功能為從數(shù)組A中折半查找元素x，如果找到則返回x所對應(yīng)的下標(biāo)，否則的話返回0。第10章內(nèi)部排序1、填空題1.快速排序和堆排序的平均時間復(fù)雜度分別為_o(nlog2n)-o(n2)_和_ o(nlog2n)_。2、選擇題1.下面給出的四種排序法中( &

33、#160;  d )排序法是不穩(wěn)定性排序法。A插入    B冒泡    C二路歸并    D堆排序2.從未排序序列中依次取出一個元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為 d 排序法。(A)插入   (B)選擇   (C)希爾   (D)二路歸并3.從未排序序列中依次取出一個元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為_a

34、_排序法。(A)插入   (B)選擇   (C)謝爾   (D)二路歸并3、判斷題1.從平均性能而言，快速排序最佳，其所需時間最省。 （f ）4、應(yīng)用題1. 對于關(guān)鍵字序列49，38，65，97，76，13，回答下述問題。（共12分）（1）寫出一趟冒泡排序的結(jié)果。（6分）（2）寫出一趟快速排序的結(jié)果。（6分）參考答案如下：（1）寫出一趟冒泡排序的結(jié)果。（6分）38,49,65,76,13,97（2）寫出一趟快速排序的結(jié)果。（6分）13,38,49,97,76,65一、 一、  

35、0;         單選題（每小題2分，共8分）1、 1、在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為 ( )。A n B n/2 C (n+1)/2 D (n-1)/22、 2、在一個單鏈表中,若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在q與p之間插入一個s所指的結(jié)點(diǎn),則執(zhí)行( )。 A slink=plink; plink=s; B plink=s; slink=q; C plink=slink; slink=p; D q

36、 link=s; slink =p;3、 3、      棧的插入和刪除操作在（ ）進(jìn)行。A 棧頂 B 棧底 C 任意位置 D 指定位置4、 4、      由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ ） A 24 B 71 C 48 D 53二、 二、            填空題（每空1分，共32分）1、 1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_、 _ 、_和

37、_四種。2、 2、一種抽象數(shù)據(jù)類型包括_和_兩個部分。3、 3、在下面的數(shù)組a中鏈接存儲著一個線性表，表頭指針為ao.next，則該線性表為_。 a 0 1 2 3 4 5 6 7 8   60 56 42 38  74 25  4 3 7 6 2 0 1 datanext 4、 4、在以HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為_和_。5、 5、用具有n個元素的一維數(shù)組存儲一個循環(huán)隊列，則其隊首指針總是指向隊首元素的_，該循環(huán)隊列的最大長度為_。6、 6、當(dāng)堆棧采用順序存儲結(jié)構(gòu)時，棧頂元素的值可用表示；當(dāng)堆

38、棧采用鏈接存儲結(jié)構(gòu)時，棧頂元素的值可用_表示。7、 7、一棵高度為5的二叉樹中最少含有_個結(jié)點(diǎn)，最多含有_個結(jié)點(diǎn)；一棵高度為5的理想平衡樹中，最少含有_個結(jié)點(diǎn)，最多含有_個結(jié)點(diǎn)。8、 8、在圖的鄰接表中，每個結(jié)點(diǎn)被稱為_，通常它包含三個域：一是_；二是_；三是_。9、 9、在一個索引文件的索引表中，每個索引項包含對應(yīng)記錄的_和_兩項數(shù)據(jù)。10、 10、            假定一棵樹的廣義表表示為A（B（C，D（E，F(xiàn)，G），H（I，J），則樹中所含的結(jié)點(diǎn)數(shù)為_個，樹的深度為_,樹的

39、度為_, 結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為_,孩子結(jié)點(diǎn)為_ 。11、 11、            在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時間復(fù)雜度為_,整個堆排序過程的時間復(fù)雜度為_。12、 12、            在對m階的B_樹插入元素的過程中，每向一個結(jié)點(diǎn)插入一個索引項（葉子結(jié)點(diǎn)中的索引項為關(guān)鍵字和空指針）后，若該結(jié)點(diǎn)的索引項數(shù)等于_個，則必須把它分裂為_個結(jié)點(diǎn)。

40、0;三、 三、            運(yùn)算題（每小題6分，共24分）1、 1、已知一組記錄的排序碼為（46，79，56，38，40，80, 95，24），寫出對其進(jìn)行快速排序的每一次劃分結(jié)果。 2、 2、一個線性表為B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT0.12，散列函數(shù)為H（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。 3、 3、已知一棵二叉樹的前序遍歷的結(jié)

41、果序列是ABECKFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。  4、 4、已知一個圖的頂點(diǎn)集V各邊集G如下：V = 0，1，2，3，4，5，6，7，8，9；E = （0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）當(dāng)它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點(diǎn)V0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷等到的頂點(diǎn)序列。假定每個頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號從大到小的次序鏈接的。圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表

42、示時  鄰接表表示時         四、 四、            閱讀算法，回答問題（每小題8分，共16分） 1、假定從鍵盤上輸入一批整數(shù)，依次為：78 63 45 30 91 34 1，請寫出輸出結(jié)果。# include < iostream.h># include < stdlib.h >consst int stackmaxsize = 30;typedef i

43、nt elemtype;struct stack elemtype stack stackmaxsize; int top;# include “stack.h”Void main ( ) stack a; initstack(a); int x; cin >>x; while (x! = -1) push (a, x ); cin >>x;while (!stackempty (a) cout <<pop (a) <<” ;cout <<end1;該算法的輸出結(jié)果為：_. 2、閱讀以下二叉樹操作算法，指出該算法的功能。Templat

44、e <calss type > void BinTree <Type> ：unknown (BinTreeNode<Type>*t) BinTreeNode< Type> *p =t, *temp; if (p!=NULL) temp = pleftchild; pleftchild = prightchild; prightchild = temp; unknown(pleftchild); undnown(prightchild); 該算法的功能是：_  五、 五、