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、下列排序算法中，占用輔助空間最多的是（）。A.歸并排序B.快速排序C.希爾排序D.堆排序2、無(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，b3、線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）。A.隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)B.順序存取的存儲(chǔ)結(jié)構(gòu)C.索引存取的存儲(chǔ)結(jié)構(gòu)D.Hash存取的存儲(chǔ)結(jié)構(gòu)4、有六個(gè)元素6，5，4，3，2，1順序入棧，下列不是合法的出棧序列的是（）。A.543612B.453126C.346521D.2341565、已知有向圖G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>，<V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓?fù)湫蛄惺牵ǎ?。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、若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)（）。A．只有eB．有e、bC．有e、cD．無(wú)法確定7、已知關(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，198、有n（n>0）個(gè)分支結(jié)點(diǎn)的滿二叉樹的深度是（）。A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）9、設(shè)X是樹T中的一個(gè)非根結(jié)點(diǎn)，B是T所對(duì)應(yīng)的二叉樹。在B中，X是其雙親的右孩子，下列結(jié)論正確的是（）。A.在樹T中，X是其雙親的第一個(gè)孩子B.在樹T中，X一定無(wú)右兄弟C.在樹T中，X一定是葉結(jié)點(diǎn)D.在樹T中，X一定有左兄弟10、對(duì)n個(gè)記錄的線性表進(jìn)行快速排序?yàn)闇p少算法的遞歸深度，以下敘述正確的是（）。A.每次分區(qū)后，先處理較短的部分B.每次分區(qū)后，先處理較長(zhǎng)的部分C.與算法每次分區(qū)后的處理順序無(wú)關(guān)D.以上三者都不對(duì)二、填空題11、有向圖G=(V，E)，其中V(G)={0，1，2，3，4，5｝，用<a，b，d>三元組表示弧<a，b>及弧上的權(quán)d。E(G)為E(G)=｛<0，5，100>，<0，2，10>，<1，2，5>，<0，4，30>，<4，5，60>，<3，5，10>，<2，3，50>，<4，3，20>｝，則從源點(diǎn)0到頂點(diǎn)3的最短路徑長(zhǎng)度是______，經(jīng)過(guò)的中間頂點(diǎn)是______。12、設(shè)用希爾排序?qū)?shù)組{98，36，-9，0，47，23，1，8，10，7}進(jìn)行排序，給出的步長(zhǎng)（也稱增量序列）依次是4，2，1則排序需______趟，寫出第一趟結(jié)束后，數(shù)組中數(shù)據(jù)的排列次序______。13、在基于關(guān)鍵字比較且時(shí)間為O（nlog2n）的排序中，若要求排序是穩(wěn)定的，則可選用______排序；若要求就地排序（及輔助空間為O（1）），則可選用______排序。14、數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的______和______以及它們之間的相互關(guān)系，并對(duì)與這種結(jié)構(gòu)定義相應(yīng)的______，設(shè)計(jì)出相應(yīng)的______。15、線性表L=（a1，a2，…，an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是______。16、設(shè)正文串長(zhǎng)度為n，模式串長(zhǎng)度為m，則串匹配的KMP算法的時(shí)間復(fù)雜度為_(kāi)_____。17、設(shè)廣義表L=（（），（）），則head（L）是______；tail（L）是______；L的長(zhǎng)度是______；深度是______。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、對(duì)處理大量數(shù)據(jù)的外存介質(zhì)而言，索引順序存取方法是一種方便的文件組織方法。（）20、倒排序文件的優(yōu)點(diǎn)是維護(hù)簡(jiǎn)單。（）21、廣義表（（（a，b，c），d，e，f））的長(zhǎng)度是4。（）22、一個(gè)廣義表可以為其他廣義表所共享。（）23、對(duì)于有n個(gè)結(jié)點(diǎn)的二叉樹，其高度為log2n。（）24、樹形結(jié)構(gòu)中元素之間存在一對(duì)多的關(guān)系。（）25、順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（）26、若中序遍歷平衡的二叉排序樹，可得到排好序的關(guān)鍵碼序列。（）27、采用線性探測(cè)法處理散列時(shí)的沖突，當(dāng)從哈希表刪除一個(gè)記錄時(shí)，不應(yīng)將這個(gè)記錄的所在位置置空，因?yàn)檫@會(huì)影響以后的查找。（）28、有向圖中頂點(diǎn)V度等于其鄰接矩陣中第V行中的1的個(gè)數(shù)。（）四、簡(jiǎn)答題29、對(duì)于具有n個(gè)葉結(jié)點(diǎn)且所有非葉結(jié)點(diǎn)都有左、右孩子的二叉樹。(1)試問(wèn)這種二叉樹的結(jié)點(diǎn)總數(shù)是多少?(2)試證明2-（li-1）=1。其中：li表示第i個(gè)葉結(jié)點(diǎn)所在的層號(hào)（設(shè)根結(jié)點(diǎn)所在層號(hào)為1）。30、下面程序段的時(shí)間復(fù)雜度是什么？31、已知有6個(gè)頂點(diǎn)（頂點(diǎn)編號(hào)為0～5）的有向帶權(quán)圖G，其鄰接矩陣A為上三角矩陣，按行為主序（行優(yōu)先）保存在如下的一維數(shù)組中。要求：（1）寫出圖G的鄰接矩陣A。（2）畫出有向帶權(quán)圖G。求圖G的關(guān)鍵路徑，并計(jì)算該關(guān)鍵路徑的長(zhǎng)度。五、算法設(shè)計(jì)題32、當(dāng)一棵有n（n≤100）個(gè)結(jié)點(diǎn)的二叉樹按順序存儲(chǔ)方式存儲(chǔ)在bt[1..n]中時(shí)，試寫一個(gè)算法，求出二叉樹中結(jié)點(diǎn)值分別為x和y的兩個(gè)結(jié)點(diǎn)的最近公共祖先結(jié)點(diǎn)的值。33、寫出一趟快速排序算法。34、已知字符串s1中存放一段英文，寫出算法format（s1，s2，s3，n），將其按給定的長(zhǎng)度n格式化成兩端對(duì)齊的字符串s2，其多余的字符送s3。35、在輸入數(shù)據(jù)無(wú)序的情況下，建立一個(gè)數(shù)據(jù)值為整型的遞增有序的順序存儲(chǔ)線性表L，且要求當(dāng)輸入相同數(shù)據(jù)值時(shí)，線性表中不能存在數(shù)據(jù)值相同的數(shù)據(jù)元素，試寫出其算法。順序存儲(chǔ)結(jié)構(gòu)的線性表描述為：

