一、考點歸納?

1）排序

2、查找

3、復雜度

4、經典問題

0 - 1 背包	動態規劃	0 - 1 背包問題具有最優子結構性質和重疊子問題性質。通過動態規劃可以利用一個二維數組來記錄子問題的解，避免重復計算，從而高效地求解出背包能裝下的最大價值。
分數背包	貪心算法	分數背包問題具有貪心選擇性質，即通過每次選擇單位重量價值最大的物品放入背包，最終能得到全局最優解。因為物品可以分割，所以貪心策略有效。
鄰分背包	動態規劃	與 0 - 1 背包類似，鄰分背包也需要考慮不同物品組合下的最優解，通過動態規劃可以較好地處理這種組合優化問題，將問題分解為子問題并求解。
旅行商問題	動態規劃	動態規劃可以通過記錄已經訪問過的城市集合和當前所在城市來求解，但時間復雜度較高，對于大規模問題不適用。模擬退火、遺傳算法等近似算法可以在合理時間內得到近似最優解，適用于實際應用中的大規模問題。
矩陣鏈乘	動態規劃	矩陣鏈乘問題具有最優子結構性質，通過動態規劃可以將原問題分解為多個子問題，計算出子問題的最優解并存儲，避免重復計算，從而高效地確定矩陣鏈乘的最優計算順序，減少計算量。
最長公共子序列	動態規劃	最長公共子序列問題具有最優子結構性質和重疊子問題性質。通過動態規劃利用二維數組記錄兩個序列的子序列之間的最長公共子序列長度，從底向上計算，最終得到整個序列的最長公共子序列長度和具體序列。

5、加密

?二、刷題
1、采用冒泡排序算法對(49,38,65,97,76,13,27,49)進行非降序排序，兩趟后的序列為()
通過相鄰元素交換的方式，最值冒泡，排到隊尾
第一個泡 =》38,49,65,76,13,27,49,97
第二個泡 =》38,49,65,13,27,49,76,97

2、采用簡單選擇排序算法對序列(34,12,49,28,31,52,51,49)進行非降序排序，兩趟后的序列為()
①最值12，與首元素34交換=>[12,34,49,28,31,52,51,49]=> [12]、[34,49,28,31,52,51,49]
②最值28，與首元素34交換=>[12]、[28,49,34,31,52,51,49]=>[12,28] [49,34,31,52,51,49]

3、對于一個初始無序的關鍵字序列，在下面的排序方法中，()第一趟排序結束后，一定能將序列中的某個元素在最終有序序列中的位置確定下來? ?

①直接插入排序? ?②冒泡排序? ?③簡單選擇排序? ④堆排序? ⑤快速排序? ⑥歸并排序

關鍵詞最終有序序列中的位置=》這道題考察快速排序

以序列?[3, 2, 1]為例

①直接插入排序

整個序列會被劃分為已排序序列和待排序序列兩部分，將未排序數據插入到已排序序列的合適位置。? ? 初始已排序[3],待排序[2,1]? ? ?=>第一趟結束[2,3] , [1]? ? ? ? ? ? ? ? ? ? ? ? ? ? 否

②冒泡排序? ? ? ? ? ?是

③簡單選擇排序? ? 是

整個序列會被劃分為已排序序列和待排序序列兩部分，從待排序序列中找出最小的元素
初始已排序[],待排序[3,2,1]=》找出待排序的最值1? => 最值與第一個元素交換

=》[1,2,3]=》已排序[1],待排序[2,3]? ? ?

④堆排序? ? ? ? ? 是

因為堆排序屬于選擇排序，所以它符合條件

⑤快速排序? ? ? ? ?是

快速排序選擇一個基準元素，將序列分為兩部分，使得左邊部分的元素都小于等于基準元素，右邊部分的元素都大于等于基準元素。在第一趟排序結束后，基準元素就被放置到了它在最終有序序列中的正確位置。例如，對于序列?[3, 2, 1]，若選擇?3?為基準元素，第一趟排序后變為?[2, 1, 3]，基準元素?3?的最終位置確定了。

⑥歸并排序? ? ? ??否

歸并排序是將序列分成子序列，然后兩兩合并。在第一趟歸并時，將其看作是由單個元素組成的子序列，即[3]、2]、[1]，合并后得到[2,3]? [1]? ? ?

綜上，答案是②③④⑤。

4.1、對一組數據進行排序，要求排序算法的時間復雜度為O(nlogn),并要求排序是穩定的，則可采用（D 歸并排序）算法。
? ? ?對一組數據進行排序，要求排序算法的時間復雜度為O(nlogn),且空間復雜度為O(1)，則可采用（B 堆排序）算法。
A)直接插入排序? ? ? B)堆排序? ? ? ?C)快速排序? ? ? ? ? ? ? ?D)歸并排序

4.2、下列排序算法中占用輔助存儲空間最多的是(A)

A)歸并排序? ?? ? B) 快速排序? ? ? ?C) 堆排序? ? ? ? ? ? ? D)冒泡排序

4.3、(A)是穩定的排序算法
A)冒泡排序? ? ? ? B)快速排序? ? ? ? C)堆排序? ? ? ? D)簡單選擇排序
見第一張插圖

5、折半查找問題

