數(shù)據(jù)結(jié)構(gòu)填空題大全_第1頁
數(shù)據(jù)結(jié)構(gòu)填空題大全_第2頁
數(shù)據(jù)結(jié)構(gòu)填空題大全_第3頁
數(shù)據(jù)結(jié)構(gòu)填空題大全_第4頁
數(shù)據(jù)結(jié)構(gòu)填空題大全_第5頁
已閱讀5頁,還剩7頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、數(shù)據(jù)結(jié)構(gòu)填空題大全二、填空題(每題6分,共24分)1. 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的聯(lián)系。當(dāng)結(jié)點之間存在 M對N ( M : N)的聯(lián)系時,稱這種結(jié)構(gòu)為圖或者是圖的結(jié)構(gòu)2. 隊列的插入操作是在隊列的尾 進(jìn)行,刪除操作是在隊列的首 進(jìn)行。3. 當(dāng)用長度為N的數(shù)組順序存儲一個棧時,假定用top=N表示??眨瑒t表示棧滿的條件是top=0 (要超出才為滿)。4. 對于一個長度為 n的單鏈存儲的線性表,在表頭插入元素的時間復(fù)雜度為0(1),在表尾插入元素的時間復(fù)雜度為0(n)。5. 設(shè)W為一個二維數(shù)組,其每個數(shù)據(jù)元素占用 4個字節(jié),行下標(biāo)i從0到7,列下標(biāo)j從0 到3,則二維數(shù)組 W的數(shù)據(jù)元素共占用

2、128個字節(jié)。W中第6行的元素和第4列的元素 共占用_44_個字節(jié)。若按行順序存放二維數(shù)組 W,其起始地址為100,則二維數(shù)組元素 W6, 3的起始地址為 108。6. 廣義表A= (a,(a,b),(a,b),c),則它的深度為,它的長度為丄。7. 二叉樹是指度為2的 有序樹。一棵結(jié)點數(shù)為 N的二叉樹,其所有結(jié)點的度的總和是n-1。8. 對一棵二叉搜索樹進(jìn)行中序遍歷時,得到的結(jié)點序列是一個有序序列有序列表。對一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到的結(jié)點序列是該算術(shù)表達(dá)式的_后綴表達(dá)式后綴表達(dá)式(或歹U波蘭式) 。9. 對于一棵具有 n個結(jié)點的二叉樹,用二叉鏈表存儲時,其指針總數(shù)為_

3、2n_個,其中n-1個用于指向孩子,n+1個指針是空閑的。點的有向完全圖中,包含有_n(n-1)_條邊。9. 假定一個線性表為(12,23,74,55,63,40),若按Key % 4條件進(jìn)行劃分,使得同一余數(shù)的元素成為一個子表,則得到的四個子表分別為(12,40)、_( )、_(_74)和 _(23,55,63)。10. 向一棵B_樹插入元素的過程中,若最終引起樹根結(jié)點的分裂,則新樹比原樹的高度 增加1。11. 在堆排序的過程中,對任一分支結(jié)點進(jìn)行篩運算的時間復(fù)雜度為O (Iog2 n),整個堆排序過程的時間復(fù)雜度為_O( nlog2 n)_。12. 在快速排序、堆排序、歸并排序中,歸并 排

4、序是穩(wěn)定的。二、填空題(每空1分,共32分)1、 數(shù)據(jù)的邏輯結(jié)構(gòu)被分為 _集合、線性、樹和圖四種。2、 一種抽象數(shù)據(jù)類型包括 數(shù)據(jù)描述和 操作聲明兩個部分。3、 在下面的數(shù)組a中鏈接存儲著一個線性表,表頭指針為ao.next,則該線性表為_ (38,56, 25, 60, 42, 74)。4、在以HL為表頭指針的帶表頭附加結(jié)點的單鏈表和循環(huán)單鏈表中,判斷鏈表為空的條件分別為HL tnext =NULL 和HL=HL 宀 next; 。5、用具有n個元素的一維數(shù)組存儲一個循環(huán)隊列,則其隊首指針總是指向隊首元素的前一個位置 ,該循環(huán)隊列的最大長度為 n-1。6、 當(dāng)堆棧采用順序存儲結(jié)構(gòu)時,棧頂元素

