樂山師范學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法分析》2022-2023學(xué)年期末試卷

學(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)與算法分析》2022-2023學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、一個(gè)有序序列為{12,18,24,35,47,50,62,83,90,115,134}，當(dāng)用二分法查找值為90的元素時(shí)，需要比較的次數(shù)是（）。A.1B.2C.3D.42、在數(shù)據(jù)結(jié)構(gòu)中，使用隊(duì)列來實(shí)現(xiàn)廣度優(yōu)先遍歷圖，以下關(guān)于遍歷過程的描述，錯(cuò)誤的是（）A.從起始節(jié)點(diǎn)開始入隊(duì)B.隊(duì)列為空時(shí)結(jié)束遍歷C.訪問節(jié)點(diǎn)時(shí)將其未訪問的鄰接節(jié)點(diǎn)入隊(duì)D.節(jié)點(diǎn)不會(huì)被重復(fù)訪問3、對(duì)于一個(gè)具有n個(gè)元素的小根堆，若要?jiǎng)h除堆頂元素并重新調(diào)整堆，以下關(guān)于操作的平均時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、在一個(gè)長(zhǎng)度為n的有序線性表中進(jìn)行二分查找，在最壞情況下，需要比較的次數(shù)為（）。A.O(n)B.O(n^2)C.O(log?n)D.O(nlog?n)5、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹中，若采用后序遍歷得到的節(jié)點(diǎn)序列是ABC，中序遍歷序列是BAC，則先序遍歷序列是什么？A.CABB.ABCC.ACBD.無法確定6、在一個(gè)具有n個(gè)元素的二叉排序樹中，查找一個(gè)不存在的元素，其時(shí)間復(fù)雜度最壞情況下為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)7、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣存儲(chǔ)，則存儲(chǔ)空間的復(fù)雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)8、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉排序樹中，刪除一個(gè)節(jié)點(diǎn)后，為了保持二叉排序樹的性質(zhì)，可能需要進(jìn)行哪些操作？A.僅調(diào)整刪除節(jié)點(diǎn)的子樹B.從根節(jié)點(diǎn)開始重新調(diào)整C.調(diào)整整個(gè)樹的結(jié)構(gòu)D.以上都有可能9、已知一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEABC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EACDB10、數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)中重要的基礎(chǔ)課程，它研究數(shù)據(jù)的組織、存儲(chǔ)和管理方式。以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的說法中，錯(cuò)誤的是？（）A.數(shù)據(jù)結(jié)構(gòu)可以分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。B.線性結(jié)構(gòu)包括數(shù)組、鏈表、棧和隊(duì)列等。C.非線性結(jié)構(gòu)包括樹、圖和集合等。D.數(shù)據(jù)結(jié)構(gòu)只與編程語言有關(guān)，與實(shí)際應(yīng)用場(chǎng)景無關(guān)。11、若哈希函數(shù)H(key)=key%7，要將關(guān)鍵字38插入到長(zhǎng)度為7的哈希表中，其存儲(chǔ)位置是：A.3B.5C.6D.012、在一個(gè)具有n個(gè)元素的順序表中，若要將其逆置，以下關(guān)于操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是恰當(dāng)?shù)?？A.O(1)B.O(logn)C.O(n)D.O(nlogn)13、二叉樹的遍歷方式可以遞歸實(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)。14、設(shè)有一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)無向圖，使用普里姆（Prim）算法求最小生成樹。在算法執(zhí)行過程中，需要選擇一個(gè)頂點(diǎn)作為起始點(diǎn)。以下關(guān)于起始點(diǎn)選擇對(duì)算法時(shí)間復(fù)雜度的影響，哪一個(gè)是恰當(dāng)?shù)?？A.起始點(diǎn)的選擇對(duì)時(shí)間復(fù)雜度沒有影響B(tài).選擇不同的起始點(diǎn)可能導(dǎo)致時(shí)間復(fù)雜度不同C.選擇頂點(diǎn)度最小的作為起始點(diǎn)可以降低時(shí)間復(fù)雜度D.選擇頂點(diǎn)度最大的作為起始點(diǎn)可以降低時(shí)間復(fù)雜度15、設(shè)有一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉搜索樹，若要查找一個(gè)值大于給定值的最小節(jié)點(diǎn)，以下關(guān)于查找操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)16、在一個(gè)具有n個(gè)元素的循環(huán)隊(duì)列中，若隊(duì)尾指針rear指向隊(duì)尾元素的下一個(gè)位置，隊(duì)頭指針front指向隊(duì)頭元素，則隊(duì)列中元素的個(gè)數(shù)為？A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+117、在數(shù)據(jù)結(jié)構(gòu)中，對(duì)于線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，以下說法正確的是：順序存儲(chǔ)結(jié)構(gòu)可以隨機(jī)訪問元素，但插入和刪除操作效率較低；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)插入和刪除操作方便，但不能隨機(jī)訪問。那么在頻繁進(jìn)行插入和刪除操作的情況下，應(yīng)優(yōu)先選擇哪種存儲(chǔ)結(jié)構(gòu)？（）A.順序存儲(chǔ)B.鏈?zhǔn)酱鎯?chǔ)C.兩者均可D.無法確定18、二叉樹的性質(zhì)和遍歷方式可以用于解決很多實(shí)際問題，以下關(guān)于它們的應(yīng)用的說法中，錯(cuò)誤的是？（）A.二叉搜索樹可以用于實(shí)現(xiàn)高效的查找、插入和刪除操作，適用于數(shù)據(jù)庫索引和文件系統(tǒng)等。B.平衡二叉樹可以用于解決二叉搜索樹的不平衡問題，提高查找效率，適用于大規(guī)模數(shù)據(jù)的存儲(chǔ)和管理。C.二叉樹的遍歷方式可以用于實(shí)現(xiàn)二叉樹的復(fù)制、遍歷和序列化等操作，適用于數(shù)據(jù)備份和傳輸?shù)取.二叉樹的性質(zhì)和遍歷方式只適用于理論研究，在實(shí)際應(yīng)用中沒有實(shí)際價(jià)值。19、對(duì)于一個(gè)具有n個(gè)元素的有序單鏈表，若要在其中查找一個(gè)特定元素，平均需要比較的次數(shù)為？（）A.n/2B.nC.lognD.nlogn20、在一個(gè)字符串中，要查找某個(gè)子串首次出現(xiàn)的位置，通?？梢允褂媚姆N算法？（）A.冒泡排序B.快速排序C.順序查找D.二分查找二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋如何在一個(gè)有序鏈表中查找中位數(shù)節(jié)點(diǎn)。2、（本題10分）分析在字符串匹配問題中，BM算法的特點(diǎn)和優(yōu)勢(shì)。3、（本題10分）解釋什么是左偏樹數(shù)據(jù)結(jié)構(gòu)，說明其特點(diǎn)和優(yōu)勢(shì)，并闡述如何進(jìn)行插入和刪除操作。4、（本題10分）深入解釋在具有n個(gè)元素的數(shù)組中，如