NOIP提高组C++试题.docx

1、NOIP提高组C+试题第二十一届全国青少年信息学奥林匹克联赛初赛提高组 C+语言试题竞赛时间：2015 年 10 月 11 日 14:3016:30选手注意： 试题纸共有 9 页，答题纸共有 2 页，满分 100 分。请在答题纸上作答，写在试题纸上的 一律无效。 不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。一、单项选择题（共 15 题，每题 1.5 分，共计 22.5 分；每题有且仅有一个正确 选项）1. 在计算机内部用来传送、存贮、加工处理的数据或指令都是以（ ）形式进行的。A.二进制码B.八进制码C.十进制码D.智能拼音码2. 下列说法正确的是（ ）。A.CPU

2、的主要任务是执行数据运算和程序控制B.存储器具有记忆能力，其中信息任何时候都不会丢失C.两个显示器屏幕尺寸相同，则它们的分辨率必定相同D.个人用户只能使用 Wifi 的方式连接到 Internet3. 与二进制小数 0.1 相等的十六进制数是（ ）。A.0.8B.0.4C.0.2D.0.14. 下面有四个数据组，每个组各有三个数据，其中第一个数据为八进制数，第二个数据为 十进制数，第三个数据为十六进制数。这四个数据组中三个数据相同的是（ ）。A.120 82 50B.144 100 68C.300 200 C8D.1762 1010 3F25. 线性表若采用链表存储结构，要求内存中可用存储单元

3、地址（ ）。A.必须连续B.部分地址必须连续C.一定不连续D.连续不连续均可6. 今有一空栈 S，对下列待进栈的数据元素序列 a,b,c,d,e,f 依次进行进栈，进栈，出栈， 进栈，进栈，出栈的操作，则此操作完成后，栈 S 的栈顶元素为（ ）。A.fB.cC.aD.b7. 前序遍历序列与后序遍历序列相同的二叉树为（ ）。A.非叶子结点只有左子树的二叉树B.只有根结点的二叉树C.根结点无右子树的二叉树D.非叶子结点只有右子树的二叉树8. 如果根的高度为 1，具有 61 个结点的完全二叉树的高度为（ ）。A.5B.6C.7D.89. 6 个顶点的连通图的最小生成树，其边数为（ ）。A.6B.5C

4、.7D.410. 设某算法的计算时间表示为递推关系式 T(n) = T(n - 1) + n（n 为正整数）及 T(0) = 1，则 该算法的时间复杂度为（ ）。A.O(log n)B.O(n log n)C.O(n)D.O(n2)11. 具有 n 个顶点，e 条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运 算的时间复杂度均为（ ）。A.(n2)B.(e2)C.(ne)D.(n + e)12. 在数据压缩编码的应用中，哈夫曼（Huffman）算法是一种采用了（ ）思想的算法。A.贪心B.分治C.递推D.回溯13. 双向链表中有两个指针域，llink 和 rlink，分别指回前驱及

5、后继，设 p 指向链表中的 一个结点，q 指向一待插入结点，现要求在 p 前插入 q，则正确的插入为（ ）。A.p-llink = q; q-rlink = p;p-llink-rlink = q; q-llink = p-llink;B.q-llink = p-llink; p-llink-rlink = q; q-rlink = p; p-llink = q-rlink;C.q-rlink = p; p-rlink = q;p-llink-rlink = q; q-rlink = p;D.p-llink-rlink = q; q-rlink = p;q-llink = p-llink; p

6、-llink = q;14. 对图 G 中各个结点分别指定一种颜色，使相邻结点颜色不同，则称为图 G 的一个正常 着色。正常着色图 G 所必需的最少颜色数，称为 G 的色数。那么下图的色数是（ ）。A.3B.4C.5D.615. 在 NOI 系列赛事中参赛选手必须使用由承办单位统一提供的设备。下列物品中不允许选 手自带的是（ ）。A.鼠标B.笔C.身份证D.准考证二、不定项选择题（共 5 题，每题 1.5 分，共计 7.5 分；每题有一个或多个正确 选项，多选或少选均不得分）1. 以下属于操作系统的有（ ）。A.Windows XPB.UNIXC.LinuxD.Mac OS2. 下列属于视频文

7、件格式的有（ ）。A.AVIB.MPEGC.WMVD.JPEG3. 下列选项不是正确的 IP 地址的有（ ）。A.202.300.12.4B.192.168.0.3C.100:128:35:91D.111-103-35-214. 下列有关树的叙述中，叙述正确的有（ ）。A.在含有 n 个结点的树中，边数只能是(n-1)条B.在哈夫曼树中，叶结点的个数比非叶结点个数多 1C.完全二叉树一定是满二叉树D.在二叉树的前序序列中，若结点 u 在结点 v 之前，则 u 一定是 v 的祖先5. 以下图中一定可以进行黑白染色的有（ ）。（黑白染色：为各个结点分别指定黑白 两种颜色之一，使相邻结点颜色不同。）