5、的值可用S.stack S.top表示;當(dāng)堆棧采用鏈接存儲結(jié)構(gòu)時,棧頂元素的值可用_ HS t data _表示。7、 一棵高度為5的二叉樹中最少含有 5個結(jié)點,最多含有 31個結(jié)點;&在圖的鄰接表中,每個結(jié)點被稱為 邊結(jié)點,通常它包含三個域:一是 鄰接點域 _; 二是權(quán)域; 三是鏈域。9、 在一個索引文件的索引表中,每個索引項包含對應(yīng)記錄的_索引值域和_開始位置域兩項數(shù)據(jù)。10、 假定一棵樹的廣義表表示為 A ( B ( C, D (E, F, G), H (I, J),則樹中所含的結(jié) 點數(shù)為10個,樹的深度為 3,樹的度為3,結(jié)點H的雙親結(jié)點為b,孩子結(jié)點為 i和J 。11、 在堆

6、排序的過程中,對任一分支結(jié)點進(jìn)行篩運算的時間復(fù)雜度為_ O (Iog2n) _,整個堆排序過程的時間復(fù)雜度為 O(nlog 2n) _。12、 在對m階的B_樹插入元素的過程中,每向一個結(jié)點插入一個索引項(葉子結(jié)點中的索引項為關(guān)鍵字和空指針)后,若該結(jié)點的索引項數(shù)等于M個,則必須把它分裂為M-1個結(jié)點。第二部分非選擇題(共70分)二、填空題(本大題共 10小題,每小題2分,若有兩個空格,每個空格1分,共20分)不寫解答過程,將正確的答案寫在每小題的空格內(nèi)。錯填或不填均無分。16數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù),它與數(shù)據(jù)的存儲(或存儲結(jié)構(gòu))無關(guān),是獨立于計算機(jī)的。17.在一個帶頭結(jié)點的單循環(huán)

7、鏈表中,p指向尾結(jié)點的直接前驅(qū),則指向頭結(jié)點的指針 head可用 p 表示為 head= p> next> next。18棧頂?shù)奈恢檬请S著 進(jìn)棧和退棧 操作而變化的。19. 在串S= “ structure”中,以t為首字符的子串有12 個。B中,其中B0存儲個葉子結(jié)點。20. 假設(shè)一個9階的上三角矩陣 A按列優(yōu)先順序壓縮存儲在一維數(shù)組矩陣中第1個元素a1,1則B31中存放的元素是 _048 。21. 已知一棵完全二叉樹中共有768結(jié)點,則該樹中共有_J8422. 已知一個圖的廣度優(yōu)先生成樹如右圖所示,則與此相 應(yīng)的廣度優(yōu)先遍歷序列為。23. 在單鏈表上難以實現(xiàn)的排序方法有快速排序

