常州工學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷

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

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