軟件技術(shù)基礎(chǔ)復(fù)習(xí)

軟件技術(shù)基礎(chǔ)復(fù)習(xí)2023/2/11、頁式存儲(chǔ)中，知道邏輯地址求對應(yīng)物理地址。1.分頁存儲(chǔ)管理的基本思想

用戶程序的地址空間被劃分成若干固定大小的區(qū)域，稱為“頁”，相應(yīng)地，內(nèi)存空間分成若干個(gè)物理塊，頁和塊的大小相等?？蓪⒂脩舫绦虻娜我豁摲旁趦?nèi)存的任一塊中，實(shí)現(xiàn)了離散分配。2.

分頁存儲(chǔ)管理的地址機(jī)構(gòu)

15

1211

0

頁號(hào)P

頁內(nèi)位移量W

頁號(hào)4位，每個(gè)作業(yè)最多24=16頁，表示頁號(hào)從0000~1111（24-1），頁內(nèi)位移量的位數(shù)表示頁的大小，若頁內(nèi)位移量12位，則212=4k，頁的大小為4k，頁內(nèi)地址從000000000000~111111111111

若給定一個(gè)邏輯地址為A，頁面大小為L，則

頁號(hào)P=INT[A/L]，頁內(nèi)地址W=A

MOD

L地址結(jié)構(gòu)及頁面大小設(shè)置頁面的劃分完全是一種系統(tǒng)硬件的行為。地址結(jié)構(gòu)如下：頁內(nèi)地址頁號(hào)3112110在這個(gè)完整的32位地址結(jié)構(gòu)中，頁號(hào)占10位、頁內(nèi)偏移量（也叫頁內(nèi)地址）占12位，頁面大小為4KB。若給定某一個(gè)邏輯地址（或相對地址），通過下面式子可以得出頁號(hào)和頁內(nèi)偏移量：

頁號(hào)=邏輯地址DIV頁面大小頁內(nèi)偏移量=邏輯地址MOD頁面大小例如頁面大小為4KB的系統(tǒng)中，若邏輯地址為28024由上式求得28024div4096=6（頁號(hào)）

28024mod4096=3448（頁內(nèi)偏移量）00000000

0000

0000011011010111100028024頁號(hào)6頁內(nèi)地址3448某采用分頁存儲(chǔ)管理的系統(tǒng)中，物理地址占20位，邏輯地址中頁號(hào)占6位，頁大小為1K，問：（1）該系統(tǒng)的內(nèi)存空間大小是多少？每塊的大小是多少？（2）邏輯地址共幾位，每個(gè)作業(yè)最大長度是多少？(1)內(nèi)存空間大小為220=1M。每塊的大小為1K(2)邏輯地址16位。每個(gè)作業(yè)最大長度為64K實(shí)例：在采用頁式存儲(chǔ)管理的系統(tǒng)中，某作業(yè)J的的邏輯地址空間為4頁（每頁2048字節(jié)），且已知該作業(yè)的頁面映象表如下：試借助地址變換圖（畫出地址變換圖）求出有效邏輯地址4865所對應(yīng)的物理地址。某分頁式存儲(chǔ)管理系統(tǒng)存放了一個(gè)具有5個(gè)頁面的作業(yè)，頁面按頁號(hào)從小到大存放的塊號(hào)分別為5，10，3，6，20設(shè)每頁大小為4096字節(jié)。（1）請畫出該作業(yè)的頁表（2）每塊頁面在內(nèi)存中的起始地址（3）作業(yè)中語句MOV[10000],2345中邏輯地址10000使用哪塊頁面，在內(nèi)存的物理地址為多少？頁號(hào)塊號(hào)起始地址0520480110409602312288362457642081920邏輯地址10000對應(yīng)的頁號(hào)為10000/4096＝2，頁內(nèi)地址為10000％4096＝

1808，2號(hào)頁面對應(yīng)的塊號(hào)為3，所以邏輯地址10000對應(yīng)內(nèi)存單元地址為12288＋1808＝14096

