數據結構習題與實驗-C++

浙江萬里學院

內容簡介數據結構是計算機專業的核心課，是重要的專業根底課。實踐是學習本課程的一個重要的環節。目前各種“數據結構”教材較為注重理論的表達與介紹，算法描述不拘泥某種語言的語法細節，默認讀者已具備扎實的程序設計根底，可以在課下獨立完成數據結構實驗。實際上在讀者群中程序設計的根底并不一致，相當一局部人根底較為薄弱。多數學生反映數據結構的上機實驗存在一定的困難，希望有適宜的實驗參考書指導學習。數據結構的理論學習也有一定的深度，存在一定的難度。學生必須完成一定數量的思考題、練習題、書面作業題，一方面穩固根本知識、一方面提高聯系實際分析解決問題的能力。正是基于以上的原因編寫了這本“數據結構實驗與習題”。本資料的前期版本〔用C語言描述算法，用C/C++描述算法〕已經使用數屆，現在是第三次修訂，主要是使用C++面向對象技術描述算法和實現程序。本參考書包括C++語言根底、書面作業練習題和上機實驗習題三局部。在C++語言根底知識局部，這里針對數據結構上機實驗所必須的C++根本知識〔結構體、類等等〕做補充介紹。這局部內容非常重要，掌握的是否熟練會直接影響“數據結構“的學習。在習題局部，既有選擇題、判斷題，也有用圖表解答的練習題、算法設計題或綜合解答分析題。并且配有局部練習題的答案供學生自學、練習、參考。在實驗局部，包括有完整的C++語言源程序例題，介紹了一些設計數據結構題目所需的C++語言常用的知識和技巧。在實驗題中，既有簡單容易的驗證題，即驗證已經給出的源程序，或者擴充已經給出的源程序，也有需獨立思考設計的綜合實驗題。第1局部、第2局部的習題1、習題2、習題5、習題6和第3局部的上機實驗要求及標準、實驗1、實驗2、實驗5、實驗6由楊秀金改寫。第2局部的習題3、習題9和第3局部的實驗3、實驗9由汪沁改寫。第2局部的習題4、習題7、習題8和第3局部的實驗4、實驗7、實驗8由鄧芳改寫。由于時間倉足、水平有限，書中難免存在錯誤和不妥之處，敬請讀者指正。計算機與信息學院楊秀金汪沁鄧芳2005年2月修訂于浙江萬里學院錢湖校區目錄第1局部C++語言根本知識一、C++源程序結構---------------------------------------------------------------------------1二、結構體及運用-----------------------------------------------------------------------------1三、類的根本概念及運用--------------------------------------------------------------------3四、結構體在類中的使用--------------------------------------------------------------------4第2局部書面作業練習題習題1緒論------------------------------------------------------------------------------------6習題2線性表---------------------------------------------------------------------------------8習題3棧和隊列------------------------------------------------------------------------------11習題4串---------------------------------------------------------------------------------------13習題5數組------------------------------------------------------------------------------------15習題6樹與二叉樹---------------------------------------------------------------------------17習題7圖---------------------------------------------------------------------------------------24習題8查找------------------------------------------------------------------------------------31習題9排序------------------------------------------------------------------------------------34第3局部上機實驗習題上機實驗要求及標準--------------------------------------------------------------------------37實驗1復數ADT及其實現-----------------------------------------------------------------39實驗2線性表---------------------------------------------------------------------------------40實驗3棧和隊列------------------------------------------------------------------------------47實驗4串---------------------------------------------------------------------------------------53實驗5數組------------------------------------------------------------------------------------57實驗6樹與二叉樹---------------------------------------------------------------------------60實驗7圖---------------------------------------------------------------------------------------64實驗8查找------------------------------------------------------------------------------------68實驗9排序------------------------------------------------------------------------------------71第1局部C++根本知識各種數據結構以及相應算法的描述總是要選用一種語言工具。在計算機科學開展過程中，早期數據結構教材大都采用PASCAL語言為描述工具，后來出現了采用C語言為描述工具的教材版本、至今又出現了采用C++語言為描述工具的多種教材版本。本教實驗指導書是為已經學習過C++語言的學生而編寫。編寫實驗指導書目的為了配合理論教學。程序要求在C++Builder開發環境之下調試運行，采用面向對象方法進行設計。典型的數據結構被設計成為類〔class〕，典型算法設計成為類的函數成員，然后在主函數中聲明創立類對象，根據實際需要調用重要的算法。由于C++的使用具有一定的難度，為了同學更好的學習數據結構自身的知識內容，減輕描述工具所帶來的困難，這里針對數據結構上機實驗所必須的C++根本知識〔結構體、類等等〕做補充介紹。#include….//#include….//編譯預處理…………classA{………..};//類成員函數定義；…….intmain(){…………….}編譯預處理等類的相關程序編碼主函數程序代碼這局部內容詳細參見本指導書的第3局部的程序實例。二、結構體及運用數據結構課程所研究的問題均運用到“結構體”和“類”。在C++語言中結構體和函數又是理解和掌握“類”的語法根底。定義結構體的一般格式：struct結構體類型名{類型名1變量名1；//數據子域類型名2變量名2；……類型名n變量名n；}其中struct是保存字。結構體類型名由用戶自己命名。在使用時必須聲明一個具體的結構體類型的變量，聲明創立一個結構體變量的方法是：結構體類型名結構體變量名；一個結構體中可以包含多個數據子域。數據子域的類型名一般指根本數據類型〔intchar等〕，也可是已經定義的另一結構體名。數據子域變量名可以是簡單變量，也可以是數組。它們也可以稱為結構體的數據成員，它們的訪問控制具有‘公有’屬性。1.通過“結構體變量名.數據子域”可以訪問數據子域。//設計Student結構體，在主程序中運用。#include<iostream.h>#include<conio.h>#include<string.h>structStudent//定義結構體Student{longnum;//學號intx;//成績charname[10];//姓名}intmain(){Students1;//聲明創立一個結構體變量s1或者使用鍵盤輸入cin>>或者使用鍵盤輸入cin>>s1.num;cin>>s1.x;cin>>;s1.num=1001;s1.x=83;strcpy(,“李明”)；//輸出結構體變量s1的內容

