圖、查找、排序、數(shù)組

1、第七章圖一、填空題1 若在有向圖G中存在一條弧,則稱頂點(diǎn)V于頂點(diǎn)V。2頂點(diǎn)個(gè)數(shù)為10的完全無向圖中共有 無向邊。3頂點(diǎn)個(gè)數(shù)為5的完全有向圖中共有條弧。4若某無向圖的鄰接矩陣中共有 10個(gè)值為1的元素，則說明此無向圖中共有 無向邊。5若某有向圖的鄰接矩陣中共有 10個(gè)值為1的元素，則說明此有向圖中共有弧。6. 任意一個(gè)無向圖的鄰接矩陣 （一定/不一定）是對(duì)稱矩陣。7. 在無向圖 G中，若對(duì)于任意一對(duì)頂點(diǎn)都存在路徑，則稱無向圖G為8. 在無向圖G中，若對(duì)于任意一對(duì)頂點(diǎn)都是連通的，則稱無向圖G為9. 在頂點(diǎn)個(gè)數(shù)為n的無向圖G中，若對(duì)于任意一對(duì)頂點(diǎn)都存在鄰接關(guān)系， 則無向圖G共有邊。10. 在有向圖G

2、中，若對(duì)于任意一對(duì)頂點(diǎn)都存在兩條方向相反的路徑，則稱有向圖G為。11. 具有n個(gè)頂點(diǎn)的無向圖，最多有條邊。12. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 倍。13. 對(duì)于具有n個(gè)頂點(diǎn)和e條邊的無向圖，在其對(duì)應(yīng)的鄰接鏈表中一共包含 表結(jié)點(diǎn)。14. 對(duì)于具有n個(gè)頂點(diǎn)和e條邊的有向圖，在其對(duì)應(yīng)的鄰接鏈表中一共包含 表結(jié)點(diǎn)。15. 具有n個(gè)頂點(diǎn)的有向圖，最多有 條邊。16. 邊或弧上帶有權(quán)值的圖稱為 。17. 對(duì)于一個(gè)有n個(gè)頂點(diǎn)的完全無向圖，其鄰接矩陣中值為1的元素共有個(gè)。18. 對(duì)于一個(gè)有n個(gè)頂點(diǎn)的完全有向圖，其鄰接矩陣中值為1的元素共有個(gè)。19. 對(duì)于一個(gè)有n個(gè)頂點(diǎn)的完全無向圖，其鄰接矩陣中

3、值為 0的元素共有個(gè)。20. 對(duì)于一個(gè)有向圖，所謂出度是指 。二、簡(jiǎn)答題1 對(duì)于下圖所示的無向圖，（1）畫出其鄰接矩陣和鄰接鏈表示意圖；（2）寫出 該圖基于順序（鄰接矩陣）存儲(chǔ)結(jié)構(gòu)，從頂點(diǎn)V1出發(fā)的深度優(yōu)先搜索和廣度優(yōu)2. 個(gè)有向圖的順序存儲(chǔ)結(jié)構(gòu)為（2）鄰接矩陣G1 00 01 01 1（1）存放頂點(diǎn)信息的數(shù)組verV1V2V3V4畫出其對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，并寫出基于此鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)從V1出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索的遍歷序列。（4+2+2=8分）3. 要將下面的圖用鄰接矩陣.（順序存儲(chǔ)結(jié)構(gòu)）的方式進(jìn)行存儲(chǔ)，（1）請(qǐng)畫出存 儲(chǔ)結(jié)構(gòu)示意圖；（2）根據(jù)此存儲(chǔ)結(jié)構(gòu)圖寫出對(duì)此圖進(jìn)行深度優(yōu)先搜索和廣度優(yōu)

4、先 搜索序列（遍歷從頂點(diǎn)1出發(fā)）。（4+2+2=8分）21A4. 已知一個(gè)無向圖的鄰接鏈表如下所示，請(qǐng)畫出該無向圖并寫出基于此鏈?zhǔn)酱?儲(chǔ)結(jié)構(gòu)從V1出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先遍歷的序列（4+2+2=8分）。1V163H 2 A2V24*1 3 |十1A3V721A4 | V5 |3 |2 |1 | A5V74A6V6*1A5. 設(shè)無向圖G如下圖所示，要求（1）給出該圖的鄰接矩陣和鄰接鏈表；（2） 基于鄰接矩陣寫出從V1出發(fā)進(jìn)行深度優(yōu)先搜索的遍歷序列；（3）基于鄰接鏈表 寫出從V6出發(fā)進(jìn)行廣度優(yōu)先搜索遍歷的序列（4+2+2=8分）。6. 要將下列的圖用鄰接鏈表的方式進(jìn)行存儲(chǔ)（1）請(qǐng)畫出存儲(chǔ)結(jié)構(gòu)圖，

