數(shù)據(jù)結(jié)構(gòu)歷年真題總結(jié)

903數(shù)據(jù)結(jié)構(gòu)歷年真題總結(jié)

.2010:108

.選擇

?數(shù)據(jù)結(jié)構(gòu)定義

?數(shù)據(jù)D+關(guān)系/結(jié)構(gòu)S=DS

?圖的結(jié)點(diǎn)的度

?有向圖：A->B,A的出度1（從A出去的弧的數(shù)目）入度0（進(jìn)入A的弧的數(shù)目）B的出

度0入度1

?無向圖：A-B-C,B的度是2（和某結(jié)點(diǎn)相連的邊數(shù)）

?棧

?棧的序列，記住先入棧的后出棧即可

?廣義表的長(zhǎng)度

?廣義表的長(zhǎng)度是指廣義表中原子/子表的數(shù)目，例如T=（a,（c,s）,b）長(zhǎng)度3,包含2個(gè)原子

和1個(gè)子表

?散列表的平均檢索長(zhǎng)度

?散列表的平均查找長(zhǎng)度ASL依賴于裝填因子影響,不直接依賴表元素個(gè)數(shù)N,也不直接依

賴于表長(zhǎng)M

?樹的度和樹的結(jié)點(diǎn)的度

?結(jié)點(diǎn)的度：結(jié)點(diǎn)孩子的數(shù)目

?樹的度：樹中結(jié)點(diǎn)最大的度數(shù)稱為樹的度

.樹中的結(jié)點(diǎn)數(shù)=所有結(jié)點(diǎn)的度數(shù)之和+1,具體做題可以設(shè)度0結(jié)點(diǎn)有n0個(gè)，度1結(jié)點(diǎn)有1

個(gè)…，則可以根據(jù)題目得到兩個(gè)式子，一個(gè)是樹中結(jié)點(diǎn)數(shù)=0*n0+l*nl+...+m*nm+l,另

一個(gè)是樹中結(jié)點(diǎn)數(shù)=n0+nl+n2+...nm,聯(lián)立求解即可

?二維數(shù)組

?公式記不住就死算，注意從0開始還是1開始

?連通無向圖

?n個(gè)結(jié)點(diǎn)的連通無向圖，至少要有n-1個(gè)邊。例如A-B-C-D，有4個(gè)點(diǎn)，至少3個(gè)邊

.關(guān)鍵路徑

?關(guān)鍵路徑是指事件節(jié)點(diǎn)網(wǎng)絡(luò)（AOE網(wǎng)）中，從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑

?完全二叉樹

?完全二叉樹：結(jié)點(diǎn)編號(hào)連續(xù)的二叉樹

?完全二叉樹高K,則至少有2的k-1次方個(gè)結(jié)點(diǎn)（可以舉例子硬算）

.填空

?棧和隊(duì)列

?悔口隊(duì)列都是操作受限的線性表,共同點(diǎn)是只運(yùn)行在固定端點(diǎn)處進(jìn)行插入刪除

?樹，森林與二叉樹的轉(zhuǎn)換

?森林轉(zhuǎn)換二叉樹

?森林中每棵樹轉(zhuǎn)換成二叉樹，第二顆樹接到第一顆樹的右孩子處，以此類推（王道書

P172)

（0森林轉(zhuǎn)化得到的二叉樹

?樹轉(zhuǎn)換二叉樹

?兄弟結(jié)點(diǎn)連線，每個(gè)結(jié)點(diǎn)只保留與其第一個(gè)孩子的連線其他連線都擦去，以樹根為軸順

時(shí)針轉(zhuǎn)45°

(c)抹線(d)旋轉(zhuǎn)

?DFS

?從某個(gè)點(diǎn)開始，一直遍歷到無法遍歷的點(diǎn)，再沿著之前遍歷的軌跡退回，退回到能夠遍歷

未訪問結(jié)點(diǎn)的結(jié)點(diǎn)停止，繼續(xù)重復(fù)上述操作

