NOI竞赛创新试题及对应答案

NOI竞赛创新试题及对应答案考试时间：______分钟总分：______分姓名：______一、选择题（每题只有一个正确选项，请将正确选项的字母填在题后的括号内。每题2分，共30分）1.在一个无向连通图中，如果移除某个顶点及其所有关联边后，剩余图不再连通，则该顶点称为图的关节点。以下关于无向连通图关节点的说法中，正确的是（）。A.该图至少存在两个关节点B.移除该关节点后，剩余图可能存在多个连通分量C.如果该图是树，则所有顶点都是关节点D.关节点度数一定大于等于22.给定一个长度为n的序列，定义序列A的“摇摆度”为其中相邻元素之间严格单调递增和严格单调递减对数的总和。例如，序列[1,7,4,9,2,5]的摇摆度为5（1->7上升，7->4下降，4->9上升，9->2下降，2->5上升）。以下序列中，摇摆度等于3的是（）。A.[3,3,3,3]B.[1,2,3,4,5]C.[5,4,3,2,1]D.[1,3,2,4,3]3.在一个由m个点（编号1到m）和n条无向边组成的简单图中，如果存在一个点，从该点出发进行BFS（广度优先搜索）遍历时，可以访问到所有其他点，则称该点为图的中心点。以下关于简单图中心点的说法中，正确的是（）。A.任何简单图都至少存在一个中心点B.如果一个图有唯一的中心点，那么该中心点一定是叶子节点C.完全图Km的中心点数量可能为1或2D.中心点的度数一定小于等于图中其他任何点的度数4.设f(x)是定义在实数集R上的一个函数，满足对于任意x,y∈R，都有f(x+y)=f(x)+f(y)+xy，且f(1)=1。则f(0)的值等于（）。A.-1B.0C.1D.25.在一个信息通信网络中，节点代表通信设备，边代表通信链路。为了确保任意两个节点之间都能通信（可能经过其他节点转发），需要添加最少的边数，使得网络变为连通图。这个最小边数被称为图的“连通性”（ConnectivityNumber）。以下关于连通性的说法中，正确的是（）。A.对于n个节点的连通图，其连通性至少为n-1B.如果一个图是连通的，那么它的连通性为0C.移除一个关节点不一定会降低图的连通性D.完全图Kn的连通性为n-26.给定一个由0和1组成的n×n矩阵，定义矩阵的“核心连通块”为：从任意一个1出发，通过上下左右相邻的1可以到达的所有1组成的最大连通区域。以下关于矩阵核心连通块的说法中，正确的是（）。A.核心连通块的大小等于矩阵中1的总数B.如果矩阵中存在一个1，则该1一定属于某个核心连通块C.核心连通块之间可能存在零的间隔D.核心连通块的数量等于矩阵中最大连通块的大小7.在一个有向无环图（DAG）中，对于任意两个顶点u和v，如果从u到v存在有向路径，则称u是v的祖先，v是u的子孙。以下关于DAG祖先与子孙关系的说法中，正确的是（）。A.一个顶点可以没有祖先B.一个顶点可以没有子孙C.如果u是v的祖先，且w是v的祖先，则u一定是w的祖先D.DAG中所有顶点可以构成一个父子关系树8.设T是包含n个节点和m条边的无向树。以下关于树T的性质中，错误的是（）。A.T中不存在环B.T有n-1条边C.T是连通的D.T中任意两个节点之间有且仅有一条简单路径E.T至少有两个叶子节点（度数为1的节点）9.在一个序列中，定义“局部极小值”为：该位置上的元素小于其相邻元素（如果存在相邻元素）。定义“局部极大值”为：该位置上的元素大于其相邻元素（如果存在相邻元素）。以下关于序列极值点的说法中，正确的是（）。A.一个严格单调递增或递减的序列没有局部极值点B.序列的长度为1时，它既不是局部极小值点也不是局部极大值点C.序列的最后一个元素不可能是局部极大值点D.序列的长度为2时，它可能同时是局部极小值点和局部极大值点10.对于一个给定的正整数n，计算其二进制表示中1的个数是一个经典问题。以下关于计算二进制中1的个数的算法复杂度的说法中，正确的是（）。A.使用位运算的方法，复杂度可以达到O(n)B.使用除以2的方法，复杂度可以达到O(logn)C.使用查找表的方法，复杂度可以达到O(1)D.任何方法都无法在优于O(logn)的复杂度下完成计算11.在一个无向图中，如果存在一个点集S，满足对于图中任意两个不同的点u和v，要么u和v都在S中，要么u和v都不在S中，且S中任意两个不同的点都是相邻的，则称S为图的一个独立集。以下关于无向图独立集的说法中，正确的是（）。A.空集是任何图的独立集B.如果一个图有最大独立集大小k，那么该图至少有k个点C.一个图的独立集一定不是它的生成树D.完全图Kn的最大独立集大小为112.假设有n个任务需要在一个单核处理器上执行，每个任务i有一个处理时间ti（ti>0）和一个截止时间di（di>0）。如果任务执行时间超过其截止时间，则产生罚款。目标是在不违反任何任务截止时间的前提下，找到一个任务执行顺序，使得所有任务的总罚款最小。以下关于该问题的说法中，正确的是（）。A.这是一个经典的贪心问题，可以通过按任务处理时间升序排列解决B.这是一个经典的贪心问题，可以通过按任务截止时间升序排列解决C.这是一个NP完全问题，没有多项式时间的精确算法D.如果所有任务的截止时间都相同，问题简化为使总处理时间最小13.在一个由m个节点组成的集合中，定义一个“生成树”为：包含所有m个节点的一个无环连通子图。在一个无向连通图中，可能存在多个不同的生成树。以下关于生成树的性质中，错误的是（）。A.任何无向连通图都至少存在一个生成树B.一个无向连通图的生成树数量是有限的C.所有权重相同的边组成的生成树是唯一的D.Kruskal算法和Prim算法都能找到最小生成树14.设A是一个n×n的矩阵，B是另一个m×m的矩阵。定义矩阵C=A*B的(i,j)元素为：C[i][j]=Σ(k=1ton)A[i][k]*B[k][j]。以下关于矩阵乘法复杂度的说法中，正确的是（）。A.使用朴素算法计算C的复杂度为O(nm)B.使用Strassen算法计算C的复杂度可以达到O(n^2.807)C.使用分块矩阵乘法，可以在O(n^2logn)复杂度下计算CD.矩阵乘法是可并行化的，可以在O(n^2)复杂度下完成15.在一个字符串S中，定义一个“回文子串”为：S中连续的字符序列，该序列正读和反读都相同。例如，在字符串"abba"中，"aba"、"bb"、"abba"都是回文子串。以下关于字符串回文子串的说法中，正确的是（）。A.任何长度大于1的字符串至少有一个回文子串B.一个字符串的所有字符都相同，则其所有子串都是回文子串C.计算字符串S的所有回文子串数量的问题是P问题D.使用动态规划可以在O(n^2)复杂度下找到字符串S的所有回文子串二、多项选择题（每题有多个正确选项，请将所有正确选项的字母填在题后的括号内。每题3分，共30分）1.以下关于有向无环图（DAG）的拓扑排序的说法中，正确的是（）。A.一个DAG的拓扑排序结果唯一当且仅当该DAG是树B.拓扑排序是对DAG中所有顶点的一个线性排列C.如果对一个DAG进行深度优先搜索，并按退出栈的顺序输出顶点，则可以得到一个拓扑排序D.拓扑排序可以用来判断一个有向图中是否存在环2.在一个无向图中，如果存在一个点集S，使得图中的所有边都至少与S中的一个点关联，则称S为图的一个“点覆盖”。以下关于无向图点覆盖的说法中，正确的是（）。A.空集是任何图的点覆盖B.如果一个图是连通的，那么它的点覆盖数量至少为2C.一个图的最大点覆盖大小等于其补图的最小顶点覆盖大小D.对于任何无向图，其点覆盖数量总是小于或等于其边数3.给定一个包含n个元素的序列，定义该序列的“最长不下降子序列”（LIS）为其子序列中元素严格递增或相等的元素个数的最大值。例如，序列[3,2,6,4,5,1]的LIS长度为4（子序列[2,4,5]或[3,4,5]或[3,6]或[2,6]等）。以下关于LIS的说法中，正确的是（）。A.序列的LIS长度一定小于或等于序列的长度B.一个严格单调递增的序列的LIS长度等于其长度C.计算序列的LIS长度问题可以使用动态规划解决，复杂度可以达到O(nlogn)D.序列的LIS一定是序列的一个连续子序列4.在一个无向连通图中，如果移除某个边及其两个端点后，剩余图不再连通，则该边称为图的“桥”或“割边”。以下关于无向连通图桥的说法中，正确的是（）。A.一个连通图可能没有桥B.如果一个图是树，则所有边都是桥C.移除一条桥会降低图的连通分量数量D.图中所有桥的端点都是关节点5.设f(x)是定义在实数集R上的一个函数，满足对于任意x,y∈R，都有f(x+y)=f(x)+f(y)。这种函数称为“加性函数”。以下关于加性函数的性质中，正确的是（）。A.如果f是加性的，且f(1)=c，那么对于任意整数n，都有f(n)=ncB.如果f是加性的，且f是奇函数（f(-x)=-f(x)），那么对于任意有理数q=p/q（p,q为整数，q>0），都有f(q)=(p/q)cC.任何加性函数都是线性的D.如果f是加性的，那么f(0)=06.在一个字符串S中，定义一个“子串”为：S中连续的字符序列。定义两个字符串A和B的“LCS”为：A和B的子串的最长公共子序列。例如，字符串"ABCBDAB"和"BDCABB"的LCS为"BCAB"。以下关于字符串LCS的说法中，正确的是（）。A.任何字符串S与自身比较，其LCS长度等于S的长度B.如果字符串A和B没有公共字符，则它们的LCS长度为0C.计算字符串A和B的LCS问题可以使用动态规划解决，复杂度可以达到O(|A|*|B|)D.LCS问题是NP完全问题7.在一个由m个节点和n条边组成的无向图中，如果存在一个点集S，使得图中的所有环都至少与S中的一个点关联，则称S为图的一个“点割”或“割集”。以下关于无向图点割的说法中，正确的是（）。A.空集不可能是任何图的点割B.一个连通图的最小点割（点数最少）的大小等于其最大点覆盖的大小C.如果一个图是树，那么它的点割就是其关节点集D.对于任何无向图，其点割数量总是小于或等于其边数8.假设要在一张地图上用最少的折线段绘制所有城市对之间的通信线路，要求任意两条线路不相交（可能在城市点处相交，但在空中不相交）。以下关于该问题的说法中，正确的是（）。A.这是一个欧拉回路问题B.这是一个欧拉路径问题C.如果所有城市都是偶度点，则问题有解且解唯一D.如果存在奇度点，则问题无解9.在一个序列中，定义“子序列”为：通过删除零个或多个元素（不改变剩余元素的相对顺序）得到的新序列。例如，序列[1,3,2,4]的子序列有[1,2,4]、[3,4]等。以下关于序列子序列的说法中，正确的是（）。A.一个序列的长度为n，则其子序列的总数为2^nB.任何序列都至少有两个子序列（空序列和自身）C.计算一个序列包含特定模式（如"101"）的子序列数量是困难的D.序列的子序列一定是序列的连续子序列10.在一个无向连通图中，定义一个“双连通分量”或“BiconnectedComponent”为：图的一个最大连通子图，其中任意两个顶点之间都存在至少两条不交叉的路径（即移除该子图中的任何单个顶点，子图仍然连通）。以下关于无向连通图双连通分量的说法中，正确的是（）。A.双连通分量中不包含关节点B.双连通分量的边界（即该分量与外部顶点相连的顶点集合）是它的关节点集C.一个连通图可以包含多个双连通分量D.如果一个图是树，则它没有双连通分量三、判断题（请判断下列说法的正误，正确的填“√”，错误的填“×”。每题1分，共20分）1.在一个有向图中，如果存在一个环，那么该环上的所有顶点都是该图的一个强连通分量。（×）2.如果一个无向图是连通的，并且其边数等于其点数减1，那么该图一定包含一个汉密尔顿回路。（×）3.对于任何两个不同的正整数a和b，它们的最大公约数与最小公倍数的乘积等于a与b的乘积。（√）4.在一个无向图中，如果移除一个顶点后，图变得不连通，那么该顶点一定是图的关节点。（√）5.一个图的邻接表表示比邻接矩阵表示更节省空间，当该图是稀疏图时尤其如此。（√）6.任何有向图都可以进行拓扑排序。（×）7.在一个序列中，严格单调递增的序列没有局部极值点。（√）8.如果一个图的生成树是唯一的，那么该图的边权重一定各不相同。（×）9.计算一个字符串的所有子串的数量是O(n)复杂度的。（×）10.矩阵乘法可以使用分治法在O(n^1.585)复杂度下完成。（√）11.一个图的点覆盖一定包含该图的所有关节点。（×）12.一个图的最大独立集与该图的最小点覆盖的点数之和等于该图的顶点总数。（√）13.在一个无向图中，如果存在一条边u-v，使得移除该边后图变得不连通，那么u和v一定是关节点。（×）14.对于任何序列，其最长不下降子序列（LIS）一定是唯一的。（×）15.如果一个无向图是欧拉图（存在欧拉回路），那么该图的所有顶点度数都为偶数。（√）16.如果一个无向图的所有顶点度数都小于等于2，那么该图是树。（×）17.加性函数f(x+y)=f(x)+f(y)必然满足f(x)=cx的形式，其中c是常数。（×）18.字符串的最长公共子序列（LCS）一定是两个字符串的连续子串的公共部分。（×）19.在一个无向图中，如果存在一个点集S，使得图中的所有边都至少与S中的一个点关联，那么S的补点集也是一个点覆盖。（√）20.在一个双连通分量中，移除任意一个顶点后，剩余部分仍然是双连通的。（×）试卷答案一、选择题1.B2.D3.A4.B5.A6.B7.B8.D9.A10.B11.A12.C13.C14.B15.B解析1.B:关节点定义是移除后图不连通，但移除关节点不一定需要移除边，只要移除该点即可。A不一定，树只有一个关节点。C树所有点都是关节点。D无向图关节点度数至少为1（若为0则移除后图仍连通）。2.D:A全是常数。B单调递增无极值。C全是常数。D1,3,2,4中1->3上升,3->2下降,2->4上升,4->1上升,4->2下降,1->2上升，共有5个。3.A:DAG可能没有环，如树。BDAG可能存在多个拓扑排序。CBFS按访问顺序输出是拓扑排序。DBFS用于查找环。4.B:f(0)=f(0+0)=f(0)+f(0),故f(0)=0。f(1)=f(1+0)=f(1)+f(0),故f(1)=1。5.A:连通图移除点数最少的点集使其不连通，该点集大小至少为2（除单个点图），所以边数至少n-1。m>=n-1。n个点的树有n-1边。连通图至少有n-1边。6.B:1是子串。子序列不要求连续。LIS不要求连续。7.B:f(x)=x满足条件。f(1)=1。f(n)=f(1+1+...+1)=nf(1)=n。8.B:需要至少两条线路相交，即至少3条线路。奇度点需要出度入度平衡，至少有奇数条线路，无法满足所有线路不相交。9.C:LIS可以使用二分+贪心解决，复杂度O(nlogn)。10.A:朴素算法O(n^3)。Strassen算法O(n^2.807)。分块O(n^2logn)。11.A:S是点覆盖，所有边至少关联S中点。S补集所有边不关联S中点，即不关联S补集中点，所以S补集是点覆盖。12.B:最小点割点数=最大匹配点数=点覆盖点数。最小割割集大小=最大流流量=最小点覆盖点数。13.B:任何图都有生成树。最小生成树不唯一，只要满足生成树性质即可。14.B:朴素算法O(n^3)。LCS可以使用动态规划O(n*m)。15.B:1是子串。子序列不要求连续。16.A:双连通分量无关节点。移除一个点仍连通，说明该点不是关节点。17.A:f(0)=0,f(1)=f(1+0)=f(1)+f(0)=f(1),故f(1)=0。所以f(x)=0x=0对所有整数x成立。18.A:LIS不要求连续。LCS不要求连续。19.B:移除一个点仍连通，说明该点不是关节点。双连通分量无关节点。20.A:移除一个点后，剩余部分可能变为多个连通分量，不再是双连通的。二、多项选择题1.B,C2.A,C3.A,B,C4.A,B,C5.A,B6.A,B,C7.A,B,C8.B,D9.A,B,C10.A,B,C解析1.B:DAG是强连通当且仅当是单点环。拓扑排序输出顺序是线性排列。BFS按访问顺序输出是拓扑排序。拓扑排序用于判断无环。2.A:空集是任何图的点覆盖。C最小点覆盖=最大匹配。D点覆盖点数<=边数（每个边至少关联一个覆盖点，覆盖点数<=边数/2，边数<=2*点覆盖点数）。3.A:LIS>=1。BLIS>=max(seq)。CLIS可以使用二分+贪心O(nlogn)。DLIS不要求连续。4.A:连通图可以无桥。B树所有边都是桥（移除桥图不连通）。C移除桥u-v，uv属于同一连通分量，移除后uv不在同一分量，连通分量数增加。D桥的端点一定是关节点（移除桥u-v，uv属于同一分量，移除v，uv不在同一分量，v是关节点。移除u同理）。5.A:f(n)=f(1+1+...+1(n个))=nf(1)=nc。B奇函数且加性，f(x)=f(x+y-y)=f(x)+f(-y)=-f(y)+f(-y)=0。f(q)=f(p/q)=f(p)+f(-q)=pf(1)-qf(1)=(p-q)c。C反例f(x)=x^2是加性的但不是线性的。Df(x+y)=f(x)+f(y),f(0)=f(0+0)=f(0)+f(0),f(0)=0。6.A:LCS(S,S)=max(len(subseq(S)))=len(S)。BLCS(A,B)=0当且仅当A,B无公共字符。CLCS可以使用动态规划O(n*m)。DLCS不要求连续。7.A:空集不是点割。C最小点割=最大点覆盖。D点割数量<=边数（每个边至少关联一个割点，割点点数<=边数/2，边数<=2*点割点数）。8.B:需要至少两条线路相交，即至少3条线路。D奇度点需要出度入度平衡，至少有奇数条线路，无法满足所有线路不相交。9.A:子序列删除任意元素，2^n个。B空序列和自身。C模式101，可以枚举起点，检查模式匹配，O(n^3)。D子序列不要求连续。10.A:双连