：圖練習(xí)習(xí)題

1、第七章：圖練習(xí)題一、 選擇題1、一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有（ ）條邊。A、n B、n(n-1) C、n(n-1)/2 D、2n2、具有6個(gè)頂點(diǎn)的無(wú)向圖至少有（ ）條邊才能保證是一個(gè)連通圖。A、5 B、6 C、7 D、83、具有n個(gè)頂點(diǎn)且每一對(duì)不同的頂點(diǎn)之間都有一條邊的圖被稱為（ ）。A、線性圖 B、無(wú)向完全圖 C、無(wú)向圖 D、簡(jiǎn)單圖4、具有4個(gè)頂點(diǎn)的無(wú)向完全圖有（ ）條邊。A、6 B、12 C、16 D、205、G是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有（ ）個(gè)頂點(diǎn)A、6 B、7 C、8 D、96、存儲(chǔ)稀疏圖的數(shù)據(jù)結(jié)構(gòu)常用的是（ ）。A、鄰接矩陣 B、三元組 C、鄰接表 D、十字鏈表7

2、、對(duì)一個(gè)具有n個(gè)頂點(diǎn)的圖，采用鄰接矩陣表示則該矩陣的大小為（ ）。A、n B、(n-1)2 C、(n+1)2 D、n28、設(shè)連通圖G的頂點(diǎn)數(shù)為n，則G的生成樹的邊數(shù)為（ ）。A、n-1 B、n C、2n D、2n-19、n個(gè)頂點(diǎn)的無(wú)向圖的鄰接表中結(jié)點(diǎn)總數(shù)最多有（ ）個(gè)。A、2n B、n C、n/2 D、n(n-1)10、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則表向量的大小為（ ），所有頂點(diǎn)鄰接表的結(jié)點(diǎn)總數(shù)為（ ）。A、n B、n+1 C、n-1 D、2n E、e/2 F、e G、2e H、n+e11、在有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)中，頂點(diǎn)v在表結(jié)點(diǎn)中出現(xiàn)的次數(shù)是（ ）。A、頂點(diǎn)v的

3、度 B、頂點(diǎn)v的出度 C、頂點(diǎn)v 的入度 D、依附于頂點(diǎn)v的邊數(shù)12、已知一個(gè)圖，若從頂點(diǎn)a出發(fā)進(jìn)行深度和廣度優(yōu)先搜索遍歷，則可能得到的頂點(diǎn)序列分別為（ ）和（ ）（1） A、abecdf B、acfebd C、acebfd D、acfdeb（2） A、abcedf B、abcefd C、abedfc D、acfdeb13、采用鄰接表存儲(chǔ)的圖的深度和廣度優(yōu)先搜索遍歷算法類似于二叉樹的（ ）和（ ）。A、中序遍歷 B、先序遍歷 C、后序遍歷 D、層次遍歷14、已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖所示，分別根據(jù)圖的深度和廣度優(yōu)先搜索遍歷算法，從頂點(diǎn)v1出發(fā)，得到的頂點(diǎn)序列分別為（ ）和（ ）。A、v

4、1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v2,v3,v5,v4 D、v1,v4,v3,v5,v215、已知有8個(gè)頂點(diǎn)為A，B，C，D，E，F(xiàn)，G，H的無(wú)向圖，其鄰接矩陣存儲(chǔ)結(jié)構(gòu)如下，由此結(jié)構(gòu)，從A點(diǎn)開始深度遍歷，得到的頂點(diǎn)序列為（ ）。ABCDEFGHA01010000B10101110C01010000D10100010E01000001F01000011G01010101H00001110A、ABCDGHFE B、ABCDGFHE C、ABGHFECD D、ABFHEGDCE、ABEHFGDC F、ABEHGFCD16、已知一個(gè)圖如下，在該圖的最小生成樹中各