2、P,V操作信號(hào)量機(jī)制荷蘭著名科學(xué)家，后來的計(jì)算機(jī)圖靈獎(jiǎng)獲得者，E.W.Dijkstra于1965年提出了用作進(jìn)程同步工具的信號(hào)量（semaphore）機(jī)制，這是一種卓有成效的進(jìn)程互斥同步工具，已被廣泛應(yīng)用于現(xiàn)代計(jì)算機(jī)系統(tǒng)中。信號(hào)量的思想：兩個(gè)或多個(gè)進(jìn)程可以利用彼此間收發(fā)的簡單的信號(hào)來實(shí)現(xiàn)“正確的”并發(fā)執(zhí)行，一個(gè)進(jìn)程在收到一個(gè)指定信號(hào)前，會(huì)被迫在一個(gè)確定的或者需要的地方停下來，從而保持同步或互斥。經(jīng)典的整型信號(hào)量＝》經(jīng)記錄型信號(hào)量＝》信號(hào)量集機(jī)制CPU忙等造成死鎖不易死鎖，可能導(dǎo)致資源利用率低1.整型信號(hào)量最初由Dijkstra將信號(hào)量定義為一個(gè)整型量SS是個(gè)具有非負(fù)初值的整型變量，表示該信號(hào)量的值，且S的值只能由定義在信號(hào)量上的P操作原語和V操作原語來改變；2.記錄型信號(hào)量

P（Passeren/proberen

）、V（Vrijgeren/verhogen

）是荷蘭語，分別代表“通過/測試或等待”及“釋放/增加或發(fā)信號(hào)”。信號(hào)量S值的物理含義：

當(dāng)S≥0時(shí)，表示某類可用資源的數(shù)目，或者說表示可以執(zhí)行P操作而不會(huì)被阻塞的進(jìn)程的數(shù)目；當(dāng)S＜0時(shí)，其絕對值表示信號(hào)量S的阻塞隊(duì)列中的進(jìn)程數(shù)，即系統(tǒng)中因請求該類資源而被阻塞的進(jìn)程的數(shù)目，亦即被信號(hào)燈擋住的進(jìn)程數(shù)目，這些進(jìn)程需要?jiǎng)e的進(jìn)程發(fā)出相應(yīng)的信號(hào)燈來喚醒。另外，S的值只能由P、V操作來改變。

P(S)操作和V(S)操作的物理含義：P(S)操作表示“等信號(hào)”，即測試一個(gè)要等的信號(hào)是否到達(dá)；V(S)操作表示“發(fā)信號(hào)”。這個(gè)信號(hào)在實(shí)現(xiàn)同步時(shí)就是“合作者的伙伴進(jìn)程已完成前趨任務(wù)”，在實(shí)現(xiàn)互斥時(shí)就是“臨界資源可用”。另外，在互斥問題中，每執(zhí)行一次P(S)操作的含義，也可理解為進(jìn)程請求一個(gè)單位的S類資源；每執(zhí)行一次V(S)操作的含義，也可理解為進(jìn)程釋放一個(gè)單位的S類資源。信號(hào)量應(yīng)用1.利用P、V操作原語實(shí)現(xiàn)進(jìn)程的互斥即保證進(jìn)程互斥地進(jìn)入各自的臨界區(qū)。這里所用信號(hào)量的初值一般為1，表示臨界資源未被占用，且其可用數(shù)目為1。

