算法與數(shù)據(jù)結構習題

PAGEPAGE18第1章數(shù)據(jù)結構概論一、判斷題1算法可以沒有輸入語句。2數(shù)據(jù)的邏輯結構按照數(shù)據(jù)元素前驅的個數(shù)劃分為線性與非線性兩類，線性的數(shù)據(jù)結構指數(shù)據(jù)元素只有一個前驅，非線性的則有多個前驅。3數(shù)據(jù)結構包括數(shù)據(jù)間的邏輯結構、數(shù)據(jù)的存儲方式和數(shù)據(jù)的運算三個方面。二、選擇題1算法的時間復雜度取決于。(A)．問題的規(guī)模(B)．待處理數(shù)據(jù)的初態(tài)(C)．編碼的語言(D)．占用內存的大小2算法與程序的主要區(qū)別在于程序可以不滿足算法的B。(A)．確定性(B)．有窮性(C)．可行性(D)．健壯性3.算法分析的兩個方面是。(A)．空間復雜性和時間復雜性(B)．正確性和簡明性(C)．可讀性和文檔性(D)．數(shù)據(jù)復雜性和程序復雜性三、填空題1若算法中語句頻度之和為，則算法的時間復雜度為。2數(shù)據(jù)的存儲結構分為、、和四種。3在線性結構、樹結構和圖結構中，前驅和后繼結點之間分別存在著、和的關系。4算法的計算工作量大小和實現(xiàn)算法所需的存儲單元多少，分別稱為計算的和。四、應用題1計算帶下劃線語句的執(zhí)行次數(shù)，n為已知的正整數(shù)。(1)x=91,y=n;while(y>0){if(x>100){x=x-10;y--;}elsex++;}(2)j=0，k=0;while(k<n){j++;k+=10*j;}2一個算法所需時間由下述遞歸方程表示，試求出該算法的時間復雜度的級別。其中：n是問題的規(guī)模，為簡單起見，可設n是2的整數(shù)冪。第2章線性表一、判斷題1線性關系的邏輯結構與存儲結構總是一致的。2每種數(shù)據(jù)結構都包括插入、刪除和查找這三種基本運算。3線性表中的每個結點最多只有一個前驅和一個后繼。4線性的數(shù)據(jù)結構既可以順序存儲，也可以鏈接存儲；非線性的數(shù)據(jù)結構則只能鏈接存儲。5順序存儲方式只能用于存儲線性結構。6多維數(shù)組是向量的推廣。7設串s的長度為n，則s的子串個數(shù)最多為n(n+1)/2。8單鏈表從任何一個結點出發(fā)，都能訪問到所有結點。9線性表的長度是線性表所占用的存儲空間的大小。10雙循環(huán)鏈表中，任意一結點的后繼指針均指向其邏輯后繼。11數(shù)據(jù)結構、數(shù)據(jù)元素、數(shù)據(jù)項在計算機中的映象(或表示)分別稱為存儲結構、結點、數(shù)據(jù)域。12線性表的順序存儲結構優(yōu)于鏈式存儲結構。二、選擇題1若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度為，元素的移動次數(shù)為(0≤i≤n)。(A)．O(0)(B)．O(1)(C)．O(n)(D)．O(n2)(E)．n-i+1(F)．n-i(G)．i(H)．i-12在長度為n的順序存儲的線性表中，刪除第i個元素(0≤i≤n-1)時，需要從前向后依次前移個元素。(A)．n-i(B)．n-i+1(C)．n-i-1(D)．i3從解決問題的需要出發(fā)，為實現(xiàn)必要的功能所建立的數(shù)據(jù)結構，稱為。(A)．物理結構(B)．邏輯結構(C)．數(shù)據(jù)類型(D)．數(shù)據(jù)對象4若長度為n的線性表采用順序存儲結構，在其第i(0≤i≤n)個位置插入一個新元素的平均移動元素移動次數(shù)為，在其第i(0≤i≤n-1)個位置刪除一個元素的平均移動元素移動次數(shù)為。(A)．n(B)．(n+1)/2(C)．n/2(D)．(n-1)/25若長度為n的無序線性表采用順序存儲結構，在其中查找某個元素時，所需要的平均比較的次數(shù)為。(A)．n(B)．(n-1)/2(C)．n/2(D)．(n+1)/26對于只在首、尾兩端進行插入操作的線性表，宜采用的存儲結構為。(A)．順序表(B)．帶頭指針的單鏈表(C)．帶尾指針的單循環(huán)鏈表(D)．單鏈表7在一個單鏈表中，若要在指針q所指結點的后面插入一個由指針p所指向的結點，則執(zhí)行。(A)．q->link=p->link；p->link=q；(B)．p->link=q->link；q=p；(C)．q->link=p->link；p=q；(D)．p->link=q->link；q->link=p；8在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結點，則執(zhí)行。(A)．HL=p;p->next=HL;(B)．p->link=HL;HL=p;(C)．p->link=HL;p=HL;(D)．p->link=HL->link;HL->link=p;9在一個單鏈表HL中，若要刪除由指針q所指向結點的后繼結點，則執(zhí)行。(A)．p=q->link;p->link=q->link;deletep;(B)．p=q->link;q->link=p;deletep;(C)．p=q->link;q->link=p->link;deletep;(D)．q->link=q->link->link;q->link=q;10設p為有頭結點雙向循環(huán)鏈表中某結點的指針，lLink為左鏈指針，rLink為右鏈指針，則下述表達式中，不恒為真。(A)．p->rLink->lLink==p(B)．p->rLink->lLink==p->lLink->rLink(C)．p->lLink->rLink==p(D)．p->rLink->rLink==p->lLink->lLink11若某鏈表最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個結點，則采用存儲方式最節(jié)省時間。(A)．單鏈表(B)．雙向鏈表(C)．帶頭結點的雙循環(huán)鏈表(D)．單循環(huán)鏈表12鏈表不具有的特點是。(A)．可隨機訪問任一元素(B)．插入刪除不需要移動元素(C)．不必事先估計存儲空間(D)．所需空間與線性表長度成正比13線性表采用鏈式存儲時，其地址。(A)．連續(xù)的(B)．部分連續(xù)的(C)．一定是不連續(xù)的(D)．連續(xù)與否均可14設有一8×8下三角矩陣A[8][8]，采用按行壓縮存儲的方式存放在一維數(shù)組B[]中，則數(shù)組B[]的容量至少需要個元素空間。(A)．32(B)．36(C)．16(D)．64三、填空題1對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復雜度為，在表尾插入元素的時間復雜度為。2在線性表的單鏈接存儲中，若一個元素所在結點的地址為p，則其后繼結點的地址為，若假定p為一個數(shù)組a中的下標，則其后繼結點的下標為。3在單循環(huán)鏈表中，最后一個結點的指針指向結點。4在雙向鏈表中每個結點包含有兩個指針域，一個指向其結點，另一個指向其結點。5在雙向循環(huán)鏈表中表頭結點的左指針域指向結點，最后一個結點的右指針域指向結點。6在以HL為表頭指針的帶附加表頭結點的單鏈表和單循環(huán)鏈表中，鏈表為空的條件分別為和。7在雙循環(huán)鏈表L中，指針p所指結點為尾結點的條件為。8在單鏈表中，如果要使指針p指向它所指結點的后繼結點，其語句是。9在一個稀疏矩陣中，每個非零元素所對應的三元組包括該元素的、和三項。10二維數(shù)組A[4][5]按行優(yōu)先存儲方法存儲在內存中，若每個元素占2個存儲單元，且數(shù)組中第一個元素的存儲地址為120，則元素A[3][4]的存儲地址為。如果其余條件不變，但是數(shù)組的存放方式變?yōu)榱行騼?yōu)先，則元素A[3][4]的存儲地址變?yōu)?。四、算法設計1編寫算法將以數(shù)組表示方式的順序表原地逆置。2對于帶附加頭結點的單鏈表，給出下列算法的代碼。(1)假設單鏈表中結點的數(shù)據(jù)域中數(shù)據(jù)依升序排列，將名為newNode，數(shù)據(jù)域數(shù)據(jù)為x的結點插入到該單鏈表中。(2)從無序的單鏈表中查找出所有元素的最大值，該值由函數(shù)返回；若單鏈表為空，則顯示出錯信息并停止運行。(3)統(tǒng)計出單鏈表中結點的值等于給定值x的結點數(shù)。五、閱讀算法并描述其功能1函數(shù)1代碼如下:intfun1(intx){inti=0;while(i<=last&&data[i]!=x) i++;if(i>=0&&i<=last){ last--; for(intj=i;j<=last;j++) data[j]=data[j+1]; return1;}return0;}2函數(shù)2代碼如下:intfun2(intx){inti=0,flag=0;while(i<=last&&!flag) if(data[i]!=x)i++;elseflag=1;returnflag;}六、簡答題線性結構可用順序表或鏈表存儲。試問：(1)兩種存儲表示各有哪些主要優(yōu)缺點?(2)如果有n個表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化，表的總數(shù)也可能自動改變，在此情況下，應選用哪種存儲表示?為什么?(3)若表中很少進行插入和刪除，但要求以最快的速度存取表中的元素，這時，應采用哪種存儲表示?為什么?