8、和 堆排序,希爾排序。24. 在有序表(12, 24, 36, 48, 60, 72, 84)中二分查找關(guān)鍵字 72時所需進(jìn)行的關(guān)鍵字 比較次數(shù)為_2 。25. 多重表文件和倒排文件都?xì)w屬于多關(guān)鍵字文件。1設(shè)順序循環(huán)隊列 Q0: m-1的隊頭指針和隊尾指針分別為 F和R,其中隊頭指針F指向當(dāng) 前隊頭元素的前一個位置,隊尾指針R指向當(dāng)前隊尾元素所在的位置,則出隊列的語句為 F=(F+1) % m;。2. 設(shè)線性表中有n個數(shù)據(jù)元素,則在順序存儲結(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為O(n),在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為_ O(n)。3. 設(shè)一棵二叉樹中有n個結(jié)點,則當(dāng)用二叉鏈表作為

9、其存儲結(jié)構(gòu)時,該二叉鏈表中共有2n個指針域,n+1個空指針域。4. 設(shè)指針變量p指向單鏈表中結(jié)點 A,指針變量s指向被插入的結(jié)點 B,則在結(jié)點A的后面插入結(jié)點B的操作序列為s->next=p->next; s->next=s_。5. 設(shè)無向圖G中有n個頂點和e條邊,則其對應(yīng)的鄰接表中有 n個表頭結(jié)點和2e個表結(jié)點。6. 設(shè)無向圖G中有n個頂點e條邊,所有頂點的度數(shù)之和為m,貝U e和m有_m=2e關(guān)系。7. 設(shè)一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC,則該二叉樹的后序遍歷序列為_cba。8. 設(shè)一棵完全二叉樹中有21個結(jié)點,如果按照從上到下、從左到右的順序從1開始順序

10、編號,則編號為 8的雙親結(jié)點的編號是 4,編號為8的左孩子結(jié)點的編號是16。9. 下列程序段的功能實現(xiàn)子串t在主串s中位置的算法,要求在下劃線處填上正確語句。int in dex(char s , char t)i=j=0;while(i<strle n(s) && j<strle n( t) if(si=tj)i=i+l; j=j+l;elsei=_i-j+1; j=0;if (j=strlen(t)return(i-strlen(t);else return (-1);10. 設(shè)一個連通圖G中有n個頂點e條邊,則其最小生成樹上有_n-1條邊。二、填空題(24分)

11、1. 為了能有效地應(yīng)用HASH查找技術(shù),必須解決的兩個問題是_構(gòu)造一個好的HASH函數(shù)禾廿確定解決沖突的方法。2. 下面程序段的功能實現(xiàn)數(shù)據(jù)x進(jìn)棧,要求在下劃線處填上正確的語句。typedef struct int s100; int top; sqstack;void push(sqstack &stack,i nt x)if (stack.top=m- 1) printf( “ overflow ” );1. else stack.top+;stack.sstack.top=x;3. 中序遍歷二叉排序樹所得到的序列是 有序序列(填有序或無序)。4. 快速排序的最壞時間復(fù)雜度為 0(

12、n2),平均時間復(fù)雜度為0(nlog 2n)。5. 設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為NO,度數(shù)為1的結(jié)點數(shù)為N1,則該二叉樹中度數(shù)為2的結(jié)點數(shù)為 N0-1;若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu),則該二叉樹中共有2N0+N 1個空指針域。2. 6.設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e,所有頂點的度數(shù)之和為d,則e=_d/2_。7. 設(shè)一組初始記錄關(guān)鍵字序列為(55,63,44,38,75,80,31,56),則利用篩選法建立的初始堆為 (31,38,54,56,75,80,55,63)。v - 3 - - 2 - - 4V? - 1 - 3v3 728. 設(shè)某無向圖G的鄰接表為43,則從頂點V1

13、開始的深度優(yōu)先遍歷序列為(1,3,4,2);廣度優(yōu)先遍歷序列為 (1,3,2,4)。填空殖(48分,其中最后兩小題各 6分)1. 數(shù)據(jù)的物理結(jié)構(gòu)主要包括 順序存儲結(jié)構(gòu)_ 和_鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種情況。2. 設(shè)一棵完全二叉樹中有500個結(jié)點,則該二叉樹的深度為_9_;若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu),則共有 501個空指針域。3. 設(shè)輸入序列為1、2、3,則經(jīng)過棧的作用后可以得到 5種不同的輸出序列。4. 設(shè)有向圖G用鄰接矩陣Ann作為存儲結(jié)構(gòu),則該鄰接矩陣中第i行上所有元素之和等于頂點i的出度,第i列上所有元素之和等于頂點i的入度。5. 設(shè)哈夫曼樹中共有 n個結(jié)點,則該哈夫曼樹中有_0個度數(shù)

14、為1的結(jié)點。6. 設(shè)有向圖G中有n個頂點e條有向邊,所有的頂點入度數(shù)之和為d,貝U e和d的關(guān)系為e=d。7. 中序遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列(填先序、中序或后序)。8. 設(shè)查找表中有 100個元素,如果用二分法查找方法查找數(shù)據(jù)元素X,則最多需要比較7次就可以斷定數(shù)據(jù)元素X是否在查找表中。9. 不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧,其入棧和出棧操作的時間復(fù)雜度均為0(1)。10. 設(shè)有n個結(jié)點的完全二叉樹,如果按照從自上到下、從左到右從1開始順序編號,則第i個結(jié)點的雙親結(jié)點編號為U2,右孩子結(jié)點的編號為_21+。11. 設(shè)一組初始記錄關(guān)鍵字為(72,73,71,2

15、3,94,16,5),則以記錄關(guān)鍵字 72為基準(zhǔn)的一趟快速排序結(jié)果為(5,16,71,23,72,94,73。12. 設(shè)有向圖G中有向邊的集合 E=1,2,2,3,1,4,4,2,4,3,則該圖的一種拓?fù)湫蛄袨椋?,4,3,2)。13. 下列算法實現(xiàn)在順序散列表中查找值為x的關(guān)鍵字,請在下劃線處填上正確的語句。struct recordi nt key; int others;int hashsqsearch(struct record hashtable ,i nt k)int i,j; j=i=k % p;while (hashtablej.key!=k&&hashtabl

16、ej.flag!=0)j=(_j+1) %m; if (i=j) return(-1);if (hashtablej.key=k) return (j); else return( -1);14. 下列算法實現(xiàn)在二叉排序樹上查找關(guān)鍵值k,請在下劃線處填上正確的語句。typedef struct no de 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)r

