2022年中國海洋大學計算機科學與技術專業《數據結構與算法》科目期末試卷A（有答案）一、選擇題1、無向圖G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，對該圖進行深度優先遍歷，得到的頂點序列正確的是（）。A.a，b，e，c，d，fB.a，c，f,e，b，dC.a，e，b，c，f,dD.a，e，d，f，c，b2、下列排序算法中，占用輔助空間最多的是（）。A.歸并排序B.快速排序C.希爾排序D.堆排序3、某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節省運算時間。A.單鏈表B.僅有頭指針的單循環鏈表C.雙鏈表D.僅有尾指針的單循環鏈表4、已知串S='aaab'，其next數組值為（）。A.0123B.1123C.1231D.12115、在用鄰接表表示圖時，拓撲排序算法時間復雜度為（）。A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、下列選項中，不能構成折半查找中關鍵字比較序列的是（）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，4507、下列敘述中，不符合m階B樹定義要求的是（）。A．根結點最多有m棵子樹B．所有葉結點都在同一層上C．各結點內關鍵字均升序或降序排列D．葉結點之間通過指針鏈接8、已知一棵二叉樹的前序遍歷結果為ABCDEF，中序遍歷結果為CBAEDF，則后序遍歷結果為（）。A.CBEFDAB.FEDCBAC.CBEDFAD.不定9、一棵非空的二叉樹的前序序列和后序序列正好相反，則該二叉樹一定滿足（）。A.其中任意一個結點均無左孩子B.其中任意一個結點均無右孩子C.其中只有一個葉結點D.其中度為2的結點最多為一個10、對序列{15，9，7，8，20，-1，4}用希爾排序方法排序，經一趟后序列變為{15，-1，4，8，20，9，7}則該次采用的增量是（）。A.1B.4C.3D.2二、填空題11、對單鏈表中元素按插入方法排序的C語言描述算法如下，其中L為鏈表頭結點指針。請填充算法中標出的空白處，完成其功能。12、分別采用堆排序，快速排序，起泡排序和歸并排序，對初態為有序的表，則最省時間的是______算法，最費時間的是______算法。13、VSAM（虛擬存儲存取方法）文件的優點是：動態地______，不需要文件進行______，并能較快地______進行查找。14、關鍵碼序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照關鍵碼值遞增的次序進行排序，若采用初始步長為4的希爾排序法，則一趟掃描的結果是______；若采用以第一個元素為分界元素的快速排序法，則掃描一趟的結果是______。15、設T是一棵結點值為整數的二叉排序樹，A是一個任意給定的整數。在下面的算法中，free_tree（T）在對二叉排序樹丁進行后序遍歷時釋放二又排序樹T的所有結點；delete_subtree（T，A），首先在二叉排序樹T中查找值為A的結點，根據查找情況分別進行如下處理：（1）若找不到值為A的結點，則返回根結點的地址（2）若找到值為A的結點，則刪除以此結點為根的子樹，并釋放此子樹中的所有結點，若值為A的結點是查找樹的根結點，刪除后變成空的二叉樹，則返null；否則返回根結點的地址。16、設正文串長度為n，模式串長度為m，則串匹配的KMP算法的時間復雜度為______。17、模式串P=‘abaabcac’的next函數值序列為______。18、假設一個15階的上三角矩陣A按行優先順序壓縮存儲在一維數組B中，則非零元素A9.9在B中的存儲位置k=______。（注：矩陣元素下標從1開始）三、判斷題19、對處理大量數據的外存介質而言，索引順序存取方法是一種方便的文件組織方法。（）20、倒排文件的目的是為了多關鍵字查找。（）21、設模式串的長度為m，目標串的長度為n，當n≈m且處理只匹配一次的模式時，樸素的匹配（即子串定位函數）算法所花的時間代價可能會更為節省。（）22、稀疏矩陣壓縮存儲后，必會失去隨機存取功能。（）23、哈夫曼樹度為1的結點數等于度為2和0的結點數之差。（）24、二叉樹是一般樹的特殊情形。（）25、順序存儲方式的優點是存儲密度大，且插入、刪除運算效率高。（）26、在外部排序過程中，對長度為n的初始序列進行“置換-選擇”排序時，可以得到的最大初始有序段的長度不超過n/2。（）27、有向圖中頂點V度等于其鄰接矩陣中第V行中的1的個數。（）28、B-樹中所有結點的平衡因子都為零。（）四、簡答題29、用一個數組S（設大小為MAX）作為兩個堆棧的共享空間。請說明共享方法，棧滿／棧空的判斷條件，并用C語言或PASCAL語言設計公用的入棧操作push（i，x），其中i為0或1，用于表示棧號，x為入棧值。30、請寫出應填入下列敘述中（）內的正確答案。排序有各種方法，如插入排序、快速排序、堆排序等。設一數組中原有數據如下：15，13，20，18，12，60。下面是一組用不同排序方法進行一遍排序后的結果。（）排序的結果為：12，13，15，18，20，60（）排序的結果為：13，15，18，12，20，60（）排序的結果為：13，15，20，18，12，60（）排序的結果為：12，13，20，18，15，6031、已知圖的鄰接矩陣為：當用鄰接表作為圖的存儲結構，且鄰接點都按序號從大到小排列時，試寫出：(1)以頂點V1為出發點的唯一的深度優先遍歷序列。當用鄰接表作為圖的存儲結構，且鄰接點都按序號從大到小排列時，試寫出：(1)以頂點V1為出發點的唯一的深度優先遍歷序列。(2)以頂點V1為出發點的唯一的廣度優先遍歷序列。(3)該圖唯一的拓撲有序序列。五、算法設計題32、已知一棵二叉樹的前序遍歷序列和中序遍歷序列分別存于兩個一維數組中，試編寫算法建立該二叉樹的二叉鏈表。33、請編寫完整的程序。如果矩陣A中存在這樣的一個元素A[i，j]滿足條件：A[i，j]是第i行中值最小的元素，且又是第j列中值最大的元素，則稱之為該矩陣的一個馬鞍點。請編程計算出m*n的矩陣A的所有馬鞍點。34、已知二叉樹T，試寫出復制該二叉樹的算法（t→T）。35、編寫算法，求二叉樹的寬度。

