回溯演算法時間復雜度

❶ 演算法-KMP

大一下參加學校ACM預備隊集訓的時候首次接觸KMP演算法，當時看了很多介紹文章，仍然不是很理解其實質，只是簡單地套模板AC題目，待大二數據結構與演算法課堂上再聽老師介紹一次，才恍然大悟其實KMP也就是那麼回事嘛。但當初為啥看那麼多文章都沒弄明白呢？正巧最近和朋友聊天時他告訴我他對KMP不是很理解，於是打算自己寫一篇文章，鞏固自己對KMP的認識，也希望能夠幫助更多朋友理解KMP。
在開始之前，需要知曉的概念：

前綴：以原串串頭為自身串頭的子串，如 的前綴有：
後綴：以原串串尾為自身串尾的子串，如 的後綴有：

注意：字元串前後綴都不包括該串本身

給你一個文本串T(Text String)

再給你一個模式串P(Pattern String)

問該模式串是否在文本串中，怎麼找？

一開始只好分別從文本串與模式串的串頭開始逐字母比較

二者相同，再比較T串與P串的下一位

如此反復

如果一直這么順利，兩串對應位置的字元總相同，待P串中最後一個字元也匹配完畢，說明該模式串在文本串中存在，耶( •̀ ω •́ )y超開心，查找結束。但，大多數匹配過程不會如此順利，在該例中，當匹配進行至

很明顯，失配了。現在怎麼辦？按樸素思想，將P串相對T串整體右移一位，重新開始匹配，即

但這種演算法效率無疑是十分低下的。設T串長度N，P串長度M，則樸素演算法時間復雜度為O(MN)

已知的重要信息並沒有被使用——已匹配的字元串前綴

在上例中，當P串最後一個字元匹配失敗時，其已有包含七個字元的 前綴子串S 匹配成功

完全可以利用前綴子串S做點什麼。觀察到在S串

中，有相同前後綴，即下圖藍色部分

而S串各字元又與T串中對應字元相同，即有

當失配發生後，直接將P串右移四位使S串藍色後綴部分對齊T串中藍色前綴部分

從圖中紅框部分繼續嘗試匹配，發現再次失配。這次，已匹配成功的前綴串S為

而在該串中沒有相同的前後綴，只能將P串串頭移至失配處進行比較

再次失配。此時前綴串S為空串，只好如樸素演算法般將P串整體右移一位，重新開始比較

匹配成功。於是又按照之前的步驟往下匹配，直至再次失配或匹配成功

後續步驟同上，不再贅述

上述示例已展現，KMP演算法的精髓在於對已匹配成功的前綴串S的利用

在樸素演算法中，匹配失敗了，T串待匹配字元會回溯

T串原本已匹配至T[7] = 'X'，但是因為失配，需回溯到T[1] = 'b'重新開始匹配

而在KMP演算法中，若P[M]與T[K]匹配失敗，K不會回溯。既然匹配過程是從T[0]開始逐漸向右進行的，至T[K]失配發生時，T[0]至T[K-1]早已匹配過，何必再回溯過去重復匹配呢？於是乎，就如問題引入部分展示般

每當失配發生，我們總是去關注P串中已匹配成功的前綴串S

因為該前綴串是匹配成功的，說明在T串中必定存在與該前綴串相同的子串，記為S'

若S串中存在相同前後綴

則S'串必然也存在此相同前後綴

所以只需將P串右移四位，使得S串的該相同前綴對齊S'串的該相同後綴

再嘗試比較T[7]與P[3]

至於T[7]與P[3]是否能夠匹配另說（當然，本例中一看就知道沒匹配上），但通過對前綴串S的利用，成功省去了P串右移一位、兩位和三位後的無效匹配

