NOIP2022提高组C++初赛试题.doc

《NOIP2022提高组C++初赛试题.doc》由会员分享，可在线阅读，更多相关《NOIP2022提高组C++初赛试题.doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、NOIP2022进步组C+初赛试题第二十二届全国青少年信息学奥林匹克联赛初赛 进步组 C+语言试题 竞赛时间：20_ 年 10 月 22 日 14:3016:30 选手注意: 试题纸共有 13 页，答题纸共有 2 页，总分值 100 分。请在答题纸上作答，写 在试题纸上的一律无效。 不得使用任何电子设备如计算器、手机、电子词典等或查阅任何书籍资料。一、单项选择题共 15 题，每题 1.5 分，共计 22.5 分；每题有且仅有一个正确 选项1.以下不是微软公司出品的软件是 。.Powerpoint .Word .E_cel .Acrobat Reader 2.假如开场时计算机处于小写输入状态，如

2、今有一只小老鼠反复按照 CapsLock、字母键 A、字母键 S 和字母键 D 的顺序来回按键，即 CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、，屏幕上输出的第 81 个字符是字母 。.A .S .D .A 3.二进制数 00100 和 00 异或的结果是 。.00000 .0001 .01000100 .00111000 4.与二进制小数 0.1 相等的八进进制数是 。.0.8 .0.4 .0.2 .0.1 5.以比拟作为根本运算，在 N 个数中找最小数的最少运算次数为 。.N .N-1 .N2 .log N 6.表达式

3、a_(b+c)-d 的后缀表达形式为 。.abcd_+- .abc+_d- .abc_+d- .-+_abcd 7.一棵二叉树如右图所示，假设采用二叉树链表存储该二叉 树各个结点包括结点的数据、左孩子指针、右孩子指 针。假如没有左孩子或者右孩子，那么对应的为空指针。那么该链表中空指针的数目为 。A.6 B.7 C.12 .14 8.G 是一个非连通简单无向图，共有 28 条边，那么该图至少有 个顶点。.10 .9 .8 .7 CCF NOIP20_ 初赛进步组 C+语言试题 第 1 页，共 13 页 9.某计算机的 和内存之间的地址总线宽度是 32 位bit，这台计算机最 多可以使用 的内存。

4、A.2GB B.4GB C.8GB D.16GB 10.有以下程序：#include using namespace std; int main int k = 4, n = 0; while (n 。假如 L 中存在 _ i1 _i+1 _n， 那么称 L 是单峰的，并称 _i 是 L 的 “峰顶”。如今 L 是单峰的，请把 a-c 三行代码补全到算法中使得算法 正确找到 L 的峰顶。a.Search(k+1, n) b.Search(1, k-1) c.return Lk Search(1, n) 1.k n/2 2.if Lk Lk-1 and Lk Lk+1 3.then _4.els

5、e if Lk Lk-1 and Lk using namespace std; int main int a6 = 1, 2, 3, 4, 5, 6; int pi = 0; int pj = 5; int t , i; while (pi using namespace std; int main char a100100, b100100; string c100; string tmp; int n, i = 0, j = 0, k = 0, total_len100, length1003; CCF NOIP20_ 初赛进步组 C+语言试题 第 5 页，共 13 页 cin n; g

6、etline(cin, tmp); for (i = 0; i = lengthi2) cout lengthi1) break; if (j = lengthi2) cout using namespace std; int lps(string seq, int i, int j) int len1, len2; if (i = j) return 1; if (i j) return 0; if (seqi = seqj) return lps(seq, i + 1, j - 1) + 2; len1 = lps(seq, i, j - 1); len2 = lps(seq, i + 1

7、, j); if (len1 len2) return len1; return len2; int main string seq = “acmerandacm“; int n = seq.size; cout #include using namespace std; int map100100; int sum100, weight100; int visit100; CCF NOIP20_ 初赛进步组 C+语言试题 第 7 页，共 13 页 int n; void dfs(int node) visitnode = 1; sumnode = 1; int v, ma_w = 0; fo