?完全二叉樹

?N個(gè)結(jié)點(diǎn)的完全二叉樹,葉子結(jié)點(diǎn)的個(gè)數(shù)為向上取整(n/2),高度是向上取整log以2為底

(n+D

?廣義表的操作

?tail:tail是取出來的永遠(yuǎn)是一個(gè)表(結(jié)果外面還要套一對(duì)括號(hào))

?head:取廣義表第一個(gè)元素(可以是原子也可以是表)

?例如LS=((a,b,c),(d,e,f)),head(LS)=(a,b,c),而tail(LS)=((d,e,f))

?最小生成樹

?最小生成樹是圖的應(yīng)用，從圖生成一個(gè)樹，該樹包括盡可能少的邊

?Prim:每次選與當(dāng)前頂點(diǎn)集中距離最近的頂點(diǎn)納入考量，適合邊稠密的圖

?kruskal:全局選邊上權(quán)重最小的點(diǎn)，不構(gòu)成回路則加入，構(gòu)成則舍棄，適合邊稀疏頂點(diǎn)多

的圖

?快速排序

?選Pivot,high,low,先從high開始往前掃，確定樞軸值前面的元素

?樹的遍歷

?前序中任何T+中序，可以確定一個(gè)樹

?根左右前序，左根右中序，左右根后序

?簡(jiǎn)答

.二分蟄找

?比較次數(shù)：向上取整Iog2（n+1）

?要求：原本的順序表已經(jīng)有序

?應(yīng)用

?拓?fù)渑判?/p>

?每次輸出一個(gè)沒有入度的點(diǎn)，可以用來判斷是否有回路

?B-樹插入

?先按照二叉排序樹的比較，找到位置將結(jié)點(diǎn)插入

?插入后判斷是否滿足B-樹的階，比如3階的B-樹中，每個(gè)結(jié)點(diǎn)最多有2個(gè)元素（3個(gè)指針）

?如果滿足ok,比如插入30,這是一個(gè)3階的B-樹

?如果不滿足，先插入，然后將該結(jié)點(diǎn)中間元素上升到父結(jié)點(diǎn)，并從中間裂開。比如插入26,

發(fā)現(xiàn)會(huì)再30旁邊，這個(gè)結(jié)點(diǎn)有3個(gè)元素了（4個(gè)指針）不滿足3階，所以中間元素30上

移動(dòng)到24旁邊，26和37裂開分居左右

?比如再插入85,原本應(yīng)該再g結(jié)點(diǎn)上617085不滿足，70上移，61和85裂開，得到這

個(gè)情況，然后發(fā)現(xiàn)e又不符合，70再上移動(dòng)，53和90裂開，得到下圖2

I312I26851

5061QO

?哈夫曼樹

?哈夫曼樹建立

?每次選擇最小權(quán)重結(jié)點(diǎn)構(gòu)建成

?帶權(quán)路徑長(zhǎng)度

?WPL是每個(gè)結(jié)點(diǎn)*（根到該結(jié)點(diǎn)走了幾個(gè)邊）的求和

?例如上面的圖WPL=（9+12+15）*2+6*3+（3+5）*4=122,即abf三點(diǎn)在第三層

要2個(gè)邊，c再第四層要3個(gè)邊，de在第五層要4個(gè)邊，在求和即可

?排序

?直接插入排序

?每一趟將一個(gè)元素插入到最終排序好的位置，。（（1人2）

?快速排序

?假設(shè)從小到大排，選第一個(gè)元素作為pivot,后面設(shè)立low和high，先high往前掃描，

直到比pivot指的元素小，則換位，再low往后掃，直到比pivot值大則換位，重復(fù)兩

個(gè)步驟

?堆排序

?初始化堆

?調(diào)整堆，如果要從小到大排序，則調(diào)整成大根堆，如果從大到小，則調(diào)整成小根堆

?假設(shè)從小到大排序，要求大根堆，將堆頂元素與末尾元素進(jìn)行交換，使末尾元素最大。

