數(shù)據(jù)結(jié)構(gòu)-復(fù)習(xí)題-FXT252259-1706

1、 18/18數(shù)據(jù)結(jié)構(gòu) 復(fù)習(xí)題（課程代碼 252259）一、填空題（本大題共40小題）隊(duì)列中是按照_先進(jìn)先出_的原則進(jìn)行數(shù)據(jù)元素的增刪。_棧_又稱為LIFO表。在順序存儲(chǔ)的完全二叉樹中，若編號(hào)為i的結(jié)點(diǎn)有左孩子結(jié)點(diǎn)，則其右孩子結(jié)點(diǎn)的編號(hào)為_2i+1_。存儲(chǔ)地址與關(guān)鍵字之間存在某種映射關(guān)系的存儲(chǔ)結(jié)構(gòu)為_散列存儲(chǔ)結(jié)構(gòu)_。在串S=“structure”中，以r為首字符的子串有_9_個(gè)。設(shè)有整型二維數(shù)組M43，每個(gè)元素（整數(shù)）占2個(gè)存儲(chǔ)單元，元素按行的順序存儲(chǔ)，數(shù)組的起始地址為200，元素M11的地址是_208_。在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，包含有_ n(n-1)/2_條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有

2、向完全圖中，包含有_ n(n-1)_條邊。假定一個(gè)線性表為(12,23,74,55,63,40)，若按Key % 4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為_（12，40） （ ） （74） （23,55，63）_。向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度_增加1_。在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_ O(log2n)_，整個(gè)堆排序過程的時(shí)間復(fù)雜度為_ O(nlog2n)_。在快速排序、堆排序、歸并排序中，_歸并_排序是穩(wěn)定的。一棵深度為5的滿二叉樹中的結(jié)點(diǎn)數(shù)為_31_個(gè)。在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩

3、陣中,非零元素的個(gè)數(shù)為_2e _。從一棵二叉排序樹中查找一個(gè)元素時(shí)，若元素的值大于根結(jié)點(diǎn)的值，則繼續(xù)向_右子樹_查找。_拓樸排序_可以判斷出一個(gè)有向圖中是否有環(huán)。棧又稱為_后進(jìn)先出_的線性表。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為數(shù)據(jù)的_物理結(jié)構(gòu)_。有4個(gè)結(jié)點(diǎn)的不同的二叉樹有_9_棵。含有60個(gè)結(jié)點(diǎn)的樹有_59_條分支。在圖結(jié)構(gòu)中，前驅(qū)元素和后繼元素之間存在著_多對(duì)多_的聯(lián)系。_哈夫曼樹_又稱最優(yōu)二叉樹。一棵二叉樹有67個(gè)結(jié)點(diǎn)，這些結(jié)點(diǎn)的度要么是0，要么是2。這棵二叉樹中度為2的結(jié)點(diǎn)有_33_個(gè)。在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針head可用p表示為head=_ p

4、nextnext _。棧頂?shù)奈恢檬请S著_進(jìn)棧和出棧_操作而變化的。設(shè)一個(gè)散列表的容量為M，用線性探測法解決沖突.。若要查找一個(gè)鍵值，至少要進(jìn)行1次比較，至多要進(jìn)行_M_次比較。在n個(gè)結(jié)點(diǎn)的線索二叉鏈表中，有_ n-1_個(gè)線索指針。具有180個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為_8_。序列中有1000個(gè)元素基本按鍵值遞增順序排列，就算法的比較次數(shù)而言，應(yīng)選擇_ _直接插入_排序算法。若堆棧的入棧序列為1,2,3,n-1,n，輸出元素i需要進(jìn)行_ n-i+1_次出棧操作。對(duì)于隊(duì)，只能在 隊(duì)尾 插入元素，只能在 隊(duì)頭 刪除元素。抽象數(shù)據(jù)類型ADT可以用三元組（D，S，P）表示，它們分別表示： 數(shù)據(jù)對(duì)象 、