①二分查找就是折半查找，因為有一個考點是折半查找屬于__分治__算法，如果題目出線二分查找，那就沒人會選錯了。
②在線性表L中進行二分(折半)查找，要求L順序存儲，元素有序排列
? ? ? 寫代碼的時候基于有序數組實現二分查找
?③考察二分查找生成二叉判定樹：“左子樹元素小于根節點元素，右子樹元素大于根節點元素” ? ?

?2023真題：折半查找等概率查找某個包含8個元素的有序表，查找成功的平均查找長度為？2.625

假設有序表為{a1, a2, a3, a4, a5, a6, a7, a8}

• 第一次折半，中間元素是a4,因為(1 + 8) /2 = 4，所以二叉判定樹的根節點是a4。
• 左子樹是{a1, a2, a3}，右子樹是{a5, a6, a7, a8}。
• 遞歸左子樹? (1+3)/2=2=>{a1},{a3}
• 遞歸右子樹? (5+8)/2=6=>{a5},{a7,a8}=>{a8}
• 
  二分查找生成的二叉判定樹屬于平衡二叉樹(樹中任意節點的左右子樹高度差的絕對值不超過 1，并且左右子樹也都是平衡二叉樹。)
  
  結點的高度代表查找長度(次數)，比如a4是1，因為第一次折半就是它，求總長度
  
  1*1+2*2+3*4+4*1=18
  
  =》平均長度? ?21/8 = 2.625
  ?

6、 采用貪心策略求解(A)問題，一定可以得到最優解
A)分數背包? ?B)0-1背包? ?C)旅行商? ?D)最長公共子序列
①貪心策略就是找最貴的。

• A. 分數背包：背包容量5kg，沙土A 3千克總價值100元，沙土B 6千克總價值100元，
  沙土A更貴，根據貪心策略，先把沙土A裝完，再裝沙土B。
• B. 0 - 1 背包：在 0 - 1 背包問題中，物品是不可分割的，要么取要么不取。
  背包容量1立方米，玉石原石A 0.4立方總價值100元，玉石原石B 1立方總價值200元，先把玉石原石A裝完，再裝原石B，裝不上=》只裝了100元，失敗
• C. 旅行商問題：該問題是要找出一個旅行商在訪問所有城市后回到起始城市的最短路徑。貪心策略可能會選擇當前距離最近的未訪問城市作為下一個目的地，但這種局部最優的選擇可能會導致錯過全局最優解。
  A->B=1,A->C=2,B->C=一百萬,C->A=2,C->B=3,B->A=5;
  由A開始，訪問所有城市后回到A，由貪心法得到A->B->C->A=一百多萬
  
  最短路徑實為A->C->B->A=10
• D. 最長公共子序列：求解最長公共子序列問題需要考慮兩個序列的整體結構和對應關系，不能簡單地通過貪心選擇來確定。例如，對于序列 “AGGTAB” 和 “GXTXAYB”，如果使用貪心策略，可能會先選擇第一個序列中的 “A”，但這樣會導致錯過更長的公共子序列 “GTAB”。所以貪心策略不適用于最長公共子序列問題。
  ?

7、在求解某問題時，經過分析發現該問題具有最優子結構和重疊子問題性質，則適用(C)算法設計策略得到最優解。
A)?分治? ? ? ? ??B)貪心? ? ? ? ?C)?動態規則? ? ? ? ?D)?回溯

若了解問題的解空間，并以廣度優先的方式搜索解空間，則采用的是(D)算法策略。
A)?動態規則? ? ? ? ??B)貪心? ? ? ? ?C) 回溯?? ? ? ? ?D)?分支界限?

動態規劃：最優子結構
貪心法：局部最優解
回溯法：深度優先
分支界限：廣度優先

8、利用報文摘要算法生成報文摘要的目的是(A)
A)防止發送的報文被篡改? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?報文摘要算法，如MD5
B)對傳輸數據進行加密，防止數據被竊聽? ? ? ? 隨便一個加密算法，如RSA
C)驗證通信對方的身份，防止假冒

對比項目	數字證書	數字簽名
概念	由證書頒發機構（CA）頒發的權威性電子文檔，用于證明證書持有者的身份和公鑰的合法性	使用發送者的私鑰對要發送的數據的摘要進行加密得到的信息
功能	提供身份驗證，確保通信雙方能確認對方身份的真實性和合法性	保證數據的完整性、認證發送者的身份以及防止抵賴
防止報文被篡改	本身不能直接防止報文被篡改，無法檢測和防止報文在傳輸過程中被篡改	可以通過驗證簽名來發現報文是否被篡改，因為報文篡改會導致摘要變化，使簽名驗證不通過
確認身份	用于確認擁有該證書的一方的身份，無論是服務器端還是客戶端	主要用于確認發送報文一方的身份，接收方通過發送方公鑰驗證簽名來確認發送者身份

D)防止發送方否認發送過的數據=》數字簽名

9、系統交付用戶使用了一段時間后發現，系統的某個功能響應非常慢。修改了某模塊的一個算法使其運算速度得到了提升，則該行為屬于(C)維護
A)改正性? ? ? 修改錯誤
B)適應性? ? ? 外部環境變化，比如屏幕變大
C)改善性? ? ??擴充功能、改善性能
D)預防性? ? ??系統監控與預警


至此完結，其他章節的選擇題沒有太多需要理解的東西，刷刷刷，要把大片的時間放到下午的大題上去。