信息学初赛复习资料-笔试

1 信息学初赛复习资料 初赛考的知识点就是计算机基本常识 基本操作和程序设计基础知识 其中选择题考查的是知识 而问题 解决类型的题目更加重视能力的考查 一般说来 选择题只要多用心积累就可以了 问题解决题目的模式比较 固定 大家应当做做以前的题目 写运行结果和程序填空也需要多做题目 并且培养良好的程序阅读和分析能 力 就像语文的阅读理解一样 近几年来 初赛的考查范围有了很大的变化 越来越紧跟潮流了 这就需要大家有比较广泛的知识 包括 计算机硬件 软件 网络 简单的数据结构 例如栈 队列 树和图等 和简单的算法 例如排序 查找和搜 索等 程序设计语言以及一些基本的数学知识和技巧 例如排列组合 但最主要的 还是取决于你对程序设 计语言的熟悉程度 再加上认真仔细的心态 选择题 一 硬件 计算机发展可划分 年代 元件 第一代 1946 1958 电子管 第二代 1959 1964 晶体管 第三代 1965 1970 集成电路 第四代 1971 大规模集成电路 1946 年 2 月 在美国宾夕法尼亚大学诞生了世界上第一台电子计算机 ENIAC Electronic Numerical Integrator And Computer 这台计算机占地 170 平方米 重 30 吨 用了 18000 多个电子管 每秒能进行 5000 次加法运算 冯 诺依曼理论 1944 年 美籍匈牙利数学家 冯 诺依曼 提出计算机基本结构和工作方式的设想 为计算机的诞生和发展 提供了理论基础 时至今日 尽管计算机软硬件技术飞速发展 但计算机本身的体系结构并没有明显的突破 当今的计算机仍属于冯 诺依曼架构 其理论要点如下 1 计算机硬件设备由存储器 运算器 控制器 输入设备和输出设备 5 部分组成 2 存储程序思想 把计算过程描述为由许多命令按一定顺序组成的程序 然后把程序和数据一起输入计 算机 计算机对已存入的程序和数据处理后 输出结果 我国的计算机发展情况 我国从 1956 年开始计算机的科研和教学工作 1960 年我国第一台自行设计的通用电子计算机 107 机诞生 1964 年我国研制成大型通用电子计算机 119 机 1983 年每秒运行一亿次的银河巨型计算机在国防科技大学诞生 1992 年研制成功每秒运行 10 亿次的 银河 巨型计算机 1997 年又研制成功每秒运行 130 亿次的 银河 巨型计算机 我国较有名的微型计算机品牌有 联想 长城 方正 等 微型机的主要技术指标 1 字长 知己算计能够直接处理的二进制数据的位数 单位为位 BIT 2 2 主频 指计算机主时钟在一秒钟内发出的脉冲数 在很大程度上决定了计算机的运 算速度 3 内存容量 是标志计算机处理信息能力强弱的一向技术指标 单位为字节 BYTE 8BIT 1BYTE 1024B 1KB 1024KB 1MB 4 外存容量 一般指软盘 硬盘 光盘 计算机的特点 运算速度快 运算精度高 具有记忆能力 具有逻辑判断能力 具有自动控制能力 计算机的应用 1 数值计算 弹道轨迹 天气预报 高能物理等等 2 信息管理 企业管理 物资管理 电算化等 3 过程控制 工业自动化控制 卫星飞行方向控制 4 辅助工程 CAD CAM CAT CAI 等 计算机硬件由五大部分组成 运算器 控制器 存储器 输入设备 输出设备 中央处理器 CPU Central Processing Unit 由运算器 控制器和一些寄存器组成 运算器进行各种算术运算和逻辑运算 控制器是计算机的指挥系统 CPU 的主要性能指标是主频和字长 存储器 内部存储器 中央处理器能直接访问的存储器称为内部存储器 它包括快速缓冲存储器和主存储器 中央处理器不能直 接访问的存储器称为外部存储器 外部存储器中的信息必须调入内存后才能为中央处理器处理 主存储器 内存也常泛称主存 但严格上说 只有当内存中只有主存 而没有快速缓冲存储器时 才能称 为主存 主存储器按读写功能 可分只读存储器 ROM 和随机存储器 RAM 两种 外部存储器 外存储器 也称为辅助存储器 一般容量较大 速度比主存较慢 硬盘 Hard disk 目前的硬盘大多采用了温彻斯特技术 所以又称为 温盘 温氏技术的特点是 将盘片 读写磁头及驱动装置精密地组装在一个密封盒里 采用接触式起停 非接触 式读写的方式 磁盘不工作时 磁头停在磁盘表面的起停区 一旦加电后 磁头随着盘片旋转的气流 飞 起 来 悬浮在磁盘表面 进行读写 软盘 Floppy Disk 目前常见的是 3 5 英寸 1 44 MB 的软盘 3 光盘存储器 CD ROM 普通的 CD ROM 只能读 不能写 CD 盘片的存储量大约是 650 MB 输入设备 键盘 Keyboard 目前大多使用 104 或 108 键盘 鼠标 Mouse 主要有机械型鼠标和光电型鼠标两种 手写笔 触摸屏 麦克风 扫描仪 Scanner 视频输入设备 条形码扫描器 输出设备 显示器 Monitor 目前主要有 CRT 阴极射线管 显示器和 LCD 液晶显示器 打印机 Printer 主要有针式打印机 喷墨打印机 激光打印机 绘图仪 音箱 例题 微型计算机的问世是由于 C 的出现 A 中小规模集成电路 B 晶体管电路 C 超 大规模集成电路 D 电子管电路 中央处理器 CPU 能访问的最大存储器容量取决于 A A 地址总线 B 数据总线 C 控制总线 D 实际内存容量 微型计算机中 C 的存取速度最快 A 高速缓存 B 外存储器 C 寄存器 D 内存储器 在计算机硬件系统中 cache 是 D 存储器 A 只读 B 可编程只读 C 可擦除可编程只读 D 高速缓冲 若我们说一个微机的 CPU 是用的 PII300 此处的 300 确切指的是 A A CPU 的主时钟频率 B CPU 产品的系列号 C 每秒执行 300 百万条指令 D 此种 CPU 允许最大内存容量 计算机主机是由 CPU 与 D 构成的 A 控制器 B 输入 输出设备 C 运算器 D 内存储器 计算机系统总线上传送的信号有 B A 地址信号与控制信号 B 数据信号 控制信号与地址信号 C 控制信号与数据信号 D 数据信号与地址信号 不同类型的存储器组成了多层次结构的存储器体系 按存取速度从快到慢的排列是 C A 快存 辅存 主存 B 外存 主存 辅存 C 快存 主存 辅存 D 主存 辅存 外存 微机内存储器的地址是按 C 编址的 A 二进制位 B 字长 C 字节 D 微处理器的型号 在微机中 通用寄存器的位数是 C A 8 位 B 16 位 C 计算机字长 D 32 位 不同的计算机 其指令系统也不同 这主要取决于 C A 所用的操作系统 B 系统的总体结构 C 所用的 CPU D 所用的程序设计语言 下列说法中 哪个 些 是错误的 BDE A 程序是指令的序列 它有三种结构 顺序 分支和循环 B 数据总线决定了中央处理器 CPU 所能访问的最大内存空间的大小 C 中央处理器 CPU 内部有寄存器组 用来储存数据 D 不同厂家生产的 CPU 所能处理的指令集是相同的 4 E 数据传输过程中可能会出错 奇偶校验法可以检测出数据中哪一位在传输中出了差错 CPU 访问内存的速度比访问下列哪个 些 存储设备要慢 AD A 寄存器 B 硬盘 C 软盘 D 高速缓存 E 光盘 下列哪个 些 不是个人计算机的硬件组成部分 B A 主板 B 虚拟内存 C 电源 D 硬盘 E 总线 美籍匈牙利数学家冯 诺依曼对计算机科学发展所做出的贡献是 C A 提出理想计算机的数学模型 成为计算机科学的理论基础 B 是世界上第一个编写计算机程序的人 C 提出存储程序工作原理 并设计出第一台具有存储程序功能的计算机 EDVAC D 采用集成电路作为计算机的主要功能部件 E 指出计算机性能将以每两年翻一番的速度向前发展 下列哪个不是 CPU 中央处理单元 B A Intel Itanium B DDR SDRAM C AMD Athlon64 D AMD Opteron E IBM Power 5 下列说法中错误的是 B A CPU 的基本功能就是执行指令 B CPU 访问内存的速度快于访问高速缓存的速度 C CPU 的主频是指 CPU 在 1 秒内完成的指令周期数 D 在一台计算机内部 一个内存地址编码对应唯一的一个内存单元 E 数据总线的宽度决定了一次传递数据量的大小 是影响计算机性能的因素之一 用静电吸附墨粉后转移到纸张上 是哪种输出设备的工作方式 C A 针式打印机 B 喷墨打印机 C 激光打印机 D 笔式绘图仪 E 喷墨绘图仪 处理器A 每秒处理的指令数是处理器 B 的2 倍 某一特定程序P 分别编译为处理器A 和处理器B 的指令 编译结果处理器 A 的指令数是处理器B 的4 倍 已知程序P 在处 理器A 上执行需要1 个小时 那么在输入相同的情况下 程序P 在处理器B 上执行需 要 D 小时 A 4 B 2 C 1 D 1 2 E 1 4 以下哪个不是计算机的输出设备 D A 音箱 B 显示器 C 打印机 D 扫描仪 E 绘图仪 二 进制与编码 四种常用的数制及它们之间的相互转换 进制 基数 基数个数 权 进数规律 十进制 0 1 2 3 4 5 6 7 8 9 10 10i 逢十进一 二进制 0 1 2 2i 逢二进一 八进制 0 1 2 3 4 5 6 7 8 8i 逢八进一 十六进制 0 1 2 3 4 5 6 7 8 9 A B C D E F 16 16i 逢十六进一 十进制数转换为二进制数 八进制数 十六进制数的方法 二进制数 八进制数 十六进制数转换为十进制数的方法 按权展开求和法 1 二进制与十进制间的相互转换 1 二进制转十进制 5 方法 按权展开求和 例 1011 01 2 1 2 3 0 2 2 1 2 1 1 2 0 0 2 1 1 2 2 10 8 0 2 1 0 0 25 10 11 25 10 规律 个位上的数字的次数是 0 十位上的数字的次数是 1 依奖递增 而十 分位的数字的次数是 1 百分位上数字的次数是 2 依次递减 注意 不是任何一个十进制小数都能转换成有限位的二进制数 2 十进制转二进制 十进制整数转二进制数 除以 2 取余 逆序排列 短除反取余法 例 89 10 1011001 2 2 89 2 44 1 2 22 0 2 11 0 2 5 1 2 2 1 2 1 0 0 1 十进制小数转二进制数 乘以 2 取整 顺序排列 乘 2 取整法 例 0 625 10 0 101 2 0 625 X 2 1 25 1 X 2 0 5 0 X 2 1 0 1 2 八进制与二进制的转换 二进制数转换成八进制数 从小数点开始 整数部分向左 小数部分向右 每 3 位为一组用一位八进制数 的数字表示 不足 3 位的要用 0 补足 3 位 就得到一个八进制数 八进制数转换成二进制数 把每一个八进制数转换成 3 位的二进制数 就得到一个二进制数 例 将八进制的 37 416 转换成二进制数 3 7 4 1 6 011 111 100 001 110 即 37 416 8 11111 10000111 2 例 将二进制的 10110 0011 转换成八进制 0 1 0 1 1 0 0 0 1 1 0 0 2 6 1 4 即 10110 011 2 26 14 8 3 十六进制与二进制的转换 二进制数转换成十六进制数 从小数点开始 整数部分向左 小数部分向右 每 4 位为一组用一位十六进 制数的数字表示 不足 4 位的要用 0 补足 4 位 就得到一个十六进制数 十六进制数转换成二进制数 把每一个八进制数转换成 4 位的二进制数 就得到一个二进制数 例 将十六进制数 5DF 9 转换成二进制 5 D F 9 0101 1101 1111 1001 即 5DF 9 16 10111011111 1001 2 例 将二进制数 1100001 111 转换成十六进制 6 0110 0001 1110 6 1 E 即 1100001 111 2 61 E 16 注意 以上所说的二进制数均是无符号的数 这些数的范围如下表 无符号位二进制数位数 数值范围 十六进制范围表示法 8 位二进制数 0 255 255 2 8 1 00 0FFH 16 位二进制数 0 65535 65535 2 16 1 0000H 0FFFFH 32 位二进制数 0 232 1 00000000H 0FFFFFFFFH 带符号数的机器码表示方法 1 带符号二进制数的表示方法 带符号二进制数用最高位的一位数来表示符号 0 表示正 1 表示负 含符号位二进制数位数 数值范围 十六进制范围表示法 8 位二进制数 128 127 80H 7FH 16 位二进制数 32768 32767 8000H 7FFFH 32 位二进制数 2147483648 2147483647 80000000H 7FFFFFFFH 2 符号位的表示 最常用的表示方法有原码 反码和补码 1 原码表示法 一个机器数 x 由符号位和有效数值两部分组成 设符号位为 x0 x 真值的绝对值 x x1x2x3 xn 则 x 的机器数原码可表示为 x 原 210 当 x 0 时 x 0 0 当 x 0 时 x 0 1 例如 已知 x 1 1011B x 2 1001B 则 x1 x 2有原码分别是 x1 原 11011B x 2 原 01001B 规律 正数的原码是它本身 负数的原码是取绝对值后 在最高位 左端 补 1 2 反码表示法 一个负数的原码符号位不变 其余各位按位取反就是机器数的反码表示法 正数的反码 与原码相同 按位取反的意思是该位上是 1 的 就变成 0 该位上是 0 的就变成 1 即 1 0 0 1 例 Bx10 x02 求 反 1x和 反2 解 反 反 B 3 补码表示法 首先分析两个十进制数的运算 78 38 41 79 62 141 如果使用两位数的运算器 做 79 62 时 多余的 100 因为超出了运算器两位数的范围而自动丢弃 这样在 做 78 38 的减法时 用 79 62 的加法同样可以得到正确结果 模是批一个计量系统的测量范围 其大小以计量进位制的基数为底数 位数为指数的幂 如两位十进制数 的测量范围是 1 9 溢出量是 100 模就是 102 100 上述运算称为模运算 可以写作 79 38 79 62 mod 100 进一步写为 38 62 此时就说 38 的补法 对模 100 而言 是 62 计算机是一种有限字长的数字系统 因此它的运算都是有模运算 超出模的运算结果都将溢出 n 位二进制的模是 2n 一个数的补码记作 x 补 设模是 M x 是真值 则补码的定义如下 0 xMx原补 例 设字长 n 8 位 x 1011011B 求 x 补 解 因为 n 8 所以模 M 2 8 100000000B x 4 F 1 1 f 2 2 f 3 4 在磁盘的目录结构中 我们将与某个子目录有关联的目录数称为度 例如下图 该图表达了 A 盘的目录结构 DI Dll D2 均表示子目录的名字 在这里 根目录的度为 2 D1 子目录 的度为 3 D11 子目录的度为 4 D12 D2 D111 D112 D113 的度均为 1 又不考虑子目录的名字 则可简单 的图示为如下的树结构 若知道一个磁盘的目录结构中 度为 2 的子目录有 2 个 度为 3 的子目录有 1 个 度为 4 的子目录有 3 个 试问 度为 1 的子目录有几个 2 2 3 1 4 3 1 x 2 1 3 x 1 2 19 根据 Nocomachns 定理 任何一个正整数 n 的立方一定可以表示成 n 个连续的奇数的和 例如 13 1 23 3 5 33 7 9 11 43 13 15 17 19 在这里 若将每一个式中的最小奇数称为 X 那么当给出 n 之后 请写出 X 与 n 之间的关系表达式 n 2 n 1 设循环队列中数组的下标范围是 1 n 其头尾指针分别为 f 和 r 则其元素个数为 D A r f B r f 1 C r f MOD n 1 D r f n MOD n 有 2 n 的一个长方形方格 用一个 1 2 的骨牌铺满方格 例如 n 3 时 为 2 3 方格 此时用一个 1 2 的骨牌铺满方格 共有 3 种铺法 试对给出的任意一个 n n 0 求出铺法总数的递推公式 F 1 1 F 2 2 F n F n 1 F n 2 n 3 FUNCTION ACK M N INTEGER INTEGER BEGIN IF M 0 THEN ACK N 1 ELSE IF N 0 THEN ACK ACK M 1 1 ELSE ACK ACK M 1 ACK M N 1 END BEGIN WRITELN ACK 3 4 READLN END 输出 125 表达式 1 34 5 56 7 的后缀表达式为 C A 1 34 5 56 7 B 1 34 5 56 7 C 1 34 5 56 7 D 1 34 5 56 7 E 1 34 5 56 7 已知元素 8 25 14 87 51 90 6 19 20 问这些元素以怎样的顺序进入栈 才能使出栈的顺序满足 8 在 51 前面 90 在 87 的后面 20 在 14 的后面 25 在 6 的前面 19 在 90 的后面 D 题意是全 部进栈 再依次出栈 A 20 6 8 51 90 25 14 19 87 B 51 6 19 20 14 8 87 90 25 C 19 20 90 7 6 25 51 14 87 D 6 25 51 8 20 19 90 87 14 E 25 6 8 51 87 90 19 14 20 假设我们用 d a1 a2 a5 表示无向图 G 的 5 个顶点的度数 下面给出的哪 些 组 d 值合理 BE A 5 4 4 3 1 B 4 2 2 1 1 C 3 3 3 2 2 D 5 4 3 2 1 E 2 2 2 2 2 20 下列关于程序语言的叙述 不正确的是 D A 编写机器代码不比编写汇编代码容易 B 高级语言需要编译成目标代码或通过解释器解释后才能被 CPU 执行 C 同样一段高级语言程序通过不同的编译器可能产生不同的可执行程序 D 汇编代码可被 CPU 直接运行 E 不同的高级语言语法略有不同 下列哪个程序设计语言不支持面向对象程序设计方法 C A C B Object Pascal C C D Smalltalk E Java 某个车站呈狭长形 宽度只能容下一台车 并且只有一个出入口 已知某时刻该车站状态为空 从这一时刻开 始的出入记录为 进 出 进 进 出 进 进 进 出 出 进 出 假设车辆入站的顺序为 1 2 3 则车辆出站的顺序为 A 1 2 3 4 5 B 1 2 4 5 7 C 1 3 5 4 6 D 1 3 5 6 7 E 1 3 6 5 7 二叉树 T 已知其前序遍历序列为 1 2 4 3 5 7 6 中序遍历序列为 4 2 1 5 7 3 6 则其后序遍历序列为 B A 4 2 5 7 6 3 1 B 4 2 7 5 6 3 1 C 4 2 7 5 3 6 1 D 4 7 2 3 5 6 1 E 4 5 2 6 3 7 1 满二叉树的叶结点个数为 N 则它的结点总数为 C A N B 2 N C 2 N 1 D 2 N 1 E 2N 1 在下图中 从顶点 E 出发存在一条路径可以遍历图中的每条边一次 而且仅遍历一次 A A 点 B B 点 C C 点 D D 点 E E 点 某大学计算机专业的必修课及其先修课程如下表所示 课 程 代 号 C0 C1 C2 C3 C4 C5 C6 C7 课 程 名 称 高 等 数 学 程 序 设 计 语 言 离 散 数 学 数 据 结 构 编 译 技 术 操 作 系 统 普 通 物 理 计 算 机 原 理 先 修 课 程 C0 C1 C1 C2 C3 C3 C7 C0 C6 请你判断下列课程安排方案哪个是不合理的 D A C0 C6 C7 C1 C2 C3 C4 C5 B C0 C1 C2 C3 C4 C6 C7 C5 C C0 C1 C6 C7 C2 C3 C4 C5 D C0 C1 C6 C7 C5 C2 C3 C4 E C0 C1 C2 C3 C6 C7 C5 C4 完全二叉树的结点个数为4 N 3 则它的叶结点个数为 E A 2 N B 2 N 1 C 2 N 1 D 2 N 2 E 2 N 2 平面上有五个点A 5 3 B 3 5 C 2 1 D 3 3 E 5 1 以这五点作为完全图 G 的顶点 每两点之间的直线距离是图G 中对应边的权值 以下哪条边不是图G 的最小生成树中 的边 D A AD B BD C CD D DE E EA 二叉树T的宽度优先遍历序列为A B C D E F G H I 已知A是C的父结点 D 是G 的 父结点 F 是I 的父结点 树中所有结点的最大深度为3 根结点深度设为0 可知F 的父结点是 C A 无法确定 B B C C D D E E 设栈S的初始状态为空 元素a b c d e f g依次入栈 以下出栈序列不可能出现的是 E A a b c e d f g B b c a f e g d C a e d c b f g D d c f e b a g E g e f d c b a 21 将数组 32 74 25 53 28 43 86 47 中的元素按从小到大的顺序排列 每次可以交换任 意两个元素 最少需要交换 5 次 取火柴游戏的规则如下 一堆火柴有N 根 A B 两人轮流取出 每人每次可以取1 根或 2 根 最先没有火柴可取的人为败方 另一方为胜方 如果先取者有必胜策略则记为1 先取者没有必胜策略记为0 当N 分别为100 200 300 400 500 时 先取者有无必 胜策略的标记顺序为 11011 回答应为一个由0 和 或 1 组成的字符串 在所有排序方法中 关键字比较的次数与记录的初始排列次序无关的是 BD A 希尔排序 B 起泡排序 C 插入排序 D 选择排序 七 排列组合 例题 在书架上放有编号为 1 2 n 的 n 本书 现将 n 本书全部取下然后再放回去 当放回去时要求每本书都不能放 在原来的位置上 例如 n 3 时 原来位置为 123 放回去时只能为 312 或 231 这两种 问题 求当 n 5 时满足以上条件的放法共有多少种 不用列出每种放法 c 5 0 5 c 5 1 4 c 5 2 3 c 5 3 2 c 5 4 1 c 5 5 0 60 20 5 1 44 平面上有三条平行直线 每条直线上分别有 7 5 6 个点 且不同直线上三个点都不在同一条直线上 问用这 些点为顶点 能组成多少个不同三角形 C 7 2 5 6 C 5 2 7 6 C 6 2 7 5 7 6 5 21 11 10 13 15 12 210 231 130 180 210 751 平面上有三条平行直线 每条直线上分别有 7 5 6 个点 且不同直线上三个点都不在同一条直线上 问用这 些点为顶点 能组成多少个不同四边形 21 10 21 15 10 15 21 30 10 42 15 35 1155 525 570 2250 由 3 个 a 1 个 b 和 2 个 c 构成的所有字符串中 包含子串 abc 的共有 D 个 A 20 B 8 C 16 D 12 E 24 由 3 个 a 5 个 b 和 2 个 c 构成的所有字符串中 包含子串 abc 的共有 D 个 A 40320 B 39600 C 840 D 780 E 60 8 7 2 4 4 C 5 2 4 5 8 3 5 7 40 20 840 60 780 八 综合 下面一段程序是用 C 语言书写的 int func1 int n int i sum 0 for i 1 i n i sum i i return sum A FORTRAN B PASCAL C C D PROLOG E BASIC 多媒体计算机是指 D 计算机 A 专供家庭使用的 B 装有 CD ROM 的 B 连接在网络上的高级 D 具有处理文字 图形 声音 影像等信息的 在 WORD 文档编辑中实现图文混合排版时 关于文本框的下列叙述正确的是 C 22 A 文本框中的图形没有办法和文档中输入文字叠加在一起 只能在文档的不同位置 B 文本框中的图形不可以衬于文档中输入的文字的下方 C 通过文本框 可以实现图形和文档中输入的文字的叠加 也可实现文字环绕 D 将图形放入文本框后 文档中输入的文字不能环绕图形 计算机软件保护法是用来保护软件 D 的 A 编写权 B 复制权 C 使用权 D 著作权 64KB 的存储器用十六进制表示 它的最大的地址码是 B A 10000 B FFFF C 1FFFF D EFFFF 在外部设备中 绘图仪属于 B A 输入设备 B 输出设备 C 辅 外 存储器 D 主 内 存储器 某种计算机的内存容量是 640K 这里的 640K 容量是指 C 个字节 A 640 B 640 1000 C 640 1024 D 640 1024 1024 已知数组中 A 中 每个元素 A I J 在存贮时要占 3 个字节 设 I 从 1 变化到 8 J 从 1 变化到 10 分配内 存时是从地址 SA 开始连续按行存贮分配的 试问 A 5 8 的起始地址为 A A SA 141 B SA 180 C SA 222 D SA 225 电线上停着两种鸟 A B 可以看出两只相邻的鸟就将电线分为了一个线段 这些线段可分为两类 一类是两端的小鸟相同 另一类则是两端的小鸟不相同 已知 电线两个顶点上正好停着相同的小鸟 试问两端为不同小鸟的线段数目一定是 B A 奇数 B 偶数 C 可奇可偶 D 数目固定 一个文本屏幕有 25 列及 80 行 屏幕的左上角以 1 1 表示 而右下角则以 80 25 表示 屏幕上每 一个字符占用两字节 byte 整个屏幕则以线性方式存储在电脑的存储器内 内屏幕左上角开始 位移为 0 然后逐列逐列存储 求位於屏幕 X Y 的第一个字节的位移是 B A Y 80 X 2 1 B Y 1 80 X 1 2 C Y 80 X 1 2 D Y 1 80 X 2 1 计算机能直接执行的指令包括两部分 它们是 B A 源操作数与目标操作数 B 操作码与操作数 C ASCII 码与汉字代码 D 数字与字符 解释程序的功能是 C A 将高级语言程序转换为目标程序 B 将汇编语言程序转换为目标程序 C 解释执行高级语言程序 D 解释执行汇编语言程序 192 168 0 1 属于 C A A 类地址 B B 类地址 C C 类地址 D D 类地址 最高位 1 126 为 A 类 128 191 是 B 类 192 223 是 C 类 十进制数 13 和 14 进行 与 操作的结果是 B 23 A 27 B 12 C 15 D 11 1101 and 1110 1100 12 完全二叉树对每个节点从上往下 从左往右编号 第 i 层的第 j 个节点的编号是 D A 2i j B 2i j 1C 2i 1 j D 2i 1 j 1 以下排序方法 那种是稳定的 C A 希尔排序 B 堆排序 C 冒泡排序 D 快速排序 排序的稳定性指的是对于原来所有的 a i a j i j 排序以后 a i 的新位置仍然在 a j 的前面 关于 0 的原码 反码和补码描述正确的是 C A 0 的原码只有一种表示方法 B 0 的反码只有一种表示方法 C 0 的补码只有一种表示方法 D 0 的原码 反码和补码均有两种表示方法 要使用 1280 1024 16 位真彩显示 显存至少应为 C MB A 1 B 2 C 4 D 8 1280 1024 2Byte 2 5MB 计算机能够自动工作 主要是因为采用了 C A 二进制数制 B 高速电子元件 C 存储程序控制 D 程序设计语言 当计算机的主存储器的容量达到 1GB 的时候 其地址的表示至少需要 C 位 A 10 B 20 C 30 D 40 1024 1024 1024Byte 230Byte 每个字节的地址用一个数表示 所以需要 30 个位 TCP IP 协议中 不属于应用层的是 D A WWW B FTP C SMTP D TCP 一棵有 n 个节点的完全二叉树的高度是 D A n 2 B log2n C log2n 2 D log2n 1 借助一个栈 输入顺序是 123456 以下输出顺序不可能的是 A A 142356 B 123654 C 231456 D 213546 对整数 N 8934632178 每次删除一个位置上的数字 使得新的数尽可能小 那么第四次删掉的数字是 D A 6 B 8 C 7 D 4 二叉树 T 设 n0 n1 和 n2 分别表示度为 0 1 和 2 的顶点个数 则它们的关系是 A A n0 n2 1 B n1 n0 1 C n2 n0 1 D n2 n1 1 中缀表达式 A B C D E 的后缀表达式形式是 D A AB C D E B ABC D E C ABCD E D ABCD E G 是一个非连通的无向图 共有 28 条边 则它至少有 C 个顶点 A 6 B 8 C 9 D 10 对 n 个元素从小到大排序 已将它们分成了 n k 组 每组 k 个数 而且每组中的所有数都大于前一组的所有数 24 那么采用基于比较的排序 时间下界是 B A O nlogn B O nlogk C O klogn D O klogk 计算机是由 D 控制器 存储器 输入设备和输出设备构成的 A ROM B I O C CPU D ALU ALU 算术逻辑单元 即通常所说的运算器 圆周上有 n 个点 任意两点间连一条弦 而且没有 3 条弦交于一点的情况 问在圆内一共有多少三角形 C n 3 4 C n 4 5 C n 5 C n 6 ASCII 码的主要作用是 A A 方便信息交换 B 方便信息存储 C 便于管理 D 便于输出 现在的计算机通常是将处理程序放在连续的内存地址中 CPU 在执行这个处理程序时 是使用一个叫做 D 的 寄存器来指示程序的执行顺序 A 累加寄存器 B 指令寄存器 C 内存地址寄存器 D 指令地址寄存器 结构化程序设计的一种基本方法是 B A 归纳法 B 逐步求精法 C 递归法 D 筛选法 二叉树后序遍历是 dabec 中序遍历是 debac 则后序遍历是 D A acbed B decab C deabc D cedba OSI 七层协议中 最底层是 A 会话层 B 数据链路层 C 物理层 D 网络层 设 x 是值大于零的实型变量 计算 PASCAL 中 x8的表达式为 A ln 8 exp x B exp 8 ln x C x 8 D sqr sqr sqr x x 在微型计算机中 常用 码实现十进制数与二进制数之间的自动转换 A BCD 码 B ASCII 码 C 海明码 D 机内码 已知 A 11001010B B 00001111B C 01011100B A V B C B A 11001110 B 01110110 C 11101110 D 01001100 二叉树是重要的数据结构 5 个点的不同的二叉树有 个 A 22 B 30 C 40 D 42 逻辑代数式子 f AB ABC AB C D 则 f 的简化式子为 A AB B A B C ABC D ABCD 插入排序是一种简单实用的工具 在对数组排序时 我们可能用二分查找 对要插入的元素快速找到在已经排 好元素序列中的位置 下面的描述中正确的是 A 二分查找的时间复杂度为 O lgN 因此排序的时间复 杂度为 O N lgN B 二分查找的时间复杂度为 O N 因此排序的时间复杂度为 O N lgN C 二分查找的时间复杂度为 O lgN 因此排序的时间复杂度为 O N N D 二分查找的时间复杂度为 O N 因此排序的时间复杂度为 O N N 有 5 本不同的数学书分给 5 个男同学 有 4 本不同的英语书分给 4 个女同学 将全部书收回来后再重新发给他 们 与原方案都不相同的方案有 种 十进制数 11 128 可用二进制数码序列表示为 D A 1011 1000000 B 1011 100000000 C 0 001011 D 0 0001011 25 x 补码 10011000 其原码为 B A 011001111 B 11101000 C 11100110 D 01100101 下面哪些计算机网络不是按覆盖地域划分的 D A 局域网 B 都市网 C 广域网 D 星型网 设栈 S 和队列 Q 的初始状态为空 元素 e1 e2 e3 e4 e5 e6 依次通过栈 S 一个元素出栈后即进入队列 Q 若出队 的顺序为 e2 e4 e3 e6 e5 e1 则栈 S 的容量至少应该为 B A 2 B 3 C 4 D 5 以下哪一个不是栈的基本运算 B A 删除栈顶元素 B 删除栈底的元素 C 判断栈是否为空 D 将栈置为空栈 在顺序表 2 5 7 10 14 15 18 23 35 41 52 中 用二分查找 12 所需的关键码比较的次数为 C A 2 B 3 C 4 D 5 某数列有 1000 个各不相同的单元 由低至高按序排列 现要对该数列进行二分查找 binary search 在最坏 的情况下 需检视 B 个单元 A 1000 B 10 C 100 D 500 线性表若采用链表存贮结构 要求内存中可用存贮单元地址 D A 必须连续 B 部分地址必须连续 C 一定不连续 D 连续不连续均可 下列叙述中 正确的是 D A 线性表的线性存贮结构优于链表存贮结构 B 队列的操作方式是先进后出 C 栈的操作方式是先进先出 D 二维数组是指它的每个数据元素为一个线性表的线性表 设有一个共有 n 级的楼梯 某人每步可走 1 级 也可走 2 级 也可走 3 级 用递推公式给出某人从底层开始走 完全部楼梯的走法 例如 当 n 3 时 共有 4 种走法 即 1 1 1 1 2 2 1 3 F n f n 1 f n 2 f n 3 n 4 F 1 1 f 2 2 f 3 4 有 2 n 的一个长方形方格 用一个 1 2 的骨牌铺满方格 例如 n 3 时 为 2 3 方格 此时用一个 1 2 的骨牌铺满方格 共有 3 种铺法 试对给出的任意一个 n n 0 求出铺法总数的递推公式 F 1 1 F 2 2 F n F n 1 F n 2 n 3 FUNCTION ACK M N INTEGER INTEGER BEGIN IF M 0 THEN ACK N 1 ELSE IF N 0 THEN ACK ACK M 1 1 ELSE ACK ACK M 1 ACK M N 1 END BEGIN WRITELN ACK 3 4 READLN END 输出 125 平面上有三条平行直线 每条直线上分别有 7 5 6 个点 且不同直线上三个点都不在同一条直线上 问用这 些点为顶点 能组成多少个不同三角形 26 C 7 2 5 6 C 5 2 7 6 C 6 2 7 5 7 6 5 21 11 10 13 15 12 210 231 130 180 210 751 电线上停着两种鸟 A B 可以看出两只相邻的鸟就将电线分为了一个线段 这些线段可分为两类 一类是两端的小鸟相同 另一类则是两端的小鸟不相同 已知 电线两个顶点上正好停着相同的小鸟 试问两端为不同小鸟的线段数目一定是 B A 奇数 B 偶数 C 可奇可偶 D 数目固定 192 168 0 1 属于 C A A 类地址 B B 类地址 C C 类地址 D D 类地址 最高位 1 126 为 A 类 128 191 是 B 类 192 223 是 C 类 关于 0 的原码 反码和补码描述正确的是 C A 0 的原码只有一种表示方法 B 0 的反码只有一种表示方法 C 0 的补码只有一种表示方法 D 0 的原码 反码和补码均有两种表示方法 借助一个栈 输入顺序是 123456 以下输出顺序不可能的是 A A 142356 B 123654 C 231456 D 213546 对整数 N 8934632178 每次删除一个位置上的数字 使得新的数尽可能小 那么第四次删掉的数字是 D A 6 B 8 C 7 D 4 中缀表达式 A B C D E 的后缀表达式形式是 D E AB C D E F ABC D E G ABCD E H ABCD E 已知 A 11001010B B 00001111B C 01011100B A V B C B A 11001110 B 01110110 C 11101110 D 01001100 2 128KB 的存储器用十六进制表示 它的最大的地址码是 C A 10000 B EFFF C 1FFFF D FFFFF E FFFF 3 能将高级语言程序转换为目标程序的是 D A 调试程序 B 解释程序 C 编辑程序 D 编译程序 E 连接程序 9 一棵 n 个结点的完全二叉树 则二叉树的高度 h 为 D A n 2 B log2n C log2n 2 D log2n 1 E 2n 1 10 下图对该图进行广度优先拓朴排序得到的顶点序列正确的是 C A 1 2 3 4 5 6 B 1 3 2 4 5 6 C 1 3 2 4 6 5 D 1 2 3 4 6 5 27 E 1 3 2 4 5 6 11 下列属于冯 诺依曼计算机模型的核心思想是 ABC A 采用二进制表示数据和指令 B 采用 存储程序 工作方式 C 计算机硬件有五大部件 运算器 控制器 存储器 输入和输出设备 D 结构化程序设计方法 E 计算机软件只有系统软件 14 下面关于算法的正确的说法是 ACDE A 算法必须有输出 B 算法必须在计算机上用某种语言实现 C 算法不一定有输入 D 算法必须在有限步执行后能结束 E 算法的每一步骤必须有确切的定义 15 下列关于十进制数 100 的正确说法是 ABD A 原码为 01100100B B 反码为 64H C 反码为 9BH D 补码为 64H E 补码为 9BH 19 对于一个大小为 3 的栈 若输入顺序为 123456 则下列输出顺序有可能的是 AE A 123456 B 654321 C 432165 D 431256 E 321654 20 设有一个含有 13 个元素的 Hash 表 0 12 Hash 函数是 H key key 13 其中 是求余数 运算 用二次探查法解决冲突 则对于序列 31 20 33 18 53 27 则下列说法正确 的是 BCDE A 27 在 1 号格子中 B 33 在 6 号格子中 C 31 在 5 号格子中 D 20 在 7 号格子中 E 18 在 4 号格子中 图灵 Alan Turing 是 B A 美国人 B 英国人 C 德国人 D 匈牙利人 E 法国人 第一个给计算机写程序的人是 B A Alan Mathison Turing B Ada Lovelace C John von Neumann D John Mc Carthy E Edsger Wybe Dijkstra 无向图 G 有 16 条边 有 3 个 4 度顶点 4 个 3 度顶点 其余顶点的度均小于 3 则 G 至少 个顶点 11 某年级学生共选修 6 门课程 期末考试前 必须提前将这 6 门课程考完 每人每天只在下午至多考一门课程 设 6 门课程为 C1 C2 C3 C4 C5 C6 S Ci 为学习 Ci 的学生集合 已知 S Ci S C6 i 1 2 5 S Ci S Ci 1 i 1 2 3 4 S C5 S C1 问至少安排 天才能考 完这 6 门课程 4 一个家具公司生产桌子和椅子 现在有 113 个单位的木材 每张桌子要使用 20 个单位的木材 售价是 30 元 每张椅子要使用 16 个单位的木材 售价是 20 元 使用已有的木材生产桌椅 不一定要把木材用光 最多可以 卖 160 元钱 75 名儿童到游乐场去玩 他们可以骑旋转木马 坐滑行铁道 乘宇宙飞船 已知其中 20 人这三种东西都玩过 55 人至少玩过其中的两种 若每样乘坐一次的费用是 5 元 游乐场总共收入 700 可知有 10 名儿童没有玩 28 过其中任何一种 已知 a b c d e f g 七个人中 a 会讲英语 b 会讲英语和汉语 c 会讲英语 意大利语和俄语 d 会讲汉语和日 语 e 会讲意大利语和德语 f 会讲俄语 日语和法语 g 会讲德语和法语 能否将他们的座位安排在圆桌旁 使得每个人都能与他身边的人交谈 如果可以 请以 a b 开头写出你的安排方案 下列关于高级语言的说法错误的是 C A Fortran是历史上的第一个面向科学计算的高级语言 B Pascal和C 都是编译执行的高级语言 C C 是历史上的第一个支持面向对象的语言 D 编译器将高级语言程序转变为目标代码 E 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 设A true B false C false D true 以下逻辑运算表达式值为真的是 D A A B C D B A B C D C A B C D D A B C D E A B C D 其他问题类型 写运行结果 写运行结果的题 大家一定不要错过这个得分点 对于简单的问题 没有循环或者循环次数很少 机械的模拟 是可行的 只要仔细即可 var u array 0 3 of integer a b c x y z integer begin read u 0 u 1 u 2 u 3 a u 0 u 1 u 2 u 3 5 b u 0 u 1 u 2 div u 3 8 c u 0 u 1 div u 2 u 3 x a b 2 3 u c 3 mod 4 y c 100 13 div a div u b mod 3 5 if x y mod 2 0 then z a b c x y div 2 z a b c x y 2 writeln x y z end 输入 2 5 7 4 输出 263 var i number ndata sum integer data array 1 100 of integer procedure solve s sign n integer var i integer begin for i s to ndata do begin inc sum sign number div n data i solve i 1 sign n data i 29 end end begin read number ndata sum 0 for i 1 to ndata do read data i solve 1 1 1 writeln sum end 输入 1000 3 5 13 11 输出 328 几大方法 a 直接模拟 b 先模拟几次循环后找规律 c 直接看程序了解算法功能 d 了解程序本质后换一个方法解决 e 有时不知道算法可以通过观察猜出来 f 极少数的格子可以放弃 一般做这类题目的核心是找程序目的 即这个程序想干什么 很少有复杂的程序是 乱写 的 总有一点 写作 目的 抓住了它 不仅得出答案变得很容易了 而且对自己的结果也会比较有信心 机械模仿计算机硬算出结果的 同学往往做的慢的多 而且容易失误 99 年分区联赛 Program excpl var x y y1 jk j1 g e Integer a array 1 20 of 0 9 begin x 3465 y 264 jk 20 for j1 1 to 20 do a j1 0 while y0 do begin y1 y mod 10 y y div 10 while y10 do begin g x for e jk downto 1 do begin g g a e a e g mod 10 g g div 10 end y1 y1 1 end 30 jk jk 1 end j1 1 while a j1 0 do j1 j1 1 for Jk j1 to 20 do write a jk 4 writeln end 程序不长 但是有一定的难度 但其实有经验的话 看到 g 这个变量名和 g g a e a e g mod 10 这几个 标志句子 就可以一下子知道程序的用意了 高精度加法 对 它执行了 y1 次 y1 每次都是 y 的个位 程序就是在做 x y 所以答案就是 3465 264 914760 再看它的输出格式 输出的应该是 9 1 4 7 6 0 var n jr jw jb integer ch1 char ch array 1 20 of char begin readln n for i 1 to n do read ch i jr 1 jw n jb n while jr jw do begin if ch jw R then begin ch1 Ch jr Ch jr ch jw ch jw ch1 jr jr 1 end else if ch jw W then jw jw 1 else begin ch1 ch jw ch jw ch jb ch jb ch1 jw jw 1 jb jb 1 end end for i 1 to n do write ch i writeln end 输入 10 RBRBWWRBBR 输出 RRRRWWBBBB 这道题的关键在于看出交换两个变量的块 以及 jr jw 和 jb 的含义 整个过程有点像排序 31 var a array 1 50 of integer n i sum integer procedure work p r integer var i j temp integer begin if p a r then begin inc i temp a i a i a j a j temp end temp a i 1 a i 1 a r a r temp work p i work i 2 r end end begin read n for i 1 to n do read a i work 1 n for i 1 to n 1 do sum sum abs a i 1 a i writeln sum end 输入 10 23 435 12 345 3123 43 456 12 32 100 输出 3223 关键在于先看出 work 是快速排序 其次最后计算 sum 的时候化简 质数 Var I j s sp1 integer p boolean a array 1 10 of integer begin sp1 1 a 1 2 j 2 while sp1 10 do begin j j 1 p true for i 2 to j 1 do if j mod i O then p false if p then begin sp1 sp1 1 a sp1 j end 32 end j 2 p true while p do begin s 1 for i 1 to j do s s a I s s 1 for i 2 to s 1 do if S mod i O then p false j j 1 end writeln s writeln end 输出 30031 Var d1 d2 X Min real begin min 10000 X 3 while X 15 do begin d1 sqrt 9 X 3 X 3 d2 sqrt 36 15 X 15 X if d1 d2 0 DO 高精度分解 BEGIN J J 1 B J M