全國(guó)二級(jí)等級(jí)考試輔導(dǎo)公共基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)DataStructure

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等

線性結(jié)構(gòu)

非線性結(jié)構(gòu)

順序存儲(chǔ)

鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)ｊ?duì)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：此表必須記?。〗Y(jié)束放映數(shù)據(jù)的邏輯結(jié)構(gòu)：含義：反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。包含兩方面的信息：第一，表示數(shù)據(jù)元素的信息；第二，表示各數(shù)據(jù)元素之間的前后件關(guān)系。例1：B=(D,R)，其中D是數(shù)據(jù)對(duì)象，R是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。若有D={1,2,3,4},R={(1,2),(2,3),(3,4)}，則我們可以用圖的形式畫(huà)出該數(shù)據(jù)結(jié)構(gòu)B：1234例2：家庭成員數(shù)據(jù)結(jié)構(gòu)：B=(D,R),D={父親，兒子，女兒}，R={（父親，兒子），（父親，女兒）}，則圖形表示如下：父親女兒兒子例3：課程關(guān)系數(shù)據(jù)結(jié)構(gòu)：B=(D,R),D={教師1，教師2，班級(jí)1，班級(jí)2，班級(jí)3}，R={（教師1，班級(jí)1），（教師1，班級(jí)3），（教師2，班級(jí)1），（教師2，班級(jí)2），（教師2，班級(jí)3）}，則圖形表示如下：教師1班級(jí)3班級(jí)1教師2班級(jí)2數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)不討論非線性結(jié)構(gòu)數(shù)據(jù)的邏輯、物理結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)—只抽象反映數(shù)據(jù)元素的邏輯關(guān)系數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu)—數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)密切相關(guān) 算法設(shè)計(jì) 邏輯結(jié)構(gòu) 算法實(shí)現(xiàn) 存儲(chǔ)結(jié)構(gòu) 分為：順序存儲(chǔ)結(jié)構(gòu)借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

NEXT元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Loc+（i-1)*m順序存儲(chǔ)1536元素21400元素11346元素3∧元素4h

鏈?zhǔn)酱鎯?chǔ)

2.線性表線性表的類型定義

線性結(jié)構(gòu)特點(diǎn)：在數(shù)據(jù)元素的非空有限集中存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素除第一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼線性表是一種典型的線性結(jié)構(gòu)。數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而運(yùn)算的具體實(shí)現(xiàn)則是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。

2.1順序表上基本運(yùn)算的實(shí)現(xiàn)在c語(yǔ)言中，順序表用一維數(shù)組來(lái)實(shí)現(xiàn)存儲(chǔ)。算法：插入刪除定義：線性表的插入是指在第I（1

i

n+1）個(gè)元素之前插入一個(gè)新的數(shù)據(jù)元素x，使長(zhǎng)度為n的線性表

變成長(zhǎng)度為n+1的線性表

需將第i至第n共（n-i+1)個(gè)元素后移算法插入線性表的插入是指在表的第i個(gè)位置上插入一個(gè)值為

x

的新元素，插入后使原表長(zhǎng)為n的表:(a1，a2，...，ai-1，ai，ai+1，...，an)成為表長(zhǎng)為n+1表:(a1，a2，...，ai-1，x，ai，ai+1，...，an

)。i的取值范圍為1<=i<=n+1。內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號(hào)i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號(hào)i+1nn+1an-1x順序表上完成這一運(yùn)算則通過(guò)以下步驟進(jìn)行：

(1)將ai～an順序向下移動(dòng)，為新元素讓出位置；

(2)將x置入空出的第i個(gè)位置；

(3)修改last指針(相當(dāng)于修改表長(zhǎng))，使之仍指向最后一個(gè)元素。算法如下：for(j=n;j>=i;j--)a[j+1]=a[j];//元素后移a[i]=x;//插入元素n++;//表長(zhǎng)度增加1刪除定義：線性表的刪除是指將第i（1

i

n）個(gè)元素刪除，使長(zhǎng)度為n的線性表()niiaaaaa…….…..,,,,1,21-

變成長(zhǎng)度為n-1的線性表)(niiaaaaa…...……,,,,11,21+-

需將第i+1至第n共（n-i)個(gè)元素前移內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號(hào)i+1nn+1內(nèi)存a1a2ai+1V數(shù)組下標(biāo)01i-1n-2in-112i元素序號(hào)i+1n-1nanai+2算法如下：for(j=i;j<len;j++)a[j]=a[j+1];//元素前移len--;//表長(zhǎng)度減12.2線性表的鏈?zhǔn)綄?shí)現(xiàn)和表示線性鏈表線性鏈表的存儲(chǔ)結(jié)構(gòu)單鏈表的基本運(yùn)算插入刪除特點(diǎn)：用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素每個(gè)數(shù)據(jù)元素ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息結(jié)點(diǎn)

