2022年武夷學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)數(shù)據(jù)結(jié)

實(shí)用文檔2022年武夷學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A（有答案）一、選擇題1、將線性表的數(shù)據(jù)元素進(jìn)行擴(kuò)充，允許帶結(jié)構(gòu)的線性表是（）。A.串B.樹C.廣義表D.棧2、將兩個(gè)各有N個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（）。A.NB.2N-1C.2ND.N-13、靜態(tài)鏈表中指針表示的是（）。A.下一元素的地址B.內(nèi)存儲(chǔ)器的地址C.下一元素在數(shù)組中的位置D.左鏈或右鏈指向的元素的地址4、下面關(guān)于串的敘述中，不正確的是（）。A.串是字符的有限序列B.空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運(yùn)算D.串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)5、下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（）。A.關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B.任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成C.所有的關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成D.某些關(guān)鍵活動(dòng)若提前完成，那么整個(gè)工程將會(huì)提前完成6、若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)（）。A．只有eB．有e、bC．有e、cD．無法確定7、已知字符串S為“abaabaabacacaabaabcc”，模式串t為“abaabc”，采用KMP算法進(jìn)行匹配，第一次出現(xiàn)“失配”（s!＝t）時(shí)，i＝j(luò)＝5，則下次開始匹配時(shí)，i和j的值分別（）。A．i＝1，j＝0B．i＝5，j＝0C．i＝5，j＝2D．i＝6，j＝28、有n（n>0）個(gè)分支結(jié)點(diǎn)的滿二叉樹的深度是（）。A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）9、有關(guān)二叉樹下列說法正確的是（）。A.二叉樹的度為2B.一棵二叉樹的度可以小于2C.二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2D.二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為210、一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（）。A.（38，40，46，56，79，84）B.（40，38，46，79，56，84）C.（40，38，46，56，79，84）D.（40，38，46，84，56，79）二、填空題11、下面程序的功能是用遞歸算法將一個(gè)整數(shù)按逆序存放到一個(gè)字符數(shù)組中。如123存放成321。請(qǐng)?zhí)羁眨?2、若用n表示圖中頂點(diǎn)數(shù)目，則有______條邊的無向圖成為完全圖。13、外排序的基本操作過程是______和______。14、數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的______和______以及它們之間的相互關(guān)系，并對(duì)與這種結(jié)構(gòu)定義相應(yīng)的______，設(shè)計(jì)出相應(yīng)的______。15、在一棵m階B-樹中，若在某結(jié)點(diǎn)中插入一個(gè)新關(guān)鍵字而引起該結(jié)點(diǎn)分裂，則此結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是______；若在某結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵字而導(dǎo)致結(jié)點(diǎn)合并，則該結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是______。16、已知鏈隊(duì)列的頭尾指針分別是f和r，則將值x入隊(duì)的操作序列是______。17、設(shè)廣義表L=（（），（）），則head（L）是______；tail（L）是______；L的長(zhǎng)度是______；深度是______。18、已知一循環(huán)隊(duì)列的存儲(chǔ)空間為[m..n]，其中n>m，隊(duì)頭和隊(duì)尾指針分別為front和rear，則此循環(huán)隊(duì)列判滿的條件是______。三、判斷題19、倒排文件的目的是為了多關(guān)鍵字查找。（）20、倒排文件是對(duì)次關(guān)鍵字建立索引。（）21、隊(duì)列和棧都是運(yùn)算受限的線性表，只允許在表的兩端進(jìn)行運(yùn)算。（）22、循環(huán)隊(duì)列也存在空間溢出問題。（）23、深度為k的二叉樹中結(jié)點(diǎn)總數(shù)小于等于2k-1。（）24、若從二叉樹的任一結(jié)點(diǎn)出發(fā)，到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹一定是哈夫曼樹。（）25、算法的優(yōu)劣與算法描述語(yǔ)言無關(guān)，但與所用計(jì)算機(jī)有關(guān)。（）26、為了很方便地插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。（）27、若一個(gè)有向圖的鄰接矩陣對(duì)角線以下元素均為零，則該圖的拓?fù)溆行蛐蛄斜囟ù嬖?。（?8、有向圖中頂點(diǎn)V度等于其鄰接矩陣中第V行中的1的個(gè)數(shù)。（）四、簡(jiǎn)答題29、用一個(gè)數(shù)組S（設(shè)大小為MAX）作為兩個(gè)堆棧的共享空間。請(qǐng)說明共享方法，棧滿／?？盏呐袛鄺l件，并用C語(yǔ)言或PASCAL語(yǔ)言設(shè)計(jì)公用的入棧操作push（i，x），其中i為0或1，用于表示棧號(hào)，x為入棧值。30、下面程序段的時(shí)間復(fù)雜度是什么？31、已知世界六大城市為：北京(Pe)、紐約(N)、巴黎(Pa)、倫敦(L)、東京(T)、墨西哥(M)，下表給定了這六大城市之間的交通里程：世界六大城市交通里程表(單位：百公里)（1）畫出這六大城市的交通網(wǎng)絡(luò)圖。（2）畫出該圖的鄰接表表示法。（3）畫出該圖按權(quán)值遞增的順序來構(gòu)造的最?。ù鷥r(jià)）生成樹。五、算法設(shè)計(jì)題32、對(duì)給定關(guān)鍵字序號(hào)j（1<j<n），要求在無序記錄A[1..n]中找到關(guān)鍵字從小到大排在第j位上的記錄，寫一個(gè)算法利用快速排序的劃分思想實(shí)現(xiàn)上述查找（要求用最少的時(shí)間和最少的空間）。例如：給定無序關(guān)鍵字{7，5，1，6，2，8，9，3}，當(dāng)j=4時(shí)，找到的關(guān)鍵字應(yīng)是5。33、有二叉排序樹采用二叉鏈表方式存放，樹中結(jié)點(diǎn)值各不相同，欲得到一個(gè)由大到小的結(jié)點(diǎn)值遞減序列，簡(jiǎn)述處理方法思路，用非遞歸形式寫出算法。34、以順序存儲(chǔ)結(jié)構(gòu)表示串，設(shè)計(jì)算法。求串s中出現(xiàn)的第一個(gè)最長(zhǎng)重復(fù)子串及其位置并分析算法的時(shí)間復(fù)雜度。35、已知兩個(gè)定長(zhǎng)數(shù)組，它們分別存放兩個(gè)非降序有序序列，請(qǐng)編寫程序把第二個(gè)數(shù)組序列中的數(shù)逐個(gè)插入到前一個(gè)數(shù)組序列中，完成后兩個(gè)數(shù)組中的數(shù)分別有序（非降序）并且第一數(shù)組中所有的數(shù)都不大于第二個(gè)數(shù)組中的任意一個(gè)數(shù)。注意，不能另開辟數(shù)組，也不能對(duì)任意一個(gè)數(shù)組進(jìn)行排序操作。例如：第一個(gè)數(shù)組為：4，12，28第二個(gè)數(shù)組為：1，7，9，29，45輸出結(jié)果為：l，4，7……第一個(gè)數(shù)組9，12，28，29，45……第二個(gè)數(shù)組

