noip2009初赛

全国青少年信息学奥林匹克联赛（NOIP）是中国计算机学会组织的一项旨在培养青少年计算机科学能力的比赛。初赛主要面向提高组的学生，通常包括选择题和编程题两部分，考察参赛者的计算机基础知识、算法理解以及编程能力。 1. 图灵机是计算机科学的基础概念，由英国数学家阿兰·图灵提出，它是一种抽象的计算模型，用于描述能够执行任何计算的机器。选项C正确，图灵机并非实际的计算机设备，而是一个理论上的计算模型，不存在运行速度，也没有在二战中直接用于破译密码，尽管图灵本人在二战期间的工作对密码破译起到了关键作用。 2. BIOS（Basic Input Output System）是计算机启动过程中加载的固件，包含了最基本的设备驱动程序，用于初始化硬件。选项A正确，BIOS是基本输入输出系统的简称，但关于它是软件还是固件的定义存在争议。它并不包含所有设备的驱动，如声卡、图形界面显示器的驱动，而是只包含启动过程中的基本硬件支持。 3. ASCII编码是字符编码标准，大写字母A的ASCII编码为65（十进制），J的ASCII编码为65加上9（因为J在A后面9个字母），即74，转换为十六进制为4A。 4. 16位带符号整数的二进制补码1111111111101101表示负数，因为最高位为1。将该二进制数转换为原码，得到1000000000010011，其中最高位为符号位，代表负号，其余位转换为十进制为19，因此这个数表示的是-19。 5. 在非空满k叉树中，叶节点的数量与分支节点（非叶节点）的关系可以通过公式N0=(K-1)N+1得出，其中N0表示叶节点数，N表示分支节点数，K表示每个分支节点的子节点数量。如果k=2，这棵树就是完全二叉树，根据题目，选择D。 6. 后缀表达式是运算符位于操作数之后的表示形式，常用于编译原理和计算器设计。表达式a*(b+c)-d的后缀表达式是abc+*d-，遵循操作数在前，运算符在后的规则。 7. Huffman编码是一种最优的前缀编码方法，确保没有编码是其他编码的前缀，以避免解码时的歧义。选项B中的0是00的前缀，因此不是合法的Huffman编码。 8. 快速排序在平均情况下具有O(nlogn)的时间复杂度，而在最坏情况下，当输入数组已经排序或逆序时，时间复杂度退化为O(n^2)。 9. Prim算法是一种寻找加权无向图最小生成树的算法，从一个顶点开始逐步添加边，使得当前生成树的总权重最小。根据题目描述，选择A的顶点序列符合Prim算法的顺序。 10. 全国信息学奥林匹克的官方网站通常会提供竞赛相关信息、资源和报名渠道，帮助参赛者和指导教师了解比赛详情。 这些知识点涵盖了计算机科学的基础概念，如图灵机、计算机硬件（BIOS）、ASCII编码、数值转换、数据结构（多叉树、二叉树）、算法（快速排序、Prim算法）、编码理论（Huffman编码）以及计算机网络（网站信息）。理解和掌握这些知识点对参加NOIP初赛的学生至关重要。