數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲(chǔ)位置數(shù)據(jù)域指針域結(jié)點(diǎn)

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

ZHAOQIANSUNLIZHOUWUZHENGWANG^H例線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲(chǔ)地址1713192531374331H頭指針實(shí)現(xiàn)typedefstructnode{

datatype

data;structnode*next;}LNode，*LinkList；

;定義的LNode是結(jié)點(diǎn)的類型，LinkList是指向Lnode類型結(jié)點(diǎn)的指針類型。

datanextp結(jié)點(diǎn)（*p）(*p)表示p所指向的結(jié)點(diǎn)(*p).data

p->data表示p指向結(jié)點(diǎn)的數(shù)據(jù)域(*p).link

p->next表示p指向結(jié)點(diǎn)的指針域定義：結(jié)點(diǎn)中只含一個(gè)指針域的鏈表叫~，也叫單鏈表線性鏈表單鏈表的基本運(yùn)算插入刪除pabxss->next=p->next;p->next=s;單鏈表的插入插入：在線性表兩個(gè)數(shù)據(jù)元素a和b間插入x，已知p指向a算法思路：1.找到第i-1個(gè)結(jié)點(diǎn)；若存在繼續(xù)2，否則結(jié)束

2.申請(qǐng)、填裝新結(jié)點(diǎn)；

3.將新結(jié)點(diǎn)插入。結(jié)束。pabc刪除：?jiǎn)捂湵碇袆h除b，設(shè)p指向ap->next=p->next->next;單鏈表的刪除算法思路：1.找到第i-1個(gè)結(jié)點(diǎn)；若存在繼續(xù)2，否則結(jié)束；

2.若存在第i個(gè)結(jié)點(diǎn)則繼續(xù)3，否則結(jié)束；

3.刪除第i個(gè)結(jié)點(diǎn)，結(jié)束。循環(huán)鏈表

單鏈表上的訪問(wèn)是一種順序訪問(wèn)，從其中某一個(gè)結(jié)點(diǎn)出發(fā)，可以找到它的直接后繼，但無(wú)法找到它的直接前驅(qū)。因此，我們可以考慮建立這樣的鏈表，具有單鏈表的特征，但又不需要增加額外的存貯空間，僅對(duì)表的鏈接方式稍作改變，使得對(duì)表的處理更加方便靈活。從單鏈表可知，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)镹ULL，表示單鏈表已經(jīng)結(jié)束。如果將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域改為存放鏈表中頭結(jié)點(diǎn)（或第一個(gè)結(jié)點(diǎn)）的地址，就使得整個(gè)鏈表構(gòu)成一個(gè)環(huán)，又沒(méi)有增加額外的存貯空間，稱這樣的鏈表為循環(huán)鏈表。循環(huán)鏈表優(yōu)點(diǎn)：可以從任何一個(gè)結(jié)點(diǎn)出發(fā)訪問(wèn)到其他結(jié)點(diǎn)。單鏈表：只有從頭結(jié)點(diǎn)（或第一個(gè)結(jié)點(diǎn)出發(fā)才能訪問(wèn)到其他結(jié)點(diǎn)）3.棧和隊(duì)列棧棧是特殊的線性表，是操作受限的線性表，稱限定性DS棧的定義棧的存儲(chǔ)實(shí)現(xiàn)和運(yùn)算實(shí)現(xiàn)順序棧棧定義棧（stack）棧的定義和特點(diǎn)定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表，表尾—棧頂，表頭—棧底，不含元素的空表稱空棧特點(diǎn)：先進(jìn)后出（FILO）或后進(jìn)先出（LIFO）ana1a2……...棧底棧頂...出棧進(jìn)棧棧s=(a1,a2,……,an)堆棧操作A進(jìn)BA進(jìn)A出CA進(jìn)A出DA進(jìn)A出出初始出棧元素順序：B→C→D→A棧的存儲(chǔ)實(shí)現(xiàn)和運(yùn)算實(shí)現(xiàn)由于棧是運(yùn)算受限的線性表，因此線性表的存儲(chǔ)結(jié)構(gòu)對(duì)棧也是適用的，只是操作不同而已。順序棧鏈棧約定：棧頂指針指向棧頂元素。3.2隊(duì)列隊(duì)列是特殊的線性表，是操作受限的線性表，稱限定性DS隊(duì)列的定義及特點(diǎn)定義：隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表隊(duì)尾(rear)——允許插入的一端隊(duì)頭(front)——允許刪除的一端隊(duì)列特點(diǎn)：先進(jìn)先出(FIFO)a1a2a3…….an入隊(duì)出隊(duì)frontrear隊(duì)列Q=(a1,a2,……,an)3.2.1隊(duì)列的定義

