全国青少年信息学奥赛初赛试题解析（2017）

"NOIP2017-初赛-提高组-带答案.pdf" 这篇内容涉及全国信息学奥林匹克联赛初赛的试题，适合于准备此类比赛的学生和教练。题目涵盖了计算机编程、算法、数据结构、逻辑推理等多个方面，具有很高的学习价值。 1. NOIP竞赛自2020年起不再支持Pascal语言，这表明竞赛语言更新换代的趋势，参赛者需要关注和支持的语言变化。 2. 在8位二进制补码中，10101011代表的负数是-85。二进制补码用于表示有符号整数，最高位为符号位，1表示负数，转换时需进行反码加1操作。 3. 计算图像存储空间：分辨率为1600x900，16位色的位图，每个像素需要16/8=2字节，总面积为1600*900*2字节=2880000字节，即约2812.5KB。 4. 日期推算题，2017年10月1日是星期日，1949年10月1日与2017年相差68年，其中非闰年20个，闰年14个，非闰年对星期的影响是7*20=140，闰年对星期的影响是7*14+1=99，总共影响是140+99=239，239除以7余2，所以1949年的10月1日是星期二。 5. 连通图转化为树的条件是删除m-n+1条边，因为树的边数总是比节点数少1。 6. 算法的时间复杂度分析：根据递推关系T(N)=2T(N/2)+NlogN，可以判断这是一个分治算法，时间复杂度为O(NlogN)。 7. 后缀表达式（逆波兰表示法）：表达式a*(b+c)*d转换为后缀表达式是abc+*d，即将运算符置于操作数之后。 8. 构成简单无向连通图的个数可以通过握手定理计算，每个节点至少有一条边，四点构成的无向连通图包括树形结构和环形结构，总共有35种。 9. 分配问题，可以看作是组合问题，使用组合公式C(n+k-1, k-1)，这里n=7，k=4，解得C(10,3)=120。 10. 数列题，根据斐波那契数列的性质，随着n的增大，f[n]将接近黄金分割比例(√5-1)/2。 11. 归并排序两数组A和B，最坏情况下需要比较2n-1次，因为每个元素都需要和另一个数组的所有元素比较一次。 12. 称重问题的算法填充顺序是找到不合格硬币的关键，根据描述，算法应该是先将所有硬币分为三组，所以正确顺序是c(划分三组)，b(用天平称重)，a(合并结果)。 13. 硬币问题的算法设计通常涉及到二分查找的思想，通过逐步缩小范围找出异常硬币。 这些题目展示了信息学竞赛中常见的知识领域，如数据结构、算法、计算理论、逻辑推理和数学应用。解答这些问题需要扎实的计算机科学基础和良好的问题解决能力。