實(shí)習(xí)四等多個(gè)文件2015總復(fù)習(xí)

1數(shù)據(jù)結(jié)構(gòu)2015年秋季授課教師：張劍波授課班級(jí)：111141-2班2課程總復(fù)習(xí)

考試安排各部分比重分布各章重要知識(shí)點(diǎn)題型3考試安排考試時(shí)間：2015年12月20日，19:00-21:00考試地點(diǎn)：教一樓204、206、2074考前答疑安排

安排在數(shù)據(jù)結(jié)構(gòu)專業(yè)實(shí)習(xí)的時(shí)間段2015年12月17周四下午時(shí)間：2:00—5:45地點(diǎn)：信息樓805可以增加其他答疑時(shí)間（學(xué)委聯(lián)系）5課程各部分內(nèi)容比重分布內(nèi)容比例涵蓋章節(jié)時(shí)間復(fù)雜度、線性表±15%第1、2章棧和隊(duì)列±15%第3章數(shù)組和矩陣±10%第4章二叉樹、堆、Huffman±20%第5章散列、字典±5%第6章圖±20%第8章搜索結(jié)構(gòu)及排序算法±15%第7、9章6考試題型及大致分值分布大致題型大致分值一、單選題30分15*2二、解答題40——50分,6題三、算法分析與設(shè)計(jì)20——30分，3題7成績?cè)u(píng)定考勤+上機(jī)實(shí)習(xí)期末考試30-40%60-70%8重要知識(shí)點(diǎn)回顧9Chapter1程序性能-重要知識(shí)點(diǎn)本章重要知識(shí)點(diǎn)：算法的性能分析與度量程序（算法）的時(shí)間復(fù)雜性操作計(jì)數(shù)：識(shí)別關(guān)鍵操作10Chapter1程序性能-重要復(fù)習(xí)題本章重要復(fù)習(xí)題P381.10P391.12、1.1311示例計(jì)算機(jī)執(zhí)行下面的語句時(shí)，語句s的執(zhí)行次數(shù)為

。

for(i=1;i<n-1;i++)for(j=1;j<=i;j++)s;12Chapter2線性表-重要知識(shí)點(diǎn)本章重要知識(shí)點(diǎn)什么是線性結(jié)構(gòu)公式化描述與鏈表描述的含義線性表的公式化描述——順序表特性：操作：插入、刪除、搜索線性表的鏈表描述——鏈表（重點(diǎn)）單鏈表雙向鏈表、循環(huán)鏈表操作：插入、刪除、搜索、合并、拆分、逆置等13

Chapter2線性表本章重要算法（程序）順序表類：P46-47順序表的基本操作：P47-49，reSize單鏈表類：P60-61單鏈表的基本操作：P57-58，P61-66循環(huán)鏈表類：P67-68，約瑟夫環(huán)問題雙向鏈表類：P70雙向鏈表的基本操作：P71-7314Chapter2線性表1、順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的比較與區(qū)別2、區(qū)別帶表頭節(jié)點(diǎn)和不帶表頭節(jié)點(diǎn)的鏈表結(jié)構(gòu)；為了避免把空鏈表作為特殊情況處理使用頭節(jié)點(diǎn)后，每個(gè)鏈表至少包含一個(gè)節(jié)點(diǎn)（頭節(jié)點(diǎn)）3、各種鏈表結(jié)構(gòu)的區(qū)別4、鏈表合并、拆分、逆置等算法15Chapter2線性表-重要復(fù)習(xí)題本章重要復(fù)習(xí)題P832.2P842.4線性表的逆置：2.62.17P862.15、2.2216示例在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針的操作為（）。A．p->llink->rlink=p->rlink;p->rlink->llink=p->llink;B．p->llink=p->llink->llink;p->llink->rlink=p;C．p->rlink->llink=p;p->rlink=p->rlink->rlinkD．p->rlink=p->llink->llink;p->llink=p->rlink->rlink;A17Chapter3棧和隊(duì)列-重要知識(shí)點(diǎn)