5、數(shù)據(jù)關(guān)系 和 基本操作 。棧是一種受限制的線性表，也叫LIFO結(jié)構(gòu)，LIFO的含義是 后進(jìn)先出 在單鏈表中，若要在指針p所指結(jié)點(diǎn)后插入指針s所指結(jié)點(diǎn)，則需要執(zhí)行下列兩條語句：s-next=p-next； p-next=s 通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：_正確性 易讀性 強(qiáng)壯性 高效率_。一個(gè)算法的時(shí)間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級(jí)表示為_ O(n)_。假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J），則樹中所含的結(jié)點(diǎn)數(shù)為_9_個(gè)，樹的深度為_3_，樹的度為_3_。后綴算式9 2 3 +- 10 2 / -的值為_1_。中綴算式（3+4X）-2Y/3對(duì)應(yīng)的

6、后綴算式為_3 4 X * + 2 Y * 3 / -_。若用鏈表存儲(chǔ)一棵二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹共有_2n_個(gè)指針域，其中有_n-1_個(gè)指針域是存放了地址，有_n+1_個(gè)指針是空指針。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有_e_個(gè)和_2e_個(gè)。AOV網(wǎng)是一種_有向無回路_的圖。二、單項(xiàng)選擇題（本大題共50小題）將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（D ）A）O（1） B）O（n） C）O（m） D）O（m+n）如下所示的圖的拓?fù)湫蛄袨椋?D）C1C

7、2C3C4C5C6A） C1，C2，C3，C4，C5，C6C1，C2，C5，C3，C4，C5，C7C1，C4，C2，C3，C5，C6C1，C2，C5，C4，C3，C6在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中,零元素的個(gè)數(shù)為( D )A）e B）2e C）n2e D）n22e設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)該有(A)條邊才能確保是一個(gè)連通圖A5 B6 C7 D8有N個(gè)結(jié)點(diǎn)的圖的鄰接矩陣存儲(chǔ)法中，鏈表的表頭結(jié)點(diǎn)有（ A ）個(gè)。A、 N B、 2N C、N/2 D、N*N E、N-2具有4個(gè)頂點(diǎn)的無向完全圖有（ A ）條邊。A、6 B、12 C、16 D、20鄰接矩陣是對(duì)稱矩陣的圖為(D ）。A、有

8、向圖 B、帶權(quán)有向圖 C、帶權(quán)連通圖 D、無向圖在長度為n的線性表中查找值為x的數(shù)據(jù)元素的時(shí)間復(fù)雜度為（C）。A）O(0)B）O(1)C）O(n)D）O(n2)若一個(gè)棧的輸入序列是1，2，3，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素是（D）。A）不確定B）n-iC、n-i-1D、n-i+1設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6依次通過棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)的順序是e2,e4,e3,e6,e5,e1，則棧的容量至少應(yīng)該是（C）。A、6B、4C、3D、2一個(gè)棧的入棧序列是1，2，3，4，5，則棧的不可能的出棧序列是（C）。A、5，4，3

9、，2，1B、4，5，3，2，1C、4，3，5，1，2D、1，2，3，4，5設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否匹配的算法，采用（B）數(shù)據(jù)結(jié)構(gòu)最佳。A、順序表B、棧C、隊(duì)列D、鏈表在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)，通常設(shè)置一個(gè)打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個(gè)（B）結(jié)構(gòu)。A、棧B、隊(duì)列C、數(shù)組D、線性表線性表若采用鏈表存儲(chǔ)結(jié)構(gòu)，要求內(nèi)存中可用存儲(chǔ)單元地址( D )A必須連續(xù) B部分地址必須連續(xù) C一定不連續(xù) D連續(xù)不連續(xù)均可依次在初始為空的隊(duì)列中插入元素X，Y，Z，W以后，緊接著作了兩次刪除操作，此時(shí)的隊(duì)頭元素是（ C ）A）X B）Y C）Z D）W已知一個(gè)有向圖如下圖所示，則從頂點(diǎn)a出發(fā)

