北華大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁北華大學(xué)《數(shù)據(jù)結(jié)構(gòu)》

2021-2022學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在數(shù)據(jù)結(jié)構(gòu)中，樹的遍歷可以采用遞歸和非遞歸方式。以下關(guān)于非遞歸中序遍歷二叉樹的說法，錯誤的是（）A.可以使用棧來輔助實現(xiàn)B.比遞歸方式更復(fù)雜C.時間復(fù)雜度與遞歸方式相同D.空間復(fù)雜度一定比遞歸方式低2、在一個具有n個元素的順序存儲的線性表中，刪除第i個元素（1<=i<=n），需要移動多少個元素？（）A.n-iB.iC.n-i+1D.n-i-13、在一棵度為4的樹中，若有20個度為4的節(jié)點，10個度為3的節(jié)點，1個度為2的節(jié)點，10個葉子節(jié)點，那么這棵樹的總節(jié)點數(shù)是多少？A.82B.81C.79D.784、設(shè)有一個字符串S="helloworld"，要計算字符串S的長度（不包括結(jié)束符'\0'），以下函數(shù)正確的是？（）A.intlength(char*s){intcount=0;while(*s!='\0'){count++;s++;}returncount;}B.intlength(char*s){intcount=0;for(;*s!='\0';s++){count++;}returncount;}C.intlength(char*s){intcount=0;do{count++;s++;}while(*s!='\0');returncount;}D.intlength(char*s){intcount=0;while(s[count]!='\0'){count++;}returncount;}5、以下哪種數(shù)據(jù)結(jié)構(gòu)適合頻繁進(jìn)行插入和刪除操作，并且能夠快速查找最大元素？（）A.數(shù)組B.鏈表C.棧D.最大堆6、在一個棧中，若入棧序列為1,2,3,4，且在入棧過程中可以出棧，則可能得到的出棧序列有多少種？（）A.14B.15C.16D.177、在數(shù)據(jù)結(jié)構(gòu)中，使用并查集解決集合合并問題時，以下關(guān)于路徑壓縮的描述，錯誤的是（）A.可以提高查找效率B.不改變集合的關(guān)系C.增加了合并操作的復(fù)雜度D.使樹的高度降低8、在一個B樹中，每個節(jié)點的關(guān)鍵字?jǐn)?shù)量最少為多少？（）A.1B.2C.?m/2?-1D.m-19、在數(shù)據(jù)結(jié)構(gòu)中，對于線性表的順序存儲和鏈?zhǔn)酱鎯Γ韵抡f法正確的是：順序存儲結(jié)構(gòu)可以隨機訪問元素，但插入和刪除操作效率較低；鏈?zhǔn)酱鎯Y(jié)構(gòu)插入和刪除操作方便，但不能隨機訪問。那么在頻繁進(jìn)行插入和刪除操作的情況下，應(yīng)優(yōu)先選擇哪種存儲結(jié)構(gòu)？（）A.順序存儲B.鏈?zhǔn)酱鎯.兩者均可D.無法確定10、一棵完全二叉樹的第6層（根為第1層）有8個葉子節(jié)點，則該完全二叉樹的節(jié)點總數(shù)最多為（）。A.39B.56C.111D.11911、若要在一個已排序的數(shù)組中使用二分查找算法查找一個特定元素，以下關(guān)于時間復(fù)雜度的描述，哪一項是正確的？A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)12、在一個具有n個節(jié)點的完全二叉樹中，若節(jié)點編號從1開始，對于編號為i的節(jié)點，其雙親節(jié)點的編號是多少？A.i/2B.(i-1)/2C.(i+1)/2D.以上都不對13、對于一個具有n個元素的有序鏈表，若要在其中查找一個特定元素，其平均時間復(fù)雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)14、在一個字符串中，要查找某個子串首次出現(xiàn)的位置，通?？梢允褂媚姆N算法？（）A.冒泡排序B.快速排序C.順序查找D.二分查找15、已知一個具有n個頂點的無向圖采用鄰接矩陣存儲，若要刪除所有的邊，時間復(fù)雜度為？（）A.O(n)B.O(n2)C.O(nlogn)D.O(e)16、在一個具有n個節(jié)點的帶權(quán)有向圖中，若存在負(fù)權(quán)邊，以下哪種最短路徑算法可能不適用？A.迪杰斯特拉算法B.貝爾曼-福特算法C.弗洛伊德算法D.以上都適用17、對于一個具有n個頂點和e條邊的帶權(quán)有向圖，使用弗洛伊德（Floyd）算法求所有頂點對之間的最短路徑。以下關(guān)于該算法的時間復(fù)雜度的描述，哪一個是恰當(dāng)?shù)?？A.O(n)B.O(n^2)C.O(n^3)D.O(e^3)18、在一個哈希表中，若采用線性探測法解決哈希沖突，當(dāng)發(fā)生沖突時，新元素會存儲在什么位置？A.沖突位置的下一個位置B.沖突位置C.隨機位置D.以上都不對19、隊列也是一種常見的數(shù)據(jù)結(jié)構(gòu)，遵循先進(jìn)先出的原則。對于一個循環(huán)隊列，以下說法不正確的是（）A.隊頭指針和隊尾指針的移動需要考慮循環(huán)的情況B.當(dāng)隊頭指針等于隊尾指針時，隊列為空C.可以通過犧牲一個存儲單元來區(qū)分隊列空和隊列滿的情況D.循環(huán)隊列可以避免假溢出的問題20、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，有鄰接矩陣和鄰接表兩種存儲方式。對于一個稀疏圖，以下說法正確的是（）A.鄰接矩陣比鄰接表更節(jié)省存儲空間B.鄰接表更適合用于存儲和遍歷C.兩種存儲方式的時間復(fù)雜度相同D.稀疏圖的邊數(shù)很少，節(jié)點數(shù)很多二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋圖的生成樹是什么，以及如何找到一個圖的最小生成樹。2、（本題10分）對于一個用鏈表實現(xiàn)的棧，解釋其入棧和出棧操作的基本原理，并說明在什么情況下可能會出現(xiàn)棧溢出或棧下溢的情況。3、（本題10分）論述在二叉樹的遍歷中，如何利用線索二叉樹優(yōu)化遍歷效率。4、（本題10分）論述如何在一個帶權(quán)有向圖中計算源點到所