保定學(xué)院《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》2022-2023學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁(yè)，共3頁(yè)保定學(xué)院

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》2022-2023學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對(duì)于一個(gè)具有n個(gè)元素的堆排序，其空間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)2、已知一棵二叉樹的先序遍歷序列為ABC，中序遍歷序列為BAC，則該二叉樹的右子樹為空的條件是？（）A.A為根節(jié)點(diǎn)B.B為根節(jié)點(diǎn)C.C為根節(jié)點(diǎn)D.無(wú)法確定3、若一棵二叉樹的先序遍歷序列為ABC，中序遍歷序列為BAC，則該二叉樹的后序遍歷序列為？（）A.BCAB.CBAC.ABCD.ACB4、對(duì)于一個(gè)采用鏈?zhǔn)酱鎯?chǔ)的隊(duì)列，若隊(duì)頭指針和隊(duì)尾指針相同，則隊(duì)列的狀態(tài)為：A.隊(duì)空B.隊(duì)滿C.不確定D.隊(duì)列中只有一個(gè)元素5、對(duì)于單鏈表，若要訪問(wèn)鏈表中的第i個(gè)元素，必須從鏈表的頭指針開(kāi)始依次遍歷，平均時(shí)間復(fù)雜度為O(n)。那么如果要在鏈表的末尾添加一個(gè)新元素，時(shí)間復(fù)雜度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)6、AVL樹是一種高度平衡的二叉搜索樹，以下關(guān)于AVL樹的旋轉(zhuǎn)操作，描述不正確的是（）A.旋轉(zhuǎn)操作用于保持樹的平衡B.包括單旋轉(zhuǎn)和雙旋轉(zhuǎn)兩種類型C.旋轉(zhuǎn)操作不會(huì)改變二叉搜索樹的性質(zhì)D.每次插入或刪除節(jié)點(diǎn)都需要進(jìn)行旋轉(zhuǎn)操作7、在一個(gè)具有n個(gè)元素的無(wú)序鏈表中，若要對(duì)其進(jìn)行快速排序，以下關(guān)于快速排序的平均時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)8、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若其所有頂點(diǎn)的度之和為20，則該圖的邊數(shù)為（）。A.5B.10C.15D.209、在一個(gè)帶頭結(jié)點(diǎn)的單鏈表中，若要?jiǎng)h除表中所有值為x的結(jié)點(diǎn)，最優(yōu)的算法時(shí)間復(fù)雜度是？（）A.O(1)B.O(n)C.O(nlogn)D.O(n^2)10、在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，若每個(gè)頂點(diǎn)的度都為k，則邊的數(shù)量為多少？（）A.nk/2B.nkC.n(k-1)/2D.n(k-1)11、對(duì)于一個(gè)具有n個(gè)元素的無(wú)序數(shù)組，使用插入排序進(jìn)行排序，其最好情況下的時(shí)間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)12、設(shè)有一個(gè)字符串S="helloworld"，要計(jì)算字符串S的長(zhǎng)度（不包括結(jié)束符'\0'），以下函數(shù)正確的是？（）A.intlength(char*s){intcount=0;while(*s!='\0'){count++;s++;}returncount;}B.intlength(char*s){intcount=0;for(;*s!='\0';s++){count++;}returncount;}C.intlength(char*s){intcount=0;do{count++;s++;}while(*s!='\0');returncount;}D.intlength(char*s){intcount=0;while(s[count]!='\0'){count++;}returncount;}13、哈希表的性能取決于哈希函數(shù)的設(shè)計(jì)和沖突解決方法的選擇，以下關(guān)于它們的說(shuō)法中，錯(cuò)誤的是？（）A.好的哈希函數(shù)應(yīng)該具有均勻分布性、隨機(jī)性和高效性等特點(diǎn)。B.沖突解決方法的選擇應(yīng)該根據(jù)哈希表的大小、數(shù)據(jù)的特點(diǎn)和操作的頻率等因素來(lái)決定。C.哈希表的性能可以通過(guò)調(diào)整哈希函數(shù)和沖突解決方法來(lái)優(yōu)化。D.哈希表的性能只取決于哈希函數(shù)的設(shè)計(jì)，與沖突解決方法無(wú)關(guān)。14、在一個(gè)具有n個(gè)頂點(diǎn)和m條邊的有向圖中，使用弗洛伊德算法求所有頂點(diǎn)對(duì)之間的最短路徑，其時(shí)間復(fù)雜度為？A.O(n^2)B.O(n^3)C.O(mn)D.O(m^2)15、在一個(gè)具有n個(gè)元素的順序表中，若要將其逆置，以下關(guān)于操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是恰當(dāng)?shù)模緼.O(1)B.O(logn)C.O(n)D.O(nlogn)16、對(duì)于一個(gè)采用順序存儲(chǔ)的棧，若棧頂指針top等于-1時(shí)，表示：A.棧滿B.?？誄.棧中只有一個(gè)元素D.棧中至少有一個(gè)元素17、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，使用弗洛伊德（Floyd）算法求所有頂點(diǎn)對(duì)之間的最短路徑。以下關(guān)于該算法的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)?？A.O(n)B.O(n^2)C.O(n^3)D.O(e^3)18、以下關(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)整19、在數(shù)據(jù)結(jié)構(gòu)中，對(duì)于線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，以下說(shuō)法正確的是：順序存儲(chǔ)結(jié)構(gòu)可以隨機(jī)訪問(wèn)元素，但插入和刪除操作效率較低；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)插入和刪除操作方便，但不能隨機(jī)訪問(wèn)。那么在頻繁進(jìn)行插入和刪除操作的情況下，應(yīng)優(yōu)先選擇哪種存儲(chǔ)結(jié)構(gòu)？（）A.順序存儲(chǔ)B.鏈?zhǔn)酱鎯?chǔ)C.兩者均可D.無(wú)法確定20、若要從一個(gè)具有n個(gè)元素的有序單鏈表中刪除所有值重復(fù)的元素，使得鏈表中每個(gè)元素的值都不同，最優(yōu)的算法時(shí)間復(fù)雜度是？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）闡述并查集中如何處理大規(guī)模數(shù)據(jù)的合并和查詢操作。2、（本題10分）分析在字符串匹配中，如何結(jié)合多種算法提高匹配效率。3、（本題10分）論述在字符串匹配的模糊匹配中，如何實(shí)現(xiàn)近似匹配和相似度計(jì)算。4、（本題10分）在數(shù)據(jù)結(jié)構(gòu)中，闡述如何使用配對(duì)堆進(jìn)行優(yōu)先隊(duì)列操作，給出算法步驟和實(shí)現(xiàn)代碼，并分析其性能優(yōu)勢(shì)和適用場(chǎng)景。三、設(shè)計(jì)題（本