回溯算法时间复杂度

❶ 算法-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