學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁鄭州大學(xué)

《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對(duì)于一個(gè)m行n列的二維數(shù)組，按行優(yōu)先存儲(chǔ)時(shí)，元素a[i][j]（0<=i<m,0<=j<n）的地址計(jì)算公式為：A.LOC(a[i][j])=LOC(a[0][0])+i*n+jB.LOC(a[i][j])=LOC(a[0][0])+j*m+iC.LOC(a[i][j])=LOC(a[0][0])+i*m+jD.LOC(a[i][j])=LOC(a[0][0])+j*n+i2、在一個(gè)具有n個(gè)元素的順序表中，刪除第i個(gè)元素（1<=i<=n），平均需要移動(dòng)的元素個(gè)數(shù)約為？A.n/2B.n-iC.iD.n-i+13、若對(duì)一棵二叉排序樹進(jìn)行中序遍歷，得到的節(jié)點(diǎn)序列是一個(gè)遞增序列，則該二叉排序樹（）。A.沒有左子樹B.沒有右子樹C.左子樹均為空D.右子樹均為空4、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的無向完全圖，其邊的數(shù)量為多少？A.n(n-1)/2B.n(n+1)/2C.n^2D.n^2/25、在一個(gè)具有n個(gè)元素的無序數(shù)組中，使用選擇排序進(jìn)行排序，其空間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)6、排序算法的穩(wěn)定性和時(shí)間復(fù)雜度可以用于選擇合適的排序算法，以下關(guān)于它們的說法中，錯(cuò)誤的是？（）A.穩(wěn)定性對(duì)于某些應(yīng)用場(chǎng)景非常重要，如對(duì)具有多個(gè)關(guān)鍵字的記錄進(jìn)行排序時(shí)。B.時(shí)間復(fù)雜度是衡量排序算法效率的重要指標(biāo)，不同的排序算法具有不同的時(shí)間復(fù)雜度。C.可以根據(jù)實(shí)際情況選擇穩(wěn)定的或不穩(wěn)定的排序算法，以及時(shí)間復(fù)雜度較低的排序算法。D.排序算法的穩(wěn)定性和時(shí)間復(fù)雜度只適用于理論研究，在實(shí)際應(yīng)用中沒有實(shí)際價(jià)值。7、對(duì)于一個(gè)具有n個(gè)元素的快速排序，每次劃分選取的基準(zhǔn)元素不同，對(duì)排序的時(shí)間復(fù)雜度有何影響？（）A.沒有影響B(tài).可能會(huì)提高C.可能會(huì)降低D.以上都不對(duì)8、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠方便地實(shí)現(xiàn)集合的交、并、差等運(yùn)算？（）A.二叉樹B.鏈表C.哈希表D.樹狀數(shù)組9、對(duì)于一個(gè)具有n個(gè)元素的堆排序，其空間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、在一個(gè)棧中，若入棧序列為1,2,3,4，且在入棧過程中可以出棧，則可能得到的出棧序列有多少種？（）A.14B.15C.16D.1711、在數(shù)據(jù)結(jié)構(gòu)中，雙向循環(huán)鏈表相較于單向鏈表，以下優(yōu)勢(shì)描述錯(cuò)誤的是（）A.可以方便地反向遍歷B.插入和刪除節(jié)點(diǎn)的操作更簡(jiǎn)單C.查找前一個(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度更低D.空間復(fù)雜度更低12、若一棵二叉樹的層次遍歷序列為ABCDEFGHI，則其可能的中序遍歷序列有多少種？（）A.1B.n!C.2^nD.不確定13、已知一個(gè)圖的鄰接表如下所示，則從頂點(diǎn)V1出發(fā)進(jìn)行廣度優(yōu)先遍歷，可能得到的頂點(diǎn)訪問序列是（）。V1:->V2->V3V2:->V4V3:->V4->V5V4:->V5V5:A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V4,V3,V5D.V1,V4,V2,V3,V514、在一個(gè)具有n個(gè)元素的堆中，進(jìn)行插入操作的時(shí)間復(fù)雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)15、在一個(gè)具有n個(gè)元素的無序數(shù)組中，使用冒泡排序進(jìn)行排序。以下關(guān)于冒泡排序的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.最好情況為O(n)，最壞情況為O(n^2)B.最好情況和最壞情況均為O(n)C.最好情況為O(nlogn)，最壞情況為O(n^2)D.最好情況和最壞情況均為O(n^2)16、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無向圖，若采用克魯斯卡爾（Kruskal）算法生成最小生成樹，其時(shí)間復(fù)雜度為？（）A.O(n2)B.O(eloge)C.O(nlogn)D.O(e2)17、對(duì)于一個(gè)具有n個(gè)元素的哈希表，負(fù)載因子越大，發(fā)生沖突的可能性如何變化？（）A.越大B.越小C.不變D.不確定18、在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，若存在從頂點(diǎn)i到頂點(diǎn)j的路徑，同時(shí)也存在從頂點(diǎn)j到頂點(diǎn)i的路徑，則該圖被稱為？（）A.強(qiáng)連通圖B.弱連通圖C.連通圖D.非連通圖19、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的有向圖，若采用鄰接矩陣存儲(chǔ)，判斷圖中是否存在從頂點(diǎn)i到頂點(diǎn)j的路徑的時(shí)間復(fù)雜度為？（）A.O(1)B.O(n)C.O(n2)D.O(logn)20、若一個(gè)棧的輸入序列為1,2,3,4,5，不可能得到的輸出序列是？（）A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,5二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋什么是拓?fù)渑判?，并說明其在項(xiàng)目管理等領(lǐng)域的應(yīng)用。2、（本題10分）深入分析在利用鏈表實(shí)現(xiàn)隊(duì)列時(shí)，如何解決假溢出問題，并說明其實(shí)現(xiàn)原理和代碼示例。3、（本題10分）在一個(gè)二叉樹中，如何判斷兩棵二叉樹是否相同？4、（本題10分）論述在動(dòng)態(tài)規(guī)劃的求解過程中，如何通過備忘錄