8、A.二分图B.完全图C.树D.连通图三、问题求解（共 2 题，每题 5 分，共计 10 分；每题全部答对得 5 分，没有部 分分）1. 在 1 和 2015 之间（包括 1 和 2015 在内）不能被 4、5、6 三个数任意一个数整除的数 有 个。2. 结点数为 5 的不同形态的二叉树一共有 种。（结点数为 2 的二叉树一共有 2种：一种是根结点和左儿子，另一种是根结点和右儿子。）四、阅读程序写结果（共 4 题，每题 8 分，共计 32 分）1. #include using namespace std; struct point int x; int y;int main() struct

9、EXint a; int b; point c; e;e.a = 1;e.b = 2;e.c.x = e.a + e.b;e.c.y = e.a * e.b;cout e.c.x , e.c.y endl; return 0;输出： 2. #include using namespace std;void fun(char *a, char *b) a = b;(*a)+;int main() char c1, c2, *p1, *p2; c1 = A;c2 = a;p1 = &c1; p2 = &c2; fun(p1, p2);cout c1 c2 endl; return 0;输出： 3.

10、 #include #include using namespace std; int main() int len, maxlen; string s, ss; maxlen = 0;do cin ss;len = ss.length(); if (ss0 = #)break;if (len maxlen) s = ss;maxlen = len; while (true); cout s endl; return 0;输入：Iam acitizen of China#输出： 4. #include using namespace std;int fun(int n, int fromPos

11、, int toPos) int t, tot;if (n = 0)return 0;for (t = 1; t n;cout fun(n, 1, 3) endl; return 0;输入：5输出： 五、完善程序（共 2 题，每题 14 分，共计 28 分）1. （双子序列最大和）给定一个长度为 n（3 n 1000）的整数序列，要求从中选出两个 连续子序列，使得这两个连续子序列的序列和之和最大，最终只需输出这个最大和。一 个连续子序列的序列和为该连续子序列中所有数之和。要求：每个连续子序列长度至少 为 1，且两个连续子序列之间至少间隔 1 个数。（第五空 4 分，其余 2.5 分）#incl

12、ude using namespace std;const int MAXN = 1000; int n, i, ans, sum; int xMAXN;int lmaxMAXN;/ lmaxi为仅含 xi及 xi左侧整数的连续子序列的序列和中，最大的序列和 int rmaxMAXN;/ rmaxi为仅含 xi及 xi右侧整数的连续子序列的序列和中，最大的序列和int main() cin n;for (i = 0; i xi;lmax0 = x0;for (i = 1; i n; i+) if (lmaxi - 1 = 0)lmaxi = xi; elselmaxi = lmaxi - 1

13、+ xi; for (i = 1; i n; i+)if (lmaxi = 0; i-) if (rmaxi + 1 = 0; i-) if (rmaxi rmaxi + 1);ans = x0 + x2;for (i = 1; i ans) ans = sum;cout ans endl; return 0;2. （最短路径问题）无向连通图 G 有 n 个结点，依次编号为 0,1,2,.,(n-1)。用邻接矩阵的 形式给出每条边的边长，要求输出以结点 0 为起点出发，到各结点的最短路径长度。使用 Dijkstra 算法解决该问题：利用 dist 数组记录当前各结点与起点的已找到的最 短路径长

14、度；每次从未扩展的结点中选取 dist 值最小的结点 v 进行扩展，更新与 v 相邻 的结点的 dist 值；不断进行上述操作直至所有结点均被扩展，此时 dist 数据中记录的值 即为各结点与起点的最短路径长度。（第五空 2 分，其余 3 分）#include using namespace std;const int MAXV = 100; int n, i, j, v;int wMAXVMAXV; / 邻接矩阵，记录边长/ 其中 wij为连接结点 i 和结点 j 的无向边长度，若无边则为-1 int distMAXV;int usedMAXV; / 记录结点是否已扩展（0：未扩展；1：已扩

15、展）int main() cin n;for (i = 0; i n; i+) for (j = 0; j wij; dist0 = 0;for (i = 1; i n; i+) disti = -1;for (i = 0; i n; i+) usedi = 0;while (true) ;for (i = 0; i n; i+)if (usedi != 1 & disti != -1 & (v = -1 | );if (v = -1) break;for (i = 0; i n; i+)if (wvi != -1 & (disti = -1 | ) disti = distv + wvi;for (i = 0; i n; i+) cout disti endl;return 0;