初始時(shí),隊(duì)列為空,有

front

=-1rear

=

-1隊(duì)列元素個(gè)數(shù)=rear-front約定

rear指出實(shí)際隊(duì)尾元素所在的位置,front指出實(shí)際隊(duì)頭元素所在位置的前一個(gè)位置.queue[0~M-1]0M-1abcdfrontrearad順序隊(duì)列出入隊(duì)循環(huán)隊(duì)列為充分利用向量空間，克服“假上溢”現(xiàn)象的方法是：將向量空間想象為一個(gè)首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量。存儲(chǔ)在其中的隊(duì)列稱為循環(huán)隊(duì)列（CircularQueue）。循環(huán)隊(duì)列判斷：空隊(duì)列：s=0并且front=rear滿隊(duì)列：s=1并且front=rear利用"模運(yùn)算"

計(jì)算循環(huán)隊(duì)列元素個(gè)數(shù)方法：若front<rear:元素個(gè)數(shù)=rear-front若front>rear元素個(gè)數(shù)=n-（front-rear）其中n是循環(huán)隊(duì)列的容量。在前面討論的數(shù)據(jù)結(jié)構(gòu)都屬于線性結(jié)構(gòu)，線性結(jié)構(gòu)的特點(diǎn)是邏輯結(jié)構(gòu)簡(jiǎn)單，具有單一的前驅(qū)和后繼的數(shù)據(jù)關(guān)系。而現(xiàn)實(shí)中的許多事物的關(guān)系并非這樣簡(jiǎn)單，如人類社會(huì)的族譜、各種社會(huì)組織機(jī)構(gòu)以及城市交通、通訊等，這些事物中的聯(lián)系都是非線性的，采用非線性結(jié)構(gòu)進(jìn)行描繪會(huì)更明確和便利。所謂非線性結(jié)構(gòu)是指，在該結(jié)構(gòu)中至少存在一個(gè)數(shù)據(jù)元素，有兩個(gè)或兩個(gè)以上的直接前驅(qū)（或直接后繼）元素。樹(shù)型結(jié)構(gòu)和圖型結(jié)構(gòu)就是其中十分重要的非線性結(jié)構(gòu)。2005-41數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指______。A）存儲(chǔ)在外存中的數(shù)據(jù)B）數(shù)據(jù)所占的存儲(chǔ)空間量C）數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式D）數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示答案：D2下列關(guān)于棧的描述中錯(cuò)誤的是______。

A）棧是先進(jìn)后出的線性表

B）棧只能順序存儲(chǔ)

C）棧具有記憶作用

D）對(duì)棧的插入與刪除操作中，不需要改變棧底指針答案：B2005-43.對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為_(kāi)_____。

A）log2nB）n/2C）nD）n+1答案：C4.下列對(duì)于線性鏈表的描述中正確的是______。A）存儲(chǔ)空間不一定是連續(xù)，且各元素的存儲(chǔ)順序是任意的B）存儲(chǔ)空間不一定是連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面C）存儲(chǔ)空間必須連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面D）存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的答案：

A2005-45.有以下結(jié)構(gòu)體說(shuō)明和變量定義，如圖所示：

structnode{intdata;structnode*next;}*p,*q,*r;

pqr

現(xiàn)要將q所指結(jié)點(diǎn)從鏈表中刪除，同時(shí)要保持鏈表的連續(xù)，以下不能完成指定操作的語(yǔ)句是______。

A）p->next=q->next;B）p->next=p->next->next;C）p->next=r;D）p=q->next;

答案：D2005-9（1）下列關(guān)于棧的描述正確的是A）在棧中只能插入元素而不能刪除元素B）在棧中只能刪除元素而不能插入元素C）棧是特殊的線性表，只能在一端插入或刪除元素D）棧是特殊的線性表，只能在一端插入元素，而在另一端刪除元素

答案：C（2）下列敘述中正確的是A）一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲(chǔ)結(jié)構(gòu)B）數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)屬于非線性結(jié)構(gòu)C）一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)不影響數(shù)據(jù)處理的效率D）一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率答案：D2006-4(1)按照“后進(jìn)先出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是

A)隊(duì)列B)棧C)雙向鏈表D)二叉樹(shù)答案：B(2)下列敘述中正確的是A)線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B)棧與隊(duì)列是非線性結(jié)構(gòu)C)雙向鏈表是非線性結(jié)構(gòu)D)只有根結(jié)點(diǎn)的二叉樹(shù)是線性結(jié)構(gòu)答案：A2006-9（1）數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊(duì)列屬于(【5】)。答案：線性結(jié)構(gòu)2007-4(1)下列對(duì)隊(duì)列的敘述正確的是()A)隊(duì)列屬于非線性表B)隊(duì)列按“先進(jìn)后出”原則組織數(shù)據(jù)C)隊(duì)列在隊(duì)尾刪除數(shù)據(jù)D)隊(duì)列按“先進(jìn)先出”原則組織數(shù)據(jù)答案：D2007-9（1）下列敘述中正確的是A）程序執(zhí)行的效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān)B）程序執(zhí)行的效率只取決于程序的控制結(jié)構(gòu)C）程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量D）以上三種說(shuō)法都不對(duì)答案：A

