2023期末試卷A〔有答案〕一、選擇題1、廣義LS=〔〔a，b，c〕，〔d，e，f〕〕，headtailLS中原子e的運算是〔 〕。A.head〔tail〔LS〕〕B.tail 〔head〔LS〕〕〔tail〔tail〔head〔LS〕〕〕〕2、將兩個各有N個元素的有序表歸并成一個有序表，其最少的比較次數是〔 〕。A.NB.2N-1C.2ND.N-13、鏈表不具有的特點是〔 〕。A.插入、刪除不需要移動元素B. 可隨機訪問任一元素C.不必事先估量存儲空間D. 所需空間與線性長度成正比4、循環隊列A[0..m-1]存放其元素值，用front和rear分別表示隊頭和隊尾，則當前隊列中的元素數是〔 〕。A.〔rear-front+m〕%mB.rear-front+1C.rear-front-1D.rear-front5、有向圖G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛<V1，V2>，<V6，V7>｝，G的拓撲序列是〔 〕。A.V1，V3，V4，V6，V2，V5，V7B.V1 ，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1 ，V2，V5，V3，V4，V6，V76、以下表達中，不符合m階B樹定義要求的是〔 〕。A．根結點最多有m棵子樹B ．全部葉結點都在同一層上C．各結點內關鍵字均升序或降序排列D．葉結點之間通過指針鏈接7、關鍵5，8，12，19，28，20，15，22是小根堆〔最小堆〕，插入關鍵字3，調整后的小根堆是〔〕。A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，198、一棵非空的二叉樹的前序序列和后序序列正好相反，則該二叉樹肯定滿足〔〕。A.其中任意一個結點均無左孩子B.其中任意一個結點均無右孩子C.其中只有一個葉結點D.其中度2的結點最多為一個9、設X是樹T中的一個非根結點，B是T所對應的二叉樹。在B中，X是其雙親的右孩子，以下結論正確的選項是〔 〕。在樹T中，X是其雙親的第一個孩子在樹T中，X肯定無右兄弟在T中，X肯定是葉結點在T中，X肯定有左兄弟10、下面關于B和B+樹的表達中，不正確的選項是〔 〕A.B樹和B+樹都是平衡的多叉樹B.B 樹和B+樹都可用于文件的索引構造C.B樹和B+樹都能有效地支持挨次檢索D.B 樹和B+樹都能有效地支持隨機檢索二、填空題11、屬于不穩定排序的有 。12、在哈希函數H〔key〕=key%p中，p值最好取 。13、以下是用類C語言寫出的算法，該算法將以二叉鏈表存儲的二叉樹中的葉結點按從左到右的挨次鏈成一個帶頭結點的雙向循環鏈表，鏈接時，結點的Lchild域作為前鏈域，指向結點的直接前驅，結點的Rchild域作為后鏈域，指向結點的直接后繼。算法中，使top，p，t為關心指針，head為雙向循環鏈表的頭指針。試填充算法中的空格，使算法完整?？胢階B-樹中，假設在某結點中插入一個關鍵字而引起該結點分裂，則此結點中原有的關鍵字的個數是 ；假設在某結點中刪除一個關鍵字而導致結點合并，則該結點中原有的關鍵字的個數是 。15、關鍵碼序列〔Q，H，C，Y，Q，A，M，S，R，D，F，X〕，要依據關鍵碼值遞增的次序進展排序，假設承受初始步4的希爾排序法，則一趟掃描的結果是；假設承受以第一個元素為分界元素的快速排序法，則掃描一趟的結果是。16、TP是兩個給定的串，在T中查找等于P的子串的過程稱為P為 。義表L=〔〔〕，〔〕〕，則head〔L〕是 ；tail〔L〕是 ；L的長度是 ；深度是 。18、閱讀以下程序說明和程序，填充程序中的 。說明】本程序完成將二叉樹中左、右孩子交換的操作。交換的結果如下所示〔編者略〕。本程序承受非遞歸的方法，設立一個堆棧stack存放還沒有轉換過的結點，它的棧頂指針tp。交換左、右子樹的算法為：把根結點放入堆棧。當堆棧不空時，取出棧頂元素，交換它的左、右子樹，并把它的左、右子樹分別入棧。重復〔2〕直到堆棧為空時為止。三、推斷題鍵字查找。〔 〕20、倒排文件是對次關鍵字建立索引?！?〕21、隊列和棧都是運算受限的線性表，只允許在表的兩端進展運算?！?〕必會失去隨機存取功能。〔 〕23、一棵樹中的葉子數肯定等于與其對應的二叉樹的葉子數。〔 〕24、二叉樹是一般樹的特別情形?！?〕25、數據的規律構造是指數據的各數據項之間的規律關系?！?〕〔 〕27、連通圖上各邊權值均不一樣，則該圖的最小生成樹是唯一的?！?〕28、平衡二叉樹中，假設某個結點的左、右孩子的平衡因子為零，則該結點的平衡因子肯定是零。〔 〕四、簡答題i29、對于具有n個葉結點且全部非葉結點都有左、右孩子的二叉樹。(1)試問這種二叉樹的結點總數是多少?i試證明〕。

