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