湖南財(cái)政經(jīng)濟(jì)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁(yè)，共3頁(yè)湖南財(cái)政經(jīng)濟(jì)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》

2021-2022學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹中，若采用中序遍歷得到的節(jié)點(diǎn)序列是有序的，則該二叉樹可能是什么類型？A.滿二叉樹B.完全二叉樹C.二叉搜索樹D.以上都有可能2、對(duì)于一個(gè)具有n個(gè)元素的順序存儲(chǔ)的循環(huán)隊(duì)列，隊(duì)尾指針rear指向隊(duì)尾元素的下一個(gè)位置，隊(duì)頭指針front指向隊(duì)頭元素，若隊(duì)列非空，則隊(duì)列中元素的個(gè)數(shù)為？（）A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+13、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無(wú)向圖，使用克魯斯卡爾（Kruskal）算法構(gòu)造最小生成樹，其時(shí)間復(fù)雜度主要取決于：A.邊數(shù)eB.頂點(diǎn)數(shù)nC.n和e的和D.n和e的乘積4、若要在一個(gè)具有n個(gè)元素的有序鏈表中插入一個(gè)新元素，使其仍然有序，平均時(shí)間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(nlog?n)5、若對(duì)線性表的操作只有兩種，即插入和刪除，且以鏈表作為存儲(chǔ)結(jié)構(gòu)，則插入和刪除操作的時(shí)間復(fù)雜度分別為：A.O(n)和O(n)B.O(1)和O(1)C.O(n)和O(1)D.O(1)和O(n)6、在一個(gè)具有n個(gè)元素的循環(huán)鏈表中，查找第i個(gè)元素（1<=i<=n），平均需要遍歷的節(jié)點(diǎn)個(gè)數(shù)約為？A.n/2B.nC.2nD.n/47、在數(shù)據(jù)結(jié)構(gòu)中，哈弗曼編碼是一種用于數(shù)據(jù)壓縮的編碼方式，以下關(guān)于哈弗曼編碼的描述，錯(cuò)誤的是（）A.出現(xiàn)頻率高的字符編碼較短B.編碼是唯一的C.解碼過(guò)程簡(jiǎn)單D.對(duì)所有數(shù)據(jù)都能達(dá)到很好的壓縮效果8、在一棵二叉搜索樹中，刪除一個(gè)有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)時(shí)，通常采用的方法是：A.用左子樹的最大值替代該節(jié)點(diǎn)B.用右子樹的最小值替代該節(jié)點(diǎn)C.隨機(jī)選擇左子樹或右子樹的節(jié)點(diǎn)替代D.不進(jìn)行替代，直接刪除9、在一個(gè)字符串中，要查找某個(gè)子串首次出現(xiàn)的位置，通?？梢允褂媚姆N算法？（）A.冒泡排序B.快速排序C.順序查找D.二分查找10、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若其所有頂點(diǎn)的度之和為20，則該圖的邊數(shù)為（）。A.5B.10C.15D.2011、若要對(duì)一組無(wú)序的整數(shù)進(jìn)行排序，使其最終變?yōu)橐粋€(gè)遞增的有序序列，以下哪種排序算法在平均情況下性能最優(yōu)？A.冒泡排序B.插入排序C.選擇排序D.希爾排序12、在一個(gè)具有n個(gè)元素的順序表中，在第i個(gè)元素（1<=i<=n）之前插入一個(gè)新元素時(shí)，需要向后移動(dòng)的元素個(gè)數(shù)為：A.n-iB.iC.n-i+1D.n-i-113、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)字符串的高效存儲(chǔ)和操作？（）A.二叉樹B.哈希表C.字符數(shù)組D.鏈表14、在一個(gè)長(zhǎng)度為n的有序數(shù)組中進(jìn)行二分查找，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(logn)D.O(n2)15、在一個(gè)有序的單鏈表中，若要?jiǎng)h除一個(gè)重復(fù)出現(xiàn)的元素，使得鏈表中不再有重復(fù)元素，應(yīng)如何操作？（）A.從頭遍歷，遇到重復(fù)元素就刪除B.從尾遍歷，遇到重復(fù)元素就刪除C.先排序，再刪除重復(fù)元素D.建立一個(gè)新鏈表，將不重復(fù)元素插入16、對(duì)于一個(gè)具有n個(gè)元素的堆，進(jìn)行插入操作的時(shí)間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)17、在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，若采用鄰接矩陣存儲(chǔ)，則矩陣中非零元素的個(gè)數(shù)至少為？（）A.nB.n-1C.2(n-1)D.n(n-1)/218、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列？A.鏈表B.隊(duì)列C.棧D.堆19、在一個(gè)用數(shù)組實(shí)現(xiàn)的小根堆中，若要插入一個(gè)元素，應(yīng)該將其插入到數(shù)組的哪個(gè)位置？A.數(shù)組末尾B.堆頂C.任意位置D.以上都不對(duì)20、棧和隊(duì)列的應(yīng)用場(chǎng)景非常廣泛，以下關(guān)于它們的應(yīng)用的說(shuō)法中，錯(cuò)誤的是？（）A.?？梢杂糜趯?shí)現(xiàn)函數(shù)調(diào)用、表達(dá)式求值和括號(hào)匹配等。B.隊(duì)列可以用于實(shí)現(xiàn)任務(wù)調(diào)度、消息隊(duì)列和廣度優(yōu)先搜索等。C.棧和隊(duì)列可以用于實(shí)現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。D.棧和隊(duì)列只適用于計(jì)算機(jī)科學(xué)領(lǐng)域，在其他領(lǐng)域沒(méi)有實(shí)際價(jià)值。二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）在一個(gè)二叉搜索樹中，如何實(shí)現(xiàn)查找第k大元素的操作？2、（本題10分）在一個(gè)循環(huán)隊(duì)列中，如何判斷隊(duì)列是空還是滿？請(qǐng)分別說(shuō)明具體的判斷條件和方法。3、（本題10分）詳細(xì)闡述在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，如何求關(guān)鍵路徑。4、（本題10分）闡述如何在一個(gè)具有n個(gè)元素的鏈表中，使用堆排序算法進(jìn)行排序，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。三、設(shè)計(jì)題（本大