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

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

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