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

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

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