5、（2）并根 據(jù)此存儲(chǔ)結(jié)構(gòu)圖寫出對(duì)此圖進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索的遍歷結(jié)果。（設(shè)此題中各頂點(diǎn)A B C、D E的存儲(chǔ)序號(hào)分別為：1、2、3、4、5,遍歷從A點(diǎn) 開始）。（4+4=8分）7. 對(duì)于下圖所示的無向圖，（1）畫出其鄰接矩陣和鄰接鏈表示意圖；（2）寫出 該圖基于鏈?zhǔn)剑ㄠ徑渔湵恚┐鎯?chǔ)結(jié)構(gòu)，從頂點(diǎn) V5出發(fā)的深度優(yōu)先搜索和廣度優(yōu)8. 要將下列的圖用鄰接矩陣的方式進(jìn)行存儲(chǔ)（1）請(qǐng)寫出對(duì)應(yīng)的鄰接矩陣，（2） 并根據(jù)此存儲(chǔ)結(jié)構(gòu)圖寫出對(duì)此圖進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索的遍歷結(jié)果。（設(shè)此題中各頂點(diǎn)A、B、C、D E的存儲(chǔ)序號(hào)分別為：1、2、3、4、5,遍歷從 B點(diǎn)開始）。（4+4=8分）9. 已

6、知圖G的頂點(diǎn)集合V和邊集E合分別為：V(G)=V1,V2,V3,V4,V5E(G)=(V1,V2),(V1,V3),(V1,V4),(V2,V4),(V3,V4),(V4,V5)（1） 給出圖G對(duì)應(yīng)的鄰接矩陣和鄰接鏈表；（4分）（2）當(dāng)圖G采用鄰接矩陣方式存儲(chǔ)時(shí)，寫出從頂點(diǎn)V1出發(fā)進(jìn)行深度優(yōu)先搜索和 廣度優(yōu)先搜索時(shí)的遍歷序列。（4分）10. 已知有向圖G的頂點(diǎn)集合V和邊集E合分別為：V（G）=V1,V2,V3,V4,V5E（G）=,vV1,V3,vV2,V4,vV3,V4,vV4,V2,vV4,V5,vV5,V3（1） 給出圖G對(duì)應(yīng)的鄰接矩陣和鄰接鏈表；（4分）（2）當(dāng)圖G采用鄰接矩陣方式存儲(chǔ)

7、時(shí)，寫出從頂點(diǎn)V1出發(fā)進(jìn)行深度優(yōu)先搜索和 廣度優(yōu)先搜索時(shí)的遍歷序列。（4分）11. 已知有向圖G的頂點(diǎn)集合V和邊集E合分別為：V（G）=V1,V2,V3,V4,V5E（G）=,vV1,V3,vV2,V4,vV3,V4,vV4,V1,vV4,V2,vV4,V5,vV5,V3 （1）判斷圖G是否為強(qiáng)連通圖？ （ 2分）（2）畫出圖G對(duì)應(yīng)的鄰接鏈表；（2分）（3）當(dāng)圖G采用此鄰接鏈表方式存儲(chǔ)時(shí)，寫出從頂點(diǎn)V1出發(fā)進(jìn)行深度優(yōu)先搜索 和廣度優(yōu)先搜索時(shí)的遍歷序列。（4分）12. 設(shè)無向圖G如下圖所示，要求（1）給出該圖的集合表示形式（頂點(diǎn)集合和邊集合）鄰接矩陣和鄰接鏈表；（2）給出該圖的鄰接鏈表存儲(chǔ)示意圖

8、；（3）基于此鄰接鏈表寫出從 V1出發(fā)進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷的 序列（2+2+4=8分）。13. 已知一個(gè)無向圖的順序存儲(chǔ)結(jié)構(gòu)為：（1）存放頂點(diǎn)信息的數(shù)組ver（2）鄰接矩陣GV1V2V3V4V5廠 0 0 1 10 0 10110 110 1010 111畫出其對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，并寫出基于此鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)從V1出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索的遍歷序列。（4+2+2=8分）V（G）=V1,V2,V3,V4,V5其對(duì)應(yīng)的鄰接矩陣為：14. 已知有向圖G的頂點(diǎn)集合V為:01100 0 0 10 0 0 1110 0（1）畫出圖G的圖形并判斷圖G是否為強(qiáng)連通圖？ （ 4分）（2）畫出圖G