第3章棧和隊列一、判斷題1單鏈表形式的隊列，頭指針f指向隊列的第一個結點，尾指針r指向隊列的最后一個結點。2棧和隊列邏輯上都是線性表，都是限制存取點的線性結構。3消除遞歸不一定需要使用棧。4遞歸工作棧的紀錄包括返回地址與本層的所有局部變量值。二、選擇題1在一個順序隊列中，隊首指針指向隊首元素的位置。(A)．前一個(B)．后一個(C)．當前2假定一順序隊列的隊首和隊尾指針分別為f和r，則判斷隊空的條件為。(A)．f+1==r (B)．r+1==f(C)．f==0(D)．f==r3輸入序列為1，2，3，4，不可能通過棧得到的輸出序列有。(A)．4312(B)．3421(C)．1342(D)．3124(E)．1324(F)．23414對于順序存儲的隊列，存儲空間大小為n，頭指針為F，尾指針為R。若以循環(huán)隊列的方式管理隊列中的數(shù)據(jù)，則隊列中元素的個數(shù)為。(A)．R-F (B)．n+R-F(C)．(R-F+1)modn(D)．(n+R-F)modn5棧的插入與刪除操作在進行。(A)．棧頂(B)．棧底(C)．任意位置(D)．指定位置6當利用大小為N的一維數(shù)組順序存儲一個棧時，假定用top==N表示棧空，則向這個棧插入一個元素時，首先應執(zhí)行語句修改top指針。(A)．top++(B)．top--(C)．top=0(D)．top7若讓元素1，2，3依次進棧，則出棧次序不可能出現(xiàn)種情況。(A)．3，2，1(B)．2，1，3(C)．3，1，2(D)．1，3，28在一個循環(huán)順序隊列中，隊首指針指向隊首元素的位置。(A)．前一個(B)．后一個(C)．當前(D)．后面9當利用大小為N的一維數(shù)組順序存儲一個循環(huán)隊列時，該隊列的最大長度為。(A)．N-2(B)．N-1(C)．N(D)．N+110從一個循環(huán)順序隊列刪除元素時，首先需要。(A)．前移一位隊首指針(B)．后移一位隊首指針(C)．取出隊首指針所指位置上的元素(D)．取出隊尾指針所指位置上的元素11假定一個循環(huán)順序隊列的隊首和隊尾指針分別為f和r，則判斷隊空的條件是。(A)．f+1==r(B)．r+1==f(C)．f==0(D)．f==r12假定一個鏈隊的隊首和隊尾指針分別為front和rear，則判斷隊空的條件是。(A)．front==rear(B)．front!=NULL(C)．rear!=NULL(D)．front==NULL三、填空題1對于單鏈表形式的隊列，其空隊列的F指針和R指針都等于。2用循環(huán)鏈表表示的隊列長度為n，若只設頭指針，則出隊和入隊的時間復雜度分別是和；若只設尾指針，則出隊和入隊的時間復雜度分別是和。3從一個鏈棧中刪除一個結點時，需要把棧頂結點的指針域的值賦給。4當用長度為N的數(shù)組順序存儲一個棧時，假定用top==N表示?？眨瑒t表示棧滿的條件為。5假設以S和X分別表示進棧和退棧操作，則對輸入序列a，b，c，d，e進行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為。6對于順序存儲的棧，因為棧的空間是有限的，在進行運算時，可能發(fā)生棧的上溢，在進行運算時，可能發(fā)生棧的下溢。7棧又稱為表，隊列又稱為表。四、寫出算法的運行結果設隊列Q={11,23,37,47,59}，其中11為隊頭元素，59為隊尾元素。函數(shù)Invert(Q)的偽代碼如下：voidInvert(Queue&Q){StackS;S.MakeEmpty();while(!Q.IsEmpty())S.Push(Q.DeQueue());while(!S.IsEmpty())Q.EnQueue(S.Pop());}(1)執(zhí)行函數(shù)Invert(Q)之后，隊列Q的最終狀況是什么；(2)用程序驗證你的結論。五、算法設計題1假設以數(shù)組Q[0…m-1]存放循環(huán)隊列中的元素，同時以rear和length分別表示循環(huán)隊列中的隊尾位置和隊列中所含元素個數(shù)。試給出該循環(huán)隊列的判空函數(shù)(IsEmpty)、判滿函數(shù)(IsFull)、入隊函數(shù)(EnQueue)和出隊函數(shù)(DeQueue)。2若使用循環(huán)鏈表來表示隊列，p是鏈表中的一個指針。試基于此結構給出隊列的判空函數(shù)、入隊函數(shù)和出隊函數(shù)。3已知head為單鏈表的表頭指針，鏈表中存儲的都是整型數(shù)據(jù)，試寫出實現(xiàn)下列運算的遞歸算法。(1)求鏈表中的最大整數(shù);(2)求鏈表的結點個數(shù);(3)求所有結點值之和。

