整合營銷服務(wù)商
電腦端+手機端+微信端=數(shù)據(jù)同步管理
免費咨詢熱線：
電腦端+手機端+微信端=數(shù)據(jù)同步管理
免費咨詢熱線：
.在C++中，下面哪個關(guān)鍵字用于聲明一個變量，其值不能被修改? ( )
A. unsigned
B. const
C. static
D. mutable
【答案】B
【考點】考點: C++語法知識: 變量與常量
【解析】變量是存儲信息的容器，變量在計算機內(nèi)有一個內(nèi)存地址，里面放的內(nèi)容即變量的值，變量是允許被修改，但是常量的值不允許被修改，常量的定義格式如下:
const 數(shù)據(jù)類型 常量名 = 常量值;
數(shù)據(jù)類型 const 常量名 = 常量值;
題目說其值不能被修改指的是常量，因此選擇 const 修飾，所以答案選擇 B。
2. 八進(jìn)制數(shù) 12345670 和 07654321 的和為 ( )
A. 22222221
B. 21111111
C. 22111111
D. 22222211
【答案】D
【考點】進(jìn)制轉(zhuǎn)換 (初賽集訓(xùn)內(nèi)容)
【解析】R 進(jìn)制的運算逢 R 進(jìn)一，題目是八進(jìn)制加法，所以每一個進(jìn)制位上的數(shù)字是逢 8 進(jìn)一。
12345670
+ 07654321
--------------
22222211
3. 閱讀下述代碼，請問修改 data 的 value 成員以存儲 3.14，正確的方式是( )
union Data{
int num;
float value;
char symbol;
};
union Data data;A. data.value = 3.14;
B. value.data = 3.14;
C. data->value = 3.14;
D. value->data = 3.14;
【答案】A
【考點】聯(lián)合體(NOI新大綱內(nèi)容)
【解析】共用體定義格式:
union 共用體名{
成員列表
};共用體的所有成員占用同一段內(nèi)存，修改一個成員會影響其余所有成員。
共用體占用的內(nèi)存等于最長的成員占用的內(nèi)存。
共用體使用了內(nèi)存覆蓋技術(shù)，同一時刻只能保存一個成員的值，如果對新的成員賦值，就會把原來成員的值覆蓋掉。
題目中 data 占用 4 個字節(jié)，修改 value 使用 . 運算符，-> 適用于指針。
4. 假設(shè)有一個鏈表的節(jié)點定義如下：
struct Node { int data; Node* next;};現(xiàn)在有一個指向鏈表頭部的指針：Node* head。如果想要在鏈表中插入一個新節(jié)點，其成員 data 的值為 42，并使新節(jié)點成為鏈表的第一個節(jié)點，下面哪個操作是正確的? ( )
A. Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
B. Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
C. Node* newNode = new Node; newNode->data = 42; head->next = newNode;
D. Node* newNode = new Node; newNode->data = 42; newNode->next = head;【答案】A
【考點】鏈表的插入(數(shù)據(jù)結(jié)構(gòu))
【解析】題目使用頭插法即可
B. 賦值錯誤。
C. 新插入的結(jié)點的后繼未確認(rèn)。
D. 表頭結(jié)點的后繼未指向新生成的結(jié)點。
5. 根節(jié)點的高度為 1，一根擁有 2023 個節(jié)點的三叉樹高度至少為 ( )
A. 6
B. 7
C. 8
D. 9
【答案】C
【考點】樹
【解析】觀察下圖
第 1 層有 1 個結(jié)點
第 2 層有 3 個結(jié)點
第 3 層有 27 個結(jié)點
......
第 n 層有 3n 個結(jié)點
根據(jù)性質(zhì)知道是一個等比數(shù)列，公比為 3，根據(jù)等比數(shù)列求和公式:
計算過程如下:
6. 小明在某一天中依次有七個空閑時間段，他想要選出至少一個空閑時間段來練習(xí)唱歌，但他希望任意兩個練習(xí)的時間段之間都有至少兩個空閑的時間段讓他休息，則小明一共有（ ）種選擇時間段的方案。
A. 31
B. 18
C. 21
D. 33
【答案】B
【考點】枚舉法
【解析】枚舉的方法講解
① 只有一個練習(xí)時間段的情況
② 只有兩個練習(xí)時間段的情況
③ 只有三個練習(xí)時間段的情況
7. 以下關(guān)于高精度運算的說法錯誤的是( )
A. 高精度計算主要是用來處理大整數(shù)或需要保留多位小數(shù)的運算
B. 大整數(shù)除以小整數(shù)的處理的步驟可以是，將被除數(shù)和除數(shù)對齊，從左到右逐位嘗試將除數(shù)乘以某個數(shù)，通過減法得到新的被除數(shù)，并累加商
C. 高精度乘法的運算時間只與參與運算的兩個整數(shù)中長度較長者的位數(shù)有關(guān)。
D. 高精度加法運算的關(guān)鍵在于逐位相加并處理進(jìn)位。
【答案】C
【考點】高精度運算
【解析】高精度乘法的時間取決于兩個大整數(shù)的長度的乘積有關(guān)，高精度乘低精度 O(n) 的時間復(fù)雜度，高精度乘高精度 O(n*n) 的時間復(fù)雜度。
8. 后綴表達(dá)式“6 2 3 + - 3 8 2 / + * 2 ^ 3 +”對應(yīng)的中綴表達(dá)式是 ( )
A. ((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3
B. 6 - 2 + 3 * 3 + 8 / 2 ^ 2 + 3
C. (6 - (2 + 3)) * ((3 + 8 / 2) ^ 2) + 3
D. 6 - ((2 + 3) * (3 + 8 / 2)) ^ 2 + 3
【答案】A
【考點】棧的應(yīng)用
【解析】首先 6，2，3 入棧，遇到第一個操作符 +，彈出 2 和 3 執(zhí)行加法，然后將 2 + 3 的結(jié)果入棧，遇到操作符 -，彈出兩個數(shù) 6 和 (2 + 3) 執(zhí)行減法，然后將 (6 - (2 + 3)) 的結(jié)果入棧，3，8，2 依次入棧，遇到操作符 /，彈出 2 和 8 執(zhí)行除法，然后將 8/2 入棧，遇到操作符 +，彈出 8/2 和 3 執(zhí)行加法，然后將 (3 + 8/2) 入棧，遇到操作符 *，彈出 (6 - (2 + 3)) 和 (3 + 8/2) 執(zhí)行乘法，然后將 (6-(2 + 3))*(3 + 8/2) 入棧，然后 2 入棧，遇到操作符 ^ 彈出 2 和 (6-(2 + 3))*(3 + 8/2) 執(zhí)行異或操作，然后將 (6-(2 + 3))*(3 + 8/2)^2 入棧，然后 3 入棧，遇到操作符 +，然后彈出 3 和 (6-(2 + 3))*(3 + 8/2)^2 執(zhí)行加法，然后將 (6-(2 + 3))*(3 + 8/2)^2 + 3 入棧，所以最終結(jié)果選 A。
9. 二進(jìn)制數(shù) 101010 和 八進(jìn)制數(shù) 166 的和為( )
A. 二進(jìn)制數(shù) 10110000
B. 八進(jìn)制數(shù) 236
C. 十進(jìn)制數(shù) 158
D. 十六進(jìn)制數(shù) A0
【答案】D
【考點】進(jìn)制轉(zhuǎn)換
【解析】先將二進(jìn)制數(shù)和八進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制
160 轉(zhuǎn)換成16進(jìn)制是 A0，八進(jìn)制是 240，二進(jìn)制數(shù)是 10100000。
10. 假設(shè)有一組字符 {a,b,c,d,e,f}，對應(yīng)的頻率分別為 5%，9%，12%，13%，16%，45%。請問以下哪個選項是字符 a, b, c, d, e, f分別對應(yīng)的一組哈夫曼編碼？( )
A. 1111，1110，101，100，110，0
B. 1010，1001，1000，011，010，00
C. 000，001，010，011，10，11
D. 1010，1011，110，111，00，01
【答案】A
【考點】哈夫曼編碼/霍夫曼編碼
【解析】記住要點: 霍夫曼編碼左 0 右 1，哈夫曼編碼的形態(tài)不唯一，但是 WPL 一定是唯一的，哈夫曼樹的形態(tài)如下:
哈夫曼樹的形態(tài)不唯一，但是結(jié)點到根節(jié)點的路徑的長度一定是唯一的，路徑的長度是唯一的所以 WPL 是唯一，備考北化刷王道數(shù)據(jù)結(jié)構(gòu)以前刷到過類似的題目hhh。合并的策略一定是選擇 n 個結(jié)點中最小的兩個結(jié)點進(jìn)行合并，然后再將合并的結(jié)果放入合并的集合中。B、C、D 選可以從路徑上排除，這個題比較好 。
11. 給定一棵二叉樹，其前序遍歷結(jié)果為：ABDECFG，中序遍歷結(jié)果為：DEBACFG。請問這棵樹的正確后序遍歷結(jié)果是什么？( )
A. EDBGFCA
B. EDGBFCA
C. DEBGFCA
D. DBEGFCA
【答案】A
【考點】樹的遍歷
【解析】前序遍歷順序: 根左右 中序遍歷順序: 左根右
后序遍歷: 左右根 ==> EDBGFCA。
12. 考慮一個有向無環(huán)圖，該圖包括4條有向邊：(1,2)，(1,3)，(2,4)，和(3,4)。以下哪個選項是這個有向無環(huán)圖的一個有效的拓?fù)渑判颍? )
A. 4，2，3，1
B. 1，2，3，4
C. 1，2，4，3
D. 2，1，3，4
【答案】B
【考點】拓?fù)渑判?、有向圖
【解析】有向圖如下所示
拓?fù)渑判? 度為 0 的點從圖中去掉。率先去掉 1 號點，(1,2)，(1,3) 這兩條邊去掉，度為 0 的點是 2 和 3，可以是 2 這個點先去掉，也可以是 3 這個點去掉，最后去掉 4 這個點，所以拓?fù)湫蛄惺? 1, 2, 3, 4 或者 1, 3, 2, 4。
13. 在計算機中，以下哪個選項描述的數(shù)據(jù)存儲容量最??？( )
A. 字節(jié)（byte）
B. 比特（bit）
C. 字（word）
D. 千字節(jié)（kilobyte）
【答案】B
【考點】數(shù)據(jù)存儲
【解析】數(shù)據(jù)存儲的基本單位: 字節(jié)(Byte)，數(shù)據(jù)的最小存儲單元: 比特(bit)。
1 Byte = 8 bit。
14. 一個班級有10個男生和12個女生。如果要選出一個3人的小組，并且小組中必須至少包含1個女生，那么有多少種可能的組合？（ )
A. 1420
B. 1770
C. 1540
D. 2200
【答案】A
【考點】排列組合
【解析】
① 一個女生，2 個男生
② 兩個女生，1 個男生
③ 三個女生
最終方案數(shù): 540 + 660 + 220 = 1420。
15. 以下哪個不是操作系統(tǒng)？( )
A. Linux
B. Windows
C. Android
D. HTML
【答案】D
【考點】操作系統(tǒng)
【解析】HTML 前端三劍客之一，超文本標(biāo)記語言。
第二部分 程序閱讀
程序閱讀
程序閱讀 ①
01 #include<iostream>
02 #include<cmath>
03 using namespace std;
04
05 double f(double a,double b,double c){
06 double s=(a+b+c)/2;
07 return sqrt(s*(s-a)*(s-b)*(s-c));
08 }
09
10 int main(){
11 cout.flags(ios::fixed);
12 cout.precision(4);
13
14 int a,b,c;
15 cin>>a>>b>>c;
16 cout<<f(a,b,c)<<endl;
17 return 0;
18 }假設(shè)輸入的所有數(shù)都為不超過1000的正整數(shù)，完成下面的判斷題和單選題：
16. （2分）當(dāng)輸入為“2 2 2”時，輸出為“1.7321”( )
【答案】?
【解析】a = 2, b = 2, c = 2, s = 3, 計算結(jié)果如下
17. （2分）將第7行中的"（s-b）*（s-c）"改為"（s-c）*（s-b）"不會影響程序運行的結(jié)果( )
【答案】?
【解析】乘法交換率 = a*b = b*a，所以交換后結(jié)果并不會發(fā)送變化。
18. （2分）程序總是輸出四位小數(shù)( )
【答案】?
【解析】cou.precision(4): 保留四位小數(shù)輸出。
19. （3分）當(dāng)輸入為“3 4 5”時，輸出為( )
A. 6.0000
B. 12.0000
C. 24.0000
D. 30.0000
【答案】A
【解析】a = 3, b = 4, c = 5, s = 6，根據(jù)海倫－秦九韶公式知代碼求三角形面積，根據(jù) a, b, c 的關(guān)系得知是直角三角形，所以面積為 6，故選 A。
20. （3分）當(dāng)輸入為“5 12 13”時，輸出為( )
A. 24.0000
B. 30.0000
C. 60.0000
D. 120.0000
【答案】B
【解析】a = 5, b = 12, c = 13，根據(jù)海倫－秦九韶公式知代碼求三角形面積，根據(jù) a, b, c 的關(guān)系得知是直角三角形，所以面積為 30，故選 B。
點評: 第一道題送分題 12 分應(yīng)該拿滿分，語法簡單題，未拿到滿分的同學(xué)應(yīng)該好好進(jìn)行自我反思為什么語法難度的閱讀題會丟分。
程序閱讀 ②
01 #include<iostream>
02 #include<vector>
03 #include<algorithm>
04 using namespace std;
05
06 int f(string x,string y){
07 int m=x.size();
08 int n=y.size();
09 vector<vector<int>>v(m+1,vector<int>(n+1,0));
10 for(int i=1;i<=m;i++){
11 for(int j=1;j<=n;j++){
12 if(x[i-1]==y[j-1]){
13 v[i][j]=v[i-1][j-1]+1;
14 }else{
15 v[i][j]=max(v[i-1][j],v[i][j-1]);
16 }
17 }
18 }
19 return v[m][n];
20 }
21
22 bool g(string x,string y){
23 if(x.size() != y.size()){
24 return false;
25 }
26 return f(x+x,y)==y.size();
27 }
28
29 int main(){
30 string x,y;
31 cin>>x>>y;
32 cout<<g(x,y)<<endl;
33 return 0;
34 }21. （1.5分）f函數(shù)的返回值小于等于min（n,m）。( )
【答案】?
【解析】f 函數(shù)是一個典型的最長公共子序列模型，屬于動態(tài)規(guī)劃里面的內(nèi)容
v[i][j]: 表示字符串 1 前 i 個字符和字符串 2 前 j 個字符，屬性值表示共有的子序列，狀態(tài)轉(zhuǎn)移方程如下
所以 f 函數(shù)最終的返回值應(yīng)該小于等于兩個字符串中最小的那個長度。
22. （1.5分） f函數(shù)的返回值等于兩個輸入字符串的最長公共子串的長度。( )
【答案】?
【解析】子串: 要求連續(xù); 子序列: 要求不連續(xù)，f 函數(shù)求的是最長公共子序列。
23. （1.5分）當(dāng)輸入兩個完全相同的字符串時，g函數(shù)的返回值總是true( )
【答案】?
【解析】f 函數(shù)的返回值是字符串的長度，所以 f(x+x, y) = y.size() 是恒成立，所以 g 函數(shù)的返回值總是 true。
24. （3分）將第19行中的“v[m][n]”替換為“v[n][m]”，那么該程序( )
A. 行為不變
B. 只會改變輸出
C. 一定非正常退出
D. 可能非正常退出
【答案】D
【解析】當(dāng)字符串 x 和 字符串 y 長度相等的情況情況不變，所以排除 B 和 C，當(dāng)字符串 x 的長度大于或者小于字符串長度 y 導(dǎo)致數(shù)組越界訪問，可能導(dǎo)致程序異常終止。
25. （3分）當(dāng)輸入為“csp-j p-jcs”時，輸出為: ( )
A. 0
B. 1
C. T
D. F
【答案】B
【解析】csp-jcsp-j p-jcs，f 函數(shù)的返回值是 5，和 p-jcs 長度相等，g 函數(shù)返回 true，bool 類型的輸出 true 自動轉(zhuǎn)化成 1。
26. （3分）當(dāng)輸入為“csppsc spsccp”時，輸出為: ( )
A. T
B. F
C. 0
D. 1
【答案】D
【解析】csppsccsppsc spsccp，f 函數(shù)的返回值是 6，和 spsccp 長度相等，g 函數(shù)返回 true，bool 類型的輸出 true 自動轉(zhuǎn)化成 1。
點評: 第二道題 f 函數(shù)考察同學(xué)們對于動態(tài)規(guī)劃學(xué)習(xí)的檢驗。
程序閱讀 ③
01 #include <iostream>
02 #include <cmath>
03 using namespace std;
04
05 int solve1(int n){
06 return n*n;
07 }
08
09 int solve2(int n){
10 int sum=0;
11 for(int i=1;i<=sqrt(n);i++){
12 if(n%i==0){
13 if(n/i==i){
14 sum+=i*i;
15 }else{
16 sum+=i*i+(n/i)*(n/i);
17 }
18 }
19 }
20 return sum;
21 }
22
23 int main(){
24 int n;
25 cin>>n;
26 cout<<solve2(solve1(n))<<" "<<solve1((solve2(n)))<<endl;
27 return 0;
28 }27. （1.5分）如果輸入的n為正整數(shù)，solve2函數(shù)的作用是計算n所有的因子的平方和 ( )
【答案】?
【解析】solve2 函數(shù)代碼解析如下:
28. （1.5分） 第13~14行的作用是避免n的平方根因子i（或n/i）進(jìn)入第16行而被計算兩次 ( )
【答案】?
【解析】平方數(shù) n 中出現(xiàn) i 是 n 的因子時，必然 n/i 和 i 相同，同一個因子出現(xiàn)兩次但是計算只計算一次，所以該判斷題敘述正確。
29. （1.5分）如果輸入的n為質(zhì)數(shù)，solve2（n）的返回值為n2+1 ( )
【答案】?
【解析】循環(huán)枚舉 i 是從 1 開始枚舉，質(zhì)數(shù)的定義除了 1 和它本身外沒有其余的因子，所以 sum = n*n + 1*1，所以敘述正確。
30. （4分）如果輸入的n為質(zhì)數(shù) p 的平方，那么 solve2（n）的返回值為( )
A. p2+p+1
B. n2+n+1
C. n2+1
D. P4+2p2+1
【答案】B
【解析】n 的因子有 1, p, n，sum 統(tǒng)計的是 n*n + p*p + 1*1，題目說 n 是質(zhì)數(shù) p 的平方，那么 p*p = n，等價替換返回值等于 n*n + n + 1 或者 p*p*p*p + p*p + 1，兩個答案的變形都算正確，所以最終選 B。
31. （3分）當(dāng)輸入為正整數(shù)時，第一項減去第二項的差值一定 ( )
A. 大于0
B. 大于等于0且不一定大于0
C. 小于0
D. 小于等于0且不一定小于0
【答案】D
【解析】特殊代值法排除，當(dāng) n 為 1 時 solve2(solve1(n))-solve1((solve2(n)))結(jié)果都為 0，因為模擬計算后發(fā)現(xiàn)都為 1，所以排除 A、C 兩個選項；代入一個值 n為 3 的情況，solve1(3) = 9，solve2(9) = 1*1 + 9*9 + 3*3 = 91，solve2(3) = 1*1 + 3*3 = 10，solve1(10) = 100，91 - 100 = -9，所以選 D，暑期集訓(xùn)說過這種結(jié)論題一般代值大概率能找出正確答案，算是做題技巧。
32. （3分） 當(dāng)輸入為“5”時，輸出為 ( )
A. 651 625
B. 650 729
C. 651 676
D. 652 625
【答案】C
【解析】solve1(5) = 25，solve2(25) = 1*1 + 5*5 + 25*25 = 651。
solve2(5) = 1*1 + 5*5 = 26，solve1(26) = 26*26 = 676。
點評: 數(shù)學(xué)知識因數(shù)分解。
第三部分 程序完善
程序完善
(1)(尋找被移除的元素)問題:原有長度為 n+1 公差為 1 等升數(shù)列，將數(shù)列輸?shù)匠绦虻臄?shù)組時移除了一個元素，導(dǎo)致長度為 n 的開序數(shù)組可能不再連續(xù)，除非被移除的是第一個或最后之個元素。需要在數(shù)組不連續(xù)時，找出被移除的元素。試補全程序。
01 #include <iostream>
02 #include <vector>
03
04 using namespace std;
05
06 int find missing(vector<int>& nums){
07 int left = 0, right = nums.size() - 1;
08 while (left < right){
09 int mid = left + (right left) / 2;
10 if (nums[mid] = mid + ①){
11 ②;
12 }else{
13 ③
14 }
15 }
16 return ④;
17 }
18
19 int main(){
20 int n;
21 cin >> n;
22 vector<int> nums(n);
23 for (int i= 0; i< n; i++) cin >> nums[i];
24 int missing_number = find_missing(nums);
25 if_(missing_number == ⑤) {
26 cout << "Sequence is consecutive" << endl;
27 }else{
28 cout << "Missing number is " << ,missing numbeer << endl;
29 }
30 return 0;
31 }二分適用條件: ① 區(qū)間單調(diào)性 ② 二分的答案滿足單調(diào)性
單調(diào)遞增區(qū)間查找 >= x 的最小值
int Find_L(int n, int num){ // n 表示 n 個數(shù), num 查詢的數(shù)
int L = 0, R = n-1; // L:左端點, R:右端點
while(L < R){
int mid = (L+R)>>1; //中間點
if(a[mid] >= num) R = mid; //左子區(qū)間
else L = mid + 1; //右子區(qū)間
}
return L; //二分的 >= num 的最小值
}單調(diào)遞增區(qū)間查找 <= x 的最大值
int Find_R(int n, int num){ //n:n個元素,num:查詢值
int L = 0, R = n - 1; //L:左端點 R:右端點
while(L < R){
int mid = (L + R + 1)/2; //中間點
if(a[mid] <= num) L = mid; //右區(qū)間
else R = mid - 1; //左區(qū)間
}
return R; // 二分 <= num 的最大值
}33. ① 處應(yīng)填( )
A. 1
B. nums[0]
C. right
D. left
【答案】B
【解析】等差數(shù)列公差 1 說明原序列具有連續(xù)性，連續(xù)必然滿足 nums[0] + mid == nums[mid]，不連續(xù) nums[mid] 必然大于 nums[0] + mid。
34. ②處應(yīng)填( )
A. left=mid+1
B. right=mid-1
C. right=mid
D. left=mid
【答案】A
【解析】當(dāng) if 成立說明左區(qū)間連續(xù)，答案必然在右區(qū)間 [mid+1, right] ，通過不斷調(diào)整左指針 left 和右指針 right 來確定答案處于哪個區(qū)間，因此需要將 left 修改成 mid+1。
35. ③處應(yīng)填( )
A. left=mid+1
B. right=mid-1
C. right=mid
D. left=mid
【答案】C
【解析】if 不成立答案處于左區(qū)間 [left, mid]，只需要修改指針 right = mid。
36. ④處應(yīng)填( )
A. left+nums[0]
B. right+nums[0]
C. mid+nums[0
D. right+1
【答案】A
【解析】返回的是被刪除的數(shù)，被刪除的數(shù)即不連續(xù)的位置 + 起始值。
37. ⑤處應(yīng)填( )
A. nums[0]+n
B. nums[0]+n-1
C. nums[0]+n+1
D. nums[n-1]
【答案】D
【解析】如果 n 個數(shù)連續(xù)， left = right = n-1，返回的數(shù)必然是序列中的最后一個數(shù)，反之則返回的數(shù)即是被刪除的數(shù)。
這個題大多數(shù)認(rèn)真學(xué)的同學(xué)都是滿分，注意認(rèn)真學(xué)并不是說上課聽講，而是自己課后自己動手去模擬過二分的過程，聽老師講懂了和自己動手驗證老師上課講的內(nèi)容記憶會更加深刻。
②(編輯距離) 給定兩個字符串，每次操作可以選擇刪除 (Delete)、插入 (Insert)、替換 (Replace)，一個字符，求將第一個字符串轉(zhuǎn)換為第二個字符串所需要的最少操作次數(shù)。
1.#include <iostream>
2.#include <string>
3.#include <vector>
4.using namespace std;
5.
6.int min(int x,int y,int z){
7. return min(min(x,y),z);
8.}
9.
10.int edit_dist_dp(string str1,string str2){
11. int m=str1.length();
12. int n=str2.length();
13. vector<vector<int>> dp(m+1,vector<int>(n+1));
14.
15. for(int i=0;i<=m;i++){
16. for(int j=0;j<=n;j++){
17. if(i==0)
18. dp[i][j]= ①;
19. else if(j==0)
20. dp[i][j]= ②;
21. else if(③)
22. dp[i][j]= ④;
23. else
24. dp[i][j]=1+min(dp[i][j-1],min(dp[i-1][j],⑤));
25. }
26. }
27. return dp[m][n];
28.}
29.
30.int main(){
31. string str1,str2;
32. cin>>str1>>str2;
33. cout<<"Mininum number of operation:"
34. <<edit_dist_dp(str1,str2)<<endl;
35. return 0;
36.}一、狀態(tài)表示：dp[i][j]
1. 集合：將 str1[1~i] 和 str2[1~j] 匹配的操作數(shù)量的集合
2. 屬性：最少操作次數(shù)
二、狀態(tài)計算：
1. 思想-----集合的劃分
2. 集合劃分依據(jù)：根據(jù)最后一步進(jìn)行劃分
刪除操作：dp[i][0] = i;
插入操作：dp[0][i] = i;
3. 具體劃分為3類：
1. 增加：dp[i][j] = dp[i, j - 1] + 1
2. 刪除：dp[i][j] = dp[i - 1, j] + 1
3. 修改：dp[i][j] = dp[i - 1, j - 1] + 1 (str1[i] != str2[j])
4. 匹配：dp[i][j] = dp[i - 1][j - 1] (str1[i] == str2[j])
38. ① 處應(yīng)填( )
A. j
B. i
C. m
D. n
【答案】A
【解析】第一個字符串長度為 0，第二個字符串長度為 j，將第一個字符串轉(zhuǎn)換成第二個字符串操作的次數(shù)是 j，這個操作是增加。
39. ② 處應(yīng)填( )
A. j
B. i
C. m
D. n
【答案】B
【解析】第一個字符串長度為 i，第二個字符串長度為 0，將第一個字符串轉(zhuǎn)換成第二個字符串操作的次數(shù)是 i，這個是刪除操作。
40. ③處應(yīng)填( )
A. str1[i-1]==str2[j-1]
B. str1[i]==str2[j]
C. str1[i-1]!=str2[j-1]
D. str1[i]!=str2[j]
【答案】A
【解析】匹配操作，第一個字符串和第二個字符串匹配。
41. ④處應(yīng)填( )
A. dp[i-1][j-1]+1
B. dp[i-1][j-1]
C. dp[i-1][j]
D. dp[i][j-1]
【答案】B
【解析】匹配的情況不需要操作
42. ⑤處應(yīng)填( )
A. dp[i][j] + 1
B. dp[i-1][j-1]+1
C. dp[i-1][j-1]
D. dp[i][j]
【答案】C
【解析】前 i-1 個字符與前 j 個字符最少操作次數(shù)、前 i 個字符與前 j-1 個字符最少操作次數(shù)、前 i-1 個字符與前 j-1 個字符最少操作三者取 min 后 + 1。
第四部分 總結(jié)
關(guān)于孩子是否適合走信奧這條路我的觀念依舊是能從中學(xué)到什么，對以后的學(xué)習(xí)生活有什么幫助，如果太看中成績，那么 99.9999% 的學(xué)生都是失敗者。
言歸正傳說一下考試試卷考點分析：
暑期集訓(xùn)的內(nèi)容沒有花太多的時間講動態(tài)規(guī)劃，因為想的是不太好挖空，主要太簡單，沒想到今年的題型比去年的簡單，對于系統(tǒng)學(xué)習(xí)的同學(xué)大部分都是 90 左右，這里的系統(tǒng)學(xué)習(xí)不是說考試出現(xiàn)的概率小就不考的誤區(qū)，程序閱讀沒學(xué)過動態(tài)規(guī)劃影響不大，暑期初賽集訓(xùn)課后有認(rèn)真思考的同學(xué) 65 左右。
學(xué)習(xí)建議:
① 戒驕戒躁，靜心學(xué)習(xí)
② 按照要求課后自覺上機練習(xí)(考場兩小時，課后兩三年功夫)
③ 戒掉功利主義的心態(tài)，如果只是為了保送清華北大建議放棄，打信奧能進(jìn)清北，全力沖刺高考文化課妥妥也牛掰(破音)
④ 不要相信不勞而獲，很多宣傳主打一個就是夸張宣傳，比如跟著誰學(xué)零基礎(chǔ)包 CSP-J 獲獎(主打吹牛)、包 CSP-J 晉級(主打考級)
⑤ 系統(tǒng)學(xué)習(xí)
⑥ 職業(yè)規(guī)劃，未來規(guī)劃專業(yè)不讀計算機、不讀研、不選擇和互聯(lián)網(wǎng)相關(guān)行業(yè)打不打信奧都沒有什么關(guān)系
教學(xué)反思:
① 不講概率事件，也不會按著家長的要求去講機構(gòu)的內(nèi)容，不會再將整個競賽體系打亂，union 是 2023 新大綱的內(nèi)容，認(rèn)為考是一個小概率事件，但是確實是考了，動態(tài)規(guī)劃程序題小概率事件考了
② 將競賽體系進(jìn)行順序的調(diào)整，考核不通過的學(xué)員不會講下一個階段的內(nèi)容
③ 第一年參賽只能說去和已經(jīng)獲獎的對手同臺競技，第一次比賽結(jié)束后續(xù)一定要好好學(xué)習(xí)，課后認(rèn)真刷題(杜絕水題)
④ 和機構(gòu)博弈的學(xué)員不帶，就是機構(gòu)不開課，家長就說自己找了教練，教務(wù)必然會各種挽留家長(已經(jīng)遇到過幾次，心累，沒有那個功夫和機構(gòu)斗嘴皮子，您說的全對！每天笑哈哈，拒絕精神內(nèi)耗)
⑤ 要想出成績不會再順著學(xué)員的心態(tài)數(shù)據(jù)削弱，完全掌握就是完全掌握，有些細(xì)節(jié)不注意錯就是錯，有則改之，無責(zé)加勉勵
天小白給大家簡單的講解了如何學(xué)習(xí)前端的方法，那么接下來我會做一系列的教程來教給大家如何一步步的學(xué)習(xí)，今天我們就說下三分鐘快速知道如何學(xué)HTML。
其實大家都知道無論是HTML還是HTML5都很簡單容易上手，所以很多想從事IT行業(yè)的人都作為入門語言。因為簡單易學(xué)，所以并沒有一套完整的學(xué)習(xí)流程，導(dǎo)致了一些人走了彎路，所以今天小白就簡單梳理一下個人學(xué)習(xí)意見。
一：閱讀官方資料
官方資料永遠(yuǎn)是最準(zhǔn)確和最基礎(chǔ)的，所以剛開始學(xué)習(xí)的時候就要先來看官放資料，一直到時間久了，很多東西不記得了，都要來查看官方資料，把官方基礎(chǔ)資料記在心里。
小白認(rèn)為，任何一門語言第一步都是要先閱讀然后再分析。熟悉HTML代碼的組成部分，聲明，結(jié)構(gòu)，標(biāo)簽，閉合等，這些都需要我們學(xué)習(xí)和分析。剛開始學(xué)習(xí)的時候肯定自己是寫不出來的，那么就要我們看完代碼后自己拷貝，敲打，然后記憶。逐漸把看到的知識點變成自己的代碼元素。
二：閱讀他人代碼
準(zhǔn)備出來足夠的時間去看別人的網(wǎng)站，分析別人的源代碼，看到不懂的就去查閱資料，做好筆記，讓不懂的知識點變成自己的知識。
在這里我提倡建議大家多去關(guān)注下HTML相關(guān)的技術(shù)論壇，論壇上會經(jīng)常有人提出問題，大家可以嘗試去回答，哪怕是查資料也好，這都是對知識的一次深層記憶。時間久了，你就發(fā)現(xiàn)自己進(jìn)步神速。
三：練習(xí)
通過上面兩個步驟，我們已經(jīng)掌握了足夠多的HTML代碼，那么我們可以使用DW進(jìn)行做一些簡單的網(wǎng)站制作，進(jìn)一步加深和練習(xí)。在練習(xí)過程中，可以使用對比的方法，找個目標(biāo)網(wǎng)站進(jìn)行仿制，逐步讓自己寫出的代碼能和原版有一樣的展現(xiàn)。不對的地方就進(jìn)行修改，這樣水平就會進(jìn)一步提升。
進(jìn)階：代碼優(yōu)化
以上步驟都進(jìn)行完以后，我們就需要再提升一下自己的能力，那就是我們嘗試著優(yōu)化我們的HTML代碼。如何用最簡單的邏輯實現(xiàn)我們的功能需求，同時避免冗余代碼的存在，保證一個良好的代碼書寫習(xí)慣。
總結(jié)：學(xué)習(xí)技術(shù)，只看不練永遠(yuǎn)無法上手的，所以我們要多記多練，首先我們要記HTML代碼最基本的網(wǎng)頁組成部分，比如說顏色如何表示、結(jié)構(gòu)排序如何表示、超鏈接如何表示、關(guān)鍵詞與標(biāo)題等等如何表示，而這些東西我們都必須將之記憶在大腦之中，通過記憶這個過程要讓自己的頭腦中有豐富的HTML代碼可以隨時利用。
、BeautifulSoup簡介
BeautifulSoup是Python爬蟲應(yīng)用解析Html的利器，是Python三方模塊bs4中提供的進(jìn)行HTML解析的類，可以認(rèn)為是一個HTML解析工具箱，對HTML報文中的標(biāo)簽具有比較好的容錯識別功能。lxml是一款html文本解析器，BeautifulSoup構(gòu)建對象時需要指定HTML解析器，推薦使用lxml。
BeautifulSoup和lxml安裝命令：
1.pip install -i https://pypi.tuna.tsinghua.edu.cn/simple bs4
2.pip install -i https://pypi.tuna.tsinghua.edu.cn/simple lxml
加載BeautifulSoup：
1.from bs4 import BeautifulSoup
BeatifulSoap解析HTML報文的常用功能：
通過標(biāo)簽的contents屬性，可以訪問其下嵌套的所有下級HTML元素，這些該標(biāo)簽下的子標(biāo)簽對應(yīng)的HTML元素放到一個contents 指向的列表中。
如：print(soup.body.contents)
可以訪問標(biāo)簽對應(yīng)的父、子、兄弟及祖先標(biāo)簽信息；
使用strings屬性迭代訪問除標(biāo)簽外的所有內(nèi)容；
可以使用find、find_all、find_parent、find_parents等系列方法查找滿足特定條件的標(biāo)簽；
使用select通過css選擇器定位特定標(biāo)簽。
二、一些解析技巧
在HTML解析時，如果通過簡單的tag、或單個tag屬性（如id、class）或文本一次搜索或select定位是最簡單的，而有些情況需要使用組合方法才能處理。
2.1、通過標(biāo)簽的多個屬性組合定位或查找
經(jīng)常有些要定位的標(biāo)簽有很多，按單個屬性查找也有很多，得使用多個屬性查找。如：
上面的html文本中有多個id為article_content的div標(biāo)簽，如果使用：
就會返回兩條記錄。這時候就可以使用多標(biāo)簽屬性定位的如下4種語句：
以上四種方式是等價的，因為id可以用#來標(biāo)記，class在查找時需要和Python關(guān)鍵字class區(qū)分，因此有上述不同方法，注意select的每個屬性必須用中括號括起來，不同屬性的中括號之間不能有空格，如果有空格表示的就不是查找同一標(biāo)簽的屬性，空格后的屬性表示前一個屬性對應(yīng)標(biāo)簽的子孫標(biāo)簽的屬性。
2.2、利用tag標(biāo)簽關(guān)系定位內(nèi)容
tag標(biāo)簽關(guān)系包括父子、兄弟、祖先等關(guān)系，有時要查找或定位的內(nèi)容本身不是很好定位，但結(jié)合其他標(biāo)簽關(guān)系（主要是父子、祖先關(guān)系）則可以唯一確認(rèn)。
案例：
這是博文中關(guān)于博主個人信息的部分報文：
以上報文中，如果要取博主的原創(chuàng)文章數(shù)和周排名，原創(chuàng)文章數(shù)和博主周排名的tag標(biāo)簽完全相同，二者都在span標(biāo)簽內(nèi)，標(biāo)簽的屬性及值都相同，只是span標(biāo)簽的父標(biāo)簽dt標(biāo)簽的兄弟標(biāo)簽dd標(biāo)簽的string的中文內(nèi)容才能區(qū)分。對于這種情況，首先要通過祖先標(biāo)簽<div class="data-info d-flex item-tiling">定位到祖先標(biāo)簽，再在祖先標(biāo)簽內(nèi)通過中文字符串定位到要訪問屬性的兄弟標(biāo)簽的子標(biāo)簽，然后通過該子標(biāo)簽找到其父標(biāo)簽的父標(biāo)簽，再通過該父標(biāo)簽的dt子標(biāo)簽的span子標(biāo)簽訪問具體取值。
示例代碼如下：
注意：上面的select使用的也是標(biāo)簽的屬性來定位標(biāo)簽，并且兩個中括號之間有空格，表明后一個要查找的標(biāo)簽在前一個屬性對應(yīng)標(biāo)簽的子孫標(biāo)簽范圍內(nèi)。
2.3、分析前去除程序代碼避免干擾
在解析HTML報文時，絕大多數(shù)情況是需要分析有用的標(biāo)簽信息，但作為技術(shù)文章，大部分的博文中都有代碼，這些代碼可能會對分析進(jìn)行干擾。如本文中的代碼含有一些分析的HTML報文，如果獲取本文的完整HTML內(nèi)容，這些報文在非代碼部分也會出現(xiàn)，此時要排除代碼的影響，可以將代碼先從分析內(nèi)容中去除再來分析。
目前大多數(shù)技術(shù)平臺的博文編輯器都支持對代碼的標(biāo)識，象markdown等編輯器代碼的標(biāo)簽為code標(biāo)檢，如果有其他編輯器用不同標(biāo)簽的，只有確認(rèn)了標(biāo)簽名，都可以按下面介紹的類似方式來處理。
處理步驟如下：
獲取報文；
構(gòu)建BeatifulSoap對象soup；
通過soup.code.extract()或soup.code.decompose（）方式就從soup對象中去除了代碼部分，decompose方法與extract方法的區(qū)別就是decompose直接刪除對應(yīng)對象數(shù)據(jù)而extract再刪除時將刪除對象單獨返回。
三、小結(jié)
本文介紹了使用BeatifulSoap解析HTML報文的三個使用技巧，包括通過多屬性組合查找或定位標(biāo)簽、通過結(jié)合多個標(biāo)簽關(guān)系來定位標(biāo)簽以及去除html報文中的代碼標(biāo)簽來避免代碼對解析的影響。
寫字不易，敬請支持：
如果閱讀本文于您有所獲，敬請點贊、評論、收藏，謝謝大家的支持！
————————————————
版權(quán)聲明：本文為轉(zhuǎn)載文章，如有侵權(quán)，請聯(lián)系作者刪除。
*請認(rèn)真填寫需求信息，我們會在24小時內(nèi)與您取得聯(lián)系。
