版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、數(shù)據(jù)結(jié)構(gòu)試卷(一)1數(shù)據(jù)結(jié)構(gòu)試卷(二)4數(shù)據(jù)結(jié)構(gòu)試卷(三)6數(shù)據(jù)結(jié)構(gòu)試卷(四)8數(shù)據(jù)結(jié)構(gòu)試卷(五)11數(shù)據(jù)結(jié)構(gòu)試卷(六)14數(shù)據(jù)結(jié)構(gòu)試卷(七)16數(shù)據(jù)結(jié)構(gòu)試卷(八)18數(shù)據(jù)結(jié)構(gòu)試卷(九)20數(shù)據(jù)結(jié)構(gòu)試卷(十)23數(shù)據(jù)結(jié)構(gòu)試卷(一)參考答案26數(shù)據(jù)結(jié)構(gòu)試卷(二)參考答案27數(shù)據(jù)結(jié)構(gòu)試卷(三)參考答案28數(shù)據(jù)結(jié)構(gòu)試卷(四)參考答案30數(shù)據(jù)結(jié)構(gòu)試卷(五)參考答案32數(shù)據(jù)結(jié)構(gòu)試卷(六)參考答案33數(shù)據(jù)結(jié)構(gòu)試卷(七)參考答案36數(shù)據(jù)結(jié)構(gòu)試卷(八)參考答案37數(shù)據(jù)結(jié)構(gòu)試卷(九)參考答案38數(shù)據(jù)結(jié)構(gòu)試卷(十)參考答案39數(shù)據(jù)結(jié)構(gòu)試卷(一)一、單選題(每題 2 分,共20分)1. 棧和隊(duì)列的共同特點(diǎn)是( a
2、)。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出 C.都是先進(jìn)先出D.沒有共同點(diǎn) 2. 用鏈接方式存儲的隊(duì)列,在進(jìn)行插入運(yùn)算時( d ). A. 僅修改頭指針 B. 頭、尾指針都要修改 C. 僅修改尾指針 D.頭、尾指針可能都要修改3. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)?( d ) A. 隊(duì)列 B. 棧 C. 線性表 D. 二叉樹4. 設(shè)有一個二維數(shù)組Amn,假設(shè)A00存放位置在644(10),A22存放位置在676(10),每個元素占一個空間,問A33(10)存放在什么位置?腳注(10)表示用10進(jìn)制表示。c A688 B678 C692 D6965. 樹最適合用來表示( c )。 A.
3、有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素 C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù)6. 二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為( d ). A2k-1 B.2K+1 C.2K-1 D. 2k-17. 若有18個元素的有序表存放在一維數(shù)組A19中,第一個元素放A1中,現(xiàn)進(jìn)行二分查找,則查找A3的比較序列的下標(biāo)依次為( c d ) A. 1,2,3B. 9,5,2,3 C. 9,5,3D. 9,4,2,38. 對n個記錄的文件進(jìn)行快速排序,所需要的輔助存儲空間大致為 c A. O(1) B. O(n) C. O(1og2n) D. O(n2)9. 對于線性表(7,34,55,25,64,46,20
4、,10)進(jìn)行散列存儲時,若選用H(K)=K %9作為散列函數(shù),則散列地址為1的元素有( c d )個, A1 B2 C3 D410. 設(shè)有6個結(jié)點(diǎn)的無向圖,該圖至少應(yīng)有( a )條邊才能確保是一個連通圖。 A.5 B.6 C.7 D.8二、填空題(每空1分,共26分)1. 通常從四個方面評價算法的質(zhì)量:_時間 正確性_、_占用內(nèi)存_易讀性_、_復(fù)雜度_強(qiáng)壯性_和_準(zhǔn)確度_ 高效率_。2. 一個算法的時間復(fù)雜度為(n3+n2log2n+14n)/n2,其數(shù)量級表示為_3 0(n)_。3. 假定一棵樹的廣義表表示為A(C,D(E,F(xiàn),G),H(I,J),則樹中所含的結(jié)點(diǎn)數(shù)為_9_個,樹的深度為_3
5、_,樹的度為_2_。4. 后綴算式9 2 3 +- 10 2 / -的值為_3_-1_。中綴算式(3+4X)-2Y/3對應(yīng)的后綴算 式為_3 4X* + 2Y* / -_。5. 若用鏈表存儲一棵二叉樹時,每個結(jié)點(diǎn)除數(shù)據(jù)域外,還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中,n個結(jié)點(diǎn)的二叉樹共有_n_2n_個指針域,其中有_n-1_個指針域是存放了地址,有_3_n+1_個指針是空指針。6. 對于一個具有n個頂點(diǎn)和e條邊的有向圖和無向圖,在其對應(yīng)的鄰接表中,所含邊結(jié)點(diǎn)分別有_e+1_e_個和_e+1_2e_個。7. AOV網(wǎng)是一種_有向無回路_的圖。8. 在一個具有n個頂點(diǎn)的無向完全圖中,包含有
6、_n-1_n(n-1)/2_條邊,在一個具有n個頂點(diǎn)的有向完全圖中,包含有_n-1_n(n-1)_條邊。9. 假定一個線性表為(12,23,74,55,63,40),若按Key % 4條件進(jìn)行劃分,使得同一余數(shù)的元素成為一個子表,則得到的四個子表分別為_(12,40)_、_(23,63,55)_、_(74)_和_( )_。10. 向一棵B_樹插入元素的過程中,若最終引起樹根結(jié)點(diǎn)的分裂,則新樹比原樹的高度_增加1_。1. 在堆排序的過程中,對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時間復(fù)雜度為_0(n/2)_ O(log2n) _,整個堆排序過程的時間復(fù)雜度為_0(1)_ O(nlog2n)_。11. 在快速排
7、序、堆排序、歸并排序中,_堆排序_歸并排序_排序是穩(wěn)定的。三、計(jì)算題(每題 6 分,共24分)1. 在如下數(shù)組A中鏈接存儲了一個線性表,表頭指針為A 0.next,試寫出該線性表。 A 0 1 2 3 4 5 6 7 data605078903440next3572041A0 A3 A2 A7 A1 A5 A4 A0線性表為:(78,50,40,60,34,90)2. 請畫出下圖的鄰接矩陣和鄰接表。 1. 鄰接矩陣:3. 已知一個圖的頂點(diǎn)集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)1
8、2,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25; 用克魯斯卡爾算法得到最小生成樹,試寫出在最小生成樹中依次得到的各條邊。(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204. 畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時,每加入一個數(shù)據(jù)后堆的變化。四、閱讀算法(每題7分,共14分)1. LinkList mynote(LinkList L) /L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針 if(L&L-next) q=L;L=Lnext;p=L; S1: while(pnext) p=pnext; S2: pnext=q;q
9、next=NULL; return L; 請回答下列問題: (1)說明語句S1的功能; 判斷p的下一節(jié)點(diǎn)是否為空,如不為空p則指向下一節(jié)點(diǎn) 查詢鏈表的尾節(jié)點(diǎn) (2)說明語句組S2的功能; 使P的下一節(jié)點(diǎn)賦值給q,并令q的下一節(jié)點(diǎn)為空指針。將第一個節(jié)點(diǎn)鏈接到鏈表的尾部,作為新的尾節(jié)點(diǎn) (3)設(shè)鏈表表示的線性表為(a1,a2, ,an),寫出算法執(zhí)行后的返回值所表示的線性表。 a2,a3,an,a12. void ABC(BTNode * BT) if BT ABC (BT-left); ABC (BT-right); coutdatadata) item=BST-data;/查找成功 retur
10、n _item_true_; else if(itemdata) return Find(_BST-data_BST-left_,item); else return Find(_item_BST-right_,item); /if六、編寫算法(共8分)統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。 int CountX(LNode* HL,ElemType x)int count;node *head,*p;head = HL;p=head-next;if(head-data!=null) while(p-next)if(p-data=x)count+; Struct node HLele
11、mtype data;Struct node *next;node;int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;/i為計(jì)數(shù)器 while(p!=NULL) if (P-data=x) i+; p=p-next; /while, 出循環(huán)時i中的值即為x結(jié)點(diǎn)個數(shù) return i; /CountX數(shù)據(jù)結(jié)構(gòu)試卷(二)一、選擇題(24分)1下面關(guān)于線性表的敘述錯誤的是( )。(A) 線性表采用順序存儲必須占用一片連續(xù)的存儲空間(B) 線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間(C) 線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實(shí)現(xiàn)(D) 線性
12、表采用順序存儲便于插入和刪除操作的實(shí)現(xiàn)2設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m,若用二叉鏈表作為存儲結(jié)構(gòu),則該哈夫曼樹中總共有( )個空指針域。(A) 2m-1(B) 2m(C) 2m+1(D) 4m3設(shè)順序循環(huán)隊(duì)列Q0:M-1的頭指針和尾指針分別為F和R,頭指針F總是指向隊(duì)頭元素的前一位置,尾指針R總是指向隊(duì)尾元素的當(dāng)前位置,則該循環(huán)隊(duì)列中的元素個數(shù)為( )。(A) R-F(B) F-R(C) (R-F+M)M(D) (F-R+M)M4設(shè)某棵二叉樹的中序遍歷序列為ABCD,前序遍歷序列為CABD,則后序遍歷該二叉樹得到序列為( )。(A) BADC(B) BCDA(C) CDAB(D) CBDA5設(shè)
13、某完全無向圖中有n個頂點(diǎn),則該完全無向圖中有( )條邊。(A) n(n-1)/2(B) n(n-1)(C) n2 (D) n2-16設(shè)某棵二叉樹中有2000個結(jié)點(diǎn),則該二叉樹的最小高度為( )。(A) 9(B) 10(C) 11(D) 127設(shè)某有向圖中有n個頂點(diǎn),則該有向圖對應(yīng)的鄰接表中有( )個表頭結(jié)點(diǎn)。(A) n-1(B) n(C) n+1(D) 2n-18設(shè)一組初始記錄關(guān)鍵字序列(5,2,6,3,8),以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為( )。(A) 2,3,5,8,6(B) 3,2,5,8,6(C) 3,2,5,6,8(D) 2,3,6,5,8二、填空題(24分)1.
14、 為了能有效地應(yīng)用HASH查找技術(shù),必須解決的兩個問題是_和_。2. 下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧,要求在下劃線處填上正確的語句。typedef struct int s100; int top; sqstack;void push(sqstack &stack,int x)if (stack.top=m-1) printf(“overflow”);else _;_;3. 中序遍歷二叉排序樹所得到的序列是_序列(填有序或無序)。4. 快速排序的最壞時間復(fù)雜度為_,平均時間復(fù)雜度為_。5. 設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0,度數(shù)為1的結(jié)點(diǎn)數(shù)為N1,則該二叉樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為_;若采用二
15、叉鏈表作為該二叉樹的存儲結(jié)構(gòu),則該二叉樹中共有_個空指針域。6. 設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e,所有頂點(diǎn)的度數(shù)之和為d,則e=_。7. 設(shè)一組初始記錄關(guān)鍵字序列為(55,63,44,38,75,80,31,56),則利用篩選法建立的初始堆為_。8 已知一有向圖的鄰接表存儲結(jié)構(gòu)如下:從頂點(diǎn)1出發(fā),DFS遍歷的輸出序列是 ,BFS遍歷的輸出序列是 三、應(yīng)用題(36分)1 設(shè)一組初始記錄關(guān)鍵字序列為(45,80,48,40,22,78),則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。2 設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A,指針變量q指向被插入結(jié)點(diǎn)B,要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B
16、的操作序列(設(shè)雙向鏈表中結(jié)點(diǎn)的兩個指針域分別為llink和rlink)。3 設(shè)一組有序的記錄關(guān)鍵字序列為(13,18,24,35,47,50,62,83,90),查找方法用二分查找,要求計(jì)算出查找關(guān)鍵字62時的比較次數(shù)并計(jì)算出查找成功時的平均查找長度。4 設(shè)一棵樹T中邊的集合為(A,B),(A,C),(A,D),(B,E),(C,F(xiàn)),(C,G),要求用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。5 設(shè)有無向圖G,要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。6 設(shè)有一組初始記錄關(guān)鍵字為(45,80,48,40,22,78),要求構(gòu)造一棵二叉排序樹并給出構(gòu)造
17、過程。四、算法設(shè)計(jì)題(16分) 1 設(shè)有一組初始記錄關(guān)鍵字序列(K1,K2,Kn),要求設(shè)計(jì)一個算法能夠在O(n)的時間復(fù)雜度內(nèi)將線性表劃分成兩部分,其中左半部分的每個關(guān)鍵字均小于Ki,右半部分的每個關(guān)鍵字均大于等于Ki。2 設(shè)有兩個集合A和集合B,要求設(shè)計(jì)生成集合C=AB的算法,其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。數(shù)據(jù)結(jié)構(gòu)試卷(三)一、選擇題(每題1分,共20分)1設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D,R),D=01,02,03,04,05,06,07,08,09,R=r,r=,則數(shù)據(jù)結(jié)構(gòu)A是( )。(A) 線性結(jié)構(gòu)(B) 樹型結(jié)構(gòu)(C) 物理結(jié)構(gòu)(D) 圖型結(jié)構(gòu)2下面程序的時間復(fù)雜為(
18、 )for(i=1,s=0; i=n; i+) t=1;for(j=1;jnext;p-data=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設(shè)有n個待排序的記錄關(guān)鍵字,則在堆排序中需要( )個輔助記錄單元。(A) 1(B) n(C) nlog2n(D) n25設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20,15,14,18,21,36,40,10),則以
19、20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為( )。(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,216設(shè)二叉排序樹中有n個結(jié)點(diǎn),則在二叉排序樹的平均平均查找長度為( )。(A) O(1)(B) O(log2n)(C)(D) O(n2)7設(shè)無向圖G中有n個頂點(diǎn)e條邊,則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個數(shù)分別為( )。(A) n,e(B) e,n(C) 2n,e(D) n,2e8. 設(shè)某強(qiáng)連通圖中有n個頂點(diǎn),則該強(qiáng)連通圖中至少有
20、( )條邊。(A) n(n-1)(B) n+1(C) n(D) n(n+1)9設(shè)有5000個待排序的記錄關(guān)鍵字,如果需要用最快的方法選出其中最小的10個記錄關(guān)鍵字,則用下列( )方法可以達(dá)到此目的。(A) 快速排序(B) 堆排序(C) 歸并排序(D) 插入排序10.下列四種排序中( )的空間復(fù)雜度最大。(A) 插入排序(B) 冒泡排序(C) 堆排序(D) 歸并排序二、填空殖(每空1分 共20分)1. 數(shù)據(jù)的物理結(jié)構(gòu)主要包括_和_兩種情況。2. 設(shè)一棵完全二叉樹中有500個結(jié)點(diǎn),則該二叉樹的深度為_;若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu),則共有_個空指針域。3. 設(shè)輸入序列為1、2、3,則經(jīng)過
21、棧的作用后可以得到_種不同的輸出序列。4. 設(shè)有向圖G用鄰接矩陣Ann作為存儲結(jié)構(gòu),則該鄰接矩陣中第i行上所有元素之和等于頂點(diǎn)i的_,第i列上所有元素之和等于頂點(diǎn)i的_。5. 設(shè)哈夫曼樹中共有n個結(jié)點(diǎn),則該哈夫曼樹中有_個度數(shù)為1的結(jié)點(diǎn)。6. 設(shè)有向圖G中有n個頂點(diǎn)e條有向邊,所有的頂點(diǎn)入度數(shù)之和為d,則e和d的關(guān)系為_。7. _遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個遞增的關(guān)鍵字序列(填先序、中序或后序)。8. 設(shè)查找表中有100個元素,如果用二分法查找方法查找數(shù)據(jù)元素X,則最多需要比較_次就可以斷定數(shù)據(jù)元素X是否在查找表中。9. 不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧,其入棧和出棧操作的時間
22、復(fù)雜度均為_。10. 設(shè)有n個結(jié)點(diǎn)的完全二叉樹,如果按照從自上到下、從左到右從1開始順序編號,則第i個結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號為_,右孩子結(jié)點(diǎn)的編號為_。11. 設(shè)一組初始記錄關(guān)鍵字為(72,73,71,23,94,16,5),則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為_。12. 設(shè)有向圖G中有向邊的集合E=,則該圖的一種拓?fù)湫蛄袨開。13. 下列算法實(shí)現(xiàn)在順序散列表中查找值為x的關(guān)鍵字,請?jiān)谙聞澗€處填上正確的語句。struct recordint key; int others;int hashsqsearch(struct record hashtable ,int k)int i,j; j=
23、i=k % p;while (hashtablej.key!=k&hashtablej.flag!=0)j=(_) %m; if (i=j) return(-1); if (_ ) return(j); else return(-1);14. 下列算法實(shí)現(xiàn)在二叉排序樹上查找關(guān)鍵值k,請?jiān)谙聞澗€處填上正確的語句。typedef struct nodeint key; struct node *lchild; struct node *rchild;bitree;bitree *bstsearch(bitree *t, int k) if (t=0 ) return(0);else while (
24、t!=0)if (t-key=k)_; else if (t-keyk) t=t-lchild; else_;三、計(jì)算題(每題10分,共30分)1.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ,中序遍歷序列是EFAGBCHKIJD,畫出此二叉樹,并畫出它的后序線索二叉樹。2已知待散列的線性表為(36,15,40,63,22),散列用的一維地址空間為0.6,假定選用的散列函數(shù)是H(K)= K mod 7,若發(fā)生沖突采用線性探查法處理,試:(1)計(jì)算出每一個元素的散列地址并在下圖中填寫出散列表: 0 1 2 3 4 5 6(2)求出在查找每一個元素概率相等情況下的平均查找長度。3已知序列(10
25、,18,4,3,6,12,1,9,18,8)請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。四、算法設(shè)計(jì)題(每題15分,共30分)1 設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。2 設(shè)計(jì)一個求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。數(shù)據(jù)結(jié)構(gòu)試卷(四)一、選擇題(每題1分共 20分)1設(shè)一維數(shù)組中有n個數(shù)組元素,則讀取第i個數(shù)組元素的平均時間復(fù)雜度為( )。(A) O(n)(B) O(nlog2n)(C) O(1)(D) O(n2)2設(shè)一棵二叉樹的深度為k,則該二叉樹中最多有( )個結(jié)點(diǎn)。(A) 2k-1(B) 2k(C) 2k-1(D) 2k-13設(shè)某無向圖中有n個頂點(diǎn)e條邊,則該無向圖中所有頂點(diǎn)的入度之和為( )。
26、(A) n(B) e(C) 2n(D) 2e4在二叉排序樹中插入一個結(jié)點(diǎn)的時間復(fù)雜度為( )。(A) O(1)(B) O(n)(C) O(log2n)(D) O(n2)5設(shè)某有向圖的鄰接表中有n個表頭結(jié)點(diǎn)和m個表結(jié)點(diǎn),則該圖中有( )條有向邊。(A) n(B) n-1(C) m(D) m-16設(shè)一組初始記錄關(guān)鍵字序列為(345,253,674,924,627),則用基數(shù)排序需要進(jìn)行( )趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。(A) 3(B) 4(C) 5(D) 87設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作( )。(A) 必須判別棧是否為滿(B) 必須判別棧是否為空(C) 判別棧元素的類型
27、(D) 對棧不作任何判別8下列四種排序中( )的空間復(fù)雜度最大。(A) 快速排序(B) 冒泡排序(C) 希爾排序(D) 堆9設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0,度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl,度數(shù)為2的結(jié)點(diǎn)數(shù)為N2,則下列等式成立的是( )。(A) N0=N1+1(B) N0=Nl+N2(C) N0=N2+1(D) N0=2N1+l10.設(shè)有序順序表中有n個數(shù)據(jù)元素,則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過( )。(A) log2n+1(B) log2n-1(C) log2n(D) log2(n+1)二、填空題(每空1分共 20分)1 設(shè)有n個無序的記錄關(guān)鍵字,則直接插入排序的時間復(fù)雜度為_
28、,快速排序的平均時間復(fù)雜度為_。2 設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X,則刪除結(jié)點(diǎn)X需要執(zhí)行的語句序列為_(設(shè)結(jié)點(diǎn)中的兩個指針域分別為llink和rlink)。3 根據(jù)初始關(guān)鍵字序列(19,22,01,38,10)建立的二叉排序樹的高度為_。4 深度為k的完全二叉樹中最少有_個結(jié)點(diǎn)。5 設(shè)初始記錄關(guān)鍵字序列為(K1,K2,Kn),則用篩選法思想建堆必須從第_個元素開始進(jìn)行篩選。6 設(shè)哈夫曼樹中共有99個結(jié)點(diǎn),則該樹中有_個葉子結(jié)點(diǎn);若采用二叉鏈表作為存儲結(jié)構(gòu),則該樹中有_個空指針域。7 設(shè)有一個順序循環(huán)隊(duì)列中有M個存儲單元,則該循環(huán)隊(duì)列中最多能夠存儲_個隊(duì)列元素;當(dāng)前實(shí)際存儲_個隊(duì)列元素(
29、設(shè)頭指針F指向當(dāng)前隊(duì)頭元素的前一個位置,尾指針指向當(dāng)前隊(duì)尾元素的位置)。8 設(shè)順序線性表中有n個數(shù)據(jù)元素,則第i個位置上插入一個數(shù)據(jù)元素需要移動表中_個數(shù)據(jù)元素;刪除第i個位置上的數(shù)據(jù)元素需要移動表中_個元素。9 設(shè)一組初始記錄關(guān)鍵字序列為(20,18,22,16,30,19),則以20為中軸的一趟快速排序結(jié)果為_。10 設(shè)一組初始記錄關(guān)鍵字序列為(20,18,22,16,30,19),則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為_。11 設(shè)某無向圖G中有n個頂點(diǎn),用鄰接矩陣A作為該圖的存儲結(jié)構(gòu),則頂點(diǎn)i和頂點(diǎn)j互為鄰接點(diǎn)的條件是_。12 設(shè)無向圖對應(yīng)的鄰接矩陣為A,則A中第i上非0元素的個數(shù)_第i
30、列上非0元素的個數(shù)(填等于,大于或小于)。13 設(shè)前序遍歷某二叉樹的序列為ABCD,中序遍歷該二叉樹的序列為BADC,則后序遍歷該二叉樹的序列為_。14 設(shè)散列函數(shù)H(k)=k mod p,解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點(diǎn),成功時返回指向關(guān)鍵字的指針,不成功時返回標(biāo)志0。typedef struct node int key; struct node *next; lklist; void createlkhash(lklist *hashtable )int i,k; lklist *s;for(i=0;im
31、;i+)_;for(i=0;ikey=ai;k=ai % p; s-next=hashtablek;_;三、計(jì)算題(每題10分,共30分)1、畫出廣義表LS=( ) , (e) , (a , (b , c , d )的頭尾鏈表存儲結(jié)構(gòu)。2、下圖所示的森林:(1) 求樹(a)的先根序列和后根序列; (2) 求森林先序序列和中序序列;(3)將此森林轉(zhuǎn)換為相應(yīng)的二叉樹;3、設(shè)散列表的地址范圍是 0.9 ,散列函數(shù)為H(key)= (key 2 +2)MOD 9,并采用鏈表處理沖突,請畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲結(jié)構(gòu)。四、算法設(shè)計(jì)題(每題10分,共30分)1 設(shè)單鏈表中有
32、僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符),要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個單鏈表的算法,使每個單鏈表只包含同類字符。2. 設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。3. 在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。數(shù)據(jù)結(jié)構(gòu)試卷(五)一、選擇題(20分) 1數(shù)據(jù)的最小單位是( )。(A) 數(shù)據(jù)項(xiàng)(B) 數(shù)據(jù)類型(C) 數(shù)據(jù)元素(D) 數(shù)據(jù)變量2設(shè)一組初始記錄關(guān)鍵字序列為(50,40,95,20,15,70,60,45),則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為( )。(A) 40,50,20,95(B) 15,40,60,20(C) 15,20,40,45(D) 4
33、5,40,15,203設(shè)一組初始記錄關(guān)鍵字序列為(25,50,15,35,80,85,20,40,36,70),其中含有5個長度為2的有序子表,則用歸并排序的方法對該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果為( )。(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,854函數(shù)substr(“DATASTRUCTURE”,5,9)的返回值為( )。(A) “STRUCTURE”(B) “DATA
34、”(C) “ASTRUCTUR”(D) “DATASTRUCTURE”5設(shè)一個有序的單鏈表中有n個結(jié)點(diǎn),現(xiàn)要求插入一個新結(jié)點(diǎn)后使得單鏈表仍然保持有序,則該操作的時間復(fù)雜度為( )。(A) O(log2n)(B) O(1)(C) O(n2)(D) O(n)6設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0,度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl,度數(shù)為m的結(jié)點(diǎn)數(shù)為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)Nm7設(shè)有序表中有1000個元素,則用二分查找查找元素X最多需要比較( )次。(A) 25(
35、B) 10(C) 7(D) 18設(shè)連通圖G中的邊集E=(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c),則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為( )。(A) abedfc(B) acfebd(C) aebdfc(D) aedfcb9設(shè)輸入序列是1、2、3、n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則輸出序列中第i個輸出元素是( )。(A) n-i(B) n-1-i(C) n+1-i(D) 不能確定10 設(shè)一組初始記錄關(guān)鍵字序列為(45,80,55,40,42,85),則以第一個記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是( )。(A) 40,4
36、2,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. 設(shè)有一個順序共享?xiàng)0:n-1,其中第一個棧項(xiàng)指針top1的初值為-1,第二個棧頂指針top2的初值為n,則判斷共享?xiàng)M的條件是_。2. 在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是_。3. 設(shè)有一個n階的下三角矩陣A,如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽蔷€上元素)存放在n(n+1)個連續(xù)的存儲單元中,則Aij與A00之間有_個數(shù)據(jù)元素。4. 棧的插入和刪除只能在棧的棧頂進(jìn)行,后進(jìn)棧的元素必定先出棧,所
37、以又把棧稱為_表;隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行,先進(jìn)隊(duì)列的元素必定先出隊(duì)列,所以又把隊(duì)列稱為_表。5. 設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF,則該二叉樹的前序遍歷序列為_,中序遍歷序列為_,后序遍歷序列為_。6. 設(shè)一棵完全二叉樹有128個結(jié)點(diǎn),則該完全二叉樹的深度為_,有_個葉子結(jié)點(diǎn)。7. 設(shè)有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示,則A中第i行中所有非零元素個數(shù)之和等于頂點(diǎn)i的_,第i列中所有非零元素個數(shù)之和等于頂點(diǎn)i的_。8. 設(shè)一組初始記錄關(guān)鍵字序列(k1,k2,kn)是堆,則對i=1,2,n/2而言滿足的條件為_。9. 下面程序段的功能是實(shí)現(xiàn)冒泡排序算法
38、,請?jiān)谙聞澗€處填上正確的語句。void bubble(int rn)for(i=1;i=n-1; i+)for(exchange=0,j=0; jrj+1)temp=rj+1;_;rj=temp;exchange=1;if (exchange=0) return;10. 下面程序段的功能是實(shí)現(xiàn)二分查找算法,請?jiān)谙聞澗€處填上正確的語句。struct recordint key; int others;int bisearch(struct record r , int k) int low=0,mid,high=n-1; while(lownext=0(C) head-next=head(D)
39、head!=04時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是( )。(A) 堆排序(B) 冒泡排序(C) 希爾排序(D) 快速排序5設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反,則該二叉樹滿足的條件是( )。(A) 空或只有一個結(jié)點(diǎn)(B) 高度等于其結(jié)點(diǎn)數(shù)(C) 任一結(jié)點(diǎn)無左孩子(D) 任一結(jié)點(diǎn)無右孩子6一趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是( )。(A) 堆排序(B) 冒泡排序(C) 快速排序(D) 希爾排序7設(shè)某棵三叉樹中有40個結(jié)點(diǎn),則該三叉樹的最小高度為( )。(A) 3(B) 4(C) 5(D) 68順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)
40、雜度為( )。(A) O(n)(B) O(n2)(C) O(n1/2)(D) O(1og2n)9二路歸并排序的時間復(fù)雜度為( )。(A) O(n)(B) O(n2)(C) O(nlog2n)(D) O(1og2n)10. 深度為k的完全二叉樹中最少有( )個結(jié)點(diǎn)。(A) 2k-1-1(B) 2k-1(C) 2k-1+1(D) 2k-111.設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針,指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針,指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X,則入隊(duì)列的操作序列為( )。(A) front-next=s;front=s;(B) s-next=rear;rear=s;(C) rear
41、-next=s;rear=s;(D) s-next=front;front=s;12.設(shè)某無向圖中有n個頂點(diǎn)e條邊,則建立該圖鄰接表的時間復(fù)雜度為( )。(A) O(n+e)(B) O(n2)(C) O(ne)(D) O(n3)13.設(shè)某哈夫曼樹中有199個結(jié)點(diǎn),則該哈夫曼樹中有( )個葉子結(jié)點(diǎn)。(A) 99(B) 100(C) 101(D) 10214.設(shè)二叉排序樹上有n個結(jié)點(diǎn),則在二叉排序樹上查找結(jié)點(diǎn)的平均時間復(fù)雜度為( )。(A) O(n)(B) O(n2)(C) O(nlog2n)(D) O(1og2n)15.設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu),則有向圖G中頂點(diǎn)i的入度為( )。(A
42、) 第i行非0元素的個數(shù)之和(B) 第i列非0元素的個數(shù)之和(C) 第i行0元素的個數(shù)之和(D) 第i列0元素的個數(shù)之和二、判斷題(20分)1調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點(diǎn)。( )2分塊查找的平均查找長度不僅與索引表的長度有關(guān),而且與塊的長度有關(guān)。( )3冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。( )4滿二叉樹一定是完全二叉樹,完全二叉樹不一定是滿二叉樹。( )5設(shè)一棵二叉樹的先序序列和后序序列,則能夠唯一確定出該二叉樹的形狀。( )6層次遍歷初始堆可以得到一個有序的序列。( )7設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT,則二叉樹BT中一定沒有右子樹。( )8線性表的順序
43、存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更好。( )9中序遍歷二叉排序樹可以得到一個有序的序列。( )10.快速排序是排序算法中平均性能最好的一種排序。( )三、填空題(30分)1for(i=1,t=1,s=0;i=n;i+) t=t*i;s=s+t;的時間復(fù)雜度為_。2設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的新結(jié)點(diǎn)X,則進(jìn)行插入操作的語句序列為_(設(shè)結(jié)點(diǎn)的指針域?yàn)閚ext)。3設(shè)有向圖G的二元組形式表示為G =(D,R),D=1,2,3,4,5,R=r,r=,則給出該圖的一種拓?fù)渑判蛐蛄衉。4設(shè)無向圖G中有n個頂點(diǎn),則該無向圖中每個頂點(diǎn)的度數(shù)最多是_。5設(shè)二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為50,度數(shù)為1的結(jié)點(diǎn)數(shù)為30,則該二叉樹中總共有_個結(jié)點(diǎn)數(shù)。6設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針,則判斷該循環(huán)隊(duì)列為空的條件為_。7設(shè)二叉樹中結(jié)點(diǎn)的兩個指針域分別為lchild和rchild,則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_。8簡單選擇排序和直接插入排序算法的平均時間復(fù)雜度為_。9快速排序算法的空間復(fù)雜度平均情況下為_,最壞的情況下為_。10.散列表中解決沖突的兩種方法是_和_。四、算法設(shè)計(jì)題
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 電能表安06課件講解
- 2023年抗甲狀腺藥項(xiàng)目融資計(jì)劃書
- 國華電力危險化學(xué)品安全管理培訓(xùn)課件
- PLC控制技術(shù)試題庫(附參考答案)
- 養(yǎng)老院老人入住告知制度
- 養(yǎng)老院環(huán)境衛(wèi)生維護(hù)制度
- 《高血壓規(guī)范化管理》課件
- 2024年土地經(jīng)營權(quán)租賃與農(nóng)業(yè)保險配套服務(wù)合同3篇
- 教育局制式合同(2篇)
- 《土壤顆粒的分類》課件
- 井下修井作業(yè)技術(shù)課件
- 早期復(fù)極綜合征的再認(rèn)識課件
- 李商隱詩歌《錦瑟》課件
- 世界文化遺產(chǎn)-樂山大佛課件
- 2022小學(xué)一年級數(shù)學(xué)活用從不同角度解決問題測試卷(一)含答案
- 博爾赫斯簡介課件
- 2021年山東交投礦業(yè)有限公司招聘筆試試題及答案解析
- 施工單位資料檢查內(nèi)容
- 大氣課設(shè)-酸洗廢氣凈化系統(tǒng)
- 學(xué)校校慶等大型活動安全應(yīng)急預(yù)案
- 檢測公司檢驗(yàn)檢測工作控制程序
評論
0/150
提交評論