棧重要知識(shí)點(diǎn)棧結(jié)構(gòu)的特性：LIFO棧的公式化描述——順序棧（重點(diǎn)）棧的鏈?zhǔn)矫枋觥湕Ｃ枋霾僮鳎喝霔?、出棧、取棧頂元素、?？?、棧滿等棧的應(yīng)用括號(hào)匹配表達(dá)式求值棧與遞歸：遞歸工作棧18Chapter3棧和隊(duì)列-重要算法

棧重要算法順序棧定義及操作：P89-91鏈棧定義及操作：P93-94括號(hào)匹配算法：P95表達(dá)式求值：P95-100中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式利用后綴表達(dá)式計(jì)算值棧與遞歸：P105-109用棧實(shí)現(xiàn)遞歸轉(zhuǎn)為非遞歸用迭代法實(shí)現(xiàn)遞歸19Chapter3棧和隊(duì)列-重要知識(shí)點(diǎn)

隊(duì)列重要知識(shí)點(diǎn)隊(duì)列結(jié)構(gòu)的特性：FIFO隊(duì)列的公式化描述——循環(huán)隊(duì)列（重點(diǎn)）隊(duì)列的鏈?zhǔn)矫枋觥滉?duì)列描述操作：入隊(duì)列、出隊(duì)列、取隊(duì)頭元素、隊(duì)空、隊(duì)滿等隊(duì)列的應(yīng)用：楊輝三角優(yōu)先隊(duì)列的概念20Chapter3棧和隊(duì)列-重要算法隊(duì)列重要算法循環(huán)隊(duì)列及操作：P116-117鏈隊(duì)列及操作：118-119楊輝三角：P121優(yōu)先隊(duì)列的存儲(chǔ)與表示：P124-12621Chapter3棧和隊(duì)列-重要復(fù)習(xí)題本章重要復(fù)習(xí)題P1323.7、3.16P1333.22，rear和length22示例1、用I表示入棧操作，O表示出棧操作，若元素入棧順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的I和O操作串為（）。