17、eturn(t) else if (t->key>k) t=t->lchild; else_ t=t->rchild;二、填空題(42分)21. 設(shè)有n個無序的記錄關(guān)鍵字,則直接插入排序的時間復(fù)雜度為_ O(n ),快速排序的平均時間復(fù)雜度為 O(nlog 2n)。2 .設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點 X,則刪除結(jié)點X需要執(zhí)行的語句序列為 p>llink->rlink=p->rlink; p->rlink->llink=p->rlink (設(shè)結(jié)點中的兩個指針域分別為llink 和rlink )。3根據(jù)初始關(guān)鍵字序列(19, 22

18、, 01, 38, 10)建立的二叉排序樹的高度為 3_。4深度為k的完全二叉樹中最少有_2k-1_個結(jié)點。5. 設(shè)初始記錄關(guān)鍵字序列為(K1 , K2 ,,Kn),則用篩選法思想建堆必須從第_ n/2_個元素開始進(jìn)行篩選。6. 設(shè)哈夫曼樹中共有99個結(jié)點,則該樹中有 50_個葉子結(jié)點;若采用二叉鏈表作為存儲結(jié)構(gòu),則該樹中有51個空指針域。7. 設(shè)有一個順序循環(huán)隊列中有M個存儲單元,則該循環(huán)隊列中最多能夠存儲_m-1個隊列元素;當(dāng)前實際存儲_(R-F+M)%M 個隊列元素(設(shè)頭指針F指向當(dāng)前隊頭元素的前一個位置,尾指針指向當(dāng)前隊尾元素的位置)。&設(shè)順序線性表中有n個數(shù)據(jù)元素,則第i個位

19、置上插入一個數(shù)據(jù)元素需要移動表中_n+1-i個數(shù)據(jù)元素;刪除第i個位置上的數(shù)據(jù)元素需要移動表中_ n-i _個元素。9. 設(shè)一組初始記錄關(guān)鍵字序列為(20, 18, 22, 16, 30, 19),則以20為中軸的一趟快速排序結(jié)果為 (19 , 18, 16, 20, 30, 22)。10. 設(shè)一組初始記錄關(guān)鍵字序列為(20, 18, 22, 16, 30, 19),則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為 (16 , 18, 19, 20, 32 , 22)。11設(shè)某無向圖 G中有n個頂點,用鄰接矩陣A作為該圖的存儲結(jié)構(gòu),則頂點i和頂點j互為鄰接點的條件是Aij=1。12 設(shè)無向圖對應(yīng)的鄰接矩

20、陣為A,則A中第i上非0元素的個數(shù)一等于第i列上非0元素的個數(shù)(填等于,大于或小于)。13. 設(shè)前序遍歷某二叉樹的序列為ABCD ,中序遍歷該二叉樹的序列為BADC,則后序遍歷該二叉樹的序列為 BDCA。14. 設(shè)散列函數(shù)H(k)=k mod p,解決沖突的方法為鏈地址法。 要求在下列算法劃線處填上正 確的語句完成在散列表 hashtalbe中查找關(guān)鍵字值等于 k的結(jié)點,成功時返回指向關(guān)鍵字的指針,不成功時返回標(biāo)志0。typedef struct node int key; struct node *n ext; Iklist;void createlkhash(lklist *hashtab

21、le)int i,k; lklist *s;for(i=0;i<m;i+) hashtablei=0;for(i=0;i< n;i+)s=(lklist *)malloc(sizeof(lklist); s_>key=ai;k=ai % p; s->next=hashtablek;hashtablek=s;二、填空題洪30分)1. 設(shè)有一個順序共享棧S0: n-1,其中第一個棧項指針topi的初值為-1,第二個棧頂指針top2的初值為n,則判斷共享棧滿的條件是_top1+1=top2。2. 在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點的優(yōu)點是 可以隨機(jī)訪問到任一個頂點的簡單