10、進(jìn)行深度優(yōu)先偏歷，不可能得到的DFS序列為（ A ）。A) a d b e f cB) a d c e f bC) a d c b f eD) a d e f c b若連通無向圖G有n個(gè)頂點(diǎn)，則圖G的生成樹有（ B ）條邊A）n B）n-1 C）n(n-1)/2 D）n/2設(shè)數(shù)組datam作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front值為（ D ）A）front=front+1 B）front=(front+1)%(m-1)C）front=(front-1)%m D）front=(front+1)%m設(shè)某算法的問題規(guī)模函數(shù)f(n)=25

11、n3+5000n2，則它的漸進(jìn)時(shí)間復(fù)雜度為（ A ）。A）O(n3) B）O(n2) C）O(n) D）O(1)假定一個(gè)順序隊(duì)列的隊(duì)首和隊(duì)尾指針分別為f和r，則判斷隊(duì)空的條件為( D )。A）f+1=r B）r+1=f C）f=0 D）f=r線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（ B ）A） 必須是不連續(xù)的B） 連續(xù)與否均可C） 必須是連續(xù)的D） 和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)設(shè)計(jì)遞歸問題的非遞歸算法一般需要用到（ D ）。A）鏈表 B）隊(duì)列 C）樹 D）堆棧對(duì)下面二叉樹，按中序遍歷所得到的結(jié)點(diǎn)序列為（ A ）。A）DBEAFCB）DEBFCAC）BDEACFD）ABCDEF對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無

12、向圖，若采用鄰接表表示，則存放表頭結(jié)點(diǎn)的數(shù)組的大小為（ A ）。A）n B）n+1 C）n-1 D）n+邊數(shù)設(shè)有一個(gè)含有n 個(gè)(n2)關(guān)鍵字的有序表，設(shè)s和h分別是用順序查找法和二分查找法進(jìn)行查找時(shí)的等概率情況下查找成功的平均查找次數(shù)，則s和h的關(guān)系是（ B ）。A）s = h B）s h C）s h D）不能確定一棵深度為7的滿二叉樹有（ D ）葉子結(jié)點(diǎn)。A）7 B）14 C）32 D）64設(shè)二叉樹根結(jié)點(diǎn)的層次為1，含有15個(gè)結(jié)點(diǎn)的二叉樹中的最小高度是（4 ）A） 6B） 5C） 4D） 3在長度為n的順序表的第i（1in+1）個(gè)位置上插入一個(gè)元素，元素的移動(dòng)次數(shù)為（ B ）。A）i-1 B

13、）n-i+1 C）i D）n-i一棵深度為8的滿二叉樹有（ C ）葉子結(jié)點(diǎn)。A）256 B）255 C）128 D）127在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊(A )A只有右子樹上的所有結(jié)點(diǎn) B只有右子樹上的部分結(jié)點(diǎn)C只有左子樹上的所有結(jié)點(diǎn) D只有左子樹上的部分結(jié)點(diǎn)以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述，正確的是( C)A線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)浇Y(jié)構(gòu)B二叉樹的第I層上有2的（I-1）次冪個(gè)結(jié)點(diǎn)，深度為K的二叉樹上有2的（k-1）次冪個(gè)結(jié)點(diǎn)C二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表D棧的操作方式是先進(jìn)先出在單鏈表中，增加頭結(jié)點(diǎn)的目的是為了（ C ）。A使單鏈表至少有一個(gè)結(jié)點(diǎn)B表示表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C方