然后繼續(xù)調(diào)整堆，再將堆頂元素與末尾元素交換，得到第二大元素。如此反復(fù)進(jìn)行交換、

重建、交換，最終遍歷堆的結(jié)果即為從小到大，可參考圖解堆排序

?o(nlogn)

?程序題

?試用c語言編寫一介遍歷二叉直找樹的算法，要求遍歷過程恰好按照結(jié)點(diǎn)的鍵

值從大到小排列

?二叉排序樹，又叫二叉查找樹BST,左子樹<根<右子樹，本題可以參考二叉樹的遍歷，按

照右根左的順序遍歷即可

voidsearch(BiTree*t)

(

//空BST則直接返回false

if(t==NULL){

returnfalse;

)

//按右根左順序遍歷BST

else(

search(t->rchild);

visit(t);

search(t->lchild);

}

}

?設(shè)L是一個(gè)帶頭結(jié)點(diǎn)的非遞減有序單鏈表的表頭指針，試設(shè)計(jì)一算法，將元素

e插入到鏈表L中合適位置，使該鏈表仍然非遞減有序

?遍歷該鏈表，上徽大小，當(dāng)e比該元素大時(shí)則繼續(xù)，小則停止，在該位置插入

//定義單鏈表的表頭指針

structLinkList{

intdata;

LinkList*next;

)*L；

〃遍歷鏈表以插入

voidinsert(LinkList*newNode){

LinkList*temp=L;

//遍歷

while(temp->next!=NULL){

if(temp->next->data>newNode->data){

break;

}

temp=temp->next;

}

//把newnode插入到temp后面

newNode->next=temp->next;

temp->next=newNode;

)

.2011:105

.選擇

?雙循環(huán)鏈表的刪除

?單鏈表插入：先連再改，待插入結(jié)點(diǎn)指向后繼結(jié)點(diǎn)s->next=p->next,前驅(qū)結(jié)點(diǎn)指向待插

入結(jié)點(diǎn)p->next=s

?單鏈表刪除：先連再改q指向被刪除結(jié)點(diǎn)q=p->next,前驅(qū)結(jié)點(diǎn)指向后繼結(jié)點(diǎn)p-

>next=q->next,釋放q指針。

?雙鏈表插入：先改后繼，再改前驅(qū)。待插入結(jié)點(diǎn)指向后繼s->next=p->next,后繼結(jié)點(diǎn)指

向待插入結(jié)點(diǎn)p->next->prior=s,待插入結(jié)點(diǎn)指向前驅(qū)s->prior=p,前驅(qū)指向待插入結(jié)

點(diǎn)p->next=s

?雙鏈表刪除：先前驅(qū)指后繼，再后繼指前驅(qū)

?棧

?數(shù)據(jù)結(jié)構(gòu)的概念辨析

?錯(cuò)誤：因?yàn)殛?duì)列只允許再一端插入且再另一端刪除，因此一定是順序表

?隊(duì)列是線性表(線性結(jié)構(gòu))，不一定是順序表(順序存儲(chǔ))，可以是鏈隊(duì)列

?錯(cuò)誤：二維數(shù)組的每個(gè)元素都有兩個(gè)前驅(qū)結(jié)點(diǎn)和兩個(gè)后繼結(jié)點(diǎn)

?數(shù)組是線性表的推廣，一維數(shù)組是線性表，二維數(shù)組是元素是線性表的線性表

?線性表除了第一個(gè)元素外，有且僅一個(gè)前驅(qū)；除了最后一個(gè)元素之外，有且僅一個(gè)后繼

?因此這里，二維數(shù)組的第一個(gè)元素，沒有前驅(qū)結(jié)點(diǎn)；二維數(shù)組最后一個(gè)元素，沒有后繼

結(jié)點(diǎn)

?錯(cuò)誤：鏈接存儲(chǔ)是一種緊湊結(jié)構(gòu)