第4章樹一、判斷題1在只有度為和度為的結點的叉樹中，設度為的結點有個，度為的結點有個，則有。2一般樹和二叉樹的全部結點個數(shù)均可以為0。3具有個結點的樹，其全體結點的度數(shù)之和為。4用樹的前序遍歷和中序遍歷可以導出樹的后序遍歷。5將一棵樹轉換成二叉樹后，該二叉樹沒有根結點。6用二叉鏈表存貯n個結點的二叉樹時，結點的2n個指針域中有n+1個為空。7去掉一顆非空樹的根，這顆樹就變成了一個森林。8在二叉樹中，設度為的結點有個，度為2的結點有個，則有。9如果約定遍歷的次序是先左子樹，后右子樹，則二叉樹的各遍歷序列中，各葉子結點的相對次序決不會發(fā)生改變。10按照堆的定義，如果存在左右子女，則堆中任一子樹根結點的關鍵碼均大于其左子女的關鍵碼，但小于其右子女的關鍵碼。11Huffman樹一定是滿二叉樹。12Huffman樹是帶權路徑長度最短的樹，路徑上權值較大的結點離根較近。二、選擇題1下列關于二叉樹的陳述中，正確的是（）。(A)．二叉樹是度為2的有序樹(B)．二叉樹中結點只一個孩子時無左右之分(C)．二叉樹中必有度為2的結點(D)．二叉樹最多只有兩棵子樹，且有左右之分2若一棵二叉樹具有10個度為2的結點，則該二叉樹的度為0的結點個數(shù)是（）。(A)．9(B)．11(C)．12(D)．不確定3一個二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（）。(A)．CABDEFG(B)．BCDEAFG(C)．DBACEFG(D)．EBACDFG4高度為的滿二叉樹(僅含根結點的二叉樹高度為零)的結點個數(shù)（）。(A)．(B)．(C)．(D)．5有64個結點的完全二叉樹的深度是（）。(A)．8(B)．7(C)．6(D)．56設二叉樹中有個度為0的結點，個度為1的結點，個度為2的結點，則（）。(A)．(B)．(C)．(D)．7已知某二叉樹的結點的后序序列是BDECA,中序序列是BADCE,前序序列是（）。(A)．EDCBA(B)．ABCDE(C)．CDABC(D)．CDEBA8樹有幾個根結點()。(A)．0個或1個(B)．0個可多個(C)．有只有1個(D)．或1個以上9A另有3個兄弟，B是A的雙親，B的度()(A)．3(B)．4(C)．5(D)．110某二叉樹的前序序列與后序序列正好相反，則該二叉樹是（）。(A)．空或只有一個結點(B)．高度等于其結點數(shù)(C)．任一結點無左孩子(D)．任一結點無右孩子11將樹轉換成二叉樹，其對應的二叉樹的根結點的右孩子（）。(A)．為空(B)．指向其它孩子(C)．指向其兄弟(D)．指向最后一個結點12將一棵有100個結點的完全二叉樹從根這一層開始,每一層上從左到右依次對結點進行編號,根結點的編號為1，則編號為49結點的左孩子編號是（）。(A)．98(B)．99(C)．50(D)．4813將森林轉換成二叉樹，其對應的二叉樹的根結點的右孩子（）。(A)．空(B)．指向其孩子(C)．指向其兄弟(D)．指向第二棵樹的根結點14森林的中根次序遍歷等同于該森林對應的二叉樹的什么遍歷序列（）。(A)．前序遍歷序列(B)．后序遍歷序列(C)．中序遍歷序列(D)．都不是15下列關于二叉樹的陳述中，正確的是（）。(A)．二叉樹是度為2的樹(B)．結點只有一個孩子時無左右之分(C)．二叉樹中必有度為2的結點(D)．每個結點最多只有兩棵子樹，而且有左右之分16用二叉鏈表存貯有n個結點的二叉樹時，結點的所有指針域中有（）個為空。(A)．n(B)．n+1(C)．n–1(D)．n/217堆的存儲方式是采用（）。(A)．有左右子女指針的二叉鏈表(B)．帶雙親指針與左右子女指針的二叉鏈表(C)．帶雙親指針的三叉鏈表存儲(D)．完全二叉樹的順序存儲18由權值為2,3,5,6,8的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（）。(A)．24(B)．48(C)．55(D)．5319在有n個葉子結點的哈夫曼樹中，其結點總數(shù)為（）。(A)．不確定(B)．2n(C)．2n+1(D)．2n-1三、應用題1設初始數(shù)據(jù)為{40,12,64,74,65,63,82,36}，試將其分別調整為最大堆與最小堆。2試分別找出滿足以下條件的所有二叉樹（1）二叉樹的前序序列與中序序列相同；（2）二叉樹的中序序列與后序序列相同；（3）二叉樹的前序序列與后序序列相同。3判斷以下序列是否是堆？如果不是，將它調整為最小堆。（1）{100,86,48,73,35,39,42,57,66,21};（2）{12,24,33,70,33,56,48,92,86,65};（3）{103,97,56,38,66,23,42,12,30,52,06,20};（4）{5,56,20,23,40,38,29,61,35,76,28,99};4假定用于通信的電文僅由8個字母c1,c2,c3,c4,c5,c6,c7,c8組成，各字母在電文中出現(xiàn)的頻度分別為5，25，3，6，10，11，36，4。試為這8個字母設計不等長的哈夫曼編碼，并給出該電文的總碼數(shù)。5將下圖中的樹轉換成為二叉樹。四、算法設計若用二叉鏈表作為二叉樹的存儲表示，試針對以下問題編寫遞歸算法：（1）統(tǒng)計二叉樹中葉子結點的個數(shù)。（2）統(tǒng)計二叉樹中的結點個數(shù)。（3）計算二叉樹的高度。（4）用以下二叉樹驗證所寫算法的正確性（約定：二叉樹的創(chuàng)建采用廣義表法）