14、便運(yùn)算的實(shí)現(xiàn)D說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)使用雙向鏈表存放數(shù)據(jù)的優(yōu)點(diǎn)是(A )A提高檢索速度 B很方便地插入和刪除數(shù)據(jù)C節(jié)約存儲(chǔ)空間 D很快回收存儲(chǔ)空間帶頭結(jié)點(diǎn)的單鏈表Head為空的判定條件是(B )AHead=NIL BHead.Next=NIL CHead.Next=Head DHead=Head下列哪一種圖的鄰接矩陣是對(duì)稱矩陣(B )A有向圖 B無向圖 CAOV網(wǎng) DAOE網(wǎng)下列敘述中，正確的是( D)A線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu) B隊(duì)列的操作方式是先進(jìn)后出C棧的操作方式是先進(jìn)先出D二維數(shù)組是指它的每個(gè)數(shù)據(jù)元素為一個(gè)線性表的線性表一維數(shù)組與線性表的區(qū)別是 ( A ) A前者

15、長度固定，后者長度可變 B后者長度固定，前者長度可變C兩者長度均固定 D兩者長度均可變設(shè)有三個(gè)元素A、B、C順序進(jìn)棧，在進(jìn)棧過程中可以出棧，出棧次序錯(cuò)誤的排列是(C )AABC BBCA CCAB DCBA若進(jìn)棧序列為1，2，34假定進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能的出棧序列是( D)A2，4，1，3 B3，1，4，2 C3，4，1，2 D1，2，3，4若已知一個(gè)棧的入棧順序是1，2，3n，其輸出序列為P1,P2，P3Pn，若P1是n，則Pi是（ C）（A） I （B）n-i （C）n-i+1 （D）不確定棧和隊(duì)列都是(C )A順序存儲(chǔ)的線性結(jié)構(gòu) B鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)C限制存取點(diǎn)的線性結(jié)構(gòu) D

16、限制存取點(diǎn)的非線性結(jié)構(gòu)循環(huán)隊(duì)列用數(shù)組A0m-1存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是(A )A（rear-front+m） MOD m Brear-front-1 Crear-front+1 Drear-front設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)的順序是e2、e4、e3、e6、e5、e1，則棧S的容量至少應(yīng)是（B ）A2 B3 C4 D6一個(gè)文本屏幕有25列及80行，屏幕的左上角以（1，1）表示，而右下角則以（80，25）表示，屏幕上每一個(gè)字符占用兩字節(jié)（byt

17、e），整個(gè)屏幕則以線性方式存儲(chǔ)在電腦的存儲(chǔ)器內(nèi)，從屏幕左上角開始，位移為0，然后逐列逐列存儲(chǔ)。求位於屏幕（X，Y）的第一個(gè)字節(jié)的位移是（ ）A.（Y*80+X）*2-1 B.（Y-1）*80+X-1）*2C.（Y*80+X-1）*2 D.（Y-1）*80+X）*2-1對(duì)任何一棵二叉樹T，設(shè)N0、N1、N2分別是度數(shù)為0、1、2的結(jié)點(diǎn)數(shù)，則下列判斷正確的是（ A）AN0N21BN1N01CN2N01DN2N11下面關(guān)于二叉樹的敘述正確的是(A )A一棵二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)等于度為2的結(jié)點(diǎn)個(gè)數(shù)加1B一棵二又樹中的結(jié)點(diǎn)個(gè)數(shù)大于0C二叉樹中任何一個(gè)結(jié)點(diǎn)要么是葉，要么恰有兩個(gè)子女D二叉樹中，任何一個(gè)結(jié)

18、點(diǎn)的左子樹和右子樹上的結(jié)點(diǎn)個(gè)數(shù)一定相等先序序列和中序序列相同的二叉樹為空樹或(C )A任一結(jié)點(diǎn)均無右孩子的非空二叉樹 B僅有兩個(gè)結(jié)點(diǎn)的二叉樹C任一結(jié)點(diǎn)均無左孩子的非空二叉樹 D不存在這樣的二叉樹給出一組整型數(shù)28、10、37、63、35、30、23，請(qǐng)用二叉樹對(duì)它進(jìn)行排序。為此，首先要生成一棵二叉樹，規(guī)則是把第一數(shù)放在根處，接著凡比它小的數(shù)放在左子樹，比它大的數(shù)放在右子樹，直到把所有的數(shù)均安排好。然后對(duì)此二叉樹進(jìn)行( )，得到的就是按照升序排列好的序列。( B)A前序遍歷 B中序遍歷 C后序遍歷 D橫向遍歷下面關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，不正確的敘述是( A)A順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入

