2014NOIP初赛解题报告

《2014NOIP初赛解题报告》由会员分享，可在线阅读，更多相关《2014NOIP初赛解题报告（5页珍藏版）》请在金锄头文库上搜索。

1、2014NOIP 初赛解题报告一 选择题。1. 考点：程序设计语言。计算机语言的发展：机器语言（由 0 和 1 组成）汇编语言（ “认机器” ）高级语言高级语言：（1）面向过程语言（ C、pascal） （2 ）面向对象语言（VB、C+、Java）2. 考点：计算机基础知识。 TBGBMBKBB （210=1024）3. 考点：二进制的加法运算。 按位运算：0+0=0 0+1=1 1+1=10（前一位加 1）4. 考点：网络协议。（1 ）网络协议：网络上通信的两台计算机之间共同遵守的规则和约定，以确保发送和接收数据的有序和准确。（2 ）网络协议有很多种，但是相互通信的两台计算机必须遵守同一个协

2、议。（3 ）网络协议其实是安装在电脑里的”软件”。（4 ）网络协议采用分层体系结构，不同层解决不同的问题，下层服务上层，对等层间进行通信。（5 ） OSI 模型（网络参考模型）：物理层数据链路层 网络层传输层会话层表示层应用层（6 ） TCP/IP 协议：目前最通用的网络协议。（数据链路层网络层（如：IP 协议）传输层（TCP 协议或 UDP 协议）应用层（HTTP、FTP 、 SMTP、POP3 等协议）5. 考点：IP 地址格式。IPV4（32 位二进制）的 IP 地址格式：0255. 0255. 0255. 0255IPV6（128 位二进制）的 IP 地址格式：分为 8 组，每组由 4

3、 个十六进制数表示6. 考点：无向图的特征。度数之和是边数的 2 倍。解题办法：举例法，线段是最简单的无向图。（有向图的特征。出度之和或入度之和是边数的 1 倍。最简单的有向图“箭头” ）7. 考点：有序链表的顺序检索。（1 ） 明确条件：有序、概率相等。 （2）求：平均检索长度。 （用 n 表达） （3 ）解题方法：举例（如：1,2,3,4）归纳为用 n 表示8. 考点：编译器的主要功能是将源程序翻译成指令。 （源程序目标程序）9. 考点：二进制转换为十进制。22+21+20+2(-1)+2(-2)10. 考点：运算顺序和函数功能。Trunc（x）:取整数部分 Round（x）:四舍五入，取

4、整数部分11. 考点：指针与链表。指针：用来存放位置信息。链表：是分散的数据“环环相扣” 。解题方法：（1）画图辅助。 （新的箭头指向） （2 ）注意赋值顺序是否正确。12. 考点：查找。 （1）明确题意： 2n 个数、最少（理想状态：可尝试把大问题分解为小问题。 ） 、比较次数解题方法：（1）分成 N 组，两两比较，共比较 N 次。 （2）A 组：放比较后小的数，B 组：放比较后大的数。（3 ）在 A 组中找出最小值。 （需比较 N-1 次） （4）在 B 组中找出最大值。 （需比较 N-1 次）（4 ）一共需要比较 3N-1 次。13. 考点：完全图与生成树概念。完全图：所以点之间都有边相

5、连的无向图。 （6*5 / 2 =15（条边） ）生成树：除了“根结点” ，其他点都是“长”出来的，有且只有“一枝” 。 （6-1=5（条边） ）14. 考点：排序算法的时间复杂度。快速排序、堆排序、归并排序：将大问题分解为小问题解决。 （特点：分组、递归）时间复杂度 O（nlog 2n）插入排序、冒泡排序、选择排序：在原来的“队列”比较、交换数值进行排序。时间复杂度 O（n 2） （1 ） 插入排序：保证当前已排序的数处于“最佳位置” 。N 个数需进行 N 趟排序，每趟添加一个数，第 i 趟都需要对 i 个数进行位置的“微调” 。（2 ） 归并排序：分组（最小单位）合并（多组“同时进行” ，

6、所以减少时间复杂度） ，用递归实现。（3 ） 冒泡排序： 按顺序“寻找”每一个位置的数是哪一个（该数通过“小步挪动” ，即与相邻数交换位置，一步步“爬上来” ） ，共需要 N-1 趟。（4 ） 选择排序： 按顺序“寻找”每一个位置的数是哪一个（先“决选”出唯一合适的数，再“大步跨越”到准确位置） ，共需要 N-1 趟。15. 考点：排序算法的变形。解题方法：明确条件：n 个数、不等、最坏情况下（倒序） 、找到第 N 小元素。求：比较次数。 找出比较数的语句固定数的比较语句 +非固定数的比较语句（循环结构中）最坏情况（使循环执行最多次） 1【 固定】+ 2*（n-3+1） 【非固定 】= 2n-

7、3 二 不定项选择题1. 考点：逻辑运算。运算顺序：非与或 （负乘加）2. 考点：操作系统软件。Oracle 为数据库管理系统。3. 考点：比赛规则。4. 考点：图的存储。 （1）邻接矩阵（用“表”的形式存储每个点相互间的关系） （2）用 N 个“数组”存储以每个点为起点的 N 条“路径” ）5. 考点：数的表示。无符号十进制：0255 （8 位） 有符号十进制：-127127（1 位符号，7 位数值）三 问题求解1. 考点：组合排列。解题方法：分情况考虑：36+36+6+24=102（个）（1 ） 有两个 1 组成：四个位置选两个放 1（(4*3)/(2*1)=6，其他三个数中的两个 3*2

