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、下列說(shuō)法不正確的是（）。A.圖的遍歷是從給定的源點(diǎn)出發(fā)每個(gè)頂點(diǎn)僅被訪問(wèn)一次B.遍歷的基本方法有兩種：深度遍歷和廣度遍歷C.圖的深度遍歷不適用于有向圖D.圖的深度遍歷是一個(gè)遞歸過(guò)程2、用數(shù)組r存儲(chǔ)靜態(tài)鏈表，結(jié)點(diǎn)的next域指向后繼，工作指針j指向鏈中結(jié)點(diǎn)，使j沿鏈移動(dòng)的操作為（）。A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next3、算法的計(jì)算量的大小稱為計(jì)算的（）。A.效率B.復(fù)雜性C.現(xiàn)實(shí)性D.難度4、有六個(gè)元素6，5，4，3，2，1順序入棧，下列不是合法的出棧序列的是（）。A.543612B.453126C.346521D.2341565、下面關(guān)于串的敘述中，不正確的是（）。A.串是字符的有限序列B.空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運(yùn)算D.串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)6、下列關(guān)于無(wú)向連通圖特性的敘述中，正確的是（）。Ⅰ．所有的頂點(diǎn)的度之和為偶數(shù)Ⅱ．邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1Ⅲ．至少有一個(gè)頂點(diǎn)的度為1A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ7、下列選項(xiàng)中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是（）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，4508、一棵哈夫曼樹共有215個(gè)結(jié)點(diǎn)，對(duì)其進(jìn)行哈夫曼編碼，共能得到（）個(gè)不同的碼字。A.107B.108C.214D.2159、在下述結(jié)論中，正確的有（）。①只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0。②二叉樹的度為2。③二叉樹的左右子樹可任意交換。④深度為K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。A.①②③B.⑦③④C.②④D.①④10、在文件“局部有序”或文件長(zhǎng)度較小的情況下，最佳內(nèi)部排序的方法是（）。A.直接插入排序B.起泡排序C.簡(jiǎn)單選擇排序D.快速排序二、填空題11、對(duì)n個(gè)記錄的表r[1..n]進(jìn)行簡(jiǎn)單選擇排序，所需進(jìn)行的關(guān)鍵字間的比較次數(shù)為______。12、起始地址為480，大小為8的塊，其伙伴塊的起始地址是______；若塊大小為32，則其伙伴塊的起始地址為______。13、數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是______。14、數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的______和______以及它們之間的相互關(guān)系，并對(duì)與這種結(jié)構(gòu)定義相應(yīng)的______，設(shè)計(jì)出相應(yīng)的______。15、按LSD進(jìn)行關(guān)鍵字排序，除最次位關(guān)鍵字之外，對(duì)每個(gè)關(guān)鍵字進(jìn)行排序時(shí)，只能用______的排序方法。16、每一棵樹都能唯一地轉(zhuǎn)換為它所對(duì)應(yīng)的二叉樹。若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列是______。設(shè)上述二叉樹是由某棵樹轉(zhuǎn)換而成，則該樹的前序序列是______。17、一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹有______個(gè)度為1的結(jié)點(diǎn)、有______個(gè)分支（非終端）結(jié)點(diǎn)和______個(gè)葉子，該滿二叉樹的深度為______。18、在順序存儲(chǔ)的二叉樹中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處在同一層的條件是______。三、判斷題19、倒排文件的目的是為了多關(guān)鍵字查找。（）20、哈希表與哈希文件的唯一區(qū)別是哈希文件引入了“桶”的概念。（）21、循環(huán)隊(duì)列也存在空間溢出問(wèn)題。（）22、廣義表（（（a，b，c），d，e，f））的長(zhǎng)度是4。（）23、對(duì)于有n個(gè)結(jié)點(diǎn)的二叉樹，其高度為log2n。（）24、二叉樹是一般樹的特殊情形。（）25、排序算法中的比較次數(shù)與初始元素序列的排列無(wú)關(guān)。（）26、為提高排序速度，進(jìn)行外排序時(shí)，必須選用最快的內(nèi)排序算法。（）27、無(wú)環(huán)有向圖才能進(jìn)行拓?fù)渑判?。（?8、采用線性探測(cè)法處理散列時(shí)的沖突，當(dāng)從哈希表刪除一個(gè)記錄時(shí)，不應(yīng)將這個(gè)記錄的所在位置置空，因?yàn)檫@會(huì)影響以后的查找。（）四、簡(jiǎn)答題29、閱讀下面的算法，說(shuō)明算法實(shí)現(xiàn)的功能。30、調(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ù)：31、設(shè)二叉樹BT的存儲(chǔ)結(jié)構(gòu)如表：其中BT為樹根結(jié)點(diǎn)的指針，其值為6，Lchild、Rchild分別為結(jié)點(diǎn)的左、右孩子指針域data為結(jié)點(diǎn)的數(shù)據(jù)域。試完成下列各題：（1）畫出二叉樹BT邏輯結(jié)構(gòu)。（2）寫出按前序、中序、后序遍歷該二叉樹所得到的結(jié)點(diǎn)序列。（3）畫出二叉樹的后序線索樹。五、算法設(shè)計(jì)題32、假設(shè)有兩個(gè)按元素值遞增次序排列的線性表，均以單鏈表形式存儲(chǔ)。請(qǐng)編寫算法將這兩個(gè)單鏈表歸并為一個(gè)按元素值遞減次序排列的單鏈表，并要求利用原來(lái)兩個(gè)單鏈表的結(jié)點(diǎn)存放歸并后的單鏈表。33、給定一個(gè)整數(shù)數(shù)組b[0..N-1]，b中連續(xù)的相等元素構(gòu)成的子序列稱為平臺(tái)。試設(shè)計(jì)算法，求出b中最長(zhǎng)平臺(tái)的長(zhǎng)度。34、圖G有n個(gè)點(diǎn)，利用從某個(gè)源點(diǎn)到其余各點(diǎn)最短路徑算法思想，設(shè)計(jì)一產(chǎn)生G的最小生成樹的算法。35、設(shè)二叉排序樹的各元素值均不相同，采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，試分別設(shè)計(jì)遞歸和非遞歸算法按遞減序打印所有左子樹為空，右子樹非空的結(jié)點(diǎn)的數(shù)據(jù)域的值。

