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

2022年馬鞍山學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A（有答案）一、選擇題1、已知廣義表LS=（（a，b，c），（d，e，f）），用head和tail數(shù)取出LS中原子e的運(yùn)算是（）。A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））2、下列排序算法中，占用輔助空間最多的是（）。A.歸并排序B.快速排序C.希爾排序D.堆排序3、以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是（）。A.循環(huán)隊(duì)列B.鏈表C.哈希表D.棧4、在下列表述中，正確的是（）A.含有一個(gè)或多個(gè)空格字符的串稱為空格串B.對(duì)n（n>0）個(gè)頂點(diǎn)的網(wǎng)，求出權(quán)最小的n-1條邊便可構(gòu)成其最小生成樹(shù)C.選擇排序算法是不穩(wěn)定的D.平衡二叉樹(shù)的左右子樹(shù)的結(jié)點(diǎn)數(shù)之差的絕對(duì)值不超過(guò)l5、已知串S='aaab'，其next數(shù)組值為（）。A.0123B.1123C.1231D.12116、已知關(guān)鍵字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入關(guān)鍵字3，調(diào)整后的小根堆是（）。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，197、下列敘述中，不符合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、在下述結(jié)論中，正確的有（）。①只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0。②二叉樹(shù)的度為2。③二叉樹(shù)的左右子樹(shù)可任意交換。④深度為K的完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹(shù)。A.①②③B.⑦③④C.②④D.①④9、有關(guān)二叉樹(shù)下列說(shuō)法正確的是（）。A.二叉樹(shù)的度為2B.一棵二叉樹(shù)的度可以小于2C.二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2D.二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為210、分別以下列序列構(gòu)造二叉排序樹(shù)，與用其他三個(gè)序列所構(gòu)造的結(jié)果不同的是（）。A.（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，20，110，130）D.（100，80，60，90，120，130，110）二、填空題11、設(shè)用希爾排序?qū)?shù)組{98，36，-9，0，47，23，1，8，10，7}進(jìn)行排序，給出的步長(zhǎng)（也稱增量序列）依次是4，2，1則排序需______趟，寫出第一趟結(jié)束后，數(shù)組中數(shù)據(jù)的排列次序______。12、在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)______。13、已知有序表為（12，18，24，35，47，50，62，83，90，115，134）當(dāng)用二分法查找90時(shí)，需______次查找成功，查找47時(shí)______成功，查找100時(shí)，需______次才能確定不成功。14、文件由______組成；記錄由______組成。15、VSAM（虛擬存儲(chǔ)存取方法）文件的優(yōu)點(diǎn)是：動(dòng)態(tài)地______，不需要文件進(jìn)行______，并能較快地______進(jìn)行查找。16、已知一循環(huán)隊(duì)列的存儲(chǔ)空間為[m..n]，其中n>m，隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear，則此循環(huán)隊(duì)列判滿的條件是______。17、設(shè)有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù)順序存放在向量A[1：N]中，其下標(biāo)值最大的分支結(jié)點(diǎn)為_(kāi)_____。18、設(shè)有一個(gè)空棧，棧頂指針為1000H（十六進(jìn)制），現(xiàn)有輸入序列為l，2，3，4，5，經(jīng)過(guò)PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，輸出序列是______，而棧頂指針值是______。設(shè)棧為順序棧，每個(gè)元素占4個(gè)字節(jié)。三、判斷題19、倒排序文件的優(yōu)點(diǎn)是維護(hù)簡(jiǎn)單。（）20、對(duì)磁帶機(jī)而言，ISAM是一種方便的文件組織方法（）21、隊(duì)列和棧都是運(yùn)算受限的線性表，只允許在表的兩端進(jìn)行運(yùn)算。（）22、一個(gè)廣義表可以為其他廣義表所共享。（）23、哈夫曼樹(shù)度為1的結(jié)點(diǎn)數(shù)等于度為2和0的結(jié)點(diǎn)數(shù)之差。（）24、任何二叉樹(shù)的后序線索樹(shù)進(jìn)行后序遍歷時(shí)都必須用棧。（）25、外部排序是把外存文件調(diào)入內(nèi)存，可利用內(nèi)部排序的方法進(jìn)行排序，因此排序所花的時(shí)間取決于內(nèi)部排序的時(shí)間。（）26、為提高排序速度，進(jìn)行外排序時(shí)，必須選用最快的內(nèi)排序算法。（）27、B-樹(shù)中所有結(jié)點(diǎn)的平衡因子都為零。（）28、在動(dòng)態(tài)存儲(chǔ)管理系統(tǒng)中做空間分配時(shí)，最佳適配法與最先適配法相比，前者容易增加閑置空間的碎片。（）四、簡(jiǎn)答題29、調(diào)用下列C函數(shù)f（n），回答下列問(wèn)題：（1）試指出f（n）值的大小，并寫出，f（n）值的推導(dǎo)過(guò)程。（2）假定n=5，試指出，f（5）值的大小和執(zhí)行，f（5）時(shí)的輸出結(jié)果。C函數(shù)：30、設(shè)有n個(gè)元素采用起泡排序法進(jìn)行排序，通常需要進(jìn)行多少趟排序?對(duì)于第J趟起泡通常需要進(jìn)行多少次關(guān)鍵字比較?在程序設(shè)計(jì)中如何設(shè)置判斷條件，有可能使起泡趟數(shù)可以減少并且能完成排序。31、設(shè)將n（n＞1）個(gè)整數(shù)存放到一維數(shù)組R中。試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面都盡可能高效的算法，將R中存有的序列循左移P（0＜P＜n）個(gè)位置，即將R中的數(shù)據(jù)由（X0，X1，…，Xn－1）變換為（xp，xp＋1，…，xn－1，x0，x1，…，xp－1）。要求：（1） 給出算法的基本設(shè)計(jì)思想。（2） 根據(jù)設(shè)計(jì)思想，采用C或C＋＋或JAVA語(yǔ)言描述算法，關(guān)鍵之處給出注釋。說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。五、算法設(shè)計(jì)題32、設(shè)有一個(gè)數(shù)組中存放了一個(gè)無(wú)序的關(guān)鍵序列K1，K2，…，Kn?，F(xiàn)要求將Kn放在將元素排序后的正確位置上，試編寫實(shí)現(xiàn)該功能的算法，要求比較關(guān)鍵字的次數(shù)不超過(guò)n（注：用程序?qū)崿F(xiàn)）。33、一個(gè)有向圖G=(V，E)的平方圖G2=(V，E2)滿足下述性質(zhì)：(U，w)∈E2當(dāng)且僅當(dāng)存在某個(gè)頂點(diǎn)v∈V，使得(u，v)∈E且(v，w)∈E。寫一個(gè)算法從給定的G求出G2，G和G2可分別用兩個(gè)鄰接表表示。34、按圖的寬度優(yōu)先搜索法寫一算法判別以鄰接矩陣存儲(chǔ)的有向圖中是否存在由頂點(diǎn)Vi到頂點(diǎn)Vj的路徑(i≠j)35、編寫一算法，利用葉結(jié)點(diǎn)中的空指針域?qū)⑺腥~結(jié)點(diǎn)鏈接為一個(gè)帶有頭結(jié)點(diǎn)的雙鏈表，算法返回頭結(jié)點(diǎn)的地址。