8、=6，所以，6*6=36（个）（2 ） 有两个 8 组成：与（ 1）同理，所以共 36 个（3 ） 由两个 1 和两个 8 组成，即任选两个位置放 1，剩下位置直接放 8：(4*3)/(2*1)=6（个）（4 ） 组成的四个数各不相同：4*3*2*1=24（个）2. 考点：求图的最短路径。参考算法：Dijkstra 算法，用来计算从一个点到其他所有点的最短路径的算法，主要是每趟解决起点到图中一个点的最短路径，直到所有点都解决。具体思路应用如下：（1 ） 从 A 出发，与 A 相连的有 B、F、G ，具有最短路径是 B，AB 路径形成，通过 B 可到达 C 和 H（2 ） 与 A“相连”的点 F

9、、G、C、H，具有最短路径的是 C 和 G，任选一个点确定，如 C，AC 形成，通过C 可到达 D 和 I，并可修改 A 到 F 的路径（3 ） 与 A“相连”的点有 F、G、H、 D、I，具有最短路径的是 G，AG 路径形成，通过 G 可修改 A 到 H的路径（4 ） 与 A“相连”的点有 F、H 、D、I，具有最短路径的是 G，AG 路径形成，具有最短路径的是 F，A F路径形成，通过 F 可修改 A 到 H 的路径（5 ） 与 A“相连”的点有 H、 D、I，具有最短路径的是 H，AH 路径形成，通过 G 可修改 A 到 D、I 的路径（6 ） 与 A“相连”的点有 D、I，具有最短路径

10、的是 D，AD 路径形成，通过 D 可到达 E（7 ） 与 A“相连”的点有 I、E ，具有最短路径的是 I， A路径形成，通过 D 可到达 E四、阅读程序写结果(共 4 题，每题 8 分，共计 32 分)1. var【a, b,】 i, tot, 【c1, c2】:integer;/分组变量名，同组作用类似beginreadln(a,b); tot:=0;for i:=a to b do/代入 a 和 b 数值，减少变量个数beginABCDEFGHI11364 2854934742 c1:=i div 10;/识别功能：提取个位数c2:=i mod 10; /识别功能：提取十位数if (c

11、1+c2) mod 3=0 then/当个位数与十位数之和与 3 整除时inc(tot);/累加：满足条件加 1（计算个数）end;writeln(tot);/输出语句：（要填写的结果）end.输入:7 31输出:_2. 考点：递归函数varn, m:integer;function fun(n, minNum, maxNum : integer): integer; /代入数值，减少变量个数var tot, i:integer;beginif n=0 then/最简单的情况exit(1);/退出函数，函数值为 1tot:=0;/tot 初始化for i:=minNum to maxNum d

12、o/代入数值，减少变量个数tot:=tot + fun(n-1, i+1, maxNum);/tot 累加；递归函数，与多个 n-1 时的值有关系exit(tot);end;beginreadln(n, m);writeln(fun(m, 1, n);/输出语句（函数值） ；代入数值，减少变量个数end.输入:6 3输出:_3.考点：冒泡排序的变形。 constSIZE=100;Var/（1）根据变量名识别变量功能dict:array1.SIZEof string;/代入常量的值；字符串数组rank,ind:array1.SIZEof integer; /代入常量的值；rank 排序；ind

13、标记、位置i, j, n, tmp:integer;/i,j 循环过程中当前位置；tmp 中间值，辅助变量beginreadln(n);/输入数据量（7 个字符串）for i:=1 to n dobeginranki:=i;/状态初始化indi:=i; /状态初始化readln(dicti);/输入数据（结合题目的输入数据）end;for i:=1 to n-1 do/识别程序主体部分的功能for j:=1 to n-i do/两层循环，循环范围 “像”冒泡排序中的if dictindjdictindj+1 then/相邻“字符串”之间的比较begin/如果前一项比较大，则交换位置，所以结果是

14、“从小到大”tmp:=indj;/indj:=indj+1;indj+1:=tmp;/对各字符串的 “序号”进行排序（注意字符串数组的数据未交换位置）end;for i:=1 to n dorankindi:=i;/每个字符串排序后“应该”在的位置for i:=1 to n dowrite(ranki, );writeln;end.输入:2 题：（1 ）划分功能函数和主函数， （2）先阅读主函数，因为程序是从主函数出发的（3）递归：从最简单的情况出发，当 n=0 时的所有函数值为 0，递推出 n=1 时的所有函数值，以此类推，最后推算出 fun(3,1,6)的值7aaaababbbaaaaaa

15、cccaa输出:_4. constSIZE=100;varalive:array1.SIZE of integer;/alive:”还在，还可用” ，判断功能n, m, num, i, j:integer;/根据变量名猜测作用function next(num:integer):integer;/下一个数beginrepeatinc(num);加 1if numn then/n=11,当大于 11 时，则变为 1，类似“时钟”的轮回num:=1;until alivenum0;/用“轮回”的方式找到“还可用”的数exit(num);/以找到的数为函数值end;begin/（ 1）从主函数开始阅读read(n, m);for i:=1 to n doalivei:=1;/数据初始化num:=1;/数据初始化（从 1 开始）for i:=1 to n do/代入变量值，减少变量个数；第一层循环beginfor j:=1 to m-1 do/代入变量值，m=1=2(每隔一个数) ；第二层循环num:=next(num);/根据函数名猜测功能（下一个） ；阅读函数判断功能write(num,