考研數(shù)據(jù)結(jié)構(gòu)2011年復(fù)習(xí)

2011年11月24日數(shù)據(jù)結(jié)構(gòu)第2

頁《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)重點試題類型（卷面100分）單項選擇題（四選一，每小題2分）30分 考核基本概念和基礎(chǔ)知識。填空題20分，10小題 考核基本概念和簡單算法。簡答題30分，5-6小題 在基本概念和基本算法的基礎(chǔ)上，考察對于常見的基本算法的掌握情況。算法題20分，2-3小題

針對具體的問題，采用C語言，完成整個程序。考察綜合運用知識的能力。第3

頁《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)重點考核重點基本概念與基礎(chǔ)知識基本算法及其運用難度不大，但要求基礎(chǔ)扎實算法設(shè)計的關(guān)鍵是對于基本算法的理解和靈活使用第4

頁《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)重點說明不要求背誦，不要求記憶基本概念的準(zhǔn)確定義，關(guān)鍵是要掌握基本概念的核心。不需要記憶算法的實現(xiàn)細節(jié)，關(guān)鍵是掌握算法的核心思想。簡答題目不需要長篇大論，只要說明關(guān)鍵點就即可。算法設(shè)計要先簡要寫明基本算法，然后再給出程序。第5

頁第一章緒論—基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)：描述數(shù)據(jù)間的邏輯關(guān)系。典型的邏輯結(jié)構(gòu)：集合、線性、樹、圖數(shù)據(jù)的存儲結(jié)構(gòu)：邏輯結(jié)構(gòu)在存儲器中的映象。典型的存儲結(jié)構(gòu)：順序和鏈?zhǔn)紸DT：是對數(shù)據(jù)結(jié)構(gòu)的一種更準(zhǔn)確的抽象描述，它忽略了數(shù)據(jù)結(jié)構(gòu)的具體實現(xiàn)步驟，將更多的注意力放在數(shù)據(jù)的基本操作上，通過基本操作描述數(shù)據(jù)的邏輯關(guān)系。它包括三個部分：數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作。什么是算法的時間復(fù)雜度？如何計算？什么是算法的空間復(fù)雜度？如何計算？第6

頁數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等線性結(jié)構(gòu)非線性結(jié)構(gòu)順序存儲鏈?zhǔn)酱鎯€性表棧隊樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面：緒論—基本概念第7

頁數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指______。

A.數(shù)據(jù)的存儲結(jié)構(gòu)B.數(shù)據(jù)元素的結(jié)構(gòu)C.數(shù)據(jù)的邏輯結(jié)構(gòu)D.數(shù)據(jù)元素之間的關(guān)系答案：A在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的基本單位是______。A.數(shù)據(jù)項B.數(shù)據(jù)類型

C.數(shù)據(jù)元素D.數(shù)據(jù)變量答案：C在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的A.存儲結(jié)構(gòu) B.邏輯結(jié)構(gòu)C.邏輯和物理結(jié)構(gòu) D.物理結(jié)構(gòu)答案：B緒論—練習(xí)題第8

頁下面程序段的時間復(fù)雜度為 for(i=0;i<m;i++)

for(j=0;j<n;j++)

A[i][j]=i*j;A.O(m*m) B.O(m*n)C.O(m+n) D.O(n*n)緒論—練習(xí)題第9

頁第二章線性表—基本概念

線性表是n個具有相同類型的數(shù)據(jù)元素構(gòu)成的有限序列。線性表的存儲鏈序存儲(鏈表)順序存儲(順序表)雙向循環(huán)鏈表單向循環(huán)鏈表單鏈表鏈表的靜態(tài)存儲第10

頁線性表—練習(xí)題線性表的順序存儲結(jié)構(gòu)是通過____方式表示元素之間的關(guān)系。A.后繼元素地址B.元素的存儲順序C.左、右孩子地址D.后繼元素的數(shù)組下標(biāo)答案：B線性鏈表是通過______表示元素之間關(guān)系的。A.后繼元素的地址B.元素的存儲順序C.左、右孩子地址D.元素的相對存儲位置答案：A第11

頁線性表—練習(xí)題在線性表順序存儲結(jié)構(gòu)下，在第i個元素之前插入新元素一般需要______。A.移動元素B.修改頭指針