?鏈?zhǔn)酱鎯?chǔ)密度低，內(nèi)存中可以不必連續(xù)，是不緊湊的

?正確：一維數(shù)組是一種順序表

?一維數(shù)組就是線性表的順序?qū)崿F(xiàn)

.括號(hào)匹配的應(yīng)用

?括號(hào)匹配是棧的應(yīng)用之一

?樹的遍歷（不是二叉樹的遍歷）

?樹的遍歷是指按照某種方式訪問每個(gè)結(jié)點(diǎn)，且僅訪問一次。二叉樹的前中后序遍歷其實(shí)是

一樣的，只不過樹變成了二叉樹，例如下面的樹和對(duì)應(yīng)的二叉樹

?先根遍歷：若非空，先訪問根，再依次遍歷根的每棵子樹。與將樹轉(zhuǎn)化成二叉樹后的先

序遍歷一致。

?后根遍歷：若非空，先依次遍歷根的每棵子樹，再訪問根.與將樹轉(zhuǎn)化成二叉樹后的中

序遍歷一致。

?上圖的先根遍歷結(jié)果是ABEFCD,后根遍歷結(jié)果是EFBCGDA。

?森林的遍歷P173

?先序遍歷：訪問第一棵樹的根，再先序遍歷第一棵樹中根的子樹森林，再遍歷除去第一

棵樹之后的森林

?后續(xù)遍歷：中序遍歷第一顆子樹的根節(jié)點(diǎn)的字?jǐn)?shù)森林，再訪問第一顆樹的根，再遍歷出

去第一棵樹的根節(jié)點(diǎn)

.廣義表

?廣義表head獲得的是第一個(gè)元素（可以是子表也可以是原子），tail獲得的一定是子表

（用了tail先不管，外面套個(gè)括號(hào)先，再寫里面的內(nèi)容）

.十字鏈表

?十字鏈表是圖的一種存儲(chǔ)方法（表示方法）P218

?鄰接矩陣：頂點(diǎn)數(shù)平方的空間復(fù)雜度

?鄰接表：無向圖（二倍邊數(shù)+頂點(diǎn)數(shù)的空間復(fù)雜度），有向圖（一倍邊數(shù)+頂點(diǎn)數(shù)的空

間復(fù)雜度）

a）

首元結(jié)點(diǎn)

datafirstinfirstout

普通結(jié)點(diǎn)

tailvexheadvexhlinktlinkinfo

?鄰接多重表：無向圖

a）b）

首元結(jié)點(diǎn)

datafirstedge

普通結(jié)點(diǎn)

markivexilinkjvexjlinkinfo

?直接插入排序

?直接插入排序比較次數(shù)最少（當(dāng)已經(jīng)基本有序時(shí)），只需要比較n-1（每次都比較1次，

一共n-1個(gè)元素要比）

?數(shù)據(jù)結(jié)構(gòu)概念辨析

?鏈表

?鏈表動(dòng)態(tài)分配存儲(chǔ)，空間靈活，插入刪除很快，查找慢（不能隨機(jī)訪問）

.填空

?鏈表頭結(jié)點(diǎn)的作用

?使得在鏈表頭部的操作如插入刪除等和在后面的操作一致

?使得非空和空鏈表操作一致

?數(shù)組

?算錯(cuò)了。。。

?樹的表示法

?樹的表示法即樹的存儲(chǔ)結(jié)構(gòu)P170-171

?雙親表示法

?孩子表示法

?孩子兄弟表示法

?二叉樹結(jié)點(diǎn)數(shù)計(jì)算

?二叉樹只有度為0,1,2的結(jié)點(diǎn)

?二叉樹有n0=n2+1即度0結(jié)點(diǎn)數(shù)目=度2結(jié)點(diǎn)數(shù)目+1

?二叉樹深度計(jì)算

?N個(gè)結(jié)點(diǎn)的二叉樹，最多N層（單支樹），最少向上取整Iog2（n+1）層（完全二叉樹）

