數(shù)據(jù)結構歷年真題總結

903數(shù)據(jù)結構歷年真題總結

.2010:108

.選擇

?數(shù)據(jù)結構定義

?數(shù)據(jù)D+關系/結構S=DS

?圖的結點的度

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

度0入度1

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

?棧

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

?廣義表的長度

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

和1個子表

?散列表的平均檢索長度

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

賴于表長M

?樹的度和樹的結點的度

?結點的度：結點孩子的數(shù)目

?樹的度：樹中結點最大的度數(shù)稱為樹的度

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

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

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

?二維數(shù)組

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

?連通無向圖

?n個結點的連通無向圖，至少要有n-1個邊。例如A-B-C-D，有4個點，至少3個邊

.關鍵路徑

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

?完全二叉樹

?完全二叉樹：結點編號連續(xù)的二叉樹

?完全二叉樹高K,則至少有2的k-1次方個結點（可以舉例子硬算）

.填空

?棧和隊列

?悔口隊列都是操作受限的線性表,共同點是只運行在固定端點處進行插入刪除

?樹，森林與二叉樹的轉換

?森林轉換二叉樹

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

P172)

（0森林轉化得到的二叉樹

?樹轉換二叉樹

?兄弟結點連線，每個結點只保留與其第一個孩子的連線其他連線都擦去，以樹根為軸順

時針轉45°

(c)抹線(d)旋轉

?DFS

?從某個點開始，一直遍歷到無法遍歷的點，再沿著之前遍歷的軌跡退回，退回到能夠遍歷

未訪問結點的結點停止，繼續(xù)重復上述操作

?完全二叉樹

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

