這篇就一直更新一些C++的選擇題和編程題了。

目錄

筆試題1

答案及解析1

筆試題2

答案及解析2

力扣編程題

88.?合并兩個(gè)有序數(shù)組

解析代碼

349.?兩個(gè)數(shù)組的交集

解析代碼

60.?排列序列

解析代碼

46.?全排列

解析代碼

本篇完。

---

筆試題1

1. 以下哪種STL容器中的對(duì)象是連續(xù)存儲(chǔ)的：()

A.list

B.vector

C.map

D.set

2.?STL中的一級(jí)容器有：（）

A.vector、deque、list、set、multiset、map、multimap

B.序列式容器、關(guān)聯(lián)式容器、容器適配器

C.set、multiset、map、multimap

D.vector、deque、list

3.?以下STL的容器存放的數(shù)據(jù)，哪個(gè)肯定是排好序的（）

A.vector

B.deque

C.list

D.map

4.?當(dāng)很頻繁地對(duì)序列中部進(jìn)行插入和刪除操作時(shí)，應(yīng)該選擇使用的容器是（）

A.vector

B.list

C.deque

D.stack

5.?下面有關(guān)vector和list的區(qū)別，描述錯(cuò)誤的是？ （）

A.vector擁有一段連續(xù)的內(nèi)存空間，因此支持隨機(jī)存取，如果需要高效的隨即存取

B.list擁有一段不連續(xù)的內(nèi)存空間，如果需要大量的插入和刪除，應(yīng)該使用list

C.vector<int>::iterator支持“+”、“+=”、“<”等操作符

D.list<int>::iterator則不支持“+”、“+=”、“<”等操作符運(yùn)算，但是支持了[ ]運(yùn)算符

6.?關(guān)于vector<>初始化問(wèn)題下面那個(gè)是非法的??（）

A.vector<string> sVec；

B.vector<vector<int>> ivvec;

C.vector<vector<string>> svvec( "hello");

7.?T是一個(gè)數(shù)據(jù)類(lèi)型，關(guān)于std::vector::at 和 std::vector::operator[] 描述正確的是： ()

A.at總是做邊界檢查， operator[] 不做邊界檢查

B.at不做邊界檢查， operator[] 做邊界檢查

C.at和operator[] 是一樣的

D.at下標(biāo)越界拋異常，operator[]下標(biāo)越界觸發(fā)斷言

8.?STL中的unordered_map和priority_queue使用的底層數(shù)據(jù)結(jié)構(gòu)分別是什么?()

A.rbtree,queue

B.hashtable,heap

C.rbtree,heap

D.hashtable,queue

9.?map和unordered_map的區(qū)別說(shuō)法錯(cuò)誤的是（）

A.map的底層是紅黑樹(shù)，unordered_map的底層結(jié)構(gòu)是哈希表

B.map是有序的，unordered_map不是，且map的查詢(xún)效率更高

C.map和unordered_map底層存儲(chǔ)的都是鍵值對(duì)

D.map和unordered_map的應(yīng)用場(chǎng)景不同

10.?下面關(guān)于deque說(shuō)法正確的是（）

A.deque沒(méi)有vector尾插效率高

B.deque的底層是一段連續(xù)空間

C.如果要對(duì)集合中的元素進(jìn)行排序時(shí)，元素不適合放在deque中

D.deque是priority_queue的底層默認(rèn)容器

答案及解析1

1. B

??A：錯(cuò)誤，list的底層結(jié)構(gòu)為帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，是鏈?zhǔn)浇Y(jié)構(gòu)

??B：正確，vector是動(dòng)態(tài)類(lèi)型順序表，底層是一段連續(xù)空間

??C：錯(cuò)誤，map底層是紅黑樹(shù)，樹(shù)形結(jié)構(gòu)

??D：錯(cuò)誤，set底層是紅黑樹(shù)，樹(shù)形結(jié)構(gòu)

2. D

??一級(jí)容器即序列式容器（存的不是）

??A：錯(cuò)誤，set、multiset、map、multimap是關(guān)聯(lián)式容器，不是序列式容器

??B：錯(cuò)誤，非題目所問(wèn)

??C：錯(cuò)誤，都是關(guān)聯(lián)式容器

