GESP 202412 五級

你的姓名：

1. 下?關(guān)于鏈表和數(shù)組的描述，錯(cuò)誤的是（）。

A. 當(dāng)數(shù)據(jù)數(shù)量不確定時(shí)，為了應(yīng)對各種可能的情況需要申請?個(gè)較?的數(shù)組，可能浪費(fèi)空間；此時(shí)?鏈表?較合適，??可動態(tài)調(diào)整。B. 在鏈表中訪問節(jié)點(diǎn)的效率較低，時(shí)間復(fù)雜度為 O(n)。C. 鏈表插?和刪除元素效率較低，時(shí)間復(fù)雜度為 O(n)。D. 鏈表的節(jié)點(diǎn)在內(nèi)存中是分散存儲的，通過指針連在?起。

2. 在循環(huán)單鏈表中，節(jié)點(diǎn)的 next 指針指向下?個(gè)節(jié)點(diǎn)，最后?個(gè)節(jié)點(diǎn)的next 指針指向（）。

A. 當(dāng)前節(jié)點(diǎn)B. nullptrC. 第?個(gè)節(jié)點(diǎn)D. 上?個(gè)節(jié)點(diǎn)

3. 為了?便鏈表的增刪操作，?些算法?成?個(gè)虛擬頭節(jié)點(diǎn)，?便統(tǒng)?刪除頭節(jié)點(diǎn)和其他節(jié)點(diǎn)。下?代碼實(shí)現(xiàn)了刪除鏈表中值為val 的節(jié)點(diǎn)，橫線上應(yīng)填的最佳代碼是（）。

A. dummyHead->next = head; cur = dummyHead;B. dummyHead-＞next = head-＞next; cur = dummyHead;C. dummyHead->next = head; cur = dummyHead->next;D. dummyHead->next = head->next; cur = dummyHead->next;

4. 對下?兩個(gè)函數(shù)，說法錯(cuò)誤的是（）。

A. 兩個(gè)函數(shù)的實(shí)現(xiàn)的功能相同。B. fibA采?遞推?式。C. fibB采?的是遞歸?式。D. fibA時(shí)間復(fù)雜度為 O(n)，fibB的時(shí)間復(fù)雜度為 O(n*n)。

5. 兩塊長?形?地的長寬分別為24米和 36米，要將它們分成正?形的?塊，使得正?形的尺?盡可能?。?楊采?如下的輾轉(zhuǎn)相除函數(shù)gcd(24, 36) 來求正?形分塊的邊長，則函數(shù)gcd 調(diào)?順序?yàn)椋ǎ?div>

A. gcd(24, 36)、gcd(24, 12)、gcd(12, 0)B. gcd(24, 36)、gcd(12, 24)、gcd(0, 12)C. gcd(24, 36)、gcd(24, 12)D. gcd(24, 36)、gcd(12, 24)

6. 唯?分解定理表明，每個(gè)?于1的?然數(shù)可以唯?地寫成若?個(gè)質(zhì)數(shù)的乘積。下?函數(shù)將?然數(shù)n的所有質(zhì)因素找出來，橫線上能填寫的最佳代碼是（）。

A. for (int i = 3; i <= n; i ++)B. for (int i = 3; i * i <= n; i ++)C. for (int i = 3; i <= n; i += 2)D. for (int i = 3; i * i <= n; i += 2)

7. 下述代碼實(shí)現(xiàn)素?cái)?shù)表的埃拉托?尼(埃?)篩法，篩選出所有?于等于n的素?cái)?shù)。下?說法，正確的是（）。

A. 代碼的時(shí)間復(fù)雜度是B. 在標(biāo)記?素?cái)?shù)時(shí)，代碼從 i*i 開始，可以減少重復(fù)標(biāo)記。C. 代碼會輸出所有?于等于 n 的奇數(shù)。D. 調(diào)?函數(shù)sieve_Eratosthenes(10)，函數(shù)返回值的數(shù)組中包含的元素有:2, 3, 5, 7, 9。

8. 下述代碼實(shí)現(xiàn)素?cái)?shù)表的線性篩法，篩選出所有?于等于n的素?cái)?shù)。下?說法正確的是（）。

A. 線性篩的時(shí)間復(fù)雜度是 O(n)。B. 每個(gè)合數(shù)會被其所有的質(zhì)因?標(biāo)記?次。C. 線性篩和埃拉托?尼篩的實(shí)現(xiàn)思路完全相同。D. 以上都不對

9. 考慮以下C++代碼實(shí)現(xiàn)的快速排序算法，以下關(guān)于快速排序的說法，正確的是（）。

A. 快速排序通過遞歸對?問題進(jìn)?求解。B. 快速排序的最壞時(shí)間復(fù)雜度是 O(n logn)。C. 快速排序是?個(gè)穩(wěn)定的排序算法。D. 在最優(yōu)情況下，快速排序的時(shí)間復(fù)雜度是O(n)。

10. 下?關(guān)于歸并排序，描述正確的是（）。

