河南科技大學(xué)《數(shù)據(jù)結(jié)構(gòu)課》2021-2022學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁河南科技大學(xué)

《數(shù)據(jù)結(jié)構(gòu)課》2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、以下關(guān)于二叉排序樹的描述，錯(cuò)誤的是：A.左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值B.右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值C.中序遍歷二叉排序樹可得到一個(gè)有序序列D.二叉排序樹的查找效率總是最高的2、以下哪種圖的遍歷算法可以用于判斷一個(gè)圖是否為連通圖？A.深度優(yōu)先遍歷B.廣度優(yōu)先遍歷C.兩者均可D.兩者均不可3、對于一個(gè)具有n個(gè)元素的無序數(shù)組，使用插入排序進(jìn)行排序，其最好情況下的時(shí)間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)4、在數(shù)據(jù)結(jié)構(gòu)中，跳表的索引層數(shù)是根據(jù)數(shù)據(jù)量動(dòng)態(tài)調(diào)整的，以下關(guān)于索引層數(shù)調(diào)整的描述，錯(cuò)誤的是（）A.當(dāng)數(shù)據(jù)量增加時(shí)，可能增加索引層數(shù)B.索引層數(shù)越多，查找效率越高C.調(diào)整索引層數(shù)的過程比較復(fù)雜D.索引層數(shù)的調(diào)整不會(huì)影響數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)5、對于一個(gè)具有n個(gè)元素的無序鏈表，若要對其進(jìn)行排序，以下哪種排序算法較為合適？（）A.冒泡排序B.快速排序C.插入排序D.選擇排序6、在一個(gè)有向無環(huán)圖中，進(jìn)行拓?fù)渑判虻慕Y(jié)果是唯一的嗎？A.一定唯一B.一定不唯一C.可能唯一，也可能不唯一D.以上都不對7、在一個(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)8、對于一個(gè)具有n個(gè)元素的有序數(shù)組，使用二分查找算法查找一個(gè)特定元素。以下關(guān)于二分查找的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)?？A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、隊(duì)列也是一種常見的數(shù)據(jù)結(jié)構(gòu)，遵循先進(jìn)先出的原則。對于一個(gè)循環(huán)隊(duì)列，以下說法不正確的是（）A.隊(duì)頭指針和隊(duì)尾指針的移動(dòng)需要考慮循環(huán)的情況B.當(dāng)隊(duì)頭指針等于隊(duì)尾指針時(shí)，隊(duì)列為空C.可以通過犧牲一個(gè)存儲(chǔ)單元來區(qū)分隊(duì)列空和隊(duì)列滿的情況D.循環(huán)隊(duì)列可以避免假溢出的問題10、在數(shù)據(jù)結(jié)構(gòu)中，伸展樹（SplayTree）通過自調(diào)整保持較好的性能，以下關(guān)于伸展樹的操作，不正確的是（）A.查找操作會(huì)將被查找的節(jié)點(diǎn)旋轉(zhuǎn)到根節(jié)點(diǎn)B.插入操作可能會(huì)引起多次旋轉(zhuǎn)C.伸展樹的平均性能較好D.伸展樹的空間復(fù)雜度較高11、對于一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖，其邊的數(shù)量為多少？（）A.n(n-1)/2B.n(n-1)C.n2D.2n12、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹中，若采用后序遍歷得到的節(jié)點(diǎn)序列是ABC，中序遍歷序列是BAC，則先序遍歷序列是什么？A.CABB.ABCC.ACBD.無法確定13、在一個(gè)具有n個(gè)元素的有序雙向鏈表中，若要在指定位置插入一個(gè)新元素，以下關(guān)于插入操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、對于一個(gè)用鏈表實(shí)現(xiàn)的棧，若要獲取棧中元素的個(gè)數(shù)，以下哪種方法效率較高？A.遍歷鏈表B.維護(hù)一個(gè)計(jì)數(shù)器C.以上效率相同D.以上都不對15、在數(shù)據(jù)結(jié)構(gòu)中，使用并查集解決集合合并問題時(shí)，以下關(guān)于路徑壓縮的描述，錯(cuò)誤的是（）A.可以提高查找效率B.不改變集合的關(guān)系C.增加了合并操作的復(fù)雜度D.使樹的高度降低16、在一個(gè)具有n個(gè)元素的順序存儲(chǔ)的線性表中，刪除第i個(gè)元素（1<=i<=n），需要移動(dòng)多少個(gè)元素？（）A.n-iB.iC.n-i+1D.n-i-117、以下關(guān)于平衡二叉樹旋轉(zhuǎn)調(diào)整的描述，正確的是：A.旋轉(zhuǎn)調(diào)整一定會(huì)改變樹的中序遍歷結(jié)果B.左旋操作是將右子樹變?yōu)楦?jié)點(diǎn)，原根節(jié)點(diǎn)變?yōu)樽笞庸?jié)點(diǎn)C.右旋操作是將左子樹變?yōu)楦?jié)點(diǎn)，原根節(jié)點(diǎn)變?yōu)橛易庸?jié)點(diǎn)D.平衡二叉樹不需要進(jìn)行旋轉(zhuǎn)調(diào)整18、已知一個(gè)哈希表的長度為11，哈希函數(shù)為H(key)=key%11，采用二次探測法處理沖突。若依次插入關(guān)鍵字15、38、61、84，則在查找關(guān)鍵字61時(shí)需要進(jìn)行幾次探測？（）A.1B.2C.3D.419、排序算法的穩(wěn)定性和時(shí)間復(fù)雜度可以用于選擇合適的排序算法，以下關(guān)于它們的說法中，錯(cuò)誤的是？（）A.穩(wěn)定性對于某些應(yīng)用場景非常重要，如對具有多個(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à)值。20、在一個(gè)具有n個(gè)元素的有序數(shù)組中進(jìn)行二分查找，其時(shí)間復(fù)雜度為？A.O(n)B.O(nlogn)C.O(logn)D.O(n^2)二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)闡述在利用二叉樹進(jìn)行中序線索化的過程中，如何建立線索和遍歷線索二叉樹，并給出具體的算法步驟和代碼實(shí)現(xiàn)。2、（本題10分）解釋數(shù)據(jù)結(jié)構(gòu)中棧的應(yīng)用場景，如逆波蘭表達(dá)式求值、表達(dá)式樹構(gòu)建等，并說明其原理。3、（本題10分）描述二叉樹的遍歷算法在二叉樹的節(jié)點(diǎn)屬性統(tǒng)計(jì)問題、樹的形態(tài)變化問題中的應(yīng)用。4、（本題10分）解釋什么是AVL樹，說明其