5、邊上權(quán)值之和為（ ），在該圖的最小生成樹中，從v1到v6的路徑為（ ）。A、31 B、38 C、36 D、43 E、v1,v3,v6 F、v1,v4,v6 G、v1,v5,v4,v6 H、v1,v4,v3,v6 17、關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中的（ ）。A、從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 B、從源點(diǎn)到匯點(diǎn)的最短路徑C、最長(zhǎng)的回路 D、最短的回路18、正確的AOE網(wǎng)必須是（ ），AOE網(wǎng)中某邊權(quán)值應(yīng)當(dāng)是（ ），權(quán)值為0的邊表示（ ）。（1）A、完全圖 B、哈密爾頓圖 C、無(wú)環(huán)圖 D、強(qiáng)連通圖（2）A、實(shí)數(shù) B、正整數(shù) C、正數(shù) D、非負(fù)數(shù)（3）A、為決策而增加的活動(dòng) B、為計(jì)算方便而增加的活動(dòng) C、表示活

6、動(dòng)間的時(shí)間順序關(guān)系 D、該活動(dòng)為關(guān)鍵活動(dòng)19、已知一個(gè)圖如下，則由該圖得到的一種拓?fù)湫蛄袨椋?）。A、v1,v4,v6,v2,v5,v3 B、v1,v2,v3,v4,v5,v6 C、v1,v4,v2,v3,v6,v5 D、v1,v2,v4,v6,v3,v520、下面結(jié)論中正確的是（ ）A、在無(wú)向圖中，邊的條數(shù)是頂點(diǎn)度數(shù)之和。 B、在圖結(jié)構(gòu)中，頂點(diǎn)可以沒有任何前驅(qū)和后繼。 C、在n個(gè)頂點(diǎn)的無(wú)向圖中，若邊數(shù)大于n-1，則該圖必定是連通圖 D、圖的鄰接矩陣必定是對(duì)稱矩陣。21、下面結(jié)論中正確的是（ ）A、若有向圖的鄰接矩陣中對(duì)角線以下元素均為0，則該圖的拓?fù)渑判蛐蛄斜囟ù嬖凇?B、網(wǎng)絡(luò)的最小代價(jià)生成

7、樹是唯一的。 C、在拓?fù)渑判蛐蛄兄?，任意兩個(gè)相繼頂點(diǎn)vi和vj都存在從vi到vj的路徑。 D、在有向圖中，從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的最短路徑是唯一的。22、下面結(jié)論不正確的是（ ）。A、無(wú)向圖的連通分量是該圖的極大連通子圖。 B、有向圖用鄰接矩陣表示容易實(shí)現(xiàn)求頂點(diǎn)度數(shù)的操作。 C、無(wú)向圖用鄰接矩陣表示，圖中的邊數(shù)等于鄰接矩陣元素之和的一半。 D、有向圖的鄰接矩陣必定不是對(duì)稱矩陣。23、下面結(jié)論中正確的是（ ）。A、按深度優(yōu)先搜索遍歷圖時(shí)，與始點(diǎn)相鄰的頂點(diǎn)先于不與始點(diǎn)相鄰的頂點(diǎn)訪問。 B、一個(gè)圖按深度優(yōu)先搜索遍歷的結(jié)果是唯一的。 C、若有向圖G中包含一個(gè)環(huán)，則G的頂點(diǎn)間不存在拓?fù)渑判颉?D、圖的拓

8、撲排序序列是唯一的。24、下面結(jié)論中不正確的是（ ）。A、按廣度優(yōu)先搜索遍歷圖時(shí)，與始點(diǎn)相鄰的頂點(diǎn)先于不與始點(diǎn)相鄰的頂點(diǎn)訪問。 B、一個(gè)圖按廣度優(yōu)先搜索遍歷的結(jié)果是唯一的。 C、無(wú)向圖的鄰接表表示法中，表中結(jié)點(diǎn)的數(shù)目是圖中邊的條數(shù)的2倍。 D、圖的多重鄰接表表示法中，表中結(jié)點(diǎn)數(shù)目是圖中邊的條數(shù)。二、 填空題1、n個(gè)頂點(diǎn)的連通圖至少有（ ）條邊。2、一個(gè)無(wú)向圖有n個(gè)頂點(diǎn)和e條邊，則所有頂點(diǎn)的度數(shù)之和為（ ）。3、在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)可以有（ ）。4、若無(wú)向圖G的頂點(diǎn)度數(shù)的最小值大于或等于（ ）時(shí)，G至少有一條回路。5、設(shè)無(wú)向圖G的頂點(diǎn)數(shù)為n，圖G最少有（ ）邊，最多有（ ）