用P、V操作原語實(shí)現(xiàn)進(jìn)程互斥的效率更高一些，因?yàn)镻操作中引入了阻塞機(jī)制，所以消除了CPU忙等現(xiàn)象。三個(gè)進(jìn)程互斥進(jìn)入臨界區(qū)P(S)V(S)臨界區(qū)P(S)V(S)臨界區(qū)P(S)V(S)臨界區(qū)P1P2P3互斥區(qū)然后P1、P2同時(shí)競爭P操作，設(shè)P1先執(zhí)行設(shè)P3先進(jìn)入此時(shí)s-1->s于是s=0設(shè)P3退出后此時(shí)s+1->s于是s=1P1執(zhí)行后此時(shí)s-1->s于是s=0P2執(zhí)行此時(shí)s-1->s于是s=-1，阻塞P1退出：此時(shí)s+1->s于是s=0≤0，釋放P2P2退出后此時(shí)s+1->s于是s=1P、V操作也都是配對出現(xiàn)，但對同一個(gè)信號(hào)量的P、V操作卻不是同時(shí)出現(xiàn)在每一個(gè)進(jìn)程的程序里，而是分別出現(xiàn)在一個(gè)進(jìn)程和它的合作伙伴的代碼中。解答這類進(jìn)程同步問題的主要步驟也是有三步：(1)分析清楚題目涉及的進(jìn)程間的制約關(guān)系(2)設(shè)置信號(hào)量（包括信號(hào)量的個(gè)數(shù)和初值及其物理含義），合作進(jìn)程間需要收發(fā)幾條消息相應(yīng)就設(shè)置幾個(gè)信號(hào)量。同步信號(hào)量的初值一般為0，表示得到合作進(jìn)程的消息后才能向前推進(jìn)。(3)給出進(jìn)程相應(yīng)程序的算法描述或流程控制，并把P、V操作加到程序的適當(dāng)處。2.用P、V操作實(shí)現(xiàn)進(jìn)程的同步例1:生產(chǎn)者—消費(fèi)者問題公用緩沖池，有n個(gè)緩沖區(qū)一組生產(chǎn)者生產(chǎn)產(chǎn)品一組消費(fèi)者取走產(chǎn)品【問題分析】①生產(chǎn)者—消費(fèi)者之間的同步關(guān)系表現(xiàn)為：一旦緩沖池中所有緩沖區(qū)均裝滿產(chǎn)品時(shí)，生產(chǎn)者必須等待消費(fèi)者提供空緩沖區(qū)；一旦緩沖池中所有緩沖區(qū)全為空時(shí)，消費(fèi)者必須等待生產(chǎn)者提供滿緩沖區(qū)。②生產(chǎn)者—消費(fèi)者之間還有互斥關(guān)系：由于緩沖池是臨界資源，所以任何進(jìn)程在對緩沖區(qū)進(jìn)行存取操作時(shí)都必須和其他進(jìn)程互斥進(jìn)行。生產(chǎn)者－消費(fèi)者問題是相互合作進(jìn)程關(guān)系的一種抽象【問題解答】①所用信號(hào)量設(shè)置如下：

Ⅰ）同步信號(hào)量empty，初值為n，表示消費(fèi)者已把緩沖池中全部產(chǎn)品取走，有n個(gè)空緩沖區(qū)可用。

Ⅱ）同步信號(hào)量full，初值為0，表示生產(chǎn)者尚未把產(chǎn)品放入緩沖池，有0個(gè)滿緩沖區(qū)可用。

Ⅲ）互斥信號(hào)量mutex，初值為1，以保證同時(shí)只有一個(gè)進(jìn)程能夠進(jìn)入臨界區(qū)，訪問緩沖池。

②用信號(hào)量機(jī)制解決生產(chǎn)者—消費(fèi)者問題的算法描述如下：生產(chǎn)者i

消費(fèi)者j生產(chǎn)出一產(chǎn)品；

P（full）；P（empty）；

P（mutex）；P（mutex）；

從緩沖區(qū)取出一產(chǎn)品；將該產(chǎn)品放入緩沖區(qū)；

V（mutex）；V（mutex）；

V（empty）；V（full）；

消費(fèi)該產(chǎn)品；

實(shí)例總結(jié)，可以得出這樣的結(jié)論：實(shí)現(xiàn)進(jìn)程的同步互斥實(shí)際就是給進(jìn)程的并發(fā)執(zhí)行增加一定的限制，以保證被訪問的共享數(shù)據(jù)的完整性和進(jìn)程執(zhí)行結(jié)果的可再現(xiàn)性。用信號(hào)量機(jī)制解這類題的三個(gè)步驟：（1）分析進(jìn)程間的制約關(guān)系（2）設(shè)置信號(hào)量（3）實(shí)施P、V操作。第一步是基礎(chǔ)、關(guān)鍵，第三步是核心。掌握實(shí)現(xiàn)進(jìn)程互斥與進(jìn)程同步的第三步在形式上差異：即P、V操作總是配對出現(xiàn)的。但P,V在互斥問題中總是出現(xiàn)在同一個(gè)進(jìn)程的代碼中，且緊緊夾著臨界區(qū)；而在同步問題中，卻是分別出現(xiàn)在兩個(gè)合作進(jìn)程的代碼中，需要等消息的一方用P操作，相應(yīng)的對同一信號(hào)量的V操作則在發(fā)出此消息的另一方中。