19、、刪除運(yùn)算效率高B鏈表中的每一個(gè)結(jié)點(diǎn)都包含一個(gè)指針C包含n個(gè)結(jié)點(diǎn)的二叉排序樹的最大檢索長度為nD將一棵樹轉(zhuǎn)換為二又樹后，根結(jié)點(diǎn)沒有右子樹由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的有序樹(D )A2 B3 C4 D5三、判斷題（本大題共30小題）（ ）折半搜索只適用于有序表，包括有序的順序表和有序的鏈表。（）數(shù)據(jù)的機(jī)內(nèi)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。（ ）程序就是算法，但算法不一定是程序。 （ ）101，88，46，70，34，39，45，58，66，10是堆。（ ）程序就是算法，但算法不一定是程序。（）二叉樹中任何一個(gè)結(jié)點(diǎn)的度都是2。（ ）雙循環(huán)鏈表中任一結(jié)點(diǎn)的前趨指針均指向其邏輯前趨（ ）若從有向圖的某個(gè)頂點(diǎn)

20、出發(fā)進(jìn)行一次深度優(yōu)先搜索可以訪問圖的每個(gè)頂點(diǎn)，則該圖一定是有向完全圖。（ ）強(qiáng)連通圖的各頂點(diǎn)間均可達(dá)。（ ）對(duì)于任意一個(gè)圖，從它的某個(gè)結(jié)點(diǎn)進(jìn)行一次深度或廣度優(yōu)先遍歷可以訪問到該圖的每個(gè)頂點(diǎn)。（）在待排序的記錄集中，存在多個(gè)具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對(duì)次序仍然保持不變，稱這種排序?yàn)榉€(wěn)定排序。（ ）不管堆棧采用何種存儲(chǔ)結(jié)構(gòu)，只要堆棧不空，可以任意刪除一個(gè)元素。（）單鏈表中至多只有一個(gè)結(jié)點(diǎn)的后繼指針為空。（ ）對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列。（）散列法存儲(chǔ)的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址。（）二叉樹為二叉排序樹的充分必要條件是其任一

21、結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。（ ）隊(duì)列是一種插入和刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出的結(jié)構(gòu)。（ ）串是一種特殊的線性表，其特殊性體現(xiàn)在可以順序存儲(chǔ)。（）長度為1的串等價(jià)于一個(gè)字符型常量。（）空串和空白串是相同的。（ ）數(shù)組元素的下標(biāo)值越大，存取時(shí)間越長。（）在平衡二叉樹中，任意結(jié)點(diǎn)左右子樹的高度差（絕對(duì)值）不超過1。（ ）一個(gè)無向圖的鄰接矩陣中各元素之和與圖中邊的條數(shù)相等。（ ）程序就是算法，但算法不一定是程序。（ ）設(shè)S=”cart”，S=”cat”，則S為S的子串。（ ）有n個(gè)結(jié)點(diǎn)的不同的二叉樹有n！棵。（ ）一棵哈夫曼樹中不存在度為1的結(jié)點(diǎn)。（ ）拓?fù)渑?/p>

22、序是按AOE網(wǎng)中每個(gè)結(jié)點(diǎn)事件的最早發(fā)生時(shí)間對(duì)結(jié)點(diǎn)進(jìn)行排序。（ ）冒泡排序算法關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)。（ ）具有n個(gè)結(jié)點(diǎn)的二叉排序樹有多種，其中樹高最小的二叉排序樹是最佳的。四、應(yīng)用題（本大題共10道小題）初始序列的鍵值：（84，85，83，34，98，28，19，76，54，48），采用冒泡排序法進(jìn)行從小到大的排序，請(qǐng)寫出每一趟排序的結(jié)果，并記錄每一趟排序時(shí)交換元素的次數(shù)最后求出該排序過程的總的元素交換次數(shù)。排序過程：初 始： 84，85，83，34，98，28，19，76，54，48交換次數(shù)第1趟： 84，83，34，85，28，19，76，54，48，98 7第2趟： 8