A. 歸并排序是?個(gè)不穩(wěn)定的排序算法。B. 歸并排序的時(shí)間復(fù)雜度在最優(yōu)、最差和平均情況下都是 O(n logn)。C. 歸并排序需要額外的 O(1) 空間。D. 對于輸?數(shù)組 {12, 11, 13, 5, 6, 7}，代碼輸出結(jié)果為:7 6 5 13 12 11。

11. 給定?個(gè)長度為的有序數(shù)組nums，其中所有元素都是唯?的。下?的函數(shù)返回?cái)?shù)組中元素target的索引。關(guān)于上述函數(shù)，描述不正確的是（）。

A. 函數(shù)采??分查找，每次計(jì)算搜索當(dāng)前搜索區(qū)間的中點(diǎn)，然后根據(jù)中點(diǎn)的元素值排除?半搜索區(qū)間。B. 函數(shù)采?遞歸求解，每次問題的規(guī)模減??半。C. 遞歸的終?條件是中間元素的值等于target ，若數(shù)組中不包含該元素，遞歸不會終?。D. 算法的復(fù)雜度為 O(logn)

12. 給定?個(gè)長度為的有序數(shù)組 nums ，其中可能包含重復(fù)元素。下?的函數(shù)返回?cái)?shù)組中某個(gè)元素 target 的左邊界，若數(shù)組中不包含該元素，則返回?1。例如在數(shù)組 nums = [5,7,7,8,8,10] 中查找 target=8 ，函數(shù)返回8在數(shù)組中的左邊界的索引為3。則橫線上應(yīng)填寫的代碼為（）。

A. right = middle - 1;B. right = middle;C. right = middle + 1;D. 以上都不對

13. 假設(shè)有多個(gè)孩?，數(shù)組 g 保存所有孩?的胃?值。有多塊餅?，數(shù)組 s 保存所有餅?的尺?。?楊給孩?們發(fā)餅?，每個(gè)孩?最多只能給?塊餅?。餅?的尺??于等于孩?的胃?時(shí)，孩?才能得到滿?。?楊的?標(biāo)是盡可能滿?越多數(shù)量的孩?，因此打算采?貪?算法來找出能滿?的孩?的數(shù)?，則橫線上應(yīng)填寫的代碼為（）。

A. result++; index--;B. result--; index--;C. result--; index++;D. result++; index++;

14. 關(guān)于分治算法，以下說法中不正確的是（）。

A. 分治算法將問題分成?問題，然后分別解決?問題，最后合并結(jié)果。B. 歸并排序采?了分治思想。C. 快速排序采?了分治思想。D. 冒泡排序采?了分治思想。

15. 小楊編寫了?個(gè)如下的?精度減法函數(shù)，下?說法，正確的是（）。

A. 如果數(shù)組 a 表?的整數(shù)?于 b 表?的整數(shù)，代碼會正確返回?者的差為負(fù)數(shù)。B. 代碼假設(shè)輸?數(shù)字是以倒序存儲的，例如 500 存儲為 {0, 0, 5} 。C. 代碼的時(shí)間復(fù)雜度為 O( a.size() + b.size() )D. 當(dāng)減法結(jié)果為 0 時(shí)，結(jié)果數(shù)組仍然會存儲很多個(gè)元素 0。

第 1 題單鏈表只?持在表頭進(jìn)?插?和刪除操作。

對錯(cuò)

第 2 題線性篩相對于埃拉托斯特尼篩法，每個(gè)合數(shù)只會被它的最?質(zhì)因數(shù)篩去?次，因此效率更?。

對錯(cuò)

第 3 題任何?個(gè)?于1的?然數(shù)都可以分解成若?個(gè)不同的質(zhì)數(shù)的乘積，且分解?式是唯?的。

對錯(cuò)

第 4 題貪?算法通過每?步選擇當(dāng)前最優(yōu)解，從??定能獲得全局最優(yōu)解。

對錯(cuò)

第 5 題遞歸算法必須有?個(gè)明確的結(jié)束條件，否則會導(dǎo)致?限遞歸并可能引發(fā)棧溢出。

對錯(cuò)

第 6 題快速排序和歸并排序的平均時(shí)間復(fù)雜度均為 O(n logn)，且都是穩(wěn)定排序。

對錯(cuò)

第 7 題快速排序的時(shí)間復(fù)雜度總?插?排序的時(shí)間復(fù)雜度低。

對錯(cuò)

第 8 題 ?分查找僅適?于數(shù)組?不適合鏈表，因?yàn)?分查找需要跳躍式訪問元素，鏈表中執(zhí)?跳躍式訪問的效率低。

對錯(cuò)

第 9 題對有序數(shù)組{5,13,19,21,37,56,64,75,88,92,100} 進(jìn)??分查找，成功查找元素19 的?較次數(shù)是2。

對錯(cuò)

第 10 題遞歸函數(shù)每次調(diào)???時(shí)，系統(tǒng)都會為新開啟的函數(shù)分配內(nèi)存，以存儲局部變量、調(diào)?地址和其他信息等，導(dǎo)致遞歸通常?迭代更加耗費(fèi)內(nèi)存空間。

對錯(cuò)

3.1 奇妙數(shù)字

3.2 武器強(qiáng)化