??D：正確

3. D

map的底層是紅黑樹(shù)，紅黑樹(shù)是二叉搜索樹(shù)，二叉搜索樹(shù)中的元素如果按照中序遍歷，可以得到一個(gè)有序序列

4. B

頻繁的向序列中插入和刪除元素時(shí)，應(yīng)該選擇鏈?zhǔn)浇Y(jié)構(gòu)

list底層結(jié)構(gòu)為：帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表

5. C

??A：正確：構(gòu)造了一個(gè)空的vector，里面放置的是string類(lèi)型的對(duì)象

??B：正確：構(gòu)造了一個(gè)空的動(dòng)態(tài)二維數(shù)組

??C：錯(cuò)誤，svvec是二維的，vector套vector，不能直接使用"hello"構(gòu)造

6. C

??A：正確：構(gòu)造了一個(gè)空的vector，里面放置的是string類(lèi)型的對(duì)象

??B：正確：構(gòu)造了一個(gè)空的動(dòng)態(tài)二維數(shù)組

??C：錯(cuò)誤，svvec是二維的，vector套vector，不能直接使用"hello"構(gòu)造

7. D

??at和operator[]都是通過(guò)下標(biāo)獲取對(duì)應(yīng)的元素，兩個(gè)的不同是：

??at在下標(biāo)越界時(shí)，拋異常

??operator[]在下標(biāo)越界時(shí)，觸發(fā)斷言

8. B

unordered_map底層使用的是哈希表，priority_queue底層使用的是堆

9. B

??A：正確

??B：錯(cuò)誤，map底層是紅黑樹(shù)，查詢(xún)效率為O(logN)，unordered_map底層是哈希表，查詢(xún)效率為 O(1)，?unordered_map查詢(xún)的效率更高

??C：正確

??D：正確，map適合要求結(jié)果有序的常見(jiàn)，unordered_map適合是否有序無(wú)關(guān)，更關(guān)注查詢(xún)效率的場(chǎng)景

10. C

??A：錯(cuò)誤，如果在不擴(kuò)容的情況下deque和vector相同，需要擴(kuò)容時(shí)就不同了，vector擴(kuò)容需要搬移 大量的元素，deque不需要

??B：錯(cuò)誤，deque是分段連續(xù)的，類(lèi)似動(dòng)態(tài)的二維數(shù)組

??C：正確，因?yàn)橐判蚓托枰闅v，而deque不適合編譯，因?yàn)槠湓诒闅v時(shí)，要不斷的去檢測(cè)迭代 器是否在空間邊界

??D：錯(cuò)誤，priority_queue底層的默認(rèn)容器是vector

筆試題2

1. 下面關(guān)于適配器說(shuō)法正確的是（）

A.在STL中，stack和queue與vector一樣，都是容器

B.STL中只有容器適配器

C.適配器有自己獨(dú)立的底層數(shù)據(jù)結(jié)構(gòu)，不需要借助其他結(jié)構(gòu)

D.適配器是一種設(shè)計(jì)模式，該種模式是將一個(gè)接口包裝成客戶(hù)希望的另一個(gè)接口

2.?下面哪一個(gè)不是適配器（）

A.stack

B.queue

C.反向迭代器

D.以上都是

3.?關(guān)于仿函數(shù)說(shuō)法正確的是（）

A.仿函數(shù)就是一個(gè)函數(shù)

B.仿函數(shù)可以是靜態(tài)成員函數(shù)

C.仿函數(shù)是函數(shù)對(duì)象，可以像函數(shù)調(diào)用方式使用的對(duì)象

D.仿函數(shù)與函數(shù)指針作用不同

4.?關(guān)于仿函數(shù)說(shuō)法錯(cuò)誤的是（）

A.仿函數(shù)可以使算法功能更加靈活

B.如果想要讓一個(gè)類(lèi)的對(duì)象按照函數(shù)方式使用，只需在其中將（）重載即可

C.lambda表達(dá)式底層實(shí)際就是按照仿函數(shù)實(shí)現(xiàn)的

D.仿函數(shù)與函數(shù)指針都可以增加算法的靈活性

5. 填寫(xiě)下面空格

1. merge()算法的功能是：_______________________________________________

