數(shù)據(jù)結(jié)構(gòu)與算法c++版測(cè)試題

更多企業(yè)學(xué)院：./Shop/中小企業(yè)管理全能版183套講座+89700份資料./Shop/40.shtml總經(jīng)理、高層管理49套講座+16388份資料./Shop/38.shtml中層管理學(xué)院46套講座+6020份資料./Shop/39.shtml國(guó)學(xué)智慧、易經(jīng)46套講座./Shop/41.shtml人力資源學(xué)院56套講座+27123份資料./Shop/44.shtml各階段員工培訓(xùn)學(xué)院77套講座+ 324份資料./Shop/49.shtml員工管理企業(yè)學(xué)院67套講座+ 8720份資料./Shop/42.shtml工廠生產(chǎn)管理學(xué)院52套講座+ 13920份資料./Shop/43.shtml財(cái)務(wù)管理學(xué)院53套講座+ 17945份資料./Shop/45.shtml銷售經(jīng)理學(xué)院56套講座+ 14350份資料./Shop/46.shtml銷售人員培訓(xùn)學(xué)院72套講座+ 4879份資料./Shop/47.shtml模擬試題（一）一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？（）A）有向圖 B）隊(duì)列 C）線索二叉樹(shù) D）B樹(shù)（2）在一個(gè)單鏈表la中，若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由q指向的結(jié)點(diǎn)，則執(zhí)行如下（）語(yǔ)句序列。A）p=q; p-next=q; B）p-next=q; q-next=p;C）p-next=q-next; p=q; D）q-next=p-next; p-next=q;（3）（）不是隊(duì)列的基本運(yùn)算。A）在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B）從隊(duì)頭刪除一個(gè)元素C）判斷一個(gè)隊(duì)列是否為空 D）讀取隊(duì)頭元素的值（4）字符A、B、C依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成（）個(gè)不同的字符串。A）14 B）5 C）6 D）8（5）由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（）。A）11 B）35 C）19 D）53以下6-8題基于下圖：（6）該二叉樹(shù)結(jié)點(diǎn)的前序遍歷的序列為（）。A）E、G、F、A、C、D、B B）E、A、G、C、F、B、DC）E、A、C、B、D、G、F D）E、G、A、C、D、F、B（7）該二叉樹(shù)結(jié)點(diǎn)的中序遍歷的序列為（）。A）A、B、C、D、E、G、FB）E、A、G、C、F、B、DC）E、A、C、B、D、G、F D）B、D、C、A、F、G、E （8）該二叉樹(shù)的按層遍歷的序列為（）。A）E、G、F、A、C、D、B B）E、A、C、B、D、G、FC）E、A、G、C、F、B、D D）E、G、A、C、D、F、B（9）下面關(guān)于圖的存儲(chǔ)的敘述中正確的是（）。A）用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)B）用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中邊數(shù)和結(jié)點(diǎn)個(gè)數(shù)都有關(guān)C）用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)都有關(guān)D）用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)（10）設(shè)有關(guān)鍵碼序列(q,g,m,z,a,n,p,x,h)，下面哪一個(gè)序列是從上述序列出發(fā)建堆的結(jié)果?（）A）a,g,h,m,n,p,q,x,z B）a,g,m,h,q,n,p,x,z C）g,m,q,a,n,p,x,h,z D）h,g,m,p,a,n,q,x,z二、（每小題4分，共8分）已知一個(gè)65稀疏矩陣如下所示，試：（1）寫(xiě)出它的三元組線性表；（2）給出三元組線性表的順序存儲(chǔ)表示。三、（本題8分）求網(wǎng)的最小生成樹(shù)有哪些算法？它們的時(shí)間復(fù)雜度分別下多少，各適用何種情況？四、（每小題4分，共8分）對(duì)于如下圖所示的有向圖若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，試寫(xiě)出：（1）從頂點(diǎn)v1出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹(shù)；（2）從頂點(diǎn)v2出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹(shù)。 五、（本題8分）已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：V=1,2,3,4,5,6,7;E=,;試畫(huà)出此圖的圖形，給出所有可能的拓?fù)渑判蛐蛄?。六、（本題8分）對(duì)于序列8,18,6,16,29,28，試寫(xiě)出堆頂元素最小的初始堆。七、（本題8分）一棵二叉樹(shù)的先序、中序和后序序列分別如下，其中有一部分未顯示出來(lái)。試求出空格處的內(nèi)容，并畫(huà)出該二叉樹(shù)。先序序列： B F ICEH G中序序列：D KFIA EJC 后序序列： K FBHJ G A八、（每小題2分，共8分）設(shè)有序列：w=23,24,27,80,28，試給出：（1）二叉排序樹(shù)；（2）哈夫曼樹(shù)；（3）平衡二叉樹(shù)；（4）對(duì)于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果。九、（本題9分）有關(guān)鍵字序列7,23,6,9,17,19,21,22,5，Hash函數(shù)為H(key)=key % 5，采用鏈地址法處理沖突，試構(gòu)造哈希表。十、（本題15分）假設(shè)二叉樹(shù)中每個(gè)結(jié)點(diǎn)所含數(shù)據(jù)元素均為單字母，以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，試編寫(xiě)算法按如下圖所示的樹(shù)狀顯示二叉樹(shù)。模擬試題（一）參考答案一、單項(xiàng)選擇題（1）B （2）D （3）A （4）B（5）B（6）C（7）A（8）C（9）B（10）B二、（每小題4分，共8分）（1） (1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)（2）三元組線性表的順序存儲(chǔ)表示如下所示：三、（本題8分）求網(wǎng)的最小生成樹(shù)可使用Prim算法，時(shí)間復(fù)雜度為O(n2)，此算法適用于邊較多的稠密圖，也可使用Kruskal算法，時(shí)間復(fù)雜度為O(eloge)，此算法適用于邊較少的稀疏圖。四、（每小題4分，共8分）（1）DFS：v1 v2 v3 v4 v5 （2）BFS：v2 v3 v4 v5 v1 五、（本題8分）圖形表示如下圖所示：拓?fù)渑判驗(yàn)椋?，六、（本題8分）所構(gòu)造的堆如下圖所示：七、（本題8分）在先序序列空格中依次填A(yù)DKJ，中序中依次填BHG，后序中依次填DIEC。二叉樹(shù)如下：八、（每小題2分，共8分）（1）二叉排序樹(shù)如下圖所示：（2）哈夫曼樹(shù)如下圖所示：（3）平衡二叉樹(shù)如下圖所示：（4）對(duì)于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果：28,80,27,24,23九、（本題9分）哈希表如下圖所示：十、（本題15分）從上圖來(lái)看，二叉樹(shù)的第一層顯示在第一列，第二層顯示在第二列，第三層顯示在第三列；每行顯示一個(gè)結(jié)點(diǎn)，從上至下是先顯示右子樹(shù)，再顯示根，最后最左子樹(shù)，也就是以先遍歷右子樹(shù)，最后遍歷左子樹(shù)的中序遍歷次序顯示各結(jié)點(diǎn)。具體算法實(shí)現(xiàn)如下：/ 文件路徑名:exam1alg.h template void DisplayHelp(BinTreeNode *r, int level)/ 操作結(jié)果：按樹(shù)狀形式顯示以r為根的二叉樹(shù)，level為層次數(shù)，可設(shè)根結(jié)點(diǎn)的層次數(shù)為1if(r != NULL)/ 空樹(shù)不顯式，只顯式非空樹(shù)DisplayHelp(r-rightChild, level + 1);/ 顯示右子樹(shù)cout endl;/ 顯示新行for(int i = 0; i level - 1; i+)cout ;/ 確保在第level列顯示結(jié)點(diǎn)cout data;/ 顯示結(jié)點(diǎn)DisplayHelp(r-leftChild, level + 1);/ 顯示左子樹(shù)template void Display(const BinaryTree &bt)/ 操作結(jié)果：樹(shù)狀形式顯示二叉樹(shù) DisplayHelp(bt.GetRoot(), 1);/ 樹(shù)狀顯示以bt.GetRoot()為根的二叉樹(shù)cout =2)個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹(shù)，關(guān)于該樹(shù)的敘述中，錯(cuò)誤的是（ ）A）該樹(shù)一定是一棵完全二叉樹(shù)B）樹(shù)中一定沒(méi)有度為1的結(jié)點(diǎn)C）樹(shù)中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn) D）樹(shù)中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一任一結(jié)點(diǎn)的權(quán)值（5）下列關(guān)于二叉樹(shù)遍歷的敘述中，正確的是（）。A）若一個(gè)葉子是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的前序遍歷最后一個(gè)結(jié)點(diǎn)B）若一個(gè)結(jié)點(diǎn)是某二叉樹(shù)的前序遍歷最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)C）若一個(gè)結(jié)點(diǎn)是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn)D）若一個(gè)樹(shù)葉是某二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的中序遍歷最后一個(gè)結(jié)點(diǎn)（6）k層二叉樹(shù)的結(jié)點(diǎn)總數(shù)最多為（）。A）2k-1 B）2k+1 C）2k-1 D）2k-1（7）對(duì)線性表進(jìn)行二分法查找，其前提條件是（）。A）線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序 B）線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序C）線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序D）線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序（8）對(duì)n個(gè)記錄進(jìn)行堆排序，所需要的輔助存儲(chǔ)空間為（）。A）O(1og2n) B）O(n) C）O(1) D）O(n2)（9）對(duì)于線性表（7，34，77，25，64，49，20，14）進(jìn)行散列存儲(chǔ)時(shí)，采用鏈地址法處理沖突，若選用H(K) = K % 7作為散列函數(shù)，則散列地址為0的元素有（）個(gè)。A）1 B）2 C）3 D）4（10）下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是（）。A）數(shù)組是不同類型值的集合 B）遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉C）樹(shù)是一種線性結(jié)構(gòu)D）用一維數(shù)組存儲(chǔ)一棵完全二叉樹(shù)是有效的存儲(chǔ)方法二、（本題8分）假定一棵二叉樹(shù)廣義表表示為a(b(c),d(e,f)，分別寫(xiě)出對(duì)它進(jìn)行先序、中序、后序、按層遍歷的結(jié)果。三、（每小題4分，共8分）已知一個(gè)無(wú)向圖的頂點(diǎn)集為a, b, c, d, e，其鄰接矩陣如下所示： （1）畫(huà)出該圖的圖形；（2）根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫(xiě)出相應(yīng)的遍歷序列。四、（本題8分）樹(shù)有哪些遍歷方法？它們分別對(duì)應(yīng)于把樹(shù)轉(zhuǎn)變?yōu)槎鏄?shù)的哪些遍歷方法？五、（本題8分）如下圖所示，設(shè)輸入元素為1、2、3、P和A，輸入次序?yàn)?23PA，元素經(jīng)過(guò)棧后到達(dá)輸出序列，當(dāng)所有元素均到達(dá)輸出序列后，有哪些序列可以作為高級(jí)語(yǔ)言的變量名？ 六、（本題8分）試列出如下圖中全部可能的拓?fù)渑判蛐蛄?。七、（本題8分）已知哈希表地址空間為0.8，哈希函數(shù)為H(key)=key%7，采用線性探測(cè)再散列處理沖突，將數(shù)據(jù)序列100,20,21,35,3,78,99,45依次存入此哈希表中，列出插入時(shí)的比較次數(shù)，并求出在等概率下的平均查找長(zhǎng)度。八、（本題8分）設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 , 試畫(huà)出從空樹(shù)起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹(shù)。九、（本題9分）試畫(huà)出表達(dá)式(a+b/c)*(d-e*f)的二叉樹(shù)表示，并寫(xiě)出此表達(dá)式的波蘭式表示，中綴表示及逆波蘭式表示。十、（本題15分）以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，試編寫(xiě)計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)數(shù)目的遞歸算法。模擬試題（二）參考答案一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）B（2）D（3）A（4）A（5）A （6）A （7）C （8）C （9）D （10）D二、（本題8分）先序： a,b,c,d,e,f 中序： c,b,a,e,d,f 后序： c,b,e,f,d,a 按層： a,b,d,c,e,f 三、（每小題4分，共8分）【解答】（1）該圖的圖形如下圖所示：（2）深度優(yōu)先遍歷序列為：abdce；廣度優(yōu)先遍歷序列為：abedc。四、（本題8分）樹(shù)的遍歷方法有先根序遍歷和后根序遍歷，它們分別對(duì)應(yīng)于把樹(shù)轉(zhuǎn)變?yōu)槎鏄?shù)后的先序遍歷與中序遍歷方法。五、（本題8分）高級(jí)語(yǔ)言變量名是以字母開(kāi)頭，字母與數(shù)字的組合。由于必須以字母開(kāi)頭，有兩種可能：（1）P為第一個(gè)輸出字符的情形，那么必然要求123已經(jīng)先后入棧，這樣可得到以P開(kāi)頭的、并且123按逆序排列的（即321）、同時(shí)A位于P后任一位置的變量名序列：PA321，P3A21，P32A1，P32lA（2）A為第一個(gè)輸出字符的情形，這時(shí)要求123P已經(jīng)先后入棧，只有一種情形：AP321 六、（本題8分）全部可能的拓?fù)渑判蛐蛄袨椋?、七、（本題8分）哈希表及查找各關(guān)鍵字要比較的次數(shù)如下圖所示：ASL=(41+12+14+25)=2.5八、（本題8分）九、（本題9分）表達(dá)式的波蘭式表示，中綴表示及逆波蘭式表示分別是此表達(dá)式的二叉樹(shù)表示的前序遍歷、中序遍歷及后序遍歷序列。二叉樹(shù)表示如下圖所示：波蘭式表示：*+a/bc-d*ef中綴表示：a+b/c*d-e*f逆波蘭式表示：abc/+def*-*十、（本題15分）本題只要在遍歷二叉樹(shù)的過(guò)程序中對(duì)葉子結(jié)點(diǎn)進(jìn)行記數(shù)即可。具體算法實(shí)現(xiàn)如下：/ 文件路徑名:exam2alg.h template long LeafCountHelp(BinTreeNode *r)/ 操作結(jié)果：按樹(shù)狀形式顯示二叉樹(shù)，level為層次數(shù)，可設(shè)根結(jié)點(diǎn)的層次數(shù)為1if (r = NULL)/ 空二叉樹(shù)return 0;/ 空樹(shù)返回0else if (r-leftChild = NULL & r-rightChild = NULL)/ 只有一個(gè)結(jié)點(diǎn)的樹(shù)return 1;/ 只有一個(gè)結(jié)點(diǎn)的樹(shù)返回1else/ 其他情況, 葉子結(jié)點(diǎn)數(shù)為左右子樹(shù)的葉子結(jié)點(diǎn)數(shù)之和return LeafCountHelp(r-leftChild) + LeafCountHelp(r-rightChild);template long LeafCount(const BinaryTree &bt)/ 操作結(jié)果：計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)數(shù)目return LeafCountHelp(bt.GetRoot();/ 調(diào)用輔助函數(shù)實(shí)現(xiàn)計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)數(shù)目模擬試題（三）一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（）方面的內(nèi)容。A）健壯性和可讀性 B）并行性 C）正確性 D）時(shí)空復(fù)雜度（2）在帶有頭結(jié)點(diǎn)的單鏈表la中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行（）。A）p-next=la-next; la-next=p B）p-next=la; la=pC）p-next=la; p=la D）la=p; p-next=la（3）對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（）A）經(jīng)常需要隨機(jī)地存取元素 B）經(jīng)常需要進(jìn)行插入和刪除操作C）表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D）表中元素的個(gè)數(shù)不變（4）一個(gè)棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是（）。A）2 3 1B）3 2 1C）3 1 2 D）1 2 3（5）每一趟都能選出一個(gè)元素放在其最終位置上，并且不穩(wěn)定的排序算法是（）。A）冒泡排序B）簡(jiǎn)單選擇排序C）希爾排序D）直接插入排序（6）采用開(kāi)放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度（）。A）低于鏈接法處理沖突 B）高于鏈接法處理沖突C）與鏈接法處理沖突相同 D）高于二分查找（7）若無(wú)向圖G中含8個(gè)頂點(diǎn)，則保證圖G在任何情況下都是連通的，則需要的邊數(shù)最少是（ ）A）6 B）7 C）16 D）21（8）設(shè)棧最大長(zhǎng)度為3，入棧序列為1、2、3、4、5、6，則不可能的出棧序列是（）。A）1、2、3、4、5、6B）2、1、3、4、5、6C）3、4、2、1、5、6D）4、3、2、1、5、6（9）快速排序在最壞情況下的時(shí)間復(fù)雜度為（）。A）O(log2n) B）O(nlog2n) C）O(n) D）O(n2)（10）從二叉搜索樹(shù)中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為（）。A）O(n) B）O(1) C）O(log2n) D）O(n2)二、（本題8分）已知一個(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;試畫(huà)出些圖的圖形，用克魯斯卡爾算法得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。三、（本題8分）請(qǐng)畫(huà)出如下圖所示的鄰接矩陣和鄰接表。四、（每小題4分，共8分）設(shè)有如下圖所示的AOE網(wǎng)（其中vi（i=l，2，6）表示事件，邊上表示活動(dòng)的天數(shù)）。（1）找出所有的關(guān)鍵路徑。（2）v3事件的最早開(kāi)始時(shí)間是多少。五、（本題8分）請(qǐng)回答下列關(guān)于圖（Graph）的一些問(wèn)題： （1）有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多有多少條邊？最少有多少條邊？（2）表示一個(gè)有1000個(gè)頂點(diǎn)、1000條邊的有向圖的鄰接矩陣有多少個(gè)矩陣元素？是否是稀疏矩陣？六、（本題8分）假設(shè)把n個(gè)元素的序列（a1,a2,an）滿足條件akaj(ij)，試問(wèn)，當(dāng)ai與aj相互交換后，該序列中逆序元素的個(gè)數(shù)一定不會(huì)增加，這句話對(duì)不對(duì)？如果對(duì)，請(qǐng)說(shuō)明為什么？如果不對(duì)，請(qǐng)舉一例說(shuō)明。七、（每小題4分，共8分）對(duì)于一個(gè)有向圖，不用拓?fù)渑判颍绾闻袛鄨D中是否存在環(huán)？八、（本題8分）已知一組關(guān)鍵字為（19,14,23,1,68,20,84,27,55,11,10,79），哈希函數(shù)：H(key)=key MOD 13，哈希地址空間為012，請(qǐng)構(gòu)造用鏈地址法處理沖突的哈希表，并求平均查找長(zhǎng)度。九、（本題9分）已知關(guān)鍵字序列23，13，5，28，14，25，試構(gòu)造二叉排序樹(shù)。十、（本題15分）編寫(xiě)一個(gè)算法求二又樹(shù)的深度。模擬試題（三）參考答案一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）B （2）A （3）B （4）C （5）B （6）B （7）B （8）D （9）D （10）C二、（本題8分）圖的圖形形示如下：用克魯斯卡爾算法得到的最小生成樹(shù)為： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20三、（本題8分）鄰接矩陣：鄰接表如下圖所示：四、（每小題4分，共8分）（1）找出所有的關(guān)鍵路徑有：v1v2v3v5v6，以及v1v4v6。（2）v3事件的最早開(kāi)始時(shí)間是13。五、（本題8分）（1）如n個(gè)頂點(diǎn)依次首尾相接構(gòu)成一個(gè)環(huán)，共有n個(gè)條邊，有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最少有n條邊，每?jī)蓚€(gè)頂點(diǎn)之間可以有兩條有向邊，所以最多有n（nl）條邊。（2）表示一個(gè)有1000個(gè)頂點(diǎn)、1000條邊的有向圖的鄰接矩陣有10002個(gè)矩陣元素，而其中非零元素只有1000個(gè)，所以根據(jù)稀疏矩陣的定義應(yīng)為稀疏矩陣。六、（本題8分）不對(duì)，例如序列3、3、4、2、l的“逆序元素”個(gè)數(shù)是2，2和1是“逆序元素”；但是將第二個(gè)3和2交換后，成為3、2、4、3、l，此時(shí)“逆序元素”個(gè)數(shù)是3，2、3和1是“逆序元素”。七、（每小題4分，共8分）除了拓?fù)渑判蛩惴?，也可用深度?yōu)先遍歷方法判斷一個(gè)有向圖是否存在環(huán)。對(duì)于有向圖進(jìn)行深度優(yōu)先遍歷，如果從有向圖上某個(gè)頂點(diǎn)v出發(fā)的遍歷，在DFS(G,v)結(jié)束之前出現(xiàn)一條從頂點(diǎn)u到頂點(diǎn)v的回邊，由于u在生成樹(shù)上是v的子孫，則有向圖中必定存在包含頂點(diǎn)u和頂點(diǎn)v的環(huán)。八、（本題8分）用鏈地址法處理沖突的哈希表如下圖所示：ASL=(1*6+2*4+3*1+4*1)=1.75九、（本題9分）構(gòu)造二叉排序樹(shù)的過(guò)程如下圖所示。構(gòu)造的二叉排序樹(shù)如下圖所示：十、（本題15分）若二叉樹(shù)為空，深度為0；若二叉樹(shù)不空，則二叉樹(shù)的深度為左右子樹(shù)深度的最大值加1。本題最簡(jiǎn)單算法是遞歸算法。具體算法實(shí)現(xiàn)如下：/ 文件路徑名:exam3alg.h template int DepthHelp(BinTreeNode *r)/ 操作結(jié)果：求二叉樹(shù)的深度if (r = NULL)/ 空二叉樹(shù)return 0;/ 空二叉樹(shù)的深度為0else/ 非空二叉樹(shù)int lDepth = DepthHelp(r-leftChild);/ 左子樹(shù)的深度int rDepth = DepthHelp(r-rightChild);/ 右子樹(shù)的深度return (lDepth rDepth) ? lDepth : rDepth) + 1;/ 返回左右子樹(shù)的深度最大值加1template int Depth(BinaryTree &bt)/ 操作結(jié)果：求二叉樹(shù)的深度return DepthHelp(bt.GetRoot();/ 調(diào)用輔助函數(shù)求二叉樹(shù)的深度模擬試題（四）一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？（）A）有向圖 B）棧 C）二叉樹(shù) D）B樹(shù)（2）若某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采用（）存儲(chǔ)方式最節(jié)省時(shí)間。A）單鏈表B）帶頭結(jié)點(diǎn)的非循環(huán)雙鏈表C）帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D）單循環(huán)鏈表（3）（）不是隊(duì)列的基本運(yùn)算。A）在隊(duì)列第i個(gè)元素之后插入一個(gè)元素 B）從隊(duì)頭刪除一個(gè)元素C）判斷一個(gè)隊(duì)列是否為空 D）讀取隊(duì)頭元素的值（4）字符A、B、C、D依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成（）個(gè)不同的字符串？A）15 B）14 C）16 D）21（5）由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（）。A）11 B）37 C）19 D）53以下6-8題基于下面的敘述：若某二叉樹(shù)結(jié)點(diǎn)的中序遍歷的序列為A、B、C、D、E、F、G，后序遍歷的序列為B、D、C、A、F、G、E。（6）則該二叉樹(shù)結(jié)點(diǎn)的前序遍歷的序列為（）。A）E、G、F、A、C、D、BB）E、A、G、C、F、B、DC）E、A、C、B、D、G、F D）E、G、A、C、D、F、B（7）該二叉樹(shù)有（）個(gè)葉子。A）3 B）2 C）5 D）4（8）該二叉樹(shù)的按層遍歷的序列為（）。A）E、G、F、A、C、D、B B）E、A、C、B、D、G、FC）E、A、G、C、F、B、D D）E、G、A、C、D、F、B（9）下面的二叉樹(shù)中，（）不是完全二叉樹(shù)。（10）設(shè)有關(guān)鍵碼序列(q,g,m,z,a)，（）序列是從上述序列出發(fā)建的小根堆的結(jié)果。A）a,g ,m,q,zB）a,g,m,z,qC）g,m,q,a,zD）g, m, a,q,z二、（本題8分）試述順序查找法和折半查找法對(duì)被查找的表中元素的要求，對(duì)長(zhǎng)度為n的查找表來(lái)說(shuō)，這兩查找法在查找算法的時(shí)間復(fù)雜度是多少？三、（本題8分）設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 ，試畫(huà)出從空樹(shù)起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉排序樹(shù)。四、（本題8分）給定一個(gè)關(guān)鍵字序列24，19，32，43，38，6，13，22，請(qǐng)寫(xiě)出快速排序第一趟的結(jié)果；堆排序時(shí)所建的初始堆；然后回答在最壞情況下哪種方法的時(shí)間復(fù)雜度最差？五、（本題8分）帶權(quán)圖（權(quán)值非負(fù)，表示邊連接的兩頂點(diǎn)間的距離）的最短路徑問(wèn)題是找出從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑。假定從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑，現(xiàn)有一種解決該問(wèn)題的方法： 設(shè)最短路徑初始時(shí)僅包含初始頂點(diǎn)，令當(dāng)前頂點(diǎn)u為初始頂點(diǎn)； 選擇離u最近且尚未在最短路徑中的一個(gè)頂點(diǎn)v，加入到最短路徑中，修改當(dāng)前頂點(diǎn)u=v； 重復(fù)步驟，直到u是目標(biāo)頂點(diǎn)時(shí)為止。 請(qǐng)問(wèn)上述方法能否求得最短路徑？若該方法可行，請(qǐng)證明之；否則，請(qǐng)舉例說(shuō)明。六、（本題8分）用一維數(shù)組存放的一棵完全二叉樹(shù)：ABCDEFGHIJKL。請(qǐng)寫(xiě)出后序遍歷該二叉樹(shù)的訪問(wèn)結(jié)點(diǎn)序列。七、（本題8分）請(qǐng)說(shuō)明對(duì)一棵二叉樹(shù)進(jìn)行前序、中序和后序遍歷，其葉結(jié)點(diǎn)的相對(duì)次序是否會(huì)發(fā)生改變？為什么？八、（本題8分）對(duì)于如下圖所示的G，用Kruskal算法構(gòu)造最小生成樹(shù)，要求圖示出每一步的變化情況。九、（本題9分）已知一棵二叉樹(shù)的先序序列與中序序列分別如下，試畫(huà)出此二叉樹(shù)。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI十、（本題15分）試寫(xiě)一遞歸算法，從大到小輸出二叉排序樹(shù)中所有的關(guān)鍵字值小于key的元素值。模擬試題（四）參考答案一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）B （2）C （3）A （4）B （5）B （6）C （7）A （8）C （9）C （10）B二、（本題8分）兩種方法對(duì)查找的要求分別如下：順序查找法：表中元素可以任意存放；折半查找法：表中元素必須以關(guān)鍵字的大小遞增或遞減的次序存放：兩種方法的時(shí)間復(fù)雜度如下：順序查找法：時(shí)間復(fù)雜度為O(n)；折半查找法：時(shí)間復(fù)雜度O(log2n)；三、（本題8分）如下圖所示：四、（本題8分）快速排序的第一趟結(jié)果為22,19,13,6,24,38,43,12；堆排序時(shí)所建立的初始大頂堆如所圖所示：在最壞情況下兩種排序方法所需時(shí)間：堆是O(nlogn)，快速排序是O(n2)，所以，可見(jiàn)在最壞情況下快速排序時(shí)間復(fù)雜度最差。注意：快速排序的平均時(shí)排序速度最快，但在最壞情況下不一定比其他排序方法快。五、（本題8分）該方法求得的路徑不一定是最短路徑。例如，對(duì)于下圖所示的帶權(quán)圖，如果按照題中的原則，從A到C的最短路徑為ABC，事實(shí)上其最短路徑為 ADC。六、（本題8分）先畫(huà)出該二叉樹(shù)的樹(shù)形結(jié)構(gòu)。對(duì)其進(jìn)行后序遍歷得到后序序列為：HIDJKEBLFGCA。七、（本題8分）二叉樹(shù)任兩個(gè)中葉結(jié)點(diǎn)必在某結(jié)點(diǎn)的左/右子樹(shù)中，三種遍歷方法對(duì)左右子樹(shù)的遍歷都是按左子樹(shù)在前、右子樹(shù)在后的順序進(jìn)行遍歷的。所以在三種遍歷序列中葉結(jié)點(diǎn)的相對(duì)次序是不會(huì)發(fā)生改變的。八、（本題8分）用Kruskal算法構(gòu)造最小生成樹(shù)的過(guò)程如下圖所示：九、（本題9分）先由先序序列的第一個(gè)結(jié)點(diǎn)確定二叉樹(shù)的根結(jié)點(diǎn)，再由根結(jié)點(diǎn)在中序序列中左側(cè)部分為左子樹(shù)結(jié)點(diǎn)，在右側(cè)部分為右子樹(shù)結(jié)點(diǎn)，再由先序序列的第一個(gè)結(jié)點(diǎn)確定根結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)，由類似的方法可確定其他結(jié)點(diǎn)，如下圖所示。十、（本題15分）可按先遍歷右子樹(shù)，遍歷根結(jié)點(diǎn)，再遍歷左子樹(shù)進(jìn)行中序遍歷，這樣可實(shí)現(xiàn)由大到小遍歷一棵二叉排序樹(shù)。具體算法實(shí)現(xiàn)如下：/ 文件路徑名:exam4alg.h template void InOrderHelp(BinTreeNode *r, const KeyType &key)/ 操作結(jié)果: 從大到小輸出以r為根的二叉排序樹(shù)中所有的關(guān)鍵字值小于key的元素值if (r != NULL)/ 非空二叉排序樹(shù)InOrderHelp(r-rightChild, key);/ 遍歷右子樹(shù)if(r-data key) cout data leftChild, key);/ 遍歷左子樹(shù)template void InOrder(const BinarySortTree &t, const KeyType &key)/ 操作結(jié)果: 從大到小輸出二叉排序樹(shù)中所有的關(guān)鍵字值不小于key的元素值InOrderHelp(t.GetRoot(), key);/ 調(diào)用輔助函數(shù)實(shí)現(xiàn)從大到小輸出二叉排序樹(shù)中所有的關(guān)鍵字值不小于key的元素值模擬試題（五）一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）隊(duì)列的特點(diǎn)是（）。A）先進(jìn)后出B）先進(jìn)先出C）任意位置進(jìn)出D）前面都不正確（2）有n個(gè)記錄的文件，如關(guān)鍵字位數(shù)為d，基數(shù)為r，則基數(shù)排序共要進(jìn)行（）遍分配與收集。A）nB）dC）rD）n - d （3）在二叉樹(shù)結(jié)點(diǎn)的先序序列、中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（）。A）都不相同B）完全相同C）先序和中序相同，而與后序不同D）中序和后序相同，而與先序不同（4）限定在一端加入和刪除元素的線性表稱為（）。A）雙向鏈表B）單向鏈表C）棧D）隊(duì)列（5）快速排序執(zhí)行一遍之后，已經(jīng)到位的元素個(gè)數(shù)是（）。A）1B）3C）D）（6）設(shè)森林F對(duì)應(yīng)的二叉樹(shù)為B，它有m個(gè)結(jié)點(diǎn)，B的根為p，p的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)為n，森林F中第一棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)是（）。A）m-n-1B）n+1C）m-n+1D）m-n（7）設(shè)有198個(gè)初始?xì)w并段，如采用K-路平衡歸并三遍完成排序，則K值最大為（）。A）12B）13C）14D）15（8）下面關(guān)于廣義表的敘述中，不正確的是（）。A）廣義表可以是一個(gè)多層次的結(jié)構(gòu)B）廣義表至少有一個(gè)元素C）廣義表可以被其他廣義表所共享D）廣義表可以是一個(gè)遞歸表（9）設(shè)二叉樹(shù)根結(jié)點(diǎn)的層次為1，一棵深度（高度）為k的滿二叉樹(shù)和同樣深度完全二叉樹(shù)各有f個(gè)結(jié)點(diǎn)和c個(gè)結(jié)點(diǎn)，下列關(guān)系式不正確的是（）。A）f=cB）cfC）f=2k-1D）c2k-1-1（10）從L=(apple,pear),(orange,banana)中，取出banana元素的表達(dá)式為（）。A）head(tail(L)B）head(head(tail(L)C）tail(head(tail(L)D）head(tail(head(tail(L)二、（每小題4分，共8分）寫(xiě)出下列中綴表達(dá)式的后綴形式：（1）3*X/(Y-2)+1（2）2+X*(Y+3)三、（每小題4分，共8分）試對(duì)如下圖中的二叉樹(shù)畫(huà)出其：（1）順序存儲(chǔ)表示；（2）二叉鏈表存儲(chǔ)表示的示意圖。四、（每小題4分，共8分）判斷以下序列是否是小根堆? 如果不是，將它調(diào)整為小根堆。（1） 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 （2） 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 五、（本題8分）一棵非空的有向樹(shù)中恰有一個(gè)頂點(diǎn)入度為0，其他頂點(diǎn)入度為1。但一個(gè)恰有一個(gè)頂點(diǎn)入度為0、其他頂點(diǎn)入度為1的有向圖卻不一定是一棵有向樹(shù)。請(qǐng)舉例說(shuō)明之。六、（每小題2分，共8分）設(shè)有12個(gè)數(shù)據(jù)25,40,33,47,12,66,72,87,94,22,5,58，它們存儲(chǔ)在散列表中，利用線性探測(cè)再散列處理沖突，取散列函數(shù)為H(key)=key % 13。（1）順次將各個(gè)數(shù)據(jù)散列到表中，并同時(shí)列出各元素的比較次數(shù)。（2）計(jì)算查找成功的平均查找次數(shù)。七、（第1小題2分，第2、3小題每小題3分，本題8分）對(duì)于如下圖所示的圖G，鄰接點(diǎn)按從小到大的次序。（1）圖G有幾個(gè)連通分量？（2）按深度優(yōu)先搜索所得的樹(shù)是什么？（3）按深度優(yōu)先搜索所得的頂點(diǎn)序列是什么？八、（本題8分）已知一棵樹(shù)邊的結(jié)點(diǎn)為： ,試畫(huà)出這棵樹(shù)，并回答下列問(wèn)題：（1）哪個(gè)是根結(jié)點(diǎn)？（2）哪些是葉子結(jié)點(diǎn)？（3）樹(shù)的深度是多少？九、（本題9分）給出一組關(guān)鍵字T=(12,2,16,30,8,28,4,10,20,6,18)。寫(xiě)出用下列算法從小到大排序時(shí)第一趟結(jié)束時(shí)的序列。（1）希爾排序（第一趟排序的增量為5）（2）快速排序（選第一個(gè)記錄為樞軸）十、（本題15分）編寫(xiě)復(fù)制一棵二叉樹(shù)的非遞歸算法。模擬試題（五）參考答案一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）B（2）B（3）B（4）C（5）A（6）D（7）C（8）B（9）B（10）D二、（每小題4分，共8分）（1）3 X * Y 2 - / 1 + （2）2 X Y 3 + * + 三、（每小題4分，共8分）（1）二叉樹(shù)的順序存儲(chǔ)表示如下所示： 0123456789101112131415161718123456789（2）二叉樹(shù)的二叉鏈表存儲(chǔ)表示的示意圖如下圖所示： 四、（每小題4分，共8分）（1）不是小根堆。調(diào)整為：12,24,33,65,33,56,48,92,86,70 （2）是小根堆。五、（本題8分）如圖5-14所示的有向圖，只有一個(gè)頂點(diǎn)的入度為0外，其他每個(gè)頂點(diǎn)的入度都為1，因?yàn)榉沁B通，所以此圖卻不是有向樹(shù)。六、（每小題2分，共8分）（1）取散列函數(shù)為H(key)=key % 13。（2）順次將各個(gè)數(shù)據(jù)散列到表中，并同時(shí)列出各元素的比較次數(shù)如下表所示。各元素的比較次數(shù)地址01234567891011121314關(guān)鍵字40669455833477287222512比較121111132312（4）計(jì)算查找成功的平均查找次數(shù)=（17+23+32）/12=19/12。七、（第1小題2分，第2、3小題每小題3分，本題8分）（1）圖G有2個(gè)連通分量。（2）按深度優(yōu)先搜索所得的樹(shù)如下圖所示：（3）按深度優(yōu)先搜索所得的頂點(diǎn)序列：ABHFGCDE八、（本題8分）【解答】樹(shù)，如下圖所示：（1）C是根結(jié)點(diǎn)。（2）F，K，L，H，D，M，N是葉子結(jié)點(diǎn)。（3）深度是5。九、（本題9分）（1）（12,2,10,20,6,18,4,16,30,8,28）（2）（6,2,10,4,8,12,28,30,20,16,18）十、（本題15分）可采用層次遍歷的方式進(jìn)行復(fù)制，將已復(fù)制的結(jié)點(diǎn)進(jìn)入一個(gè)隊(duì)列中即可。具體算法實(shí)現(xiàn)如下：/ 文件路徑名:exam5alg.h template void CopyBitree(BinaryTree *fromBtPtr, BinaryTree *&toBtPtr)/ 操作結(jié)果: 復(fù)制二叉樹(shù)fromBt到toBt的非遞歸算法if (toBtPtr != NULL) delete toBtPtr;/ 釋放toBtPtrif (fromBtPtr = NULL | fromBtPtr-Empty()/ 空二叉樹(shù)toBtPtr = NULL;/ 空二叉樹(shù)else/ 非空二叉樹(shù)LinkQueueBinTreeNode * fromQ, toQ;/ 隊(duì)列BinTreeNode *fromPtr, *toPtr, *fromRoot, *toRoot;fromRoot = fromBtPtr-GetRoot();/ 取出fromBtPtr的根toRoot = new BinTreeNode(fromRoot-data);/ 復(fù)制根結(jié)點(diǎn)fromQ.InQueue(fromRoot); toQ.InQueue(toRoot);/ 入隊(duì)while (!fromQ.Empty()/ fromQ非空f(shuō)romQ.OutQueue(fromPtr);/ 出隊(duì) toQ.OutQueue(toPtr);/ 出隊(duì) if (fromPtr-leftChild != NULL)/ 左子樹(shù)非空toPtr-leftChild = new BinTreeNode(fromPtr-leftChild-data);/ 復(fù)制fromPtr左孩子fromQ.InQueue(fromPtr-leftChild); toQ.InQueue(toPtr-leftChild);/ 入隊(duì)if (fromPtr-rightChild != NULL)/ 右子樹(shù)非空 toPtr-rightChild = new BinTreeNode(fromPtr-rightChild-data);/ 復(fù)制fromPtr左孩子fromQ.InQueue(fromPtr-rightChild); toQ.InQueue(toPtr-rightChild);/ 入隊(duì)toBtPtr = new BinaryTree(toRoot);/ 生成toBtPtr模擬試題（六）一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）下列敘述