【文章內(nèi)容簡介】 二叉樹對應(yīng)的森林最多包含 _______________ 棵非空樹。 答案： 5． 深度為 n(n0) 的二叉樹最多有 _______________ 個結(jié)點。 答案： 6． n(n0) 個結(jié)點、 (n1) 條邊的連通無向圖中，頂點度數(shù)最大值為 _______________ 。 答案： 7． 在一個圖中，所有頂點的度數(shù)之和等于所有邊的數(shù)目的 _________倍。 答案： 8． 圖的深度優(yōu)先搜索方法類似于二叉樹的 _________遍歷。 答案： 9． 帶權(quán)連通圖 G, 其中 V={v1,v2,v3,v4,v5}， E={(v1,v2)7,V1,V3)6,(V1,V4)9,(V2,V3)8,(V2,V3)8,(V2,V4)4,(V2,V5)4,(V3,V4)6,(V4,V5)2}（注：頂點偶對右下角的數(shù)據(jù)為邊上的權(quán)值）， G 的最小生成樹的權(quán)值之和為 ____________。 答案： 2,4,6,8,10,12,14,16,18,20 依次存放于一個一維 數(shù)組中，然后采用折半查找方法查找元素 12，被比較過的數(shù)組元素的下標(biāo)依次為 _________。 答案： ，然后將其放在已經(jīng)排好序的序列的合適位置。這種排序法稱為 _________排序法。 答案： ，該元素將當(dāng)前參加排序的那些元素分成前后兩個部分，前一部分中所有元素都小于等于所選元素，后一部分中所有元素都大于或等于所選元素，而此時所選元素處在排序的最終位置。這種排序法稱為 _________排序法。 答 案： (49,38,65,97,76,27,13,50)采用快速排序法進(jìn)行排序，以序列的第一個元素為基準(zhǔn)元《軟件技術(shù)基礎(chǔ)》試題庫 素得到的劃分結(jié)果是 __________________。 答案： 14． 一個數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示 (映象 )稱為 ________________ 。 答案： 15． 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（ D, R ），其中 D 是 的有限集合， R 是 D 上 的 有限集合。 答案： 16．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的 _____無關(guān)，是獨立 于計算機(jī)的。 答案： 17．一個算法具有 5 個特性 :__________、 __________、 ___________、有零個或多個輸入、有一個或多個輸出。 答案： 18．線性表中 ____________________________ 稱為表的長度。 答案： 19．設(shè)長度為 n 的線性表順序存貯 ,若在它的第 i1 和第 i 個元素之間插入一個元素 , 共需移動 _________ 個元素 (1i≤n)。 答案： 20．在單鏈表中要在已知結(jié)點 *p 之前插入一新結(jié)點，需找到 。 答案： 21．循環(huán)鏈表的主要優(yōu)點是 。 答案： 從任何一個結(jié)點出發(fā)可以遍歷所有結(jié)點 22．在一個單鏈表中刪除 p 所指結(jié)點的下一個結(jié)點時，應(yīng)執(zhí)行以下操作： q=plink。 plink=____ __ Delete q 答案： 23．設(shè) SQ 為循環(huán)隊列，存儲在數(shù)組 d[m] 中，則 SQ 出隊操作對其隊頭指針 front 的修改是 _______________ 。 答案： 《軟件技術(shù)基礎(chǔ)》試題庫 24．棧中元素的進(jìn)出原則為 _____________________ 。 答案： 25．在解決計算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個 結(jié)構(gòu)，其主要特點是 。 答案： 26．對于一個以順序?qū)崿F(xiàn)的循環(huán)隊列 Q[0…m 1]，隊頭、隊尾指針分別為 f、 r，其判空的條件是 ，判滿的條件是 。 答案： r=f、 (r+1)%m=f 27．在具有 n 個單元的循環(huán)隊列中，隊滿時共有 _______個元素。 答案： 28．深度為 n(n0) 的二叉樹最多有 _______________ 個結(jié)點。 答案： 29． n(n0) 個結(jié)點、 (n1) 條邊的連通無向圖中，頂點度數(shù)最大值為 _______________ 。 答案： 30．一棵深度為 6 的滿二叉樹有 ______個非終端結(jié)點。 答案： 31．若一棵二叉樹中有 8 個度為 2 的結(jié)點 ,則它有 _____個葉子。 答案： 32．樹中結(jié)點 A 的 ____________________ 稱為 結(jié)點 A 的度。 答案： 33．一棵深度為 4 的二叉樹最多有 _______ 個結(jié)點。 答案： 34．將 轉(zhuǎn)化為二叉樹時，其根結(jié)點的右子樹總是空的。 答案： 35．哈夫曼樹是帶權(quán)路徑長度 的樹，通常權(quán)值較大的結(jié)點離根結(jié)點 。 答案： 《軟件技術(shù)基礎(chǔ)》試題庫 36．具有 n 個葉子的二叉樹，每個葉子的權(quán)值為 wi(1≤i≤n)其中帶權(quán)路徑最小的二叉樹被稱為 。 答案： 37．若已知一棵二叉樹的先序序列為 – + a * b – c d / e f，中序序列為 a + b * c – d – e / f，則其后序序列為 ___________。 答案： 38．已知一棵完全二叉樹中共有 768 結(jié)點，則該樹中共有 _____個葉子結(jié)點。 答案： 39．已知二叉樹有 50 個葉子結(jié)點，且僅有一個孩子的結(jié)點數(shù)為 30，則總結(jié)點數(shù)為 。 答案： 40．具有 10 個頂點的無向圖 ,邊的總數(shù)最多為 _____________ 。 答案： 41．在有 n 個頂點的有向圖中，每個頂點的度最大可達(dá) 。 答案： 42．有向圖 g 用 鄰接矩陣 a［１ …m,1…m ］來存儲，其第 i 行的所有元素之和等于頂點 i的 。 答案： 43． 有 n 個球隊參加的足球聯(lián)賽按主客場制進(jìn)行比賽，共需進(jìn)行 場比賽。 答案： 44． 帶權(quán)連通圖 G=V,E，其中 V={v1,v2,v3,v4,v5,},E={(v1,v2)7,(v1,v4)6， (v1,v4)9， (v2,v3)8，(v2,v4)4， (v2,v5)4， (v3,v4)6， (v4,v5)2， (注：頂點偶對右下角的數(shù)據(jù)為邊上的權(quán)值 )， G 的最小生成樹的權(quán)值之和為 __________________ 。 答案： 45． 順序查找 n 個元素的順序表 ,當(dāng)使用監(jiān)視哨時 ,若查找成功 ,比較關(guān)鍵字的次數(shù)至少為 ___次 , 最多為 ____次；若查找失敗 ,比較關(guān)鍵字的次數(shù)為 ____次。 答案： 46． 在單鏈表上難以實現(xiàn)的排序方法有 、 和 。 答案： 快速排序、堆排序 、 希爾排序 《軟件技術(shù)基礎(chǔ)》試題庫 五、簡答題 /問答題 /綜述題 1．什么是 順序表 ？ 順序表的 特點 是什么 ？ 答案： 線性表的順序存儲是指在內(nèi)存中用一塊地址連續(xù)的存儲空間順序存放線性表的各元素，用這種形式存儲的線性表稱為順序 表。數(shù)據(jù)元素在順序表中物理位置取決于數(shù)據(jù)元素在線性表中的邏輯位置，可得出順序表的特點：邏輯位置相鄰，其物理位置也相鄰。 2．什么樣的圖是連通圖？ 答案： 在無向圖 G 中，如果從一個頂點 vi 到另一個頂點 vj(i≠j)有路徑，則稱頂點 vi 和頂點vj 是連通的，若圖中任意兩頂點間都是相通的，則稱此圖是 連通圖 。 3． 二叉樹有哪幾種基本形態(tài) ? 畫圖說明之。 答案： 六、操作題 /綜合能力題 1．若對序列 (76， 38， 65， 13， 97， 27， 50， 49)采用 冒泡 排序法 (按照值的大小從小到大 )進(jìn)行排序， 共需幾趟排序？ 請分別 在下表中寫出每一趟的結(jié)果： 原始序列 76 38 65 13 97 27 50 49 答案： 共需 5 趟 第 1 趟結(jié)果 38 65 13 76 27 50 49 97 第 2 趟結(jié)果 38 13 65 27 50 49 76 97 第 3 趟結(jié)果 13 38 27 50 49 65 76 97 第 4 趟結(jié)果 13 27 38 49 50 65 76 97 第 5 趟結(jié)果 13 27 38 49 50 65 76 97 2． 若對序列 (76， 38， 65， 13， 97， 27， 50， 49)采用 選擇 排 序法 (按照值的大小從小到大 )進(jìn)行排序，請分別在下表中寫出每一趟的結(jié)果： 原始序列 76 38 65 13 97 27 50 49 答案： 第 1 趟結(jié)果 76 38 65 13 49 27 50 97 第 2 趟結(jié)果 50 38 65 13 49 27 76 97 第 3 趟結(jié)果 50 38 27 13 49 65 76 97 第 4 趟結(jié)果 49 38 27 13 50 65 76 97 第 5 趟結(jié)果 13 38 27 49 50 65 76 97 第 6 趟結(jié)果 13 27 38 49 50 65 76 97 第 7 趟結(jié)果 13 27 38 49 50 65 76 97 3． 把 1 、 2 、 3 、 4 依次進(jìn)棧（棧初始為空），任何時刻（只要棧不空），都可以出（退）《軟件技術(shù)基礎(chǔ)》試題庫 棧，試寫出所有可能的出棧序列（如 1234 ）。 答案： 4． 若一二叉樹有 2 度結(jié)點 100 個，則其葉結(jié)點有多少個？該二叉樹可以有多少個 1 度頂點？ 答案： 5． 已知某非空二叉排序樹采用順序存儲結(jié)構(gòu)依次將所有結(jié)點的數(shù)據(jù)信息存放于一維數(shù)組 ABDIC□EF□□C□□□H， 請分別寫出該二叉樹的前序遍歷序列與中序遍歷序列。 答案 ： 6． 二叉樹的順序存儲結(jié)構(gòu) : 答案： 7． 給定 30 個字符組成的電文 : D D D D D A A A B E E A A F C D A A C A B B C C C B A A D D 試為字符 A、 B、 C、 D、 E、 F 設(shè)計哈夫曼 (Huffman)編碼。 (1)畫出相應(yīng)的哈夫曼樹； (2)分別列出 A、 B、 C、 D、 E、 F 的哈夫曼碼； (3)計算該樹的帶權(quán)路徑長度 WPL。 答案： 8． 試將森林 F={ T1,T2,T3,T4 }轉(zhuǎn)換為一棵二叉樹。 T1 T2 T3 T4 答案： 9． 試畫出下列二叉樹的中序線索二叉樹存儲結(jié)構(gòu)圖。 《軟件技術(shù)基礎(chǔ)》試題庫 二叉樹 答案： 10． 試用孩子兄弟 (左孩子右兄弟 )表示法畫出下列樹的存儲結(jié)構(gòu)圖。 樹 答案： 11． 已知二叉樹的前序遍歷序列和中序遍歷序列分別是： B,A,C,D,F,E,G 和 D,C,A,F,G,E,B, 試畫出該二叉樹。 答案： 12． 試用雙親表示法畫出下列樹 T 的存儲結(jié)構(gòu)圖。 答案： 13． 假定后序遍歷二叉樹的結(jié)果是 A,C,B (1)試畫出所有可得到這一結(jié)果的不同形態(tài)的二叉樹； (2)分別寫出這些二叉樹的中序遍歷序列。 答案： 14．有 9 個帶權(quán)結(jié)點 a、 b、 c、 d、 e、 f、 g、 h、 I，分別帶權(quán) 4， 2， 7， 12， 6， 10， 5， 9，3，試以他們?yōu)槿~子結(jié)點構(gòu)造一棵哈夫曼樹（請按照左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)的次序構(gòu)造）。 答案： 《軟件技術(shù)基礎(chǔ)》試題庫 15．某二叉樹的結(jié)點數(shù)據(jù)采用順序存儲表示如下： (1) 試畫出此二叉樹的圖形表示。 (2) 寫出結(jié)點 D 的雙親結(jié)點及左、右子女。 (3) 將此二叉樹看作森林的二叉樹表示，試將它還原為森林。 答案： 16．圖的鄰接矩陣 : 答案： 17． 有向圖的逆鄰接表 : 答案： 18．找出下面網(wǎng)絡(luò)的最小生成樹。 答案： 19． 找出下面網(wǎng)絡(luò)的最小生成樹 : 答案： 20． 試畫出下列圖的鄰接表。 《軟件技術(shù)基礎(chǔ)》試題庫 圖 答案：