9、條邊。若G為有向圖，有n個(gè)頂點(diǎn)，則圖G最少有（ ）條邊，最多有（ ）條邊。具有n個(gè)頂點(diǎn)的無(wú)向完全圖，邊的總數(shù)為（ ）條，而有n個(gè)頂點(diǎn)的有向完全圖，邊的總數(shù)為（ ）條。6、在無(wú)權(quán)圖G的鄰接矩陣A中，若(vi,vj)或<vi,vj>屬于G的邊/弧的集合，則對(duì)應(yīng)元素Aij等于（ ），否則等于（ ）。7、在無(wú)向圖G的鄰接矩陣A中，若Aij=1，則Aji等于（ ）。8、已知一個(gè)圖的鄰接矩陣表示，計(jì)算第I個(gè)頂點(diǎn)的入度方法為（ ）9、在一個(gè)圖G的鄰接表表示中，每個(gè)頂點(diǎn)的鄰接表中所含的結(jié)點(diǎn)數(shù)，對(duì)于有向圖而言等于該頂點(diǎn)的（ ），而對(duì)于無(wú)向圖而言等于該頂點(diǎn)的（ ）。10、已知圖G的鄰接表如下，從頂點(diǎn)v

10、1出發(fā)的深度優(yōu)先搜索遍歷序列為（ ），廣度優(yōu)先序列為（ ）。11、n個(gè)頂點(diǎn)的弱連通有向圖G最多有（ ）條弧，最少有（ ）條弧。12、在n個(gè)頂點(diǎn)e條邊的連通圖中，連通分量個(gè)數(shù)為（ ）。13、任何（ ）的有向圖，其所有結(jié)點(diǎn)都可以排 在一個(gè)拓?fù)湫蛄兄?，拓?fù)渑判虻姆椒ㄊ窍葟膱D中選一個(gè)（ ）為0的結(jié)點(diǎn)且輸出，然后從圖中刪除該結(jié)點(diǎn)及其（ ），反復(fù)執(zhí)行，直到所有結(jié)點(diǎn)都輸出為止。14、一個(gè)連通圖的（ ）是一個(gè)極小連通子圖。15、在AOE網(wǎng)中，從源點(diǎn)到匯點(diǎn)各活動(dòng)時(shí)間總和最長(zhǎng)的路徑為（ ）。三、 簡(jiǎn)答題1、 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的連通無(wú)向圖，如果它有且只有一個(gè)簡(jiǎn)單回路，此圖有幾條邊一個(gè)具有n個(gè)頂點(diǎn)的弱連通圖至少有

11、幾條邊2、 已知某圖的鄰接表，如何建立該圖的鄰接矩陣3、 有4個(gè)頂點(diǎn)A，B，C，D的無(wú)向連通圖，按廣度和深度搜索遍歷結(jié)果都為ABCD，畫出所有可能的結(jié)構(gòu)圖4、 簡(jiǎn)述無(wú)向圖和有向圖有哪幾種存儲(chǔ)結(jié)構(gòu)，并說(shuō)明各種結(jié)構(gòu)在圖的不同操作中有什么優(yōu)越性5、 什么是AOE網(wǎng)的關(guān)鍵路徑6、 給出下圖鄰接矩陣、鄰接表和鄰接多重表存儲(chǔ)結(jié)構(gòu)。從頂點(diǎn)1出發(fā)進(jìn)行廣度個(gè)深度優(yōu)先搜索遍歷。7、 對(duì)下圖，請(qǐng)給出（1）對(duì)應(yīng)的鄰接矩陣，并給出v1,v2,v3三個(gè)頂點(diǎn)的出度和入度；（2）鄰接表和逆鄰接表表示；（3）強(qiáng)連通分量。8、 試列出圖中全部可能的拓?fù)渑判蛐蛄?。答案：一?選擇題12345678CABADCDA910111213

