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、若需在O（nlog2n）的時(shí)間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（）。A.快速排序B.堆排序C.歸并排序D.直接插入排序2、n個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目（）。A.n*nB.n(n+1)C.n/2D.n*(n-1)3、若線性表最常用的操作是存取第i個(gè)元素及其前驅(qū)和后繼元素的值，為節(jié)省時(shí)間應(yīng)采用的存儲(chǔ)方式（）。A.單鏈表B.雙向鏈表C.單循環(huán)鏈表D.順序表4、下面關(guān)于串的敘述中，不正確的是（）。A.串是字符的有限序列B.空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運(yùn)算D.串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)5、已知串S='aaab'，其next數(shù)組值為（）。A.0123B.1123C.1231D.12116、已知字符串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＝27、下列選項(xiàng)中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是（）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，4508、在下述結(jié)論中，正確的有（）。①只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0。②二叉樹的度為2。③二叉樹的左右子樹可任意交換。④深度為K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。A.①②③B.⑦③④C.②④D.①④9、一棵非空的二叉樹的前序序列和后序序列正好相反，則該二叉樹一定滿足（）。A.其中任意一個(gè)結(jié)點(diǎn)均無左孩子B.其中任意一個(gè)結(jié)點(diǎn)均無右孩子C.其中只有一個(gè)葉結(jié)點(diǎn)D.其中度為2的結(jié)點(diǎn)最多為一個(gè)10、分別以下列序列構(gòu)造二叉排序樹，與用其他三個(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、若用n表示圖中頂點(diǎn)數(shù)目，則有______條邊的無向圖成為完全圖。12、N個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí)，該矩陣至少有______個(gè)非零元素。13、索引順序文件既可以順序存取，也可以______存取。14、數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是______。15、一個(gè)算法具有5個(gè)特性：______、______、______、有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。16、每一棵樹都能唯一地轉(zhuǎn)換為它所對應(yīng)的二叉樹。若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列是______。設(shè)上述二叉樹是由某棵樹轉(zhuǎn)換而成，則該樹的前序序列是______。17、當(dāng)兩個(gè)棧共享一存儲(chǔ)區(qū)時(shí)，棧利用一維數(shù)組stack（1，n）表示，兩棧頂指針為top[1]與top[2]，則當(dāng)棧1空時(shí)，top[1]為______，棧2空時(shí)，top[2]為______，棧滿時(shí)為______。18、假設(shè)一個(gè)15階的上三角矩陣A按行優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組B中，則非零元素A9.9在B中的存儲(chǔ)位置k=______。（注：矩陣元素下標(biāo)從1開始）三、判斷題19、對磁帶機(jī)而言，ISAM是一種方便的文件組織方法（）20、哈希表與哈希文件的唯一區(qū)別是哈希文件引入了“桶”的概念。（）21、稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。（）22、棧的輸入序列是1，2，…，n，輸出序列是a1，a2，…，an若ai=n（1≤i≤n）則有：ai>ai+1>…>an。（）23、二叉樹是一般樹的特殊情形。（）24、一個(gè)樹形的葉結(jié)點(diǎn)，在前序遍歷和后序遍歷下，皆以相同的相對位置出現(xiàn)。（）25、外部排序是把外存文件調(diào)入內(nèi)存，可利用內(nèi)部排序的方法進(jìn)行排序，因此排序所花的時(shí)間取決于內(nèi)部排序的時(shí)間。（）26、在用堆排序算法排序時(shí)，如果要進(jìn)行增序排序，則需要采用“大根堆”。（）27、無環(huán)有向圖才能進(jìn)行拓?fù)渑判?。（?8、B-樹中所有結(jié)點(diǎn)的平衡因子都為零。（）四、簡答題29、設(shè)目標(biāo)為t=‘a(chǎn)bcaabbabcabaacbacba’，模式為P=‘a(chǎn)bcabaa’（1）計(jì)算模式p的nextval函數(shù)值。（2）不寫出算法，只畫出利用KMP算法進(jìn)行模式匹配時(shí)每一趟的匹配過程。30、給出一組關(guān)鍵字：29，18，25，47，58，12，51，10，分別寫出按下列各種排序方法進(jìn)行排序時(shí)的變化過程：（1） 歸并排序，每歸并一次書寫一個(gè)次序。（2） 快速排序，每劃分一次書寫一個(gè)次序。（3） 堆排序，先建成一個(gè)堆，然后每從堆頂取下一個(gè)元素后，將堆調(diào)整一次。31、已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)結(jié)構(gòu)為假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下，請?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)（k為正整數(shù)）。若查找成功，算法輸出該結(jié)點(diǎn)的data域的值，并返回1；否則，只返回0。要求：（1）描述算法的基本設(shè)計(jì)思想。（2）描述算法的詳細(xì)實(shí)現(xiàn)步驟。（3）根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語言描述算法（使用C或C＋＋或JAVA語言實(shí)現(xiàn)），關(guān)鍵之處請給出簡要注釋。五、算法設(shè)計(jì)題32、寫一算法找出n個(gè)數(shù)的最大值和最小值，要求最壞條件下的元素比較次數(shù)為33、已知P是指向單向循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的指針，試編寫只包含一個(gè)循環(huán)的算法，將線性表（a1，a2，…，an-1，an）改造為（a1，a2，…，an-1，an，an-1，…，a2，a1）。34、編寫程序，統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符出現(xiàn)的頻度并將結(jié)果存入文件（字符串中的合法字符為A～Z這26個(gè)字母和0～9這10個(gè)數(shù)字）。35、二路插入排序是將待排關(guān)鍵字序列r[1..n]中關(guān)鍵字分二路分別按序插入到輔助向量d[1..n]前半部和后半部（注：向量d可視為循環(huán)表），其原則為，先將r[1]賦給d[1]，再從r[2]記錄開始分二路插入。編寫實(shí)現(xiàn)2-路插入排序算法。