3、查找

Hash函數(shù)

折半查找312726211916130911050102H(K)=int(K/3)+1121110987654321表項(xiàng)序號(hào)根據(jù)關(guān)鍵字直接計(jì)算出元素所在位置的函數(shù)。例如：設(shè)哈希函數(shù)為：

int(K/3)+1則構(gòu)造01、02、05、09、11、13、16、19、21、26、27、31、的散列表(哈希表）為：哈希函數(shù)：沖突：兩個(gè)不同的關(guān)鍵字具有相同的存儲(chǔ)位置。

2、

構(gòu)造哈希函數(shù)的方法

（1）直接定址法——取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址，即H（K）=K或H（K）=A*K+B；（其中A、B為常數(shù)）直接定址哈希函數(shù)示例：某公司一險(xiǎn)種投保費(fèi)交納表（20年），將年份作關(guān)鍵字，哈希函數(shù)取關(guān)鍵字本身，若查找第3年應(yīng)交納的保費(fèi)，只要查找表的第3項(xiàng)即可。地址010203……20年份123…….20保費(fèi)…….…….…….…………

（2）平方取中法——取關(guān)鍵字平方后的中間幾位為哈希函數(shù)。如：K=308，K2=94864，H（K）=486（3）除后余數(shù)法——取關(guān)鍵字被不大于散列表表長m的數(shù)p除后所得的余數(shù)為哈希函數(shù)。即H（K）=KMODp（pm）3、處理沖突的方法

例已知一組關(guān)鍵字（19,14,23,1,68,20,84,27,55,11,10,79),哈希函數(shù)為：H(key)=keyMOD13,哈希

表長為m=16，設(shè)每個(gè)記錄的查找概率相等用線性探測再散列處理沖突，即Hi=(H(key)+di)MODm（19,14,23,1,68,20,84,27,55,11,10,79)H(key)=keyMOD13H(55)=3沖突

H1=(3+1)MOD16=4沖突

H2=(3+2)MOD16=5H(79)=1沖突

H1=(1+1)MOD16=2沖突

H2=(1+2)MOD16=3沖突

H3=(1+3)MOD16=4沖突

H4=(1+4)MOD16=5沖突

H5=(1+5)MOD16=6沖突

H6=(1+6)MOD16=7沖突

H7=(1+7)MOD16=8沖突

H8=(1+8)MOD16=9H(19)=6H(14)=1H(23)=10H(1)=1沖突

H1=(1+1)MOD16=2H(68)=3H(20)=7H(84)=6沖突

H1=(6+1)MOD16=7沖突

H2=(6+2)MOD16=8H(27)=1沖突

H1=(1+1)MOD16=2沖突

H2=(1+2)MOD16=3沖突

H3=(1+3)MOD16=4H(11)=11H(10)=10沖突

H1=(10+1)MOD16=11沖突

H2=(10+2)MOD16=120123456789101112131415地址關(guān)鍵字探測次數(shù)191141231

12681201843274553111103799(2)用鏈地址法處理沖突012345678910111214^127796855198420231011^^^^^^^^^^^^關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)折半查找(binarysearch)

折半查找,亦稱二分查找。查找過程：每次將待查記錄所在區(qū)間縮小一半。適用條件：采用順序存儲(chǔ)結(jié)構(gòu)的有序表。算法實(shí)現(xiàn)：設(shè)表長為n，low、high和

mid分

別指向待查元素所在區(qū)間的下界、上界和中點(diǎn),k為給定值。初始時(shí)，令

low=0,high=n-1,mid=(low+high)/2

讓給定值k與mid指向記錄的關(guān)鍵字相比較

若給定值k=s[mid].key，查找成功；midlowhighhighlow=mid+1k>s[mid].key

若給定值k>s[mid].key，則在區(qū)域

low=mid+1至high內(nèi)查找元素；k<s[mid].keyhigh=mid-1low