12、141516DAGCDBBDCBB1718192021222324ACDBABADCB二、 填空題1n-19出度數(shù)，度數(shù)22e10V1v2v3v6v5v4,v1v2v5v4v3v63任意多個(gè)11N(n-1),n-14412等于150,n(n-1)/2,0,n(n-1),n(n-1)/2,n(n-1)13無(wú)環(huán)，前驅(qū)，所有以它為尾的弧61,014生成樹7115關(guān)鍵路徑8求矩陣第I列非零元素之和三、 簡(jiǎn)答題1、（1）n條邊 （2）n-1條邊2、根據(jù)鄰接表中表向量的大小確定鄰接矩陣的行列數(shù)；由第I個(gè)頂點(diǎn)指向的單鏈表中結(jié)點(diǎn)j來(lái)確定鄰接矩陣中第I行j列元素為1，其余為0。3、略4、圖的存儲(chǔ)結(jié)構(gòu)有鄰接矩陣、

13、鄰接表、十字鏈表和鄰接多重表。借助于鄰接矩陣容易判斷任意兩個(gè)頂點(diǎn)是否有邊/弧相連，并容易求出頂點(diǎn)的度。對(duì)無(wú)向圖，頂點(diǎn)vi的度是鄰接矩陣中第I行或第j列的元素之和；對(duì)有向圖，第I行的元素之和為頂點(diǎn)vi的出度，第j列的元素之和為頂點(diǎn)vj的入度。在無(wú)向圖的鄰接表中，第I個(gè)鏈表中表結(jié)點(diǎn)個(gè)數(shù)恰好為頂點(diǎn)vi的度；而在有向圖中，第I個(gè)鏈表中表結(jié)點(diǎn)個(gè)數(shù)只是頂點(diǎn)vi的出度。利用十字鏈表容易求得頂點(diǎn)的出度和入度。鄰接多重表適合于對(duì)邊進(jìn)行操作，如在遍歷時(shí)對(duì)邊作記號(hào)或在拓?fù)渑判蛑袑?duì)邊進(jìn)行刪除。5、在AOE網(wǎng)中完成工程的最短時(shí)間是從開始點(diǎn)到完成點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度，這條路徑長(zhǎng)度最長(zhǎng)的路徑叫關(guān)鍵路徑。第九章：查找復(fù)習(xí)題一、

14、 選擇題1、順序查找一個(gè)共有n個(gè)元素的線性表，其時(shí)間復(fù)雜度為（ ），折半查找一個(gè)具有n個(gè)元素的有序表，其時(shí)間復(fù)雜度為（ ）。A、O(n) B、O(log2n) C、O(n2) D、O(nlog2n)2、在對(duì)長(zhǎng)度為n的順序存儲(chǔ)的有序表進(jìn)行折半查找，對(duì)應(yīng)的折半查找判定樹的高度為（ ）。A、n B、log2n C、log2(n+1) D、log2(n+1)3、采用順序查找方式查找長(zhǎng)度為n的線性表時(shí)，平均查找長(zhǎng)度為（ ）A、n B、n/2 C、(n+1)/2 D、(n-1)/24、采用折半查找方法檢索長(zhǎng)度為n的有序表，檢索每個(gè)元素的平均比較次數(shù)（ ）對(duì)應(yīng)判定樹的高度（設(shè)高度大于等于2）。A、小于 B、

15、大于 C、等于 D、大于等于5、已知有序表（13，18，24，35，47，50，62，83，90，115，134），當(dāng)折半查找值為90的元素時(shí)，查找成功的比較次數(shù)為（ ）。A、1 B、2 C、3 D、46、對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須（ ）。A、以順序方式存儲(chǔ) B、以鏈接方式存儲(chǔ) C、以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序 D、以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序7、順序查找法適合于存儲(chǔ)結(jié)構(gòu)為（ ）的線性表。A、散列存儲(chǔ) B、順序或鏈接存儲(chǔ) C、壓縮存儲(chǔ) D、索引存儲(chǔ)8、采用分塊查找時(shí)，若線性表中共有625個(gè)元素，查找每個(gè)元素的概率相同，假設(shè)采用順序查找來(lái)確定結(jié)點(diǎn)所在的塊時(shí)，每塊應(yīng)