?多叉樹計(jì)算

?T具有n個(gè)結(jié)點(diǎn)的K叉樹，每個(gè)結(jié)點(diǎn)都有K個(gè)指針域，則共有幾個(gè)空指針？

?有n個(gè)結(jié)點(diǎn)，所以共有n*k個(gè)指針，每個(gè)結(jié)點(diǎn)（除了根）都會(huì)占用其父結(jié)點(diǎn)一個(gè)指針域,

所以有n-1個(gè)被占用，所以共有nk-n+1個(gè)空指針

?連通無向圖

.簡(jiǎn)答

?隊(duì)列，鏈隊(duì)列，循環(huán)隊(duì)列

?隊(duì)列是只能在一端插入，另一端刪除的操作受限的線性表

?鏈隊(duì)列是使用鏈表存儲(chǔ)的隊(duì)列，循環(huán)隊(duì)列是使用順序存儲(chǔ)的隊(duì)列

?應(yīng)用

?散列查找

?散列查找，計(jì)算H值，然后探測(cè)，一直到表空的地方就行，算ASL的時(shí)候可以直接把每個(gè)

元素計(jì)算和探測(cè)幾次求和，再除以關(guān)鍵字?jǐn)?shù)目

?深度優(yōu)先生成樹

?無向圖用圓括號(hào)其中

G1=(V1,E1),Vl={a,b,c,d},El={(a,b),(a,c),(a,d)1(b,d),(c,d)}

?有向圖用尖括號(hào)G2=(V2,E2),其中V2={1,2,3},E2={<1,2>,<1,3>,<2,3>,<3,1>}

?先畫圖，再根據(jù)DFS遍歷圖，然后繪制成樹即可(遍歷順序不唯一)

?各排序的比較

?空間復(fù)雜度：堆排序需要。(1),快速排序需要。(nlog2n)，歸并排序需要。(n)

?穩(wěn)定性：歸并排序穩(wěn)定，堆排序不穩(wěn)定

?平均情況：快排平均最快

?最壞情況且內(nèi)存節(jié)約：堆排序

?二叉樹

?空樹和只有根的樹也是二叉樹的類型

?程序

?有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，設(shè)計(jì)一函數(shù)將其拆分成兩

L={alfbl,a2,b2…,an,bn},

個(gè)帶頭結(jié)點(diǎn)的單鏈表A和B,正序鏈表A={al,a2，…,an},逆序鏈表

B={bn,bn-1bl},要求鏈表A使用鏈表L的頭結(jié)點(diǎn)

typedefstruttList{

intdata;//或疇彳

structList*next;//指針域

}List)

voidsplit(List*&headL,List*&headA,List*&headB){

intcount=1;//count析漢苛作

List*p=headL;//p指向L

List*te?p;//保存偶數(shù)結(jié)點(diǎn)的岫時(shí)指針

headB->next=NULL；

while(p->next!=NULL){

//遍歷

if(count%2==0){

//偶數(shù)結(jié)點(diǎn)移動(dòng)至此eadB中,頭插法

temp=p>next->next;

p->next->next=headB->next;

headB->next=p->next;

p->next=temp;

)

else{

//奇數(shù)的時(shí)候

p=p->next;

)

count++;

)

headA=headL;

)

.假設(shè)用單鏈表方式存儲(chǔ)整數(shù)序列，如下形式，請(qǐng)編寫一個(gè)遞歸算法，對(duì)該鏈表

進(jìn)行操作，重復(fù)結(jié)點(diǎn)（值相同的結(jié)點(diǎn)），僅保留第一個(gè)，最后返回新鏈表的首

地址。

NODE*delsame_3(NODEahead)

