2022年中國海洋大學(xué)計算機(jī)科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A(有答案)

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

參考答案一、選擇題1、【答案】D2、【答案】A3、【答案】D4、【答案】A5、【答案】B6、【答案】A7、【答案】D8、【答案】A9、【答案】C10、【答案】B二、填空題11、【答案】（1）L->next=NULL//置空鏈表，然后將原鏈表結(jié)點(diǎn)逐個插入到有序表中（1） p!=NULL//當(dāng)鏈表尚未到尾，p為工作指針（2） q!=NULL//查P結(jié)點(diǎn)在鏈表中的插入位置，這時q是工作指針（4）p->next=r->next//將P結(jié)點(diǎn)鏈入鏈表中（5）r->next=p//r是q的前驅(qū)，u是下個待插入結(jié)點(diǎn)的指針12、【答案】起泡；快速13、【答案】分配和釋放存儲空間；重組；對插入的記錄@14、【答案】（Q，A，C，S，Q，D，F(xiàn)，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、答：兩棧共享一向量空間（一維數(shù)組），棧底設(shè)在數(shù)組的兩端，兩棧頂相鄰時為棧滿。設(shè)共享數(shù)組為S[MAX]，則一個棧頂指針為一l，另一個棧頂指針為MAX時，棧為空。用C語言寫的入棧操作push（i，x