站名：站名：年級(jí)專業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫、漏寫或字跡不清者，成績(jī)按零分記。…………密………………封………………線…………第1頁(yè)，共1頁(yè)常州工學(xué)院

《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、若要在一個(gè)具有n個(gè)元素的有序鏈表中插入一個(gè)新元素，使其仍然有序，平均時(shí)間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(nlog?n)2、對(duì)于一個(gè)采用鏈表存儲(chǔ)的隊(duì)列，若要?jiǎng)h除隊(duì)尾元素，以下關(guān)于操作的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)模緼.O(1)B.O(logn)C.O(n)D.O(nlogn)3、在一個(gè)具有n個(gè)元素的無序數(shù)組中，使用選擇排序進(jìn)行排序，其空間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)4、若要對(duì)一個(gè)已經(jīng)排好序的數(shù)組進(jìn)行二分查找，查找不成功時(shí)，最多需要比較多少次？（）A.lognB.logn-1C.logn+1D.n-15、棧是一種特殊的線性表，遵循先進(jìn)后出的原則。當(dāng)一個(gè)棧已滿，再進(jìn)行入棧操作時(shí)，通常會(huì)發(fā)生什么情況？A.覆蓋棧頂元素B.產(chǎn)生溢出錯(cuò)誤C.新建一個(gè)更大的棧D.自動(dòng)擴(kuò)展棧的容量6、在一個(gè)具有n個(gè)頂點(diǎn)和m條邊的有向圖中，使用弗洛伊德算法求所有頂點(diǎn)對(duì)之間的最短路徑，其時(shí)間復(fù)雜度為？A.O(n^2)B.O(n^3)C.O(mn)D.O(m^2)7、深度為5的滿二叉樹的結(jié)點(diǎn)數(shù)為：A.16B.31C.32D.158、對(duì)于一個(gè)棧，進(jìn)行入棧和出棧操作時(shí)，以下哪種情況會(huì)導(dǎo)致棧溢出？A.入棧元素過多B.出棧元素過多C.連續(xù)進(jìn)行入棧操作且存儲(chǔ)空間已滿D.連續(xù)進(jìn)行出棧操作且棧為空9、設(shè)有一個(gè)鏈棧，棧頂指針為top，若要在棧頂插入一個(gè)新元素，則需要執(zhí)行的操作是（）。A.s->next=top;top=s;B.top->next=s;top=s;C.s->next=top->next;top->next=s;D.top=s;s->next=NULL;10、設(shè)有一個(gè)具有n個(gè)頂點(diǎn)的有向圖，采用鄰接表存儲(chǔ)。若要計(jì)算每個(gè)頂點(diǎn)的出度，以下關(guān)于操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是恰當(dāng)?shù)?？A.O(n)B.O(n+e)C.O(n^2)D.O(e)11、若對(duì)一棵二叉搜索樹進(jìn)行先序遍歷，得到的節(jié)點(diǎn)序列是一個(gè)遞減序列，則該二叉搜索樹（）。A.沒有左子樹B.沒有右子樹C.左子樹均為空D.右子樹均為空12、若要在一個(gè)具有n個(gè)元素的有序數(shù)組中插入一個(gè)新元素，同時(shí)保持?jǐn)?shù)組有序，平均需要移動(dòng)多少個(gè)元素？（）A.n/2B.nC.lognD.113、對(duì)于一個(gè)具有n個(gè)元素的有序單鏈表，若要在其中查找一個(gè)特定元素，其平均時(shí)間復(fù)雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)14、在一個(gè)具有n個(gè)元素的順序存儲(chǔ)的線性表中，刪除第i個(gè)元素（1<=i<=n），需要移動(dòng)多少個(gè)元素？（）A.n-iB.iC.n-i+1D.n-i-115、以下哪種排序算法在元素基本有序的情況下性能最佳？A.快速排序B.冒泡排序C.插入排序D.堆排序16、以下關(guān)于快速排序的描述，錯(cuò)誤的是：A.快速排序在平均情況下的時(shí)間復(fù)雜度為O(nlogn)B.快速排序是一種不穩(wěn)定的排序算法C.快速排序在最壞情況下的時(shí)間復(fù)雜度為O(n^2)D.快速排序不需要額外的存儲(chǔ)空間17、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠在O(1)的時(shí)間復(fù)雜度內(nèi)實(shí)現(xiàn)元素的隨機(jī)訪問？（）A.鏈表B.隊(duì)列C.棧D.數(shù)組18、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)字符串的高效存儲(chǔ)和操作？（）A.二叉樹B.哈希表C.字符數(shù)組D.鏈表19、紅黑樹是一種自平衡的二叉搜索樹，具有嚴(yán)格的性質(zhì)。以下關(guān)于紅黑樹的描述，不正確的是（）A.節(jié)點(diǎn)要么是紅色，要么是黑色B.根節(jié)點(diǎn)一定是黑色C.從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的路徑上，黑色節(jié)點(diǎn)的數(shù)量相同D.紅黑樹的插入和刪除操作比平衡二叉樹簡(jiǎn)單20、對(duì)于一個(gè)具有n個(gè)元素的有序雙向鏈表，查找中間元素的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）深入解釋在鏈表中，如何實(shí)現(xiàn)頭插法和尾插法創(chuàng)建鏈表，并比較它們?cè)诓煌瑘?chǎng)景下的優(yōu)缺點(diǎn)。2、（本題10分）解釋在一個(gè)有向圖中如何判斷是否存在回路，以及如何使用拓?fù)渑判驅(qū)D進(jìn)行排序。3、（本題10分）詳細(xì)說明如何在一個(gè)有序鏈表中合并兩個(gè)有序鏈表，保持合并后的鏈表有序。4、（本題10分）闡述如何使用計(jì)數(shù)排序?qū)μ囟l件下的數(shù)據(jù)進(jìn)行排序，分析其優(yōu)缺點(diǎn)和適用場(chǎng)景。三、設(shè)計(jì)題（本