（2）下列敘述中正確的是A）數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)必定是一一對(duì)應(yīng)的B）由于計(jì)算機(jī)存儲(chǔ)空間是向量式的存儲(chǔ)結(jié)構(gòu)，因此，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)一定是線性結(jié)構(gòu)C）程序設(shè)計(jì)語(yǔ)言中的數(shù)組一般是順序存儲(chǔ)結(jié)構(gòu)，因此，利用數(shù)組只能處理線性結(jié)構(gòu)D）以上三種說(shuō)法都不對(duì)答案：D2008-4（3）設(shè)某循環(huán)隊(duì)列的容量為50，頭指針front=5（指向隊(duì)頭元素的前一位置），尾指針rear=29（指向隊(duì)尾元素），則該循環(huán)隊(duì)列中共有___________個(gè)元素。答案：24.解析：若front<rear，則直接用rear-front;若front>=rear，則n-(front-rear)，n為循環(huán)隊(duì)列的容量。2008-9(1)一個(gè)棧的初始狀態(tài)為空，現(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的順序是：

A）12345ABCDEB)EDCBA54321C)ABCDE12345D)54321EDCBA答案：B(2)下列敘述中正確的是：A）循環(huán)隊(duì)列有隊(duì)頭和隊(duì)尾兩個(gè)指針，因此，循環(huán)隊(duì)列是非線性結(jié)構(gòu)B）在循環(huán)隊(duì)列中，只需要隊(duì)頭指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況C）在循環(huán)隊(duì)列中，只需要隊(duì)尾指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況D）循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定答案：D2008-9（3）下列敘述中正確的是：A）順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的B）順序存儲(chǔ)結(jié)構(gòu)只針對(duì)線性結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只針對(duì)非線性結(jié)構(gòu)C）順序存儲(chǔ)結(jié)構(gòu)能存儲(chǔ)有序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表D）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省內(nèi)存空間答案：A2009-31.下列敘述中正確的是：A）棧是“先進(jìn)先出”的線性表；B）隊(duì)列是“先進(jìn)后出”的線性表；C）循環(huán)隊(duì)列是非線性結(jié)構(gòu)；D）有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)答案：D2009-31.假設(shè)用一個(gè)長(zhǎng)度為50的數(shù)組（數(shù)組元素的下標(biāo)從0到49）作為棧的存儲(chǔ)空間，棧底指針bottom指向棧底元素，棧頂指針top指向棧頂元素，如果bottom=49，top=30（數(shù)組下標(biāo)），則棧中具有（）個(gè)元素。答案：202.符合結(jié)構(gòu)化原則的三種基本控制結(jié)構(gòu)是：選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)和（）。答案：順序結(jié)構(gòu)

2009-91.下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是A)循環(huán)隊(duì)列B)帶鏈隊(duì)列C)二叉樹(shù)D)帶鏈棧答案：C2.下列數(shù)據(jù)結(jié)構(gòu)中,能夠按照“先進(jìn)后出”原則存取數(shù)據(jù)的是A)循環(huán)隊(duì)列B)棧C)隊(duì)列D)二叉樹(shù)答案：B3.對(duì)于循環(huán)隊(duì)列，下列敘述中正確的是A)隊(duì)頭指針是固定不變的B)隊(duì)頭指針一定大于隊(duì)尾指針C)隊(duì)頭指針一定小于隊(duì)尾指針D)隊(duì)頭指針可以大于隊(duì)尾指針,也可以小于隊(duì)尾指針答案：D2010-31、一個(gè)隊(duì)列的初始狀態(tài)為空?，F(xiàn)將元素A,B,C,D,E,F,5,4,3,2,1依次入隊(duì),然后再依次退隊(duì),則元素退隊(duì)的順序?yàn)椤尽?。答案：A,B,C,D,E,F,5,4,3,2,12、設(shè)某循環(huán)隊(duì)列的容量為50,如果頭指針front=45(指向隊(duì)頭元素的前一位置),尾指針rear=10(指向隊(duì)尾元素),則該循環(huán)隊(duì)列中共有【】個(gè)元素。答案：15若front<rear:元素個(gè)數(shù)=rear-front若front>rear:元素個(gè)數(shù)=n-（front-rear）其中n是循環(huán)隊(duì)列的容量。2010-91、下列敘述中正確的是