2. reverse()算法的功能是：_____________________________________________

3. unique()算法的功能是：______________________________________________

4. next_permutation()算法的功能是：____________________________________

5. sort()算法的功能是：_______________________________________________

答案及解析2

1. D

??A：錯(cuò)誤，在STL中stack和queue被認(rèn)為是容器適配器，因?yàn)樗鼈兊牡讓咏Y(jié)構(gòu)是直接將deque封裝 了一下

??B：錯(cuò)誤，除了容器適配器，還有迭代器適配器，函數(shù)適配器

??C：錯(cuò)誤，適配器沒(méi)有自己獨(dú)立的底層數(shù)據(jù)結(jié)構(gòu)，是將其他結(jié)構(gòu)拿過(guò)來(lái)重新包裝的

??D：正確，迭代器模式概念

2. D

??A：正確，stack是對(duì)deque的重新封裝

??B：正確，queue是對(duì)deque的重新封裝

??C：正確，反向迭代器失對(duì)正向迭代器的封裝

??D：錯(cuò)誤

3. C

??A：錯(cuò)誤，仿函數(shù)是一個(gè)類(lèi)中重載了()，該類(lèi)的對(duì)象可以像函數(shù)一樣使用的對(duì)象

??B：錯(cuò)誤，仿函數(shù)是依靠對(duì)象調(diào)用的，沒(méi)有對(duì)象無(wú)法使用，因?yàn)椴荒苁庆o態(tài)成員函數(shù)

??C：正確

??D：錯(cuò)誤，作用基本是類(lèi)似的，都是增加算法的靈活性，只不過(guò)C++中使用仿函數(shù)更多

4. B

A：正確，STL中的算法都是通用的，有些算法具體的做的事情需要用戶(hù)通過(guò)仿函數(shù)方式定制

B：錯(cuò)誤，是重載()而不是(]，注意看題

C：正確，lambda表達(dá)式編譯器在編譯時(shí)會(huì)在底層將其轉(zhuǎn)化為仿函數(shù)

D：正確

1. merge(first1， last1，first2，last2， resutl)算法的功能是：將兩個(gè)有序序列合并成一個(gè)序列保存到result中，合并好之后依然有序
2. reverse(first， last)算法的功能是：對(duì)[first, last)區(qū)間中的元素逆序
3. unique(first, last)算法的功能是：對(duì)[first, last)區(qū)間中的元素去重
4. next_permutation(first，last)算法的功能是：獲取當(dāng)前序列的下一個(gè)排列組合
5. sort(first，last)算法的功能是：對(duì)[first, last)區(qū)間中的元素排序，重載版本可以指定排升序還是降序

力扣編程題

88.?合并兩個(gè)有序數(shù)組

給你兩個(gè)按?非遞減順序?排列的整數(shù)數(shù)組?nums1?和?nums2，另有兩個(gè)整數(shù)?m?和?n?，分別表示?nums1?和?nums2?中的元素?cái)?shù)目。

請(qǐng)你?合并?nums2?到?nums1?中，使合并后的數(shù)組同樣按?非遞減順序?排列。

注意：最終，合并后數(shù)組不應(yīng)由函數(shù)返回，而是存儲(chǔ)在數(shù)組?nums1?中。為了應(yīng)對(duì)這種情況，nums1?的初始長(zhǎng)度為?m + n，其中前?m?個(gè)元素表示應(yīng)合并的元素，后?n?個(gè)元素為?0?，應(yīng)忽略。nums2?的長(zhǎng)度為?n?。

示例 1：

輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
解釋：需要合并 [1,2,3] 和 [2,5,6] 。
合并結(jié)果是 [1,2,2,3,5,6] ，其中斜體加粗標(biāo)注的為 nums1 中的元素。

示例 2：

輸入：nums1 = [1], m = 1, nums2 = [], n = 0
輸出：[1]
解釋：需要合并 [1] 和 [] 。
合并結(jié)果是 [1] 。

示例 3：

輸入：nums1 = [0], m = 0, nums2 = [1], n = 1
輸出：[1]
解釋：需要合并的數(shù)組是 [] 和 [1] 。
合并結(jié)果是 [1] 。
注意，因?yàn)?m = 0 ，所以 nums1 中沒(méi)有元素。nums1 中僅存的 0 僅僅是為了確保合并結(jié)果可以順利存放到 nums1 中。

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

