石河子大學《數(shù)據(jù)結(jié)構(gòu)》2023-2024學年期末試卷

站名：站名：年級專業(yè)：姓名：學號：凡年級專業(yè)、姓名、學號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁石河子大學《數(shù)據(jù)結(jié)構(gòu)》

2023-2024學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個節(jié)點的帶權(quán)有向圖中，使用迪杰斯特拉算法求最短路徑，其時間復雜度是多少？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)2、對于一個具有n個元素的順序存儲的棧，若要判斷棧是否已滿，應判斷？（）A.top==n-1B.top==nC.top>=n-1D.top>=n3、在一個帶頭結(jié)點的雙向鏈表中，若要在p所指結(jié)點之后插入一個新結(jié)點q，需要修改幾個指針？（）A.2B.4C.6D.84、在一個循環(huán)鏈表中，若要刪除鏈表中的最后一個節(jié)點，需要的時間復雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)5、設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一個元素，其存儲地址為1，每個元素占一個存儲單元，則a85的地址為？（）A.33B.32C.18D.406、在一個具有n個元素的小根堆中，最小元素的值位于（）。A.根節(jié)點B.任意節(jié)點C.葉子節(jié)點D.無法確定7、對于一個具有n個頂點和m條邊的有向圖，使用鄰接表存儲，其入度和出度的計算時間復雜度分別為（）A.O(n)和O(m)B.O(m)和O(n)C.O(n+m)和O(n+m)D.O(n^2)和O(n^2)8、字符串匹配是數(shù)據(jù)結(jié)構(gòu)中的一個重要問題，KMP算法是一種高效的字符串匹配算法。關(guān)于KMP算法，以下描述錯誤的是（）A.通過利用已經(jīng)匹配的部分信息來提高匹配效率B.計算next數(shù)組是KMP算法的關(guān)鍵步驟C.KMP算法的時間復雜度為O(m+n)，其中m和n分別是主串和模式串的長度D.KMP算法在任何情況下都比暴力匹配算法快9、圖是一種復雜的數(shù)據(jù)結(jié)構(gòu)。在有向圖中，頂點的入度是指指向該頂點的邊的數(shù)量。若要計算一個有向圖中所有頂點的入度，哪種算法較為合適？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓撲排序D.以上都可以10、設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲其下三角部分，第一個元素A[1,1]存儲在數(shù)組B[0]中，若A[8,5]在數(shù)組B中的存儲位置為k，則A[7,5]在數(shù)組B中的存儲位置為（）。A.k-13B.k-12C.k-11D.k-1011、在一個鏈式存儲的棧中，若棧頂指針為top，要判斷棧是否為空，應判斷？（）A.top==NULLB.top->next==NULLC.top->data==NULLD.*top==NULL12、對于一個具有n個頂點的有向圖，若采用鄰接表表示，則所有鄰接表中的邊節(jié)點總數(shù)為（）。A.nB.n+1C.eD.2e13、在數(shù)據(jù)結(jié)構(gòu)中，塊狀鏈表結(jié)合了鏈表和數(shù)組的優(yōu)點，以下關(guān)于塊狀鏈表的特點，描述不正確的是（）A.適合頻繁的插入和刪除操作B.可以提高隨機訪問的效率C.每個塊內(nèi)部是有序的D.空間復雜度比普通鏈表低14、二叉樹的遍歷方式可以遞歸實現(xiàn)，也可以非遞歸實現(xiàn)，以下關(guān)于它們的說法中，錯誤的是？（）A.遞歸實現(xiàn)的二叉樹遍歷方式簡單直觀，但可能會導致棧溢出問題。B.非遞歸實現(xiàn)的二叉樹遍歷方式需要使用?；蜿犃衼磔o助實現(xiàn)。C.非遞歸實現(xiàn)的二叉樹遍歷方式比遞歸實現(xiàn)的效率更高。D.二叉樹的遍歷方式只能用遞歸或非遞歸方式實現(xiàn)，不能用其他方式實現(xiàn)。15、對于一個采用鏈表存儲的棧，若要獲取棧的大小（元素數(shù)量），以下關(guān)于操作的時間復雜度的描述，哪一個是準確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)16、對于一個具有n個元素的棧，若要實現(xiàn)將棧中元素逆置，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)為？（）A.隊列B.棧C.鏈表D.數(shù)組17、對于一棵二叉樹，先序遍歷序列為ABC，中序遍歷序列為BAC，則其后序遍歷序列為？A.BCAB.CBAC.ACBD.ABC18、對于一個具有n個元素的雙向循環(huán)鏈表，若要刪除第i個節(jié)點（1<=i<=n），平均需要修改多少個指針？（）A.2B.3C.4D.519、對于一個具有n個元素的有序單鏈表，要查找一個值為x的元素，平均比較次數(shù)約為？A.n/2B.nC.lognD.120、在一個具有n個元素的順序表中，若要查找一個元素，平均需要比較多少次？（）A.n/2B.nC.lognD.不確定二、簡答題（本大題共4個小題，共40分)1、（本題10分）鏈表的歸并排序有哪些步驟？請詳細描述其實現(xiàn)過程。2、（本題10分）深入分析在一個具有n個元素的順序表中，如何使用排序算法進行數(shù)據(jù)的逆序?qū)y(tǒng)計。3、（本題10分）深入分析在一個具有n個元素的順序表中，如何使用排序算法進行數(shù)據(jù)篩選，如找出大于某個值的所有元素。4、（本題10分）對于一個具有n個頂點的無向圖，如何使用廣度優(yōu)先搜索算法計算頂點的度？三、設(shè)計題（本大題共2個小題