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

《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)具有n個(gè)元素的隊(duì)列中，若要獲取隊(duì)頭元素的前一個(gè)元素但不刪除，以下操作不可行的是？（）A.遍歷整個(gè)隊(duì)列B.使用輔助數(shù)據(jù)結(jié)構(gòu)C.直接獲取D.以上都不可行2、在一個(gè)鏈隊(duì)列中，假設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，刪除隊(duì)頭元素的操作是：A.front=front->nextB.rear=rear->nextC.front->next=NULLD.rear->next=NULL3、設(shè)棧的初始狀態(tài)為空，元素1、2、3、4、5依次入棧，出棧序列不可能是？（）A.54321B.21543C.21345D.154324、跳表是一種基于鏈表的數(shù)據(jù)結(jié)構(gòu)，用于實(shí)現(xiàn)有序集合的快速查找。關(guān)于跳表的特點(diǎn)，以下描述錯(cuò)誤的是（）A.跳表的查找、插入和刪除操作的平均時(shí)間復(fù)雜度為O(logn)B.跳表通過(guò)增加索引層次來(lái)提高查找效率C.跳表的空間復(fù)雜度比普通鏈表高D.跳表的性能不如二叉搜索樹(shù)5、設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)存儲(chǔ)單元，則a85的地址為？（）A.33B.32C.18D.406、在一個(gè)有序表（12,24,36,48,60,72,84）中，使用二分查找法查找48，需要比較的次數(shù)是：A.1B.2C.3D.47、在一個(gè)順序存儲(chǔ)的棧中，若棧頂指針top為-1，則表示棧（）A.已滿B.為空C.已損壞D.無(wú)法確定8、以下哪種排序算法是穩(wěn)定的排序算法？A.快速排序B.選擇排序C.冒泡排序D.希爾排序9、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的棧中，若棧頂指針為top，要判斷棧是否為空，應(yīng)判斷？（）A.top==NULLB.top->next==NULLC.top->data==NULLD.*top==NULL10、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)，若按照層次遍歷的順序?qū)⒐?jié)點(diǎn)編號(hào)為1到n，已知編號(hào)為i的節(jié)點(diǎn)有左孩子，則其左孩子的編號(hào)為？A.2iB.2i+1C.i*2D.i/211、對(duì)于一個(gè)用鄰接矩陣存儲(chǔ)的圖，若要判斷兩個(gè)頂點(diǎn)之間是否存在邊，時(shí)間復(fù)雜度為？（）A.O(1)B.O(n)C.O(log?n)D.O(n2)12、在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度之和為m，入度之和為k，則m和k的關(guān)系是？（）A.m=kB.m>kC.m<kD.不確定13、對(duì)于一個(gè)具有n個(gè)元素的堆，進(jìn)行堆排序。以下關(guān)于堆排序的平均時(shí)間復(fù)雜度和空間復(fù)雜度的描述，哪一個(gè)是準(zhǔn)確的？A.平均時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(1)B.平均時(shí)間復(fù)雜度為O(n^2)，空間復(fù)雜度為O(n)C.平均時(shí)間復(fù)雜度為O(logn)，空間復(fù)雜度為O(logn)D.平均時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)14、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)有向圖，使用迪杰斯特拉算法求最短路徑，其時(shí)間復(fù)雜度為？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)15、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的AVL樹(shù)，插入一個(gè)新節(jié)點(diǎn)后，調(diào)整樹(shù)的平衡，其時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)16、在一個(gè)具有n個(gè)元素的有序鏈表中，若要查找第k個(gè)元素，以下關(guān)于查找操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(k)D.O(n)17、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠高效地支持區(qū)間查詢操作？（）A.線段樹(shù)B.二叉搜索樹(shù)C.堆D.鏈表18、在一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)中，若底層從左到右依次編號(hào)，節(jié)點(diǎn)i的左孩子節(jié)點(diǎn)編號(hào)是多少（假設(shè)根節(jié)點(diǎn)編號(hào)為1）？A.2iB.2i+1C.i*2D.以上都不對(duì)19、在一個(gè)具有n個(gè)節(jié)點(diǎn)的圖中，使用弗洛伊德算法求所有節(jié)點(diǎn)對(duì)之間的最短路徑，其時(shí)間復(fù)雜度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)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分）詳細(xì)闡述B樹(shù)在文件系統(tǒng)中的應(yīng)用和優(yōu)化策略。2、（本題10分）詳細(xì)闡述B樹(shù)的刪除操作中，兄弟節(jié)點(diǎn)借調(diào)元素的過(guò)程。3、（本題10分）對(duì)于一個(gè)用鏈表實(shí)現(xiàn)的隊(duì)列，如何實(shí)現(xiàn)循環(huán)隊(duì)列的功能，說(shuō)明其優(yōu)點(diǎn)和實(shí)現(xiàn)過(guò)程中的注意事項(xiàng)。4、（本題10分）詳細(xì)闡述棧和隊(duì)列這兩種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，舉例說(shuō)明它們?cè)趯?shí)際生活中的應(yīng)用場(chǎng)景，并分析其操作的時(shí)間復(fù)雜度。