23、3，34，84，28，19，76，54，48，857第3趟： 34，83，28，19，76，54，48，846第4趟： 34，28，19，76，54，48，836第5趟： 28，19，34，54，48，764第6趟： 19，28，34，48, 542第7趟： 19，28，34，480上一趟無交換，排序完成總共交換了2+4+6+6+7+7=32次證明：已知一棵二叉樹的前序序列和中序序列，則可唯一確定該二叉樹。參考答案：證明采用歸納法。設(shè)二叉樹的前序遍歷序列為a1a2a3 an，中序遍歷序列為b1b2b3 bn。當(dāng)n=1時(shí)，前序遍歷序列為a1，中序遍歷序列為b1，二叉樹只有一個(gè)根結(jié)點(diǎn)，所以，a1=

24、 b1，可以唯一確定該二叉樹；假設(shè)當(dāng)n=k時(shí)，前序遍歷序列a1a2a3 ak和中序遍歷序列b1b2b3 bk可唯一確定該二叉樹，下面證明當(dāng)n=k+1時(shí)，前序遍歷序列a1a2a3 akak+1和中序遍歷序列b1b2b3 bk bk+1可唯一確定一棵二叉樹。在前序遍歷序列中第一個(gè)訪問的一定是根結(jié)點(diǎn)，即二叉樹的根結(jié)點(diǎn)是a1，在中序遍歷序列中查找值為a1的結(jié)點(diǎn)，假設(shè)為bi，則a1=bi且b1b2 bi-1是對(duì)根結(jié)點(diǎn)a1的左子樹進(jìn)行中序遍歷的結(jié)果，前序遍歷序列a2a3 ai是對(duì)根結(jié)點(diǎn)a1的左子樹進(jìn)行前序遍歷的結(jié)果，由歸納假設(shè)，前序遍歷序列a2a3 ai和中序遍歷序列b1b2 bi-1唯一確定了根結(jié)點(diǎn)的左

25、子樹，同樣可證前序遍歷序列ai+1ai+2 ak+1和中序遍歷序列bi+1bi+2 bk+1唯一確定了根結(jié)點(diǎn)的右子樹。逐個(gè)結(jié)點(diǎn)插入構(gòu)成平衡二叉樹，插入結(jié)點(diǎn)的數(shù)據(jù)順序?yàn)椋?2,4,1,7,8,10,9,2,11,6,5，在插入過程中平衡樹條件如被破壞，則進(jìn)行必要的調(diào)整，試畫出每插入一個(gè)結(jié)點(diǎn)后平衡樹的情況。參考答案：畫出將下面的樹轉(zhuǎn)化成二叉樹的過程，并寫出構(gòu)造出的二叉樹的先根、中根和后根遍歷序列。參考轉(zhuǎn)換過程：先根：ABCEFGDIJK中根：BFGECIJKDA后根：GFEKJIDCBA設(shè)有升序排列的線性表（2,4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,

26、41），用二分查找法進(jìn)行查找。畫出查找關(guān)鍵字27的過程（3分）第1次：2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41 第2次：2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41 第3次：2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41查找成功。畫出查找關(guān)鍵字11的過程（4分）第1次：2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27,

27、29, 30, 35, 36, 40, 41 第2次：2, 4, 7, 10, 12, 16, 18, 19,20, 24, 27, 29, 30, 35, 36, 40, 41 第3次：2, 4, 7, 10, 12, 16, 18, 19,20, 24, 27, 29, 30, 35, 36, 40, 41第4次：2, 4, 7, 10, 12,16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41第5次：2, 4, 7, 10, 12,16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41無數(shù)據(jù)可比，查找不成功。

