常州大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法分析》2022-2023學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁(yè)，共3頁(yè)常州大學(xué)

《數(shù)據(jù)結(jié)構(gòu)與算法分析》2022-2023學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)棧中，若入棧序列為1,2,3,4，且在入棧過(guò)程中可以出棧，則可能得到的出棧序列有多少種？（）A.14B.15C.16D.172、對(duì)于一棵具有n個(gè)節(jié)點(diǎn)的二叉搜索樹(shù)，其平均查找長(zhǎng)度的上限大約為？A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)3、在一個(gè)堆排序中，最大堆用于升序排序，最小堆用于降序排序。那么對(duì)于一個(gè)初始無(wú)序的數(shù)組，構(gòu)建最大堆的時(shí)間復(fù)雜度是多少？（）A.O(n)B.O(log?n)C.O(nlog?n)D.O(n2)4、在數(shù)據(jù)結(jié)構(gòu)中，紅黑樹(shù)的插入操作可能會(huì)導(dǎo)致樹(shù)的不平衡，需要進(jìn)行調(diào)整。以下關(guān)于調(diào)整過(guò)程的描述，不正確的是（）A.可能需要進(jìn)行顏色修改和旋轉(zhuǎn)操作B.調(diào)整后的紅黑樹(shù)仍然滿足紅黑樹(shù)的性質(zhì)C.調(diào)整的目的是使樹(shù)的高度盡量降低D.每次插入操作都需要進(jìn)行多次調(diào)整5、在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，邊的數(shù)量為？（）A.n(n-1)/2B.n(n-1)C.n2D.2n(n-1)6、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)，其深度為（以2為底取對(duì)數(shù)，向下取整）加1。若已知節(jié)點(diǎn)個(gè)數(shù)為100，則其深度為多少？（）A.6B.7C.8D.97、設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)锳、B、C、D、E，下列不可能的出棧序列是（）。A.EDCBAB.DECBAC.DCEABD.ABCDE8、在數(shù)據(jù)結(jié)構(gòu)中，哈弗曼編碼是一種用于數(shù)據(jù)壓縮的編碼方式，以下關(guān)于哈弗曼編碼的描述，錯(cuò)誤的是（）A.出現(xiàn)頻率高的字符編碼較短B.編碼是唯一的C.解碼過(guò)程簡(jiǎn)單D.對(duì)所有數(shù)據(jù)都能達(dá)到很好的壓縮效果9、在一個(gè)具有n個(gè)元素的循環(huán)鏈表中，查找第i個(gè)元素（1<=i<=n），平均需要遍歷的節(jié)點(diǎn)個(gè)數(shù)約為？A.n/2B.nC.2nD.n/410、在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若存在環(huán)，則使用拓?fù)渑判蛩惴〞?huì)？A.正常排序B.無(wú)法排序C.部分排序D.排序結(jié)果不確定11、圖的存儲(chǔ)方式和遍歷方式可以用于解決很多實(shí)際問(wèn)題，以下關(guān)于它們的應(yīng)用的說(shuō)法中，錯(cuò)誤的是？（）A.圖的鄰接矩陣可以用于表示網(wǎng)絡(luò)中的連接關(guān)系，如社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等。B.圖的鄰接表可以用于表示稀疏圖，如地圖、電路圖等。C.圖的遍歷方式可以用于解決路徑規(guī)劃、網(wǎng)絡(luò)流問(wèn)題和最小生成樹(shù)問(wèn)題等。D.圖的存儲(chǔ)方式和遍歷方式只適用于理論研究，在實(shí)際應(yīng)用中沒(méi)有實(shí)際價(jià)值。12、在一個(gè)具有n個(gè)元素的最大堆中，插入一個(gè)新元素后，為了恢復(fù)堆的性質(zhì)，需要進(jìn)行的調(diào)整操作的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)13、已知一個(gè)圖的鄰接表如下所示，則從頂點(diǎn)V1出發(fā)進(jìn)行廣度優(yōu)先遍歷，可能得到的頂點(diǎn)訪問(wèn)序列是（）。V1:->V2->V3V2:->V4V3:->V4->V5V4:->V5V5:A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V4,V3,V5D.V1,V4,V2,V3,V514、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向連通圖，其生成樹(shù)中邊的條數(shù)為（）。A.nB.n-1C.eD.e-115、圖的存儲(chǔ)方式和遍歷方式對(duì)圖的操作效率有很大影響，以下關(guān)于它們的說(shuō)法中，錯(cuò)誤的是？（）A.鄰接矩陣適合存儲(chǔ)稠密圖，查找邊的時(shí)間復(fù)雜度為O(1)，但空間復(fù)雜度較高。B.鄰接表適合存儲(chǔ)稀疏圖，插入邊和刪除邊的時(shí)間復(fù)雜度為O(1)，但查找邊的時(shí)間復(fù)雜度較高。C.深度優(yōu)先搜索和廣度優(yōu)先搜索是圖的兩種基本遍歷方式，它們的時(shí)間復(fù)雜度都為O(n+m)，其中n是頂點(diǎn)數(shù)，m是邊數(shù)。D.圖的存儲(chǔ)方式和遍歷方式一旦確定，就不能再改變，否則會(huì)影響圖的操作效率。16、在數(shù)據(jù)結(jié)構(gòu)中，使用隊(duì)列來(lái)實(shí)現(xiàn)廣度優(yōu)先遍歷圖，以下關(guān)于遍歷過(guò)程的描述，錯(cuò)誤的是（）A.從起始節(jié)點(diǎn)開(kāi)始入隊(duì)B.隊(duì)列為空時(shí)結(jié)束遍歷C.訪問(wèn)節(jié)點(diǎn)時(shí)將其未訪問(wèn)的鄰接節(jié)點(diǎn)入隊(duì)D.節(jié)點(diǎn)不會(huì)被重復(fù)訪問(wèn)17、已知一棵二叉樹(shù)的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA18、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)字符串的高效存儲(chǔ)和操作？（）A.二叉樹(shù)B.哈希表C.字符數(shù)組D.鏈表19、以下關(guān)于圖的存儲(chǔ)結(jié)構(gòu)的描述，哪一項(xiàng)是正確的？（）A.鄰接矩陣適合存儲(chǔ)稀疏圖B.鄰接表在存儲(chǔ)稠密圖時(shí)空間效率較高C.十字鏈表適合存儲(chǔ)有向圖D.以上都不正確20、若要在一個(gè)已排序的數(shù)組中使用二分查找算法查找一個(gè)特定元素，以下關(guān)于時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）深入分析在具有n個(gè)元素的有序鏈表中，如何進(jìn)行插入操作以保持鏈表的有序性，同時(shí)處理重復(fù)插入的情況。2、（本題10分）深入分析在一個(gè)具有n個(gè)元素的順序表中，如何使用二分查找算法來(lái)查找特定元素，并說(shuō)明其適用條件。3、（本題10分）詳細(xì)闡述在并查集的數(shù)據(jù)結(jié)構(gòu)改進(jìn)中，如何使用樹(shù)的高度或節(jié)點(diǎn)數(shù)量來(lái)優(yōu)化合并操作。4、（本題10分）在一個(gè)二叉搜索樹(shù)中，如何刪除一個(gè)具有兩個(gè)子樹(shù)的結(jié)