A．IIOOIIOOB．IOIOIIOOC．IOIIOIOOD．IOIIOOIOC2、算術(shù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（）。A．a(chǎn)b+cde/*B．a(chǎn)bcde/+*+C．a(chǎn)bcde/*++D．a(chǎn)bcde*/++B23示例若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？（）A．1和5B．2和4C．4和2D．5和1Brear=(rear+1)%MaxSize;front=(front+1)%MaxSize;24Chapter4數(shù)組和矩陣（串不考）本章重要知識(shí)點(diǎn)二維數(shù)組的一維存儲(chǔ)（行優(yōu)先、列優(yōu)先）計(jì)算元素位置特殊矩陣的壓縮存儲(chǔ)：P138-141對(duì)角、三對(duì)角（帶狀）、上（下）三角、對(duì)陣矩陣注意下標(biāo)的起止值行、列、對(duì)角線優(yōu)先映射公式稀疏矩陣的壓縮存儲(chǔ)三元組順序表轉(zhuǎn)置操作（P145）25Chapter4數(shù)組和矩陣-重要復(fù)習(xí)題本章重要復(fù)習(xí)題P1834.1、4.226示例數(shù)組A[0..5,0..6]的每個(gè)元素占5個(gè)字節(jié)，將其按列優(yōu)先次序存儲(chǔ)在起始地址為1000的內(nèi)存單元中，則元素A[5，5]的地址是（）。A．1175B．1180C．1205D．1210A設(shè)有二維數(shù)組a[m][n]行優(yōu)先：LOC(i,j)=LOC(0,0)+(i*n+j)*l列優(yōu)先：LOC(i,j)=LOC(0,0)+(j*m+i)*l

27Chapter5二叉樹和樹、Huffman、堆-重要知識(shí)點(diǎn)本章重要知識(shí)點(diǎn)非線性結(jié)構(gòu)樹結(jié)構(gòu)的特性二叉樹、滿二叉樹、完全二叉樹的定義二叉樹的特性及證明方法（注意特性P190）二叉樹的順序存儲(chǔ)二叉樹的鏈?zhǔn)酱鎯?chǔ)——二叉鏈表二叉樹的遍歷及遍歷的應(yīng)用樹的二叉鏈表表示形式28Chapter5二叉樹和樹、Huffman、堆-重要知識(shí)點(diǎn)堆堆的定義、判斷堆的、初始化及插入、刪除算法堆排序Huffman樹及Huffman算法Huffman樹的定義及性質(zhì)帶權(quán)路徑長度（WPL）Huffman算法Huffman編碼：P244-24529Chapter5二叉樹和樹、Huffman、堆-重要程序本章重要程序二叉鏈表類：P194-195二叉樹的操作：P196二叉樹遍歷的應(yīng)用(高度、交換）：P198-207前序和中序或中序和后序唯一確定一棵二叉樹表達(dá)式二叉樹：前綴、中綴、后綴樹的二叉樹描述左孩子-右兄弟表示法：P222轉(zhuǎn)換方法30Chapter5二叉樹和樹、Huffman、堆-重要程序最?。ù螅┒杨悾篜236最小（大）堆的插入、刪除及復(fù)雜度分析：P238-239初始化非空最大堆：P237堆排序及性能分析Huffman樹的建立：P242-24331Chapter5二叉樹和樹、Huffman、堆-重要復(fù)習(xí)題本章重要復(fù)習(xí)題性質(zhì)：P2465.6、5.7、5.9堆：P2475.16樹與二叉樹：P2485.17、5.18Huffman：P2485.19、5.20應(yīng)用：P2485.235.26321、一棵高度為h的滿二叉樹共有n個(gè)結(jié)點(diǎn)，其中有m個(gè)葉子結(jié)點(diǎn)，則有

成立。A、n=h+mB、h+m=2nC、m=h-1D、n=2m-1

D示例332、已知一棵完全二叉樹中共有768結(jié)點(diǎn)，則該樹中共有_____個(gè)葉子結(jié)點(diǎn)。384

3、已知一棵完全二叉樹中共有767結(jié)點(diǎn)，則該樹中共有_____個(gè)葉子結(jié)點(diǎn)。（軟考真題）384完全二叉樹中度為1的節(jié)點(diǎn)數(shù)只有兩種可能：要么為0個(gè)（奇數(shù)個(gè)結(jié)點(diǎn)），要么為1個(gè)（偶數(shù)個(gè)結(jié)點(diǎn)）。34

4、設(shè)節(jié)點(diǎn)x和y是二叉樹中任意兩個(gè)節(jié)點(diǎn)，在該二叉樹的前序遍歷序列中x在y之前，而在后序遍歷序列中x在y之后，則x和y的關(guān)系是：A、x是y的左兄弟B、x是y的右兄弟C、x是y的祖先D、x是y的后裔C355、已知某二叉樹的中序遍歷序列是dgbaechf，后序遍歷序列是gdbehfca，則其前序遍歷序列是（）。

A．a(chǎn)bdgcefhB．a(chǎn)gdbecfh C．a(chǎn)bdgechfD．a(chǎn)dbgcefh6、用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHI，寫出中序遍歷該二叉樹時(shí)訪問節(jié)點(diǎn)的順序

。AHDIBEAFCG36堆及Huffman的示例1、初始關(guān)鍵碼序列為{E，D，X，K，H，L，M，C，P}，用篩選法所建的最大堆得到的序列是

。2、給定14個(gè)字母，假設(shè)它們的權(quán)值都相等。采用Huffman編碼，則每個(gè)字母的平均編碼長度是

。XPMKHLECD54/14（或3.857）373、下列序列不是堆的是

。A、（100，85，98，77，80，60，82，40，20，10，66）B、（100，98，85，82，80，77，66，60，40，20，10）C、（10，20，40，60，66，77，80，82，85，98，100）D、（100，85，40，77，80，60，66，98，82，10，20）D38

4、有組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法建立的初始最大堆為：A、79，46，56，38，40，80B、84，79，56，38，40，46C、84，79，56，46，40，38D、84，56，79，40，46，38B39

5、在數(shù)據(jù)壓縮編碼應(yīng)用中，Huffman算法可以用來構(gòu)造具有

（1）的二叉樹，這是一種采用了（2）算法的算法。（1）A、前綴碼B、最優(yōu)前綴碼C、后綴碼D、最優(yōu)后綴碼（2）A、貪心B、分治C、遞推D、回溯解答：（1）B（2）A406、假設(shè)用于通信的電文僅由a，b，c，d，e，f，g，h，8個(gè)字母組成，各字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。（1）試為這8個(gè)字母設(shè)計(jì)Huffman編碼（需畫出相應(yīng)的Huffman樹）。（2）使用0-7的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。（提示：試從兩種編碼的帶權(quán)路徑長度上進(jìn)行比較說明）WPLHF=2.61，WPLEQ=3提高通信信道的利用率，提高報(bào)文發(fā)送速度或/和節(jié)省存儲(chǔ)空間。41Chapter6集合、字典散列-重要知識(shí)點(diǎn)

本章重要知識(shí)點(diǎn)字典結(jié)構(gòu)的特點(diǎn)散列（重點(diǎn)）散列函數(shù)-除留余數(shù)法：f(k)=k%D什么是沖突？沖突解決方案：開散列散列表搜索：P284-287Hi（k）=（H（k）+di）modm（i=1,2,...k（k≤m-1））42Chapter6集合、字典散列-重要復(fù)習(xí)題本章重要復(fù)習(xí)題P2956.9（1）43示例設(shè)有一組關(guān)鍵碼{19，01，23，14，55，20，84，27，68，11，10，77}，采用散列函數(shù)H（key）=key%13，處理沖突的方法是線性探測再散列的方法（即dj+1=（dj+1）%m）若在0~18（即m=19）的散列地址空間中對(duì)該關(guān)鍵碼構(gòu)造散列表，則關(guān)鍵碼14對(duì)應(yīng)的地址是（）。

A．1B．2C．3D．14B設(shè)有8個(gè)數(shù)據(jù)元素，其關(guān)鍵字分別為{17,26,35,49,63,72,19,25}，散列表長度為10，散列函數(shù)H（Key）=Key%7。寫出采用“線性探測再散列法”解決沖突所得的散列表，并計(jì)算搜索成功、搜索不成功的平均搜索長度。4445Chapter7搜索結(jié)構(gòu)本章重要知識(shí)點(diǎn)靜態(tài)搜索結(jié)構(gòu)：順序搜索、折半搜索二叉搜索樹（BST樹）二叉搜索樹定義、特點(diǎn)在二叉搜索樹中搜索元素的算法平均搜索長度的計(jì)算:ASL二叉搜索樹的插入、刪除AVL樹定義、特點(diǎn)平衡化旋轉(zhuǎn)的方法46Chapter7搜索結(jié)構(gòu)本章重要程序有序表的折半搜索：P304-305二叉搜索樹類：P310二叉搜索樹樹的搜索、插入：P311-312二叉搜索樹的刪除：P313-314AVL樹的構(gòu)造及四種平衡化旋轉(zhuǎn)的方法P321-32547Chapter7搜索結(jié)構(gòu)-重要復(fù)習(xí)題本章重要復(fù)習(xí)題順序搜索：P3427.2（對(duì)畫判定樹不做要求）折半搜索：P3427.3BST插入與刪除：P3427.8AVL：P3437.14、7.1548示例已知有序表為（12，18，24，35，47，50，62，83，90，115，134），當(dāng)用折半搜索90時(shí)，需進(jìn)行

次搜索可確定搜索成功；搜索40時(shí)需進(jìn)行

___次搜索才能確定不成功。2，449B

1、有數(shù)據(jù){53，30，37，12，45，24，96}，從空二叉樹開始逐個(gè)插入數(shù)據(jù)來形成二叉搜索樹，若希望高度最小，則應(yīng)選擇下面哪個(gè)序列輸入

。

A、45，24，53，12，37，96，30B、37，24，12，30，53，45，96C、12，24，30，37，45，53，96D、30，24，12，37，45，96，53示例50

2、一棵二叉搜索樹，其節(jié)點(diǎn)A、B、C、D、E、F依次存放在一個(gè)起始地址為n（假定地址以字節(jié)為單位順序編號(hào)）的連續(xù)區(qū)域中，每個(gè)節(jié)點(diǎn)占4個(gè)字節(jié)：前2個(gè)字節(jié)存放節(jié)點(diǎn)值，后2個(gè)字節(jié)依次存放左指針、右指針。若該二叉搜索樹的根節(jié)點(diǎn)為E，則它的一種可能的前序遍歷為

(1)，相應(yīng)的層序遍歷為

(2)。在以上兩種遍歷的情況下，節(jié)點(diǎn)C的左指針Lc的存放地址為

(3)，Lc的內(nèi)容為

(4)。節(jié)點(diǎn)A的右指針Ra的內(nèi)容為

(5)。（1）A.EAFCBDB.EFACDBC.EABCFDD.EACBDF（2）A.EAFCBDB.EFACDBC.EABCFDD.EACBDF（3）A.n+9B.n+10C.n+12D.n+13（4）A.n+4B.n+8C.n+12D.n+16（5）A.n+4B.n+8C.n+12D.n+16解答：（1）D；（2）A；

（3）B；（4）A；（5）B513、已知一長度為12的表（Jan，F(xiàn)eb，Mar，Apr，May，June，July，Aug，Sept，Oct，Nov，Dec）。（1）依次取表中各元素構(gòu)造一棵二叉搜索樹（按照在英文字典中的先后順序比較元素值的大小）；并求其在等概率情況下搜索成功時(shí)的平均搜索長度。（2）若對(duì)表中元素進(jìn)行排序構(gòu)成有序表，求在等概率情況下對(duì)此有序表進(jìn)行折半搜索成功的平均搜索長度。（3）按表中元素順序構(gòu)造一棵AVL樹，并求其在等概率情況下搜索成功的平均搜索長度。解答：（1）42/12；（2）37/12；（3）38/1252JanFebJulyNovSeptMarJuneMayOctAprAugDec二叉搜索樹53JanFebJulyNovSeptMarJuneMayOctAprAugDec342341342434折半搜索54MarJanAprJulyNovOctJuneMaySeptAugFebDecAVL樹55Chapter8圖本章重要知識(shí)點(diǎn)圖的基本概念路徑、連通分量、生成樹圖的類型無向圖、有向圖、加權(quán)圖（網(wǎng)）每種圖的基本特性圖的表示方法及特點(diǎn)鄰接矩陣、鄰接鏈表圖的遍歷及應(yīng)用DFSBFS56最小生成樹KruskalPrim最短路徑非負(fù)權(quán)值的單源點(diǎn)最短路徑Dijkstra活動(dòng)網(wǎng)絡(luò)AOV網(wǎng)絡(luò)：拓?fù)渑判?7Chapter8圖本章重要算法：圖的鄰接矩陣表示：P352-354圖的鄰接鏈表表示：P356-360DFS實(shí)現(xiàn)：P364-365BFS實(shí)現(xiàn)：P366最小生成樹