C.隊頭指針D.申請新的結(jié)點空間答案：A判斷帶有頭結(jié)點的線性鏈表L是否表空的條件是______。A.L.elem=NULLB.L.length=0C.L->next=NULLD.L.listsize=0答案：C第12

頁線性表—練習(xí)題在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)下，插入操作算法______。 A)需要判斷是否表滿

B)需要判斷是否表空 C)不需要判斷是否表滿

D)需要判斷是否表空和表滿答案：C循環(huán)鏈表是一種采用

結(jié)構(gòu)存儲的線性表。A)順序B)索引C)鏈?zhǔn)紻)散列答案：C第13

頁線性表—練習(xí)題用線性鏈表存儲線性表時，要求存儲空間____。A)必須是連續(xù)的

B)連續(xù)不連續(xù)都可以C)部分元素的存儲空間必須是連續(xù)的

D)必須是不連續(xù)的答案：B對于經(jīng)常要存取線性表任意指定位置元素的應(yīng)用，線性表應(yīng)采用____存儲結(jié)構(gòu)。A)順序B)鏈?zhǔn)紺)線性鏈表D)棧答案：A第14

頁線性表—練習(xí)題在p所指向的結(jié)點后插入由q指向的新結(jié)點的語句序列是____。 A)p->next=q;q->next=p->next; B)q=p->next;p->next=q; C)q->next=p->next;p->next=q; D)p=p->next;q->next=p;答案：C從邏輯結(jié)構(gòu)的角度，在線性表中，除第一個元素和最后一個元素外，其他元素都有且僅有____。答案：一個前驅(qū)和一個后繼第15

頁線性表—練習(xí)題請用C語言給出順序表（線性表的順序存儲結(jié)構(gòu)）的類型定義。答案： #defineLIST_INIT_SIZE100//線性表存儲空間的初始分配量#defineLISTINCREMENT10//線性表存儲空間的分配增量typedefstruct{

ElemType*elem;//線性表存儲空間基址

intlength;//當(dāng)前線性表長度

intlistsize;//當(dāng)前分配的表空間大小//（以sizeof(ElemType)為單位）

}SqList;第16

頁線性表—練習(xí)題將兩個非遞減有序的有序單鏈表la和lb歸并為非遞增的有序表。

TypedefstructLNode{intdata; //數(shù)據(jù)域

structLnode*next; //指針域

}LNode,*LinkList;

LinkListla,lb；//單鏈表的頭指針

請用la和lb中的結(jié)點合并生成一個新的非遞增的有序單鏈表lc。合并完成后，la和lb為空鏈表。第17

頁線性表—鏈?zhǔn)酱鎯εc實現(xiàn)已知線性元素以值遞增排列有序，以帶頭單鏈表作存儲結(jié)構(gòu)，下面算法的功能是：刪除表中所有值大于min且小于max的元素（設(shè)表中存在這樣的元素）。請在空缺處填入相應(yīng)的語句或表達式。voiddelete(LinkListL,intmin,intmax){pre=L;p=pre->next;while((①)&&(p->data<=min)){pre=p;p=p->next;}while((p!=null)&&(p->next<max)){②;}}//delete答案：①p!=NULL

②pre->next=p->next;free(p);p=pre->next;第18

頁線性表—鏈?zhǔn)酱鎯εc實現(xiàn)下面算法的功能是：在無頭結(jié)點的線性鏈表L中刪除第i元素結(jié)點,并用e返回其值，StatusListDelete_L(LinkList&L,inti,ElemType&e){p=L;if(i==1)//刪除第1元素結(jié)點{①;}else{j=1;while(②&&j<i-1){p=p->next;++j;}//尋找第i-1

if(!p->next||j>i-1)returnERROR;

③;}returnOK;}答案：①L=L->next;e=p->data;free(p);②p->next!=null;③q=p->next;p->next=q->next;e=q->data;free(q);第19

頁第三章棧和隊列—基本概念棧和隊列是限定插入和刪除只能在表的“端點”進行的線性表。棧和隊列的定義和特點棧的實現(xiàn)（順序棧和鏈棧），如何判斷?？蘸蜅M？如何判斷循環(huán)隊列的隊空和隊滿？棧和隊列的簡單應(yīng)用。第20

頁棧和隊列棧是一種____。A)存取受限的線性結(jié)構(gòu)