參考答案一、選擇題1、【答案】D2、【答案】A3、【答案】D4、【答案】A5、【答案】B6、【答案】A7、【答案】D8、【答案】A9、【答案】C10、【答案】B二、填空題11、【答案】（1）L->next=NULL//置空鏈表，然后將原鏈表結點逐個插入到有序表中（1） p!=NULL//當鏈表尚未到尾，p為工作指針（2） q!=NULL//查P結點在鏈表中的插入位置，這時q是工作指針（4）p->next=r->next//將P結點鏈入鏈表中（5）r->next=p//r是q的前驅，u是下個待插入結點的指針12、【答案】起泡；快速13、【答案】分配和釋放存儲空間；重組；對插入的記錄@14、【答案】（Q，A，C，S，Q，D，F，X，R，H，M,Y）；（F，H，C，D，a，A，M，Q，R，S，Y，X）15、【答案】free（T）；q&&q->data!=A；q=q->rchild；p->lchild=null；p->rchild=null16、【答案】O（m+n）17、【答案】0112231218、【答案】93三、判斷題19、【答案】×20、【答案】√21、【答案】√22、【答案】√23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】×28、【答案】√四、簡答題29、答：兩棧共享一向量空間（一維數組），棧底設在數組的兩端，兩棧頂相鄰時為棧滿。設共享數組為S[MAX]，則一個棧頂指針為一l，另一個棧頂指針為MAX時，棧為空。用C語言寫的入棧操作push（i，x