22、鏈表。3. 設(shè)有一個n階的下三角矩陣 A,如果按照行的順序?qū)⑾氯蔷仃囍械脑?包括對角線上元素)存放在n(n+1)個連續(xù)的存儲單元中,則Aij與A00之間有i(i+1)/2+j-1個數(shù)據(jù)元素。4. 棧的插入和刪除只能在棧的棧頂進(jìn)行,后進(jìn)棧的元素必定先出棧,所以又把棧稱為FILO 表;隊列的插入和刪除運算分別在隊列的兩端進(jìn)行,先進(jìn)隊列的元素必定先出隊列,所以又把隊列稱為 FIFO表。5. 設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF,則該二叉樹的前序遍歷序列為 ABDECF ,中序遍歷序列為 DBEAFC ,后序遍歷序列為DEBFCA。6. 設(shè)一棵完全二叉樹有128個結(jié)點,則該完

23、全二叉樹的深度為_8,有64個葉子結(jié)點。7. 設(shè)有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示,則A中第i行中所有非零元素個數(shù)之和等于頂點i的出度,第i列中所有非零元素個數(shù)之和等于頂點i的入度 。8. 設(shè)一組初始記錄關(guān)鍵字序列(k1 , k2,kn)是堆,則對i=1 , 2,,n/2而言滿足的條件為ki<=kg && k j<=k2i+1。9. 下面程序段的功能是實現(xiàn)冒泡排序算法,請在下劃線處填上正確的語句。void bubble(i nt rn)for(i=1;i<=n-1; i+)for(exchange=0,j=0; j< n_i;j+)if (rj>

24、rj+1)temp=rj+1;rj+1=rj;rj=temp;excha nge=1;if (exchange=0) return ;10. 下面程序段的功能是實現(xiàn)二分查找算法,請在下劃線處填上正確的語句。struct recordi nt key; int others;int bisearch(struct record r , i nt k)int low=0,mid,high=n-1;while(low<=high)mid=(low+high)/2;if(rmid.key=k) return(mid+1); else if(_rmid.key>k) high=mid-1;e

25、lse low=mid+1;return(O);三、填空題(30分)1. for(i=1 , t=1 , s=0; i<=n ; i+) t=t*i ; s=s+t; 的時間復(fù)雜度為 O(n)。2 .設(shè)指針變量p指向單鏈表中結(jié)點A,指針變量s指向被插入的新結(jié)點X,則進(jìn)行插入操作的語句序列為 s->next=p->next; p->next=s (設(shè)結(jié)點的指針域為next)。3. 設(shè)有向圖 G 的二元組形式表示為 G =( D,R), D=1,2,3, 4,5,R=r,r=<1,2>, <2,4> , <4,5> , <1,3&g

26、t; , <3,2> , <3,5>,則給出該圖的一種拓?fù)渑判蛐蛄?_ (1 , 3, 2, 4, 5)。4. 設(shè)無向圖G中有n個頂點,則該無向圖中每個頂點的度數(shù)最多是_n-1。5. 設(shè)二叉樹中度數(shù)為0的結(jié)點數(shù)為50,度數(shù)為1的結(jié)點數(shù)為30,則該二叉樹中總共有129個結(jié)點數(shù)。6 設(shè)F和R分別表示順序循環(huán)隊列的頭指針和尾指針,則判斷該循環(huán)隊列為空的條件為F=R。7.設(shè)二叉樹中結(jié)點的兩個指針域分別為lchild和rchild ,則判斷指針變量p所指向的結(jié)點為葉子結(jié)點的條件是 p->lchild=0&&p->rchild=0 。&簡單選擇排

27、序和直接插入排序算法的平均時間復(fù)雜度為 O(n2)。9 .快速排序算法的空間復(fù)雜度平均情況下為O(nlog2n),最壞的情況下為 _O(n)。10. 散列表中解決沖突的兩種方法是開放定址法和鏈地址法 。三、填空題(30分)1. 設(shè)指針變量p指向雙向鏈表中的結(jié)點 A ,指針變量s指向被插入的結(jié)點X ,則在結(jié)點A 的后面插入結(jié)點 X 的操作序列為 _ s->left=p =p; s->right=p->right ; p->right=s; p->right->left=s ;(設(shè)結(jié)點中的兩個指針域分別為left和right )。2. 設(shè)完全有向圖中有 n個頂點