Kruskal算法：P371-373

Prim算法：P374-375最短路徑Dijkstra算法：P376-378拓?fù)渑判?AOV網(wǎng)絡(luò))：P384-38758Chapter8圖-重要復(fù)習(xí)題本章重要復(fù)習(xí)題圖的概念：P3928.1、8.2、8.3、8.4、8.6、8.7圖的遍歷：P392

8.10最小生成樹：P392

8.11最短路徑：P3958.2459

1、在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，零元素的個(gè)數(shù)為

。

A．e

B．2e

C．n2-e

D．n2-2eD示例2、設(shè)一個(gè)包含N個(gè)頂點(diǎn)、E條邊的簡單有向圖采用鄰接矩陣存儲(chǔ)結(jié)構(gòu)（矩陣元素A[i][j]等于0/1分別表示頂點(diǎn)i與頂點(diǎn)j之間有/無?。瑒t該矩陣的元素?cái)?shù)目為（1），其中非零元素?cái)?shù)目為為（2）。

A.E2B.N2C.N2-E2D.N2+E2A.NB.N+EC.ED.N-E解答：（1）B；（2）C60

3、若采用鄰接矩陣來存儲(chǔ)簡單有向圖，則某個(gè)頂點(diǎn)i的入度等于該矩陣

。A、第i行中值為1的元素個(gè)數(shù)