A）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間是相同的

B）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要多于順序存儲(chǔ)結(jié)構(gòu)

C）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)

D）上述三種說(shuō)法都不對(duì)2、下列敘述中正確的是

A）在棧中，棧中元素隨棧底指針與棧頂指針的變化而動(dòng)態(tài)變化

B）在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動(dòng)態(tài)變化

C）在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動(dòng)態(tài)變化

D）上述三種說(shuō)法都不對(duì)2010-93、一個(gè)棧的初始狀態(tài)為空。首先將元素5,4,3,2,1依次入棧，然后退棧一次，再將元素A,B,C,D依次入棧，之后將所有元素全部退棧，則所有元素退棧（包括中間退棧的元素）的順序?yàn)椤尽?DCBA23452011-31、下列關(guān)于棧敘述正確的是A)棧頂元素最先能被刪除B)棧頂元素最后才能被刪除C)棧底元素永遠(yuǎn)不能被刪除D)以上三種說(shuō)法都不對(duì)答案：A2011-91、下列關(guān)于線性鏈表的敘述中，正確的是()。A)各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)，但它們的存儲(chǔ)順序與邏輯順序必須一致B)各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與邏輯順序可以不一致，但它們的存儲(chǔ)空間必須連續(xù)C)進(jìn)行插入與刪除時(shí)，不需要移動(dòng)表中的元素D)以上三種說(shuō)法都不對(duì)答案：C2、數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)與非線性結(jié)構(gòu)，帶鏈的棧屬于【】線性結(jié)構(gòu)4.樹(shù)與二叉樹(shù)樹(shù)的基本概念二叉樹(shù)二叉樹(shù)的性質(zhì)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的基本操作遍歷二叉樹(shù)樹(shù)的定義樹(shù)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)定義：樹(shù)(tree)是n(n>0)個(gè)結(jié)點(diǎn)的有限集T，其中：有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹(shù)的根(root)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,……Tm，其中每一個(gè)集合本身又是一棵樹(shù)，稱為根的子樹(shù)(subtree)特點(diǎn)：樹(shù)中至少有一個(gè)結(jié)點(diǎn)——根樹(shù)中各子樹(shù)是互不相交的集合A只有根結(jié)點(diǎn)的樹(shù)ABCDEFGHIJKLM有子樹(shù)的樹(shù)根子樹(shù)基本術(shù)語(yǔ)結(jié)點(diǎn)(node)——表示樹(shù)中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹(shù)的分支結(jié)點(diǎn)的度(degree)——結(jié)點(diǎn)擁有的子樹(shù)數(shù)葉子(leaf)——度為0的結(jié)點(diǎn)孩子(child)——結(jié)點(diǎn)子樹(shù)的根稱為該結(jié)點(diǎn)的孩子雙親(parents)——孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的雙親~兄弟(sibling)——同一雙親的孩子樹(shù)的度——一棵樹(shù)中最大的結(jié)點(diǎn)度數(shù)結(jié)點(diǎn)的層次(level)——從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層……深度(depth)——樹(shù)中結(jié)點(diǎn)的最大層次數(shù)二叉樹(shù)定義性質(zhì)特殊的二叉樹(shù)二叉樹(shù)的遍歷二叉樹(shù)定義