28、計(jì)算該表在等概率的情況下查找成功的平均查找次數(shù)為多少？(3分)先畫出該序列對(duì)應(yīng)的二分查找樹：共有17個(gè)值，很明顯總的查找次數(shù) = 1 + 22 + 43 + 84 + 25 = 1+4+12+32+10 = 59ASL = 59/17 = 3.47 假設(shè)以數(shù)組sq0.7存放循環(huán)隊(duì)列元素,變量f指向隊(duì)頭元素的前一位置,變量r指向隊(duì)尾元素，如用A和D分別表示入隊(duì)和出隊(duì)操作，請(qǐng)給出：隊(duì)空的初始條件；答：隊(duì)空的初始條件：f=r=0；執(zhí)行操作序列A3D1A5D2A1D2A4時(shí)的狀態(tài),并作必要的說明。（A3表示三次入隊(duì)操作，D1表示一次出隊(duì)操作）答：執(zhí)行操作A3后，f=0，r=3；/A3表示三次入隊(duì)操作執(zhí)

29、行操作D1后，f=1，r=3；/D1表示一次出隊(duì)操作執(zhí)行操作A5后，f=1，r=0；執(zhí)行操作D2后，f=3，r=0；執(zhí)行操作A1后，f=3，r=1；執(zhí)行操作D2后，f=5，r=1；執(zhí)行操作A4后，按溢出處理。因?yàn)閳?zhí)行A3后，r=4，這時(shí)隊(duì)滿，若再執(zhí)行A操作，則出錯(cuò)。已知A為稀疏矩陣，試從空間和時(shí)間角度比較采用二維數(shù)組和三元組順序表兩種不同的存儲(chǔ)結(jié)構(gòu)完成求和運(yùn)算的優(yōu)缺點(diǎn)。答：設(shè)稀疏矩陣為m行n列，如果采用二維數(shù)組存儲(chǔ)，其空間復(fù)雜度為(mn)；因?yàn)橐獙⑺械木仃囋乩奂悠饋?，所以，需要用一個(gè)兩層的嵌套循環(huán)，其時(shí)間復(fù)雜度亦為(mn)。如果采用三元組順序表進(jìn)行壓縮存儲(chǔ)，假設(shè)矩陣中有t個(gè)非零元素，其空間

30、復(fù)雜度為(t)，將所有的矩陣元素累加起來只需將三元組順序表掃描一遍，其時(shí)間復(fù)雜度亦為(t)。當(dāng)t mn時(shí)，采用三元組順序表存儲(chǔ)可獲得較好的時(shí)、空性能。設(shè)有如下的的散列表，散列函數(shù)為（） mod 13，用線性探測法解決沖突。0123456789101112141682751920842311寫出查找19的計(jì)算過程根據(jù)散列函數(shù)，可得H(19) = 19 mod 13 = 6，而地址6存儲(chǔ)的元素正好為6，所以只需要比較一次，即可得到查找19的結(jié)果。 寫出查找27的比較次數(shù)（要求寫出計(jì)算和分析過程）根據(jù)散列函數(shù)，可得H(27) = 27 mod 13 = 1，而地址1存儲(chǔ)的元素非27，即出現(xiàn)查找沖突。

31、已知采用線性探測法進(jìn)行沖突解決，所以按線性遞增的方式查找地址2，而地址2非空且也不等于27，再線性增長地址跟地址3比較，也非27，再線性增長地址跟地址4比較，查找成功。所以查找27需要比較4次。計(jì)算等概率情況下查找成功的ASL。根據(jù)散列函數(shù)及沖突解決方法可計(jì)算出各元素的哈希值和查找次數(shù)：H(14) = 14 mod 13 = 1, 比較1次H（1）= 1 mod 13 = 1，比較2次H（68）= 68 mod 13 = 3，比較1次H（27）= 27 mod 13 = 1，比較4次H（5）= 5 mod 13 = 5，比較1次H（19）= 19 mod 13 = 6，比較1次H（20）= 2