16、分（ ）個(gè)結(jié)點(diǎn)最佳。A、10 B、25 C、6 D、6259、從鍵盤依次輸入關(guān)鍵字的值：t,u,r,b,o,p,a,s,c,l，建立二叉排序樹，則其先序遍歷序列為（ ），中序遍歷序列為（ ）。A、abcloprstu B、alcpobsrut C、trbaoclpsu D、trubsaocpl10、折半查找和二叉排序樹的時(shí)間性能（ ）。A、相同 B、不相同11、一棵深度為k的平衡二叉樹，其每個(gè)非終端結(jié)點(diǎn)的平衡因子均為0，則該樹共有（ ）個(gè)結(jié)點(diǎn)。A、2k-1-1 B、2k-1 C、2k-1+1 D、2k-1 12、利用逐點(diǎn)插入法建立序列50，72，43，85，75，20，35，45，65，30對(duì)

17、應(yīng)的二叉排序樹以后，查找元素35要進(jìn)行（ ）元素間的比較。A、4次 B、5次 C、7次 D、10次13、設(shè)Hash地址空間為0到m-1，哈希函數(shù)為h(k)=k%p，為了減少發(fā)生沖突的可能性，一般取p為（ ）。A、小于m的最大奇數(shù) B、小于m的最大素?cái)?shù) C、小于m的最大偶數(shù)D、小于m的最大合數(shù)。二、 填空題1、折半查找效率較高，但要求結(jié)點(diǎn)（ ）并且要求線性表（ ）；而對(duì)于順序查找，則線性表的存儲(chǔ)方式（ ）。2、假設(shè)在有序線性表A0A9上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為（ ），比較二次查找成功的結(jié)點(diǎn)數(shù)為（ ），比較三次查找成功的結(jié)點(diǎn)數(shù)為（ ），比較四次查找成功的結(jié)點(diǎn)數(shù)為（ ），比較五次查

18、找成功的結(jié)點(diǎn)數(shù)為（ ），平均查找長(zhǎng)度為（ ）。3、在n個(gè)記錄的有序順序表中進(jìn)行折半查找，最大的比較次數(shù)是（ ）。4、折半查找判定樹既是一種（ ），也是一種（ ）。5、順序查找法的平均查找長(zhǎng)度為（ ）；折半查找法的平均查找長(zhǎng)度為（ ）；分塊查找法（以順序查找確定塊）的平均查找長(zhǎng)度為（ ）；分塊查找法（以折半查找確定塊）的平均查找長(zhǎng)度為（ ）；哈希表查找法采用鏈接法處理沖突時(shí)的平均查找長(zhǎng)度為（ ）。6、對(duì)于長(zhǎng)度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為（ ）；若進(jìn)行折半查找，則時(shí)間復(fù)雜度為（ ）；若采用分塊查找（假定總塊數(shù)和每塊長(zhǎng)度均接近n的開方），則時(shí)間復(fù)雜度為（ ）。7、用二分法查找一個(gè)線性

19、表時(shí)，該線性表必須具有的特點(diǎn)是（ ），而分塊查找法要求將待查找的表均勻地分成若干塊且塊中諸記錄的順序可以是任意的，但塊與塊之間（ ）。8、采用散列技術(shù)來(lái)實(shí)現(xiàn)查找，需要解決的問題有：（ ）和（ ）。9、在散列存儲(chǔ)中，處理沖突有（ ）和（ ）兩類方法。10、（ ）法構(gòu)造的哈希函數(shù)肯定不會(huì)發(fā)生沖突。11、在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)的查找方法為（ ）。三、 簡(jiǎn)答題1、 簡(jiǎn)述順序查找、折半查找和分塊檢索法對(duì)被檢索表中元素中的要求。若檢索表中每個(gè)元素概率相同，則對(duì)一個(gè)長(zhǎng)度為n的表，用上面三種方法檢索時(shí)平均查找長(zhǎng)度為多少2、 畫出長(zhǎng)度為10的有序表進(jìn)行折半查找的一棵判定樹，并求其等概率下的

20、平均查找長(zhǎng)度。3、 有一個(gè)10000項(xiàng)線性表，若采用分區(qū)查找，問分成多少塊較理想平均查找長(zhǎng)度為多少若每塊為40 ，則平均查找長(zhǎng)度為多少4、 輸入一組關(guān)鍵字17，31，13，11，20，35，25，8，4，11，24，40，27，畫出由此生成的二叉排序樹，如果對(duì)每個(gè)結(jié)點(diǎn)的查找概率相等，求其ASL，并分別畫出下列操作后的二叉排序樹。（1）插入數(shù)據(jù)9；（2）刪除結(jié)點(diǎn)17；（3）再刪除結(jié)點(diǎn)13。5、 設(shè)有一組關(guān)鍵字19，01，23，14，55，20，84，27，68，11，10，77，采用哈希函數(shù)：H(key)=key%13，采用開放地址法的線性探測(cè)再散列方法解決沖突，試在0到18的Hash地址空間中

