沈陽城市學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁沈陽城市學(xué)院

《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)具有n個(gè)元素的無序數(shù)組中，使用選擇排序進(jìn)行排序。以下關(guān)于選擇排序的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.最好情況為O(n)，最壞情況為O(n^2)B.最好情況和最壞情況均為O(n)C.最好情況為O(nlogn)，最壞情況為O(n^2)D.最好情況和最壞情況均為O(n^2)2、若一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EDCAB3、以下哪種數(shù)據(jù)結(jié)構(gòu)在處理頻繁的插入和刪除操作時(shí)，不需要移動(dòng)大量元素？（）A.數(shù)組B.鏈表C.棧D.隊(duì)列4、對于一個(gè)具有n個(gè)元素的哈希表，負(fù)載因子越大，發(fā)生沖突的可能性如何變化？（）A.越大B.越小C.不變D.不確定5、對于一個(gè)采用鏈?zhǔn)酱鎯?chǔ)的隊(duì)列，若隊(duì)頭指針和隊(duì)尾指針相同，則隊(duì)列的狀態(tài)為：A.隊(duì)空B.隊(duì)滿C.不確定D.隊(duì)列中只有一個(gè)元素6、在一個(gè)循環(huán)隊(duì)列中，若隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為MAXSIZE，則判斷隊(duì)滿的條件是？A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-1)%MAXSIZE==front7、對于一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹，若底層從左到右填充，則第i個(gè)節(jié)點(diǎn)的左孩子節(jié)點(diǎn)的編號為？A.2iB.2i+1C.i*2D.i*2+18、在一個(gè)具有n個(gè)元素的線性表中，采用順序查找法查找一個(gè)特定元素，若查找成功，平均查找長度為？（）A.(n+1)/2B.n/2C.lognD.n9、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹中，若每個(gè)節(jié)點(diǎn)都有左右孩子，則葉子節(jié)點(diǎn)的數(shù)量與度為2的節(jié)點(diǎn)數(shù)量有什么關(guān)系？A.葉子節(jié)點(diǎn)數(shù)量=度為2的節(jié)點(diǎn)數(shù)量+1B.葉子節(jié)點(diǎn)數(shù)量=度為2的節(jié)點(diǎn)數(shù)量-1C.葉子節(jié)點(diǎn)數(shù)量=度為2的節(jié)點(diǎn)數(shù)量D.以上都不對10、在一個(gè)具有n個(gè)元素的雙向鏈表中，若要?jiǎng)h除尾結(jié)點(diǎn)，需要修改幾個(gè)指針？（）A.1B.2C.3D.411、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹中，若采用后序遍歷得到的節(jié)點(diǎn)序列是ABC，中序遍歷序列是BAC，則先序遍歷序列是什么？A.CABB.ABCC.ACBD.無法確定12、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的線性表中，若要?jiǎng)h除第i個(gè)元素（1<=i<=n），需要找到其前驅(qū)節(jié)點(diǎn)的時(shí)間復(fù)雜度為？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)13、在一個(gè)長度為n的有序線性表中進(jìn)行二分查找，在最壞情況下，需要比較的次數(shù)為（）。A.O(n)B.O(n^2)C.O(log?n)D.O(nlog?n)14、對于一個(gè)具有n個(gè)節(jié)點(diǎn)的線索二叉樹，若n個(gè)節(jié)點(diǎn)中有m個(gè)空指針域，則線索的數(shù)量為？A.mB.m/2C.n+1D.n-115、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)優(yōu)先級隊(duì)列？A.鏈表B.隊(duì)列C.棧D.堆16、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)表達(dá)式求值？A.二叉樹B.棧C.隊(duì)列D.哈希表17、對于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣存儲(chǔ)，則存儲(chǔ)空間的復(fù)雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)18、在一個(gè)循環(huán)隊(duì)列中，隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為MAXSIZE，若rear>front，則隊(duì)列中的元素個(gè)數(shù)為？A.rear-frontB.rear-front+MAXSIZEC.rear-front-1D.(rear-front+MAXSIZE)%MAXSIZE19、對于一個(gè)有向無環(huán)圖，進(jìn)行拓?fù)渑判蚩梢缘玫揭粋€(gè)線性的序列。以下關(guān)于拓?fù)渑判虻恼f法，錯(cuò)誤的是？（）A.可以使用深度優(yōu)先搜索來實(shí)現(xiàn)B.結(jié)果可能不唯一C.若存在回路則無法進(jìn)行拓?fù)渑判駾.其時(shí)間復(fù)雜度為O(n2)20、對于一個(gè)具有n個(gè)元素的有序鏈表，進(jìn)行二分查找的時(shí)間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.不能進(jìn)行二分查找二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）說明二叉樹的遍歷算法在二叉樹的葉子節(jié)點(diǎn)之和問題、樹的直徑問題中的應(yīng)用。2、（本題10分）深入探討在一個(gè)具有n個(gè)元素的二叉搜索樹中，如何進(jìn)行插入操作的優(yōu)化。3、（本題10分）詳細(xì)說明如何在一個(gè)具有n個(gè)元素的堆中，進(jìn)行刪除操作，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。4、（本題10分）詳細(xì)解釋棧這種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)和操作，以及它在計(jì)算機(jī)程序中的常見應(yīng)用場景，比如表達(dá)式求值。三、設(shè)計(jì)題（本大