{

NODE*p,*teflp4>ead;〃速以防head不斷變化,但初始時(shí)tenp都指向新head

if(head->next=rJULL)returnhead;

head->next=delSane_3(head->next)//.'/閂到nead->next指向尾結(jié)點(diǎn),此晰end指

向鏈表倒數(shù)第二個(gè)結(jié)點(diǎn)—

p=head->next;

while(pl=NULL)

{

if(head->data=p->data)

(

//如果當(dāng)前head的數(shù)據(jù)和后面的數(shù)據(jù)一樣，則飄除

temp->next=p->next;

free(p);

p=temp->next;

}else{

//繼續(xù)

p=p->next;

temp=temp->next;

)

}

returnhead;

}

.2012:105

.選擇

.緒論

?算法的空間復(fù)雜度是算法要耗費(fèi)的存儲(chǔ)空間

?算法的有窮性：一個(gè)算法必須在執(zhí)行有窮步后結(jié)束，且每一步必須在有窮時(shí)間內(nèi)完成

.線性表

?常插入刪除可以用鏈表結(jié)構(gòu)，在表尾插入刪除順序鏈表都可以，需要隨機(jī)訪問，插入指定

位置可以用順序存儲(chǔ)，需要訪問前驅(qū)后繼可以用雙鏈表/循環(huán)鏈表等

.棧在表達(dá)式求值中的應(yīng)用

?如果是中綴表達(dá)式，需要操作數(shù)榭口操作符棧，分別讀數(shù)字和操作符。讀數(shù)字壓入數(shù)字棧，

讀操作符壓入操作符棧，如果讀到操作符比目前棧頂操作符優(yōu)先級(jí)高，則繼續(xù)；如果讀到

的操作符比操作符棧頂?shù)牟僮鞣麅?yōu)先級(jí)低，則棧頂操作符出來，數(shù)字棧出兩個(gè)元素進(jìn)行操

作得到結(jié)果壓回去，循環(huán)上述過程即可如s:〃guyon/article/details/89671260

?如果是后綴表達(dá)式，直接一個(gè)棧掃描表達(dá)式即可，掃到數(shù)字則進(jìn)，掃到操作符則將棧頂兩

個(gè)元素取出來，進(jìn)行操作，然后壓回去（看王道P92）

?數(shù)組

?死算即可

?二叉樹

?若二叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹是？

?二叉排序樹指左小于根小于右的樹，建立的時(shí)候是依次讀取元素，然后按照大小比較進(jìn)

入對(duì)應(yīng)的位置，例如給定[731015912],可以看到從任意結(jié)點(diǎn)到根不一定是有序

的

?哈夫曼樹，選所有結(jié)點(diǎn)中最小的兩個(gè)構(gòu)成新結(jié)點(diǎn)，并將其加入結(jié)點(diǎn)列表，接下來每次在

結(jié)點(diǎn)列表中選擇最小的兩個(gè)構(gòu)成新結(jié)點(diǎn)，直到?jīng)]有結(jié)點(diǎn)，可以看到右側(cè)也不一定是有序

的

?堆，有大根堆和小根堆（即一種特殊的完全二叉樹），如果是大根堆，即根必須大于左

右兩個(gè)孩子，如果從任意點(diǎn)往根走，必然是小到大的順序。（小根堆同樣）

?B+樹：B-樹的改進(jìn)，葉子上面那層結(jié)點(diǎn)之間構(gòu)成了鏈表

1235^9689111315

?完全二叉樹

?某結(jié)點(diǎn)沒有左孩子，該結(jié)點(diǎn)一定是葉子

?平衡二叉樹

?平衡因子BF計(jì)算：左子樹高度-右子樹高度（平衡時(shí)BF只有0,1,-1）

?題目中說插入結(jié)點(diǎn)之后，A的左孩子BF=O,右孩子為1（即右孩子的左子樹比右子樹高

1）,所以可以推出插入點(diǎn)在A的右孩子的左子樹上，造成A不平衡，因此是右左型，即

RL

?線索二叉樹

?把二叉樹中，沒有用的空指針，當(dāng)成線索，來指向先序/中序/后序遍歷的前驅(qū)或后繼。n個(gè)