21、對(duì)該關(guān)鍵字序列構(gòu)造Hash表。6、 若哈希表的地址范圍為0到9，Hash函數(shù)為H(key)=(key2+2)mod 9,并采用鏈地址法處理沖突，畫出元素7，4，5，3，6，2，8，9依次插入哈希表以后該哈希表的狀態(tài)。答案：一、 選擇題1AB 2D 3C 4A 5B 6C 7B 8B 9CA 10B 11D 12A 13B二、 填空題1、 按關(guān)鍵字值大小有序，順序存儲(chǔ)；既可以順序存儲(chǔ)，也可以鏈接存儲(chǔ)。2、 1，2，4，8，5，3、 log2 (n+1)4、 二叉排序樹，理想平衡樹5、 (n+1)/2, (n+1)*log2(n+1)/n-1, (s2+2s+n)/（2s）, log2(n/s+1

22、)+s/2, 1+a/2 (a為裝填因子)6、 O(n), O(log2n), O(n的開平方)7、 表中元素必須按關(guān)鍵字有序；必須有序，即前一塊中每個(gè)元素的關(guān)鍵字必須大于后一塊中每個(gè)元素的關(guān)鍵字。8、 選擇哈希函數(shù)，設(shè)定處理沖突的方法9、 開放定址法，鏈地址法10、 直接定址11、 哈希查找法三、 簡(jiǎn)答題1、對(duì)于順序檢索法，表中元素可以以任何方式存放；而采用折半檢索法時(shí)要求表中元素必須是有序的，而且需要以順序方式進(jìn)行存儲(chǔ)；若利用分塊檢索法，則要求表中元素需“塊”間有序，但每一塊內(nèi)元素可任意存放。順序和折半查找的平均檢索長(zhǎng)度分別為：(n+1)/2和log2(n+1)-1。分塊法的平均查找長(zhǎng)度與

23、確定所在塊所采用的檢索方法有關(guān)，若用順序法確定塊，則長(zhǎng)度為(n/s+s)/2+1，若用折半法確定塊，則查找長(zhǎng)度為log2(n/s+1)+s/2，其中s為每塊含有的元素個(gè)數(shù)。2、對(duì)長(zhǎng)度為10的有序表進(jìn)行折半查找的判定樹如下： 查找成功的平均查找長(zhǎng)度為： ASL=（1*1+2*2+3*4+4*3）/10=3、分成100塊較理想。平均查找長(zhǎng)度ASL=(b+s)/2+1=(100+100)/2+1=101。若每塊長(zhǎng)度為40，則可分250塊，平均查找長(zhǎng)度ASL=(b+s)/2+1=146。4、相應(yīng)二叉排序樹如下：平均查找長(zhǎng)度ASL=（1*1+2*2+3*4+4*2+5*2）/12=35/125、依題意，

24、m=19，線性探測(cè)再散列的下一地址計(jì)算公式為： d1=H(key) dj+1=(dj+1)%m j=1,2,構(gòu)造的Hash表如下：地址號(hào)012345678910112131415161718關(guān)鍵字11455276819208423111077地址計(jì)算次數(shù)1214311311327、 將7，4，5，3，6，2，8，9依次插入雜湊表后，狀態(tài)如下第十章：內(nèi)部排序練習(xí)題一、 選擇題1、下述幾種排序方法中，平均查找長(zhǎng)度最小的是（ ）。A、插入排序 B、選擇排序 C、快速排序 D、歸并排序2、設(shè)關(guān)鍵字序列為（3，7，6，9，7，1，4，5，20），對(duì)其進(jìn)行排序的最小交換次數(shù)為（ ）。A、6 B、7 C、8