(n+D

?廣義表的操作

?tail:tail是取出來的永遠是一個表(結果外面還要套一對括號)

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

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

?最小生成樹

?最小生成樹是圖的應用，從圖生成一個樹，該樹包括盡可能少的邊

?Prim:每次選與當前頂點集中距離最近的頂點納入考量，適合邊稠密的圖

?kruskal:全局選邊上權重最小的點，不構成回路則加入，構成則舍棄，適合邊稀疏頂點多

的圖

?快速排序

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

?樹的遍歷

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

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

?簡答

.二分蟄找

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

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

?應用

?拓撲排序

?每次輸出一個沒有入度的點，可以用來判斷是否有回路

?B-樹插入

?先按照二叉排序樹的比較，找到位置將結點插入

?插入后判斷是否滿足B-樹的階，比如3階的B-樹中，每個結點最多有2個元素（3個指針）

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

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

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

移動到24旁邊，26和37裂開分居左右

?比如再插入85,原本應該再g結點上617085不滿足，70上移，61和85裂開，得到這

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

I312I26851

5061QO

?哈夫曼樹

?哈夫曼樹建立

?每次選擇最小權重結點構建成

?帶權路徑長度

?WPL是每個結點*（根到該結點走了幾個邊）的求和

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

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

?排序

?直接插入排序

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

?快速排序

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

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

個步驟

?堆排序

?初始化堆

?調整堆，如果要從小到大排序，則調整成大根堆，如果從大到小，則調整成小根堆

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

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

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

?o(nlogn)

?程序題

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

值從大到小排列

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

照右根左的順序遍歷即可

voidsearch(BiTree*t)

(

//空BST則直接返回false

if(t==NULL){

returnfalse;

)

//按右根左順序遍歷BST

else(

search(t->rchild);

visit(t);

search(t->lchild);

}

}

?設L是一個帶頭結點的非遞減有序單鏈表的表頭指針，試設計一算法，將元素

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

?遍歷該鏈表，上徽大小，當e比該元素大時則繼續(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)鏈表的刪除

?單鏈表插入：先連再改，待插入結點指向后繼結點s->next=p->next,前驅結點指向待插

入結點p->next=s

?單鏈表刪除：先連再改q指向被刪除結點q=p->next,前驅結點指向后繼結點p-

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

?雙鏈表插入：先改后繼，再改前驅。待插入結點指向后繼s->next=p->next,后繼結點指

向待插入結點p->next->prior=s,待插入結點指向前驅s->prior=p,前驅指向待插入結

點p->next=s

?雙鏈表刪除：先前驅指后繼，再后繼指前驅

?棧

?數(shù)據(jù)結構的概念辨析

?錯誤：因為隊列只允許再一端插入且再另一端刪除，因此一定是順序表

?隊列是線性表(線性結構)，不一定是順序表(順序存儲)，可以是鏈隊列

?錯誤：二維數(shù)組的每個元素都有兩個前驅結點和兩個后繼結點

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

?線性表除了第一個元素外，有且僅一個前驅；除了最后一個元素之外，有且僅一個后繼

?因此這里，二維數(shù)組的第一個元素，沒有前驅結點；二維數(shù)組最后一個元素，沒有后繼

結點

?錯誤：鏈接存儲是一種緊湊結構

?鏈式存儲密度低，內存中可以不必連續(xù)，是不緊湊的

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

?一維數(shù)組就是線性表的順序實現(xiàn)

.括號匹配的應用

?括號匹配是棧的應用之一

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

?樹的遍歷是指按照某種方式訪問每個結點，且僅訪問一次。二叉樹的前中后序遍歷其實是

一樣的，只不過樹變成了二叉樹，例如下面的樹和對應的二叉樹

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

序遍歷一致。

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

序遍歷一致。

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

?森林的遍歷P173

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

棵樹之后的森林

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

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

.廣義表

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

（用了tail先不管，外面套個括號先，再寫里面的內容）

.十字鏈表

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

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

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

間復雜度）

a）

首元結點

datafirstinfirstout

普通結點

tailvexheadvexhlinktlinkinfo

?鄰接多重表：無向圖

a）b）

首元結點

datafirstedge

普通結點

markivexilinkjvexjlinkinfo

?直接插入排序

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

一共n-1個元素要比）

?數(shù)據(jù)結構概念辨析

?鏈表

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

.填空

?鏈表頭結點的作用

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

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

?數(shù)組

?算錯了。。。

?樹的表示法

?樹的表示法即樹的存儲結構P170-171

?雙親表示法

?孩子表示法

?孩子兄弟表示法

?二叉樹結點數(shù)計算

?二叉樹只有度為0,1,2的結點

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

?二叉樹深度計算

?N個結點的二叉樹，最多N層（單支樹），最少向上取整Iog2（n+1）層（完全二叉樹）

?多叉樹計算

?T具有n個結點的K叉樹，每個結點都有K個指針域，則共有幾個空指針？

?有n個結點，所以共有n*k個指針，每個結點（除了根）都會占用其父結點一個指針域,

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

?連通無向圖

.簡答

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

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

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

?應用

?散列查找

?散列查找，計算H值，然后探測，一直到表空的地方就行，算ASL的時候可以直接把每個

元素計算和探測幾次求和，再除以關鍵字數(shù)目

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

?無向圖用圓括號其中

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

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

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

?各排序的比較

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

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

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

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

?二叉樹

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

?程序

?有一個帶頭結點的單鏈表，設計一函數(shù)將其拆分成兩

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

個帶頭結點的單鏈表A和B,正序鏈表A={al,a2，…,an},逆序鏈表

B={bn,bn-1bl},要求鏈表A使用鏈表L的頭結點

typedefstruttList{

intdata;//或疇彳

structList*next;//指針域

}List)

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

intcount=1;//count析漢苛作

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

List*te?p;//保存偶數(shù)結點的岫時指針

headB->next=NULL；

while(p->next!=NULL){

//遍歷

if(count%2==0){

//偶數(shù)結點移動至此eadB中,頭插法

temp=p>next->next;

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

headB->next=p->next;

p->next=temp;

)

else{

//奇數(shù)的時候

p=p->next;

)

count++;

)

headA=headL;

)

.假設用單鏈表方式存儲整數(shù)序列，如下形式，請編寫一個遞歸算法，對該鏈表

進行操作，重復結點（值相同的結點），僅保留第一個，最后返回新鏈表的首

地址。

NODE*delsame_3(NODEahead)