9、對(duì)應(yīng)的鄰接鏈表；（2分）（3）當(dāng)圖G采用此鄰接鏈表方式存儲(chǔ)時(shí)，寫出從頂點(diǎn)V3出發(fā)進(jìn)行深度優(yōu)先搜索 的遍歷序列。（2分）15. 已知一個(gè)無向圖的鄰接鏈表如下所示，請(qǐng)寫出該無向圖的鄰接矩陣并寫出基 于此鄰接矩陣從V6出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先遍歷的序列（4+2+2=8分）。1234V3* 45V6V41A16. 已知有向圖G的頂點(diǎn)集合V和邊集E合分別為：V（G）=V1,V2,V3,V4,V5E（G）=,vV1,V3,vV2,V4,vV3,V4,vV4,V1,vV4,V2,vV4,V5,vV5,V3（1） 畫出圖G的圖形并求出各頂點(diǎn)的入度和出度。（4分）（2）畫出圖G對(duì)應(yīng)的鄰接矩陣；（2分）（3）

10、當(dāng)圖G采用此鄰接矩陣方式存儲(chǔ)時(shí)，寫出從頂點(diǎn)V1出發(fā)進(jìn)行廣度優(yōu)先搜索時(shí)的遍歷序列。（2分）17. 已知一個(gè)無向圖的順序存儲(chǔ)結(jié)構(gòu)為（1）存放頂點(diǎn)信息的數(shù)組verV1V2V3V4V5(2)鄰接矩陣G0110001011101110101L01110丿（1）畫出該圖的圖形；（2分）（2）給出其對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，并寫出基于此鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)從 V5出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索的遍歷序列。（6分）18. 要將下面的圖用鄰接.鏈表（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）的方式進(jìn)行存儲(chǔ)，（1）請(qǐng)畫出存 儲(chǔ)結(jié)構(gòu)示意圖；（2）根據(jù)此存儲(chǔ)結(jié)構(gòu)圖寫出對(duì)此圖進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索序列(遍歷從頂點(diǎn)1出發(fā))。(4+2+2=8分)B19.

11、已知一個(gè)無向圖的順序存儲(chǔ)結(jié)構(gòu)為(1)存放頂點(diǎn)信息的數(shù)組verV1V2V3V4V5(1)給出該圖的集合表示形式;00110A001011101110101L01110J(2)鄰接矩陣G（2 分）(2) 畫出該圖并求出各頂點(diǎn)的度；(4 分)(3) 寫出基于此順序存儲(chǔ)結(jié)構(gòu)從 V1出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索的遍歷序列。(2分)20. 已知一個(gè)無向圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為1234vj6 I H4 V3 44 丨一H 2 丨 T2AV-HR 丨1A5 V54 A(1) 給出該圖的集合表示形式；(2分)(2) 畫出該圖并求出各頂點(diǎn)的度；(4分)(3) 寫出基于此鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)從 V1出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜

12、索的遍歷序 列。(2分)第八章查找一、填空題1 對(duì)于一棵有n個(gè)結(jié)點(diǎn)、深度為h的二叉排序樹，當(dāng)查找一個(gè)指定關(guān)鍵字的元素且查找失敗時(shí)，最多需進(jìn)行 次比較。2 .在哈希查找中，元素關(guān)鍵字值與其在哈希表中存放位置的對(duì)應(yīng)關(guān)系稱為。3. 在哈希查找中，不同關(guān)鍵字值對(duì)應(yīng)到同一哈希地址上的現(xiàn)象稱為 。4 在有序表(41,62,75,77,82,95,100 )上進(jìn)行二分查找，查找關(guān)鍵字為 82的 數(shù)據(jù)元素需要比較的次數(shù)是 次。5. 若有序表的關(guān)鍵字為1到25的整數(shù)，在此序列中利用二分查找法查找數(shù)字2,在查找過程中與數(shù)字2比較的數(shù)字依次為：、2。6. 在順序表(2,5,7,10,14,15,18,23,35,4

13、1,52)中，用二分法查找關(guān)鍵字值10所需的關(guān)鍵字比較次數(shù)為 。7 .在順序表(2,5,7,10,15,18,21,25)中，用二分法查找關(guān)鍵字值20所需的關(guān)鍵字比較次數(shù)為 。8. 在有序表(3,9,12,32,41,62)上進(jìn)行二分查找時(shí)，在等概率條件下其平均查找長(zhǎng)度為。9. 線性有序表(a1, a2, a3,，a10)按關(guān)鍵字從小到大排列，對(duì)一個(gè)給定的關(guān)鍵字值k，用二分法查找表中關(guān)鍵字與k相等的元素，在查找不成功的情況下， 最多需要查找次。10采用二分查找方法時(shí)，要求線性表必須是 的線性表。11.在查找算法中，主關(guān)鍵字是指組成記錄的若干數(shù)據(jù)項(xiàng)中能夠 一條記錄的數(shù)據(jù)項(xiàng)。12對(duì)一個(gè)具有100元