2〔li-〕=1。其中：l表示第i結層號設結層號為30、用一個數組S〔設大小為MAX〕作為兩個堆棧的共享空間。請說明共享方法，棧滿?？盏耐茢鄺l件，并用C語言或PASCAL語言棧操作pusi，x〕，i01，用于表示棧號，x為入棧值。31、世界六大城市為：北京(Pe)、紐約(N)、巴黎(Pa)、倫敦(L)、東京(T)、墨西哥(M)，下表給定了這六大城市之間的交通里程：世界六大城市交通里程表(單位：百公里)畫出這六大城市的交通網絡圖。畫出該圖的鄰接表表示法。畫出該圖按權值遞增的挨次來構造的最小〔代價〕生成樹。五、算法設計題32、圖G有n個點，利用從某個源點到其余各點最短路徑算法思想，設計一產生G的最小生成樹的算法。33、設A[1..100]是一個記錄構成的數組，B[1..100]是一個整數數組，其值介于l～100之間，現要求按B[1..100]的內容調整A中記錄的次序，比方當B[1]=11時，則要求將A[1]整到A[11規間為〔〕。34、假設一個僅包含二元運算符的算術表達式以鏈表形式存儲在二叉樹BT中，寫出計算該算術表達式值的算法。35、以三元組表存儲的稀疏矩陣A，B非零元個數分別為m和n。試用類PASCAL語言寫簡單為〔m+〕陣B陣AA足夠大，不另加關心空間。要求描述所用構造。參考答案一、選擇題1、【答案】C2、【答案】A3、【答案】B4、【答案】A5、【答案】A6、【答案】D7、【答案】A8、【答案】C9、【答案】D10、【答案】C二、填空題11、【答案】希爾排序、簡潔選擇排序、快速排序、堆排序等12、【答案】小于等于表長20的質因子的合數13、【答案】p->Rchild=t；t->Lchild=p；p=t；t->Rchild!=null；t->Rchild；t->Lchild!=null；t->Lchild；p->Rchild=head；head->Lchild=p14、【答案】【解析】mB-樹除根結點和葉子結點外，結點中關鍵字個數最多是m1，最少15、【答案】〔Q，A，C，S，Q，D，F，X，R，H，M,Y〕；〔F，H，C，D，a【解析】mB-樹除根結點和葉子結點外，結點中關鍵字個數最多是m1，最少16、【答案】模式匹配；模式串17、【答案】〔〕；〔〔〕〕；2；218、【答案】stack[tp]=t；p=stack[tp--]；p；++tp【解析】此題主要使用堆棧完成了二叉樹左右子樹交換的操作。首先根結點進棧，然后判斷棧是否為空，假設不為空，則取棧頂元素，交換取出結點的左右指針。并將左右指針分別進棧，重復這一操作。完成二叉樹左右孩子的交換。三、推斷題19、【答案】√20、【答案】√21、【答案】×22、【答案】√23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】×四、簡答題9〔1〕樹中度為2的結結點個數減1，故具有n個葉結點且非葉子結點均有左子樹的二叉樹的結2n-1。2〕證明：當i=1時21-〕=20=1設當i=n-1時證明當i=n時公式仍成立。設某葉結點的層號為t，當將該結點變為內部結點，從而再增加兩個葉結點時，這兩個葉結點的層號都是t+1，對于公式的變化，是削減了一結2〔t1=2-t+1-1〕+2-t+1-1〕變，這證明當i=n。30、答：兩棧共享一向量空間〔一維數組〕，棧底設在數組的兩端，兩棧頂相鄰時為棧