參考答案一、選擇題1、【答案】A2、【答案】D3、【答案】A4、【答案】C5、【答案】A6、【答案】A7、【答案】A8、【答案】C9、【答案】D10、【答案】A二、填空題11、【答案】50；412、【答案】3；（10，7，-9，0，47，23，1，8，98，36）@13、【答案】歸并；堆14、【答案】邏輯結(jié)構(gòu)；物理結(jié)構(gòu)；操作（運(yùn)算）；算法15、【答案】（n-1）/216、【答案】O（m+n）17、【答案】（）；（（））；2；218、【答案】23；100CH三、判斷題19、【答案】×20、【答案】×21、【答案】×22、【答案】√23、【答案】×24、【答案】√25、【答案】×26、【答案】√27、【答案】√28、【答案】×四、簡(jiǎn)答題29、答：（1）根據(jù)二叉樹中度為2的結(jié)點(diǎn)個(gè)數(shù)等于葉結(jié)點(diǎn)個(gè)數(shù)減1的性質(zhì)，故具有n個(gè)葉結(jié)點(diǎn)且非葉子結(jié)點(diǎn)均有左子樹的二叉樹的結(jié)點(diǎn)數(shù)是2n-1。（2）證明：當(dāng)i=1時(shí)，2-（1-1）=20=1，公式成立。設(shè)當(dāng)i=n-1時(shí)公式成立，證明當(dāng)i=n時(shí)公式仍成立。設(shè)某葉結(jié)點(diǎn)的層號(hào)為t，當(dāng)將該結(jié)點(diǎn)變?yōu)閮?nèi)部結(jié)點(diǎn)，從而再增加兩個(gè)葉結(jié)點(diǎn)時(shí)，這兩個(gè)葉結(jié)點(diǎn)的層號(hào)都是t+1，對(duì)于公式的變化，是減少了一個(gè)原來(lái)的葉結(jié)點(diǎn)，增加了兩個(gè)新葉結(jié)點(diǎn)，反映到公式中，因?yàn)?-（t-1）=2-（t+1-1）+2-（t+1-1），所以結(jié)果不變，這就證明當(dāng)i=n時(shí)公式仍成立。證畢。30、答：賦值語(yǔ)句一共被執(zhí)行了m*n次，所以該程序段的時(shí)間復(fù)雜度是O（m*n）。31、答：（1）由題可以畫出待定上三角矩陣的結(jié)構(gòu)圖如下（圖中？為待定元素）：可以看出，第一行至第五行主對(duì)角線上方的