第5章圖一、判斷題1在一個有向圖的鄰接矩陣中，其主對角線及主對角線以下的元素均為零，則該圖存在著拓撲序列。2在拓撲排序序列中，任意兩個相繼結點Vi和Vj間都存在一條路徑。3用鄰接矩陣表示圖所用的存儲空間大小與圖的邊數(shù)成正比。4圖的簡單路徑絕不可能是回路。5n個結點的無向圖最多有n(n-1)條邊。6在連通圖中，任何一對頂點之間至少存在兩條路經(jīng)。7如果網(wǎng)絡上各邊的權值是互異的，則它的最小生成樹唯一。8圖的鄰接矩陣表示是惟一的，且無向圖的鄰接矩陣是一個對稱矩陣；而圖的鄰接表表示是不惟一。二、選擇題1在一個無向圖中，所有頂點的入度之和等于所有頂點的出度之和的倍。(A)．1/2(B)．1(C)．2(D)．42用鄰接矩陣存儲圖時所需存儲空間大小與圖的有關。(A)．頂點數(shù)(B)．邊數(shù)(C)．出度(D)．入度3關鍵路徑是頂點網(wǎng)絡中。(A)．從源點到匯點的最長路徑(B)．從源點到匯點的最短路徑(C)．最長的回路(D)．最短的回路4具有n個頂點的無向圖最多有條邊，n個頂點的有向完全圖中含有向邊的數(shù)目最多為。(A)．n(B)．n(n-1)(C)．n(n+1)(D)．n2(E)．n(n-1)/2(F)．n-15下圖是由7個頂點組成的無向圖，從頂點1出發(fā)進行廣度優(yōu)先遍歷，不可能得到的頂點序列是。(A)．1234576 (B)．1754326(C)．1354726(D)．12345676已知一個有向圖如下圖所示，從頂點A出發(fā)進行深度優(yōu)先遍歷，不可能得到的深度優(yōu)先遍歷序列為。(A)．ADEBFC(B)．ADBFEC(C)．ADCEBF(D)．ADCBEF三、填空題1設G為有n個頂點的無向連通圖，若采用鄰接矩陣存儲G，則矩陣大小為；則該矩陣至少有個非零元素。2對于一個具有n個頂點和e條邊的連通圖，其生成樹中頂點數(shù)和邊數(shù)分別為和。3已知鄰接矩陣A＝，從中可以看出，該圖共有個頂點。如果是有向圖，該圖共有條邊、各頂點的出度分別是、入度分別是；如果是無向圖，則共有條邊，各頂點的度分別是。4假定一個圖具有n個頂點和e條邊，當采用鄰接矩陣、鄰接表表示時，其相應的空間復雜度分別為和。四、應用題1對于下面的帶權圖，若從頂點0出發(fā)，則按照Prim(普里姆)算法，畫出最小生成樹。2對于如下圖所示的有向圖，試畫出：（1）從頂點①出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；（2）從頂點②出發(fā)進行廣度優(yōu)先搜索的得到廣度優(yōu)先生成樹。3試對下圖所示的AOE網(wǎng)絡回答下列問題：（1）這個工程最早可以在什么時間結束。（2）求每個活動的最早開始時間TE和最遲開始時間TL。（3）確定哪些活動是關鍵活動與關鍵路徑。五、算法設計題關于圖G的鄰接表創(chuàng)建、顯示、廣度與深度優(yōu)先遍歷函數(shù)的共享代碼如下，在此基礎上，完成以下算法設計。#include<iostream>usingnamespacestd;#defineMAXVEX30//圖中最多頂點個數(shù)//鄰接表中鏈表結點定義structNode{ intvno;//頂點序號 structNode*next;//指向下一個頂點的指針};intvisited[MAXVEX];//頂點訪問標識數(shù)組,全局變量intqueue[MAXVEX];//廣度優(yōu)先遍歷存儲隊列,全局變量intstack[MAXVEX];//深度優(yōu)先遍歷存儲棧,全局變量//輸入有向圖的邊,建立圖的鄰接表與鄰接矩陣intCreateGraph(Node*LGraph[MAXVEX]){//*LGraph鄰接表指針數(shù)組 intvn,en,i,j,k; Node*newnode,*p; //輸入圖的頂點數(shù)與邊數(shù) while(1) { vn=en=0; cout<<"輸入有向圖的頂點數(shù)[1-30]:"; cin>>vn; if(vn<1||vn>30) {cout<<"輸入的頂點數(shù)"<<vn<<"超限,重新輸入!"<<endl; continue; } //完全有向圖的邊數(shù)最大值為vn*(vn-1) cout<<"輸入圖的邊數(shù)[1-"<<vn*(vn-1)<<"]:";cin>>en; if(en>=1&&en<=vn*(vn-1)) break;else {cout<<"輸入的邊數(shù)"<<en<<"超限,重新輸入!"<<endl; continue; } } //鄰接表初始化 for(i=0;i<vn;i++) { newnode=newNode; newnode->vno=i+1; newnode->next=NULL; LGraph[i]=newnode;//創(chuàng)建鄰接鏈表中每根鏈的頭結點 } //輸入有向邊,構造鄰接表k=0;//邊數(shù)計數(shù) while(k<en) {i=j=-1; cout<<"輸入第"<<k+1<<"條邊的出邊頂點序號與入邊頂點序號"<<endl; cout<<"出邊頂點序號:";cin>>i; cout<<"入邊頂點序號:";cin>>j; if(i<1||j<1||i>vn||j>vn) {cout<<"輸入錯誤,頂點范圍為[1-"<<vn<<"]"<<endl; continue; } k++; //用有向邊<i,j>為鄰接表賦值 newnode=newNode; newnode->vno=j;//出邊頂點j newnode->next=NULL; p=LGraph[i-1];//出邊頂點為i,屬于第i-1條鏈 while(p->next!=NULL) p=p->next;//p指向第i-1條鏈的尾結點 p->next=newnode;//與頂點i相連的頂點j入鏈尾 } returnvn;//返回圖的頂點數(shù)}//輸出鄰接表voidDispLGraph(Node*LGraph[],intn){//*LGraph[]鄰接表,n頂點個數(shù) cout<<"有向圖的鄰接表"<<endl;Node*p; for(inti=0;i<n;i++) { p=LGraph[i];//p指向第i條鏈表的頭結點 cout<<p->vno<<"=>";//輸出頭結點的頂點序號 while(p->next!=NULL) { p=p->next; cout<<p->vno<<"=>";//輸出鏈表上頂點結點的序號 } cout<<"NULL"<<endl;//輸出鏈表結束符 }}//鄰接表表示的圖的廣度優(yōu)先遍歷voidLBFS(Node*LGraph[],ints,intn){//*LGraph[]鄰接表,s出發(fā)頂點,n頂點數(shù)inti,v,w,front,rear;Node*p;cout<<"廣度優(yōu)先遍歷為:";//置全部頂點為未訪問標識for(i=0;i<n;i++) visited[i]=0;front=rear=-1;//隊列置空queue[++rear]=s;//出發(fā)頂點s進隊visited[s-1]=1;//置頂點s已被訪問標識while(front<rear)//當隊列非空時,循環(huán){ v=queue[++front];//隊列中隊頭頂點出隊 cout<<v<<"";//輸出出隊頂點 p=LGraph[v-1];//p指向隊頭頂點在鄰接表中對應的鏈表 while(p->next!=NULL) {p=p->next; w=p->vno;if(visited[w-1]==0)//頂點w未被訪問過 {queue[++rear]=w;//頂點w進隊 visited[w-1]=1;//置頂點w已被訪問標識 } }}cout<<endl;}//鄰接表表示的圖的深度優(yōu)先遍歷voidLDFS(Node*LGraph[],ints,intn){//*LGraph[]鄰接表,s出發(fā)頂點,n頂點數(shù)inti,v,w,top;Node*p;cout<<"深度優(yōu)先遍歷為:";//置全部頂點為未訪問標識for(i=0;i<n;i++) visited[i]=0;top=-1;//棧置空stack[++top]=s;//出發(fā)頂點s進棧visited[s-1]=1;//置頂點s已被訪問標識while(top!=-1)//當棧非空時,循環(huán){v=stack[top--];//棧中的棧頂頂點出棧 cout<<v<<"";//輸出出棧頂點 p=LGraph[v-1];//p指向出棧頂點在鄰接表中對應的鏈表 while(p->next!=NULL) {p=p->next; w=p->vno;if(visited[w-1]==0)//頂點w未被訪問過 {stack[++top]=w;//頂點w進棧 visited[w-1]=1;//置頂點w已被訪問標識 } }}cout<<endl;}voidmain(){Node*LGraph[MAXVEX];//鄰接表intvexnum;//圖中頂點個數(shù)vexnum=CreateGraph(LGraph);//創(chuàng)建有向圖并返回頂點數(shù)DispLGraph(LGraph,vexnum);//輸出鄰接表LBFS(LGraph,1,vexnum);//從頂點1出發(fā),對有向圖作廣度優(yōu)先遍歷LDFS(LGraph,1,vexnum);//從頂點1出發(fā),對有向圖作深度優(yōu)選遍歷}1、假設圖G采用鄰接表存儲，設計一個算法，判斷圖G是否連通。若連通則返回1；否則返加0。2、將圖頂點的結構體中增加一個頂點入度域，設計一個算法，創(chuàng)建圖G的鄰接表。3、假設圖G采用鄰接表存儲，設計一個算法，判斷圖G是否為有向無環(huán)圖。若是有向無環(huán)圖則返回1；否則返加0。

