2014NOIP初赛解题报告.doc

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）网络协议有很多种，但是相互通信的两台计算机必须遵守同一个协议。（3）网络协议其实是安装在电脑里的”软件”。（4）网络协议采用分层体系结构，不同层解决不同的问题，下层服务上层，对等层间进行通信。（5）OSI模型（网络参考模型）：物理层数据链路层网络层传输层会话层表示层应用层（6）TCP/IP协议：目前最通用的网络协议。（数据链路层网络层（如：IP协议）传输层（TCP协议或UDP协议）应用层（HTTP、FTP、SMTP、POP3等协议）5. 考点：IP地址格式。IPV4（32位二进制）的IP地址格式：0255. 0255. 0255. 0255 IPV6（128位二进制）的IP地址格式：分为8组，每组由4个十六进制数表示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）:四舍五入，取整数部分11. 考点：指针与链表。指针：用来存放位置信息。链表：是分散的数据“环环相扣”。解题方法：（1）画图辅助。（新的箭头指向） （2）注意赋值顺序是否正确。12. 考点：查找。（1）明确题意：2n个数、最少（理想状态：可尝试把大问题分解为小问题。）、比较次数解题方法：（1）分成N组，两两比较，共比较N次。（2）A组：放比较后小的数，B组：放比较后大的数。（3）在A组中找出最小值。（需比较N-1次） （4）在B组中找出最大值。（需比较N-1次）（4）一共需要比较3N-1次。13. 考点：完全图与生成树概念。完全图：所以点之间都有边相连的无向图。（6*5 / 2 =15（条边） 生成树：除了“根结点”，其他点都是“长”出来的，有且只有“一枝”。（6-1=5（条边）14. 考点：排序算法的时间复杂度。快速排序、堆排序、归并排序：将大问题分解为小问题解决。（特点：分组、递归）时间复杂度O（nlog2n）插入排序、冒泡排序、选择排序：在原来的“队列”比较、交换数值进行排序。时间复杂度O（n2） （1） 插入排序：保证当前已排序的数处于“最佳位置”。N个数需进行N趟排序，每趟添加一个数，第i趟都需要对i个数进行位置的“微调”。（2） 归并排序：分组（最小单位）合并（多组“同时进行”，所以减少时间复杂度），用递归实现。（3） 冒泡排序： 按顺序“寻找”每一个位置的数是哪一个（该数通过“小步挪动”，即与相邻数交换位置，一步步“爬上来”），共需要N-1趟。（4） 选择排序： 按顺序“寻找”每一个位置的数是哪一个（先“决选”出唯一合适的数，再“大步跨越”到准确位置），共需要N-1趟。15. 考点：排序算法的变形。解题方法：明确条件：n个数、不等、最坏情况下（倒序）、找到第N小元素。 求：比较次数。 找出比较数的语句固定数的比较语句+非固定数的比较语句（循环结构中）最坏情况（使循环执行最多次） 1【固定】+ 2*（n-3+1）【非固定】= 2n-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=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、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，具有最短路径的是D，AD路径形成，通过D可到达E（7） 与A“相连”的点有I、E，具有最短路径的是I，A路径形成，通过D可到达EABCDEFGHI113642854934742 四、阅读程序写结果(共4题，每题8分，共计32分)1. var 【a, b,】 i, tot, 【c1, c2】:integer;/分组变量名，同组作用类似 begin readln(a,b); tot:=0; for i:=a to b do/代入a和b数值，减少变量个数 begin c1:=i div 10;/识别功能：提取个位数 c2:=i mod 10; /识别功能：提取十位数 if (c1+c2) mod 3=0 then/当个位数与十位数之和与3整除时 inc(tot);/累加：满足条件加1（计算个数） end; writeln(tot);/输出语句：（要填写的结果） end.输入:7 31输出:_2. 考点：递归函数var n, m:integer; function fun(n, minNum, maxNum : integer): integer; /代入数值，减少变量个数 var tot, i:integer; begin if n=0 then/最简单的情况 exit(1);/退出函数，函数值为1 tot:=0;/tot初始化 for i:=minNum to maxNum do/代入数值，减少变量个数 tot:=tot + fun(n-1, i+1, maxNum);/tot累加；递归函数，与多个n-1时的值有关系 exit(tot); end; begin readln(n, m); writeln(fun(m, 1, n);/输出语句（函数值）；代入数值，减少变量个数2题：（1）划分功能函数和主函数，（2）先阅读主函数，因为程序是从主函数出发的（3）递归：从最简单的情况出发，当n=0时的所有函数值为0，递推出n=1时的所有函数值，以此类推，最后推算出fun(3,1,6)的值 end.输入:6 3输出:_3.考点：冒泡排序的变形。 const SIZE=100; Var/（1）根据变量名识别变量功能 dict:array1.SIZEof string;/代入常量的值；字符串数组 rank,ind:array1.SIZEof integer; /代入常量的值；rank排序；ind标记、位置 i, j, n, tmp:integer;/i,j循环过程中当前位置；tmp中间值，辅助变量 begin readln(n);/输入数据量（7个字符串） for i:=1 to n do begin ranki:=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/如果前一项比较大，则交换位置，所以结果是“从小到大” tmp:=indj;/ indj:=indj+1; indj+1:=tmp;/对各字符串的“序号”进行排序（注意字符串数组的数据未交换位置） end; for i:=1 to n do rankindi:=i;/每个字符串排序后“应该”在的位置 for i:=1 to n do write(ranki, ); writeln; end.输入:7aaaababbbaaaaaacccaa输出:_4. const SIZE=100; var alive:array1.SIZE of integer;/alive:”还在，还可用”，判断功能11112345678910 n, m, num, i, j:integer;/根据变量名猜测作用 function next(num:integer):integer;/下一个数 begin repeat inc(num);加1 if numn then/n=11,当大于11时，则变为1，类似“时钟”的轮回 num:=1; until alivenum0;/用“轮回”的方式找到“还可用”的数 exit(num);/以找到的数为函数值 end; begin/（1）从主函数开始阅读 read(n, m); for i:=1 to n do alivei:=1;/数据初始化 num:=1;/数据初始化（从1开始） for i:=1 to n do/代入变量值，减少变量个数；第一层循环 begin for j:=1 to m-1 do/代入变量值，m=1=2(每隔一个数)；第二层循环 num:=next(num);/根据函数名猜测功能（下一个）；阅读函数判断功能 write(num, );/属于第一层循环语句，共输出n次 alivenum:=0;/输出过的数就“不能用” if in then num:=next(num);/下一趟从上一趟输出最后的数的下一个数开始 end; writeln; end.输入:11 3输出:_ 四 完善程序解题策略：（1）明确程序的条件、算法、问题目标。（2）不放过题意的任何一次一句，将其转化为语句表达。（可能填空时就是考这个）（4）自己心里预想问题可以怎么解决。（5）从定义的变量，猜想程序的算法思路。（有时需要灵感）（6）填空的内容一般有：初始化数据、边界值（判断语句和循环语句中）、关键执行语句（7）信心，我一定能做！第二十届全国青少年信息学奥林匹克联赛初赛提高组参考答案一、单项选择题（共 15 题，每题 1.5 分，共计 22.5 分）12345678BDDBCCBB9101112131415DADCCBC二、不定项选择题（共 5 题，每题 1.5 分，共计 7.5 分，多选或少选均不得分）12345ABBCDABCDEACBD三、问题求解（共 2 题，每题 5 分，共计 10 分）1. 1022. 15四、阅读程序写结果（共4题，每题8分，共计32分）1. 82. 203. 2 5 6 3 4 7 14. 3 6 9 1 5 10 4 11 8 27五、完善程序（第 1 题第 2 空 3 分，其余每空 2.5 分，共计 28 分）以下各程序填空可能还有一些等价的写法，各省赛区可请本省专家审定和上机验证，