25、 D、203、下列排序算法中不穩(wěn)定的有（ ）。A、直接選擇排序 B、直接插入排序 C、冒泡排序 D、二叉排序E、Shell排序 F、快速排序 G、歸并排序 H、堆排序 I、基數(shù)排序4、內(nèi)部排序多個(gè)關(guān)鍵字的文件，最壞情況下最快的排序方法是（ ），相應(yīng)的時(shí)間復(fù)雜度為（ ），該算法是（ ）排序方法。A、快速排序 B、插入排序 C、歸并排序 D、簡(jiǎn)單選擇排序E、O(nlog2n) F、O(n2) G、O(n2log2n) H、O(n)I、穩(wěn)定 J、不穩(wěn)定5、對(duì)初始狀態(tài)為遞增的表按遞增順序排序，最省時(shí)間的是（ ）算法，最費(fèi)時(shí)間的算法是（ ）。A、堆排序 B、快速排序 C、插入排序 D、歸并排序6、下述幾

26、種排序方法中，要求內(nèi)存量最大的是（ ）。A、插入排序 B、選擇排序 C、快速排序 D、歸并排序7、在下面的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是（ ）。A、希爾排序 B、冒泡排序 C、插入排序 D、選擇排序8、下列排序中，排序速度與數(shù)據(jù)的初始排列狀態(tài)沒有關(guān)系的是（ ）。A、直接選擇排序 B、基數(shù)排序 C、堆排序 D、直接插入排序9、若需在O(nlog2n)的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法為（ ）。A、快速排序 B、堆排序 C、歸并排序 D、直接插入排序10、排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放

27、入已排序序列正確位置上的方法，稱為（ ）。A、希爾排序 B、冒泡排序 C、插入排序 D、選擇排序11、 每次把待排序的元素劃分為左右兩個(gè)子區(qū)間，其中左區(qū)間中元素的關(guān)鍵字均小于等于基準(zhǔn)元素的關(guān)鍵字，右區(qū)間中元素的關(guān)鍵字均大于基準(zhǔn)元素的關(guān)鍵字，則此排序方法為（ ）。A、堆排序 B、快速排序 C、冒泡排序 D、Shell排序12、排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱為（ ）。A、希爾排序 B、歸并排序 C、插入排序 D、選擇排序13、n個(gè)記錄的直接插入排序所需記錄關(guān)鍵碼的最大比較次數(shù)為（ ）。A、nlog2n B、n2/2 C、(n+2)(n-1

28、)/2 D、n-114、n個(gè)記錄的直接插入排序所需的記錄最小移動(dòng)次數(shù)為（ ）。A、2(n-1) B、n2/2 C、(n+3)(n-2)/2 D、2n15、快速排序在（ ）情況下最不利于發(fā)揮其長(zhǎng)處，在（ ）情況下最易發(fā)揮其長(zhǎng)處。A、被排序的數(shù)據(jù)量很大 B、被排序的數(shù)據(jù)已基本有序 C、被排序的數(shù)據(jù)完全有序D、被排序的數(shù)據(jù)中最大與最小值相差不大 E、要排序的數(shù)據(jù)中含有多個(gè)相同值。16、直接插入排序和冒泡排序的平均時(shí)間復(fù)雜度為（ ），若初始數(shù)據(jù)有序（正序），則時(shí)間復(fù)雜度為（ ）。A、O(n) B、O(log2n) C、O(nlog2n) D、O(n2)17、一組記錄的關(guān)鍵字為（45，80，55，40，

29、42，85），則利用堆排序的方法建立的初始堆為（ ）。A、（80，45，55，40，42，85） B、（85，80，55，40，42，45） C、（85，80，55，45，42，40） D、（85，55，80，42，45，40）二、填空題1、在直接插入和直接選擇排序中，若初始數(shù)據(jù)基本有序，則選用（ ），若初始數(shù)據(jù)基本反序，則選用（ ）。2、在對(duì)一組記錄（50，40，95，20，15，70，60，45，80）進(jìn)行冒泡排序時(shí)，第一趟需進(jìn)行相鄰記錄的交換的次數(shù)為（ ），在整個(gè)排序過程中共需進(jìn)行（ ）趟才可完成。3、n個(gè)記錄的冒泡排序算法所需最大移動(dòng)次數(shù)為（ ），最小移動(dòng)次數(shù)為（ ）。4、對(duì)n個(gè)結(jié)點(diǎn)進(jìn)行快速排序，最大比較次數(shù)為（ ）。5、在對(duì)