數據結構復習2009第一部分基本概念基本知識點：數據結構和算法的概念重點：數據結構的邏輯結構、存儲結構、數據運算三方面的概念及相互關系；算法時間復雜度分析。難點：分析算法的時間復雜度。第二部分線性結構1、線性表基本知識點：線性表的邏輯結構特征，線性表的基本運算，線性表的兩種存儲結構以及為兩種存儲結構下線性表基本運算算法的實現，順序表和鏈表的優缺點比較。重點：掌握線性表的定義和特點，線性表的存儲結構；順序表和鏈表的組織方法和算法設計。難點：單鏈表和雙鏈表的各種算法設計。2、棧和隊列基本知識點：理解棧和隊列的定義、特點及與線性表的異同；掌握順序棧和鏈棧的組織方法，棧滿、棧空的判斷及其描述；掌握順序隊列、循環隊列和鏈隊列的組織方法，隊滿、隊空的判斷及描述。遞歸的相關概念。重點：棧和隊列的特點，順序棧和鏈棧的基本運算的實現算法；順序隊列、循環隊列和鏈隊列的基本運算算法。遞歸模型，遞歸算法的執行過程和遞歸設計思想。難點：靈活運用棧和隊列設計解決應用問題的算法。將遞歸算法轉化為非遞歸算法。3、串基本知識點：串的基本概念和串的基本運算。重點：串的順序存儲方法和串的鏈接存儲方法；串的基本運算算法的實現。難點：模式匹配Brute-Force算法和KMP算法。4、數組、稀疏矩陣、廣義表基本知識點：數組的順序存儲結構；特殊矩陣的壓縮存儲方法；稀疏矩陣的壓縮存儲方法廣義表的定義及其與線性表的關系；廣義表的存儲結構。重點：數組的復雜算法設計。廣義表的存儲結構以及基本運算的實現算法。難點：稀疏矩陣和各種存儲結構及基本運算的實現算法。廣義表的遞歸算法設計。第三部分樹形結構基本知識點：樹的定義及樹的相關術語、樹的表示和樹的性質。二叉樹的定義、二叉樹的性質、滿二叉樹和完全二叉樹的定義、二叉樹的順序存儲和鏈式存儲、二叉樹的遍歷過程二叉樹的線索化過程、哈夫曼樹的定義與構造方法、二叉樹與森林之間的相互轉換。重點：掌握二叉樹的性質、二叉樹的遍歷（二叉樹的各種遍歷方法及它們所確定的序列之間的關系）、二叉樹的線索化方法，構造哈夫曼樹。難點：二叉樹的各種算法，包括遞歸算法和非遞歸算法的設計。（注：要求掌握二叉樹的二叉鏈表的相關算法）第四部分圖結構基本知識點：圖的基本概念、圖的存儲結構、圖的遍歷算法（深度優先遍歷和廣度優先遍歷）、圖的生成樹和最小生成樹、最短路徑、關鍵路徑和拓撲排序。重點：圖的各種存儲結構和遍歷算法（遞歸和非遞歸算法）設計，構造最小生成樹，生成最短路徑、生成圖的關鍵路徑，拓撲排序的應用。難點：圖的遍歷算法和圖的各種復雜算法的設計。第五部分查找與排序1、查找基本知識點：查找及相關概念，各種順序表的查找算法和性能分析，各種樹表的查找算法和性能分析，哈希表的構造、查找和性能分析。重點：各種順序表和樹表的查找算法和性能分析，構造哈希表、沖突處理和性能分析。難點：各種查找算法設計和性能分析。2、內部排序基本知識點：內排序的概念；各種排序的方法。(排序算法中用到的一些概念。)重點：各種排序算法的性能特點；各種排序算法的比較和選擇。難點：復雜排序算法設計。考試題目類型：1、單項選擇題。2、填空題。3、判斷題。4、解答題(應用題、簡答題)。5、算法設計與分析題。例題第一部分基本概念例題1_1：用C/C++語言描述下列算法，并給出算法的時間復雜度。求一個n階方陣的所有元素之和。對于輸入的任意三個整數，將它們按照從小到大的順序輸出。對于輸入的任意n個整數，輸出其中的最大和最小元素。解：(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)。第二部分線性結構例題2_1_1：在線性表的如下鏈表存儲結構中，若未知鏈表頭結點的指針，僅已知p指針指向的結點，能否將它從該結構中刪除？為什么？單鏈表；(2)雙鏈表；(3)循環鏈表。答：(1)不能刪除。因為無法知道*卩結點的前趨結點的地址。能刪除。由*卩結點的左指針找到其前趨結點的地址，然后實施刪除。能刪除。循環査找一周，可以找到*卩結點的前趨結點的地址，然后實施刪除。例題2_1_2：已知長度為n的線性表A采用順序存儲結構，編寫一個時間復雜度為O(n)、空間復雜度為0(1)的算法，該算法刪除線性表中所有值為item的數據元素。解：存儲結構如下：typedefstructSeqList{ElemTyep*elem;intlength;intListSize;}SeqList;用k記錄順序表A中等于item的元素個數，邊掃描A邊統計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循環，時間復雜度為O(n)。算法中只用了兩個臨時變量i和k,輔助空間的太小與表的長度無關，空間復雜度為O(1)。例題2_1_3：設C={a1,bl,a2,b2,……,an,bn}為一線性表，采用帶頭結點的單鏈表存放，編寫一個就地算法，將其拆分為兩個線性表，使得：A=(al,a2,……,an)，B=(bl,b2,……,bn)。解：存儲結構如下：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已經被拆分，拆分后不再存在。}〃A和B采用尾插法建立。例題2_1_4：設計一個算法，將x插入一個有序(從小到大排序)的線性表(順序存儲結構)的適當位置上，并保持線性表的有序性。解：設存儲結構如下：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逆置。解：假設存儲結構如下：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插入一個有序(從小到大排序)的線性表(鏈接存儲結構)的適當位置上，并保持線性表的有序性。解：設存儲結構如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;假定單鏈表是帶頭結點的單鏈表，算法如下：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：設計一個算法判斷帶頭結點的單鏈表L是否是按值遞增的。解：設存儲結構如下：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:設計一個算法，將一個帶頭結點的單鏈表逆置。解：設存儲結構如下：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:設計一個算法，在帶頭結點的單鏈表L中刪除所有結點值為最小的結點(可能有多個結點值最小的結點)。解：設存儲結構如下：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：分別設計有關單鏈表、單循環鏈表、雙鏈表、雙循環鏈表的插入、刪除、查找、遍歷等算法。(結點個數、最大值、次大值、最小值、次小值、排序、統計、分拆、合并、歸并、銷毀、復制、有序表)(插入算法包括：前插法、后插法、第i個位置插入、值為x的結點前或后插入)(刪除算法包括：刪除第i個結點、刪除值為X的結點、刪除值為x的結點前或后的結點)(査找算法包括：査找值為X的結點、查找第i個結點)例題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：假設以不帶頭結點的循環單鏈表表示隊列，并且只設一個指針rear指向隊尾結點，但不設頭指針，請寫出相應的隊初始化、入隊、出隊和判隊空的算法。解：設存儲結構如下：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：空串和空格串有何區別?答：空串是指不含任何字符的串，其長度為0，空串是任意串的子串。空格串是指僅僅含有空格字符的串，其長度是串中空格字符的個數。例題2_3_3：設計在鏈串上實現判定兩個串是否相等的算法。解：存儲結構如下：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：編寫一個算法，計算一個三元組表表示的稀疏矩陣的對角線元素之和。解：存儲結構如下：typedefstruct{inti,j;//行下標和列下標。ElemTypeelem;}Triple;typedefstruct{Tripledata[MaxSize+1];/非0元三元組表，data[0]未用。intmu,nu,tu;//矩陣的行數、列數、非0元素個數。}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） 廣義表的長度與廣義表中含有多少個原子元素有關。（2） 一個廣義表的表尾總是一個廣義表。（3） 在廣義表中，每個原子的類型都是相同的。（4） 在廣義表中，每個子表的結構都是相同的。（5） 空的廣義表是指廣義表中不包含原子元素。（6） 廣義表的長度不小于其中任何一個子表的長度。答：（1）錯誤。（2）正確。（3）正確。（4）錯誤。（5）錯誤。（6）錯誤。第三部分樹形結構（注：以下的算法設計題，均假定二叉樹用二叉鏈表存儲）例題3_1：編寫算法，求二叉樹的結點個數、葉結點個數、單分支結點個數、雙分支結點個數。例題3_2：編寫二叉樹的先序遍歷、中序遍歷、后序遍歷的遞歸算法。例題3_3：編寫二叉樹的先序遍歷、中序遍歷的非遞歸算法。例題3_4：編寫二叉樹的層次遍歷的算法。例題3_5：給出二叉樹的先序序列EBADCFHGIKJ和中序序列ABCDEFGHIJK，畫出二叉樹并寫出二叉樹的后序序列和層次序列。例題3_6：給出二叉樹的后序序列DCEGBFHKJIA和中序序列DCBGEAHFIJK，畫出二叉樹并寫出二叉樹的后序序列和層次序列。例題3_7：給出二叉樹的層次序列ABCDEFGHIJ和中序序列DBGEHJACIF，畫出二叉樹并寫出二叉樹的先序序列和后序序列。例題3_8：編寫銷毀二叉樹的算法。例題3_9（1）：給定權集w={2,3,4,7,8,9}，試構造關于w的一棵哈夫曼樹，并求其加權路徑的長度WL，寫出相應的哈夫曼編碼。例題3_9（2）：給定權集w={7，19，2，6，32，3,21,10}，試構造關于w的一棵哈夫曼樹，并求其加權路徑的長度WPL,寫出相應的哈夫曼編碼。例題3_10：編寫算法輸出二叉樹的所有葉子結點。例題3_11：給出一棵二叉樹，畫出其中序線索二叉樹。例題3_12：設計一個算法，交換二叉樹的左右子樹。例題3_13:設計一個算法，復制一棵二叉樹。例題3_14：完全二叉樹、二叉樹的結點數、葉結點數等之間的關系。（n0=n2+1,根據這個性質可以得到一些結論）第四部分圖結構例題4_1：給定一個圖（有向圖或無向圖），寫出鄰接矩陣，或畫出其鄰接表或逆鄰接表。例題4_2：給定一個帶權的有向圖（無向圖），畫出其按Prim算法或Kruskal算法生成最小生成樹的過程及最后結果。（不要求寫出算法）。例題4_3：給出一個有向的無環圖，寫出其一個或若干個拓撲序列。（不要求定算法）。例題4_4：給定一個圖（有向圖或無向圖），寫出其從某一點出發，按深度優先或按寬度優先遍歷的序列。（不要求寫算法）。例題4_5：給定一個帶權的圖（有向圖或無向圖），寫出按照Dijkstra算法求某個源點到其余各點的最短路徑的過程。（不要求寫完整的算法）。第五部分查找與排序例題5_1（1）：給出一個有序表{1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19，20}，寫出按照二分查找法查找某個結點（如3，又如16）的查找過程。例題5_1⑵：有一個有序表R[1???13]={1,3,9,12,32,41,45,62,75,77,82,95，100}，當用二分查找法查找關鍵字為82的結點時，經過多少次比較后查找成功，依次與哪些關鍵字進行比較？例題5_2：給出一組數據,比如{7,2,9,8,13,1,4,3,6,5,11,14,10,12},畫出相應的二叉排序樹。然后再畫出在該二叉排序樹中刪除結點13后的二叉排序樹。例題5_3：分別設計在二叉排序樹