万卷网

NOIP提高组

万卷网> 考级竞赛> 信息学奥赛> NOIP提高组

NOIP提高组

更新时间： 2023-09-02 20:23:05 试题数量： 316

我的练习

顺序练习

随机练习

章节练习

错题练习

题库预览

多选题 CCF NOIP 复赛考试结束后，因（）提出的申诉将不会被受理。

多选题（）的平均时间复杂度为 O(n log n)，其中 n 是待排序的元素个数。

填空题输入：1 1000 10 15输出：_________

填空题输入：6 5 91 42 32 43 24 14 34 55 46 4输出：_________

简答题信息学NOIP提高组编程试题

填空题某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数s1,s2,…,sn，均为0或1。该系统每次随机生成 n 个数 a1,a2,…,an，均为 0 或 1，请用户回答(s1a1+s2a2+…+snan)除以2的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。然而，事与愿违。例如，当 n=4 时，有人窃听了以下 5 次问答：就破解出了密码 s1=_________，s2=_________，s3=_________，s4=_________。

多选题下列程序中，正确计算1,2,…,100 这100个自然数之和sum（初始值为 0）的是（）。

简答题（序列重排）全局数组变量 a 定义如下：Const int SIZE = 100;int a[SIZE],n;它记录着一个长度为 n 的序列a[1],a[2],…,a[n]。现在需要一个函数，以整数 p(1≤p≤n)为参数，实现如下功能：将序列 a 的前 p 个数与后 n–p 个数对调，且不改变这 p 个数（或 n–p 个数）之间的相对位置。例如，长度为 5 的序列 1,2,3,4,5，当 p=2 时重排结果为 3,4,5,1,2。有一种朴素的算法可以实现这一需求，其时间复杂度为 O(n)、空间复杂度为 O(n)：void swap1(int p){ int i, j, b[SIZE]; for (i = 1; i <= p; i++) b[ ( 1) ] = a[i]; //（2 分） for (i = p + 1; i <= n; i++) b[i - p] = a[i]; for (i = 1; i <= n; i++) a[i] = b[i]; }我们也可以用时间换空间，使用时间复杂度为 O(n2)、空间复杂度为 O(1)的算法：void swap2(int p){ int i, j, temp; for (i = p + 1; i <= n; i++) { temp = a[i]; for (j = i; j >= (2) ; j--) //（2 分） a[j] = a[j - 1]; (3) = temp; //（2 分） }}事实上，还有一种更好的算法，时间复杂度为O(n)、空间复杂度为O(1)：void swap3(int p){ int start1, end1, start2, end2, i, j, temp; start1 = 1; end1 = p; start2 = p + 1; end2 = n; while (true) { i = start1; j = start2; while ((i <= end1) && (j <= end2)) { temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j++; } if (i <= end1) start1 = i; else if ( (4) ) { //（3 分） start1 = (5) //（3 分） endl = (6) //（3 分） start2 = j; } else break; }}

填空题输入：abceecba输出：_________

填空题现有一只青蛙，初始时在 n 号荷叶上。当它某一时刻在 k 号荷叶上时，下一时刻将等概率随机跳到1,2,…,k 号荷叶之一上，直至跳到1号荷叶为止。当n=2 时，平均一共跳2次；当 n=3 时，平均一共跳 2.5 次。则当 n=5 时，平均一共跳_________次。

填空题输入：83 2 5 11 12 7 4 106输出：_________

多选题（）属于 NP 类问题。

多选题以 A0 作为起点，对下面的无向图进行深度优先遍历时（遍历的顺序与顶点字母的下标无关），最后一个遍历到的顶点可能是（）。

单选题（）是主要用于显示网页服务器或者文件系统的 HTML 文件内容，并让用户与这些文件交互的一种软件。

单选题目前计算机芯片（集成电路）制造的主要原料是（），它是一种可以在沙子中提炼出的物质。（2012年提高组初赛）