定義：二叉樹(shù)是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?shù)(n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)構(gòu)成特點(diǎn)每個(gè)結(jié)點(diǎn)至多有二棵子樹(shù)(即不存在度大于2的結(jié)點(diǎn))二叉樹(shù)的子樹(shù)有左、右之分，且其次序不能任意顛倒基本形態(tài)(5種）A只有根結(jié)點(diǎn)的二叉樹(shù)

空二叉樹(shù)AB右子樹(shù)為空AB左子樹(shù)為空ABC左、右子樹(shù)均非空二叉樹(shù)的性質(zhì)性質(zhì)1

若二叉樹(shù)的層數(shù)從1開(kāi)始，則二叉樹(shù)的第k層結(jié)點(diǎn)數(shù)，最多為2k-1個(gè)（k>=1）。性質(zhì)2

深度（高度）為k的二叉樹(shù)最多結(jié)點(diǎn)數(shù)為2k-1（k>=1）。

證明：深度為k的二叉樹(shù)，若要求結(jié)點(diǎn)數(shù)最多，則必須每一層的結(jié)點(diǎn)數(shù)都為最多，由性質(zhì)1可知，最大結(jié)點(diǎn)數(shù)應(yīng)為每一層最大結(jié)點(diǎn)數(shù)之和，既為20+21+…+2k-1=2k-1。性質(zhì)3

對(duì)任意一棵二叉樹(shù)，如果葉子結(jié)點(diǎn)(度為0)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則有n0=n2+1。證明：設(shè)二叉樹(shù)中度為1的結(jié)點(diǎn)個(gè)數(shù)為n1，根據(jù)二叉樹(shù)的定義可知，該二叉樹(shù)的結(jié)點(diǎn)數(shù)n=n0+n1+n2。又因?yàn)樵诙鏄?shù)中，度為0的結(jié)點(diǎn)沒(méi)有孩子，度為1的結(jié)點(diǎn)有1個(gè)孩子，度為2的結(jié)點(diǎn)有2個(gè)孩子，故該二叉樹(shù)的孩子結(jié)點(diǎn)數(shù)為n0*0+n1*1+n2*2，而一棵二叉樹(shù)中，除根結(jié)點(diǎn)外所有都為孩子結(jié)點(diǎn)，故該二叉樹(shù)的結(jié)點(diǎn)數(shù)應(yīng)為孩子結(jié)點(diǎn)數(shù)加1即：n=n0*0+n1*1+n2*2+1因此,有n=n0+n1+n2=n0*0+n2*1+n2*2+1，最后得到n0=n2+1。為繼續(xù)給出二叉樹(shù)的其它性質(zhì)，先定義兩種特殊的二叉樹(shù)。幾種特殊形式的二叉樹(shù)滿二叉樹(shù)定義：深度為k具有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)完全二叉樹(shù)定義：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹(shù)。特點(diǎn)1、葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)2、對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為L(zhǎng)，則其左分支下子孫的最大層次必為L(zhǎng)或L+11231145891213671014151231145891267101234567123456特殊二叉樹(shù)的性質(zhì)性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)高度為

log2n

+1或

log2（n+1）

。習(xí)題解析1、假設(shè)二叉樹(shù)中所有非葉子結(jié)點(diǎn)都有左、右子樹(shù)，則對(duì)這種二叉樹(shù)：（1）試問(wèn)：有n個(gè)葉子結(jié)點(diǎn)的樹(shù)中共有多少個(gè)結(jié)點(diǎn)？性質(zhì)3：對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1解：(1)依題意，這種二叉樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)，度為2的結(jié)點(diǎn)數(shù)n2和度為0的結(jié)點(diǎn)數(shù)n0之間滿足關(guān)系：n0=n2+1；(性質(zhì)2)所以總的結(jié)點(diǎn)數(shù)N=n2+n0=n0-1+n0=2n0-1=2n-1。二叉樹(shù)的遍歷

二叉樹(shù)的遍歷是指按照某種順序訪問(wèn)二叉樹(shù)中的每個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。遍歷是二叉樹(shù)中經(jīng)常要用到的一種操作。因?yàn)樵趯?shí)際應(yīng)用問(wèn)題中，常常需要按一定順序?qū)Χ鏄?shù)中的每個(gè)結(jié)點(diǎn)逐個(gè)進(jìn)行訪問(wèn)，查找具有某一特點(diǎn)的結(jié)點(diǎn)，然后對(duì)這些滿足條件的結(jié)點(diǎn)進(jìn)行處理。通過(guò)一次完整的遍歷，可使二叉樹(shù)中結(jié)點(diǎn)信息由非線性排列變?yōu)槟撤N意義上的線性序列。也就是說(shuō)，遍歷操作使非線性結(jié)構(gòu)線性化。二叉樹(shù)的遍歷二叉樹(shù)由根結(jié)點(diǎn)、根結(jié)點(diǎn)的左子樹(shù)和根結(jié)點(diǎn)的右子樹(shù)三部分組成。因此，只要依次遍歷這三部分，就可以遍歷整個(gè)二叉樹(shù)。若以D、L、R分別表示訪問(wèn)根結(jié)點(diǎn)、遍歷根結(jié)點(diǎn)的左子樹(shù)、遍歷根結(jié)點(diǎn)的右子樹(shù)，則二叉樹(shù)的遍歷有三種方式，即DLR（稱為先序遍歷）、LDR（稱為中序遍歷）和LRD（稱為后序遍歷）。二叉樹(shù)的遍歷先序遍歷：先訪問(wèn)根結(jié)點(diǎn),然后分別先序遍歷左子樹(shù)、右子樹(shù)中序遍歷：先中序遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹(shù)后序遍歷：先后序遍歷左、右子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)ADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDC先序遍歷:ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷:ADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA后序遍歷:B-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef遍歷算法應(yīng)用舉例