8、r (v = 1; v ma_w) ma_w = sumv; if (n - sumnode ma_w) ma_w = n - sumnode; weightnode = ma_w; int main memset(map, 0, sizeof(map); memset(sum, 0, sizeof(sum); memset(weight, 0, sizeof(weight); memset(visit, 0, sizeof(visit); cin n; int i, _, y; for (i = 1; i _ y; map_y = 1; mapy_ = 1; dfs(1); int ans

9、= n, ansN = 0; for (i = 1; i using namespace std; #define MA_N 20_00 #define infinity 2147483647 int answerMA_N, heightMA_N, previousMA_N, ne_tMA_N; int rankMA_N; int n; void sort(int l, int r) int _ = heightrank(l + r) / 2, i = l, j = r, temp; while (i _) j-; if ( (1) ) temp = ranki; ranki = rankj;

10、 rankj = temp; CCF NOIP20_ 初赛进步组 C+语言试题 第 9 页，共 13 页 i+; j-; if (i n; int i, higher, shorter; for (i = 1; i heighti; ranki = i; sort(1, n); for (i = 1; i = 2; i-) higher = shorter = infinity; if (previousi !=0) shorter = heighti - heightpreviousi; if (ne_ti != 0) (3) ; if ( (4) ) answeri = previousi

11、; else answeri = ne_ti; ne_tpreviousi = ne_ti; (5) ; for (i = 2; i 1)个城市因地震而导致交通中断时，首都到多少个城市的最短途径长度会发生改变。假如因为无法通过第 i 个城市而导致从首都出发无法到达某个城 CCF NOIP20_ 初赛进步组C+语言试题 第 10 页，共 13 页 市，也认为到达该城市的最短途径长度改变。对于每一个城市 i，假定只有第 i 个城市与外界交通中断，输出有多少个 城市会因此导致到首都的最短途径长度改变。我们采用邻接表的方式存储图的信息，其中 head_表示顶点 _ 的第一条 边的编号，ne_ti表示第

12、 i 条边的下一条边的编号，pointi表示第 i 条边的终点，weighti表示第 i 条边的长度。第一空 2 分，其余 3 分#include #include using namespace std; #define MA_N 6000 #define MA_M 100000 #define infinity 2147483647 int headMA_N, ne_tMA_M, pointMA_M, weightMA_M; int queueMA_N, distMA_N, visitMA_N; int n, m, _, y, z, total = 0, answer; void link

13、(int _,int y,int z) total+; ne_ttotal = head_; head_ = total; pointtotal = y; weighttotal = z; total+; ne_ttotal = heady; heady = total; pointtotal = _; weighttotal = z; int main int i, j, s, t; cin n m; for (i = 1; i _ y z; link(_, y, z); for (i = 1; i = n; i+) disti = infinity; (1) ; queue1 = 1; v

14、isit1 = 1; s = 1; CCF NOIP20_ 初赛进步组 C+语言试题 第 11 页，共 13 页 t = 1; / 使用 SPFA 求出第一个点到其余各点的最短路长度 while (s = t) _ = queues MA_N; j = head_; while (j != 0) if ( (2) ) distpointj = dist_ + weightj; if (visitpointj = 0) t+; queuet MA_N = pointj; visitpointj = 1; j = ne_tj; (3) ; s+; for (i = 2; i = n; i+) qu

15、eue1 = 1; memset(visit, 0, sizeof(visit); visit1 = 1; s = 1; t = 1; while (s = t) / 判断最短路长度是否不变 _ = queues; j = head_; while (j != 0) if (pointj != i (4) visitpointj = 0) (5) ; t+; queuet = pointj; j = ne_tj; s+; answer = 0; for (j = 1; j = n; j+) answer += 1 - visitj; cout i “:“ answer - 1 endl; CCF NOIP20_ 初赛进步组 C+语言试题 第 12 页，共 13 页 return 0; CCF NOIP20_ 初赛进步组 C+语言试题 第 13 页，共 13 页 第 6 页 共 6 页