32、0 mod 13 = 7，比較1次H（84）= 84 mod 13 = 6，比較3次H（23）= 23 mod 13 = 10，比較1次H（11）= 11 mod 13 = 11，比較1次故可得這10個(gè)元素查找成功總的比較次數(shù)為1+2+1+4+1+1+1+3+1+1 = 16次所以查找成功的ASL = 16/10 = 1.6等概率情況下查找不成功的ASL。查找不成功必須是比較到空元素，根據(jù)沖突解決方法可知這13個(gè)存儲(chǔ)單元查找不成功的比較次數(shù)：A0為空，所以只需比較 1次A1非空，按線性探測方法要比較到A9，即9次比較以此類推A2比較8次A3比較7次A4比較6次A5比較5次A6比較4次A7比較3

33、次A8比較2次A9比較1次A10比較3次A11比較2次A12比較1次可得查找不成功總的比較次數(shù)為1+9+8+7+6+5+4+3+2+1+3+2+1 = 52次所以查找不成功的ASL = 52/13 = 4對(duì)于如下圖所示的的無向網(wǎng)絡(luò)：畫出表示此網(wǎng)絡(luò)的鄰接矩陣。畫出表示此網(wǎng)絡(luò)的鄰接表畫出用普里姆算法構(gòu)造其最小生成樹的過程。試比較線性表的兩種存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn),在什么情況下用順序表比鏈表好? 順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲(chǔ)密度大，存儲(chǔ)空間利用率高。缺點(diǎn)：插入或刪除元素時(shí)不方便。鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存

34、儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度?。?），存儲(chǔ)空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入.刪除這樣的動(dòng)態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入.刪除操作，則采用鏈表。五、算法編寫（本大題共6小題）試寫出二分查找的遞歸算法int BinSearch(Seqlist R,int low,int high,KeyType k)。 int BinSearch(Seglist R,int low,int high,keyType

35、k) int mid; if(low=high) 保證在lowk) return Binsearch(R,low,mid1,k); 如果中間元素關(guān)鍵字值大于k， 在low和mid-1之間繼續(xù)尋找 else return BinSearch(R,mid+1,high,k); 如果中間元素關(guān)鍵字值小于k， 在mid+1和high之間繼續(xù)尋找 return(1); 返回1表示沒有找到 以下為帶空頭結(jié)點(diǎn)的循環(huán)鏈?zhǔn)疥?duì)列邏輯結(jié)構(gòu)，請(qǐng)寫出隊(duì)列的入隊(duì)和出隊(duì)算法。參考算法：/ 結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)Struct node DATATYPE data; Struct node *next; ;/ 入隊(duì)算法void InQu

36、eue(struct node *rear, DATATYPE x) struct node *p;p = (struct node *)malloc(sizeof(struct node); p-data = x; if (rear-next = rear) p-next = rear; real-next = p; Elsep-next = rear-next-next;rear-next-next = p; ;/ 出隊(duì)算法DATATYPE OutQueue(struct node *rear) struct node *p, *q; DATATYPE rlt; if (rear-next

37、 = rear) Error(“隊(duì)列已空,不能出隊(duì)!”); Elsep = rear;while(p-next !=rear)p = p-next;p-next = rear-next;q=rear;rear = p;rlt = q-data;free(q);return rlt; ;編寫在以BST為樹根指針的二叉搜索樹上進(jìn)行查找值為item的結(jié)點(diǎn)的非遞歸算法，若查找成功則由item帶回整個(gè)結(jié)點(diǎn)的值并返回true，否則返回false。bool Find( BTreeNode * BST , ElemType & item ) while ( BST != NULL ) if ( item = BT-data ) item = BST-data;return true; else if (itemdata) BST=BST-left;else BST=BST-right; return false;以下為帶空頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列，請(qǐng)寫出該隊(duì)列的入隊(duì)和出隊(duì)算法。參考算法：/* 設(shè)數(shù)據(jù)元素的類型為DataType */struct node DataType data; /* 存儲(chǔ)元素 */ struct node *next; ;/*/* 入隊(duì) */*