B、所有值為1的元素總數(shù)C、第i行及第i列中值為1的元素總個(gè)數(shù)D、第i列中值為1的元素個(gè)數(shù)D4、假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(fù)雜度是

。

A．O(n)

B．O(e)

C．O(n+e)

D．O(n*e)C615、若G是一個(gè)具有36條邊的非連通無向圖（不含自回路和多重邊），則圖G至少有

個(gè)頂點(diǎn)。A、11B、10C、9D、8B有n個(gè)頂點(diǎn)的無向圖至多有n(n-1)/2條邊。6、無向圖G=(V,E)，其中：V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（）。A．a(chǎn),b,e,c,d,fB．a(chǎn),c,f,e,b,dC．a(chǎn),e,b,c,f,dD．a(chǎn),e,d,f,c,b

D627、已知帶權(quán)的無向圖G如左圖所示（1）畫出G的鄰接表結(jié)構(gòu)（要求：頂點(diǎn)的各鄰接邊的鏈接順序按照頂點(diǎn)序號(hào)由小到大的順序鏈接）；（2）基于上述鄰接表結(jié)構(gòu)，從頂點(diǎn)A出發(fā)，分別寫出按深度優(yōu)先和寬度優(yōu)先遍歷圖G的頂點(diǎn)序列。12AB720152430108CED63hA[1]B[2]C[3]D[4]E[5]2123711241017210dataweightlink520∧515∧48524∧38530∧120215324430∧深度優(yōu)先遍歷序列：ABDCE寬度優(yōu)先遍歷序列：ABCED12AB720152430108CED641、已知帶權(quán)的無向圖G如左圖所示（1）畫出G的鄰接表結(jié)構(gòu)（要求：頂點(diǎn)的各鄰接邊的鏈接順序按照頂點(diǎn)序號(hào)由小到大的順序鏈接）；（2）基于上述鄰接表結(jié)構(gòu)，從頂點(diǎn)A出發(fā)，分別寫出按深度優(yōu)先和寬度優(yōu)先遍歷圖G的頂點(diǎn)序列。（3）以VA為出發(fā)點(diǎn)，按Prim算法和Kruskal算法分別求G的最小生成樹；12AB720152430108CED圖的應(yīng)用示例652、對(duì)如下有向圖用Dijkstra算法，求V0到各頂點(diǎn)的最短距離和路線，要求填寫過程：66V0V1<01>5V2<02>1010V3<03><023><043>------504040V4<04>202020V5<05><045>5050502567Chapter9排序本章重要知識(shí)點(diǎn)直接插入排序折半直接插入排序希爾排序冒泡排序快速排序堆排序歸并排序68Chapter9排序-重要復(fù)習(xí)題本章重要復(fù)習(xí)題排序練習(xí)：P4409.2堆排序：P4419.11冒泡的改進(jìn)：P4419.1769示例1、在文件“局部有序”或文件長度較小的情況下，最佳的內(nèi)部排序方法是（）A、插入排序B、堆排序C、歸并排序D、快速排序A最不合適的是？702、給出一組關(guān)鍵碼K={12，2，16，30，8，28，4，10，20，6，18}，按關(guān)鍵字從小到大排序：（1）寫出歸并第一趟結(jié)束時(shí)的序列；（2）寫出快速排序第一趟結(jié)束時(shí)的序列（選第一個(gè)數(shù)為支點(diǎn)）；71示例【荷蘭國旗問題】設(shè)有紅、白、藍(lán)三種顏色的條塊組成的條塊數(shù)組（顏色隨機(jī)排列），請(qǐng)編寫一個(gè)時(shí)間復(fù)雜度為O(n)的算法，使得這些條塊按紅、白、藍(lán)的順序排好，即排成荷蘭國旗圖案?！舅惴ㄋ枷搿坷眠x擇排序的思想。首先從序列中選擇所有的紅色條塊，依次放到序列的前面，然后再從剩余的序列中選擇所有的白色條塊，依次放到紅色條塊后面。這樣經(jīng)過兩趟選擇，時(shí)間復(fù)雜度為O(n)。設(shè)這些條塊顏色依次存放在L[0,…,n-1]中，