解析代碼

C語(yǔ)言寫(xiě)過(guò)了，雙指針

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int end = m + n - 1; // 雙指針if(m == 0){nums1[0] = nums2[0];}while(n > 0 && m > 0){if(nums1[m-1] >= nums2[n-1]) // 小的放后面{nums1[end--] = nums1[m-1];m--;}else{nums1[end--] = nums2[n-1];n--;}}while(n > 0) // 第二個(gè)數(shù)組還有就拷貝過(guò)去{nums1[end--] = nums2[n-1];n--;}}
};

349.?兩個(gè)數(shù)組的交集

給定兩個(gè)數(shù)組?nums1?和?nums2?，返回?它們的交集?。輸出結(jié)果中的每個(gè)元素一定是?唯一?的。我們可以?不考慮輸出結(jié)果的順序?。

示例 1：

輸入：nums1 = [1,2,2,1], nums2 = [2,2]
輸出：[2]

示例 2：

輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出：[9,4]
解釋：[4,9] 也是可通過(guò)的

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

解析代碼

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set s1(nums1.begin(),nums1.end()); // 去重unordered_set s2(nums2.begin(),nums2.end());vector<int> retV;if(s1.size() <= s2.size()){for(const auto& e : s1){if(s2.find(e) != s2.end()){retV.push_back(e);}}}else{for(const auto& e : s2){if(s1.find(e) != s1.end()){retV.push_back(e);}}}return retV;}
};

60.?排列序列

給出集合?[1,2,3,...,n]，其所有元素共有?n!?種排列。

按大小順序列出所有排列情況，并一一標(biāo)記，當(dāng)?n = 3?時(shí), 所有排列如下：

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

給定?n?和?k，返回第?k?個(gè)排列。

示例 1：

輸入：n = 3, k = 3
輸出："213"

示例 2：

輸入：n = 4, k = 9
輸出："2314"

示例 3：

輸入：n = 3, k = 1
輸出："123"

提示：

• 1 <= n <= 9
• 1 <= k <= n!

解析代碼

這題是困難題，和下面一題一樣應(yīng)該不提倡用next_permutation的，但沒(méi)學(xué)高階算法就先這樣用了

next_permutation函數(shù)在頭文件<algorithm>中，作用是是生成給定序列的下一個(gè)較大排序，直到序列按降序排列為止。到這里還需要強(qiáng)調(diào)的一點(diǎn)是，如果你希望生成所有的排列方式，一定要先將序列按升序排列，這里可以與sort函數(shù)結(jié)合起來(lái)使用，先用sort升序排列，再調(diào)用next_permutation函數(shù)。

class Solution {
public:string getPermutation(int n, int k) {string str = string("123456789").substr(0,n);while(--k){next_permutation(str.begin(), str.end());}return str;}
};

46.?全排列

給定一個(gè)不含重復(fù)數(shù)字的數(shù)組?nums?，返回其?所有可能的全排列?。你可以?按任意順序?返回答案。

示例 1：

輸入：nums = [1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

輸入：nums = [0,1]
輸出：[[0,1],[1,0]]

示例 3：

輸入：nums = [1]
輸出：[[1]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums?中的所有整數(shù)?互不相同

解析代碼

提倡不用next_permutation的，但沒(méi)學(xué)高階算法就先這樣用了，先用sort升序排列

class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> vv;sort(nums.begin(), nums.end());do{vv.push_back(nums);}while(next_permutation(nums.begin(), nums.end()));return vv;}
};

本篇完。

C++到這基本介紹了，有時(shí)間可以回去復(fù)習(xí)復(fù)習(xí)，還有一兩篇關(guān)于多線(xiàn)程的問(wèn)題放到Linux操作系統(tǒng)之后再放出來(lái)了，到這C++也夠用了。

下一篇：零基礎(chǔ)Linux_1（前期準(zhǔn)備）Linux發(fā)展史和環(huán)境安裝。

下下篇：零基礎(chǔ)Linux_2（基本指令_上）目錄/文件的顯示跳轉(zhuǎn)創(chuàng)建刪除。