繼續深入思考，給定一個具體的P串，其第N位的前綴串S內容是固定的，則S是否存在相同前後綴、相同前後綴的長度與內容也是確定的。換言之，對於一個具體的P串，當其與給定T串匹配至P[N]失配，P串應右移幾位再次與T串進行匹配也是確定的。我們完全可以使用一個數組記錄當P[N]失配後，應當使用N之前的哪一位再來與T串進行匹配，以此提高匹配效率，記該數組為Next數組

定義Next[i] = j表示當P串中第i位失配後，跳轉至P串第j位再次嘗試匹配

還是以之前的P串為例，它的Next數組求出來應為

取下標5為例，其前綴串為

最長相同前後綴為

若P[5]失配，應跳轉至P[1]再次嘗試匹配（最長相同前綴對應P[0]，則取其後一位P[1]，若存在多位，則取最後一位的下一位），P[5]的前一個字元P[4]對應字元'a'，而P[1]前一個字元P[0]同對應字元'a'，保證了P[1]之前字元與T串中對應字元保持匹配。所以Next[5] = 1，其餘下標對應Next數組值同如此求。

特別地，規定Next[0] = -1。而對於除下標0外的任意下標N，Next[N]的含義是 前N-1個已匹配成功的字元構成的前綴串S中，最長相同前後綴長度。 所以若在下標為N處匹配失敗了，則應前往Next[N]所對應的下標處匹配。

具體地，以下圖所示為例，P[6]與T[6]失配

而Next[6] = 2，所以使用P[2]再次嘗試與T[6]進行匹配

當求出P串Next數組後，便可快速進行與T串的匹配

現在問題只剩下如何求Next數組，注意到Next數組既然只與P串本身相關，與文本串T無關，故令P串與自身匹配即可求得

考慮字元串

其Next數組應為

令其與給定文本串相匹配

當匹配進行至

失配，於是跳轉至P[Next[3]] = P[1]處再次嘗試匹配

再度失配，也必然失配

問題在於不該出現P[N] =P[Next[N]]

若P[N] =P[Next[N]]，則P[N]失配後使用P[Next[N]]再次嘗試匹配，由於P[N] =P[Next[N]]，P[N]匹配失敗，P[Next[N]]必然也失敗

因此，若出現P[N] =P[Next[N]]情況，則令Next[N]=Next[Next[N]]

本例中該字元串新Next數組為

當匹配進行至

失配，於是跳轉至P[Next[3]] = P[0]處再次嘗試匹配

省去了之前跳轉至P[1]處的無效匹配

設T串長度M，P串長度N，由於KMP演算法不會回溯，分析易知時間復雜度為O(m+n)

對於P[N]，若其前綴串S含相同前後綴F，且F長度為n（n>1），Next[N]可以取1至n中任意值，為最大化匹配效率考慮，總是取最大相同前後綴以提高效率，節省時間

❷ 百度地圖的路徑搜索演算法

這個還是要問程序猿，現在比較流行A*演算法，至於網路是否開發出了新的演算法不得而知，畢竟沒有完全相同的程序。
給你看一篇文獻：
地圖中最短路徑的搜索演算法研究
學生:李小坤 導師：董巒
摘要：目前為止, 國內外大量專家學者對「最短路徑問題」進行了深入的研究。本文通過理論分析, 結合實際應用，從各個方面較系統的比較廣度優先搜索演算法(BFS)、深度優先搜索演算法(DFS)、A* 演算法的優缺點。
關鍵詞:最短路徑演算法；廣度優先演算法；深度優先演算法；A*演算法；
The shortest path of map's search algorithm
Abstract:So far, a large number of domestic and foreign experts and scholars on the" shortest path problem" in-depth study. In this paper, through theoretical analysis and practical application, comprise with the breadth-first search algorithm ( BFS ), depth-first search algorithm ( DFS ) and the A * algorithms from any aspects of systematic.
Key words: shortest path algorithm; breadth-first algorithm; algorithm; A * algorithm;
前言：
最短路徑問題是地理信息系統（GIS）網路分析的重要內容之一，而且在圖論中也有著重要的意義。實際生活中許多問題都與「最短路徑問題」有關, 比如: 網路路由選擇, 集成電路設計、布線問題、電子導航、交通旅遊等。本文應用深度優先演算法，廣度優先演算法和A*演算法，對一具體問題進行討論和分析，比較三種算的的優缺點。