72各章復(fù)習(xí)示例匯總731、給定一個(gè)有n個(gè)元素的線性表。若采用順序存儲(chǔ)結(jié)構(gòu)，則在等概率前提下，向其插入一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)平均為（）。A．nB．n/2C．(n-1)/2D．(n+1)/22、已知有序表為（12，18，24，35，47，50，62，83，90，115，134），當(dāng)用折半搜索90時(shí)，需進(jìn)行

____次搜索可確定搜索成功；搜索40時(shí)需進(jìn)行

____

次搜索才能確定不成功。一、單選題、填空D2，4743、以下程序中劃線語句的執(zhí)行次數(shù)是（）。intsum(intn){intsum=0,i,j;for(i=1;i<=n;i++){p=1;for(j=1;j<=i;j++)

p*=j;

sum+=p;}returnsum;}

A．n(n+1)/2 B．n(n+1) C．n(n-1)/2 D．n(n-1)A754、計(jì)算機(jī)執(zhí)行下面的語句時(shí)，語句s的執(zhí)行次數(shù)為

。

for(i=1;i<n-1;i++)for(j=1;j<=i;j++)s;765、下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（）A．線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B．線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C．線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D．線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。B776、在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（）。A．p->llink->rlink=p->rlink;p->rlink->llink=p->llink;B．p->llink=p->llink->llink;p->llink->rlink=p;C．p->rlink->llink=p;p->rlink=p->rlink->rlinkD．p->rlink=p->llink->llink;p->llink=p->rlink->rlink;7、遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（）的數(shù)據(jù)結(jié)構(gòu)。A．隊(duì)列B．多維數(shù)組C．棧D.線性表AC788、用I表示入棧操作，O表示出棧操作，若元素入棧順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的I和O操作串為（）。

