2014NOIP初赛解题报告

《2014NOIP初赛解题报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2014NOIP初赛解题报告一．选择题。1.考点：程序设计语言。计算机语言的发展：机器语言（由0和1组成）——汇编语言（“认机器”）——高级语言高级语言：（1）面向过程语言（C、pascal）（2）面向对象语言（VB、C++、Java……）2.考点：计算机基础知识。TB——GB——MB——KB——B（2^10=1024）3.考点：二进制的加法运算。按位运算：0+0=00+1=11+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地址格式：0~255.0~255.0~255

3、.0~255IPV6（128位二进制）的IP地址格式：分为8组，每组由4个十六进制数表示6.考点：无向图的特征。度数之和是边数的2倍。解题办法：举例法，线段是最简单的无向图。（有向图的特征。出度之和或入度之和是边数的1倍。最简单的有向图——“箭头”）7.考点：有序链表的顺序检索。（1）明确条件：有序、概率相等。（2）求：平均检索长度。（用n表达）（3）解题方法：举例（如：1,2,3,4）——归纳为用n表示8.考点：编译器的主要功能是将源程序翻译成指令。（源程序——目标程序）9.考点：二进制转换为十进制。2^2+2^1+2^0+2^(-1)+2^

4、(-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）一

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

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

7、最坏情况（使循环执行最多次）1【固定】+2*（n-3+1）【非固定】=2n-3一．不定项选择题1.考点：逻辑运算。运算顺序：非——与——或（负——乘——加）2.考点：操作系统软件。Oracle为数据库管理系统。3.考点：比赛规则。4.考点：图的存储。（1）邻接矩阵（用“表”的形式存储每个点相互间的关系）（2）用N个“数组”存储以每个点为起点的N条“路径”）5.考点：数的表示。无符号十进制：0~255（8位）有符号十进制：-127~127（1位符号，7位数值）二．问题求解1.考点：组合排列。解题方法：分情况考虑：36+36+6+24=102（个）

8、（1）有两个1组成：四个位置选两个放1（(4*3)/(2*1)=6，其他三个数中的两个3*2=6，所以，6*6=36（个）（2）有两个8组成：与（1）