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

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

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