湖南工商大學(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、對(duì)于一個(gè)采用順序存儲(chǔ)結(jié)構(gòu)的完全二叉樹，若已知根節(jié)點(diǎn)在數(shù)組中的位置為1，則其第i個(gè)節(jié)點(diǎn)的左孩子節(jié)點(diǎn)在數(shù)組中的位置為？A.2iB.2i+1C.i*2D.i*2-12、已知一個(gè)哈希表的裝填因子為0.8，哈希函數(shù)為H(key)=key%11，采用線性探測(cè)法處理沖突。若依次插入關(guān)鍵字31、25、19、49、37、21、13、17，則在查找關(guān)鍵字19時(shí)需要進(jìn)行幾次比較？（）A.1B.2C.3D.43、在數(shù)據(jù)結(jié)構(gòu)中，棧是一種特殊的線性表，遵循先進(jìn)后出的原則。以下關(guān)于棧的操作，錯(cuò)誤的是（）A.入棧操作將元素添加到棧頂B.出棧操作取出并刪除棧頂元素C.可以在棧的任意位置進(jìn)行插入和刪除操作D.棧頂指針始終指向棧頂元素4、在一個(gè)用鏈表實(shí)現(xiàn)的棧中，若要獲取棧底元素的值，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)5、以下關(guān)于快速排序的描述，錯(cuò)誤的是：A.快速排序在平均情況下的時(shí)間復(fù)雜度為O(nlogn)B.快速排序是一種不穩(wěn)定的排序算法C.快速排序在最壞情況下的時(shí)間復(fù)雜度為O(n^2)D.快速排序不需要額外的存儲(chǔ)空間6、圖的存儲(chǔ)方式和遍歷方式可以用于解決很多實(shí)際問題，以下關(guān)于它們的應(yīng)用的說法中，錯(cuò)誤的是？（）A.圖的鄰接矩陣可以用于表示網(wǎng)絡(luò)中的連接關(guān)系，如社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等。B.圖的鄰接表可以用于表示稀疏圖，如地圖、電路圖等。C.圖的遍歷方式可以用于解決路徑規(guī)劃、網(wǎng)絡(luò)流問題和最小生成樹問題等。D.圖的存儲(chǔ)方式和遍歷方式只適用于理論研究，在實(shí)際應(yīng)用中沒有實(shí)際價(jià)值。7、鏈表是另一種常見的數(shù)據(jù)結(jié)構(gòu)，它由一系列節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針。以下關(guān)于鏈表的說法中，錯(cuò)誤的是？（）A.鏈表的插入和刪除操作比較方便，只需要修改指針即可。B.鏈表可以動(dòng)態(tài)地增長(zhǎng)和縮小，不像數(shù)組那樣受固定長(zhǎng)度的限制。C.鏈表的訪問速度比數(shù)組慢，因?yàn)樾枰闅v鏈表才能找到特定的元素。D.鏈表只能存儲(chǔ)整數(shù)類型的數(shù)據(jù)元素。8、對(duì)于一個(gè)具有n個(gè)元素的堆，進(jìn)行刪除操作并調(diào)整堆的時(shí)間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、在一個(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)10、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠在O(1)的時(shí)間復(fù)雜度內(nèi)實(shí)現(xiàn)元素的隨機(jī)訪問？（）A.鏈表B.隊(duì)列C.棧D.數(shù)組11、在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，若度為2的結(jié)點(diǎn)數(shù)為m，則葉子結(jié)點(diǎn)數(shù)為：A.n-mB.m+1C.(n+1)/2D.n-2m+112、在一個(gè)具有n個(gè)元素的大頂堆中，若要將堆頂元素與最后一個(gè)元素交換，然后調(diào)整堆，其時(shí)間復(fù)雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)13、堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，分為大頂堆和小頂堆。對(duì)于大頂堆，以下描述不正確的是（）A.根節(jié)點(diǎn)的值大于其左右子節(jié)點(diǎn)的值B.可以用于實(shí)現(xiàn)優(yōu)先隊(duì)列C.構(gòu)建大頂堆的時(shí)間復(fù)雜度為O(nlogn)D.每次刪除堆頂元素后，需要重新調(diào)整堆以保持大頂堆的性質(zhì)14、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹，其深度為（以2為底取對(duì)數(shù)，向下取整）加1。若已知節(jié)點(diǎn)個(gè)數(shù)為100，則其深度為多少？（）A.6B.7C.8D.915、數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型（ADT）可以用于提高代碼的可維護(hù)性和可擴(kuò)展性，以下關(guān)于它們的說法中，錯(cuò)誤的是？（）A.ADT使得數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)與使用分離，用戶只需要關(guān)心數(shù)據(jù)結(jié)構(gòu)的操作集合，而不需要關(guān)心其內(nèi)部實(shí)現(xiàn)。B.ADT可以用多種編程語言實(shí)現(xiàn)，不同的實(shí)現(xiàn)方式可能會(huì)有不同的性能和特點(diǎn)。C.ADT的操作集合應(yīng)該具有明確的語義和規(guī)范，以便用戶正確地使用數(shù)據(jù)結(jié)構(gòu)。D.ADT只適用于線性數(shù)據(jù)結(jié)構(gòu)，不適用于非線性數(shù)據(jù)結(jié)構(gòu)。16、設(shè)有一個(gè)用鏈表實(shí)現(xiàn)的雙向循環(huá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)17、在一個(gè)哈希表中，解決沖突的方法不包括：A.開放定址法B.再哈希法C.建立索引表D.鏈地址法18、哈希表是一種用于快速查找的數(shù)據(jù)結(jié)構(gòu)。在處理哈希沖突時(shí)，常用的方法有開放地址法和鏈地址法。以下關(guān)于這兩種方法的描述，哪一項(xiàng)是不準(zhǔn)確的？A.開放地址法會(huì)增加查找時(shí)間B.鏈地址法需要額外的指針空間C.開放地址法容易產(chǎn)生聚集現(xiàn)象D.鏈地址法的沖突解決更復(fù)雜19、設(shè)棧的初始狀態(tài)為空，元素1、2、3、4、5依次入棧，出棧序列不可能是？（）A.54321B.21543C.21345D.1543220、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的無向連通圖，其生成樹的邊數(shù)為（）A.n-1B.nC.n+1D.2n二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）論述如何使用動(dòng)態(tài)規(guī)劃算法解決最長(zhǎng)公共子序列問題，給出狀態(tài)轉(zhuǎn)移方程和代碼實(shí)現(xiàn)。2、（本題10分）論述如何使用回溯法解決組合總和問題。3、（本題10分）深入探討在一個(gè)具有n個(gè)元素的二叉搜索樹中，如何進(jìn)行樹的修改操作，如節(jié)點(diǎn)值的更新。4、（本題10分）論述如何使用計(jì)數(shù)排序?qū)μ囟l件下的數(shù)組進(jìn)行排序，給出算法