福建師范大學數學與計算機學院計算機科學與技術《數據結構與算法》期末練習一選擇題1．以下與數據的存儲結構無關的術語是（D）。A．循環隊列B.鏈表C.哈希表D.棧2.算法的時間復雜度取決于（A）A．問題的規模B.待處理數據的初態C.A和BD.計算機cpu3.一個棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是（B）。A.23415B.54132C4.有關靜態鏈表的敘述：(1)靜態鏈表既有順序存儲的優點，又有動態鏈表的優點。所以，它存取表中第i個元素的時間與i無關。(2)靜態鏈表中能容納的元素個數的最大數在表定義時就確定了，以后不能增加。(3)靜態鏈表與動態鏈表在元素的插入、刪除上類似，不需做元素的移動。以上錯誤的是（B）A．（1），（2）B．（1）C．（1），（2）,(3)D.（2）5．對于有n個結點的二叉樹,其高度為（D）A．nlog2nB．log2nC．?log2n?|+1D．不確定6．從下列有關樹的敘述中,選出正確的敘述（C）A．二叉樹中每個結點有兩個子結點,而樹無此限制,因此二叉樹是樹的特殊情況。B．當K≥1時高度為K的二叉樹至多有2k-1個結點。C．哈夫曼樹是帶權路徑最短的樹,路徑上權值較大的結點離根較近。D．在二叉樹中插入結點,該二叉樹便不再是二叉樹。7．設無向圖的頂點個數為n，則該圖最多有（B）條邊。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n8．已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓撲序列是（A）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V79．下列排序算法中，其中（D）是穩定的。A.堆排序，冒泡排序B.快速排序，堆排序C.希爾排序，歸并排序D.歸并排序，冒泡排序10．對一組數據（84，47，25，15，21）排序，數據的排列次序在排序的過程中的變化為（1）8447251521（2）1547258421（3）1521258447(4）152125478411.則采用的排序是(A)。A.選擇B.冒泡C.快速D.插入12．以下數據結構中，哪一個是線性結構（D）？A．廣義表B.二叉樹C.稀疏矩陣D.串13．下面關于線性表的敘述中，錯誤的是哪一個？（B）A．線性表采用順序存儲，必須占用一片連續的存儲單元。B．線性表采用順序存儲，便于進行插入和刪除操作。C．線性表采用鏈接存儲，不必占用一片連續的存儲單元。D．線性表采用鏈接存儲，便于插入和刪除操作。14.設一個棧的輸入序列是1，2，3，4，5,則下列序列中，是棧的合法輸出序列的是（D）。A.51234B.45132C.43125D.3215415.設n為正整數.下列程序段中前置以@的語句的頻度為（）。i=1;k=0;do{@k+=10*i;i++;}While(i<=n-1);A.n–1B.nC.n+1D.n-216.一棵具有n個結點的完全二叉樹的樹高度（深度）是（A）A．?logn?+1B．logn+1C．?logn?D．logn-117．一個棧的輸入序列為123…n，若輸出序列的第一個元素是n，輸出第i（1<=i<=n）個元素是（B）。A.不確定B.n-i+1C.iD.n-i18．n個結點的完全有向圖含有邊的數目（D）。A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）19．穩定的排序方法是（B）A．直接插入排序和快速排序B．折半插入排序和起泡排序C．希爾排序和四路歸并排序D．樹形選擇排序和shell排序20．有一組數據（15，9，7，8，20，-1，7，4）用快速排序的劃分方法進行一趟劃分后數據的排序為(A)（按遞增序）。A．下面的B，C，D都不對。B．9，7，8，4，-1，7，15，20C．20，15，8，9，7，-1，4，7D.9，4，7，8，7，-1，15，2021．以下那一個術語與數據的存儲結構無關？（A）A．棧B.哈希表C.線索樹D.雙向鏈表22．下面關于串的的敘述中，哪一個是不正確的？（B）A．串是字符的有限序列B．空串是由空格構成的串C．模式匹配是串的一種重要運算D．串既可以采用順序存儲，也可以采用鏈式存儲23.某堆棧的輸入序列為a,b，c，d,下面的四個序列中，不可能是它的輸出序列的是（D）。A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b24.關于二叉樹的敘述：①只有一個結點的二叉樹的度為0;②二叉樹的度為2；③二叉樹的左右子樹可任意交換;④深度為K的完全二叉樹的結點個數小于或等于深度相同的滿二叉樹。正確的是（D）A．①②③B．②③④C．②④D．①④25．高度為K的二叉樹最大的結點數為（C）。A．2kB．2k-1C．2k-1 D．2k-126．從下列有關樹的敘述中,選出正確的敘述（C）A．二叉樹中每個結點有兩個子結點,而樹無此限制,因此二叉樹是樹的特殊情況。B．當K≥1時高度為K的二叉樹至多有2k-1個結點。C．用樹的前序遍歷和中序遍歷可以導出樹的后序遍歷。D．哈夫曼樹是帶權路徑最長的樹,路徑上權值較大的結點離根較近。27.關鍵路徑是事件結點網絡中（A）。A．從源點到匯點的最長路徑B．從源點到匯點的最短路徑C．最長回路D．最短回路28．用DFS遍歷一個無環有向圖，并在DFS算法退棧返回時打印相應的頂點，則輸出的頂點序列是(A)。A．逆拓撲有序B．拓撲有序C．無序的29．一組記錄的關鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為（C）。A．(38,40,46,56,79,84)B.(40,38,46,79,56,84)C．(40,38,46,56,79,84)D.(40,38,46,84,56,79)30.一個向量的第一個元素的地址是begin，每個元素的長度是k，則第i個元素的地址是(D)A.begin+(k-1)iB.begin+(k-2)iC.begin+kiD.begin+(i-1)k31.有一個有序表為{1，3，9，12，32，41，45，62，77，88，92，100}，用折半查找法，若要找63，要經過(C)次與63比較。A.12B.6C.4D.32.一個序列的初始狀態為（46，77，82，53，31，70），今對其進行冒泡排序，當進行兩趟冒泡后，序列中的元素排列為(D)。A.（31，46，70，53，77，82）B.（46，77，53，31，70，82）C.（46，31,82，53，77，70）D.(46，53，31，70，77，82)33.將一個長度為n的向量的第i個元素刪除時，需要前移(B)個元素。A.iB.n-iC.n+1D.n-i+134.不帶表頭的單鏈表，頭指針為head，判斷其是否為空的條件是(A)A.head==0B.head->next==nullC.head==headD.head->next==head35.在一個單鏈表中，已知*q是（*q表示指針q所指的結點，以下同）*p的前驅結點，在*q之后插入結點*s，正確的操作步驟序列是(A)。A)q->next=s;s->next=pB)s->next=p->next;q->next=s;C)p->nexr=s;s->next=p;D)p->next=s;s->next=q;36.非空循環鏈表head的尾結點*p滿足下列(C)條件A)head->next==p;B)head==p;C)p->next==head;D)p->next==037.一個棧的輸入序列是a,b,c,d,e，則可能的出棧序列是(D)。A.ecdabB)cebdaC)daecbD)abcde38.設棧s的類型為sqstack，判定?？盏臈l件是(C)。A.s==NULLB)s->top==0C)s.top==0D)s.top==NULL39.深度為5的二叉樹至多有個(B)結點。A.12B.31C.14D.1540.已知二叉樹的后、中根序列分別是bedfca和badecf，則該二叉樹的前根遍歷序列是(C)。A)defbcaB)fedbcaC)abcdefD)fedcba41.一個有n個頂點的有向圖最多有(B)弧。A)n(n+1)B)n(n-1)C)n(n+1)/2D)n(n-1)/242.具有n個頂點的無向圖至少要有(B)條邊才有可能是一個連通圖。A)n(n+1)B)n-1C)n+1D)n(n-1)43.已知有向圖的正鄰接鏈表的存儲結構如下，從頂點1出發的按深度優先遍歷序列是(B)。A)1234B)1423C)1324D)14324^4^2^3^3^4^2^4^123444.一個向量的第一個元素的地址是100，每個元素的長度是2，則第五個元素的地址是(C)A)102B)110C)108D)12045.一個循環順序隊列,隊頭、尾指針的值分別為front,rear，則隊列中元素個數為(A)。（maxlen為循環順序表的長度）A.(rear-front+maxlen)%maxlenB.(rear-front)%maxlenC.rear-front+1D.front-rear+146.一個有n個頂點的圖最少有(D)條邊。A)n(n+1)B)n(n-1)C)n(n+1)/2D)047.具有5個頂點的無向圖至少要有(A)條邊才能確保是一個連通圖。A)4B)5C)6D)748.設棧s的類型為sqstack，最多可容納maxlen個元素，則判定棧滿的條件是(B)。A.s==maxlen-1B)s.top==maxlen-1C)s->top==maxlen-1D)s.top=49.一個順序隊列q的類型為sqqueue,隊頭、尾指針分別為front,rear，最多可容納maxlen個元素，則隊空的條件是(C)。A)front==rearB)rear==0C)q.front==q.rearD)rear==maxlen-150.在具有n個結點的有序單鏈表中插入一個新結點并使鏈表仍然有序的時間復雜度是(B)A.O(1)B.O(n)C.O(nlogn)D.O(n*n)51.鏈棧與順序棧相比，比較明顯的優點是(D)A.插入操作更加方便B.刪除操作更加方便C.不會出現下溢的情況D.不會出現上溢的情況52.二叉樹中第5層上的結點個數最多為(C)A.8B.15C.16D.3253.下列編碼中屬前綴碼的是(A)A.{1,01,000,001}B.{1,01,011,010}C.{0,10,110,11}D.{0,1,00,11}54.如果求一個連通圖中以某個頂點為根的高度最小的生成樹，應采用（B）A．深度優先搜索算法 B．廣度優先搜索算法C．求最小生成樹的prim算法 D．拓撲排序算法55.對n個關鍵字的序列進行快速排序，平均情況下的空間復雜度為(B)A.O(1)B.O(logn)C.O(n)D.O(nlogn)56.對表長為n的順序表進行順序查找，在查找概率相等的情況下，查找成功的平均查找長度為(C)A.(n-1)/2B.n/2C.(n+1)/2D.n57.對于哈希函數H(key)=key%13,被稱為同義詞的關鍵字是(D)A.35和41B.23和39C.15和44D.25和5158.關于線性表的說法,下面選項正確的是（B）A線性表的特點是每個元素都有一個前驅和一個后繼B線性表是具有n(n>=0)個元素的一個有限序列C線性表就是順序存儲的表D線性表只能用順序存儲結構實現59.表長為n的順序存儲的線性表，當在任何一個位置上插入或者刪除一個元素的概率相等時，刪除一個元素需要移動元素的平均個數為（A）A(n-1)/2Bn/2CnDn-160.設雙向循環鏈表中節點的結構為(data,LLink,RLink)，且不帶頭節點。若想在指針p所指節點之后插入指針s所指節點，則應執行下列哪一個操作？（D）Ap->RLink=s;s->LLink=p;p->RLink->LLink=s;s->RLink=p->RLink;Bp->RLink=s;p->RLink->LLink=s;s->LLink=p;s->RLink=p->RLink;Cs->LLink=p;s->RLink=p->RLink;p->RLink=s;p->RLink->LLink=s;Ds->LLink=p;s->RLink=p->RLink;p->RLink->LLink=s;p->RLink=s;61.棧和隊列都是（A）A限制存取位置的線性結構B鏈式存儲的非線性結構C順序存儲的線性結構D限制存取位置的非線性結構62.單循環鏈表表示的隊列長度為n，若只設頭指針，則入隊的時間復雜度為（A）AO(n)BO(1)CO(n*n)DO(n*logn)63.一棵含有n個節點的k叉樹，可能達到的最小深度為多少？（C）An-kBn-k+1C|logkn|+1D|logkn|其中|k|表示下取整64.下列序列中(B)不是堆。A.12365368486075B.12485368366075C.12483660756853D.1236605348687565.在下列內排序方法中，(C)的平均時間復雜性是O(nlogn)。A.直接插入排序B.簡單選擇排序C.快速排序D.希爾排序66.設順序棧s非空，則語句段(C)可實現棧s的出棧操作，其中s.top為棧頂指針，s.elem為?？臻g，出棧的元素存放在x中。A.s.top:=s.top+1;B.x:=s.elem[s.top];x:=s.elem[s.top];s.top:=s.top+1;C.s.top:=s.top-1;D.x:=s.elem[s.top];x:=s.elem[s.top];s.top:=s.top-1;67.已知L是帶頭結點的單鏈表，p指向表中某結點，則要刪除p結點的后繼結點應執行操作(A)；要在p結點后插入s結點應執行操作(D)。A.pnext:=pnextnext;B.pnextnext:=.next;C.pnext:=s;snext:=pnext;D.snext:=pnext;pnext:=s;68.下述二叉樹中,哪一種滿足性質:從任一結點出發到根的路徑上所經過的結點序列按其關鍵字有序（D）。A．二叉排序樹B．哈夫曼樹C．AVL樹D．堆69.下面給出的四種排序法中(D)排序法是不穩定性排序法。A.插入B.冒泡C.二路歸并D.快速排序70.若需在O(nlog2n)的時間內完成對數組的排序，且要求排序是穩定的，則可選擇的排序方法是（C）。A.快速排序B.堆排序C.歸并排序D.直接插入排序二填空題1、在單鏈表L中，指針p所指結點有后繼結點的條件是：p->next!=null2、表達式23+((12*3-2)/4+34*5/7)+108/9的后綴表達式是：(請在表達式中用點(.)將數隔開)23.12.3*2-4/34.5*7/++108.9/+3、有一個100*90的稀疏矩陣，非0元素有9個，設每個整型數占2字節，則用三元組表示該矩陣時，所需的字節數是604、深度為9的完全二叉樹至少具有的個結點2565、已知二叉樹后序為DGEBFCA，中序為DBGEACF，則前序一定是ABDEGCF6、先根遍歷樹林正好等同于按___遍歷對應的二叉樹.先序7、構造n個結點的強連通圖，至少有_______條弧。n8、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比較的元素下標依次為6,9,11,129、在單鏈表指針為p的結點之后插入指針為s的結點的操作是：s->next=p->next;p->next=s;10、有N個頂點的有向圖，至少需要量_______條弧才能保證是連通的。N-111、在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找關鍵碼值12，需做的關鍵碼比較次數為413、下面是一個無向圖的鄰接矩陣，試將有關數據填入本題的空白處（頂點號由1開始）0101110100010101010110010該圖的頂點數為該圖的邊數為頂點3的度為。56214、后根遍歷樹林正好等同于按__(6)_遍歷對應的二叉樹。中序15、n個結點的完全有向圖含有邊的數目__(7)n*（n－l）16、當問題的規模n趨向無窮大時，算法執行時間T(n)的數量級被稱為算法的________。時間復雜度17、假設S和X分別表示進棧和出棧操作，由輸入序列“ABC”得到輸出序列“BCA”的操作序列為SSXSXX，則由“a*b+c/d”得到“ab*cd/+”的操作序列為___________。SXSSXXSSXSSXXX18、在一棵度為3的樹中，度為2的結點個數是1，度為0的結點個數是6，則度為3的結點個數是________。（注：沒有包含度為1的結點）219、如圖所示的有向無環圖可以排出________種不同的拓撲序列。1220、利用篩選法將關鍵字序列(37，66，48，29，31，75)建成的大根堆為(________)。75,66,48,29,31,3721、對長度為20的有序表進行二分查找的判定樹的高度為________。522、n個頂點的連通無向圖，其邊的條數至少為________________________。n-123、排序(sorting)有哪幾種方法_______________，_____________，____________，_____________，____________。直接插入排序，冒泡排序，快速排序，希爾排序，歸并排序，基數排序，堆排序等24、下面程序段的時間復雜度為______________。（用O估計）FORi:=1TOnDOFORj:=iTOnDOs=s+j;O（n*n）25、非線性結構包括______________和_________________。樹，圖26、在線性表的___________存儲結構上進行插入或刪除操作要移動元素。順序存儲結構27、用一維數組r[0..m-1]表示順序存儲的循環隊列，設隊頭和隊尾指針分別是front和rear，且隊頭指針所指的單元閑置，則隊滿的條件是______________________________，隊空的條件是_____________________________。Front=rear,rear+1=front28、下面表達式樹所對應的表達式的前綴表達式是_____________________________，后綴表達式是____________________________。+*a-bc/de,abc-*de/+29、在AOE-網中，設e(i)和l(i)分別表示活動的最早開始時間和最晚開始時間，則當且僅當_________________時，為關鍵活動。e(i)==l(i)30．對有向圖進行拓撲排序，若拓撲排序不成功，則說明該圖_________________。下面有向圖的一個拓撲有序序列是______________________________。存在回路，12345679831、二叉排序樹的特點是其序列是有序的。中序遍歷三簡答題1、名詞解釋：（1）抽象數據類型；（2）算法的時間復雜性； （3）散列法(hashing)；（4）索引文件。（1）抽象數據類型：（課本P7）是指一個數學模型以及定義在該模型上的一組操作。（2）算法的時間復雜性；（課本P15）一般情況下，算法中基本操作重復執行的次數是問題規模n的某個函數f（n），算法的時間量度記作T(n)=O(f(n))，它表示隨問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同，稱做算法的漸近時間復雜度，簡稱時間復雜度。（3）散列法(hashing)：（課本P253）散列法（Hashing）或哈希法是一種將字符組成的字符串轉換為固定長度（一般是更短長度）的數值或索引值的方法。根據設定的哈希函數和處理沖突的方法將一組關鍵字映像到一個有限的連續的地址集（區間）上，并以關鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表便稱為哈希表，這一映像過程稱為哈希造表或散列。（4）索引文件：