在地圖中最短路徑的搜索演算法研究中，每種演算法的優劣的比較原則主要遵循以下三點:[1]
(1)演算法的完全性：提出一個問題，該問題存在答案，該演算法能夠保證找到相應的答案。演算法的完全性強是演算法性能優秀的指標之一。
(2)演算法的時間復雜性: 提出一個問題，該演算法需要多長時間可以找到相應的答案。演算法速度的快慢是演算法優劣的重要體現。
(3)演算法的空間復雜性:演算法在執行搜索問題答案的同時，需要多少存儲空間。演算法佔用資源越少，演算法的性能越好。
地圖中最短路徑的搜索演算法:
1、廣度優先演算法
廣度優先演算法(Breadth-First-Search)，又稱作寬度優先搜索，或橫向優先搜索，是最簡便的圖的搜索演算法之一，這一演算法也是很多重要的圖的演算法的原型,Dijkstra單源最短路徑演算法和Prim最小生成樹演算法都採用了和寬度優先搜索類似的思想。廣度優先演算法其別名又叫BFS，屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位址，徹底地搜索整張圖，直到找到結果為止。BFS並不使用經驗法則演算法。
廣度優先搜索演算法偽代碼如下：[2-3]
BFS(v)//廣度優先搜索G，從頂點v開始執行
//所有已搜索的頂點i都標記為Visited(i)=1.
//Visited的初始分量值全為0
Visited(v)=1;
Q=[];//將Q初始化為只含有一個元素v的隊列
while Q not null do
u=DelHead(Q);
for 鄰接於u的所有頂點w do
if Visited(w)=0 then
AddQ(w,Q); //將w放於隊列Q之尾
Visited(w)=1;
endif
endfor
endwhile
end BFS
這里調用了兩個函數：AddQ(w,Q)是將w放於隊列Q之尾；DelHead(Q)是從隊列Q取第一個頂點，並將其從Q中刪除。重復DelHead(Q)過程，直到隊列Q空為止。
完全性：廣度優先搜索演算法具有完全性。這意指無論圖形的種類如何，只要目標存在，則BFS一定會找到。然而，若目標不存在，且圖為無限大，則BFS將不收斂（不會結束）。
時間復雜度：最差情形下，BFS必須尋找所有到可能節點的所有路徑，因此其時間復雜度為,其中|V|是節點的數目，而 |E| 是圖中邊的數目。
空間復雜度：因為所有節點都必須被儲存，因此BFS的空間復雜度為，其中|V|是節點的數目，而|E|是圖中邊的數目。另一種說法稱BFS的空間復雜度為O(B),其中B是最大分支系數，而M是樹的最長路徑長度。由於對空間的大量需求，因此BFS並不適合解非常大的問題。[4-5]
2、深度優先演算法
深度優先搜索演算法（Depth First Search）英文縮寫為DFS，屬於一種回溯演算法，正如演算法名稱那樣，深度優先搜索所遵循的搜索策略是盡可能「深」地搜索圖。[6]其過程簡要來說是沿著頂點的鄰點一直搜索下去，直到當前被搜索的頂點不再有未被訪問的鄰點為止，此時，從當前輩搜索的頂點原路返回到在它之前被搜索的訪問的頂點，並以此頂點作為當前被搜索頂點。繼續這樣的過程，直至不能執行為止。
深度優先搜索演算法的偽代碼如下：[7]
DFS(v) //訪問由v到達的所有頂點
Visited(v)=1;
for鄰接於v的每個頂點w do
if Visited(w)=0 then
DFS(w);
endif
endfor
end DFS
作為搜索演算法的一種，DFS對於尋找一個解的NP（包括NPC）問題作用很大。但是，搜索演算法畢竟是時間復雜度是O(n!)的階乘級演算法，它的效率比較低，在數據規模變大時，這種演算法就顯得力不從心了。[8]關於深度優先搜索的效率問題，有多種解決方法。最具有通用性的是剪枝，也就是去除沒有用的搜索分支。有可行性剪枝和最優性剪枝兩種。
BFS:對於解決最短或最少問題特別有效，而且尋找深度小，但缺點是內存耗費量大（需要開大量的數組單元用來存儲狀態）。
DFS：對於解決遍歷和求所有問題有效，對於問題搜索深度小的時候處理速度迅速，然而在深度很大的情況下效率不高。
3、A*演算法
1968年的一篇論文，「P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2):100-107, 1968」。[9]從此，一種精巧、高效的演算法——A*演算法問世了，並在相關領域得到了廣泛的應用。A* 演算法其實是在寬度優先搜索的基礎上引入了一個估價函數,每次並不是把所有可擴展的結點展開,而是利用估價函數對所有未展開的結點進行估價, 從而找出最應該被展開的結點,將其展開,直到找到目標節點為止。
A*演算法主要搜索過程偽代碼如下：[10]
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
算起點的估價值;
將起點放入OPEN表;
while(OPEN!=NULL) //從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
endif
for(當前節點n 的每個子節點X)
算X的估價值;
if(X in OPEN)
if(X的估價值小於OPEN表的估價值)
把n設置為X的父親;
更新OPEN表中的估價值; //取最小路徑的估價值;
endif
endif
if(X inCLOSE)
if( X的估價值小於CLOSE表的估價值)
把n設置為X的父親;
更新CLOSE表中的估價值;
把X節點放入OPEN //取最小路徑的估價值
endif
endif
if(X not inboth)
把n設置為X的父親;
求X的估價值;
並將X插入OPEN表中; //還沒有排序
endif
end for
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
end while(OPEN!=NULL)
保存路徑，即 從終點開始，每個節點沿著父節點移動直至起點，這就是你的路徑；
A *演算法分析：
DFS和BFS在展開子結點時均屬於盲目型搜索，也就是說，它不會選擇哪個結點在下一次搜索中更優而去跳轉到該結點進行下一步的搜索。在運氣不好的情形中，均需要試探完整個解集空間, 顯然，只能適用於問題規模不大的搜索問題中。而A*演算法與DFS和BFS這類盲目型搜索最大的不同，就在於當前搜索結點往下選擇下一步結點時，可以通過一個啟發函數來進行選擇，選擇代價最少的結點作為下一步搜索結點而跳轉其上。[11]A *演算法就是利用對問題的了解和對問題求解過程的了解, 尋求某種有利於問題求解的啟發信息, 從而利用這些啟發信息去搜索最優路徑.它不用遍歷整個地圖, 而是每一步搜索都根據啟發函數朝著某個方向搜索.當地圖很大很復雜時, 它的計算復雜度大大優於D ijks tr a演算法, 是一種搜索速度非常快、效率非常高的演算法.但是, 相應的A*演算法也有它的缺點.啟發性信息是人為加入的, 有很大的主觀性, 直接取決於操作者的經驗, 對於不同的情形要用不同的啟發信息和啟發函數, 且他們的選取難度比較大,很大程度上找不到最優路徑。
總結：
本文描述了最短路徑演算法的一些步驟，總結了每個演算法的一些優缺點，以及演算法之間的一些關系。對於BFS還是DFS，它們雖然好用，但由於時間和空間的局限性，以至於它們只能解決規模不大的問題，而最短或最少問題應該選用BFS,遍歷和求所有問題時候則應該選用DFS。至於A*演算法，它是一種啟發式搜索演算法，也是一種最好優先的演算法，它適合於小規模、大規模以及超大規模的問題，但啟發式搜索演算法具有很大的主觀性，它的優劣取決於編程者的經驗，以及選用的啟發式函數，所以用A*演算法編寫一個優秀的程序，難度相應是比較大的。每種演算法都有自己的優缺點，對於不同的問題選擇合理的演算法，才是最好的方法。
參考文獻：
[1]陳聖群,滕忠堅,洪親,陳清華.四種最短路徑演算法實例分析[J].電腦知識與技術(學術交流),2007(16):1030-1032
[2]劉樹林,尹玉妹.圖的最短路徑演算法及其在網路中的應用[J].軟體導刊,2011(07):51-53
[3]劉文海,徐榮聰.幾種最短路徑的演算法及比較[J].福建電腦，2008(02）:9-12
[4]鄧春燕.兩種最短路徑演算法的比較[J].電腦知識與技術，2008（12）：511-513
[5]王蘇男,宋偉,姜文生.最短路徑演算法的比較[J].系統工程與電子技術,1994(05)：43-49
[6]徐鳳生,李天志.所有最短路徑的求解演算法[J].計算機工程與科學,2006(12)：83-84
[7]李臣波,劉潤濤.一種基於Dijkstra的最短路徑演算法[J].哈爾濱理工大學學報,2008(03)：35-37
[8]徐鳳生.求最短路徑的新演算法[J].計算機工程與科學,2006(02).
[9] YanchunShen . An improved Graph-based Depth-First algorithm and Dijkstra algorithm program of police patrol [J] . 2010 International Conference on Electrical Engineering and Automatic Control , 2010(3) : 73-77
[10]部亞松.VC++實現基於Dijkstra演算法的最短路徑[J].科技信息(科學教研),2008(18)：36-37
[11] 楊長保,王開義,馬生忠.一種最短路徑分析優化演算法的實現[J]. 吉林大學學報(信息科學版),2002(02)：70-74

❸ KMP演算法的時間復雜度為什麼是O(n)

主串T，比較串P，
由於KMP演算法的思想是主串不回溯的簡化演算法，執行的時候呢在串比較的掃描裡面要麼執行POST和POSP，要麼執行NEXT[]數組的右移，然後比較，所以字元比較最多就是為O（LenthT）,即不會超過O（n）
其實KMP看起來很嚇人，但是你抓住它的思想「主串不回溯」就很簡單了.

KMP演算法是一種改進的字元串匹配演算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同時發現，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP演算法）。KMP演算法的關鍵是利用匹配失敗後的信息，盡量減少模式串與主串的匹配次數以達到快速匹配的目的。具體實現就是實現一個next()函數，函數本身包含了模式串的局部匹配信息。

❹ 回溯法求N皇後問題時間復雜度是不是O(n^n)

沒有那麼多，就是不加斜線約束，由於不能同行同列，因此也最多隻是O(n!)

❺ 用C++函數描述個演算法，並求出時間復雜度

#include<iostream.h>
int max=0,may=0;
int array[5][5];
void ReMax()
{
int i,j;
///冒泡法，時間復雜度為5*5
for(i=0;i<5;i++)
for(j=0;j<5;j++)
if(array[max][may]<array[i][j+1]){max=i;may=j+1;}
}
void main(){
int i,j;
//*a=(int*)malloc(5*sizeof(int));
cout<<"請輸入一個數組array[5][5]："<<endl;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
cin>>array[i][j];
ReMax();
cout<<"最大值坐標："<<max<<","<<may<<endl;
}

❻ 24點問題，回溯演算法

回溯演算法也叫試探法，它是一種系統地搜索問題的解的方法。回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。用回溯演算法解決問題的一般步驟為： 1、定義一個解空間，它包含問題的解。 2、利用適於搜索的方法組織解空間。 3、利用深度優先法搜索解空間。 4、利用限界函數避免移動到不可能產生解的子空間。 問題的解空間通常是在搜索問題的解的過程中動態產生的，這是回溯演算法的一個重要特性。1.跳棋問題：33個方格頂點擺放著32枚棋子，僅中央的頂點空著未擺放棋子。下棋的規則是任一棋子可以沿水平或成垂直方向跳過與其相鄰的棋子，進入空著的頂點並吃掉被跳過的棋子。試設計一個演算法找出一種下棋方法，使得最終棋盤上只剩下一個棋子在棋盤中央。演算法實現提示利用回溯演算法，每次找到一個可以走的棋子走動，並吃掉。若走到無子可走還是剩餘多顆，則回溯，走下一顆可以走動的棋子。當吃掉31顆時說明只剩一顆，程序結束。2.中國象棋馬行線問題：中國象棋半張棋盤如圖1(a)所示。馬自左下角往右上角跳。今規定只許往右跳，不許往左跳。比如圖4（a）中所示為一種跳行路線，並將所經路線列印出來。列印格式為：0，0->2,1->3,3->1,4->3,5->2,7->4,8…演算法分析：如圖1(b),馬最多有四個方向，若原來的橫坐標為j、縱坐標為i,則四個方向的移動可表示為：1: （i,j）→（i+2,j+1）； (i<3,j<8) 2: （i,j）→（i+1,j+2）； (i<4,j<7)3: （i,j）→（i-1,j+2）； (i>0,j<7) 4: （i,j）→（i-2,j+1）； (i>1,j<8)搜索策略：S1:Ａ[１]:=(0,0);S2:從Ａ[1]出發，按移動規則依次選定某個方向，如果達到的是（4,8）則轉向S3,否則繼續搜索下一個到達的頂點；S3:列印路徑。演算法設計：procere try(i:integer); var j:integer;beginfor j:=1 to 4 do if 新坐標滿足條件 thenbegin記錄新坐標;if 到達目的地 then print else try(i+1); 退回到上一個坐標，即回溯;end;end;

❼ 關於初中的NOIP問題

這是我從
中華信息學競賽網http://www.100xinxi.com/上
復制過來的NOIP大綱,你自己看看吧,還什麼不懂的,你直接去那看吧``(中華信息學競賽網)
由中國計算機學會負責組織的全國青少年信息學奧林匹克聯賽（National Olympiad in Informatics in Provinces, 簡稱NOIP）是全國信息學奧林匹克競賽（NOI）系列活動中的一個重要組成部分，旨在向中學生普及計算機基礎知識，培養計算機科學和工程領域的後備人才。普及的重點是根據中學生的特點，培養學生學習計算機的興趣，使得他們對信息技術的一些核心內容有更多的了解，提高他們創造性地運用程序設計知識解決實際問題的能力。對學生的能力培養將注重以下的幾個方面：
1.想像力與創造力；
2.對問題的理解和分析能力；
3.數學能力和邏輯思維能力；
4.對客觀問題和主觀思維的口頭和書面表達能力；
5.人文精神：包括與人的溝通能力，團隊精神與合作能力，恆心和毅力，審美能力等。
二、命題程序和組織機構
命題是考核和選拔過程中的重要一環，對計算機的普及的內容具有導向性作用。命題應注重趣味性、新穎性、知識性、應用性和中學生的心智特點，不直接從大學專業教材中選題。
在命題和審題工作中，堅持開放和規范的原則。在NOI科學委員會主持下成立的NOIP命題委員會負責命題工作，命題委員會成員主要來自參加NOIP的省（ 包括直轄市、自治區，下同。每個省最多派一名委員），也可來自社會計算機界。NOIP命題委員會的主要職責是提供NOIP的備選題目，並承擔對所提供的題目保密的責任。
1. NOIP命題委員會委員應具備如下資格：
從事一線計算機教學或信息學奧賽輔導工作兩年（含）以上；
有精力和時間從事該項工作；
對此項工作有興趣並願意作為志願者從事NOIP命題及其相關工作。
2. NOIP命題委員會委員的產生過程：
本人提出申請（填寫表格）；
中學教師需得到所在單位同意或省奧賽主管部門同意；
科學委員會批准，由中國計算機學會頒發聘書（每一聘期為兩年）。
3. NOIP命題委員會委員的職責：
每年為NOIP提供備選題題目若干，在9月1日之前提交科學委員會；
備選試題的保密期為2年，在該段時間內不得泄密或另作他用；
搜集本省信息學奧賽的有關信息並向科學委員會通報；
4. 題目一經提交，即表明同意授權中國計算機學會科學委員會全權處理，包括使用、修改和出版。試題原型被科學委員會採用後，中國計算機學會將為命題者頒發試題錄用證書，並頒發酬金。無論是委員提交的題目還是科學委員會直接提交的題目，試題版權均歸中國計算機學會所有。NOIP所用試題由科學委員會確定，這些試題可能從備選題庫中選取並做適當修改後成型，也可能直接命題。
三、競賽形式和成績評定
NOIP分兩個等級組：普及組和提高組。每組競賽分兩輪：初試和復試。
初試形式為筆試，側重考察學生的計算機基礎知識和編程的基本能力，並對知識面的廣度進行測試。初試為資格測試，獲本省初試成績在本賽區前
15%的學生進入復賽。
復試形式為上機編程，著重考察學生對問題的分析理解能力，數學抽象能力，編程語言的能力和編程技巧、想像力和創造性等。各省NOIP的等第獎在復試的優勝者中產生。
比賽中使用的程序設計語言是：
初賽：PASCAL或C/C++：
復賽：PASCAL或C/C++。
每年復賽結束後，各省必須在指定時間內將本省一等獎候選人的有關情況、源程序和可執行程序報送科學委員會。經復審和評測後，由中國計算機學會報送中國科協和教育部備案。中國計算機學會對各省獲NOIP二等獎和三等獎的分數線或比例提出指導性意見，各省可按照成績確定獲獎名單。
四、試題形式
每次NOIP的試題分四組：普及組初賽題A1、普及組復賽題A2、提高組初賽題B1和提高組復賽題B2。其中，A1和B1類型基本相同，A2和B2類型基本相同，但題目不完全相同，提高組難度高於普及組。
（一）初賽
初賽全部為筆試，滿分100分。試題由四部分組成：
1、選擇題：共20題，每題1.5分，共計30分。每題有5個備選答案，前10個題為單選題（即每題有且只有一個正確答案，選對得分），後10題為不定項選擇題（即每題有1至5個正確答案，只有全部選對才得分）。普及組20個都是單選題。
2、問題求解題：共2題，每題5分，共計10分。試題給出一個敘述較為簡單的問題，要求學生對問題進行分析，找到一個合適的演算法，並推算出問題的解。考生給出的答案與標准答案相同，則得分；否則不得分。
3、程序閱讀理解題：共4題，每題8分，共計32分。題目給出一段程序（不一定有關於程序功能的說明），考生通過閱讀理解該段程序給出程序的輸出。輸出與標准答案一致，則得分；否則不得分。
4、程序完善題：共2題，每題14分，共計28分。題目給出一段關於程序功能的文字說明，然後給出一段程序代碼，在代碼中略去了若干個語句或語句的一部分並在這些位置給出空格，要求考生根據程序的功能說明和代碼的上下文，填出被略去的語句。填對則得分；否則不得分。
（二）復賽
復賽的題型和考試形式與NOI類似，全部為上機編程題，但難度比NOI低。題目包括4道題，每題100分，共計400分。每一試題包括：題目、問題描述、輸入輸出要求、樣例描述及相關說明。測試時，測試程序為每道題提供了5-10組測試數據，考生程序每答對一組得10－20分，累計分即為該道題的得分。
五、試題的知識范圍
（一）初賽內容與要求：

計基
算本
機常
的識 1．計算機和信息社會（信息社會的主要特徵、計算機的主要特徵、數字通信網路的主要特徵、數字化）
2．信息輸入輸出基本原理（信息交換環境、文字圖形多媒體信息的輸入輸出方式）
3．信息的表示與處理（信息編碼、微處理部件MPU、內存儲結構、指令，程序，和存儲程序原理、程序的三種基本控制結構）
4．信息的存儲、組織與管理（存儲介質、存儲器結構、文件管理、資料庫管理）
5．信息系統組成及互連網的基本知識（計算機構成原理、槽和埠的部件間可擴展互連方式、層次式的互連結構、互聯網路、TCP/IP協議、HTTP協議、WEB應用的主要方式和特點）
6．人機交互界面的基本概念（窗口系統、人和計算機交流信息的途徑（文本及交互操作））
7．信息技術的新發展、新特點、新應用等。

計基
算本
機操
的作 1. Windows和LINUX的基本操作知識
2. 互聯網的基本使用常識 （網上瀏覽、搜索和查詢等）
3. 常用的工具軟體使用（文字編輯、電子郵件收發等）

程
序
設
計
的
基
本
知
識
數
據
結
構 1．程序語言中基本數據類型(字元、整數、長整、浮點)
2. 浮點運算中的精度和數值比較
3．一維數組（串）與線性表
4．記錄類型（PASCAL）/ 結構類型（C）
程
序
設
計 1．結構化程序設計的基本概念
2．閱讀理解程序的基本能力
3．具有將簡單問題抽象成適合計算機解決的模型的基本能力
4．具有針對模型設計簡單演算法的基本能力
5．程序流程描述（自然語言/偽碼/NS圖/其他）
6．程序設計語言（PASCAL/C/C++）- 2003仍允許BASIC
基本
演算法
處 理 1．初等演算法（計數、統計、數學運算等）
2．排序演算法（冒泡法、插入排序、合並排序、快速排序）
3．查找（順序查找、二分法）
4．回溯演算法

（二）復賽內容與要求：
在初賽內容的基礎上增加以下內容：
數
據
結
構 1．指針類型
2．多維數組
3．單鏈表及循環鏈表
4．二叉樹
5．文件操作（從文本文件中讀入數據，並輸出到文本文件中）
程
序
設
計 1．演算法的實現能力
2．程序調試基本能力
3．設計測試數據的基本能力
4．程序的時間復雜度和空間復雜度的估計
算
法
處
理 1．離散數學知識的應用（如排列組合、簡單圖論、數理邏輯）
2．分治思想
3．模擬法
4．貪心法
5．簡單搜索演算法（深度優先 廣度優先）搜索中的剪枝
6．動態規劃的思想及基本演算法

六、試題保密紀律
關於保密以及考試的紀律見NOI條例。NOIP主辦單位中國計算機學會負責NOIP的紀律監察工作並接受投訴，加強過程監管，防止賽題泄漏、考場舞弊、弄虛作假等現象的發生。一旦查實命題委員會委員泄密備選試題，考場泄題或舞弊，或篡改試卷和考試成績者，主辦單位將根據NOI條例及其有關規則予以懲罰。

❽ 計算機二級公共基礎知識是什麼啊

《計算機二級-公共基礎》網路網盤資源免費下載

鏈接: https://pan..com/s/1juX-rK_zhvGXNXQrq-qvew

?pwd=i9cr 提取碼: i9cr

計算機二級-公共基礎|第一章|第四章|第三章|第二章|第二章-程序設計基礎（一）.mp4|第二章-程序設計基礎（二）.mp4|第三章軟體工程基礎軟體工程基礎（七）.mp4|第三章軟體工程基礎（五）.mp4|第三章軟體工程基礎（四）.mp4|第三章-軟體工程基礎（一）.mp4|第三章-軟體工程基礎（三）.mp4|第三章-軟體工程基礎（六）.mp4|第三章-軟體工程基礎（二）.mp4|第四章資料庫設計基礎（二）.mp4