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