28、,則該完全有向圖中共有 _ n(n-1)條有向條;設(shè)完全無向圖中有n個頂點,則該完全無向圖中共有 n(n-1)/2條無向邊。3. 設(shè)關(guān)鍵字序列為(KI , K2 ,,Kn),則用篩選法建初始堆必須從第n/2_個元素開始進(jìn)行篩選。4. 解決散列表沖突的兩種方法是 開放定址法和鏈地址法。5. 設(shè)一棵三叉樹中有50個度數(shù)為0的結(jié)點,21個度數(shù)為2的結(jié)點,則該二叉樹中度數(shù)為3的結(jié)點數(shù)有_14個。6. 高度為h的完全二叉樹中最少有 2h-1_個結(jié)點,最多有_2h-1_個結(jié)點。7. 設(shè)有一組初始關(guān)鍵字序列為(24, 35, 12, 27, 18, 26),則第3趟直接插入排序結(jié)束后的結(jié)果的是 (12, 2

29、4, 35, 27, 18, 26)。8. 設(shè)有一組初始關(guān)鍵字序列為(24, 35, 12, 27, 18, 26),則第3趟簡單選擇排序結(jié)束后的結(jié)果的是 (12 , 18, 24, 27 , 35, 26)。9. 設(shè)一棵二叉樹的前序序列為 ABC,則有5種不同的二叉樹可以得到這種序列。10. 下面程序段的功能是實現(xiàn)一趟快速排序,請在下劃線處填上正確的語句。struct record int key;datatype others;void quickpass(struct record r, int s, int t, i nt &i)int j=t; struct record x

30、=rs; i=s;while(i<j)while (i<j && rj.key>x.key) j=j-1; if (i<j) ri=rj;i=i+1;while (i<j && ri.key<x.key) i=i+1; if (i<j) rj=ri;j=j-1;ri=x;三、填空題(30分)1. 設(shè)一組初始記錄關(guān)鍵字序列為(49, 38, 65, 97, 76, 13, 27, 50),則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為 (49, 13 , 27, 50, 76, 38, 65, 97)。2. 下面程序段的功能

31、是實現(xiàn)在二叉排序樹中插入一個新結(jié)點,請在下劃線處填上正確的內(nèi) 容。typedef struct nodeint data;struct node *lchild;struct node *rchild;bitree;voidbst in sert(bitree *& t,i nt k)if(t=0) _ _t=(bitree )malloc(sizeof(bitree) _ 一:t->data=k:t->lchild=t->rchild=0:else if (t->data>k) bstinsert(t->lchild,k);elsebstinser

32、t(t->rchild,k):3. 設(shè)指針變量p指向單鏈表中結(jié)點A,指針變量s指向被插入的結(jié)點 X,則在結(jié)點A的后面插入結(jié)點 X需要執(zhí)行的語句序列:s->next=p->next;p->next=s:。4. 設(shè)指針變量head指向雙向鏈表中的頭結(jié)點,指針變量p指向雙向鏈表中的第一個結(jié)點,則指針變量 p和指針變量 head之間的關(guān)系是 p=head->rlink和head=p->llink (設(shè)結(jié)點中的兩個指針域分別為llink和rlink )。5. 設(shè)某棵二叉樹的中序遍歷序列為ABCD,后序遍歷序列為BADC,則其前序遍歷序列為_ CABD。6完全二叉樹中第

33、5層上最少有 1個結(jié)點,最多有 16個結(jié)點。7.設(shè)有向圖中不存在有向邊<Vi,Vj>,則其對應(yīng)的鄰接矩陣A中的數(shù)組元素 Aij的值等于_0_。& 設(shè)一組初始記錄關(guān)鍵字序列為(49, 38, 65, 97, 76, 13, 27, 50),則第4趟直接選擇排序結(jié)束后的結(jié)果為(13, 27, 38, 50, 76, 49, 65, 97)。9 .設(shè)連通圖G中有n個頂點e條邊,則對應(yīng)的最小生成樹上有 n-1條邊。10.設(shè)有一組初始記錄關(guān)鍵字序列為(50, 16, 23, 68, 94, 70 , 73),則將它們調(diào)整成初始堆只需把16與_50_相互交換即可。二、填空題(30分)1

34、 .設(shè)指針p指向單鏈表中結(jié)點 A,指針s指向被插入的結(jié)點X,則在結(jié)點A的前面插入結(jié)點X時的操作序列為:1) s->next=p->next; 2) p->next=s ; 3) t=p->data ;4) p->data=s->data; 5) s->data=t;2 設(shè)某棵完全二叉樹中有 100個結(jié)點,則該二叉樹中有 50個葉子結(jié)點。3. 設(shè)某順序循環(huán)隊列中有m個元素,且規(guī)定隊頭指針F指向隊頭元素的前一個位置,隊尾指針R指向隊尾元素的當(dāng)前位置,則該循環(huán)隊列中最多存儲m-1隊列元素。4. 對一組初始關(guān)鍵字序列(40, 50, 95,20,15,70,

35、60, 45,10)進(jìn)行冒泡排序,則第 一趟需要進(jìn)行相鄰記錄的比較的次數(shù)為6,在整個排序過程中最多需要進(jìn)行8趟排序才可以完成。5. 在堆排序和快速排序中,如果從平均情況下排序的速度最快的角度來考慮應(yīng)最好選擇快速排序,如果從節(jié)省存儲空間的角度來考慮則最好選擇堆排序。6 .設(shè)一組初始記錄關(guān)鍵字序列為(20 , 12, 42, 31 , 18, 14, 28),則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長度是 19/7。7.設(shè)一棵二叉樹的中序遍歷序列為BDCA,后序遍歷序列為 DBAC,則這棵二叉樹的前序序列為CBDA。& 設(shè)用于通信的電文僅由 8個字母組成,字母在電文中出現(xiàn)的頻率分別為