參考答案一、選擇題1、【答案】C2、【答案】A3、【答案】C4、【答案】B5、【答案】B6、【答案】A7、【答案】C8、【答案】C9、【答案】B10、【答案】C二、填空題11、【答案】a+1；n%10【解析】通過遞歸算法，首先找到最高位的值，將其放到str對(duì)應(yīng)的數(shù)組中，依次反向獲取從高位到地位的值，將其放到數(shù)組中，完成了將整數(shù)逆序放到一個(gè)字符數(shù)組中。12、【答案】n(n-1)/213、【答案】生成有序歸并段（順串）；歸并14、【答案】邏輯結(jié)構(gòu)；物理結(jié)構(gòu)；操作（運(yùn)算）；算法15、【答案】【解析】m階B-樹除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)最多是m1，最少16、【答案】s=（LinkedList*）ma11oc（sizeof（LNode））；s->data=x；s->next=r->next；r->next=s；r=s。17、【答案】（）；（（））；2；218、【答案】（rear+1）%（n-m+1）==front三、判斷題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ǔ)言寫的入棧操作push（i，x）如下：30、答：賦值語(yǔ)句一共被執(zhí)行了m*n次，所以該程序段的時(shí)間復(fù)雜度是O（m*n）。31、答：(1)這六大城市的交通網(wǎng)絡(luò)圖如圖所示：(2)該圖的鄰接表表示法如圖所示：(3