若給定值k<s[mid].key，則在區(qū)域low至high=mid-1內(nèi)查找元素；重復(fù)上述操作，直至low>high時(shí)，查找失敗。解：①

low=0high=10mid=(low+high)/2=5k=21<s[mid].key=s[5].key=56

012345678910513192137566475808892②low=0high=mid-1=5-1=4mid=(low+high)/2=2k=21>s[2].key=19③low=mid+1=3high=4mid=(low+high)/2=3k=21=s[mid].key=s[3].key=21答：查找成功查找關(guān)鍵字等于給定值（k=21）的元素。

若給定值k<s[mid].key，則在區(qū)域low~high=mid-1內(nèi)查找元素；

若給定值k>s[mid].key，則在區(qū)域

low=mid+1~high內(nèi)查找元素；4、二叉樹的遍歷及樹、森林與二叉樹的轉(zhuǎn)換，生成排序二叉樹的過程先序遍歷定義：若二叉樹為空，遍歷結(jié)束，否則：（1）訪問根結(jié)點(diǎn)；（2）按先序方式遍歷根結(jié)點(diǎn)的左子樹；（3）按先序方式遍歷根結(jié)點(diǎn)的右子樹。ABDEGCFHABGDFECH中序遍歷定義：若二叉樹為空，遍歷結(jié)束，否則：（1）按中序方式遍歷根結(jié)點(diǎn)的左子樹；（2）訪問根結(jié)點(diǎn)；（3）按中序方式遍歷根結(jié)點(diǎn)的右子樹。ABDEGCFHDGEBHAFC后序遍歷定義：若二叉樹為空，遍歷結(jié)束，否則：（1）按后序方式遍歷根結(jié)點(diǎn)的左子樹；（2）按后序方式遍歷根結(jié)點(diǎn)的右子樹；（3）訪問根結(jié)點(diǎn)。ABDEGCFHGDBECHFA根據(jù)遍歷序列構(gòu)造二叉樹：

若給定一棵二叉樹的中序遍歷序列和另一種序列便可得到該二叉樹。不失一般性，這里以一棵二叉樹的中序遍歷序列和先序遍歷序列來構(gòu)造該二叉樹構(gòu)造二叉樹的步驟：1、從先序遍歷序列中取第一個(gè)結(jié)點(diǎn)，為該二叉樹的根結(jié)點(diǎn)，再從中序遍歷序列中找到根結(jié)點(diǎn)，根結(jié)點(diǎn)之前的結(jié)點(diǎn)序列為根結(jié)點(diǎn)左子樹的中序遍歷序列，之后的結(jié)點(diǎn)序列為根結(jié)點(diǎn)右子樹的中序遍歷序列。2、再用遞歸的方法，分別重構(gòu)根結(jié)點(diǎn)的左右子樹，重復(fù)用第一步的方法，直到得到所有的結(jié)點(diǎn)序列為止。例：已知二叉樹先序遍歷序列為ABCDEFGHIJ，中序遍歷序列為CBDEAFHIGJ，試構(gòu)造此二叉樹。ABCFAC、B、D、EF、H、I、G、JD、EH、IG、JABCDEFGJHIABCDEFGJH、I樹轉(zhuǎn)換成二叉樹操作算法：保留一個(gè)結(jié)點(diǎn)的最左子結(jié)點(diǎn)；抹掉其余兄弟結(jié)點(diǎn)與上級(jí)結(jié)點(diǎn)的連線；將兄弟結(jié)點(diǎn)連在一起；以根為軸，順時(shí)針旋轉(zhuǎn)一個(gè)角度。舉例：oooooooooooooo加線抹線ooooooo旋轉(zhuǎn)ooooooo

第一步：k1作為二叉排序樹的根。

第二步：若k2<k1，則k2所在結(jié)點(diǎn)應(yīng)插在左子樹上；否則，插入到k1的右子樹上。第三步：讀入ki，若ki〈k1（根），則進(jìn)入左子樹，否則，進(jìn)入右子樹，繼續(xù)與子樹之根比較，直到某結(jié)點(diǎn)kj，若有ki<kj

且結(jié)點(diǎn)kj的左子樹為空,則結(jié)點(diǎn)ki插入道結(jié)點(diǎn)kj的左子樹；若有ki≥kj