{

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

if(head->next=rJULL)returnhead;

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

向鏈表倒數(shù)第二個結點—

p=head->next;

while(pl=NULL)

{

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

(

//如果當前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

.選擇

.緒論

?算法的空間復雜度是算法要耗費的存儲空間

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

.線性表

?常插入刪除可以用鏈表結構，在表尾插入刪除順序鏈表都可以，需要隨機訪問，插入指定

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

.棧在表達式求值中的應用

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

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

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

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

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

個元素取出來，進行操作，然后壓回去（看王道P92）

?數(shù)組

?死算即可

?二叉樹

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

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

入對應的位置，例如給定[731015912],可以看到從任意結點到根不一定是有序

的

?哈夫曼樹，選所有結點中最小的兩個構成新結點，并將其加入結點列表，接下來每次在

結點列表中選擇最小的兩個構成新結點，直到?jīng)]有結點，可以看到右側也不一定是有序

的

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

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

?B+樹：B-樹的改進，葉子上面那層結點之間構成了鏈表

1235^9689111315

?完全二叉樹

?某結點沒有左孩子，該結點一定是葉子

?平衡二叉樹

?平衡因子BF計算：左子樹高度-右子樹高度（平衡時BF只有0,1,-1）

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

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

RL

?線索二叉樹

?把二叉樹中，沒有用的空指針，當成線索，來指向先序/中序/后序遍歷的前驅或后繼。n個

結點的線索二叉樹，包括n+1個線索。（n個結點，有2n個指針，然后其中n-1個指針

被用來當指向孩子的指針（即樹有n個結點，應該有n-1個邊，則有2n-n+l=n+l個線

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

?二分蟄找

?排序算法比較

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

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

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

.填空

?數(shù)據(jù)的存儲結構

?數(shù)據(jù)的存儲結構，又叫映像，也叫物理結構，包括數(shù)據(jù)元素的表示和關系的表示

?循環(huán)隊列

?循環(huán)隊列的元素個數(shù)：(rear+M-front)modM(M是表長)

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

M==front,隊空即rear==front

?廣義表

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

?樹的計算

?算錯了。。。樹的結點個數(shù)=樹所有結點的度+1

?哈夫曼樹

?畫個哈夫曼樹就好

?B-樹

?m階的B-樹，每個結點最多有m-1個元素，有m個指針。

?單個結點2個數(shù)字則有3個指針，是3階段【指針,A,指針B指針】

?冒泡排序和堆排序

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

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

.簡答

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

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

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

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

對象，關系和操作三部分組成

?應用

?二叉排序樹

?BST樹建立規(guī)則，按順序讀取，然后大小比較，比該結點大的進入右側，比結點小的進入

左側

?鄰接矩陣和最小生成樹

?鄰接矩陣

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

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

?柘撲排序和二叉樹轉換森林

?二叉樹轉化成森林，先拆成一堆二叉樹,然后對每個二叉樹恢復成普通的樹（右孩子變成

右兄弟，左孩子不動）

?快速排序和堆排序

?同10年

.程序

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

請設計算法去除重復部分，例如有線性表7-10-10-21-30-42-42-42-51-70,

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

2012程序設計題

1.單鏈表去重

voidfind（node*head）{

//定文商個指計

node，p,q;

//一開始指向頭結點

p=q=head;

//開始遍歷單修表

while（p->nextlaNULLX

//q指向p的后一個

q=p->next;

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

while（q->data==p->data）//魏，,過所有與p一樣的結點,直到屋1一；

//q往看再指向一個

q=q->next;

//p再指向q,即把中間一大堆一樣的結點都給跳過了

p->next=q;

p=q;

）

}

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

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

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

#include<iostream>

usingnamespacestd;

#definen20

voidmain(){

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

inti=0;

intm;〃中間變量

intj=n;

cout<<”請輸入n個數(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ù)結構分成：線性結構和非線性結構

?圖的存儲

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

表

?鄰接多重表

a)

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

一次

?鄰接多重表首元結點

datafirstedge

?臨界多重表其他結點

markivexilinkjvexjlinkinfo

?mark:標志域，用于標記此節(jié)點是否被操作過，例如在遍歷時，mark域為0表示

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

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

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

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

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

?雙向鏈表

?雙鏈表插入結點，需要更改4個指針，前驅的next,后繼的prior,以及插入結點的next

和prior指針

?圖的回路

?用拓撲排序可以判斷回路

?冒泡排序

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

.線性表

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