結(jié)點(diǎn)的線索二叉樹，包括n+1個(gè)線索。（n個(gè)結(jié)點(diǎn)，有2n個(gè)指針，然后其中n-1個(gè)指針

被用來當(dāng)指向孩子的指針（即樹有n個(gè)結(jié)點(diǎn)，應(yīng)該有n-1個(gè)邊，則有2n-n+l=n+l個(gè)線

索）（指向空的也是線索）

?二分蟄找

?排序算法比較

?I:啜次數(shù)與序列初態(tài)無關(guān)的是：簡(jiǎn)單選擇排序(每次選擇最小)

?直接插入排序(需要比較，序列初態(tài)影響比較次數(shù))，冒泡排序同樣，序列初態(tài)如果已經(jīng)

基本有序，則比較次數(shù)很少，堆排序在建堆和調(diào)整堆時(shí)候需要比較，這和初始順序也有關(guān)

.填空

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

?數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，又叫映像，也叫物理結(jié)構(gòu)，包括數(shù)據(jù)元素的表示和關(guān)系的表示

?循環(huán)隊(duì)列

?循環(huán)隊(duì)列的元素個(gè)數(shù)：(rear+M-front)modM(M是表長(zhǎng))

?循環(huán)隊(duì)列中，front指隊(duì)頭，rear指隊(duì)尾后一個(gè)(具體題目具體看)，隊(duì)滿是rear+1mod

M==front,隊(duì)空即rear==front

?廣義表

?廣義表深度是指廣義表的括號(hào)嵌套有幾層，例如(a,(a,b),d,e,((i,j),k)),深度是3。

?樹的計(jì)算

?算錯(cuò)了。。。樹的結(jié)點(diǎn)個(gè)數(shù)=樹所有結(jié)點(diǎn)的度+1

?哈夫曼樹

?畫個(gè)哈夫曼樹就好

?B-樹

?m階的B-樹，每個(gè)結(jié)點(diǎn)最多有m-1個(gè)元素，有m個(gè)指針。

?單個(gè)結(jié)點(diǎn)2個(gè)數(shù)字則有3個(gè)指針，是3階段【指針,A,指針B指針】

?冒泡排序和堆排序

?冒泡排序在最好的情況下，即基本有序的情況下，交換的次數(shù)是。次

?堆排序在最壞的情況下，需要比較向下取整nlog2n

.簡(jiǎn)答

?數(shù)據(jù)類型和抽象數(shù)據(jù)類型

?數(shù)據(jù)類型是一個(gè)值得集合和定義在該集合得一組操作的總稱

?抽象數(shù)據(jù)類型指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。僅取決于邏輯特性，和表

示實(shí)現(xiàn)無關(guān)，抽象在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性，范圍比數(shù)據(jù)類型更廣闊，一般包括數(shù)據(jù)

對(duì)象，關(guān)系和操作三部分組成

?應(yīng)用

?二叉排序樹

?BST樹建立規(guī)則，按順序讀取，然后大小比較，比該結(jié)點(diǎn)大的進(jìn)入右側(cè)，比結(jié)點(diǎn)小的進(jìn)入

左側(cè)

?鄰接矩陣和最小生成樹

?鄰接矩陣

?圖（不帶權(quán)）的鄰接矩陣：連著的是I,不連著算0（自己和自己是0）

?網(wǎng)（帶權(quán)圖）的鄰接矩陣：連著的是權(quán)，不連著算8（嚴(yán)書算無窮，別寫0）

?柘撲排序和二叉樹轉(zhuǎn)換森林

?二叉樹轉(zhuǎn)化成森林，先拆成一堆二叉樹,然后對(duì)每個(gè)二叉樹恢復(fù)成普通的樹（右孩子變成

右兄弟，左孩子不動(dòng)）

?快速排序和堆排序

?同10年

.程序

?在一個(gè)遞增有序的線性表中，有數(shù)值相同的元素存在，若存儲(chǔ)方式為單鏈表，