的右子樹為空，則結(jié)點(diǎn)ki

插入到結(jié)點(diǎn)kj

的右子樹。二叉排序樹生成：對一序列{k1,k2,…,kn}，先設(shè)一棵空二叉樹，然后將序列中的元素順次生成結(jié)點(diǎn)后，逐個(gè)插入。插入步驟如下：

例有8個(gè)數(shù)構(gòu)成的序列{10，18，3，8，12，2，7，3}，根據(jù)算法的基本思想構(gòu)成一個(gè)二叉排序樹。1010181018310183810183812101838122101838122710183812273中序遍歷二叉排序樹可得到一個(gè)關(guān)鍵字的遞增有序序列：233781012185、排序的思想及其過程插入排序選擇排序交換排序快速排序歸并排序⑴插入排序基本思想：將n個(gè)元素的數(shù)列分為已有序和無序兩個(gè)部分。

{{a1}，{a2，a3，a4，…,an}}{{a1(1)，a2(1)}，{a3(1)a4(1)

…,an(1)}}

…...{{a1(n-1)，a2(n-1)

，…},{an(n-1)}}

每次處理就是將無序數(shù)列的第一個(gè)元素與有序數(shù)列的元素從后往前逐個(gè)進(jìn)行比較,找出插入位置,將該元素插入到有序數(shù)列的合適位置中。有序無序⑵選擇排序基本思想：每次從待排序的記錄中選出關(guān)鍵字最?。ɑ蜃畲螅┑挠涗洠樞蚍旁谝延行虻挠涗浶蛄械淖詈螅ɑ蜃钋埃┟?，直到全部數(shù)列有序。

{{a1}，{a2，a3，a4，…,an}}{{a1(1)，a2(1)}，{a3(1)，a4(1)…,an(1)}}

…...{{a1(n-1)，a2(n-1)

，…},{an(n-1)}}

有序無序3、交換排序（冒泡排序）指導(dǎo)思想：兩兩比較待排序記錄的關(guān)鍵字，并交換不滿足順序要求的那些偶對元素，直到全部數(shù)列滿足有序?yàn)橹?。冒泡排序（Bubblesort）是基于交換排序的一種算法。它是依次兩兩比較待排序元素；若為逆序（遞增或遞減）則進(jìn)行交換，將待排序元素從左至右比較一遍稱為一趟“冒泡”。每趟冒泡都將待排序列中的最大關(guān)鍵字交換到最后（或最前）位置。直到全部元素有序?yàn)橹??！?/p>

a1a2a3…an-1an

最大值冒泡排序算法舉例設(shè)有數(shù)列{65,97,76,13,27,49,58}比較次數(shù)第1趟{(lán)65，76，13，27，49，58}，{97}6

第2趟{(lán)65，13，27，49，58}，{76，97}5

第3趟{(lán)13，27，49，58}，{65，76，97}4

第4趟{(lán)13，27，49}，{58，65，76，97}3

第5趟{(lán)13，27}，{49，58，65，76，97}2

第6趟{(lán)13}，{27，49，58，65，76，97}1

總計(jì)：21次4、快速排序基本思想在待排序序列中按某種方法選取一個(gè)元素K，以它為分界點(diǎn)，用交換的方法將序列分為兩個(gè)部分：比該值小的放在左邊，否則在右邊。形成

{左子序列}K{右子序列}