14、素的有序表，若采用二分查找查找某個(gè)指定關(guān)鍵字的元素， 最多需要比較次。13. 采用二分查找方法時(shí)，要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且還應(yīng)該是 的線性表。14. 采用二分查找方法時(shí)，要求線性表必須是采用 存儲(chǔ)結(jié)構(gòu)且按查找關(guān)鍵字有序排列的線性表。15. 分塊查找中對(duì)線性表分塊后應(yīng)保證 有序。16. 在結(jié)點(diǎn)數(shù)確定的二叉排序樹上進(jìn)行查找的平均查找長(zhǎng)度與二叉樹的形態(tài)有關(guān)，最差的情況是二叉排序樹為 樹的時(shí)候。17. 在結(jié)點(diǎn)數(shù)確定的二叉排序樹上進(jìn)行查找的平均查找長(zhǎng)度與二叉樹的形態(tài)有關(guān)，最好的情況是二叉排序樹為 樹的時(shí)候。18. 在哈希查找中，哈希表是指。19. 在哈希查找中，哈希函數(shù)構(gòu)造方法中的直接定址法

15、是指取 或作為哈希地址。20. 在哈希查找中，哈希函數(shù)構(gòu)造方法中的平方取中法是指取 作為哈希地址二、簡(jiǎn)答題1. 關(guān)鍵字集合為47, 7, 29，11，16, 92，22，8，3，13，地址區(qū)間為 010, 構(gòu)造合理的哈希函數(shù)，用線性探測(cè)再散列法處理沖突，畫出哈希表并求出平均查 找長(zhǎng)度 ASL。（2+4+2=8 分）哈希函數(shù)：哈希表:地址012345678910關(guān)鍵字平均查找長(zhǎng)度ASL=2. 假設(shè)哈希表的地址空間為0-6,哈希函數(shù)為H（k） = k%7,采用線性探測(cè)法處理沖 突，如將關(guān)鍵字序列（26,72,35,8,18,60依次存放到哈希表中，（1）根據(jù)哈希函數(shù)計(jì) 算每個(gè)關(guān)鍵字對(duì)應(yīng)的哈希地址并

16、畫出生成的哈希表；（2）計(jì)算出在此哈希表上進(jìn)行查找的平均查找長(zhǎng)度。（6+2=8分）地址表關(guān)鍵字26723581860地址哈希表地址0123456關(guān)鍵字3. 哈希表的地址空間為06,哈希函數(shù)為H（k） = k%7,采用二次探測(cè)再散列法處理 沖突，如將關(guān)鍵字序列（9,11,8,13,15,10依次存放到哈希表中，填寫下面的地址表 和生成的哈希表，并計(jì)算出在此哈希表上進(jìn)行查找的平均查找長(zhǎng)度。（2+4+2=8分）地址表關(guān)鍵字值9118131510哈希地址哈希表地址0123456關(guān)鍵字 值平均查找長(zhǎng)度ASL=4. 設(shè)有關(guān)鍵字序列（13, 10, 6，14, 21，17），試用除留取余法構(gòu)造哈希函數(shù), 用

17、線性探查再散列將其散列到地址空間 0-6之中，請(qǐng)問： 除留取余法中除數(shù)p如何選取，可以減少?zèng)_突？你因此用除留取余法構(gòu)造的哈 希函數(shù)為？ 畫出對(duì)應(yīng)的地址表和哈希表。 求出等概率條件下的平均查找長(zhǎng)度（2+4+2=8分）地址表：關(guān)鍵址哈希表:地址0123456關(guān)鍵字5. 設(shè)有關(guān)鍵字序列（7，8，9，16，15，18），采用除留取余法構(gòu)造哈希函數(shù) hash（key）=key%7；用鏈地址法處理沖突，將其散列到地址空間 06之中，（1） 求出其對(duì)應(yīng)哈希地址；（2）畫出對(duì)應(yīng)的哈希表；（3 ）求出其平均查找長(zhǎng)度。（1+5+2=8分）6. 哈希表的地址空間為09,哈希函數(shù)為H（k）