第6章排序一、判斷題1在待排序文件中，存在多個具有相同關鍵字的記錄，經(jīng)排序后這些記錄的相對順序仍保持不變，這種排序算法是不穩(wěn)定的。2快速排序當被排序的數(shù)量太大時最不利發(fā)揮其長處。3對有n個結點的順序表進行快速排序，在最壞情況下，其關鍵字碼比較次數(shù)為O(n2)。4在n個數(shù)據(jù)中選取前k個最小元(k<<n，n很大時)，最有效的方法是采用堆排序。5在n個數(shù)據(jù)中選取前k個的最小元(k<<n，n不是很大時)，最有效的方法是采用直接選擇排序。6在n個數(shù)據(jù)中選取前k個的最小元(k<<n，n不是很大時)，最有效的方法是采用直接插入排序。7一組數(shù)據(jù)已有序，最快的排序方法是冒泡排序。8一組數(shù)據(jù)已有序，最快的排序方法是快速排序。9外部排序指的是大文件的排序，即待排序的記錄存儲在外存上，在排序過程中需進行多次的內、外部之間的交換。10穩(wěn)定的內部排序方法有基數(shù)排序，快速排序和歸并排序。11穩(wěn)定的內部排序方法有改進的選擇排序、冒泡排序、插入排序和希爾排序。二、填空題1當從一個最小堆中刪除堆頂元素時，需要把元素填補到位置，然后再按形成最小堆的條件，將這些元素逐層調整。2在一個最小堆中，堆頂結點的值是所有結點中的，具有最大值的元素可能在。在一個最大堆中，堆頂結點的值是所有結點中的。3每次直接比較兩個元素，若出現(xiàn)逆序時就交換它們的位置，該方法稱之為排序。4用冒泡法對n個關鍵碼排序，在最好情況下，只需做次比較和次移動；在最壞的情況下要做次比較和次移動。5設關鍵碼序列為{46,79,56,38,40,80,25,34}，若采用首個元素為支點的快速排序，在整個排序過程中，所取的支點分別為。三、應用題1對于含12個關鍵碼的序列{236,295,704,612,123,734,74,665,742,512,254,469}，按照關鍵碼遞增次序進行排序，試給出以下問題的解。（1）采用冒泡排序，寫出第1趟排序的結果。（2）采用插入排序，寫出第4趟排序的結果。（3）若采用初始步長為4的希爾排序，寫出第1趟排序的結果。（4）若采用以第一個元素為支點的快速排序法，寫出第1趟排序結果。（5）采用堆排序，假定將關鍵碼序列調成最大堆為第1趟排序，寫出第2趟排序結果。（6）采用基數(shù)排序，寫出第2趟排序結果。2用遞歸方式，改寫選擇排序法。第7章查找一、選擇題1.對n個元素的順序表順序查找，若查找每個元素的概率相同，則平均查找長度為()。(A)．(n+1)/2(B)．n/2(C)．n(D)．n(n+1)/22.對線性表進行折半查找時，要求線性表必須（）(A)．以順序方式存儲(B)．以順序方式存儲，且數(shù)據(jù)元素有序(C)．以鏈接方式存儲(D)．以鏈接方式存儲，且數(shù)據(jù)元素有序3．分別以下列序列構造二叉排序樹，與用其它三個序列所構造的結果不同的是()。(A)．（100，80，90，60，120，110，130）；(B)．（100，120，110，130，80，60，90）；(C)．（100，60，80，90，120，110，130）；(D)．（100，80，60，90，120，130，110)。4.設有一組記錄的關鍵字為{19，14，23，1，68，20，84，27，55，11，10，79}，用鏈地址法構造哈希表，哈希函數(shù)為H(key)=key%13,哈希地址為1的鏈中有（）個記錄。(A)．1(B)．2(C)．3(D)．45.設哈希表長為11，哈希函數(shù)是H(key)=key%11，表中已存入關鍵字為15，38，61，84這四個關鍵字?，F(xiàn)要將關鍵字為49的結點加到表中，用二次探測再散列法解決沖突，則放入的位置是()(A)．8(B)．3(C)．5(D)．9二、判