36、7、19、2、6、32、3、21、10,根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹,則這棵哈夫曼樹的高度為69. 設(shè)一組記錄關(guān)鍵字序列為 (80, 70, 33, 65, 24, 56, 48),則用 篩選法建成的初始堆為 _(24, 65, 33, 80, 70, 56, 48)<10. 設(shè)無向圖G (如右圖所示),則其最小生成樹上所有邊的權(quán)值之和為8。二、填空題(48分,其中最后兩小題各6分)1. 設(shè)需要對 5個不同的記錄關(guān)鍵字進(jìn)行排序,則至少需要比較4次,至多需要比較 10次。2. 快速排序算法的平均時間復(fù)雜度為 O(nlog2n),直接插入排序算法的平均時間復(fù)雜度為0(n2)。3. 設(shè)二叉

37、排序樹的高度為h,則在該樹中查找關(guān)鍵字key最多需要比較 n次。4. 設(shè)在長度為20的有序表中進(jìn)行二分查找,則比較一次查找成功的結(jié)點數(shù)有 1個,比較兩次查找成功有結(jié)點數(shù)有 2個。5. 設(shè)一棵m叉樹脂的結(jié)點數(shù)為n,用多重鏈表表示其存儲結(jié)構(gòu),則該樹中有_n(m-1)+1個空指針域。6. 設(shè)指針變量p指向單鏈表中結(jié)點 A,則刪除結(jié)點A的語句序列為:q=p->next; p->data=q->data; p_>next=q_>next ; feee(q);7. 數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型:線性結(jié)構(gòu) 、樹型結(jié)構(gòu)和_圖型結(jié)構(gòu)_。8. 設(shè)無向圖G中有n個頂點e條邊,則用

38、鄰接矩陣作為圖的存儲結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷時的時間復(fù)雜度為O(n2);用鄰接表作為圖的存儲結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷的時間復(fù)雜度為 O(n+e)。9. 設(shè)散列表的長度為 8,散列函數(shù)H(k)=k % 7,用線性探測法解決沖突,則根據(jù)一組初始關(guān)鍵字序列(8, 15, 16, 22, 30, 32)構(gòu)造出的散列表的平均查找長度是_8/3。10. 設(shè)一組初始關(guān)鍵字序列為(38, 65, 97, 76, 13, 27, 10),則第3趟冒泡排序結(jié)束后的結(jié)果為 _(38, 13, 27, 10, 65, 76, 97)。11. 設(shè)一組初始關(guān)鍵字序列為(38, 65, 97, 76, 13, 27, 10),則第3趟簡單選擇排序后的結(jié)果為 _(10, 13, 27, 76, 65, 97, 38)。1.12.設(shè)有向圖 G 中的有向邊的集合 E=<1 , 2> , <2, 3>, <1 , 4>, <4, 5> , <5 , 3> ,<4 , 6> , <6 , 5>,則該圖的一個拓?fù)湫蛄?/p>

溫馨提示

  • 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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論