A．IIOOIIOOB．IOIOIIOOC．IOIIOIOOD．IOIIOOIO9、若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？（）A．1和5B．2和4C．4和2D．5和1CB7910、數(shù)組A[0..5,0..6]的每個(gè)元素占5個(gè)字節(jié)，將其按列優(yōu)先次序存儲(chǔ)在起始地址為1000的內(nèi)存單元中，則元素A[5，5]的地址是（）。

A．1175B．1180C．1205D．121011、算術(shù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（）。A．a(chǎn)b+cde/*B．a(chǎn)bcde/+*+C．a(chǎn)bcde/*++D．a(chǎn)bcde*/++AB8013、設(shè)有一組關(guān)鍵碼{19，01，23，14，55，20，84，27，68，11，10，77}，采用散列函數(shù)H（key）=key%13，處理沖突的方法是線性探測再散列的方法（即dj+1=（dj+1）%m）若在0~18（即m=19）的散列地址空間中對(duì)該關(guān)鍵碼構(gòu)造散列表，則關(guān)鍵碼14對(duì)應(yīng)的地址是（）。

A．1B．2C．3D．14B12、散列技術(shù)中的沖突指的是（）。A．兩個(gè)元素具有相同的序號(hào)B．兩個(gè)元素的關(guān)鍵碼不同，而其他屬性相同C．?dāng)?shù)據(jù)元素過多D．不同關(guān)鍵碼的元素對(duì)應(yīng)于相同的存儲(chǔ)地址D8114.在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，零元素的個(gè)數(shù)為