B)存取不受限的線性結(jié)構(gòu)C)存取受限的非線性結(jié)構(gòu)

D)存取不受限的非線性結(jié)構(gòu)答案：A隊列操作的原則是____。A)先進先出B)后進先出C)只能進行插入D)只能進行刪除答案：A第21

頁棧和隊列已知一堆棧的進棧序列為：1234，則下列哪個序列為不可能的出棧序列： A)1234B)4321C)2143D)4123答案：D用單鏈表表示的鏈?zhǔn)綏５臈ｍ斠话阍O(shè)在鏈表的______。 A)鏈頭 B)鏈尾 C)鏈頭或鏈尾均可 D)可以任意位置答案：A設(shè)有一個空棧，現(xiàn)輸入序列為1,2,3,4。經(jīng)過push，push，pop，push，pop，push，pop，pop后，輸出序列為______。答案：2341第22

頁棧和隊列在一個鏈隊列中，假定front和rear分別為隊頭和隊尾指針，則插入*s結(jié)點的操作應(yīng)執(zhí)行____。 A)s->next=rear;rear=s;s->next=rear->next; B)

front->next=s;front=s; C)s->next=rear->next;rear->next=s;rear=s; D)

s->next=front;front=s;答案：C向一個指向頭結(jié)點的棧頂指針為hs的鏈棧中插入一個*s結(jié)點時，應(yīng)執(zhí)行____。

A)hs->next=sB)hs=s C)s->next=hs->next;hs->next=s D)s->next=hs;hs=hs->next;答案：C第23

頁棧和隊列循環(huán)隊列Q（設(shè)循環(huán)隊列空間大小為MAXSIZE），進行入隊操作時如何修改隊尾指針?進行出隊操作時如何修改隊頭指針?隊空的判斷條件是什么？隊滿的判斷條件是什么？答案：入隊：rear=(rear+1)%MAXSIZE;Q[rear]=x;出隊：front=(front+1)%MAXSIZE;x=Q[front];隊空：front==rear隊滿：(rear+1)%MAXSIZE==front第24

頁棧和隊列有字符串序列為“3*-y-a/y2”，試?yán)脳⒆址涡蚋臑椤?y-*ay2/-”，請寫出操作步驟。 （可用X代表掃描該字符串過程中順序取一個字符進棧的操作，用S代表從棧中取出一個字符加入到新字符串尾的操作。例如：ABC變?yōu)锽CA，則操作步驟為XXSXSS。）答案：

XSXXXSSSXXSXXSXXSSSS第25

頁數(shù)組和廣義表—基本概念特殊矩陣的壓縮存儲：上三角矩陣、下三角矩陣、三對角矩陣，在行主序和列主序方式下如何進行地址轉(zhuǎn)換？稀疏矩陣：三元組（順序存儲，鏈?zhǔn)酱鎯Γ?，十字鏈表，簡單?yīng)用廣義表：基本定義，存儲結(jié)構(gòu)，基本運算（取表頭，取表尾），如何用廣義表描述其他數(shù)據(jù)結(jié)構(gòu)？第26

頁樹—基本概念樹、二叉樹、森林的基本概念和術(shù)語二叉樹：5條基本性質(zhì)（證明），完全二叉樹和滿二叉樹，鏈?zhǔn)酱鎯晚樞虼鎯Γ?種遍歷算法的基本思想（遞歸和非遞歸），遍歷序列還原二叉樹，線索化，基于遍歷思想的簡單應(yīng)用樹與二叉樹的轉(zhuǎn)換，森林與二叉樹的轉(zhuǎn)換哈夫曼樹：概念，哈夫曼編碼，應(yīng)用（外排序）第27

頁二叉樹—基本概念性質(zhì)1： 在二叉樹的第i

層上至多有2i-1個結(jié)點(i≥1)。性質(zhì)2： 深度為k的二叉樹上至多含2k-1個結(jié)點(k≥1)。性質(zhì)3： 對任何一棵二叉樹，若它含有n0

個葉子結(jié)點、n2個度為

2

的結(jié)點，則必存在關(guān)系式：n0=n2+1第28

頁二叉樹—基本概念兩類特殊的二叉樹滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。完全二叉樹：樹中所含的

n

個結(jié)點和滿二叉樹中編號為1至n的結(jié)點一一對應(yīng)。123456789101112131415abcdefghij第29

