數(shù)據(jù)結(jié)構(gòu)復習2010

數(shù)據(jù)結(jié)構(gòu)復習2009第一部分基本概念基本知識點：數(shù)據(jù)結(jié)構(gòu)和算法的概念重點：數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)運算三方面的概念及相互關(guān)系；算法時間復雜度分析。難點：分析算法的時間復雜度。第二部分線性結(jié)構(gòu)1、線性表基本知識點：線性表的邏輯結(jié)構(gòu)特征，線性表的基本運算，線性表的兩種存儲結(jié)構(gòu)以及為兩種存儲結(jié)構(gòu)下線性表基本運算算法的實現(xiàn)，順序表和鏈表的優(yōu)缺點比較。重點：掌握線性表的定義和特點，線性表的存儲結(jié)構(gòu)；順序表和鏈表的組織方法和算法設計。難點：單鏈表和雙鏈表的各種算法設計。2、棧和隊列基本知識點：理解棧和隊列的定義、特點及與線性表的異同；掌握順序棧和鏈棧的組織方法，棧滿、?？盏呐袛嗉捌涿枋?；掌握順序隊列、循環(huán)隊列和鏈隊列的組織方法，隊滿、隊空的判斷及描述。遞歸的相關(guān)概念。重點：棧和隊列的特點，順序棧和鏈棧的基本運算的實現(xiàn)算法；順序隊列、循環(huán)隊列和鏈隊列的基本運算算法。遞歸模型，遞歸算法的執(zhí)行過程和遞歸設計思想。難點：靈活運用棧和隊列設計解決應用問題的算法。將遞歸算法轉(zhuǎn)化為非遞歸算法。3、串基本知識點：串的基本概念和串的基本運算。重點：串的順序存儲方法和串的鏈接存儲方法；串的基本運算算法的實現(xiàn)。難點：模式匹配Brute-Force算法和KMP算法。4、數(shù)組、稀疏矩陣、廣義表基本知識點：數(shù)組的順序存儲結(jié)構(gòu)；特殊矩陣的壓縮存儲方法；稀疏矩陣的壓縮存儲方法廣義表的定義及其與線性表的關(guān)系；廣義表的存儲結(jié)構(gòu)。重點：數(shù)組的復雜算法設計。廣義表的存儲結(jié)構(gòu)以及基本運算的實現(xiàn)算法。難點：稀疏矩陣和各種存儲結(jié)構(gòu)及基本運算的實現(xiàn)算法。廣義表的遞歸算法設計。第三部分樹形結(jié)構(gòu)基本知識點：樹的定義及樹的相關(guān)術(shù)語、樹的表示和樹的性質(zhì)。二叉樹的定義、二叉樹的性質(zhì)、滿二叉樹和完全二叉樹的定義、二叉樹的順序存儲和鏈式存儲、二叉樹的遍歷過程二叉樹的線索化過程、哈夫曼樹的定義與構(gòu)造方法、二叉樹與森林之間的相互轉(zhuǎn)換。重點：掌握二叉樹的性質(zhì)、二叉樹的遍歷（二叉樹的各種遍歷方法及它們所確定的序列之間的關(guān)系）、二叉樹的線索化方法，構(gòu)造哈夫曼樹。難點：二叉樹的各種算法，包括遞歸算法和非遞歸算法的設計。（注：要求掌握二叉樹的二叉鏈表的相關(guān)算法）第四部分圖結(jié)構(gòu)基本知識點：圖的基本概念、圖的存儲結(jié)構(gòu)、圖的遍歷算法（深度優(yōu)先遍歷和廣度優(yōu)先遍歷）、圖的生成樹和最小生成樹、最短路徑、關(guān)鍵路徑和拓撲排序。重點：圖的各種存儲結(jié)構(gòu)和遍歷算法（遞歸和非遞歸算法）設計，構(gòu)造最小生成樹，生成最短路徑、生成圖的關(guān)鍵路徑，拓撲排序的應用。難點：圖的遍歷算法和圖的各種復雜算法的設計。第五部分查找與排序1、查找基本知識點：查找及相關(guān)概念，各種順序表的查找算法和性能分析，各種樹表的查找算法和性能分析，哈希表的構(gòu)造、查找和性能分析。重點：各種順序表和樹表的查找算法和性能分析，構(gòu)造哈希表、沖突處理和性能分析。難點：各種查找算法設計和性能分析。2、內(nèi)部排序基本知識點：內(nèi)排序的概念；各種排序的方法。(排序算法中用到的一些概念。)重點：各種排序算法的性能特點；各種排序算法的比較和選擇。難點：復雜排序算法設計?？荚囶}目類型：1、單項選擇題。2、填空題。3、判斷題。4、解答題(應用題、簡答題)。5、算法設計與分析題。例題第一部分基本概念例題1_1：用C/C++語言描述下列算法，并給出算法的時間復雜度。求一個n階方陣的所有元素之和。對于輸入的任意三個整數(shù)，將它們按照從小到大的順序輸出。對于輸入的任意n個整數(shù)，輸出其中的最大和最小元素。解：(1)算法如下：intsum(intA[n][n],intn){inti,j,s=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=A[i][j];returns;}本算法的時間復雜度為O(n2)。(2)算法如下：voidOrder(inta,intb,intc){if(a>b){if(b>c)cout<<c<<b<<a;elseif(a>c)cout<<b<<c<<a;elsecout<<b<<a<<c;}else{if(c<a)cout<<c<<a<<b;elseif(c<b)cout<<a<<c<<b;elsecout<<a<<b<<c;}}本算法的時間復雜度為O(1)。(3)算法如下：voidmaxmin(inta[],intn,int&max,int&min){intk;min=a[0];max=a[0];for(k=1;k<n;k++)if(a[k]>max)max=a[k];elseif(a[k]<min)min=a[k];}本算法的時間復雜度為O(n)。第二部分線性結(jié)構(gòu)例題2_1_1：在線性表的如下鏈表存儲結(jié)構(gòu)中，若未知鏈表頭結(jié)點的指針，僅已知p指針指向的結(jié)點，能否將它從該結(jié)構(gòu)中刪除？為什么？單鏈表；(2)雙鏈表；(3)循環(huán)鏈表。答：(1)不能刪除。因為無法知道*卩結(jié)點的前趨結(jié)點的地址。能刪除。由*卩結(jié)點的左指針找到其前趨結(jié)點的地址，然后實施刪除。能刪除。循環(huán)査找一周，可以找到*卩結(jié)點的前趨結(jié)點的地址，然后實施刪除。例題2_1_2：已知長度為n的線性表A采用順序存儲結(jié)構(gòu)，編寫一個時間復雜度為O(n)、空間復雜度為0(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。解：存儲結(jié)構(gòu)如下：typedefstructSeqList{ElemTyep*elem;intlength;intListSize;}SeqList;用k記錄順序表A中等于item的元素個數(shù)，邊掃描A邊統(tǒng)計k,并將不為item的元素向前移動k個位置，最后修改A的長度。算法如下：voidDeleteNode(SeqList&A,ElemTypeitem){intk=0,i=0;while(i<A.length){if(A.elem[i]==item)k++;elseA.elem[i-k]=A.elem[i];i++;A.length=A.length-k;}算法中只有一個while循環(huán)，時間復雜度為O(n)。算法中只用了兩個臨時變量i和k,輔助空間的太小與表的長度無關(guān)，空間復雜度為O(1)。例題2_1_3：設C={a1,bl,a2,b2,……,an,bn}為一線性表，采用帶頭結(jié)點的單鏈表存放，編寫一個就地算法，將其拆分為兩個線性表，使得：A=(al,a2,……,an)，B=(bl,b2,……,bn)。解：存儲結(jié)構(gòu)如下：typedefstructLNode{Elemtypedata;structLNode*next;}LNode,*LinkList;算法如下：voidFun(LinkList&C,LinkList&A,LinkList&B){LNode*pa,*pb,*p,*s;p=C->next;A=C;A->next=0;B=newLNode;B->next=0;pa=A;pb=B;while(p){s=p->next;pa->next=p;pa=p;p=s;s=s->next;if(p){pb->next=p;pb=p;p=s;s=s->next;}}pa->next=0;pb->next=0;C=0;//C已經(jīng)被拆分，拆分后不再存在。}〃A和B采用尾插法建立。例題2_1_4：設計一個算法，將x插入一個有序(從小到大排序)的線性表(順序存儲結(jié)構(gòu))的適當位置上，并保持線性表的有序性。解：設存儲結(jié)構(gòu)如下：typedefstructSeqList{ElemType*elem;intlength;intListSize;}SeqList;算法如下：voidfun(SeqList&L,ElemTypex){inti;if(L.length==L.ListSize){ElemType*p=newElemType[2*L.ListSize];L.ListSize=2*L.ListSize;for(i=0;i<L.Length;i++)p[i]=L.elem[i];delete[]L.elem;L.elem=p;}i=L.length-1;while(i>=0&&x<L.elem[i]){L.elem[i+1]=L.elem[i];i=i-1;}L.elem[i+1]=x;L.length++;}例題2_1_4B:設計一個算法，將順序表L逆置。解：假設存儲結(jié)構(gòu)如下：typedefstructSqList{ElemTypedata[Maxsize];intLength;}SqList;算法如下：voidReverse(SqList&L){inti,j;i=0;j=L.Length-1;while(i<j){ElemTypetemp=L.data[i];L.data[i]=L.data[j];L.data[j]=temp;i++;j--;}}例題2_1_5：設計一個算法，將x插入一個有序(從小到大排序)的線性表(鏈接存儲結(jié)構(gòu))的適當位置上，并保持線性表的有序性。解：設存儲結(jié)構(gòu)如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;假定單鏈表是帶頭結(jié)點的單鏈表，算法如下：voidFun(LinkList&L,ElemTypex){LNode*pre,*p;p=newLNode;p->data=x;pre=L;while(pre->next&&pre->next->data<x)pre=pre->next;p->next=pre->next;pre->next=p;}例題2_1_6：設計一個算法判斷帶頭結(jié)點的單鏈表L是否是按值遞增的。解：設存儲結(jié)構(gòu)如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;算法如下：intIsIncrease(LinkList&L)//若遞增返回1，否則返回0。{LNode*pre,*p;p=L->next;if(p==0)return1;while(p->next){pre=p;p=p->next;if(pre->data>p->data)return0;elsep=p->next;}return1;}例題2_1_7:設計一個算法，將一個帶頭結(jié)點的單鏈表逆置。解：設存儲結(jié)構(gòu)如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;算法如下：voidReverse(LinkList&H){LNode*p=H->next,*q;H->next=0;while(p){q=p->next;p->next=H->next;H->next=p;p=q;}}例題2_1_8:設計一個算法，在帶頭結(jié)點的單鏈表L中刪除所有結(jié)點值為最小的結(jié)點(可能有多個結(jié)點值最小的結(jié)點)。解：設存儲結(jié)構(gòu)如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;算法如下：voidDeleteMin(LinkList&L){ElemTypemin;LNode*pre,*p;if(L->next==0)return;min=L->next->data;p=L->next;while(p){if(p->data<min)min=p->data;p=p->next;}pre=L;p=L->next;while(p){if(p->data==min){pre->next=p->next;deletep;p=pre->next;}else{pre=p;p=p->next;}}例題2_1_9：分別設計有關(guān)單鏈表、單循環(huán)鏈表、雙鏈表、雙循環(huán)鏈表的插入、刪除、查找、遍歷等算法。(結(jié)點個數(shù)、最大值、次大值、最小值、次小值、排序、統(tǒng)計、分拆、合并、歸并、銷毀、復制、有序表)(插入算法包括：前插法、后插法、第i個位置插入、值為x的結(jié)點前或后插入)(刪除算法包括：刪除第i個結(jié)點、刪除值為X的結(jié)點、刪除值為x的結(jié)點前或后的結(jié)點)(査找算法包括：査找值為X的結(jié)點、查找第i個結(jié)點)例題2_2_1：設有5個元素，其入棧次序為：A,B,C,D,E,在各種可能的出棧次序中,以元素C，D最先出棧(即C第一個且D第二個出棧)的次序有哪幾個？答：要使C第一個且D第二個出棧，應是A入棧，B入棧，C入棧，C出棧，D入棧，D出棧,之后可以有以下幾種情況：B出棧，A出棧，E入棧，E出棧，輸出序列為CDBAE；B出棧，E入棧，E出棧，A出棧，輸出序列為CDBEA；E入棧，E出棧，B出棧，A出棧，輸出序列為CDEBA。例題2_2_2：假設以不帶頭結(jié)點的循環(huán)單鏈表表示隊列，并且只設一個指針rear指向隊尾結(jié)點，但不設頭指針，請寫出相應的隊初始化、入隊、出隊和判隊空的算法。解：設存儲結(jié)構(gòu)如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkQueue;則相應的算法如下：隊列的初始化voidInitLinkQueue(LinkQueue&rear){rear=0;}入隊列voidEnQueue(LinkQueue&rear,ElemTypex){LNode*p=newLNode;p->data=x;if(rear==0){rear=p;rear->next=rear;}else{p->next=rear->next;rear->next=p;reat=p;}}出隊列voidDeQueue(LinkQueue&rear,ElemType&x){if(rear==0)return;LNode*p=rear->next;x=p->data;if(rear==p)rear=0;elserear->next=p->next;deletep;}判別隊列是否為空inQuEmpty(LinkQueue&rear){returnrear==0;}例題2_3_1：兩個串相等的充分必要條件是什么？答：兩個串相等的充分必要條件是：兩個串的長度相等且對應位置上的字符相等。例題2_3_2：空串和空格串有何區(qū)別?答：空串是指不含任何字符的串，其長度為0，空串是任意串的子串?？崭翊侵竷H僅含有空格字符的串，其長度是串中空格字符的個數(shù)。例題2_3_3：設計在鏈串上實現(xiàn)判定兩個串是否相等的算法。解：存儲結(jié)構(gòu)如下：typedefstructLNode{chardata;structLNode*next;}LNode,*LinkString;算法如下：intEqual(LinkString&S,LinkString&T){LNode*ps=S,*pt=T;intflag=1;while(ps&&pt&&flag){if(ps->data!=pt->data)flag=0;pt=pt->next;ps=ps->next;}if(ps||pt)return0;elsereturnflag;}例題2_4_1：編寫一個算法，計算一個三元組表表示的稀疏矩陣的對角線元素之和。解：存儲結(jié)構(gòu)如下：typedefstruct{inti,j;//行下標和列下標。ElemTypeelem;}Triple;typedefstruct{Tripledata[MaxSize+1];/非0元三元組表，data[0]未用。intmu,nu,tu;//矩陣的行數(shù)、列數(shù)、非0元素個數(shù)。}TSMatrix;算法如下：intDiagonal（TSMatrix&A,ElemType&sum）//用sum返回對角線元素之和。{intk;sum=0;if（A?mu!=A?nu）{coutvv”不是正方陣，不能求對角線元素之和\n”;return0;}for（k=1;k<=A.tu;k++）if（A?data[k]?i==A?data[k]?j）sum+=A?data[k]?elem;return1;}例題2_4_2：判斷題：判斷以下敘述的正確性：（1） 廣義表的長度與廣義表中含有多少個原子元素有關(guān)。（2） 一個廣義表的表尾總是一個廣義表。（3） 在廣義表中，每個原子的類型都是相同的。（4） 在廣義表中，每個子表的結(jié)構(gòu)都是相同的。（5） 空的廣義表是指廣義表中不包含原子元素。（6） 廣義表的長度不小于其中任何一個子表的長度。答：（1）錯誤。（2）正確。（3）正確。（4）錯誤。（5）錯誤。（6）錯誤。第三部分樹形結(jié)構(gòu)（注：以下的算法設計題，均假定二叉樹用二叉鏈表存儲）例題3_1：編寫算法，求二叉樹的結(jié)點個數(shù)、葉結(jié)點個數(shù)、單分支結(jié)點個數(shù)、雙分支結(jié)點個數(shù)。例題3_2：編寫二叉樹的先序遍歷、中序遍歷、后序遍歷的遞歸算法。例題3_3：編寫二叉樹的先序遍歷、中序遍歷的非遞歸算法。例題3_4：編寫二叉樹的層次遍歷的算法。例題3_5：給出二叉樹的先序序列EBADCFHGIKJ和中序序列ABCDEFGHIJK，畫出二叉樹并寫出二叉樹的后序序列和層次序列。例題3_6：給出二叉樹的后序序列DCEGBFHKJIA和中序序列DCBGEAHFIJK，畫出二叉樹并寫出二叉樹的后序序列和層次序列。例題3_7：給出二叉樹的層次序列ABCDEFGHIJ和中序序列DBGEHJACIF，畫出二叉樹并寫出二叉樹的先序序列和后序序列。例題3_8：編寫銷毀二叉樹的算法。例題3_9（1）：給定權(quán)集w={2,3,4,7,8,9}，試構(gòu)造關(guān)于w的一棵哈夫曼樹，并求其加權(quán)路徑的長度WL，寫出相應的哈夫曼編碼。例題3_9（2）：給定權(quán)集w={7，19，2，6，32，3,21,10}，試構(gòu)造關(guān)于w的一棵哈夫曼樹，并求其加權(quán)路徑的長度WPL,寫出相應的哈夫曼編碼。例題3_10：編寫算法輸出二叉樹的所有葉子結(jié)點。例題3_11：給出一棵二叉樹，畫出其中序線索二叉樹。例題3_12：設計一個算法，交換二叉樹的左右子樹。例題3_13:設計一個算法，復制一棵二叉樹。例題3_14：完全二叉樹、二叉樹的結(jié)點數(shù)、葉結(jié)點數(shù)等之間的關(guān)系。（n0=n2+1,根據(jù)這個性質(zhì)可以得到一些結(jié)論）第四部分圖結(jié)構(gòu)例題4_1：給定一個圖（有向圖或無向圖），寫出鄰接矩陣，或畫出其鄰接表或逆鄰接表。例題4_2：給定一個帶權(quán)的有向圖（無向圖），畫出其按Prim算法或Kruskal算法生成最小生成樹的過程及最后結(jié)果。（不要求寫出算法）。例題4_3：給出一個有向的無環(huán)圖，寫出其一個或若干個拓撲序列。（不要求定算法）。例題4_4：給定一個圖（有向圖或無向圖），寫出其從某一點出發(fā)，按深度優(yōu)先或按寬度優(yōu)先遍歷的序列。（不要求寫算法）。例題4_5：給定一個帶權(quán)的圖（有向圖或無向圖），寫出按照Dijkstra算法求某個源點到其余各點的最短路徑的過程。（不要求寫完整的算法）。第五部分查找與排序例題5_1（1）：給出一個有序表{1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19，20}，寫出按照二分查找法查找某個結(jié)點（如3，又如16）的查找過程。例題5_1⑵：有一個有序表R[1???13]={1,3,9,12,32,41,45,62,75,77,82,95，100}，當用二分查找法查找關(guān)鍵字為82的結(jié)點時，經(jīng)過多少次比較后查找成功，依次與哪些關(guān)鍵字進行比較？例題5_2：給出一組數(shù)據(jù),比如{7,2,9,8,13,1,4,3,6,5,11,14,10,12},畫出相應的二叉排序樹。然后再畫出在該二叉排序樹中刪除結(jié)點13后的二叉排序樹。例題5_3：分別設計在二叉排序樹