18、= k%7,采用線性探測(cè)再散列法處理 沖突，如將關(guān)鍵字序列（9,11,16,10,15,12,24,20,18依次存放到哈希表中，填寫下 面的地址表和生成的哈希表，并計(jì)算出在此哈希表上進(jìn)行查找的平均查找長(zhǎng)度。（2+4+2=8 分）地址表關(guān)鍵字值91116101512242018哈希地址哈希表地址0123456789關(guān)鍵字值平均查找長(zhǎng)度ASL=7. 已知一個(gè)哈希表如下所示，其地址空間為0-10，哈希函數(shù)為Hash（k）=k%11,沖突處理方法為線性探測(cè)再散列。地址012345678910關(guān)鍵字值66457832544862301821回答以下問題：（1） 在此哈希表上，在哪些地址上發(fā)生了沖突？（

19、2分）（2）在查找元素32、54和21時(shí)各需要進(jìn)行多少次比較？ （ 3分）（3） 計(jì)算等概率條件下查找成功時(shí)的平均查找長(zhǎng)度。（3分）8. 假設(shè)哈希表的地址空間為0-6,哈希函數(shù)為H（k） = k%7,采用二次探測(cè)再散列法 處理沖突，如將關(guān)鍵字序列（26,72,35,8,18,60依次存放到哈希表中， 根據(jù)哈希 函數(shù)計(jì)算每個(gè)關(guān)鍵字對(duì)應(yīng)的哈希地址并畫出生成的哈希表；（2）計(jì)算出在此哈希表上進(jìn)行查找的平均查找長(zhǎng)度。（6+2=8分）地址表關(guān)鍵字26723581860地址哈希表地址0123456關(guān)鍵字ASL=9. 假設(shè)哈希表的地址空間為0-6，哈希函數(shù)為H(k) = k%7,采用鏈地址法處理沖突， 如將

