數(shù)據(jù)結(jié)構(gòu)與算法c++版測(cè)試題_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)與算法c++版測(cè)試題_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)與算法c++版測(cè)試題_第3頁(yè)
數(shù)據(jù)結(jié)構(gòu)與算法c++版測(cè)試題_第4頁(yè)
數(shù)據(jù)結(jié)構(gòu)與算法c++版測(cè)試題_第5頁(yè)
已閱讀5頁(yè),還剩47頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡(jiǎn)介

更多企業(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)下列敘述

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝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ù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(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ì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論