（課本P311）

除了文件本身（稱作數據區）之外，另建立一張指示邏輯記錄和物理記錄之間一一對應關系的表---索引表。這類包括文件數據區和索引表兩大部分的文件稱作索引文件。

索引表中的每一項稱作索引項，一般索引項都是由主關鍵字和該關鍵字所在記錄的物理

地址組成的。顯然，索引表必須按主關鍵字有序，而主文件本身則可以按主關鍵字有序或無

序，前者稱為索引順序文件（IndexedSequentialFile），后者稱為索引非順序文件（IndexedNonSequentialFile）。2、堆與二元查找樹的區別?（課本P280）堆的定義如下：n個元素的序列{Kl，K2，…，Kn}當且僅當滿足如下關系時，稱之為堆：(1)ki≤K2i且ki≤K2i+1或(2)Ki≥K2i且ki≥K2i+1(1≤i≤)若將和此序列對應的一維數組（即以一維數組作此序列的存儲結構）看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結點的值均不大于(或不小于)其左右孩子結點的值。由此，若序列{Kl，K2，…，Kn}是堆，則堆頂元素（或完全二叉樹的根）必為序列中n個元素的最小值（或最大值）。（課本P227）二叉排序樹又稱二元查找樹（BinarySearchTree），或者是一棵空樹，或者是具有下列性質的二叉樹：（1）若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；（2）若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；（3）它的左、右子樹也分別為二叉排序樹。3、快速分類法的基本思想是什么?（課本P273）快速排序是對起泡排序的一種改進。它的基本思想是，通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。4、如下所示的是一個帶權無向圖，帶框的數字表示相應邊的權，不帶框的數字表示頂點號。用prime算法求最小生成樹時，如果已確定的邊為(5,4),則，下一條邊應在哪幾條邊中選??？選取哪一條？11234565723415438下一條邊應在（5，1），（5，6），（4，6），（4，3）中選取，根據MST性質應該選?。?，6）。5、二叉樹的后根遍歷的序列中，任何一個非葉子結點均處在其孩子結點后面。該論斷是否正確？正確6、有一棵哈夫曼樹共有5個葉子結點其權值分別為0.1,0.25,0.08,0.21,0.9,試畫出該哈夫曼樹。假設該葉子分別表示a,b,c,d,e，分別給出五個葉子對應的哈夫曼編碼。0000，0001，001，01，17、對于一個隊列，若入隊的順序為a,b,c,則所有可能的出隊序列是什么？a,b,c8、已知一個圖如下，試畫出其逆鄰接鏈表。22134注意：課本P164，逆鄰接表是為了便于確定頂點的入度。9、若一個棧的輸入序列是1,2,3……，n,其輸出序列為p1,p2,……pn,若p1=n，則pi為多少？Pi=n-i+110、非空的二叉樹的中根遍歷序列中，根的右子樹的所有結點都在根結點的后邊，這說法對嗎？正確11、已知二叉樹的中根遍歷序列為abc，試畫出該二叉樹的所有可能的形態。5種12、已知一個圖如圖所示，如從頂點a出發進行按深度優先遍歷，可否得到序列acebdf?為什么？若按廣度優先遍歷，能否得到序列abedfc?為什么？ddabcef不行，不行根據深度優先和廣度優先遍歷的規則13、棧的存儲方式有哪兩種？順序存儲結構和鏈式存儲結構14、對于單鏈表、單循環鏈表和雙向鏈表，如果僅僅知道一個指向鏈表中某結點的指針p，能否將p所指結點的數據元素與其確實存在的直接前驅交換?請對每一種鏈表作出判斷，若可以，寫出程序段；否則說明理由。其中：datenext單鏈表和單循環鏈表的結點結構為priordatenext雙向鏈表的結點結構為1.單鏈表不行，因為單鏈表沒有辦法得到其前驅；

