第二篇blog】NOIP2017C++普及组基础部分试题解析https://blog.csdn.net/Prasnip_/article/details/78418070?locationNum=3&fps=1
第二篇blog，已做好奋斗准备。
附：homework是个不可数名词啊，整篇暂时出不完，先出了基础部分哈。
新手解析，见谅，大佬见错一定要指出。
——————————————————————我是更新提示分割线———————————————————————
<第一次更新>基础部分讲解至问题求解。粗体字为答案。
—————————————————————我是华丽丽的正文分割线——————————————————————
一、单项选择题
- 在8 位二进制补码中，10101011 表示的数是十进制下的（B ）。
A. 43 B. -85 C. -43 D. -44
解析：二进制补码首位为符号位，首位为1则是负数，剩下位取反计算并加一2^2+2^4+2^6+1=85。详见《—— - 计算机存储数据的基本单位是（B ）。
A. bit B. Byte C. GB D.KB
解析：没有为什么，1B基本，1b最小，别搞混了。 - 下列协议中与电子邮件无关的是（ C）。
A. POP3 B. SMTP C. WTO D.IMAP
解析：WTO世界贸易组织，初中英语。 - 分辨率为800×600、16 位色的位图，存储图像信息所需的空间为（A）。
A. 937.5KB B. 4218.75KB C. 4320KB D. 2880KB
解析：800*600*16/8=960000B，960000/1024=927.5KB
（16位色代表的含义就是分辨率每一位色占16b） - 计算机应用的最早领域是（A ）。
A. 数值计算 B. 人工智能 C. 机器人 D. 过程控制
解析：第一代计算机ENIAC见此。 - 下列不属于面向对象程序设计语言的是（ A）。
A. C B. C++ C. Java D. C#
解析：C见此，面向过程。 - NOI的中午意思是( B )
A.中国信息学联赛 B. 全国青少年信息学奥林匹克竞赛
C. 中国青少年信息学奥林匹克竞赛 D. 中国计算机协会
解析：不解释，试卷最上面就是答案，纯属刷存在感。 - 2017年10月1日是星期日，1999 年10 月1 日是（ C）。
A. 星期三 B. 星期日 C. 星期五 D. 星期二
解析: 2017-1999=18 中间共5（2000，2004，2008，2012，2016）个闰年，18*365+5=6575，6575%7=2，星期日倒退两天就是星期五。纯数学，错的就肯定是算错啦。 - 甲，乙，丙三位同学选修课程，从4 门课程中，甲选修2 门，乙、丙各选修
3 门，则不同的选修方案共有（C ）种。
A. 36 B. 48 C. 96 D. 192
解析： 甲有6种选择方式，乙，丙各有4种选择方式，6*4*4=96。 - 设G 是有n 个结点、m 条边（n ≤ m）的连通图，必须删去G 的（A ）条
边，才能使得G 变成一棵树。
A. m – n + 1 B. m – n C. m +n D.n-m+1
解析：树的边数为节点数减1，那么就让m=n-1就可以了，故选A。 - 对于给定的序列{ak}，我们把 (i, j) 称为逆序对当且仅当i < j 且ai > aj。那么
序列1, 7, 2, 3, 5, 4 的逆序对数为（ B）个。
A. 4 B. 5 C. 6 D.7
解析：就是大的在前小的在后的数对的数量，五对分别是(7,2),(7,3),(7,5),(7,4),(5,4)故选B。 - 表达式a * (b + c) * d 的后缀形式是（ B）。
A. a b c d * + * B. a b c + * d *
C. a * b c + * d D.b+c*a*d
解析：看百科吧——》后缀表达式 - 向一个栈顶指针为hs 的链式栈中插入一个指针s 指向的结点时，应执行（B）。
A. hs->next = s;
B. s->next = hs; hs = s;
C. s->next = hs->next; hs->next=s;
D.D. s->next = hs; hs = hs->next;
解析：很简单，让s指向hs，再把s赋给hs，就是B。 - 若串S = “copyright”，其子串的个数是（ C）。
A. 72 B. 45 C. 46 D. 36
解析：长度为1的字串9个，长度为2的字串8个，长度为3的字串7个，……以此类推，求和1到9即可，别忘记一个空字串，故选C。（其实看到45，46就可以选46了，就看你有没有加空字串） - 十进制小数13.375 对应的二进制数是（A）。
A. 1101.011 B. 1011.011 C. 1101.101 D. 1010.01
解析：先看整数部分，用2^N次方相加，类似第1题；再看小数部位，用乘2取整法，详见超链，经计算得A。 - 对于入栈顺序为a, b, c, d, e, f, g 的序列，下列（C ）不可能是合法的出栈序
列。
A. a, b, c, d, e, f, g B. a, d, c, b, e, g, f
C. a, d, b, c, g, f, e D. g, f, e, d, c, b, a
解析：实际强模拟即可， 就讲答案吧，a进栈，a出栈，b，c，d进栈，d出栈，答案C第3个出栈为b，可模拟后b上还有c没有出栈，故C不成立。 - 设A 和B 是两个长为n 的有序数组，现在需要将A 和B 合并成一个排好序
的数组，任何以元素比较作为基本运算的归并算法在最坏情况下至少要做
（D ）次比较。
A. n2 B. n log n C. 2n D.2n -1
解析： 最坏情况即两两都判断，合并即2n-1。 - 从( C )年开始，NOIP赛将不再支持Pascal 语言。
A. 2020 B. 2021 C. 2022 D. 2023
解析：不说了，看官网，或戳这儿。 - 一家4口人，至少两个人生日属于同一月份的概率是（C ）（假定每个人
生日属于每个月份的概率相同且不同人之间相互独立）。
A. 1/12 B. 1/144 C. 41/96 D. 3/4
解析：先求任何两个人都不在同月生的概率，A124″ role=”presentation” style=”box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; word-break: break-all; position: relative;”>A412
即为12月中选4个不同月的次数的值，124″ role=”presentation” style=”box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; word-break: break-all; position: relative;”>124
即可能发生的事件总数，A124″ role=”presentation” style=”box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; word-break: break-all; position: relative;”>A412
/124″ role=”presentation” style=”box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; word-break: break-all; position: relative;”>124
=55/96（任意两人都不在同月生的概率），根据对应事件概率1-55/96=41/96。故选C。
- 以下和计算机领域密切相关的奖项是（B ）。
A. 奥斯卡奖 B. 图灵奖 C. 诺贝尔奖 D. 普利策奖
解析：是个OIer应该都知道。
二、问题求解
1.一个人站在坐标（0, 0）处，面朝x 轴正方向。第一轮，他向前走1 单位距离，然后右转；第二轮，他向前走2 单位距离，然后右转；第三轮，他向前走3 单位距离，然后右转……他一直这么走下去。请问第2017 轮后，他的坐标是：（1009，1008）。（请在答题纸上用逗号隔开两空答案）
解析：根据图片示意可列表
| 变值 | 实值 |
|---|---|
| (x,y) | (x,y) |
| +1,0 | 1,0 |
| 0,-2 | 1,-2 |
| -3,0 | -2,-2 |
| 0,+4 | -2,2 |
| +5,0 | 3,2 |
| 0,-6 | 3,-4 |
| -7,0 | -4,-4 |
| 0,+8 | -4,+4 |
| ……. | ……. |
可寻得规律，x每两次绝对值加1，符号改变；y初值0，y每四次加2，每两次变号；2017/2=1008…….1，x绝对值即为1009，2017%4…….1,x符号即为+，得x=1009；（2017-1）/4=504，504*2=1008，y绝对值即为1008，（2017-1）%4…….0，y符号即为+，得y=1008；故得答案(1009，1008)。
2.如右图所示，共有13 个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由1变0，或由0变1）。现在要使得所有的格子中的数字都变为0，至少需要（3）次操作。
解析：没什么好解释的，很容易，第一下操作第三排倒数第二个，第二下操作第三拍第三个（正中间），第三下操作第一排第一个（最上面）。自己多想想就可以明白了。
—————————————————————我是华丽丽的正文分割线——————————————————————
写到爆炸啊！！！！！！！！！！！！！
——————————————————————我是讲废话的分割线———————————————————————
努力写后半部分ing