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

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

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