2.單循環鏈表可以，假設鏈表的元素大于等于2：

structNode

{

Node*next;

intdata;

};

循環鏈表Node*list;

Node*pnode=p;

while(pnode->next!=p)

{

pnode=pnode->next;

}

//找到其前驅了

inttmp=pnode->data;

pnode->data=p->data;

p->data->tmp;

3.雙向鏈表可以，假設鏈表的元素大于等于2，且p不為鏈表頭。

structNode

{

Node*next;

Node*pre;

intdata;

}

雙向鏈表list;

Node*pnode=p;

if(p->pre!=NULL)

{

inttmp=p->data;

p->data=p->pre->data;

p->pre->data=tmp;

}15、假設通信電文使用的字符集為{a,b,c,d,e,f,g}，字符的哈夫曼編碼依次為：0110，10，110，111，00，0111和010。(1)請根據哈夫曼編碼畫出此哈夫曼樹，并在葉子結點中標注相應字符；(2)若這些字符在電文中出現的頻度分別為：3，35，13，15，20，5和9，求該哈夫曼樹的帶權路徑長度。（1）根據哈夫曼編碼的規則畫樹。（課本P146）（2）（具體計算方法見課本P146）該哈夫曼樹的帶權路徑長度：25316、對于線性表的兩種存儲結構（順序存儲和鏈式存儲結構），如果線性表基本穩定，并且很少進行插入和刪除操作，但是要求以最快速度存取線性表中的元素，則應選擇哪種存儲結構？試說明理由。（期中試題）順序存儲17、內存中一片連續空間（不妨假設地址從1到m）提供給兩個棧s1和s2使用，怎樣分配這部分存儲空間，使得對任一棧，僅當這部分空間全滿時才發生上溢。如何判斷棧滿，?？眨蓚€棧的容量進行分析。（期中試題）18、設某二叉樹的前序遍歷序列為：ABCDEFGHI，中序遍歷序列為：BCAEDGHFI。（1）試畫出該二叉樹；（2）畫出該二叉樹后序線索化圖。（3）試畫出該二叉樹對應的森林。（期中試題）19、一棵二叉排序樹結構如下,各結點的值從小到大依次為1-9，請標出各結點的值。從上到下，從左到右依次為：5，1，9，4，6，2，7，3，820、試證明：若借助棧由輸入序列1,2,…,n得到輸出序列為P1,P2,…,Pn（它是輸入序列的一個排列），則在輸出序列中不可能出現這樣的情形：存在著i<j<k,使Pj<Pk<Pi。如果i<j，則對于pi<pj情況，說明pi在pj入棧前先出棧。而對于pi>pj的情況，則說明要將pj壓到pi之上，也就是在pj出棧之后pi才能出棧。這就說明，對于i<j<k，不可能出現pj<pk<pi的輸出序列。換句話說，對于輸入序列1，2，3，不可能出現3，1，2的輸出序列?！驹敿殔⒖肌恳驗榻柚鷹Ｓ奢斎胄蛄?,2,3,…,n,可得到輸出序列p1,p2,p3,…,pn,如果存在下標i,j,k,滿足i<j<k,那么在輸出序列中,可能出現如下5種情況:i進棧,i出棧,j進棧,j出棧,k進棧,k出棧.此時具有最小值的排在最前面pi位置,具有中間值的排在其后pj位置,具有最大值的排在pk位置,有pi<pj<pk,不可能出現pj<pk<pi的情形;i進棧,i出棧,j進棧,k進棧,k出棧,j出棧.此時具有最小值的排在最前面pi位置,具有最大值的排在pj位置,具有中間值的排在最后pk位置,有pi<pk<pj,不可能出現pj<pk<pi的情形;i進棧,j進棧,j出棧,i出棧,k進棧,k出棧.此時具有中間值的排在最前面pi位置,具有最小值的排在其后pj位置,有pj<pi<pk,不可能出現pj<pk<pi的情形;i進棧,j進棧,j出棧,k進棧,k出棧,i出棧.此時具有中間值的排在最前面pi位置,具有最大值的排在其后pj位置,具有最小值的排在pk位置,有pk<pi<pj,也不可能出現pj<pk<pi的情形;i進棧,j進棧,k進棧,k出棧,j出棧,i出棧.此時具有最大值的排在最前面pi位置,具有中間值的排在其后pj位置,具有最小值的排在pk位置,有pk<pj<pi,也不可能出現pj<pk<pi的情形.四算法閱讀1、voidAE(Stack&S){ InitStack(S); Push(S,3); Push(S,4); intx=Pop(S)+2*Pop(S); Push(S,x); inti,a[5]={1,5,8,12,15}; for(i=0;i<5;i++)Push(S,2*a[i]); while(!StackEmpty(S))print(Pop(S));}該算法被調用后得到的輸出結果為：（期中試題）2、voidABC(BTNode*BT,int&c1,int&c2){if(BT!=NULL){ABC(BT->left,c1,c2);c1++;if(BT->left==NULL&&BT->right==NULL)c2++;ABC(BT->right,c1,c2);}//if}該函數執行的功能是什么？（期中試題）3、在下面的每個程序段中，假定線性表La的類型為List，e的類型為ElemType,元素類型ElemType為int，并假定每個程序段是連續執行的。試寫出每個程序段執行后所得到的線性表La。（1）InitList(La);Inta[]={100,26,57,34,79};For(i=0;i<5;i++)ListInsert(La,1,a[i]);（2）ListDelete(La,1,e);ListInsert(La,ListLength(La)+1,e);（3）ClearList(La);For(i=0;i<5;i++)ListInsert(La,i+1,a[i]);（期中試題）4、intPrime(intn){inti=1;intx=(int)sqrt(n);while(++i<=x)if(n%i==0)break;if(i>x)return1;elsereturn0;}(1)指出該算法的功能；(2)該算法的時間復雜度是多少？（期中試題）5.寫出下述算法A的功能：其中BiTree定義如下:TypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*RChild;}BiTNode,*BiTree;StatusA(BiTreeT){QueueQ;InitQueue(Q);ENQueue(Q,T);While(notQueueEmpty(Q)){DeQueue(Q,e);If(e==NULL)break;Else{Print(e.data);ENQueue(Q,e.LChild);ENQueue(Q.e.RChild);}}}（期中試題）6.閱讀下列函數algo,并回答問題：(1)假設隊列q中的元素為(2,4,5,7,8),其中“2”(2)簡述算法algo的功能。voidalgo(Queue*Q){StackS;InitStack(&S);while(!QueueEmpty(Q))Push(&S,DeQueue(Q));while(!StackEmpty(&S))ＥnQueue(Q,Pop(&S));}（1）q=(8,7,5,4,2)（2）算法利用棧S輔助實現隊列Q的逆置。五算法填空1、下面是在帶表頭結點的循環鏈表表示的隊列上，進行出隊操作，并將出隊元素的值保留在x中的函數，其中rear是指向隊尾結點的指針。請在橫線空白處填上適當的語句。typedefstructnode{intdata;structnode*next;}lklist;voiddel(lklistrear,int&x);{lklistp,q;q=rear->next;if(_q==rear_________)printf(“itisempty!\n”);else{p=q->next;x=p->data;__q->next=p->next____________;if(_rear==p__________)rear=q;free(p);};};2、堆分配存儲方式下，串連接函數。（期中試題）typedefstruct{char*ch；intlen；}HString；HString*s，t;StatusStrCat(s，t)/*將串t連接在串s的后面*/{inti;char*temp;if(temp==NULL)return(0);for(i=0;;i++)temp［i］=s->ch［i］;for(;i<s->len+t.len;i++)temp［i］=t.ch［i-s->len］;s->len+=t.len;frs->ch=temp;return(1);}3、向單鏈表的末尾添加一個元素的算法。（期中試題）LNode是一個包含（data，Next）的結構體VoidInsertRear(LNode*&HL,constElemType&item){LNode*newptr;newptr=newLNode;If(______________________){cerr<<"Memoryallocationfailare!"<<endl;exit(1);}________________________=item;newptr->next=NULL;if(HL==NULL)HL=__________________________;else{LNode*P=HL;While(P->next!=NULL)____________________;p->next=newptr;}}4、L為一個帶頭結點的循環鏈表。函數f30的功能是刪除L中數據域data的值大于c的所有結點，并由這些結點組建成一個新的帶頭結點的循環鏈表，其頭指針作為函數的返回值。請在空缺處填入合適的內容，使其成為一個完整的算法。LinkListf30(LinkListL,intc){LinkListLc,p,pre;pre=L;p=(1);Lc=(LinkList)malloc(sizeof(ListNode));Lc->next=Lc;while(p!=L)if(p->data>c){pre->next=p->next;(2);Lc->next=p;p=pre->next;}else{pre=p;(3);}returnLc;}(1)L->next;(2)p->next=Lc->next;(3)p=p->next;vertexfirstedge5、已知圖的鄰接鏈表的頂點表結點結構為adjvexnext邊表結點EdgeNode的結構為下列算法計算有向圖G中頂點vi的入度。請在空缺處填入合適的內容，使其成為一個完整的算法。intFindDegree(ALGraph*G,inti)//ALGraph為圖的鄰接表類型{intdegree,j;EdgeNode*p;degree=(1);for(j=0;j<G->n;j++){p=G->adjlist［j］.firstedge;while((2)){if((3)){degree++;break;}p=p->next;}}returndegree;}(1)0(2)p!=NULL;(3)p->adjvex==i;六簡單應用題1、已知一個非空二元樹，其按中根和后根遍歷的結果分別為：中根：CGBAHEDJFI后根：GBCHEJIFDA試將這樣二元樹構造出來;若已知先根和后根的遍歷結果，能否構造這棵二元樹，為什么?若二叉樹中各結點的值均不相同，則由二叉樹的先序序列和中序序列，或由其后序序列和中序序列均能唯一地確定一棵二叉樹；但由先序序列和后序序列卻不一定能唯一地確定一棵二叉樹。由二叉樹的前序序列和后序序列不能唯一確定一棵二叉樹，因無法確定左右子樹兩部分。（因為前序序列的第一個元素是根結點，該元素將二叉樹中序序列分成兩部分，左邊表示左子樹，若左邊無元素，則說明左子樹為空；右邊是右子樹，若為空，則右子樹為空。）例如，任何結點只有左子樹的二叉樹和任何結點只有右子樹的二叉樹，其前序序列相同，后序序列相同，但卻是兩棵不同的二叉樹。2、對于下圖，畫出按Kruskal（克魯斯卡爾）算法和Prim（普里姆）算法構造最小生成樹的過程。（根據算法思想畫）3、畫出由下面的二叉樹轉換成的森林。（根據二叉樹轉換成的森林的方法畫）4、用Floyed（弗洛伊徳）算法求下圖每一對頂點之間的最短路徑及其長度，將計算過程的中間和最后結果填入下表：AA(0)A(1)A(2)A(3)12312312312312227223635353531051058585PATHPATH(0)PATH(1)PATH(2)PATH(3)1231231231231acacacacbac2babcbabacbabacbabac3cacbcacbcbacbcbacb5、哈夫曼樹在構造時，首先進行初始化存儲空間，結果如左下圖，當構造完成后，請填寫最后狀態表，如右下圖。（期中考試題）weightParentLchildRchildweightParentLchildRchild123456789101112131415500029000700080001400023000300011000--000--000--000--000--000--000--0001234567891011121314156、考慮右圖：(1)從頂點A出發，求它的深度優先生成樹(4分)(2)從頂點E出發，求它的廣度優先生成樹(4分)(3）根據普利姆(Prim)算法，求它的最小生成樹(請畫出過程)(設該圖用鄰接表存儲結構存儲，頂點的鄰接點按頂點編號升序排列)(6分)答案如下：七編寫算法題1、設計函數，求一個單鏈表中值為x的結點個數。并將結果放在頭結點的data域中。voidcount1(lklisthead,intx){lklistp;intcount=0;p=head->next;while(p!=NULL){if(p->data==x)count++;p=p->next;}head->data=count;}2、設計遞歸函數，求一棵二叉樹的深度。intdepth(bitreptrroot){ if(root==NULL) return0; else { intdep1=depth(root->lchild); intdep2=depth(root->rchild); if(dep1>dep2)returndep1+1; elsereturndep2+1; }}3、設計建立有向圖正鄰接矩陣的函數（數據輸入格式自定）。Typedefstruct{intdata[maxsize][maxsize];intdem,e;}sqgraph;sqgraphcrt(sqgraphg)（可參考實驗程序）4、設計函數，將不帶表頭結點的單鏈表清除。voidclearList(ListL){Listp;p=L->next;while(p!=NULL){q=p->next;free(p);p=q;}free(L);}5、設計遞歸函數，求一棵非空的二叉樹的深度。intdepth(bitreptrroot){ if(root==NULL) return0; else { intdep1=depth(root->lchild); intdep2=depth(root->rchild); if(dep1>dep2)returndep1+1; elsereturndep2+1; }}6、設線性表A=(a1,a2,a3,…,an)以帶頭結點的單鏈表作為存儲結構。編寫一個函數，刪去A中序號為奇數的結點。voidclearOdd(ListA){intcount=1;Listr=A;Listp=A->next;while(p!=NULL){q=p->next;if(count%2==1){r->next=q;free(p);}else{r=p;}p=q;count++;}}7、試編寫一個算法，能由大到小遍歷一棵二元樹。8、假設二元樹用左右鏈表示，試編寫一算法，判別給定二元樹是否為完全二元樹?TypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*RChild;}BiTNode,*BiTree;StatusA(BiTreeT){QueueQ;InitQueue(Q);ENQueue(Q,T);While(notQueueEmpty(Q)){DeQueue(Q,e);If(e==NULL)returnfalse;//不是完全二叉樹；Else{ENQueue(Q,e.LChild);ENQueue(Q.e.RChild);}}returntrue;//是完全二叉樹；}9、利用直接插入排序的方法對一組記錄按關鍵字從小到大的順序排序。（算法見課本P265）實現程序：

voidinsert_sort(ElemTypea[],intn)

//待排序元素用一個數組a表示，數組有n個元素

{inti,j;

ElemTypet;

for(i=1;i<n;i++)//i表示插入次數，共進行n-1次插入

{t=a[i];//把待排序元素賦給t

j=i-1;

while((j>=0)&&(t<a[j]))

{a[j+1]=a[j];j--;}//順序比較和移動

a[j+1]=t;}

}10、給出一棵表示表達式的二叉樹，其中運算符和運算對象都用一個字符表示，求該表達式的值。設二叉樹用二叉鏈表表示，表達式中僅包含二元運算，函數operate(a,b,op)可求任何一種二元運算的值，其中參數op表示運算符，a和b分別表示左右兩個運算對象。算法中允許直接引用函數operate(函數operate不必定義)，如果需要還允許引用棧和隊列的基本操作。（課本P129腳注部分介紹了以二叉樹表示表達式的遞歸定義）intcomputevalue(BiTreeT){if(T!=NULL){if(T->lchild==NULL&&T->rchild==NULL)returnT->data;intvalue1=computevalue(T->lchild);intvalue2=computevalue(T->rchild);returnoperate(value1,value2,T->data);}｝11、編寫算法，將一單鏈表逆轉。要求逆轉在原鏈表上進行，不允許重新構造一個鏈表（可以申明零時變量、指針）。該鏈表帶頭節點、頭節點和數據節點的結構定義如下typedefstructLNode{ElemTypedata;StructLNode*next;}List,LNode;函數定義：voidinvert(List&L)（期中考試題）12、編寫算法計算給定二叉樹中葉結點的個數。其中樹節點定義如下typedefstructBiTNode{DataTypedata;StructBiTNode*LChild,*RChild;}BiTNode,*BiTree;函數定義：CountLeaf(BiTreeT,int&LeafNum)（期中考試題）13、寫出二叉樹前根遍歷的遞歸算法已知二叉樹結點定義為：structnode{elemtpdata;structnode*lc,*rc;);Typedefstructnode*bitreptr(指向根),*tpointer(指向一般結點);voidpreorder(bitreptrP)//P