頁二叉樹—基本概念性質(zhì)5：

若對含n個結(jié)點的完全二叉樹從上到下且從左至右進行1

至n

的編號，則對完全二叉樹中任意一個編號為i

的結(jié)點：

(1)若i=1，則該結(jié)點是二叉樹的根，無雙親,否則，編號為

i/2

的結(jié)點為其雙親結(jié)點;

(2)若2i>n，則該結(jié)點無左孩子，否則，編號為

2i

的結(jié)點為其左孩子結(jié)點；

(3)若2i+1>n，則該結(jié)點無右孩子結(jié)點，否則，編號為2i+1的結(jié)點為其右孩子結(jié)點。性質(zhì)4： 具有n個結(jié)點的完全二叉樹的深度為

log2n+1。第30

頁二叉樹—基本概念性質(zhì)5：[I/2]ii+12i2i+12i+22i+3i+12i+22i+3i2i2i+1(a)i和i+1結(jié)點在同一層(b)i和i+1結(jié)點不在同一層第31

頁二叉樹—練習(xí)題樹最適合用來表示______。A）有序數(shù)據(jù)元素

B）無序數(shù)據(jù)元素

C）元素之間具有分支層次關(guān)系的數(shù)據(jù)

D）元素之間無聯(lián)系的數(shù)據(jù)答案：C在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊______。A）只有右子樹上的所有結(jié)點

B）只有右子樹上的部分結(jié)點

C）只有左子樹上的所有結(jié)點

D）只有左子樹上的部分結(jié)點答案：A第32

頁二叉樹—練習(xí)題如圖所示的二叉樹的中序序列是____。 A)V6V5V3V4V7V2V1 B)V5V6V3V7V4V2V1

C)V6V5V3V7V4V2V1 D)V6V3V5V1V4V7V2答案：D具有300個節(jié)點的二叉樹，其高度至少應(yīng)為____。A)6B)7C)8D)9答案：D對任何一棵二叉樹，若它有n0個葉子結(jié)點、n2個度為2的結(jié)點，則有：n0=____。答案：n2+1V7V1V6V5V3V2V4第33

頁二叉樹—練習(xí)題使用二叉鏈表存儲二叉樹時，要通過保存每個結(jié)點的

存儲位置，來表示二叉樹結(jié)點之間的結(jié)構(gòu)關(guān)系。答案：物理/左右孩子試分別找出滿足以下條件的所有二叉樹： (1)二叉樹的前序序列與中序序列相同; (2)二叉樹的中序序列與后序序列相同; (3)二叉樹的前序序列與后序序列相同。答案： (1)空樹或缺左子樹的單支樹；

(2)空樹或缺右子樹的單支樹；

(3)空樹或只有根結(jié)點的二叉樹。第34

頁樹與二叉樹請列舉樹的兩種存儲結(jié)構(gòu)

。答案：雙親表示法，孩子表示法，孩子兄弟表示法將圖所示樹轉(zhuǎn)換為二叉樹。acgbdfeh第35

頁第七章圖——基本概念圖的定義、術(shù)語與基本概念：有向圖、無向圖，弧、邊，出度和入度，度，有向完全圖、完全圖，連通圖、連通分量、強連通圖，生成樹，簡單路徑、簡單回路圖的常見表示方式G=(V,E)。圖的常見存儲結(jié)構(gòu)：鄰接矩陣，鄰接表（逆鄰接表），十字鏈表圖的遍歷：深度優(yōu)先，廣度優(yōu)先圖的應(yīng)用：最小生成樹，最短路徑問題，

拓撲排序，

關(guān)鍵路徑，算法的基本思想樹和二叉樹—2009試題給定二叉樹如下圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點的左子樹，R代表根結(jié)點的右子樹。若遍歷后的結(jié)點序列為3,1,7,5,6,2,4，則其遍歷方式是A．LRN B．NRL C．RLN D．RNLD．RNLC．1113215476

已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個葉結(jié)點，則該完全二叉樹的結(jié)點個數(shù)最多是A．39

B．52

C．111 D．119樹和二叉樹—2009考博試題對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號小于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，實現(xiàn)編號應(yīng)采用的遍歷次序是______。A．先序 B．中序 C．后序 D．都不是

設(shè)二叉樹只有度為0和2的結(jié)點，其結(jié)點個數(shù)為21，則該二叉樹的最大深度為________。