cout<<“姓名：”<<<<endl;;cout<<“學號：”<<s1.num<<endl:cout<<“成績：”<<s1.x<<ednl;_getch();return0;}2.設計一維數組，每個數組元素是Student結構體類型，通過以下語句段可以說明結構體數組的一般用法：通過“結構體數組名[下標].數據子域”訪問數據域。Studenta[5];//聲明創立一個結構體數組afor(inti=0,i<5,i++){cout<<“學號：”;cin>>a[i].num;//輸出數組元素a[i]的學號域cout<<“姓名：”;cin>>a[i].name；//輸出數組元素a[i]的姓名域cout<<“成績：”;cin>>a[i].x;//輸出數組元素a[i]的成績域}以上是關于結構體的根本概念和簡單運用。三、類的根本概念及運用類的是面向對象程序的根本單位。類是由數據成員和相關的函數成員組成。從面向對象的角度考慮“學生”這個類，它不僅包括“學生”的一般屬性：學號、姓名、成績等等，還應包括對于這些屬性的操作：輸入/輸出、聽課、實驗、等等。類定義的一般格式：class類名{假設干數據成員；假設干函數成員；}；類的數據成員和函數成員均存在訪問控制權限問題。訪問控制分為三種：公有〔public〕、私有(private)和受護(protected)。數據成員的定義和結構體中的數據域定義是相似的。不同的是它們必須明確訪問控制。而公有數據成員，可以認為與結構體的數據域的訪問權限相同。成員函數的定義又和一般函數的定義根本相同。不同的是類中成員函數也必須明確訪問控制權限。如果在類之中定義成員函數帶函數體，并未有什么特殊之處。如果在類之中僅有成員函數的原型聲明，當在類定義之外定義函數體時，需要加上類限定標識“類名：：”。下面是“學生”類的定義：classStudents//定義類結構體Students{private://私有成員longnum;//學號intx;//成績charname[10];//姓名public://公有成員Students();~Students(){};voidSetDat(longn,intx0,char*na0){num=n;x=x0;strcpy(name,na0);}voidPrintOut();//輸出函數的原型聲明…….;};voidStudents::PrintOut()//輸出函數前加Students::{cout<<“姓名：”<<name<<endl;;cout<<“學號：”<<num<<endl:cout<<“成績：”<<x<<ednl;}在主程序中運用類Smain(){Studentss;//聲明創立一個類對象s，調用構造函數s.PrintOut();//輸出s的內容longm;inty;charxname[10];cout<<“輸入學號，成績，姓名：”;cin>>m>>y>>xname;s.SetDat(m,y,xname);//修改對象s數據s.PrintOut();//輸出改變后s的內容_getch();return0;}運行結果：姓名：O學號：0成績：0輸入學號，成績，姓名：100190WangMing姓名：WangMing學號：1001成績：90這個例題中數據成員全部定義為私有〔private〕，以便保證數據平安性。而函數成員全部定義為公有〔public〕成員函數，可以作為類對外部的的接口。通過s.SetDat(m,y,xname);直接訪公有函數成員SetDat()，將實參〔主函數的局部變量m,y,xname〕的數據賦給私有數據成員num，x，name。通過s.PrintOut();直接訪公有函數成員PrintOut()，間接訪問輸出私有成員num，x，name。四、結構體在類中的使用1．結構體數組做類的數據成員constintMAXSIZE=100;//數組的容量structElemType//數據元素的類型{intnumb;charname[20];longtel;};classSqlist{private:ElemTypeelem[MAXSIZE];//結構體ElemType類型的數組elem[]做數據成員intlength;public:Sqlist(void);~Sqlist(){};//其他函數……};2.結構體指針變量做類的數據成員structNodeType//結點的結構定義{intdata;//數據域NodeType*next;//指針域};classLink//類聲明{private:NodeType*Head;//指向結構構體NodeType的指針變量Head做數據成員public:Link(){Head=newNodeType;//為頭結點申請空間Head->next=Head;//頭結點Head形成空環};Head~Link(){};Headvoidcreat();voidouts();};第2局部書面練習題習題1緒論1.1單項選擇題1.數據結構是一門研究非數值計算的程序設計問題中,數據元素的①C、數據信息在計算機中的②A以及一組相關的運算等的課程。①A．操作對象Ｂ．計算方法Ｃ．邏輯結構Ｄ．數據映象②A．存儲結構Ｂ．關系Ｃ．運算Ｄ．算法2.數據結構DS(DataStruct)可以被形式地定義為DS=〔D，R〕，其中D是①B的有限集合，R是D上的②D有限集合。①A．算法Ｂ．數據元素Ｃ．數據操作Ｄ．數據對象②A．操作Ｂ．映象Ｃ．存儲Ｄ．關系3.在數據結構中，從邏輯上可以把數據結構分成。A．動態結構和靜態結構Ｂ．緊湊結構和非緊湊結構Ｃ．線性結構和非線性結構Ｄ．內部結構和外部結構4.算法分析的目的是①C，算法分析的兩個主要方面是②A。①A.找出數據結構的合理性B.研究算法中的輸入和輸出的關系C.分析算法的效率以求改良D.分析算法的易懂性和文檔性②A.空間復雜性和時間復雜性B.正確性和簡明性C.可讀性和文檔性D.數據復雜性和程序復雜性5.計算機算法指的是①C，它必具備輸入、輸出和②B等五個特性。①A.計算方法B.排序方法C.解決問題的有限運算序列D.調度方法②A.可行性、可移植性和可擴充性B.可行性、確定性和有窮性C.確定性、有窮性和穩定性D.易讀性、穩定性和平安性1.2填空題〔將正確的答案填在相應的空中〕1.數據邏輯結構包括樹形結構、圖形結構和線性結構三種類型，樹形結構和圖形結構合稱為非線性結構。2.在線性結構中，第一個結點沒有前驅結點，其余每個結點有且只有1個前驅結點；最后一個結點沒有后續結點，其余每個結點有且只有1個后續結點。3.在樹形結構中，樹根結點沒有前驅結點，其余每個結點有且只有1個直接前驅結點，葉子結點沒有后續結點，其余每個結點的直接后續結點可以任意多。4.在圖形結構中，每個結點的前驅結點數和后續結點數可以任意多。5.線性結構中元素之間存在一對一關系，樹形結構中元素之間存在一對多關系，圖形結構中元素之間存在多對多關系。6.算法的五個重要特性是__輸入,_輸出_,_確定性_,_可行性_,_有窮性。7.分析下面算法〔程序段〕，給出最大語句頻度n2，該算法的時間復雜度是_O(n2)_。for(i=0;i<n;i++)for(j=0;j<n;j++)A[i][j]=0;8.分析下面算法〔程序段〕，給出最大語句頻度n(n+1)/2，該算法的時間復雜度是__n2__。for(i=0;i<n;i++)for(j=0;j<i;j++)A[i][j]=0;9.分析下面算法〔程序段〕，給出最大語句頻度n3，該算法的時間復雜度是_O(n3)。s=0;for(i=0;i<n;i++)for(j=0;j<n;j++)for(k=0;k<n;k++)s=s+B[i][j][k];sum=s;10.分析下面算法〔程序段〕給出最大語句頻度n，該算法的時間復雜度是_O(n)_。i=s=0;while(s<n){i++;s+=i;//s=s+i}11.分析下面算法〔程序段〕給出最大語句頻度log2n，該算法的時間復雜度是_O(log2n)_。i=1;while(i<=n)i=i*2;1.3算法設計題試寫一算法,自大到小依次輸出順序讀入的三個數X,Y和Z的值.試寫一算法,求出n個數據中的最大值。寫出最大語句頻度，該算法的時間復雜度。習題答案1.11.C,A2.B,D3.C4.C,A5.C,B1.21.線性結構、樹形結構、圖形結構，非線性結構2.沒有、1、沒有、13.前驅、1、后續、任意多個4.任意多個5.一對一、一對多、多對多6.有窮性、確定性、可行性、輸入、輸出7.最大語句頻度：n2，時間復雜度：.O(n2)8.最大語句頻度：n(n+1)/2，時間復雜度：.O(n2)9.最大語句頻度：n3，時間復雜度：.O(n3)10.最大語句頻度：n，時間復雜度：.O(n)11.最大語句頻度：log2n，時間復雜度：.O(log2n)習題2線性表2.1單項選擇題1.一個向量〔即一批地址連續的存儲單元〕第一個元素的存儲地址是100，每個元素的長度為2，那么第5個元素的地址是__B__。A.110B.108C.100D.1202.線性表的順序存儲結構是一種__A_的存儲結構，而鏈式存儲結構是一種__C_的存儲結構。A．隨機存取B．索引存取C．順序存取D．散列存取3.線性表的邏輯順序與存儲順序總是一致的，這種說法__B_。A.正確B.不正確4.線性表假設采用鏈式存儲結構時，要求內存中可用存儲單元的地址__D_。A.必須是連續的B.局部地址必須是連續的C.一定是不連續的D.連續或不連續都可以5.在以下的表達中，正確的選項是_C_。線性表的順序存儲結構優于鏈表存儲結構線性表的順序存儲結構適用于頻繁插入/刪除數據元素的情況線性表的鏈表存儲結構適用于頻繁插入/刪除數據元素的情況線性表的鏈表存儲結構優于順序存儲結構6.每種數據結構都具備三個根本運算：插入、刪除和查找，這種說法_B_。A.正確B.不正確7.不帶頭結點的單鏈表head為空的判定條件是__A__。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL8.帶頭結點的單鏈表head為空的判定條件是_B_。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL9.非空的循環單鏈表head的尾結點〔由p所指向〕滿足_C_。A.p->next==NULLB.p==NULLC.p->next==headD.p==head10.在雙向循環鏈表的p所指結點之后插入s所指結點的操作是_D_。A.p->right=s;s->left=p;p->right->left=s;s->right=p->right;B.p->right=s;p->right->left=s;s->left=p;s->right=p->right;C.s->left=p;s->right=p->right;p->right=s;p->right->left=s;D.s->left=p;s->right=p->right;p->right->left=s;p->right=s;11.在一個單鏈表中，q所指結點是p所指結點的前驅結點，假設在q和p之間插入s結點，那么執行___B_。A.s->next=p->next;p->next=s;C.p->next=s->next;s->next=p;B.q->next=s;s->next=p;D.p->next=s;s->next=q;12.在一個單鏈表中，假設p所指結點不是最后結點，在p之后插入s所指結點，那么執行__B__。A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;C.s->next=p->next;p=s;C.p->next=s;s->next=p;13.在一個單鏈表中，假設刪除p所指結點的后續結點，那么執行__A__。A.p->next=p->next->next；B.p=p->next;p->next=p->next->next；C.p->next=p->next;D.p=p->next->next；14.從一個具有n個結點的單鏈表中查找其值等于x結點時，在查找成功的情況下，需平均比擬__D__個結點。A.nB.n/2C.(n-1)/2D.(n+1)/215.在一個具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是__B__。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)16.給定有n個元素的向量，建立一個有序單鏈表的時間復雜度是__C__。A.O(1)〕B.O(n)C.O(n2)D.O(n*log2n)2.2填空題〔將正確的答案填在相應的空中〕1.單鏈表可以做_線性節表_的鏈接存儲表示。2.在雙鏈表中，每個結點有兩個指針域，一個指向_前驅結點_，另一個指向_后繼結點_。3.在一個單鏈表中p所指結點之前插入一個s(值為e)所指結點時，可執行如下操作：q=head;while(q->next!=p)q=q->next;s=newNode;s->data=e;q->next=s;//填空s->next=q;//填空4.在一個單鏈表中刪除p所指結點的后繼結點時，應執行以下操作：q=p->next;p->next=q->next;//填空deleteq;//填空5.在一個單鏈表中p所指結點之后插入一個s所指結點時，應執行s->next=p->next_和p->next=__s__的操作。6.對于一個具有n個結點的單鏈表，在p所指結點后插入一個新結點的時間復雜度是O(1)；在給定值為x的結點后插入一個新結點的時間復雜度是O(n)。2.3算法設計題:1.設順序表va中的數據元數遞增有序。試寫一算法，將x插入到順序表的適當位置上，以保持該表的有序性。2.試寫一算法，實現順序表的就地逆置，即利用原表的存儲空間將線性表〔a1,a2,….an〕逆置為(an,an-1,….,a1)。3.線性表中的元素以值遞增有序排列，并以單鏈表作存儲結構。試寫一算法，刪除表中所有大于x且小于y的元素〔假設表中存在這樣的元素〕同時釋放被刪除結點空間。4.試寫一算法，實現單鏈表的就地逆置(要求在原鏈表上進行)。習題答案2.11.B2.A,C3.B4.D5.C6.A7.A8.B9.C10.D11.B12.B13.A14.D15.B16.C2.21.線性結表2.前驅結點、后繼結點3.s,p4.q->next,q5.p->next,s6.O(1),O(n)習題3棧和隊列3.1單項選擇題1.一個棧的入棧序列a，b，c，d，e，那么棧的不可能的輸出序列是____。A.edcbaB.decbaC.dceabD.abcde2.假設一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，假設p1=n，那么pi為____。A.iB.n=iC.n-i+1D.不確定3.棧結構通常采用的兩種存儲結構是____。A.順序存儲結構和鏈式存儲結構散列方式和索引方式鏈表存儲結構和數組線性存儲結構和非線性存儲結構4.判定一個順序棧ST〔最多元素為m0〕為空的條件是____。A.top!=0B.top==0C.top!=m0D.top==5.判定一個順序棧ST〔最多元素為m0〕為棧滿的條件是____。A.top！=0B.top==0C.top！=6.棧的特點是____，隊列的特點是____。A.先進先出B.先進后出7.向一個棧頂指針為HS的鏈棧中插入一個s所指結點時，那么執行____。(不帶空的頭結點)HS—＞next=s;B.s—＞next=HS—＞next;HS—＞next=s;C.s—＞next=HS;HS=s;D.s—＞next=HS;HS=HS—＞next;8.從一個棧頂指針為HS的鏈棧中刪除一個結點時，用x保存被刪結點的值，那么執行____。(不帶空的頭結點)A.x=HS;HS=HS—＞next;B.x=HS—＞data;C.HS=HS—＞next;x=HS—＞data;D.x=HS—＞data;HS=HS—＞next;9.一個隊列的數據入列序列是1，2，3，4，那么隊列的出隊時輸出序列是____。A.4，3，2，1B.1，2，3，4C.1，4，3，2D.3，2，4，110.判定一個循環隊列QU〔最多元素為m0〕為空的條件是____。A.rear-front==m0B.rear-front-1==m0C.front==rearD.front==rear+111.判定一個循環隊列QU〔最多元素為m0,m0==Maxsize-1〕為滿隊列的條件是____。A.((rear-front)+Maxsize)%Maxsize==m0B.rear-front-1==m0C.front==rearD.front==rear+112.循環隊列用數組A[0，m-1]存放其元素值，其頭尾指針分別是front和rear，那么當前隊列中的元素個數是____。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front13.棧和隊列的共同點是____。A.都是先進后出B.都是先進先出C.只允許在端點處插入和刪除元素D.沒有共同點3.2填空題〔將正確的答案填在相應的空中〕1.向量、棧和隊列都是____結構，可以在向量的____位置插入和刪除元素；對于棧只能在____插入和刪除元素；對于隊列只能在____插入元素和____刪除元素。2.向一個長度為n的向量的第i個元素〔1≤i≤n+1〕之前插入一個元素時，需向后移動____個元素。3.向一個長度為n的向量中刪除第i個元素〔1≤i≤n〕時，需向前移動____個元素。4.向棧中壓入元素的操作是____。5.對棧進行退棧時的操作是____。6.在一個循環隊列中，隊首指針指向隊首元素的____。7.從循環隊列中刪除一個元素時，其操作是____。8.在具有n個單元的循環隊列中，隊滿時共有____個元素。9.一個棧的輸入序列是12345，那么棧的輸出序列43512是____。10.一個棧的輸入序列是12345，那么棧的輸出序列12345是____。3.3算法設計題:1.輸入一個任意的非負十進制整數,輸出與其等值的八進值數。2.按照四那么運算加、減、乘、除和冪運算〔↑〕優先關系的慣例，并仿照教科書3.2節例3—1的格式，畫出對以下算術表達式求值時操作數棧和運算符棧的變化過程：A-B*C/D+E↑F3.假設以帶頭結點的循環鏈表表示隊列，并且只設一個指針指向隊尾元素結點〔注意不設頭指針〕，試編寫相應的隊列初始化、入隊列和出隊列的算法。習題答案3.11.C2.C3.A4.B5.D6.BA7.C8.B D9.CB10.C11.A12.A13.C3.21.線性、任何、棧頂、隊尾、隊首2.n-i+13.n-i4.先移動棧頂指針，后存入元素5.先取出元素，后移動棧頂指針6.前一個位置7.先移動隊首元素，后取出元素8.n-19.不可能的10.可能的習題4串4.1單項選擇題1．以下表達中正確的選項是。A.串是一種特殊的線性表 B.串的長度必須大于零C.串中無素只能是字母 D.空串就是空白串2．空串與空格串是相同的，這種說法____。A.正確B.不正確3．串是一中特殊的線性表，其特殊性表達在____。A.可以順序存儲 B.數據元素是一個字符C.可以鏈接存儲 D.數據元素可以是多個字符4．設有兩個串p和q，求q在p中首次出現的位置的運算稱作____。A.連接 B.模式匹配C.求子串 D.求串長5．設串s1=’ABCDEFG’，s2=’PQRST’，函數con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號i的字符開始的j個字符組成的子串，len(s)返回串s的長度，那么con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結果串是____。A.BCDEF B.BCDEFGC.BCPQRST D.BCDEFEF6．設串的長度為n，那么它的子串個數為。A.n B.n(n+1) C.n(n+1)/2 D.n(n+1)/2+14.2填空題〔將正確的答案填在相應的空中〕1．串的兩種最根本的存儲方式是____。2．兩個串相等的充分必要條件是____。3．空串是____，其長度等于____。4．空格串是____，其長度等于____。5．設s=’I︺AM︺A︺TEACHER’,其長度是____。4.3判斷題1．串是由有限個字符構成的連續序列，串長度為串中字符的個數，子串是主串中符構成的有限序列。 〔〕2．子串定位函數的時間復雜度在最壞情況下為O〔n*m〕，因此子串定位函數沒有實際使用的價值。 〔〕3．KMP算法的最大特點是指主串的指針不需要回溯。 〔〕4．設模式串的長度為m，目標串的長度為n；當n≈m且處理只匹配一次的模式時，樸素的匹配〔即子串定位函數〕算法所花的時間代價也可能會更為節省。 〔〕5．如果一個串中的所有字符均在另一串中出現，那么說前者是后者的子串。 〔〕4.3算法設計題1．編寫算法，從串s中刪除所有和串t相同的子串。2．編寫算法，實現串的根本操作Replace(&S,T,V)。3．寫一個遞歸算法來實現字符串逆序存儲，要求不另設存儲空間。習題答案4.11．A 2．B3．B4．B5．D6．C4.21．順序存儲方式和鏈接存儲方式2．兩個串的長度相等且對應位置的字符相同3．零個字符的串、零4．由一個或多個空格字符組成的串、其包含的空格個數5．144.3 × × √ √ ×4.43.voidreverse(chararr[]){charch;inti=1; do{cin>>ch;reverse(arr);arr[i]=ch;i++;}while(ch!=’#’&&i<n)}習題5數組和廣義表5.1單項選擇題1.常對數組進行的兩種根本操作是____。A.建立與刪除B.索引和修改C.對數據元素的存取和修改D.查找與索引2.二維數組M的成員是6個字符〔每個字符占一個存儲單元，即一個字節〕組成的串，行下標i的范圍從0到8，列下標j的范圍從0到9，那么存放M至少需要①__個字節；M數組的第8列和第5行共占②____個字節。①A.90B.180C.240D.540②A.108B.114C.54D.603.二維數組A中，每個元素的長度為3個字節，行下標i從0到7，列下標j從0到9，從首地址SA開始連續存放在存儲器內，存放該數組至少需要的字節數是____。A.80B.100C.240D.2704.二維數組A中，每個元素A的長度為3個字節，行下標i從0到7，列下標j從0到9，從首地址SA開始連續存放在存儲器內，該數組按行存放時，數組元素A[7][4]的起始地址為____。A.SA+141B.SA+144C.SA+222D.SA+2255.二維數組A中，每個元素A的長度為3個字節，行下標i從0到7，列下標j從0到9，從首地址SA開始連續存放在存儲器內，該數組按列存放時，元素A[4][7]的起始地址為____。A.SA+141B.SA+180C.SA+222D.SA+2255.2填空題〔將正確的答案填在相應的空中〕1.二維數組A[m][n]采用行序為主方式存儲，每個元素占k個存儲單元，并且第一個元素的存儲地址是LOC(A[0][0])，那么A[i][j]的地址是____LOC(A[0][0])+(n*i+j)*k___。2.二維數組A[10][20]采用列序為主方式存儲，每個元素占一個存儲單元并且A[0][0]的存儲地址是200，那么A[6][12]的地址是____。3.二維數組A[10..20][5..10]采用行序為主方式存儲，每個元素占4個存儲單元，并且A[10][5]的存儲地址是1000，那么A[18][9]的地址是____。4．求以下廣義表操作的結果：(1)GetTail[GetHead[((a,b),(c,d))]];(2)GetTail[GetHead[GetTail[((a,b),(c,d))]]]5.利用廣義表的GetHead和GetTail操作寫出如上題的函數表達式,把原子banana分別從以下廣義表中別離出來.(1)L1=(((apple)),((pear)),(banana),orange);(2)L2=(apple,(pear,(banana),orange));5.3算法設計題:1.假設稀疏矩陣A和B均以三元組順序表作為存儲結構。試寫出矩陣相加的算法，另設三元組表C存放結果矩陣。2.假設系數矩陣A和B均以三元組順序表作為存儲結構。試寫出滿足以下條件的矩陣相加的算法：假設三元組順序表A的空間足夠大，將矩陣B加到矩陣A上，不增加A，B之外的附加空間，你的算法能否到達O〔m+n〕的時間復雜度？其中m和n分別為A，B矩陣中非零元的數目。3．試編寫一個以三元組形式輸出用十字鏈表表示的稀疏矩陣中非零元素及其下標的算法。習題答案5.11.C2.D,A3.C4.C5.B5.21.LOC(A[0][0])+(n*i+j)*k2.200+〔6*20+12〕=3263.1000+((18-10)*6+(9-5))*4=12084．(1).(b)(2).(d)5.(1)GetHead[GetHead[GetTail[GetTail[L1]]]];(2)GetHead[GetHead[GetHead[GetTail[L2]]]];習題6樹和二叉樹6.1單項選擇題1.由于二叉樹中每個結點的度最大為2，所以二叉樹是一種特殊的樹，這種說法____。A.正確B.錯誤2.假定在一棵二叉樹中，雙分支結點數為15，單分支結點數為30個，那么葉子結點數為個。A．15 B．16 C．17 D．473.按照二叉樹的定義，具有3個結點的不同形狀的二叉樹有____種。A.3B.4C.5D.64.按照二叉樹的定義，具有3個不同數據結點的不同的二叉樹有____種。A.5B.6C.30D.325.深度為5的二叉樹至多有____個結點。A.16B.32C.31D.106.設高度為h的二叉樹上只有度為0和度為2的結點，那么此類二叉樹中所包含的結點數至少為____。 A.2hB.2h-1C.2h+1D.h+17.對一個滿二叉樹，m個樹葉，n個結點，深度為h，那么____。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-18.任何一棵二叉樹的葉結點在先序、中序和后序遍歷序列中的相對次序____。A.不發生改變B.發生改變C.不能確定D.以上都不對9.如果某二叉樹的前根次序遍歷結果為stuwv，中序遍歷為uwtvs，那么該二叉樹的后序為____。A.uwvtsB.vwutsC.wuvtsD.wutsv10.二叉樹的前序遍歷序列中，任意一個結點均處在其子女結點的前面，這種說法____。A.正確B.錯誤11.某二叉樹的前序遍歷結點訪問順序是abdgcefh，中序遍歷的結點訪問順序是dgbaechf，那么其后序遍歷的結點訪問順序是____。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca12.在一非空二叉樹的中序遍歷序列中，根結點的右邊____。A.只有右子樹上的所有結點B.只有右子樹上的局部結點C.只有左子樹上的局部結點D.只有左子樹上的所有結點13.如圖6.1所示二叉樹的中序遍歷序列是____。A.abcdgefB.dfebagcC.dbaefcgD.defbagcggcefdbaaagedbchf圖6.2圖6.1a14.一棵二叉樹如圖6.2所示，其中序遍歷的序列為____。aA.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgha15．設a,b為一棵二叉樹上的兩個結點，在中序遍歷時，a在b前的條件是。aA．a在b的右方 B．a在b的左方C．a是b的祖先 D．a是b的子孫16.某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是____。A.acbedB.decabC.deabcD.cedba17.實現任意二叉樹的后序遍歷的非遞歸算法而不使用棧結構，最正確方案是二叉樹采用____存儲結構。A.二叉鏈表B.廣義表存儲結構C.三叉鏈表D.順序存儲結構18.如圖6.3所示的4棵二叉樹，____不是完全二叉樹。(A)(B)(C)(D)(A)(B)(C)(D)圖6.319.如圖6.4所示的4棵二叉樹，____是平衡二叉樹。〔A〕〔A〕〔B〕〔C〕〔D〕圖8.84棵二叉樹(A)(B)(C)(D)圖6.420.在線索化二叉樹中，t所指結點沒有左子樹的充要條件是____。A.t—＞left=NULLB.t—＞ltag=1C.t—＞ltag=1且t—＞left=NULLD.以上都不對21.二叉樹按某種順序線索化后，任一結點均有指向其前驅和后續的線索，這種說法____。A.正確B.錯誤22.二叉樹為二叉排序樹的充分必要條件是其任一結點的值均大于其左孩子的值、小于其右孩子的值。這種說法____。A.正確B.錯誤23.具有五層結點的二叉平衡樹至少有____個結點。A.10B.12C.15D.1724.樹的根本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的根本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉化得到的二叉樹叫做這棵數對應的二叉樹。結論____是正確的。A.樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同B.樹的后根遍歷序列與其對應的二叉樹的后序遍歷序列相同C.樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同D.以上都不對25.樹最適合用來表示____。A.有序數據元素B.無序數據元素C.元素之間具有分支層次關系的數據D.元素之間無聯系的數據k1k111kkkkkk21435671.有一棵樹如圖6.5所示，答復下面的問題：⑴這棵樹的根結點是____；⑵這棵樹的葉子結點是____；⑶結點k3的度是____；⑷這棵樹的度是____；⑸這棵樹的深度是____；⑹結點k3的子女是____；圖6.5一棵樹⑺結點k3的父結點是____；圖6.5一棵樹2.指出樹和二叉樹的三個主要差異____、____、____。3.從概念上講，樹與二叉樹是兩種不同的數據結構，將樹轉化為二叉樹的根本目的是____。4.一棵二叉樹的結點數據采用順序存儲結構，存儲于數組t中，如圖6.6所示，那么該二叉樹的鏈接表示形式為____。12123456789101112131415161718192021eafdgcjlhb圖6.6一棵二叉樹的順序存儲數組t6.在一棵二叉樹中，度為零的結點的個數為n0，度為2的結點的個數為n2，那么有n0=____。7.一棵二叉樹的第i〔i≥1〕層最多有____個結點；一棵有n〔n>0〕個結點的滿二叉樹共有____個葉子和____個非終端結點。8.結點最少的樹為____，結點最少的二叉樹為____。iaiae d bchHf圖6.7一棵二叉樹ji10.由如圖6.7所示的二叉樹，答復以下問題：⑴其中序遍歷序列為____；⑵其前序遍歷序列為____；⑶其后序遍歷序列為____；6.3簡答題1.根據二叉樹的定義，具有三個結點的二叉樹有5種不同的形態，請將它們分別畫出。2.假設一棵二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。gcgcefdba圖6.8一棵樹3.由如圖6.7所示的二叉樹，答復以下問題：〔1〕畫出該二叉樹的中序線索二叉樹；〔2〕畫出該二叉樹的后序線索二叉樹；〔3〕畫出該二叉樹對應的森林。4.一棵樹如圖6.8所示，轉化為一棵二叉樹，表示為____。5.以數據集{4，5，6，7，10，12，18}為結點權值，畫出構造Huffman樹的每一步圖示，計算其帶權路徑長度為。6.一棵含有N個結點的k叉樹,可能到達的最大深度和最小深度各為多少?7.證明:一棵滿k叉樹上的葉子結點數n和非葉子結點數n之間滿足以下關系:n=(k-1)n+16.4算法設計題1.編寫按層次順序〔同一層自左至右〕遍歷二叉樹的算法。2．試編寫算法，對一棵二叉樹,統計葉子的個數。3．試編寫算法，對一棵二叉樹根結點不變，將左、右子樹進行交換，樹中每個結點的左、右子樹進行交換。7.假設用于通訊的電文僅有八個字母(a,b,c,d,e,f,g,h)組成，字母在電文中出現的頻率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。試為這八個字母設計哈夫曼編碼。使用0-7的二進制表示形式是另一種編碼方案。對于上述實例，比擬兩種方案的優缺點。8.試編寫算法，對一棵以孩子-兄弟鏈表表示的樹統計葉子的個數。假設一棵二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。請畫出該樹。習題答案6.11.B2.B3.C4.C5.C6.A7.D8.A9.C10.A11.D2.A13.B14.B15.B16.D17.C18.C19.B20.B21.B22.B23.B24.A25.C6.21.⑴k1⑵k2,k5,k7,k4⑶2⑷3⑸4⑹k5,k6⑺k1eaEfjcdeaEfjcdlghb圖6.9樹中結點的最大度數沒有限制，而二叉樹結點的最大度數為2；樹的結點無左、右之分，而二叉樹的結點有左、右之分；3.樹可采用孩子-兄弟鏈表〔二叉鏈表〕做存儲結構，目的并利用二叉樹的已有算法解決樹的有關問題。4.如圖6.9所示5.2k-1、2k-1、2k-2+16.n2+17.2i-12[log2n+1]-12[log2n+1]–18.只有一個結點的樹；空的二叉樹9.5；如圖6.10所示a圖6.10樹形5種aaaaa圖6.10樹形5種aaaacccccbbbbbb6.31.5種,圖6.11EBEFEBEFAECDKGHIJ圖6.12圖6.11樹形5種3.中序線索二叉樹如圖6.13〔左〕所示；后序線索二叉樹如圖6.13〔右〕所示；該二叉樹轉換后的的森林如圖6.14所示。圖6.13圖6.13aa11dhjbkc圖6.14對應的森林iefababcedig圖6.15一棵樹的孩子兄弟表示6237623725191813121096745圖6.16Huffman樹6.一棵含有N個結點的k叉樹,可能到達的最大深度h=N-k+1，最小深度各為:logkN+1。習題7圖7.1單項選擇題1．在一個圖中，所有頂點的度數之和等于所有邊數的____倍。A.1/2B.1C.2D.42．任何一個無向連通圖的最小生成樹。A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在3．在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的____倍。A.1/2B.1C.2D.44．一個有n個頂點的無向圖最多有____條邊。A.nB.n(n-1)C.n(n-1)/2D.2n5．具有4個頂點的無向完全圖有____條邊。A.6B.12C.16D.206．具有6個頂點的無向圖至少應有____條邊才能確保是一個連通圖。A.5B.6C.7D.87．在一個具有n個頂點的無向圖中，要連通全部頂點至少需要____條邊。A.nB.n+1C.n-1D.n/28．對于一個具有n個頂點的無向圖，假設采用鄰接矩陣表示，那么該矩陣的大小是____。A.nB.(n-1)2C.n-1D.n9．對于一個具有n個頂點和e條邊的無向圖，假設采用鄰接表表示，那么表頭向量的大小為_①___；所有鄰接表中的結點總數是_②___。①A.nB.n+1C.n-1D.n+e②A.e/2B.eC.2eD.n+e10．一個圖如圖7.1所示，假設從頂點a出發按深度搜索法進行遍歷，那么可能得到的一種頂點序列為__①__；按廣度搜索法進行遍歷，那么可能得到的一種頂點序列為__②__。①A.a,b,e,c,d,fB.e,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b②A.a,b,c,e,d,fB.a,b,c,e,f,dC.a,e,b,c,f,dD.a,c,f,d,e,bbbaecdf 圖7.1一個無向圖圖7.1一個無向圖11．一有向圖的鄰接表存儲結構如圖7.2所示。112345324524^^^^^圖7.2一個有向圖的鄰接表存儲結構圖7.2一個有向圖的鄰接表存儲結構⑴根據有向圖的深度優先遍歷算法，從頂點v1出發，所得到的頂點序列是____。A.v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5C.v1,v3,v4,v5,v2D.v1,v4,v3,v5,v2⑵根據有向圖的寬度優先遍歷算法，從頂點v1出發，所得到的頂點序列是____。A.v1,v2,v3,v4,v5B.v1,v3,v2,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v212．采用鄰接表存儲的圖的深度優先遍歷算法類似于二叉樹的____。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷13．采用鄰接表存儲的圖的廣度優先遍歷算法類似于二叉樹的____。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷14．判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以利用____。A.求關鍵路徑的方法B.求最短路徑的Dijkstra方法C.廣度優先遍歷算法D.深度優先遍歷算法15．關鍵路徑是事件結點網絡中。A.從源點到匯點的最長路徑B.從源點到匯點的最短路徑C.最長的回路D.最短的回路16．下面不正確的說法是。〔1〕在AOE網中，減小一個關鍵活動上的權值后，整個工期也就相應減小；〔2〕AOE網工程工期為關鍵活動上的權之和；〔3〕在關鍵路徑上的活動都是關鍵活動，而關鍵活動也必在關鍵路徑上。A.〔1〕 B.〔2〕 C.〔3〕 D.〔1〕、〔2〕17．用DFS遍歷一個無環有向圖，并在DFS算法退棧返回時打印出相應的頂點，那么輸出的頂點序列是。A.逆拓撲有序的 B.拓撲有序的 C.無序的18．在圖7.3所示的拓撲排列的結果序列為。A.125634 B.516234 C.123456 D.521634圖7.3有向圖圖7.3有向圖19．一個有n個頂點的無向連通圖，它所包含的連通分量個數為。A.0 B.1 C.n D.n+120．對于一個有向圖，假設一個頂點的入度為k1,、出度為k2，那么對應鄰接表中該頂點單鏈表中的結點數為。A.k1 B.k2 C.k1-k2 D.k1+k221．對于一個有向圖，假設一個頂點的入度為k1,、出度為k2，那么對應逆鄰接表中該頂點單鏈表中的結點數為。A.k1 B.k2 C.k1-k2 D.k1+k27.2填空題〔將正確的答案填在相應餓空中〕1．n個頂點的連通圖至少____條邊。2．在無權圖G的鄰接矩陣A中，假設(vi,vj)或＜vi,vj＞屬于圖G的邊集合，那么對應元素A[i][j]等于____，否那么等于____。3．在無向圖G的鄰接矩陣A中，假設A[i][j]等于1，那么A[j][i]等于____。4．圖G的鄰接表如圖7.4所示，其從頂點v1出發的深度優先搜索序列為____，其從頂點v1出發的廣度優先搜索序列為____。v1v1v3v2v4v5v6v2v5v4v3v5^^v6v4v6v3圖7.4圖G的鄰接表5．一個有向圖的鄰接矩陣表示，計算第i個結點的入度的方法是____。6．一個圖的鄰接矩陣表示，刪除所有從第i個結點出發的邊的方法是____。7．如果含n個頂點的圖形成一個環，那么它有棵生成樹。8．一個非連通無向圖，共有28條邊，那么該圖至少有個頂點。9．遍歷圖的過程實質上是。當以鄰接表做存儲結構時，BFS遍歷圖的時間復雜度為，DFS遍歷圖的時間復雜度為，兩者不同之處在于，反映在數據結構上的差異是。10．一個圖的表示法是唯一的，而表示法是不唯一的。11．有向圖中的結點前驅后繼關系的特征是。12．假設無向圖G的頂點度數最小值大于等于時，G至少有一條回路。13．根據圖的存儲結構進行某種次序的遍歷，得到的頂點序列是的。7.3綜合題15156243〔1〕每個頂點的入/出度；〔2〕鄰接矩陣；〔3〕鄰接表；〔4〕逆鄰接表；〔5〕強連通分量。圖7。5一個有向圖圖7。5一個有向圖babadcef16111515151613141221〔1〕圖7.661261213212495201516106154372圖7.73．試列出圖7.8中全部的拓撲排序序列。1123456圖7.84．請用圖示說明圖7.9從頂點a到其余各頂點之間的最短路徑。5543223356abdfce圖7.95．AOE網有9個結點：V1，V2，V3，V4，V5，V6，V7，V8，V9，其鄰接矩陣如下：(1)請畫出該AOE圖。(2)計算完成整個方案需要的時間。(3)求出該AOE網的關鍵路徑。∝645∝∝∝∝∝∝∝∝∝1∝∝∝∝∝∝∝∝1∝∝∝∝∝∝∝∝∝2∝∝∝∝∝∝∝∝∝97∝∝∝∝∝∝∝∝4∝∝∝∝∝∝∝∝∝2∝∝∝∝∝∝∝∝4∝∝∝∝∝∝∝∝∝習題答案7.1 1.C 2.B 3.B 4.C 5.A 6.A 7.C8.D 9.AC 10.DB 11.CB 12.A 13.D 14.D 15.A 16.A 17.A 18.B 19.B 20.B 21.A7.21.n-1 2.1;03.14.v1,v2,v3,v6,v5,v4；v1,v2,v5,v4,v3,v65.求矩陣第i列非零元素之和6.將矩陣第i行全部置為零7.n8.99.對每個頂點查找其鄰接點的過程；O〔n+e〕〔e為圖中的邊數〕；O〔n+e〕；遍歷圖的順序不同；DFS采用棧存儲訪問過的結點，BFS采用隊列存儲訪問過的結點。10．鄰接矩陣鄰接表11．一個結點可能有假設干個前驅，也可能有假設干個后繼12．213．唯babadce1115131412f6612495106154372〔2〕3．152364152634156234561234516234512634512364W=3W=7W=3W=7W=9W=6W=543233abdfce5．(1)該AOE圖為：(2)完成整個方案需要18天。(3)關鍵路徑為：〔V1，V2，V5，V7，V9〕和〔V1，V2，V5，V8，V9，〕習題8查找8.1單項選擇題1.順序查找法適合于存儲結構為____的線性表。A.散列存儲B.順序存儲或鏈接存儲C.壓縮存儲D.索引存儲2.對線性表進行二分查找時，要求線性表必須____。A.以順