參考答案一、選擇題1、【答案】C2、【答案】A3、【答案】D4、【答案】C5、【答案】A6、【答案】A7、【答案】D8、【答案】D9、【答案】B10、【答案】C二、填空題11、【答案】3；（10，7，-9，0，47，23，1，8，98，36）@12、【答案】2(n-1)13、【答案】2；4；3【解析】二分法查找元素次數(shù)列表查找100是找到115就停止了。14、【答案】記錄；數(shù)據(jù)項(xiàng)15、【答案】分配和釋放存儲(chǔ)空間；重組；對(duì)插入的記錄@16、【答案】（rear+1）%（n-m+1）==front17、【答案】【解析】最大的分支結(jié)點(diǎn)是最后一個(gè)葉子結(jié)點(diǎn)的父結(jié)點(diǎn)。18、【答案】23；100CH三、判斷題19、【答案】×20、【答案】×21、【答案】×22、【答案】√23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、簡(jiǎn)答題29、答：（1）第一層for循環(huán)判斷n+1次，往下執(zhí)行n次，第二層for執(zhí)行次數(shù)為（n+（n-1）+（n-2）+…+1），第三層循環(huán)體受第一層循環(huán)和第二層循環(huán)的控制，其執(zhí)行次數(shù)如表1-1所示。執(zhí)行次數(shù)為f(n)=（1+2+…+，n）+（2+3+…+，n）+…+n=n*n（n+1）/2-n（n2-1）/6。（2）在n=5對(duì)，f（5）=55，執(zhí)行過(guò)程中，輸出結(jié)果為：30、答：n個(gè)元素采用起泡排序法進(jìn)行排序，通常需要進(jìn)行n-1趟排序。第j趟起泡排序要進(jìn)行n-j次比較。在一趟排序中，若沒(méi)有記錄交換，則表示排序完成。因而，可通過(guò)設(shè)標(biāo)記來(lái)控制排序結(jié)束，下面語(yǔ)句段說(shuō)明了標(biāo)記flag的使用。31、答：（1）算法的基本設(shè)計(jì)思想：先將n個(gè)數(shù)據(jù)由x0，x1，…，xp，…，xn－1原地逆置，得到xn－1，…，xp，xp－1，…，x0然后再將數(shù)組R中的前n－P個(gè)數(shù)和后P個(gè)數(shù)分別原地逆置，最終