例根據(jù)給出的二叉樹(shù)的前序序列和中序序列，建立該二叉樹(shù).分析：若二叉樹(shù)的任意兩個(gè)結(jié)點(diǎn)的值都不相同，則二叉樹(shù)的前序序列和中序序列能唯一確定一棵二叉樹(shù)。另外，由前序序列和中序序列的定義可知，前序序列中第一個(gè)結(jié)點(diǎn)必為根結(jié)點(diǎn)，而在中序序列中，根結(jié)點(diǎn)剛好是左、右子樹(shù)的分界點(diǎn)，因此，可按如下方法建立二叉樹(shù)：1.用前序序列的第一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn);2.在中序序列中查找根結(jié)點(diǎn)的位置，并以此為界將中序序列劃分為左、右兩個(gè)序列(左、右子樹(shù));3.根據(jù)左、右子樹(shù)的中序序列中的結(jié)點(diǎn)個(gè)數(shù)，將前序序列去掉根結(jié)點(diǎn)后的序列劃分為左、右兩個(gè)序列，它們分別是左、右子樹(shù)的前序序列;4.對(duì)左、右子樹(shù)的前序序列和中序序列遞歸地實(shí)施同樣方法，直到所得左、右子樹(shù)為空。假設(shè)前序序列為ABDGHCEFI，中序序列為GDHBAECIF，則得到的二叉樹(shù)如下頁(yè)所示1。A為根結(jié)點(diǎn)ABDGHCEFIGDHBAECIFBDGHCEFIA2.B為左子樹(shù)的根結(jié)點(diǎn)BDGHGDHBCEFIDHGBA3.D為左子樹(shù)的左子樹(shù)的根結(jié)點(diǎn)4。C為右子樹(shù)的根結(jié)點(diǎn)5。F為右子樹(shù)的右子樹(shù)的根結(jié)點(diǎn)CEFIECIF2005-4（1）某二叉樹(shù)中度為2的結(jié)點(diǎn)有18個(gè)，則該二叉樹(shù)中有【1】個(gè)葉子結(jié)點(diǎn)。答案：19對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2-9（4）一棵二叉樹(shù)第六層（根結(jié)點(diǎn)為第一層）的結(jié)點(diǎn)數(shù)最多為【4】個(gè)。答案：322006-4(6)對(duì)如下二叉樹(shù)進(jìn)行后序遍歷的結(jié)果為A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCA 答案：D(7)在深度為7的滿二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為A)32B)31C)64D)63答案：CABCDEF2006-910.對(duì)下列二叉樹(shù)進(jìn)行中序遍歷的結(jié)果是________。

A）ACBDFEG

B）ACBDFGEC）ABDCGEF

D）FCADBEG答案：AFCEADGB2007-9（8）一棵二叉樹(shù)中共有70個(gè)葉子結(jié)點(diǎn)與80個(gè)度為1的結(jié)點(diǎn)，則該二叉樹(shù)中的總結(jié)點(diǎn)數(shù)為

A）219

B）221

C）229

D）231答案：A解析：n0=n2+1n=n0+n1+n2（2）深度為5的滿二叉樹(shù)有___________個(gè)葉子結(jié)點(diǎn)。答案：162008-91.對(duì)下列二叉樹(shù)進(jìn)行中序遍歷的結(jié)果是：答案：DBXEAYFZCABDCEFXYZ2009-31.某二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)是：

A）10B）8C）6D）4答案：C2009-91.某二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)以及3個(gè)度為1的結(jié)點(diǎn)，則該二叉樹(shù)中共有【】個(gè)結(jié)點(diǎn)。答案：142010-31.設(shè)二叉樹(shù)如下：

對(duì)該二叉樹(shù)進(jìn)行后序遍歷的結(jié)果為【】。答案：EDBGHFCA2010-91.一棵二叉樹(shù)有10個(gè)度為1的結(jié)點(diǎn)，7個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)共有【】個(gè)結(jié)點(diǎn)。答案：252011-31.下列敘述中正確的是A)有一個(gè)以上根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是非線性結(jié)構(gòu)B)只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是線性結(jié)構(gòu)C)循環(huán)鏈表是非線性結(jié)構(gòu)D)雙向鏈表是非線性結(jié)構(gòu)答案：B2.某二叉樹(shù)共有7個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)，則該二叉樹(shù)的深度為(假設(shè)根結(jié)點(diǎn)在第1層)A)3B)4C)6D)7答案：D說(shuō)明：n0=n2+1，說(shuō)明度為2的結(jié)點(diǎn)數(shù)為0，即二叉樹(shù)中只有度為1的結(jié)點(diǎn)和葉子結(jié)點(diǎn)，那么此二叉樹(shù)應(yīng)為一顆單支樹(shù)，樹(shù)中結(jié)點(diǎn)個(gè)數(shù)即為樹(shù)的深度。3.一棵二叉樹(shù)的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為【】。DEBFCA2011-91.下列關(guān)于二叉樹(shù)的敘述中，正確的是()。A)葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)少一個(gè)B)葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)C)葉子結(jié)點(diǎn)數(shù)是度為2的結(jié)點(diǎn)數(shù)的兩倍D)度為2的結(jié)點(diǎn)數(shù)是度為1的結(jié)點(diǎn)數(shù)的兩倍答案：B5.查找查找查找——也叫檢索，是根據(jù)給定的某個(gè)值，在表中確定一個(gè)關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素一、順序查找二、折半查找（二分查找）1順序查找查找過(guò)程：從表的一端開(kāi)始逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較算法描述i例01234567891011513192137566475808892找6464監(jiān)視哨iiii比較次數(shù)=5比較次數(shù)：查找第n個(gè)元素：1查找第n-1個(gè)元素：2……….查找第1個(gè)元素：n查找第i個(gè)元素：n+1-i查找失?。簄+12折半查找查找過(guò)程：每次將待查記錄所在區(qū)間縮小一半適用條件：采用順序存儲(chǔ)結(jié)構(gòu)的有序表lowhighmid例1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid例1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhigh等考真題（1）對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為_(kāi)_____。