參考答案一、選擇題1、【答案】C2、【答案】A3、【答案】B4、【答案】C5、【答案】B6、【答案】A7、【答案】A8、【答案】B9、【答案】D10、【答案】A二、填空題11、【答案】n（n-1）/212、【答案】480+8=488；480-32=44813、【答案】算法的時(shí)間復(fù)雜度和空間復(fù)雜度14、【答案】邏輯結(jié)構(gòu)；物理結(jié)構(gòu)；操作（運(yùn)算）；算法15、【答案】穩(wěn)定16、【答案】FEGHDCB；BEF【解析】樹的前序序列對(duì)應(yīng)二叉樹的前序序列，該二叉樹轉(zhuǎn)換成森林時(shí)含三棵樹，其第一棵樹的前序是BEF。17、【答案】【解析】滿二叉樹沒(méi)有度為1的結(jié)點(diǎn)，度為0的結(jié)點(diǎn)等于度為2的結(jié)點(diǎn)個(gè)數(shù)+1。18、【答案】【解析】用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)二叉樹時(shí)，要按完全二叉樹的形式存儲(chǔ)，非完全二叉樹存儲(chǔ)時(shí)，要加“虛結(jié)點(diǎn)”。設(shè)編號(hào)為i和j的結(jié)點(diǎn)在順序存儲(chǔ)中的下標(biāo)為s和t，則結(jié)點(diǎn)i和j在同一層上的條件是三、判斷題19、【答案】√20、【答案】×21、【答案】√22、【答案】×23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、簡(jiǎn)答題29、答：本算法功能是將兩個(gè)無(wú)頭結(jié)點(diǎn)的循環(huán)鏈表合并為一個(gè)循環(huán)鏈表。head1最后一個(gè)結(jié)點(diǎn)的鏈域指向head2，head2最后一個(gè)結(jié)點(diǎn)的鏈域指向head1，head1為結(jié)果循環(huán)鏈表的指針。30、答：（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é)果為：31、答：（1）二叉樹