《廣州大學(xué)插本數(shù)據(jù)結(jié)構(gòu)試題.doc》由會(huì)員分享,可在線閱讀,更多相關(guān)《廣州大學(xué)插本數(shù)據(jù)結(jié)構(gòu)試題.doc(53頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
數(shù)據(jù)結(jié)構(gòu)試卷(一)
一、單選題(每題 2 分,共20分)
1. 棧和隊(duì)列的共同特點(diǎn)是( )。
A.只允許在端點(diǎn)處插入和刪除元素
B.都是先進(jìn)后出
C.都是先進(jìn)先出
D.沒有共同點(diǎn)
2. 用鏈接方式存儲(chǔ)的隊(duì)列,在進(jìn)行插入運(yùn)算時(shí)( ).
A. 僅修改頭指針 B. 頭、尾指針都要修改
C. 僅修改尾指針 D.頭、尾指針可能都要修改
3. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)?( )
A. 隊(duì)列 B. 棧 C. 線性表 D. 二叉樹
4. 設(shè)有一個(gè)二維數(shù)組A[m][n],假設(shè)A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每個(gè)元素占一個(gè)空間,問A[3][3](10)存放在什么位置?腳注(10)表示用10進(jìn)制表示。
A.688 B.678 C.692 D.696
5. 樹最適合用來表示( )。
A.有序數(shù)據(jù)元素 B.無(wú)序數(shù)據(jù)元素
C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無(wú)聯(lián)系的數(shù)據(jù)
6. 二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. 若有18個(gè)元素的有序表存放在一維數(shù)組A[19]中,第一個(gè)元素放A[1]中,現(xiàn)進(jìn)行二分查找,則查找A[3]的比較序列的下標(biāo)依次為( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. 對(duì)n個(gè)記錄的文件進(jìn)行快速排序,所需要的輔助存儲(chǔ)空間大致為
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. 對(duì)于線性表(7,34,55,25,64,46,20,10)進(jìn)行散列存儲(chǔ)時(shí),若選用H(K)=K %9作為散列函數(shù),則散列地址為1的元素有( )個(gè),
A.1 B.2 C.3 D.4
10. 設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖,該圖至少應(yīng)有( )條邊才能確保是一個(gè)連通圖。
A.5 B.6 C.7 D.8
二、填空題(每空1分,共26分)
1. 通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量:_________、_________、_________和_________。
2. 一個(gè)算法的時(shí)間復(fù)雜度為(n3+n2log2n+14n)/n2,其數(shù)量級(jí)表示為________。
3. 假定一棵樹的廣義表表示為A(C,D(E,F(xiàn),G),H(I,J)),則樹中所含的結(jié)點(diǎn)數(shù)為__________個(gè),樹的深度為___________,樹的度為_________。
4. 后綴算式9 2 3 +- 10 2 / -的值為__________。中綴算式(3+4X)-2Y/3對(duì)應(yīng)的后綴算式為_______________________________。
5. 若用鏈表存儲(chǔ)一棵二叉樹時(shí),每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外,還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中,n個(gè)結(jié)點(diǎn)的二叉樹共有________個(gè)指針域,其中有________個(gè)指針域是存放了地址,有________________個(gè)指針是空指針。
6. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無(wú)向圖,在其對(duì)應(yīng)的鄰接表中,所含邊結(jié)點(diǎn)分別有_______個(gè)和________個(gè)。
7. AOV網(wǎng)是一種___________________的圖。
8. 在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中,包含有________條邊,在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中,包含有________條邊。
9. 假定一個(gè)線性表為(12,23,74,55,63,40),若按Key % 4條件進(jìn)行劃分,使得同一余數(shù)的元素成為一個(gè)子表,則得到的四個(gè)子表分別為____________________________、___________________、_______________________和__________________________。
10. 向一棵B_樹插入元素的過程中,若最終引起樹根結(jié)點(diǎn)的分裂,則新樹比原樹的高度___________。
11. 在堆排序的過程中,對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為________,整個(gè)堆排序過程的時(shí)間復(fù)雜度為________。
12. 在快速排序、堆排序、歸并排序中,_________排序是穩(wěn)定的。
三、計(jì)算題(每題 6 分,共24分)
1. 在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表,表頭指針為A [0].next,試寫出該線性表。
A 0 1 2 3 4 5 6 7
data
60
50
78
90
34
40
next
3
5
7
2
0
4
1
2. 請(qǐng)畫出下圖的鄰接矩陣和鄰接表。
3. 已知一個(gè)圖的頂點(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)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
用克魯斯卡爾算法得到最小生成樹,試寫出在最小生成樹中依次得到的各條邊。
4. 畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時(shí),每加入一個(gè)數(shù)據(jù)后堆的變化。
四、閱讀算法(每題7分,共14分)
1. LinkList mynote(LinkList L)
{//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針
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;
}
return L;
}
請(qǐng)回答下列問題:
(1)說明語(yǔ)句S1的功能;
(2)說明語(yǔ)句組S2的功能;
(3)設(shè)鏈表表示的線性表為(a1,a2, …,an),寫出算法執(zhí)行后的返回值所表示的線性表。
2. void ABC(BTNode * BT)
{
if BT {
ABC (BT->left);
ABC (BT->right);
cout<
data<< ;
}
}
該算法的功能是:
五、算法填空(共8分)
二叉搜索樹的查找——遞歸算法:
bool Find(BTreeNode* BST,ElemType& item)
{
if (BST==NULL)
return false; //查找失敗
else {
if (item==BST->data){
item=BST->data;//查找成功
return ___________;}
else if(itemdata)
return Find(______________,item);
else return Find(_______________,item);
}//if
}
六、編寫算法(共8分)
統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。
int CountX(LNode* HL,ElemType x)
數(shù)據(jù)結(jié)構(gòu)試卷(二)
一、選擇題(24分)
1.下面關(guān)于線性表的敘述錯(cuò)誤的是( )。
(A) 線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間
(B) 線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間
(C) 線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)
(D) 線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)
2.設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m,若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu),則該哈夫曼樹中總共有( )個(gè)空指針域。
(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m
3.設(shè)順序循環(huán)隊(duì)列Q[0:M-1]的頭指針和尾指針分別為F和R,頭指針F總是指向隊(duì)頭元素的前一位置,尾指針R總是指向隊(duì)尾元素的當(dāng)前位置,則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為( )。
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4.設(shè)某棵二叉樹的中序遍歷序列為ABCD,前序遍歷序列為CABD,則后序遍歷該二叉樹得到序列為( )。
(A) BADC (B) BCDA (C) CDAB (D) CBDA
5.設(shè)某完全無(wú)向圖中有n個(gè)頂點(diǎn),則該完全無(wú)向圖中有( )條邊。
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6.設(shè)某棵二叉樹中有2000個(gè)結(jié)點(diǎn),則該二叉樹的最小高度為( )。
(A) 9 (B) 10 (C) 11 (D) 12
7.設(shè)某有向圖中有n個(gè)頂點(diǎn),則該有向圖對(duì)應(yīng)的鄰接表中有( )個(gè)表頭結(jié)點(diǎn)。
(A) n-1 (B) n (C) n+1 (D) 2n-1
8.設(shè)一組初始記錄關(guān)鍵字序列(5,2,6,3,8),以第一個(gè)記錄關(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. 為了能有效地應(yīng)用HASH查找技術(shù),必須解決的兩個(gè)問題是____________________和__________________________。
2. 下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧,要求在下劃線處填上正確的語(yǔ)句。
typedef struct {int s[100]; int top;} sqstack;
void push(sqstack &stack,int x)
{
if (stack.top==m-1) printf(“overflow”);
else {____________________;_________________;}
}
3. 中序遍歷二叉排序樹所得到的序列是___________序列(填有序或無(wú)序)。
4. 快速排序的最壞時(shí)間復(fù)雜度為___________,平均時(shí)間復(fù)雜度為__________。
5. 設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0,度數(shù)為1的結(jié)點(diǎn)數(shù)為N1,則該二叉樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為_________;若采用二叉鏈表作為該二叉樹的存儲(chǔ)結(jié)構(gòu),則該二叉樹中共有_______個(gè)空指針域。
6. 設(shè)某無(wú)向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e,所有頂點(diǎn)的度數(shù)之和為d,則e=_______。
7. 設(shè)一組初始記錄關(guān)鍵字序列為(55,63,44,38,75,80,31,56),則利用篩選法建立的初始堆為___________________________。
8. 已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下:從頂點(diǎn)1出發(fā),DFS遍歷的輸出序列是
,BFS遍歷的輸出序列是
三、應(yīng)用題(36分)
1. 設(shè)一組初始記錄關(guān)鍵字序列為(45,80,48,40,22,78),則分別給出第4趟簡(jiǎn)單選擇排序和第4趟直接插入排序后的結(jié)果。
2. 設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A,指針變量q指向被插入結(jié)點(diǎn)B,要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列(設(shè)雙向鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別為llink和rlink)。
3. 設(shè)一組有序的記錄關(guān)鍵字序列為(13,18,24,35,47,50,62,83,90),查找方法用二分查找,要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長(zhǎng)度。
4. 設(shè)一棵樹T中邊的集合為{(A,B),(A,C),(A,D),(B,E),(C,F(xiàn)),(C,G)},要求用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲(chǔ)結(jié)構(gòu)并將該樹轉(zhuǎn)化成對(duì)應(yīng)的二叉樹。
5. 設(shè)有無(wú)向圖G,要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。
6. 設(shè)有一組初始記錄關(guān)鍵字為(45,80,48,40,22,78),要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。
四、算法設(shè)計(jì)題(16分)
1. 設(shè)有一組初始記錄關(guān)鍵字序列(K1,K2,…,Kn),要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分,其中左半部分的每個(gè)關(guān)鍵字均小于Ki,右半部分的每個(gè)關(guān)鍵字均大于等于Ki。
2. 設(shè)有兩個(gè)集合A和集合B,要求設(shè)計(jì)生成集合C=A∩B的算法,其中集合A、B和C用鏈?zhǔn)酱鎯?chǔ)結(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={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>},則數(shù)據(jù)結(jié)構(gòu)A是( )。
(A) 線性結(jié)構(gòu) (B) 樹型結(jié)構(gòu) (C) 物理結(jié)構(gòu) (D) 圖型結(jié)構(gòu)
2.下面程序的時(shí)間復(fù)雜為( )
for(i=1,s=0; i<=n; i++) {t=1;for(j=1;j<=i;j++) t=t*j;s=s+t;}
(A) O(n) (B) O(n2) (C) O(n3) (D) O(n4)
3.設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,若刪除單鏈表中結(jié)點(diǎn)A,則需要修改指針的操作序列為( )。
(A) q=p->next;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個(gè)待排序的記錄關(guān)鍵字,則在堆排序中需要( )個(gè)輔助記錄單元。
(A) 1 (B) n (C) nlog2n (D) n2
5.設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20,15,14,18,21,36,40,10),則以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,21
6.設(shè)二叉排序樹中有n個(gè)結(jié)點(diǎn),則在二叉排序樹的平均平均查找長(zhǎng)度為( )。
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7.設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)e條邊,則其對(duì)應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為( )。
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. 設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn),則該強(qiáng)連通圖中至少有( )條邊。
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9.設(shè)有5000個(gè)待排序的記錄關(guān)鍵字,如果需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字,則用下列( )方法可以達(dá)到此目的。
(A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 插入排序
10.下列四種排序中( )的空間復(fù)雜度最大。
(A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 歸并排序
二、填空殖(每空1分 共20分)
1. 數(shù)據(jù)的物理結(jié)構(gòu)主要包括_____________和______________兩種情況。
2. 設(shè)一棵完全二叉樹中有500個(gè)結(jié)點(diǎn),則該二叉樹的深度為__________;若用二叉鏈表作為該完全二叉樹的存儲(chǔ)結(jié)構(gòu),則共有___________個(gè)空指針域。
3. 設(shè)輸入序列為1、2、3,則經(jīng)過棧的作用后可以得到___________種不同的輸出序列。
4. 設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲(chǔ)結(jié)構(gòu),則該鄰接矩陣中第i行上所有元素之和等于頂點(diǎn)i的________,第i列上所有元素之和等于頂點(diǎn)i的________。
5. 設(shè)哈夫曼樹中共有n個(gè)結(jié)點(diǎn),則該哈夫曼樹中有________個(gè)度數(shù)為1的結(jié)點(diǎn)。
6. 設(shè)有向圖G中有n個(gè)頂點(diǎn)e條有向邊,所有的頂點(diǎn)入度數(shù)之和為d,則e和d的關(guān)系為_________。
7. __________遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列(填先序、中序或后序)。
8. 設(shè)查找表中有100個(gè)元素,如果用二分法查找方法查找數(shù)據(jù)元素X,則最多需要比較________次就可以斷定數(shù)據(jù)元素X是否在查找表中。
9. 不論是順序存儲(chǔ)結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧,其入棧和出棧操作的時(shí)間復(fù)雜度均為____________。
10. 設(shè)有n個(gè)結(jié)點(diǎn)的完全二叉樹,如果按照從自上到下、從左到右從1開始順序編號(hào),則第i個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為____________,右孩子結(jié)點(diǎn)的編號(hào)為___________。
11. 設(shè)一組初始記錄關(guān)鍵字為(72,73,71,23,94,16,5),則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為___________________________。
12. 設(shè)有向圖G中有向邊的集合E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>},則該圖的一種拓?fù)湫蛄袨開___________________。
13. 下列算法實(shí)現(xiàn)在順序散列表中查找值為x的關(guān)鍵字,請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。
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. 下列算法實(shí)現(xiàn)在二叉排序樹上查找關(guān)鍵值k,請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。
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_____________;
}
三、計(jì)算題(每題10分,共30分)
1.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ,中序遍歷序列是EFAGBCHKIJD,畫出此二叉樹,并畫出它的后序線索二叉樹。
2.已知待散列的線性表為(36,15,40,63,22),散列用的一維地址空間為[0..6],假定選用的散列函數(shù)是H(K)= K mod 7,若發(fā)生沖突采用線性探查法處理,試:
(1)計(jì)算出每一個(gè)元素的散列地址并在下圖中填寫出散列表:
` 0 1 2 3 4 5 6
(2)求出在查找每一個(gè)元素概率相等情況下的平均查找長(zhǎng)度。
3.已知序列(10,18,4,3,6,12,1,9,18,8)請(qǐng)用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。
四、算法設(shè)計(jì)題(每題15分,共30分)
1. 設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。
2. 設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。
數(shù)據(jù)結(jié)構(gòu)試卷(四)
一、選擇題(每題1分共 20分)
1.設(shè)一維數(shù)組中有n個(gè)數(shù)組元素,則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為( )。
(A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2)
2.設(shè)一棵二叉樹的深度為k,則該二叉樹中最多有( )個(gè)結(jié)點(diǎn)。
(A) 2k-1 (B) 2k (C) 2k-1 (D) 2k-1
3.設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊,則該無(wú)向圖中所有頂點(diǎn)的入度之和為( )。
(A) n (B) e (C) 2n (D) 2e
4.在二叉排序樹中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為( )。
(A) O(1) (B) O(n) (C) O(log2n) (D) O(n2)
5.設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn),則該圖中有( )條有向邊。
(A) n (B) n-1 (C) m (D) m-1
6.設(shè)一組初始記錄關(guān)鍵字序列為(345,253,674,924,627),則用基數(shù)排序需要進(jìn)行( )趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。
(A) 3 (B) 4 (C) 5 (D) 8
7.設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作( )。
(A) 必須判別棧是否為滿 (B) 必須判別棧是否為空
(C) 判別棧元素的類型 (D) 對(duì)棧不作任何判別
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+l
10.設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素,則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過( )。
(A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1)
二、填空題(每空1分共 20分)
1. 設(shè)有n個(gè)無(wú)序的記錄關(guān)鍵字,則直接插入排序的時(shí)間復(fù)雜度為________,快速排序的平均時(shí)間復(fù)雜度為_________。
2. 設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X,則刪除結(jié)點(diǎn)X需要執(zhí)行的語(yǔ)句序列為_________________________________________________________(設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink)。
3. 根據(jù)初始關(guān)鍵字序列(19,22,01,38,10)建立的二叉排序樹的高度為____________。
4. 深度為k的完全二叉樹中最少有____________個(gè)結(jié)點(diǎn)。
5. 設(shè)初始記錄關(guān)鍵字序列為(K1,K2,…,Kn),則用篩選法思想建堆必須從第______個(gè)元素開始進(jìn)行篩選。
6. 設(shè)哈夫曼樹中共有99個(gè)結(jié)點(diǎn),則該樹中有_________個(gè)葉子結(jié)點(diǎn);若采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu),則該樹中有_____個(gè)空指針域。
7. 設(shè)有一個(gè)順序循環(huán)隊(duì)列中有M個(gè)存儲(chǔ)單元,則該循環(huán)隊(duì)列中最多能夠存儲(chǔ)________個(gè)隊(duì)列元素;當(dāng)前實(shí)際存儲(chǔ)________________個(gè)隊(duì)列元素(設(shè)頭指針F指向當(dāng)前隊(duì)頭元素的前一個(gè)位置,尾指針指向當(dāng)前隊(duì)尾元素的位置)。
8. 設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素,則第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中_______個(gè)數(shù)據(jù)元素;刪除第i個(gè)位置上的數(shù)據(jù)元素需要移動(dòng)表中_______個(gè)元素。
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è)某無(wú)向圖G中有n個(gè)頂點(diǎn),用鄰接矩陣A作為該圖的存儲(chǔ)結(jié)構(gòu),則頂點(diǎn)i和頂點(diǎn)j互為鄰接點(diǎn)的條件是______________________。
12. 設(shè)無(wú)向圖對(duì)應(yīng)的鄰接矩陣為A,則A中第i上非0元素的個(gè)數(shù)_________第i列上非0元素的個(gè)數(shù)(填等于,大于或小于)。
13. 設(shè)前序遍歷某二叉樹的序列為ABCD,中序遍歷該二叉樹的序列為BADC,則后序遍歷該二叉樹的序列為_____________。
14. 設(shè)散列函數(shù)H(k)=k mod p,解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語(yǔ)句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點(diǎn),成功時(shí)返回指向關(guān)鍵字的指針,不成功時(shí)返回標(biāo)志0。
typedef struct node {int key; struct node *next;} lklist;
void createlkhash(lklist *hashtable[ ])
{
int i,k; lklist *s;
for(i=0;ikey=a[i];
k=a[i] % p; s->next=hashtable[k];_______________________;
}
}
三、計(jì)算題(每題10分,共30分)
1、畫出廣義表LS=(( ) , (e) , (a , (b , c , d )))的頭尾鏈表存儲(chǔ)結(jié)構(gòu)。
2、下圖所示的森林:
(1) 求樹(a)的先根序列和后根序列;
(2) 求森林先序序列和中序序列;
(3)將此森林轉(zhuǎn)換為相應(yīng)的二叉樹;
3、設(shè)散列表的地址范圍是[ 0..9 ],散列函數(shù)為H(key)= (key 2 +2)MOD 9,并采用鏈表處理沖突,請(qǐng)畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲(chǔ)結(jié)構(gòu)。
四、算法設(shè)計(jì)題(每題10分,共30分)
1. 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符),要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法,使每個(gè)單鏈表只包含同類字符。
2. 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。
3. 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉排序樹。
數(shù)據(jù)結(jié)構(gòu)試卷(五)
一、選擇題(20分)
1.?dāng)?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) 45,40,15,20
3.設(shè)一組初始記錄關(guān)鍵字序列為(25,50,15,35,80,85,20,40,36,70),其中含有5個(gè)長(zhǎng)度為2的有序子表,則用歸并排序的方法對(duì)該記錄關(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,85
4.函數(shù)substr(“DATASTRUCTURE”,5,9)的返回值為( )。
(A) “STRUCTURE” (B) “DATA”
(C) “ASTRUCTUR” (D) “DATASTRUCTURE”
5.設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn),現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序,則該操作的時(shí)間復(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)Nm
7.設(shè)有序表中有1000個(gè)元素,則用二分查找查找元素X最多需要比較( )次。
(A) 25 (B) 10 (C) 7 (D) 1
8.設(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) aedfcb
9.設(shè)輸入序列是1、2、3、……、n,經(jīng)過棧的作用后輸出序列的第一個(gè)元素是n,則輸出序列中第i個(gè)輸出元素是( )。
(A) n-i (B) n-1-i (C) n+1-i (D) 不能確定
10 設(shè)一組初始記錄關(guān)鍵字序列為(45,80,55,40,42,85),則以第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是( )。
(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. 設(shè)有一個(gè)順序共享?xiàng)[0:n-1],其中第一個(gè)棧項(xiàng)指針top1的初值為-1,第二個(gè)棧頂指針top2的初值為n,則判斷共享?xiàng)M的條件是____________________。
2. 在圖的鄰接表中用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是____________________。
3. 設(shè)有一個(gè)n階的下三角矩陣A,如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽?duì)角線上元素)存放在n(n+1)個(gè)連續(xù)的存儲(chǔ)單元中,則A[i][j]與A[0][0]之間有_______個(gè)數(shù)據(jù)元素。
4. 棧的插入和刪除只能在棧的棧頂進(jìn)行,后進(jìn)棧的元素必定先出棧,所以又把棧稱為__________表;隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行,先進(jìn)隊(duì)列的元素必定先出隊(duì)列,所以又把隊(duì)列稱為_________表。
5. 設(shè)一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)元素為ABCDEF,則該二叉樹的前序遍歷序列為___________,中序遍歷序列為___________,后序遍歷序列為___________。
6. 設(shè)一棵完全二叉樹有128個(gè)結(jié)點(diǎn),則該完全二叉樹的深度為________,有__________個(gè)葉子結(jié)點(diǎn)。
7. 設(shè)有向圖G的存儲(chǔ)結(jié)構(gòu)用鄰接矩陣A來表示,則A中第i行中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的________,第i列中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的__________。
8. 設(shè)一組初始記錄關(guān)鍵字序列(k1,k2,……,kn)是堆,則對(duì)i=1,2,…,n/2而言滿足的條件為_______________________________。
9. 下面程序段的功能是實(shí)現(xiàn)冒泡排序算法,請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。
void bubble(int r[n])
{
for(i=1;i<=n-1; i++)
{
for(exchange=0,j=0; j<_____________;j++)
if (r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;}
if (exchange==0) return;
}
}
10. 下面程序段的功能是實(shí)現(xiàn)二分查找算法,請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。
struct record{int key; int others;};
int bisearch(struct record r[ ], int k)
{
int low=0,mid,high=n-1;
while(low<=high)
{
________________________________;
if(r[mid].key==k) return(mid+1); else if(____________) high=mid-1;else low=mid+1;
}
return(0);
}
三、應(yīng)用題(32分)
1. 設(shè)某棵二叉樹的中序遍歷序列為DBEAC,前序遍歷序列為ABDEC,要求給出該二叉樹的的后序遍歷序列。
2. 設(shè)無(wú)向圖G(如右圖所示),給出該圖的最小生成樹上邊的集合并計(jì)算最小生成樹各邊上的權(quán)值之和。
3. 設(shè)一組初始記錄關(guān)鍵字序列為(15,17,18,22,35,51,60),要求計(jì)算出成功查找時(shí)的平均查找長(zhǎng)度。
4. 設(shè)散列表的長(zhǎng)度為8,散列函數(shù)H(k)=k mod 7,初始記錄關(guān)鍵字序列為(25,31,8,27,13,68),要求分別計(jì)算出用線性探測(cè)法和鏈地址法作為解決沖突方法的平均查找長(zhǎng)度。
四、算法設(shè)計(jì)題(28分)
1. 設(shè)計(jì)判斷兩個(gè)二叉樹是否相同的算法。
2. 設(shè)計(jì)兩個(gè)有序單鏈表的合并排序算法。
數(shù)據(jù)結(jié)構(gòu)試卷(六)
一、選擇題(30分)
1. 設(shè)一組權(quán)值集合W={2,3,4,5,6},則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長(zhǎng)度之和為( )。
(A) 20 (B) 30 (C) 40 (D) 45
2.執(zhí)行一趟快速排序能夠得到的序列是( )。
(A) [41,12,34,45,27] 55 [72,63]
(B) [45,34,12,41] 55 [72,63,27]
(C) [63,12,34,45,27] 55 [41,72]
(D) [12,27,45,41] 55 [34,63,72]
3.設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點(diǎn),則其判空條件是( )。
(A) head==0 (B) head->next==0
(C) head->next==head (D) head!=0
4.時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是( )。
(A) 堆排序 (B) 冒泡排序 (C) 希爾排序 (D) 快速排序
5.設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反,則該二叉樹滿足的條件是( )。
(A) 空或只有一個(gè)結(jié)點(diǎn) (B) 高度等于其結(jié)點(diǎn)數(shù)
(C) 任一結(jié)點(diǎn)無(wú)左孩子 (D) 任一結(jié)點(diǎn)無(wú)右孩子
6.一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是( )。
(A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希爾排序
7.設(shè)某棵三叉樹中有40個(gè)結(jié)點(diǎn),則該三叉樹的最小高度為( )。
(A) 3 (B) 4 (C) 5 (D) 6
8.順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為( )。
(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)
9.二路歸并排序的時(shí)間復(fù)雜度為( )。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
10. 深度為k的完全二叉樹中最少有( )個(gè)結(jié)點(diǎn)。
(A) 2k-1-1 (B) 2k-1 (C) 2k-1+1 (D) 2k-1
11.設(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->next=s;rear=s; (D) s->next=front;front=s;
12.設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊,則建立該圖鄰接表的時(shí)間復(fù)雜度為( )。
(A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3)
13.設(shè)某哈夫曼樹中有199個(gè)結(jié)點(diǎn),則該哈夫曼樹中有( )個(gè)葉子結(jié)點(diǎn)。
(A) 99 (B) 100 (C) 101 (D) 102
14.設(shè)二叉排序樹上有n個(gè)結(jié)點(diǎn),則在二叉排序樹上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為( )。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
15.設(shè)用鄰接矩陣A表示有向圖G的存儲(chǔ)結(jié)構(gòu),則有向圖G中頂點(diǎn)i的入度為( )。
(A) 第i行非0元素的個(gè)數(shù)之和 (B) 第i列非0元素的個(gè)數(shù)之和
(C) 第i行0元素的個(gè)數(shù)之和 (D) 第i列0元素的個(gè)數(shù)之和
二、判斷題(20分)
1.調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點(diǎn)。( )
2.分塊查找的平均查找長(zhǎng)度不僅與索引表的長(zhǎng)度有關(guān),而且與塊的長(zhǎng)度有關(guān)。( )
3.冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。( )
4.滿二叉樹一定是完全二叉樹,完全二叉樹不一定是滿二叉樹。( )
5.設(shè)一棵二叉樹的先序序列和后序序列,則能夠唯一確定出該二叉樹的形狀。( )
6.層次遍歷初始堆可以得到一個(gè)有序的序列。( )
7.設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT,則二叉樹BT中一定沒有右子樹。( )
8.線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。( )
9.中序遍歷二叉排序樹可以得到一個(gè)有序的序列。( )
10.快速排序是排序算法中平均性能最好的一種排序。( )
三、填空題(30分)
1.for(i=1,t=1,s=0;i<=n;i++) {t=t*i;s=s+t;}的時(shí)間復(fù)雜度為_________。
2.設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的新結(jié)點(diǎn)X,則進(jìn)行插入操作的語(yǔ)句序列為__________________________(設(shè)結(jié)點(diǎn)的指針域?yàn)閚ext)。
3.設(shè)有向圖G的二元組形式表示為G =(D,R),D={1,2,3,4,5},R={r},r={<1,2>,<2,4>,<4,5>,<1,3>,<3,2>,<3,5>},則給出該圖的一種拓?fù)渑判蛐蛄衉_________。
4.設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn),則該無(wú)向圖中每個(gè)頂點(diǎn)的度數(shù)最多是_________。
5.設(shè)二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為50,度數(shù)為1的結(jié)點(diǎn)數(shù)為30,則該二叉樹中總共有_______個(gè)結(jié)點(diǎn)數(shù)。
6.設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針,則判斷該循環(huán)隊(duì)列為空的條件為_____________________。
7.設(shè)二叉樹中結(jié)點(diǎn)的兩個(gè)指針域分別為lchild和rchild,則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_____________________________________________。
8.簡(jiǎn)單選擇排序和直接插入排序算法的平均時(shí)間復(fù)雜度為___________。
9.快速排序算法的空間復(fù)雜度平均情況下為__________,最壞的情況下為__________。
10.散列表中解決沖突的兩種方法是_____________和_____________。
四、算法設(shè)計(jì)題(20分)
1. 設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。
2. 設(shè)計(jì)判斷二叉樹是否為二叉排序樹的算法。
3. 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法
數(shù)據(jù)結(jié)構(gòu)試卷(七)
一、選擇題(30分)
1.設(shè)某無(wú)向圖有n個(gè)頂點(diǎn),則該無(wú)向圖的鄰接表中有( )個(gè)表頭結(jié)點(diǎn)。
(A) 2n (B) n (C) n/2 (D) n(n-1)
2.設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn),則該無(wú)向圖的最小生成樹上有( )條邊。
(A) n (B) n-1 (C) 2n (D) 2n-1
3.設(shè)一組初始記錄關(guān)鍵字序列為(60,80,55,40,42,85),則以第一個(gè)關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是( )。
(A) 40,42,60,55,80,85 (B) 42,45,55,60,85,80
(C) 42,40,55,60,80,85 (D) 42,40,60,85,55,80
4.( )二叉排序樹可以得到一個(gè)從小到大的有序序列。
(A) 先序遍歷 (B) 中序遍歷 (C) 后序遍歷 (D) 層次遍歷
5.設(shè)按照從上到下、從左到右的順序從1開始對(duì)完全二叉樹進(jìn)行順序編號(hào),則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為( )。
(A) 2i+1 (B) 2i (C) i/2 (D) 2i-1
6.程序段s=i=0;do {i=i+1; s=s+i;}while(i<=n);的時(shí)間復(fù)雜度為( )。
(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2)
7.設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head,則其判空條件是( )。
(A) head==0 (B) head->next==0
(C) head->next==head (D) head!=0
8.設(shè)某棵二叉樹的高度為10,則該二叉樹上葉子結(jié)點(diǎn)最多有( )。
(A) 20 (B) 256 (C) 512 (D) 1024
9.設(shè)一組初始記錄關(guān)鍵字序列為(13,18,24,35,47,50,62,83,90,115,134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個(gè)數(shù)為( )。
(A) 1 (B) 2 (C) 3 (D) 4
10.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏5臈m敚瑒t刪除棧頂元素的操作序列為( )。
(A) top=top+1; (B) top=top-1;
(C) top->next=top; (D) top=top->next;
二、判斷題(20分)
1.不論是入隊(duì)列操作還是入棧操作,在順序存儲(chǔ)結(jié)構(gòu)上都需要考慮“溢出”情況。( )
2.當(dāng)向二叉排序樹中插入一個(gè)結(jié)點(diǎn),則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。( )
3.設(shè)某堆中有n個(gè)結(jié)點(diǎn),則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(log2n)。( )
4.完全二叉樹中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。( )
5.哈夫曼樹中沒有度數(shù)為1的結(jié)點(diǎn)。( )
6.對(duì)連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點(diǎn)。( )
7.先序遍歷一棵二叉排序樹得到的結(jié)點(diǎn)序列不一定是有序的序列。( )
8.由樹轉(zhuǎn)化成二叉樹,該二叉樹的右子樹不一定為空。( )
9.線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。( )
10.帶權(quán)無(wú)向圖的最小生成樹是唯一的。( )
三、填空題(30分)
1. 設(shè)指針變量p指向雙向鏈表中的結(jié)點(diǎn)A,指針變量s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為_________=p;s->right=p->right;__________=s; p->right->left=s;(設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為left和right)。
2. 設(shè)完全有向圖中有n個(gè)頂點(diǎn),則該完全有向圖中共有________條有向條;設(shè)完全無(wú)向圖中有n個(gè)頂點(diǎn),則該完全無(wú)向圖中共有________條無(wú)向邊。
3. 設(shè)關(guān)鍵字序列為(Kl,K2,…,Kn),則用篩選法建初始堆必須從第______個(gè)元素開始進(jìn)行篩選。
4. 解決散列表沖突的兩種方法是________________和__________________。
5. 設(shè)一棵三叉樹中有50個(gè)度數(shù)為0的結(jié)點(diǎn),21個(gè)度數(shù)為2的結(jié)點(diǎn),則該二叉樹中度數(shù)為3的結(jié)點(diǎn)數(shù)有______個(gè)。
6. 高度為h的完全二叉樹中最少有________個(gè)結(jié)點(diǎn),最多有________個(gè)結(jié)點(diǎn)。
7. 設(shè)有一組初始關(guān)鍵字序列為(24,35,12,27,18,26),則第3趟直接插入排序結(jié)束后的結(jié)果的是__________________________________。
8. 設(shè)有一組初始關(guān)鍵字序列為(24,35,12,27,18,26),則第3趟簡(jiǎn)單選擇排序結(jié)束后的結(jié)果的是__________________________________。
9. 設(shè)一棵二叉樹的前序序列為ABC,則有______________種不同的二叉樹可以得到這種序列。
10. 下面程序段的功能是實(shí)現(xiàn)一趟快速排序,請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。
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(ix.key) j=j-1; if (i
下載提示(請(qǐng)認(rèn)真閱讀)
- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
文檔包含非法信息?點(diǎn)此舉報(bào)后獲取現(xiàn)金獎(jiǎng)勵(lì)!
下載文檔到電腦,查找使用更方便
9.9
積分
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
-
廣州大學(xué)
數(shù)據(jù)結(jié)構(gòu)
試題
- 溫馨提示:
1: 本站所有資源如無(wú)特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
裝配圖網(wǎng)所有資源均是用戶自行上傳分享,僅供網(wǎng)友學(xué)習(xí)交流,未經(jīng)上傳用戶書面授權(quán),請(qǐng)勿作他用。
鏈接地址:http://www.hcyjhs8.com/p-9364972.html