請(qǐng)?jiān)O(shè)計(jì)算法去除重復(fù)部分，例如有線性表7-10-10-21-30-42-42-42-51-70,

去除之后是7-10-21-30-42-70

2012程序設(shè)計(jì)題

1.單鏈表去重

voidfind（node*head）{

//定文商個(gè)指計(jì)

node，p,q;

//一開始指向頭結(jié)點(diǎn)

p=q=head;

//開始遍歷單修表

while（p->nextlaNULLX

//q指向p的后一個(gè)

q=p->next;

//如果p的后一個(gè)所指和當(dāng)前p所指數(shù)據(jù)域一樣

while（q->data==p->data）//魏，,過所有與p一樣的結(jié)點(diǎn),直到屋1一；

//q往看再指向一個(gè)

q=q->next;

//p再指向q,即把中間一大堆一樣的結(jié)點(diǎn)都給跳過了

p->next=q;

p=q;

）

}

?試設(shè)計(jì)算法再On時(shí)間復(fù)雜度內(nèi)，隊(duì)數(shù)組A[0,L...n-l]劃分為左右兩個(gè)部分,

使得左邊的所有元素均為奇數(shù)，右邊都為偶數(shù)，要求輔助空間。1

2.數(shù)組劃分奇偶

#include<iostream>

usingnamespacestd;

#definen20

voidmain(){

intA[n];〃定義整型數(shù)組

inti=0;

intm;〃中間變量

intj=n;

cout<<”請(qǐng)輸入n個(gè)數(shù)”;

for(i=0;i<n;i-?-+){

cin>>A[i];

)

//交換

for(i=0;i<(n/2);i++){

j=n-i；

if(A[i]%2==0){

//前偶后奇則交換

if(A[j]%2!=0){

m=A[j];

A[j]=A[i];

A[i]=m;

)

}

}

)

}

.2013:105

.選擇

?基本概念

?邏輯上將數(shù)據(jù)結(jié)構(gòu)分成：線性結(jié)構(gòu)和非線性結(jié)構(gòu)

?圖的存儲(chǔ)

?無向圖可以用鄰接矩陣，鄰接表，鄰接多重表，有向圖可以用鄰接矩陣，鄰接表，十字鏈

表

?鄰接多重表

a)

?例如里面V1后面接著［01］和［03］gpvl和v2有邊，vl和v4有邊，即邊只存儲(chǔ)

一次

?鄰接多重表首元結(jié)點(diǎn)

datafirstedge

?臨界多重表其他結(jié)點(diǎn)

markivexilinkjvexjlinkinfo

?mark:標(biāo)志域，用于標(biāo)記此節(jié)點(diǎn)是否被操作過，例如在遍歷時(shí)，mark域?yàn)?表示

未被遍歷；mark為1表示該節(jié)點(diǎn)已被遍歷；

?ivex和jvex:數(shù)據(jù)域，分別存儲(chǔ)圖中各邊兩端的頂點(diǎn)所在數(shù)組中的位置下標(biāo);

?ilink:指針域，指向下一個(gè)存儲(chǔ)與ivex有直接關(guān)聯(lián)頂點(diǎn)的節(jié)點(diǎn)；

?jlink:指針域，指向下一個(gè)存儲(chǔ)與jvex有直接關(guān)聯(lián)頂點(diǎn)的節(jié)點(diǎn)；

?info:指針域，用于存儲(chǔ)與該頂點(diǎn)的其他信息，比如無向網(wǎng)中各邊的權(quán)；

?雙向鏈表

?雙鏈表插入結(jié)點(diǎn)，需要更改4個(gè)指針，前驅(qū)的next,后繼的prior,以及插入結(jié)點(diǎn)的next

和prior指針

?圖的回路

?用拓?fù)渑判蚩梢耘袛嗷芈?/p>

?冒泡排序

?冒泡排序的規(guī)則：兩兩比較，小的/大的冒上去/下去

.線性表

?線性表的定義：n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。n可以為0,即空