【正文】 【答案 】 1+2+3...+(k1)+k=k(k+1)/2 【解析】在散列表的一連串連續(xù)空間內(nèi)，第一個(gè)關(guān)鍵字只需探測(cè)一次，第二個(gè)就要探測(cè) 2 次，如此這般，第 k 個(gè)關(guān)鍵字就要探測(cè)。 C）其左右子樹均為二叉排序樹。 11． _____________是一棵二叉樹，如果不為空，則它必須滿足下面的條件： A）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根的值。因此，可得每 塊的最佳長(zhǎng)度是 16，應(yīng)將查找表分為 16塊。 【答案】（ 1） 16 （ 2） 16 （ 3） 21 【解析】分塊查找的平均查找長(zhǎng)度由兩部分組成 —— 查找索引表確定所在塊的平均查找長(zhǎng)度 Lb 和在塊中查找元素的平均查找長(zhǎng)度 Lw，即 ASLbs=Lb+Lw=(b+s)/2+1，其中 s 為每塊的長(zhǎng)度， b 為所分的快數(shù)。 【答案】（ 1）確定待查元素所在的塊 （ 2）在塊內(nèi)查找待查的元素 10．分塊查找中，要得到最好的平均查找長(zhǎng)度，應(yīng) 對(duì) 256 個(gè)元素的線性查找表分成 _____________塊，每塊的最佳長(zhǎng)度是 _____________。（設(shè)下標(biāo)從 1 開 始） 【答案】 4， 9， 14， 17， 20 8．對(duì)于線性表（ 70,34,55,23,65,41,20,100）進(jìn)行散列存儲(chǔ)時(shí)，若選用 H(K)=K%9 作為散列函數(shù)，則散列地址為 1 的元素有 _____________個(gè)，散列地址為 7 的元素有 _____________ 個(gè)。 【答案】（ 1）順序存儲(chǔ)結(jié)構(gòu) （ 2）有序 6．假設(shè)在有序線性表 A[1..20]上進(jìn)行二分查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為 _____________個(gè) ，比較二次查找成功的結(jié)點(diǎn)數(shù)為 _____________ ，比較三次查找成功的結(jié)點(diǎn)數(shù)為 _____________ ，比較四次查找成功的結(jié)點(diǎn)數(shù)為 _____________ ，比較五次查找成功的結(jié)點(diǎn)數(shù)為 _____________，平均查找長(zhǎng)度為_____________ 。 【答案】（ 1） 4 （ 2） 4 （ 3） 5 （ 4） 10 4．從一棵二叉排序樹中查找一個(gè)元素時(shí)，若元 素的值等于根結(jié)點(diǎn)的值，則表明 _____________ ，若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向 _____________查找，若元素的值大于根結(jié)點(diǎn)的值，則繼續(xù)向 _____________ 查找。 【答案】素?cái)?shù) 2．采用分塊查找法（塊長(zhǎng)為 s，以順序查找確定塊）查找長(zhǎng)度為 n 的線性表時(shí)的平均查找長(zhǎng)度為_____________。 【 答案】 C 24．設(shè)哈希表長(zhǎng) m=14，哈希函數(shù) H(key)=key%11。 C）二次探測(cè)能夠保證只要哈希表未填滿，總能找到一個(gè)不沖突的地址。 【答案】 D 23．下面有關(guān)散列沖突解決的說(shuō)法中不正確的是（ ） A）處理沖突即當(dāng)某關(guān)鍵字得到的哈希地址已經(jīng)存在時(shí)，為其尋找另一個(gè)空地址。 C）構(gòu)造哈希函數(shù)時(shí)不需要考慮記錄的查找頻率。 A )(d+1)%m B） (d1)%m C） (d+4)%m D） (d4)%m 【答案】 D 22．下面有關(guān)散列查找的說(shuō)法中正確的是（ ） A）直接定址法所得地址集合和關(guān)鍵字集合的大小不一定相同。 A） 0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON B） 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MON C） 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON D） 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON 【答案】 B 20．若根據(jù)查找表建立長(zhǎng)度為 m 的散列表，采用線性探測(cè)法處理沖突，假定對(duì)一個(gè)元素第一次計(jì)算的散列地址為 d ，則下一次的散列地址為 ( ) 。 A） 10 B） 25 C） 6 D） 625 【答案】 B 15．采用分塊查找法（塊長(zhǎng)為 s，以二分查找確定塊）查找長(zhǎng)度為 n 的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為（ ） A） s+n B） log2n＋ s/2 C） log2 (n/s+1)+s/2 D） (n+s)/2 【答案】 C 16．對(duì)一棵二叉排序樹根結(jié)點(diǎn)而言，左子樹中所有結(jié)點(diǎn)與右子樹中所有結(jié)點(diǎn)的關(guān)鍵字大小關(guān)系是（ ） A）小于 B）大于 C）等于 D）不小于 【答案】 A 17．若二叉排序樹中關(guān)鍵字互不相同，則下面命題中不正確的是（ ） A）最小元和最大元一定是葉子 B）最大元必?zé)o右孩子 C）最小元必?zé)o左孩子 D）新結(jié)點(diǎn)總是作為葉結(jié)點(diǎn)插入二叉排序樹 【答案】 A 18．設(shè)二叉排序樹中關(guān)鍵字由 1至 1000的整數(shù)構(gòu)成，現(xiàn)要查找關(guān)鍵字為 363的結(jié)點(diǎn)，下述關(guān)鍵字序列（ ）不可能是在二叉排序樹上查找到的序列 ? A） 2,252,401,398,330, 344,397,363 B） 924, 220, 911, 244, 898, 258, 362, 363 C） 2, 399, 387, 219, 266, 382, 381, 278, 363 D） 925, 202, 911, 240, 912, 245, 363 【答案】 D 19．在初始為空的散列表中依次插入關(guān)鍵字序列 (MON,TUE,WED,THU,FRI,SAT,SUN),散列函數(shù)為 H(k)=i MOD 7，其中， i 為關(guān)鍵字 k 的第一個(gè)字母在英文字母表中的序號(hào)，地址值域?yàn)? [0:6] ，采用線性再散列法處理沖突。 A） 2 B） 3 C） 4 D） 5 【答案】 C 12．從具有 n 個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)元素時(shí)，在最壞情況下的時(shí)間復(fù)雜度為 ( ) 。 100 個(gè)元素查找表的判定樹深為 8（ 64100128）。 A） R[1]， R[2]， R[3]， R[4] B） R[1]， R[13]， R[2]， R[3] C） R[7]， R[3]， R[5]， R[4] D） R[7]， R[4]， R[2]， R[3] 【答案】 C 10．設(shè)有一個(gè)長(zhǎng)度為 100 的已排好序的表，用二分查找進(jìn)行查找，若查找不成功，至少比較（ ）次。 D）經(jīng)常進(jìn)行插入和刪除操作時(shí)可以采用二分查找。 B）靜態(tài)查找表中關(guān)鍵字有序時(shí)，可用二分查找。 求解的關(guān)鍵是求解如下的一個(gè) n 階方陣序列： D(1)， D(0)， D(1)，． ．．， D(k)， D(n1) 其中 D(1)[i][j]=G． arcs[i][j] D(k)=Min{D(k1)[i][j]， D(k1)[i][k]+D(k1)[k][j]} 0≤ k≤ n1 【答案】 每對(duì)頂點(diǎn)之間的最短路徑及長(zhǎng)度總結(jié)如下： 頂點(diǎn) A 到頂點(diǎn) C 最短路徑為： AC，長(zhǎng)度為：１ 頂點(diǎn) A 到頂點(diǎn) B 最短路徑為： ACB，長(zhǎng)度為： 4 頂點(diǎn) C 到頂點(diǎn) A 最短路徑為： CBA，長(zhǎng)度為： 12 頂點(diǎn) C 到頂點(diǎn) B 最短路徑為： CB，長(zhǎng)度為： 3 頂點(diǎn) B 到頂點(diǎn) A 最短路徑為： BA，長(zhǎng)度為： 9 頂點(diǎn) B 到頂點(diǎn) C 最短路徑為： BAC，長(zhǎng)度為： 10 第 8 章 查找 選擇題 1．順序查找法適合于存儲(chǔ)結(jié)構(gòu)為（ ）的線性表。 【解析】 Floyd 算法是依次添加頂點(diǎn)來(lái)修改相應(yīng)路徑，也就是說(shuō) ,若（ vi，．．．， vk）和 (vk，．．．， vj)分別是從 vi 到 vk 和從 vk 到 vj 的中間頂點(diǎn)的序號(hào)不大于 k1 的最短路徑，則將（ vi，．．． vk，．．．，vj）和已經(jīng)得到的從 vi 到 vj 且中間頂點(diǎn)序號(hào)不大于 k１的最短路徑相比較，其長(zhǎng)度較短者便是從 vi 到 vj的中間頂點(diǎn)的序號(hào)不大于 k 的最短路徑。 【答案】 S 是已找到最短路徑的終點(diǎn)的集合。 【答案】（ 1） 0132465 （ 2） 0123465 9．給定帶權(quán)有向圖 G 和源點(diǎn) v1,利用迪杰斯特拉（ Dijkstra）算法求從 v1 到其余各頂點(diǎn)的最短路徑。 【答案】 關(guān)鍵路徑為： a0a4a6a9 8． 拓?fù)渑判虻慕Y(jié)果不是唯一的，試寫出下圖任意 2 個(gè)不同 的拓?fù)湫蛄小?（ 2）最早發(fā)生時(shí)間從 ve(0)開始按拓?fù)渑判蛳蚯斑f推到 ve(6), 最晚發(fā)生時(shí)間從 vl(6)按逆拓?fù)渑判蛳蚝筮f推到 vl(0)。要求：給出每一個(gè)事件和每一個(gè) 活動(dòng)的最早開始時(shí)間和最晚開始時(shí)間。 【答案】 【解析】 Kruscal 算法的操作步驟： 首先將 n 個(gè)頂點(diǎn)看成 n 個(gè)互不連通的分量，從邊集中找最小 代價(jià)的邊，如果落在不同連通分量上，則將其加入最小生成樹，直到所有頂點(diǎn)都在同一連通分量上。 【答案】該無(wú)向圖如下所示： 深度優(yōu)先搜索生成樹為： 廣度優(yōu)先搜索生成樹為： 6．請(qǐng)分別用 Prim 算法和 Kruskal 算法構(gòu)造以下網(wǎng)絡(luò)的最小生成樹，并求出該樹的代價(jià)。 【答案】 鄰接矩陣如下： 鄰接表如下： 逆鄰接表如下： 十字鏈表如下： 深度優(yōu)先遍歷序列為 ABCFED，廣度優(yōu)先遍歷序列為 ABDCEF 5．已知下面是某無(wú)向圖的鄰接表，畫出該無(wú)向圖，并分別給出從 A 出發(fā)的深度優(yōu)先搜索生成樹和廣度優(yōu)先搜索生成樹。 4．熟悉圖的存儲(chǔ)結(jié)構(gòu)，畫出下面有向圖的鄰接矩陣、鄰接表、逆鄰接表、十字鏈表。 （ 2）鄰接矩陣 中如果第 i 行第 j 列的元素非 0 則表示頂點(diǎn) i 與頂點(diǎn) j 相連。但在無(wú)向圖中，頂點(diǎn) i 到頂點(diǎn) j 與頂點(diǎn) j 到頂點(diǎn) i 是同一條邊，所以總共有 n(n1)/2 條邊。并說(shuō)明在 n 個(gè)頂 點(diǎn)的無(wú)向完全圖中，邊的條數(shù)為 n(n1)/2。 （ 2）強(qiáng)連通圖是任意兩頂點(diǎn)間都存在路徑的有向圖。其中， V={ v1, v2, v3, v4, v5}， E={v2, v1, v3, v2, v4, v3, v4, v2, v1, v4, v4, v5, v5, v1}，請(qǐng)畫出該有向圖并判斷是否是強(qiáng)連通圖。（ ） 【答案】√ 14．一個(gè)無(wú)向連通圖的生成樹是含有該連通圖的全部頂點(diǎn)的極大連通子圖。（ ） 【答案】 12．假設(shè)一個(gè)有 n 個(gè)頂點(diǎn)和 e 條弧的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn) vi 相關(guān)的所有弧的時(shí)間復(fù)雜度是 O(n*e) 。（ ） 【答案】 10．在 AOV 網(wǎng)絡(luò)中如果存在環(huán)，則拓?fù)渑判虿荒芡瓿伞＃? ） 【答案】√ 8．任何一個(gè)關(guān)鍵活動(dòng)提前完成 , 那么整個(gè)工程將會(huì)提前完成。（ ） 【答案】√ 6．用鄰接表表示圖時(shí)，頂點(diǎn)個(gè)數(shù)設(shè)為 n，邊的條數(shù)設(shè)為 e，在鄰接表上執(zhí)行有關(guān)圖的遍歷操作時(shí)，時(shí)間代價(jià)為 O(n+e)。（ ） 【答案】√ 4．有 n1 條邊的圖一定是生成樹。（ ） 【答案】 2．圖的最小生成樹是唯一的。 【答案】設(shè)邊的信息表示為（始點(diǎn)，終點(diǎn)，權(quán)值），則在 Kruscal 算法構(gòu)造最小生成樹過程中順序選出的各條邊為：（ 3 ， 5， 1），（ 2， 4， 2），（ 1， 5， 3），（ 1， 2， 3）。 【答案】（ 1） n （ 2） n1 10． Prim 算法和 Kruscal 算法的時(shí)間復(fù)雜度分別為 _____________和 _____________。 【答案】（ 1）出邊 （ 2） 入邊 8． 對(duì)于一個(gè)具有 n 個(gè)頂點(diǎn)和 e 條邊的無(wú)向圖，當(dāng)分別采用鄰接矩陣、鄰接表表示時(shí)，求任一頂點(diǎn)度數(shù)的時(shí)間復(fù)雜度依次為 _____________和 _____________。 【答案】（ 1） O(n2) （ 2） O(e) 6．對(duì)于一個(gè)具有 n 個(gè)頂點(diǎn)和 e 條邊的有向圖和無(wú)向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別為_____________和 _____________條。 【答案】 n1 4．假定一個(gè)圖具