A）log2nB）n/2C）nD）n+1答案：C（2）下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是

A）順序存儲(chǔ)的有序線性表B）線性鏈表

C）二叉鏈表D）有序線性鏈表答案：A（3）在長(zhǎng)度為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為_(kāi)_______。

A）63

B）64

C）6D）7答案：B（4）在長(zhǎng)度為n的有序線性表中進(jìn)行二分法查找，最壞情況下需要比較的次數(shù)是：A）O(n)B）O(n2）C）O（log2n）D）O（nlog2n）答案：C等考真題(1)下列敘述中正確的是

A)對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行查找,最壞清況下需要的比較次數(shù)為n

B)對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找,最壞情況下需要的比較次數(shù)為(n/2)

C)對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找,最壞情況下需要的比較次數(shù)為(log2n)D)對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找,最壞情況下需要的比較次數(shù)為(nlog2n)答案：A(2010年3月)對(duì)分查找適用條件：采用順序存儲(chǔ)結(jié)構(gòu)的有序表，不適用于線性鏈表(2)在長(zhǎng)度為n的線性表中，尋找最大項(xiàng)至少需要比較【】次。答案：n-1(2010年9月)(3)有序線性表能進(jìn)行二分查找的前提是該線性表必須是【】存儲(chǔ)的。答案：順序(2011年3月)等考真題(2)在長(zhǎng)度為n的順序存儲(chǔ)的線性表中插入一個(gè)元素，最壞情況下需要移動(dòng)表中【】個(gè)元素。。答案：n(2011年9月)排序?yàn)榱吮阌诓檎?，通常希望?jì)算機(jī)中的數(shù)據(jù)表是按關(guān)鍵碼有序的。排序和查找一樣，是一種非常重要的數(shù)據(jù)處理功能，計(jì)算機(jī)系統(tǒng)的很大一部分工作是對(duì)數(shù)據(jù)進(jìn)行排序。插入排序：直接插入排序交換排序：冒泡排序、快速排序選擇排序：簡(jiǎn)單選擇排序排序排序定義——將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列叫排序。插入排序基本思路：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排序好的子序列的適當(dāng)位置，直到全部記錄插入完成為止。直接插入排序排序過(guò)程：整個(gè)排序過(guò)程為n-1趟插入，即先將序列中第1個(gè)記錄看成是一個(gè)有序子序列，然后從第2個(gè)記錄開(kāi)始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序?yàn)橹?。?9386597761327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序結(jié)果：算法評(píng)價(jià)時(shí)間復(fù)雜度若待排序記錄按關(guān)鍵字從小到大排列(正序)關(guān)鍵字比較次數(shù)：記錄移動(dòng)次數(shù)：若待排序記錄按關(guān)鍵字從大到小排列(逆序)關(guān)鍵字比較次數(shù)：記錄移動(dòng)次數(shù)：若待排序記錄是隨機(jī)的，取平均值關(guān)鍵字比較次數(shù)：記錄移動(dòng)次數(shù)：交換排序基本思路：通過(guò)排序表中兩個(gè)記錄關(guān)鍵碼的比較，若與排序要求相逆，則將二者交換。交換排序冒泡排序排序過(guò)程將第一個(gè)記錄的關(guān)鍵字與第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序r[1].key>r[2].key，則交換；然后比較第二個(gè)記錄與第三個(gè)記錄；依次類推，直至第n-1個(gè)記錄和第n個(gè)記錄比較為止——第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在最后一個(gè)記錄上對(duì)前n-1個(gè)記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個(gè)記錄位置重復(fù)上述過(guò)程，直到“在一趟排序過(guò)程中沒(méi)有進(jìn)行過(guò)交換記錄的操作”為止例4938659776132730

初始關(guān)鍵字3849657613273097

第一趟38496513273076

第二趟384913273065

第三趟3813273049

第四趟132