。A．e

B．2e

C．n2-e

D．n2-2eD

15.假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(fù)雜度是

。

A．O(n)

B．O(e)

C．O(n+e)

D．O(n*e)C82

16.設(shè)一個(gè)包含N個(gè)頂點(diǎn)、E條邊的簡單有向圖采用鄰接矩陣存儲(chǔ)結(jié)構(gòu)（矩陣元素A[i][j]等于0/1分別表示頂點(diǎn)i與頂點(diǎn)j之間有/無?。?，則該矩陣的元素?cái)?shù)目為（1），其中非零元素?cái)?shù)目為為（2）。

A.E2B.N2C.N2-E2D.N2+E2A.NB.N+EC.ED.N-E解答：（1）B；（2）C8317.若G是一個(gè)具有36條邊的非連通無向圖（不含自回路和多重邊），則圖G至少有

個(gè)頂點(diǎn)。A、11B、10C、9D、8有n個(gè)頂點(diǎn)的無向圖至多有n(n-1)/2條邊。84二、解答題1、設(shè)有三對(duì)角矩陣，如上圖所示，將帶狀區(qū)域中的元素ai,j(|i-j|≤1)放在一維數(shù)組B中，則（1）B的大小為多少？（2）元素ai,j在B中的位置是什么？（B的下標(biāo)從0開始計(jì)，以行優(yōu)先方式存儲(chǔ)）85參考解答（1）B的大小：3n-2（2）A[i,j]=B[2i+j-2]

862、設(shè)有以下次序出現(xiàn)的關(guān)鍵字：65，23，31，26，7，91，53，15，72，52，49，68，要求用散列（哈希）方法將它們填入有14個(gè)位置的表中。（1）對(duì)上述關(guān)鍵字構(gòu)造一個(gè)散列（哈希）函數(shù)，使得發(fā)生的沖突盡可能少；（2）用線性開型尋址方法（線性探測再散列法）解決沖突，寫出散列（哈希）函數(shù)并指出上述各關(guān)鍵字在表中的位置。87解：用除留余數(shù)法，H(k)=k%p，p=13，各元素的散列地址如下：H(65)=0，H(23)=10，H(31)=5，H(26)=0，H(7)=7，H(91)=0，H(53)=1，H(15)=2，H(72)=7，H(52)=0，H(49)=10，H(68)=3，65269153153152772682349012345678910111213參考解答88三、算法閱讀1、已知一帶表頭節(jié)點(diǎn)的單鏈表L為（5，7，0，9，4，2，8），first指針指向表頭節(jié)點(diǎn)，data為鏈表的值域，link為指針域。閱讀以下程序，回答問題。template<classType>voidChain<Type>::fun(Typemin,Typemax){ChainNode<Type>*pr=first,*p=first->link;while(p){if(p->data>min&&p->data<max){pr->link=p->link;deletep;p=pr->link;}else{pr=p;p=pr->link;}}}（1）說明該程序的功能；（2）試畫出執(zhí)行L.fun(3,7);調(diào)用后的L鏈表的邏輯示意圖。89參考解答（1）刪除單鏈表中所有大于min且小于max的元素。（2）first->7->0->9->2->8。90

（1）Fibonacci序列0,1,1,2,3,5,8,13,21,34..，其中每個(gè)元素是前兩個(gè)元素之和，可遞歸定義為：

試?yán)脳砟M計(jì)算的遞歸調(diào)用，編寫一個(gè)非遞歸實(shí)現(xiàn)的算法代碼，并給出必要的注釋。【注明】已知棧的三個(gè)運(yùn)算定義如下（可直接使用）：Push（S，x）：元素x入S棧；Pop（S，x）：S棧頂元素出棧；S_IsEmpty（S）：判斷?？眨瑃rue為空，false不為空。另外，top為棧頂指針。四、算法設(shè)計(jì)與實(shí)現(xiàn)91inti,x1,x2