20、關(guān)鍵字序列(26,72,35,8,18,60依次存放到哈希表中，(1)根據(jù)哈希函數(shù)計(jì)算每 個(gè)關(guān)鍵字對(duì)應(yīng)的哈希地址并畫出生成的哈希表；(2)計(jì)算出在此哈希表上進(jìn)行查找的平均查找長(zhǎng)度。(6+2=8分)地址表關(guān)鍵字26723581860地址10. 已知一個(gè)哈希表如下所示，其地址空間為 0-10,哈希函數(shù)為Hash(k)=k%11， 沖突處理方法為二次探測(cè)再散列。地址012345678910關(guān)鍵字值66457854 :48 :1862303221回答以下問題：(1) 在此哈希表上，在哪些地址上發(fā)生了沖突？(2分)(2) 在查找元素32、54和21時(shí)各需要進(jìn)行多少次比較？ ( 3分)(3) 計(jì)算等概率條

21、件下查找成功時(shí)的平均查找長(zhǎng)度。(3分)11. 已知一個(gè)哈希表如下所示，其地址空間為 0-10，哈希函數(shù)為Hash(k)=k%11, 沖突處理方法為二次探測(cè)再散列。012345678910回答以下問題:(1) 在此哈希表上，在哪些地址上發(fā)生了沖突？(2分)(2) 在查找元素32、54和21時(shí)各需要進(jìn)行多少次比較？ ( 3 分)(3) 計(jì)算等概率條件下查找成功時(shí)的平均查找長(zhǎng)度。(3分)12. 關(guān)鍵字集合為47, 7, 29, 11, 16, 92, 22, 8, 3, 13，地址區(qū)間為 010,構(gòu)造合理的哈希函數(shù)，用二次探測(cè)再散列法處理沖突，畫出哈希表并求出平均查 找長(zhǎng)度 ASL。(2+4+2=8

22、 分)哈希函數(shù)：哈希表:地址012345678910關(guān)鍵字平均查找長(zhǎng)度ASL=13. 關(guān)鍵字集合為47 , 7, 29, 11, 16, 92, 22, 8, 3, 13，地址區(qū)間為 010,構(gòu)造合理的哈希函數(shù)，用鏈地址法處理沖突，畫出哈希表并求出平均查找長(zhǎng)度ASL。(2+4+2=8 分)14. 假設(shè)哈希表的地址空間為0-12,哈希函數(shù)為H(k) = k%13,采用線性探測(cè)法處 理沖突，如將關(guān)鍵字序列(50,26,45,72,62,35,28,18,60,71,90,67依次存放到哈希表 中，(1)根據(jù)哈希函數(shù)計(jì)算每個(gè)關(guān)鍵字對(duì)應(yīng)的哈希地址并畫出生成的哈希表；(2)15. 假設(shè)哈希表的地址空間為

23、0-12,哈希函數(shù)為H(k) = k%13,采用二次探測(cè)法處 理沖突，如將關(guān)鍵字序列(50,26,45,72,62,35,28,18,60,71,90,67依次存放到哈希表中，(1)根據(jù)哈希函數(shù)計(jì)算每個(gè)關(guān)鍵字對(duì)應(yīng)的哈希地址并畫出生成的哈希表；(2)計(jì)算出在此哈希表上進(jìn)行查找的平均查找長(zhǎng)度。(6+2=8分)16. 假設(shè)哈希表的地址空間為0-12,哈希函數(shù)為H(k) = k%13,采用鏈地址法處理 沖突，如將關(guān)鍵字序列(50,26,45,72,62,35,28,18,60,71,90,67依次存放到哈希表中，(1)根據(jù)哈希函數(shù)計(jì)算每個(gè)關(guān)鍵字對(duì)應(yīng)的哈希地址并畫出生成的哈希表；(2)計(jì)算出在此哈希表上

24、進(jìn)行查找的平均查找長(zhǎng)度。(6+2=8分)17. 哈希表的地址空間為09,哈希函數(shù)為H(k) = k%7,采用二次探測(cè)再散列法處 理沖突，如將關(guān)鍵字序列(9,11,16,10,15,12,24,20,18依次存放到哈希表中，填寫 下面的地址表和生成的哈希表，并計(jì)算出在此哈希表上進(jìn)行查找的平均查找長(zhǎng) 度。(2+4+2=8 分)地址表關(guān)鍵字值91116101512242018哈希地址哈希表地址0123456789關(guān)鍵字值平均查找長(zhǎng)度ASL=18. 哈希表的地址空間為09,哈希函數(shù)為H(k) = k%7,采用鏈地址法處理沖突，如將關(guān)鍵字序列(9,11,16,10,15,12,24,20,18依次存放到

25、哈希表中(1)填寫下面的地址表；(2)畫出生成的哈希表；(3)計(jì)算出在此哈希表上進(jìn)行查找的平均查找長(zhǎng)度。(2+4+2=8 分)地址表關(guān)鍵字值91116101512242018哈希地址19哈希表的地址空間為05,哈希函數(shù)為H(k) = k%5,分別采用線性探測(cè)再散列 法和二次探測(cè)再散列法處理沖突，如將關(guān)鍵字序列 (9,11,16,14,15)依次存放到哈 希表中，分別畫出兩種沖突處理方法生成的哈希表， 并比較在兩個(gè)不同哈希表上 進(jìn)行查找的平均查找長(zhǎng)度。(6+2=8分)20.哈希表的地址空間為05,哈希函數(shù)為H(k) = k%5,分別采用線性探測(cè)再散列 法和鏈地址法處理沖突，如將關(guān)鍵字序列(9,1

26、1,16,14,15)依次存放到哈希表中，分別畫出兩種沖突處理方法生成的哈希表， 并比較在兩個(gè)不同哈希表上進(jìn)行查找 的平均查找長(zhǎng)度。(6+2=8分)二、算法設(shè)計(jì)題1設(shè)計(jì)一算法實(shí)現(xiàn)：在降序排列的整型順序線性表上采用二分查找方法查找指 定關(guān)鍵字值的元素。2設(shè)計(jì)一算法實(shí)現(xiàn)：在升序排列的整型順序表上采用順序查找方法查找指定值 的元素。3假設(shè)學(xué)生信息類型定義如下，設(shè)計(jì)算法實(shí)現(xiàn)在順序存儲(chǔ)的學(xué)生信息表上查找 并輸出所有成績(jī)高于90分的學(xué)生信息，函數(shù)返回值為滿足條件的學(xué)生人數(shù)。typedef structIo ng num;char n ame20;float score;STUDENT;第九章排序一、填空題

27、1在直接插入、冒泡、快速排序和簡(jiǎn)單選擇排序方法中，具有穩(wěn)定性的排序方 法有。2每次從無序表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做排序。3. 排序算法的穩(wěn)定性是指4. 在冒泡、快速、直接插入三種排序方法中，排序的趟數(shù)與數(shù)據(jù)表的初始排列順 序無關(guān)的是排序方法。5.對(duì)7個(gè)元素構(gòu)成的線性表進(jìn)行快速排序時(shí)， 分。在最好情況下共需進(jìn)行一次劃6.對(duì)7個(gè)元素構(gòu)成的線性表進(jìn)行快速排序時(shí)，在最差情況卜共需進(jìn)行次劃分。7.對(duì)7個(gè)元素構(gòu)成的線性表進(jìn)行快速排序時(shí)，在最好情況下共需進(jìn)行次比較?？焖俸秃?jiǎn)單選擇排序方法中應(yīng)選8.當(dāng)數(shù)據(jù)表初態(tài)基本有序的情況下，在冒泡、擇排序方法，從而使得排序的趟數(shù)

28、最少。9 對(duì)于n個(gè)元素構(gòu)成的線性表，采用簡(jiǎn)單選擇排序共需進(jìn)行 趟排序。10.對(duì)于n個(gè)元素構(gòu)成的降序順序線性表，采用快速排序按照關(guān)鍵字升序排列時(shí) 共需進(jìn)行次劃分。11對(duì)于n個(gè)元素構(gòu)成的降序順序線性表，采用冒泡排序按照關(guān)鍵字升序排列時(shí)共需進(jìn)行趟排序。12 .在直接插入、冒泡、快速排序方法中，不具有穩(wěn)定性的排序方法是。13. 在直接插入、快速排序和簡(jiǎn)單選擇排序方法中，不具有穩(wěn)定性的排序方法有。14. 在直接插入、冒泡、快速排序和簡(jiǎn)單選擇排序方法中，平均時(shí)間復(fù)雜度最低的排序方法是。15.16.17.18.19.20二、簡(jiǎn)答題1對(duì)于一組給定的關(guān)鍵字 53,87,12,61,35,48,20,42,16,

29、93，寫出用冒泡排序法進(jìn) 行升序排列的各趟結(jié)果。（每趟排序時(shí)產(chǎn)生該趟的最小數(shù)升到表上端的對(duì)應(yīng)位 置）（ 8 分）2對(duì)于一組給定的關(guān)鍵字 53,87,12,61,35,48,20,42,16,93，寫出用冒泡排序法進(jìn) 行升序排列的各趟結(jié)果。（每趟排序時(shí)產(chǎn)生該趟的最大數(shù)沉到表下端的對(duì)應(yīng)位 置）（ 8 分）3對(duì)于一組給定的關(guān)鍵字 53,87,12,61,35,48,20,42，寫出用快速排序法進(jìn)行升 序排列的各趟劃分結(jié)果，對(duì)于第一趟劃分要求寫出劃分的具體過程。（8 分）4對(duì)于一組給定的關(guān)鍵字 53,87,12,61,35,48，寫出分別用直接插入法和簡(jiǎn)單選 擇法進(jìn)行升序排列的各趟結(jié)果。 （8 分）5

30、對(duì)于一組給定的關(guān)鍵字 53,87,12,61,35,48,20,42,16,93，寫出用快速排序法進(jìn) 行升序排列的各趟劃分結(jié)果。（8 分）6對(duì)于一組給定的關(guān)鍵字 53,87,12,61,35,48,20,42,16,93，寫出用快速排序法進(jìn) 行降序排列的各趟劃分結(jié)果。（8 分）7對(duì)于一組給定的關(guān)鍵字 53,87,12,61,35,48，寫出分別用冒泡排序法和簡(jiǎn)單選擇法進(jìn)行升序排列的各趟結(jié)果。 （8 分）8對(duì)于一組給定的關(guān)鍵字 53,87,12,61,35,48，寫出分別用冒泡排序法和直接插入排序法進(jìn)行升序排列的各趟結(jié)果。 （ 8 分）9對(duì)于一組給定的關(guān)鍵字 60,50,40,30,20,10，

31、寫出分別用冒泡排序法和簡(jiǎn)單選擇法進(jìn)行升序排列的各趟結(jié)果。 （8 分）10對(duì)于一組給定的關(guān)鍵字 60,50,40,30,20,10 ，寫出分別用冒泡排序法和直接 插入排序法進(jìn)行升序排列的各趟結(jié)果。 （ 8 分）11對(duì)于一組給定的關(guān)鍵字 53,87,12,61,35,48 ，寫出分別用冒泡排序法和直接 插入排序法進(jìn)行降序排列的各趟結(jié)果。 （8 分）12對(duì)于一組給定的關(guān)鍵字 53,87,12,61,35,48 ，寫出分別用冒泡排序法和簡(jiǎn)單 選擇法進(jìn)行降序排列的各趟結(jié)果。 （8 分）13對(duì)于一組給定的關(guān)鍵字序列 45,19,81,58,12,33,20,65,77,28，寫出用簡(jiǎn)單選 擇排序法進(jìn)行降序

32、排列的各趟結(jié)果。 （8 分）14對(duì)于一組給定的關(guān)鍵字序列 45,19,81,58,12,33,20,65,77,28，寫出用直接插入排序法進(jìn)行降序排列的各趟結(jié)果。 （ 8 分）15對(duì)于一組給定的關(guān)鍵字序列 45,19,81,58,12,33,20,65,77,28，寫出用冒泡排序法進(jìn)行降序排列的各趟結(jié)果。 （ 8 分）16對(duì)于一組給定的關(guān)鍵字序列 45,19,81,58,12 ，分別寫出用直接插入排序法和 快速排序法進(jìn)行降序排列的各趟結(jié)果。 （8 分）17對(duì)于一組給定的關(guān)鍵字序列 58,12,33,20,65,77 ，分別寫出用冒泡排序法和 快速排序法進(jìn)行升序排列的各趟結(jié)果。 （ 8 分）18

33、對(duì)于一組給定的關(guān)鍵字序列 58,12,33,20,65,77 ，分別寫出用冒泡排序法和直接插入排序法進(jìn)行升序排列的各趟結(jié)果。 （8 分）19對(duì)于一組給定的關(guān)鍵字序列 45,19,81,58,12,33,20,65，寫出用快速排序法進(jìn)行升序排列的各趟劃分結(jié)果，對(duì)于第一趟劃分要求寫出劃分的具體過程。 （8 分） 20.對(duì)于一組給定的關(guān)鍵字序列58,12,33,20,65,77，分別寫出用冒泡排序法和 簡(jiǎn)單選擇排序法進(jìn)行升序排列的各趟結(jié)果。（8分）三、算法設(shè)計(jì)題1設(shè)計(jì)一算法實(shí)現(xiàn)，對(duì)一個(gè)整型順序表中的元素按降序（從大到?。┑捻樞蚺?列，要求排序采用冒泡排序方法實(shí)現(xiàn)。（10分）2設(shè)計(jì)一算法實(shí)現(xiàn)，對(duì)一個(gè)整

34、型順序表中的元素按升序（從小到大）的順序排列。要求（1）排序采用冒泡排序方法實(shí)現(xiàn)；（2）每趟冒泡產(chǎn)生一個(gè)最大數(shù)沉到 待排序線性表的最下端。（10分）3設(shè)計(jì)一算法實(shí)現(xiàn)，對(duì)一個(gè)整型順序表中的元素按降序（從大到小）的順序排列，要求排序采用直接插入排序方法實(shí)現(xiàn)。（10分）4設(shè)計(jì)一算法實(shí)現(xiàn)，對(duì)一個(gè)整型順序表中的元素按降序（從大到?。┑捻樞蚺帕校笈判虿捎煤?jiǎn)單選擇排序方法實(shí)現(xiàn)。（10分）第十章數(shù)組一、填空題1設(shè)二維數(shù)組int M44，每個(gè)元素（整數(shù)）占2個(gè)存儲(chǔ)單元，元素按行優(yōu)先的順 序存儲(chǔ)，數(shù)組的起始地址為200,元素M11的地址是。2 設(shè)二維數(shù)組int M44，每個(gè)元素（整數(shù)）占2個(gè)存儲(chǔ)單元，元素按行

35、優(yōu)先的順序存儲(chǔ)，數(shù)組的起始地址為100,元素M23的地址是。3 設(shè)二維數(shù)組int M44，每個(gè)元素（整數(shù)）占2個(gè)存儲(chǔ)單元，元素按列優(yōu)先的順序存儲(chǔ)，數(shù)組的起始地址為 100,元素M21的地址是。4 設(shè)二維數(shù)組int M44，每個(gè)元素（整數(shù)）占2個(gè)存儲(chǔ)單元，元素按列優(yōu)先的順序存儲(chǔ)，數(shù)組的起始地址為1000,元素M12的地址是。5. 對(duì)于多維數(shù)組總是采用儲(chǔ)結(jié)構(gòu)對(duì)其進(jìn)行存儲(chǔ)。6. 對(duì)于一個(gè)200行200列的上三角矩陣，若每個(gè)元素需占用兩個(gè)字節(jié)進(jìn)行存儲(chǔ)，采用壓縮存儲(chǔ)方法共需占用 字節(jié)。7. 對(duì)于一個(gè)1000行1000列的上三角矩陣，若每個(gè)元素需占用兩個(gè)字節(jié)進(jìn)行存儲(chǔ)，采用壓縮存儲(chǔ)方法比壓縮前共可節(jié)約 字節(jié)。8. 對(duì)于一個(gè)100行100列的下三角矩陣，若每個(gè)元素需占用兩個(gè)字節(jié)進(jìn)行存儲(chǔ)，采用壓縮存儲(chǔ)方法共需占用字節(jié)。9. 對(duì)于一個(gè)100行100列的下三角矩陣，若每個(gè)元素需占用兩個(gè)字節(jié)進(jìn)行存儲(chǔ)，采用壓縮存儲(chǔ)方法比壓縮前共可節(jié)約 字節(jié)