再分別對左、右兩部分實(shí)施上述分解過程，直到各子序列長度為1，即有序?yàn)橹?。分界點(diǎn)元素值K的選取方法不同，將構(gòu)成不同的排序法，也將影響排序的效率：取左邊第1個(gè)元素為分界點(diǎn)；取中點(diǎn)A[（left+right）/2]為分界點(diǎn)；選取最大和最小值的平均值為分界點(diǎn)等。設(shè)有序列{a1，a2，…,An},選取中點(diǎn)元素K為分界點(diǎn),分別從序列兩頭分別與K進(jìn)行比較,小于K的元素交換到左邊,否則交換到右邊;一趟處理后,左邊子序列的元素均小于分界點(diǎn)值K,右邊子序列元素均大于等于K值。Step1分別從兩端開始，指針i指向第一個(gè)元素A[left]，指針j指向最后一個(gè)元素A[right]，分界點(diǎn)取K；Step2循環(huán)（ij）從右邊開始進(jìn)行比較：若KA[j]，則將A[j]交換到左邊；若K〈A[j]，則j=j-1，再進(jìn)行比較；從左邊開始進(jìn)行比較：若K〉A(chǔ)[i]，則i=i+1，再進(jìn)行比較；若KA[i]，則將A[i]交換到右邊。當(dāng)i=j時(shí)，一次分解操作完成。Step3在對分解出的左、右兩個(gè)子序列按上述步驟繼續(xù)進(jìn)行分解，直到子序列長度為1（不可再分）為止，也即序列全部有序?？焖倥判蛩惴ㄅe例對于數(shù)列{49，38，60，90，70，15，30，49}，采用中點(diǎn)分界法：初始狀態(tài):4938609070153049比較次數(shù)第1趟

493860907015304949386090701530495（i4、j1）

49386049701530905（i5、j2）

{49386049701530}90

小計(jì)：10

ik=90jijji5、歸并排序

歸并是將兩個(gè)或兩個(gè)以上的有序表合成一個(gè)新的有序表。用這種思想實(shí)現(xiàn)的排序稱作歸并排序(MergingSort)。假設(shè)初始序列有n個(gè)記錄，可以看成是有n個(gè)有序的字序列，然后兩兩歸并，得到n/2個(gè)有序的子序列，再兩兩歸并，直到得到一個(gè)長度為n的有序序列為止，這種排序方法稱為2-路歸并排序。

2-路歸并排序是我們最經(jīng)常使用的歸并排序。其核心操作是將一維數(shù)組中前后相鄰的2個(gè)有序序列歸并成為一個(gè)有序序列。Step1把待排序的n個(gè)記錄看作是長度為1的有序序列。將相鄰子序列兩兩歸并為長度為2的有序序列；Step2把得到的n/2個(gè)長度為2的有序子序列再歸并為長度為2*2的有序序列；Step3按Step2的方式，重復(fù)對相鄰有序子序列進(jìn)行歸并操作，直到成為一個(gè)有序序列為止。4949382713766597第一趟排序?qū)⒚恳粋€(gè)元素看成一個(gè)有序表兩兩歸并3849492776136597第二趟排序3849659713274976第三趟排序13972776654938491397277665493849給定數(shù)列{513、87、512、61、908、170、897、275、653、462}，計(jì)算采用下列算法的比較次數(shù)：插入、選擇、冒泡、快速、歸并排序。(1)插入排序：1．{513}{87、512、61、908、170、897、275、653、462}02．{87，513}{512、61、908、170、897、275、653、462}13．{87，512，513}{61、908、170、897、275、653、462}24．{61，87，512，513}{908、170、897、275、653、462}35．{61，87，512，513、908}{170、897、275、653、462}16．{61，87，170、512，513、908}{897、275、653、462}47．{61，87，170、512，513、897、908}{275、653、462}28．{61，87，170、275、512，513、897、908}{653、462}59．{61，87，170、275、512，513、653、897、908}{462}310．{61，87，170、275、462、512，513、653、897、908}6比較次數(shù)=1+2+3+1+4+2+5+3+6=27(2)選擇排序：1．{61}{87、512，513、908、170、897、275、653、462}92．{61，87}{512，513、908、170、897、275、653、462}83．{61，87，170}{513、908、512、897、275、653、462}74．{61，87，170，275}{908、512、897、513、653、462}65．{61，87，170，275，462}{512、897、513、653、908}56．{61，87，170，275，462，512}{897、513、653、908}47．{61，87，170，275，462，512，513}{897、653、908}38．{61，87，170，275，462，512，513、653}{897、908}29．{61，87，170，275，462，512，513、653、897}{908}110．{61，87，170，275，462，503、512、653、897，908}0比較次數(shù)=9+8+7+6+5+4+3+2+1=45（3）冒泡排序0．{513、87、512、61、908、170、897、275、653、462}1．{87，512，61，513，170，897，275，653，462，908}92．{87，61，512，170，513，275，653，462，896，908}83．{61，87，170，512，275，513，462，653，896，908}74．{61，87，170，275，512，462，513，653，896，908}65．{61，87，170，275，462，512，513，653，896，908}56．{61，87，170，275，462，512，513，653，896，908}4但沒有交換，停止。7．{61，87，170，275，462，503，512，653，896，908}0比較次數(shù)=9+8+7+6+5+4+=39注意：如果采用沒有改進(jìn)的方法，比較次數(shù)為45（4）快速排序513、87、512、61、908、170、897、275、653、4621．{462、87、512、61、275、170}、513、{897、653、908}92．{170、87、275、61}、462、{512}、513、{653}、897、{908}73．{61、87}、170、{275}、462、{512}、513、{653}、897、{908}44．{61}、87、170、275、{462}、503、512、{653}、897、90825．61、87、170、275、462、503、512、653、897、9080比較次數(shù)=9+7+4+2=22（5）歸并排序0．513、87、512、61、908、170、897、275、653、4621．{87、513}、{61、512}、{170、908}、{275、897}、{462、653}52．{61，87，512，513}、{170、275、897、908}、{462、653}63．{61，87，170，275，512，513，897，908}、{462、653}64．{61，87，170，275，462，503，512，653，897，908}8比較次數(shù)=5+6+6+8=256、通過鄰接矩陣、鄰接表寫出其圖的遍歷70一、深度優(yōu)先搜索二、廣度優(yōu)先搜索

