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

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