【正文】 輸入項序列由A，B，C組成，試給出全部可能的輸出序列。5．設有4個元素4依次進棧，而棧的操作可隨時進行（進出?？扇我饨诲e進行，但要保證進棧次序不破壞4的相對次序），請寫出所有不可能的出棧次序和所有可能的出棧次序。6．現(xiàn)有稀疏矩陣A如圖所示，要求畫出三元組表示法和十字鏈表表示法：7．設4維數(shù)組的4個下標的范圍分別為[1，0]，[1，2]，[1，3]，[2，1]，請分別按行序和列序列出各元素。8．有一份電文中共使用5個字符：a，b，c，d，e，它們出現(xiàn)的頻率依次為4，7，5，2，9，試畫出對應的哈夫曼樹（請按左子樹根結點的權小于等于右子樹根結點的權的次序構造），并求出每個字符的哈夫曼編碼。9．有如圖所示的二叉樹，回答如下問題。（1） 寫出該樹的中序遍歷序列。（2） 寫出該樹的先序遍歷序列。（3） 寫出該樹的后序遍歷序列；（4） 畫出該二叉樹的中序線索二叉樹；（5） 畫出該二叉樹的后序線索二叉樹；（6） 畫出該二叉樹對應的森林； 10．已知一棵樹邊的集合為{i,m,i,n,e,i,b,e,b,d,a,b,g,j,g,k,c,g,c,f,h,l,c,h ,a,c}，畫出這棵樹。11．假設二叉樹采用順序存儲結構，如圖所示。（1） 畫出二叉樹表示；（2） 寫出先序遍歷、中序遍歷和后序遍歷的結果；（3） 寫出結點值c的雙親結點，其左、右孩子；（4） 畫出把此二叉樹還原成森林的圖。1234567891011121314151617181920eafdgcjhib12．已知一棵二叉樹的中序序列為cbedahgijf，后序序列為cedbhjigfa，畫出該二叉樹的先序線索二叉樹。13．某二叉樹的先序遍歷序列是abdgcefh，中序遍歷序列是dgbaechf，給出其后序遍歷序列。14．將下圖所示森林轉換成為二叉樹，并寫出轉化后二叉樹中序遍歷結果。 15．有一份電文中共使用8個字符：a、b、c、d、e、f、o、i，它們的出現(xiàn)頻率依次為10，20，15，32，40，60，26，18。試畫出對應的哈夫曼樹（請按左子樹根結點的權小于等于右子樹根結點的權的次序構造），并求出每個字符的哈夫曼編碼。16．已知某系統(tǒng)在通信聯(lián)絡中只可能出現(xiàn)A,B,C,D,E,F,G,H八種字符，，，。17．對有五個頂點{v1,v2,v3,v4,v5}的圖的鄰接矩陣如圖所示，解答下列問題：（1）畫出邏輯圖。（2）畫出該邏輯結構的鄰接表。（3）基于鄰接矩陣寫出圖的深度、廣度優(yōu)先遍歷序列。18．如圖所示，解答如下問題：（1）寫出從定點A出發(fā)，深度和廣度優(yōu)先遍歷方法遍歷該圖的頂點序列。（2）根據(jù)普里姆算法和克魯斯卡爾算法，分別求它的最小生成樹，要求給出構造過程。19．給出如圖所示的無向圖G的鄰接矩陣和鄰接表兩種存儲結構。并在給定的鄰接表的基礎上，指出從頂點1出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷序列。20．使用普里姆算法構造出如圖所示的圖G的一棵最小生成樹。21．使用克魯斯卡爾算法構造出如圖所示的圖G的一棵最小生成樹。22．設有一棵二叉樹，它的中序和后序遍歷結果如下，請畫出該二叉樹。 中序：1 4 3 5 6 2 后序：4 6 5 3 2 123．設一棵順序二叉樹具有10個結點，請計算其中葉子結點的數(shù)目。24．設如圖所示二叉樹是由某棵樹轉化而來，請畫出其對應的原樹。25．設有如圖所示的一棵樹，請將其轉化為二叉樹。26．下表給出了某工程各工序之間的優(yōu)先關系和各工序所需時間。解答下列問題：（1）畫出相應的AOE圖；（2）給出各事件的最早發(fā)生時間和最晚發(fā)生時間；（3）找出關鍵路徑，并指明完成該工程所需最短時間；（4）若把AOE網(wǎng)視為AOV網(wǎng)，給出其一個拓撲序列的例子。工序代號ABCDEFGHIJKLMM時間151050815409015806015302040先驅工作－－A,BBC,DBEG,IEIF,IH,J,KLG27．某不帶權有向圖如下所示。給出其鄰接矩陣和鄰接表表示。28．求如下AOE圖的關鍵路徑，要求給出求解過程。29．有一組數(shù)據(jù)，內容如下：8，15，38，57，68，88，98，108，129，234，256試用二分查找法查找68和222，要求先畫出二叉折半檢索樹，然后寫出查找過程。30．已知有序表為｛12，18，24，35，47，50，62，83，90，115，134｝，請畫出采用折半查找法對應的判斷樹。31．設數(shù)據(jù)集合d＝｛1，12，5，8，3，10，7，13，9｝，試完成下列各題：（1）依次取d中各數(shù)據(jù)，構造一棵二叉排序樹bt。（2）如何依據(jù)此二叉樹bt得到d的一個有序序列。（3）畫出在二叉樹bt中刪除“12”后的樹結構。32．對給定的數(shù)列R＝{7，16，4，8，20，9，6，18，5}，構造一棵二叉排序樹，并且（1）給出按中序遍歷得到的數(shù)列R1。（1）給出按后序遍歷得到的數(shù)列R2。33．已知序列{17，18，60，40，7，32，73，65，85}，請給出采用冒泡排序法對該序列作升序排序時每一趟的結果。34．已知序列{503，87，512，61，908，170，897，275，653，462}，請給出采用快速排序法對該序列作升序排序時每一趟的結果。35．已知序列{503，87，512，61，908，170，897，275，653，462}，請給出采用堆排序法對該序列作升序排序時每一趟的結果。36．已知序列{503，87，512，61，908，170，897，275，653，462}，請給出采用希爾排序法對該序列作升序排序時每一趟的結果。37．已知序列{17，18，60，40，7，32，73，65，85}，請給出采用直接插入排序法對該序列作升序排序時每一趟的結果。38．設散列表的長度m＝13（0，1，2，…，12），散列函數(shù)為H（k）＝k mod m，給定的關鍵字序列為{19，14，23，10，68，20，84，27，55，11}。試畫出用線性探測法解決沖突時所構造的散列表。五、算法設計題。1．已知一個順序表L，其中的元素按值非遞減有序排列，設計一個算法插入一個元素x后保持該順序表仍按非遞減有序排列。2．設計一個算法從順序表L中刪除所有值為x的元素。3．已知線性表元素遞增有序，并以帶頭結點的單鏈表作存儲結構，設計一個高效算法，刪除表中所有值大于mink且小于maxk的元素（若表中存在這樣的元素）。并分析所寫算法的時間復雜度。4．設計一個在帶頭結點的單鏈表中刪除一個最小值結點的高效算法。5．有一個不帶頭結點的單鏈表L（至少有一個結點），其頭指針為head。設計一個算法將L逆置，即最后一個結點變成第一個結點，原來倒數(shù)第二個結點變成第二個結點，如此等等。6．假設二叉樹采用鏈式存儲方式存儲，編寫一個二叉樹前序遍歷的非遞歸算法。7．假設二叉樹采用鏈式存儲方式存儲，編寫一個二叉樹后序遍歷的非遞歸算法。8．假設二叉樹采用鏈式存儲方式存儲，編寫一個二叉樹中序遍歷的非遞歸算法。9．編寫一個c++函數(shù)。實現(xiàn)線性表就地逆置。即在原表的存儲空間內將線性表（a1,a2,…,an）逆置為（an,…,a2,a1）。10．編寫一個單鏈表倒鏈程序，即將單鏈表中每個結點的前驅與后繼關系顛倒。11．在數(shù)組a[0…n1]中存放有n個不同的整數(shù)，請編寫一個函數(shù)，將a中的n個數(shù)按從小到大的順序排列。12．有一個不帶頭結點的單鏈表L（至少有一個結點），其頭指針為head。設計一個算法將L逆置，即最后一個結點變成第一個結點，原來倒數(shù)第二個結點變成第二個結點，如此等等。13．已知非空線性鏈表的第一個結點的指針為head，請寫一個算法，將該鏈表中數(shù)據(jù)域值最小的結點移動到鏈表的最前端。編寫的函數(shù)具有如下原型：void func(TLinkNode *head),其中鏈結點的結構如下：struct TLinkNode{int data。TLinkNode *next。}請完成該算法。14．在數(shù)組a[0…n1]中存放有n個不同的整數(shù)，請編寫一個函數(shù)，將a中的n個數(shù)按從小到大的順序排列，要求使用改進的插入排序算法，元素a[i]要插入的位置由折半（二分）查找算法找到。22