圖的遍歷遍歷定義：從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊，訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次，就叫做圖的遍歷，它是圖的基本運(yùn)算。遍歷實(shí)質(zhì)：找每個(gè)頂點(diǎn)的鄰接點(diǎn)的過程。圖的特點(diǎn)：圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。解決思路：可設(shè)置一個(gè)輔助數(shù)組

visited[n]，用來標(biāo)記每個(gè)被訪問過的頂點(diǎn)。它的初始狀態(tài)為0，在圖的遍歷過程中，一旦某一個(gè)頂點(diǎn)i

被訪問，就立即改visited[i]為1，防止它被多次訪問。圖常用的遍歷：怎樣避免重復(fù)訪問？71一、深度優(yōu)先搜索(DFS)基本思想：——仿樹的先序遍歷過程。Depth_FirstSearchv1v1v2v3v8v7v6v4v5DFS結(jié)果例1：→→→→→→→v2v4v8v5v3v6v7例2：v2→v1→v3→v5→DFS結(jié)果v4

→v6起點(diǎn)起點(diǎn)遍歷步驟應(yīng)退回到V8，因?yàn)閂2已有標(biāo)記72深度優(yōu)先搜索（遍歷）步驟：詳細(xì)歸納：在訪問圖中某一起始頂點(diǎn)

v

后，由

v出發(fā)，訪問它的任一鄰接頂點(diǎn)

w1；再從

w1出發(fā)，訪問與

w1鄰接但還未被訪問過的頂點(diǎn)

w2；然后再從

w2出發(fā)，進(jìn)行類似的訪問，…

如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn)

u為止。接著，退回一步，退到前一次剛訪問過的頂點(diǎn)，看是否還有其它未被訪問的鄰接頂點(diǎn)。

如果有，則訪問此頂點(diǎn)，之后再從此頂點(diǎn)出發(fā)，進(jìn)行與前述類似的訪問；

如果沒有，就再退回一步進(jìn)行搜索。重復(fù)上述過程，直到連通圖中所有頂點(diǎn)都被訪問過為止。簡單歸納：訪問起始點(diǎn)v;若v的第1個(gè)鄰接點(diǎn)沒訪問過，深度遍歷此鄰接點(diǎn)；若當(dāng)前鄰接點(diǎn)已訪問過，再找v的第2個(gè)鄰接點(diǎn)重新遍歷。73討論1：計(jì)算機(jī)如何實(shí)現(xiàn)DFS？123456100000020000003000000400000050000006000000000000123456010000110000111000111010111110111111DFS結(jié)果鄰接矩陣A輔助數(shù)組visited[n]起點(diǎn)——開輔助數(shù)組

visited[n]！例：1234561011100210001031000104100001501100060