參考答案一、選擇題1、【答案】C2、【答案】D3、【答案】D4、【答案】B5、【答案】A6、【答案】C7、【答案】A8、【答案】D9、【答案】C10、【答案】C二、填空題11、【答案】n(n-1)/212、【答案】2(N-1)13、【答案】隨機(jī)14、【答案】算法的時(shí)間復(fù)雜度和空間復(fù)雜度15、【答案】有窮性；確定性；可行性16、【答案】FEGHDCB；BEF【解析】樹的前序序列對應(yīng)二叉樹的前序序列，該二叉樹轉(zhuǎn)換成森林時(shí)含三棵樹，其第一棵樹的前序是BEF。17、【答案】0；n+1；top[1]+1=top[2]18、【答案】93三、判斷題19、【答案】×20、【答案】×21、【答案】√22、【答案】×23、【答案】×24、【答案】√25、【答案】×26、【答案】√27、【答案】√28、【答案】√四、簡答題29、答：（1）p的nextval函數(shù)值為0110132（p的next函數(shù)值為0111232）。（2）利用KMP（改進(jìn)的nextval）算法，每趟匹配過程如下：30、答：（1）2一路歸并第一趟：18，29，25，47，12，58，10，51。第二趟：18，25，29，47，10，12，51，58。第三趟：10，12，18，25，29，47，51，58。（2）快速排序第一趟：10，18，25，12，29，58，51，47。第二趟：10，18，25，12，29，47，51，88。第三趟：10，12，18，25，29，47，51，88。（3）堆排序建大堆：58，47，51，29，18，12，25，10。51，47，25，29，18，12，10，58。47，29，25，10，18，12，51，58。29，18，25，10，12，47，51，58。25，18，12，10，29，47，51，58。18，10，12，25，29，47，51，58。12，10，18，25，29，47，51，58。10，12，18，25，29，47，51，58。31、答：（1）算法的基本設(shè)計(jì)思想定義兩個(gè)指針變量p和q，初始時(shí)均指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。p指針沿鏈表移動(dòng)；當(dāng)p指針移動(dòng)到第k個(gè)結(jié)點(diǎn)時(shí)，q指針開始與p指針同步移動(dòng)；當(dāng)p指針移動(dòng)到鏈表最后一個(gè)結(jié)點(diǎn)時(shí)，因?yàn)閜和q相隔k，故q指針?biāo)冈貫榈箶?shù)第k個(gè)結(jié)點(diǎn)。以上過程對鏈表僅進(jìn)行一遍掃描。（2）算法的詳細(xì)實(shí)現(xiàn)步驟①count＝