A．5 B．6 C．10 D．11A．先序D．11樹和二叉樹—2009考博試題利用哈夫曼算法為報文“abigblackbugbitabigblackbag”設(shè)計一個編碼（注意：包括空格），使該報文的長度最短。要求給出最終的哈夫曼樹，每個字符的哈夫曼編碼，以及報文最終的長度。5*3+7*3+２*４+4*3+3*3+2*4+2*4+5+5+8*2=107a:5 b:7 c:2 g:4 i:3 k:2 l:2 t:1 u:1”:8a:000b:001c:0100g:011i:100k:1010l:1011t:01010u:01011”:11tu2kl4c4i7g8ab12“352015圖—2005試題

設(shè)圖的鄰接表的類型定義如下。若帶權(quán)圖中邊的權(quán)值類型為整型，請對該鄰接表的類型定義做出適當(dāng)修改，使之能夠用于表示邊帶權(quán)的圖。#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVnode{VertexTypedata;ArcNode*finrstarc;}Vnode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvexs;intvexnum,arcnum;}ALGraph;typedefstructArcNode{intadjvex;intweight;structArcNode*nextarc;}ArcNode;在求連通網(wǎng)的最小生成樹時，普里姆（Prim）算法適用于___________，克魯斯卡爾（Kruskal）算法適用于____________。拓撲排序可以用來檢查________中是否存在回路。圖—2007試題下列圖的存儲結(jié)構(gòu)中，只能用來表示有向圖的是A.鄰接矩陣 B.鄰接表 C.十字鏈表 D.鄰接多重表有向圖邊稠密的網(wǎng)C.十字鏈表邊稀疏的網(wǎng)圖—2008試題TopologicalSort是一個利用隊列對圖G進行拓撲排序的算法，請在該算法的空白處填入合適的語句或表達式。提示：數(shù)組InDegree事先已存放每個頂點的入度；數(shù)組TopOrder在算法執(zhí)行后將存放每個頂點在拓撲排序中的順序。intTopologicalSort(GraphG){QueueQ;intCounter=0;intI,V,W;InitQueue(Q);for(I=0;I<G.vexnum;I++)if(InDegree[I]==0)Enqueue(Q,I);while(______________){Dequeue(Q,V);TopOrder[V]=++Counter;for(W=FirstAdjVex(G,V);W!=-1;W=NextAdjVex(G,V,W))if(_________________)Enqueue(Q,W);}DestroyQueue(Q);return(Counter==G.vexnum);}!QueueEmpty(Q)--Indegree[W]==0 圖—2009試題下列關(guān)于無向連通圖特性的敘述中，正確的是I．所有頂點的度之和為偶數(shù) II．邊數(shù)大于頂點個數(shù)減1III．至少有一個頂點的度為1A．只有I B．只有II C．I和II D．I和IIIA．只有I圖—2009試題帶權(quán)圖（權(quán)值非負，表示邊連接的兩頂點間的距離）的最短路徑問題是找出從初始頂點到目標(biāo)頂點之間的一條最短路徑。假設(shè)從初始頂點到目標(biāo)頂點之間存在路徑，現(xiàn)有一種解決該問題的方法：①設(shè)最短路徑初始時僅包含初始頂點，令當(dāng)前頂點u為初始頂點；②選擇離u最近且尚未在最短路徑中的一個頂點v，加入到最短路徑中，修改當(dāng)前頂點u=v；③重復(fù)步驟②，直到u是目標(biāo)頂點時為止。請問上述方法能否求得最短路徑？若該方法可行，請證明之；否則，請舉例說明。abc754圖—2009考博試題在圖中判斷兩個頂點是否相鄰，采用_______存儲結(jié)構(gòu)效率最高。A．鄰接矩陣 B．鄰接表C．十字鏈表 D．鄰接多重表A．鄰接矩陣普里姆算法是用于求解________的最小生成樹。A．無向圖 B．有向連通圖C．無向連通網(wǎng) D．有向網(wǎng)C．無向連通網(wǎng)圖—2009考博試題有向圖的鄰接表如圖所示。 （1）畫出該圖； （2）給出以V0為起始結(jié)點的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列； （3）簡述在鄰接表存儲結(jié)構(gòu)下，求圖中某頂點i的入度的方法；V001234431^2V1V2V3V4^0^