信息学奥赛初赛复习题

第 页0 信息学奥赛初赛复习信息学奥赛初赛复习 金陵中学河西分校金陵中学河西分校 内部资料 注意保密 第 页1 第一部分 选择题第一部分 选择题 一 一 计算机发展历程 计算机发展历程 NOI2007笔试复习题 部分 笔试复习题 部分 1 NOI机试使用的操作系统是 A Windows B Linux C MacOS D Vxworks 2 Linux中为文件改名使用的命令是 A mv B ren C chroot D su 3 在Linux中返回上一级目录使用的命令是 A cd B cd C cd D cd 4 使用高级语言编写的程序称之为 A 源程序 B 编辑程序 C 编译程序 D 链接程序 5 属于面向对象程序设计语言的是 A C B C C Pascal D Basic 6 在Linux系统中 下面的说法中正确的是 A 文件夹中的文件可以与该文件夹同名 B 文件夹中的文件不能与该文件夹同名 C 在不同文件夹中的两个文件不可以使用相同的文件名 D 以上说法都不对 7 一个完整的计算机系统应包括 A 系统硬件和系统软件 B 硬件系统和软件系统 C 主机和外部设备 D 主机 键盘 显示器和辅助存储器 8 目前微型计算机中采用的逻辑组件是 A 小规模集成电路 B 中规模集成电路 C 大规模和超大规模集成电路 D 独立组件 9 软件与程序的区别是 A 程序价格便宜 软件价格昂贵 B 程序是用户自己编写的 而软件是由厂家提供的 C 程序是用高级语言编写的 而软件是由机器语言编写的 D 软件是程序以及开发 使用和维护所需要的所有文档的总称 而程序是软件的一部分 10 IT表示 A 通信技术 B 信息技术 C 网络技术 D 信息学 11 计算机中央处理器简称为 A IBM B UBS C CPU D Computer 11 计算机内存储器的作用是 A 用来存放暂时不用的程序和数据 B 用来存放当前CPU正在使用的程序和数据 C 用来存放要删除的信息 D 仅用来存储选手的数据和程序 12 用来全面管理计算机硬件和软件资源的软件叫 A 操作系统 B 应用软件 C 管理软件 D 系统平台 13 LAN是指 A 互联网 B 局域网 C 广域网 D 城域网 14 在微机中 bit 的中文含义是 A 二进制位 B 字 C 字节 D 双字 第 页2 15 为了避免混淆 十六进制数在书写时常在后面加字母 A H B O C D D B 16 计算机所能辨认的最小信息单位是 A 位 B 字节 C 字 D 字符串 17 ASCII的含义是 A 条件码 B 二 十进制编码 C 二进制码 D 美国信息交换标准代码 18 在计算机术语中经常用RAM表示 A 只读存储器 B 可编程只读存储器 C 动态随机存储器 D 随机存取存储器 19 RAM存储器在断电后 其中的数据会 A 丢失 B 自动保存 C 不变化 D 需人工保存 20 ROM存储器在断电后 其中的数据会 A 丢失 B 自动保存 C 不变化 D 需人工保存 21 现代计算机所应用的存储程序原理是 提出的 A 图灵 B 布尔 C 冯 诺依曼 D 爱因斯坦 22 计算机内所有的信息都是以 数码形式表示的 A 八进制 B 十进制 C 二进制 D 十六进制 23 计算机能直接识别和执行的语言是 A 机器语言 B 汇编语言 C C语言 D Pascal语言 24 Linux是一个 操作系统 意思是源码可以免费获得 A 开源的 B 有使用许可的 C 不开放源代码的 25 NOI的中文意思是 A 中国信息学奥赛 B 中国国家奥委会 C 国际信息学奥赛D 中国信息学联赛 重要作业重要作业 1 微机内的存储器的地址是以 编址的 A 二进制位 B 字长 C 字节 D 微处理器的型号 2 在 24 24 点阵的字库中 汉字 一 与 编 的字模占用字节数分别是 A 32 32 B 32 72 C 72 72 D 72 32 3 不同的计算机 其指令系统也不相同 这主要取决于 A 所用的操作系统 B 系统的总体结构 C 所用的 CPU D 所用的程序设计语言 4 2KB的内存能存储 个汉字的机内码 A 1024 B 516 C 2048 D 218 5 下列哪个 些 软件不是操作系统软件的名字 A WindowsXP B DOS C Linux D OS 2 E ARCH INFO 6 美籍匈牙利数学家冯 诺依曼对计算机科学发展所做出的贡献是 A 提出理想计算机的数学模型 成为计算机科学的理论基础 B 是世界上第一个编写计算机程序的人 C 提出存储程序工作原理 并设计出第一台具有存储程序功能的计算机 EDVAC D 采用集成电路作为计算机的主要功能部件 第 页3 E 指出计算机性能将以每两年翻一番的速度向前发展 7 下列哪个不是 CPU 中央处理单元 A Intel Itanium B DDR SDRAM C AMD Athlon64 D AMD Opteron E IBM Power 5 8 下面哪个部件对于个人桌面电脑的正常运行不是必需的 A CPU B 图形卡 显卡 C 光驱 D 主板 E 内存 9 下列哪个软件属于操作系统软件 A Microsoft Word B 金山词霸 C Foxmail D WinRAR E RED HAT LINUX 10 下列哪个不是计算机的存储设备 A 文件管理器 B 内存 C 高速缓存 D 硬盘 E U 盘 11 下列哪个程序设计语言不支持面向对象程序设计方法 A C B Object Pascal C TURBO PASCAl D Smalltalk E Java 12 设有一个十阶的对称矩阵 A 采用压缩存储方式 以行序为主存储 a11 为第一个元 素 其存储地址为 1 每个元素占 1 个地址空间 则 a85 的地址为 A 13 B 33 C 18 D 50 13 奔腾的地址线是 32 根 最大存储量为 A 4GB B 4MB C 32MB 14 JPEG 是一种 的图象压缩方式 A 有损压缩 B 无损压缩 C 不可压缩 D 以上都正确 15 一台计算机的字长是 8 字节 表示是 A 能处理的数字最大是 8 个十进制数 99999999 B 能处理的字符串最多由 8 个英文字母组成 C 在 CPU 中作为一个整体加以传送处理二进制代码为 64 位 D CPU 的运行的最大结果为 2 的 64 次方 16 微型计算机内存储器是按 A 二进制位编码 B 字节编码 C 字长编码 D CPU 的型号不同而编址不同 17 下列叙述中正确的是 A 汉字的计算机内存是国际码 B 存储器具有记忆能力 其中的信息任何时候都不会消失 C 所有十进制数都能准确的转换为二进制数 D 正数的二进制原码的补码是原码本身 第 页4 18 PASCAL 编译程序的功能是 A 把 PASCAL 源程序转换成可运行的 EXE 文件 B 生成和修改一个 PASCAL 源程序 C 实现 PASCAL 的源程序到等价的目标程序的转换 D 实现 PASCAL 的源程序到等价的目标码程序的转换 19 操作系统是对什么进行管理的系统软件 A 软件 B 硬件 C 计算机资源 D 应用程序 20 计算机处理信息的精度决定于 A CPU主频 B 硬盘的容量 C 系统总线的传输频率 D CPU字长 21 计算机的基本硬件结构一直沿袭 设计的框架 A 比尔 盖茨 B 冯 诺依曼 C 布尔 D 图灵 22 在流程图的符号中 菱形框一般作为 A 起止框 B 输入输出框 C 判断框 D 处理工作框 23 算法的3种结构是 A 顺序 分支 循环 B 顺序 重复 循环 C 顺序 分支 判断 D 顺序 流程 循环 24 用于管理计算机资源 方便用户使用计算机的是 A 数据库 B 应用软件 C 操作系统 D 计算机语言 25 分辨率为1280 1024真彩色 16位 的17英寸显示器的显存容量应为 MB A 1 B 2 5 C 4 D 8 26 计算机的主存储器容量达到1GB时 其地址的表示至少需要使用 个2进制位 A 10位 B 20位 C 30位 D 40位 27 PASCAL程序运行时 是在哪种存储器中进行 A 硬盘 B RAM C ROM D CACHE 三 计算机中数的表示三 计算机中数的表示 1 十进制算术表达式 3 512 7 64 4 8 5 的运算结果 用二进制表示为 A 10111100101 B 11111100101 C 11110100101 D 11111101101 2 计算机中的数有浮点与定点数两种 其中用浮点数表示的数 通常由 这两部 分组成 A 指数与基数 B 尾数与小数 C 阶码与尾数 D 整数与小数 3 x 补码 10011000 其原码为 A 011001111 B 11101000 C 11100110 D 01100101 4 表达式 1 34 5 56 7 的后缀表达式为 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 5 8 位无符号二进制数能够表示的最大十进制数是 第 页5 A 255 B 256 C 64 D 63 6 已知 A 72E H B 1315 D 则 A B 的结果是 A 674 O B 1AD H C 523 D D 101101011 B 7 产生 100 至 300 之间的随机整数 Random 且包含 100 300 两个整数的表达式 A Random 100 200 B Random 200 100 C RANDOM 201 100 D Random 300 8 在微型计算机中 常用 码实现十进制数与二进制数之间的自动转换 A BCD 码 B ASCII 码 C 海明码 D 机内码 9 设有一个十阶的对称矩阵 A 采用压缩存储方式 以行序为主存储 a11为第一个元素 其存储地址为 1 每个元素占一个地址空间 则 a85的地址为 A 13 B 33 C 18 D 50 10 ASCII 码的主要作用是 A 便与信息交换 B 便于信息存储 C 便于管理 D 便于输出 11 二进制数 0 1101010的补码是 A 0010101 B 10010110 C 10010101 D 01101010 12 国际信息交换码ASCII码的长度为1个字节 其中的最高位为0 因此ASCII码表中的 符号有 个 A 127 B 128 C 255 D 256 13 十进制数100的反码和补码表示分别是 A 9BH和64H B 64H和9BH C 64H和64H D 9BH和9BH 14 关于 零 的原码 反码 补码 下列说法正确的是 A 零的原码表示只有一种 B 零的反码表示只有一种 C 零的补码表示只有一种 D 零的原码 反码 补码表示都有两种 四 四 网络知识网络知识 1 1 调制解调器又称为 Modem 可用于连结计算机与电话线拨号上网 调制是指 A 把电信号转换成光信号 B 把光信号转换成电信号 C 把模拟信号转换成数字信号 D 把数字信号转换成模拟信号 2 2 OSI 的 7 层协议中 最底层是 A 会话层 B 数据链接层 C 物理层 D 网络层 3 3 网络通信协议 如 Internet 采用的 TCP IP 协议是一组 A 软件 B 存储器 C 外部设备 D 约定的规则 第 页6 4 4 国际互联网的目的在于使不同网络上的用户相互通信 交换信息 那么用于网络之间 互连的中继设备称 A 放大器 B 网桥 C 网关 D 网间连接器 5 5 在 TCP IP 协议中 TCP 和 IP 分别提供什么服务 A 传输层 网络层 B 链路层 网络层 C 传输层 会话层 D 物理层 链路层 6 6 TCP IP 协议是指 A 文件传输协议 远程登陆协议 B 邮件传输协议 远程登陆协议 C 传输控制协议 因特网互联协议 D 文件传输协议 邮件传输协议 7 7 Intel 给我们提供了资源共享 浏览 检索信息和远程登录等多种服务 下面几个选 项中用于远程登录的是 A Telnet B E Mail C TCP IP D WWW 8 IE是目前流行的浏览器软件 它的工作基础是解释执行用 语言书写的文件 A VC B C C HTML D HTTP 9 计算机网络最大的优点是 A 精度高 B 资源共享 C 运行速度快 D 存储容量大 E 逻辑判断能力强 10 TCP IP 协议共有 层协议 A 3 B 4 C 5 D 6 11 IP v4 地址是由 位二进制数码表示的 A 16 B 32 c 24 D 8 五 五 二进制的二进制的逻辑运算逻辑运算 1 已知 A 11001010B B 00001111B C 01011100B A B C B A 11001110 B 01110110 C 11101110 D 01001100 2 已知A 35H A 05H A 30H 的结果是 提示 先化成二进制 A 30H B 05H C 35H D 53H 3 假设A true B false C true D true 逻辑运算表达式A B C D的值是 A true B false C 0 D 1 E NULL 4 逻辑代数式子 f AB ABC AB C D 则 f 的简化式子为 A AB B A B C ABC D ABCD 5 两个十进制数13与14 将它们进行 与 运算 其值为 A 27 B 12 C 15 D 11 6 在 Pascal 程序中 表达式 200 or 10 的值是 A 20 B 1 C 220 D 202 7 在 Pascal 语言中 表达式 23 or 2 xor 5 的值是 A 18 B 1 C 23 D 32 六 集合运算六 集合运算 1 设全集 E 1 2 3 4 5 集合 A 1 4 B 1 2 5 C 2 4 则集合 A 第 页7 B C 为 A 空集 B 1 C 3 5 D 1 5 E 1 3 5 2 设全集 I a b c d e f g 集合 A a b c B b d e C e f g 那么集合 为 BCBA A a b c d B a b d e C b d e D b c d e E d f g 3 已知集合 E 2 请问 的所有子集个数是多少 25 10 32 64 4 设全集 E 1 2 3 4 5 集合 A 1 2 5 B 1 4 C 2 4 则集合 A B C A B 为 A 空集 B 1 C 2 4 D 1 3 5 七 数据结构七 数据结构 1 已知队列 13 2 11 34 41 77 5 7 18 26 15 第一个进入队列的元素是 13 则第五个出队列的元素是 A 5 B 41 C 77 D 13 E 18 2 线性表若采用链表存贮结构 要求内存中可用存贮单元地址 A 必须连续 B 部分地址必须连续 C 一定不连续 D 连续不连续均可 3 下列叙述中 正确的是 A 线性表的线性存贮结构优于链表存贮结构 B 队列的操作方式是先进后出 C 栈的操作方式是先进先出 D 二维数组是指它的每个数据元素为一个线性表的线性表 4 某数列有 1000 个各不相同的单元 由低至高按序排列 現要对该数列進行二分法检 索 binary search 在最坏的情況下 需检视 个单元 A 1000 B 10 C 100 D 500 5 在顺序表 2 5 7 10 14 15 18 23 35 41 52 中 用二分法查找 12 所需 的关键码比较的次数为 A 2 B 3 C 4 D 5 6 以下哪一个不是栈的基本运算 A 删除栈顶元素 B 删除栈底的元素 C 判断栈是否为空 D 将栈置为空栈 7 设栈 S 和队列 Q 的初始状态为空 元素 e 1 e 2 e 3 e 4 e 5 e 6依次通过栈 S 一个元素出栈后即进入队列 Q 若出队的顺序为 e 2 e 4 e 3 e 6 e 5 e 1 则 栈 S 的容量至少应该为 A 2 B 3 C 4 D 5 8 设栈 S 和队列 Q 的初始状态为空 元素 e1 e2 e3 e4 e5 e6 依次通过栈 S 一个元素 出栈后即进入队列 Q 若出队的顺序为 e2 e4 e3 e6 e5 e1 则栈 S 的容量至少应该为 第 页8 2 3 4 5 9 对按关键字排序好的线性表进行二分查找 该线性表适合的存储结构为 A 顺序结构 B 链接存储 C 索引存储 D 散列存储 10 在数据结构中 链表是 A 顺序存储的线性表结构 B 非顺序存储的线性表结构 C 非顺序存储的非线性结构 D 顺序存储的非线性表结构 11 在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区 主要 将要输出打印的数据依次写入该缓冲区 而打印机从该缓冲区中取出数据打印 该缓冲 区应该是一个 结构 A 堆栈 B 数组 C 线性表 D 队列 E 链表 例 1 设某循环队列的容量为 50 如果头指针 front 45 指向队头元素的前一个位置 尾指针 rear 10 指向队尾元素 则该循环队列中共有 15 元素 答案 50 45 10 15 如果反过来 头 10 尾 45 则元素个数是 45 10 35 元素的个数是 当队尾元素的个数是 当队尾 队头的时候 队尾减去队头 反之 容量队头的时候 队尾减去队头 反之 容量 队头队头 队尾 队尾 例 2 若用一个大小为 6 的数组来实现循环队列 且当前 rear 和 front 的值 分别为 0 和 3 当从队列中删除一个元素 再加入两个元素后 rear 和 front 的值分别为 A 1 和 5 B 2 和 4 C 4 和 2 D 5 和 1 例 3 设循环队列中数组的下标范围是 1 n 其头尾指针分别为 f 和 r 则其元素个数为 A r f B r f 1 C r f MOD n 1 D r f n MOD n 八 八 树 详见高级本树 详见高级本 P108 111 补充作业补充作业 1 1 给出一棵二叉树的中序遍历 DBGEACHFI 与后序遍历 DGEBHIFCA 画出此二叉 树 2 2 已知 按中序遍历二叉树的结果为 abc 问 有多少种不同形态的二叉树可以得到这一遍历结果 并画出这些二叉树 5 种 3 一棵二叉树的高度为 h 所有结点的度为 0 或为 2 则此树最少有 个结点 A 2h 1 B 2h 1 C 2h 1 D h 1 4 4 按照二叉数的定义 具有 3 个结点的二叉树有 种 A 3 B 4 C 5 D 6 卡特兰数 NOI 专刊 第 3 期 25 页 5 5 设有一棵 k 叉树 其中只有度为 0 和 k 两种结点 设 n 0 n k 分别表示度为 0 和 度为 k 的结点个数 试求出 n 0 和 n k之间的关系 n 0 数学表达式 数学表达式 仅含 n k k 和数字 6 一个高度为 h 的二叉树最小元素数目是 第 页9 A 2h l B h C 2h 1 D 2h E 2h l 7 一棵含有 101 个结点的完全二叉树存储在数组 A 1 101 中 对 1 k 101 若 A k 是叶子结点 则 k 的最小值是 A 51 B 50 C 49 D 48 8 8 如果一棵 m 度树中有 n1 个度为 1 的结点 n2 个度为 2 的结点 有 nm 个度为 m 的结点 则该树中叶结点的的个数 A N1 B M N1 N2 C N1 2N2 M 1 NM 1 1 D N2 2N3 M 1 NM 1 9 对于一颗二叉树 T 设 n0 n1 n2 分别是度数为 0 1 2 的顶点数 则下列判断中正 确的是 A n0 n2 1 B n1 n0 1 C n2 n0 1 D n2 n1 1 10 一棵 n 个节点的完全二叉树 则该树的高度 h 为 A n 2 B log n C log n 2 D log n 1 四 图 详见高级本四 图 详见高级本 P123 126P123 126 运用 prim 算法和 kruskal 算法分别画出图 1 的最小生 成树形成的过程 2 3 4 4 5 7 12 九 排序算法 详见高级本 九 排序算法 详见高级本 重要作业重要作业 1 下列排序算法中 最坏情况下的时间复杂度最低的是 A 堆排序 B 选择排序 C 快速排序 D 插入排序 2 在待排序的数据表已经为有序时 下列排序算法中花费时间反而多的是 A 堆排序 B 希尔排序 C 冒泡排序 D 快速排序 3 利用改进的选择排序算法 从小到大 对以下数据 75 84 65 73 55 52 79 66 进行一趟操作的结果是 A 52 75 84 65 73 55 66 79B 75 65 73 55 52 79 66 84 C 52 84 65 73 55 75 79 66D 52 84 75 73 65 55 79 66 4 对有 18 个元素的有序表作二分查找 则查找 A 3 的比较序列的下标为 A 1 2 3 B 9 5 2 3 C 9 5 3 D 9 4 2 3 5 一个对象序列的排序码为 46 79 56 38 40 84 采用快速排序以位于最左位置 的对象为基准而得到的第一次划分结果为 A 38 46 79 56 40 84 B 38 79 56 46 40 84 C 40 38 46 56 79 84 D 38 46 56 79 40 84 综合练习综合练习 1 计算机各部分之间的信息传输是通过总线结构来实现的 总线又分为三部分 下列不 是总线三部分的是 第 页10 A 地址总线 B 数据总线 C 指令总线D 控制总线 2 计算机指令是由一些简单的电信号来控制的 机器指令通常包括 A 地址码 控制码B 控制码 操作码 C 识别码 操作码D 操作码 地址码 3 计算机网络的主要目的是实现资源共享 它采用了多种连接方式将多台计算机连接在 一起 以下不属于计算机网络采用的拓扑结构是 A 总线结构 B 星型结构 C 树型结构D 环型结构 4 在计算机中 防火墙的作用是 A 防止火灾蔓延 B 防止网络攻击 C 防止计算机死机 D 防止使用者误删除数据 5 网络协议是支撑网络运行的通信规则 因特网上最基本的通信协议是 A HTTP 协议 B TCP IP 协议 C POP3 协议 D FTP 协议 6 某处于环境恶劣高山之巅的气象台要在短期内接入 Internet 网 现在要选择连接山 上山下节点的传输介质 恰当的选择是 A 无线传输 B 光缆 C 双绞线 D 同轴电缆 7 在下列关于计算机算法的说法中 不正确的是 A 一个正确的算法至少要有一个输入 B 算法的改进 在很大程度上推动了计算机科学与技术的进步 C 判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性 D 目前仍然存在许多涉及到国计民生的重大课题 还没有找到能够在计算机上实施的有 效算法 8 线性表 a1 a2 an 以链表方式存储时 访问第 i 位置元素的时间复杂性为 A O i B O 1 C O n D O i 1 9 一个 n 个顶点的强连通图 至少有多少个有向边 A n 1 B n 1 n C n 1 n 2 D n 10 对有 18 个元素的有序表作二分查找 则查找 A 3 的比较序列的下标为 A 1 2 3 B 9 5 2 3 C 9 5 3 D 9 4 2 3 10 树形结构中数据元素之间存在 的关系 A 一对一 B 一对多 C 多对一 D 无法确定 11 链表不具有的特点是 A 可随机访问任一元素 B 插入删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与线性表长度成正比 12 广义表 A a a a 的深度为 A 3 B 4 C 5 D 6 13 请指出在顺序表 2 5 7 10 14 15 18 23 35 41 52 中 用二分法查 找关键码 12 需做多少次关键码比较 A 2 B 3 C 4 D 5 第 页11 14 一个对象序列的排序码为 46 79 56 38 40 84 采用快速排序以位于最左位 置的对象为基准而得到的第一次划分结果为 A 38 46 79 56 40 84 B 38 79 56 46 40 84 C 40 38 46 56 79 84 D 38 46 56 79 40 84 15 一数组构造双栈 栈 1 的栈底在数组的低端 栈 2 的栈底在数组的高端 如果进栈 的序列为 A B C D E 则执行操作栈 1 进栈 栈 2 进栈 栈 2 出栈 栈 1 出栈 栈 2 进栈 栈 2 进栈 栈 1 进栈 栈 2 出栈 栈 1 出栈 栈 2 出栈后得到的序列为 A BAEDC B CEDAB C BADEC D ABCDE 16 对于线性表 L a1 a2 an 下列说法正确的是 A 每个元素都有一个直接前驱和一个直接后继 B 线性表中至少要有一个元素 C 表中所有元素的大小排列顺序必须是由小到大或由大到小 D 除第一个和最后一个元素外 每个元素都有且仅有一个直接前驱和一个直接后继 17 利用改进的选择排序算法 从小到大 对以下数据 75 84 65 73 55 52 79 66 进行一趟操作的结果是 A 52 75 84 65 73 55 66 79B 75 65 73 55 52 79 66 84 C 52 84 65 73 55 75 79 66D 52 84 75 73 65 55 79 66 18 以下 不是栈的基本运算 A 删除栈顶元素 删除栈底元素 判断栈是否为空 将栈置为空栈 19 将下三角矩阵 A 1 8 L 8 的下三角部分逐行地存储到起始地址为 1000 的内存单 元中 已知每个元素占 4 个单元 则 A 7 5 的地址为 A 1020 B 1100 C 1080 D 1120 20 两个栈共享一个存储空间的好处是 A 节省存储空间 降低上溢发生的机率 B 减少存取时间 降低下溢发生的机率 C 节省存储时间 降低下溢发生的机率 D 减少存取时间 降低上溢发生的机率 21 一个递归算法必须包括 A 递归部分 B 终止条件和递归部分 C 迭代部分 D 终止条件和迭代部分 22 以下哪一个不是栈的基本运算 A 删除栈顶元素 B 删除栈底元素 C 判断栈是否为空 D 将栈置为空栈 23 一个对象序列的排序码为 46 79 56 38 40 84 采用快速排序以位于最左位 置的对象为基准而得到的第一次划分结果为 A 38 46 79 56 40 84 B 38 79 56 46 40 84 C 40 38 46 56 79 84 D 38 46 56 79 40 84 2424 线性表 L a1 a2 an 下列说法正确的是 A 每个元素都有一个直接前驱和一个直接后继 B 线性表中至少要有一个元素 C 表中诸元素的排列顺序必须是由小到大或由大到小 D 除第一个和最后一个元素外 每个元素都有一个仅有一个直接前驱和直接后继 第 页12 25 一个对象序列的排序码为 46 79 56 38 40 84 采用快速排序以位于最左位 置的对象为基准而得到的第一次划分结果为 A 38 46 79 56 40 84 B 38 79 56 46 40 84 C 40 38 46 56 79 84 D 38 46 56 79 40 84 2626 一棵二叉树如下图所示 若采用顺序存储结构 即用一 维数组元素存储该二叉树中的结点 根结点的下标为 l 若 某结点的下标为 i 则其左孩子位于下标 2i 处 右孩子位于 下标 2i 1 处 则该数组的大小至少为 A 6 B 10 C 12 D 15 27 为了提高测试的效率 应该 A 随机选取测试数据 B 取一切可能的输入数据作为测试数据 C 在完成编码以后制定软件的测试计划 D 集中对付那些错误群集的程序 2828 算法的时间复杂度是指 A 执行算法程序所需要的时间 B 算法程序的长度 C 算法执行过程中所需要的基本运算次数 D 算法程序中的指令条数 2929 树是节点的集合 它的根节点数目是 A 有且只有 1 B 1 或多于 1 C 0 或 1 D 至少 2 30 在编程时 使用任一种高级语言 不一定是 C 或者是 PASCAL 如果需要从磁盘文 件中输入一个很大的二维数组 例如 1000 1000 的 double 型数组 按行读 即外 层循环是关于行的 与按列读 即外层循环是关于列的 相比 在输入效率上 A 没有区别 B 按行读的方式要高一些 C 按列读的方式要高一些 D 取决于数组的存储方式 3131 下列排序算法中 每一趟都能选出一个元素放在其最终位置上 并且是不稳 定的 A 冒泡排序 B 希尔排序 C 直接选择排序 D 直接插入排序 32 64KB 的存储器用十六进制表示 它的最大的地址码是 A 10000 B FFFF C 1FFFF D EFFFF 3333 PC 机中 CPU 进行算术和逻辑运算时 可处理的信息的长度为 A 32 位 B 16 位 C 8 位 D 都可以 34 一棵完全二叉树 如果其上有一个结点的编号为 11 则其父结点的编号为 A 22 B 12 C 10 D 5 35 下面关于主存储器 也称为内存 的叙述中 不正确的是 A 当前正在执行的指令与数据都必须存放在主存储器内 否则处理器不能进行处理 B 存储器的读 写操作一次读出或写入一个字节 C 字节是主存储器中信息的基本编址单位 第 页13 D 从程序设计的角度来看 cache 高速缓存 也是主存储器 36 计算机的主存储器容量达到 1GB 时 其地址的表示至少需要使用多少个 2 进位 A 10 位 B 20 位 C 30 位 D 40 位 37 MIPS 是衡量 CPU 处理速度的一种常用指标 它的含义是 A 每秒钟平均可执行的单字长定点指令的数目 B 每秒钟平均可执行指令的数目 C 每秒钟平均可执行的浮点指令的数目 D 每秒钟平均可执行的算术运算指令的数目 38 一幅 1024 768 的彩色图像 其数据量达 2 25MB 左右 若图像数据没有经过压缩处 理 则该图像中的每一个像素是使用多少个二进位表示的 A 8 位 B 16 位 C 24 位 D 32 位 39 互联网络上的服务都是基于一种协议 WWW 服务基于 协议 A SMIP B HTTP C SNMP D TELNET 40 无向图 G V E 其中 V a b c d e f E a b a e a c b e c f f d e d 对该图进行深度优先遍历 得到的顶点序列正确的是 A a b e c d f B a c f e b d C a e b c f d D a b e d f c 第二部分第二部分 问题求解问题求解 排列与组合 详见高级本 排列与组合 详见高级本 数据结构数据结构 奥数奥数 递推等递推等 重要作业重要作业 1 平面上有三条平行直线 每条直线上分别有 7 5 6 个点 且不同直线上三个点 都不在同一条直线上 问用这些点为顶点 能组成多少个不同三角形 2 子集划分 将 n 个数 1 2 n 划分成 r 个子集 每个数都恰好属于一个子集 任何两个不同的子集没有共同的数 也没有空集 将不同划分方法的总数记为 S n r 例如 S 4 2 7 这 7 种不同的划分方法依次为 1 234 2 134 3 124 4 123 12 34 13 24 14 23 当 n 6 r 3 时 S 6 3 提示 先固定一个数 对于其余的 5 个数考虑 S 5 3 与 S 5 2 再分这两种情况对原 固定的数进行分析 提示 S 6 3 S 5 2 3 S 5 3 S m n s m 1 n 1 n S m 1 n 123 11 211 3131 4176 511525 61 第 页14 3 某商店有 m 种不同颜色的小球且每种小球的数量都足够多 要在这 m 种不同颜色的小 球里挑选出 n 个小球 设共有 s 种不同的选法 例如当 m 2 n 3 时 s 等于 4 也就是 说 共有 4 种不同的选法 分别为 0 3 1 2 2 1 3 0 现在 令 m 6 n 5 试求出选法数 s 12345 111111 223456 336101521 44 55 66 4 给出一组顶点 顶点值用 A B C D E F 表示 其对应权值分别为 2 3 1 7 8 4 请以 A B C D E F 为叶子顶点构造一棵哈夫曼树 并求出它的 最小带权路径长度 WPL 的值 5 今天是放寒假的最后一天 马上迎来 2011 年春节 住在同一个宿舍的四名同学为了 相互祝愿 每人各设计了一张贺年卡送给别人 为了避免矛盾 他们将贺年卡先集中起 来 然后让每人从中拿一张别人送的贺年卡 问四张不同的贺年卡有多少种不同的取法 错排问题 8 金中机器人小 P 由 P1 P2 P3 P4 P5 P6 六个子部件组成 这些子部件之间有下 列关系 P1 P2 P1 P3 P1 P4 P2 P3 P2 P5 P3 P5 P3 P6 P4 P3 P4 P6 P5 P6 表示先于关系 如 P1 P2 表示 P1 子部件完成安装后才能进行子部件 P2 的安装工 作 请搞信息学竞赛的你告诉金中机器人兴趣小组的同学该如何安装小 P 注意 一个 时间段只能安装一个子部件 如果有多种安装方法 只需给出其中一种安装秩序 9 设计法码称重 要求 1 不同重量的法码最多设计一个 2 必须能称出规定重量以内所有物品的重量 3 设计最少的法码 如要称 4 克以内的重量 可设计 2 种不同重量的法码 1 克和 3 克 可称 1 克到 4 克重量 若称 1000 克以内重量的物品 需要设计的最少法码个数 10 有 14 个人排队买票 每人要买一张票 票价每张 50 元 恰有 7 个人只有 50 元钞 票 7 个人只有 100 元钞票 已知开始售票之前售票员无零钱 问有多少种排法使得售票 员不至于找不开钱 拿着同样面值钞票的人视为等价 11 一位大城市的律师在他住所以北 n 个街区和以东 n 个街区处工作 每天他走 2n 个街 区去上班 如果他从不穿越 但可以碰到 从家到办公室的对角线 那么有多少条可能 的道路 12 设有一棵 k 叉树 其中只有度为 0 和 k 两种结点 设 n 0 n k 分别表示度为 0 第 页15 和度为 k 的结点个数 试求出 n 0 和 n k之间的关系 度之和 nk k 结点数 13 一棵二叉树的先序 中序 后序遍历序列分别如下 其中有一部分未显示出来 请 补全各序列 先序 ABDFKICEHJG 中序 DBKFIAHEJCG 后序 DKIFBHJEGCA 14 假定一个 AOV 网的顶点集和边集为 V 0 1 2 3 4 5 6 7 8 9 E 若在他的邻接表存储结构中 每个顶点邻接表中的边结点都是按照终点 序号从大到小链接的 则写出唯一一种拓朴序列 15 如图表示一个地区的通讯网 边表示城市间的通讯线路 边上的权表示架设线路花 费的代价 如何选择能沟通每个城市且总代价最省的 n 1 条线路 画出所有可能的选择 16 对于下面这棵树 写出它的先根遍历结果 2 分 然后将该树转换成二叉树 17 对下图所示的带权无向图 写出深度优先搜索 序列 从 1 出发 3 分 并按 克鲁斯卡算法求其最小生成树 18 对于下面的有向图 有多少种不同的拓朴序列 第 页16 第三部分第三部分 写程序运行结果写程序运行结果 一 模拟法一 模拟法 死算死算 1 var a work array 1 100 of integer i j x d max integer begin read max for i 1 to max do begin read a i work i a i end d max div 2 while d 1 do begin for i d 1 to max do begin x work i j i d while j 0 and x A and zimu Z for i A to zimu do begin write ord zimu ord i 1 for j A to i do write j for j pred i downto A do write j if ord i 64 mod 25 0 then readln else writeln end end 输入 E 输出 4 Var I j integer A array 1 3 1 3 of integer Begin For i 1 to 3 do Begin For j 1 to 3 do Begin If i 3 then a I j a i 1 a i 1 j 1 else a I j j write a I j end writeln end end 5 var i j l n k s t integer 第 页18 b array 1 10 of 0 9 begin readln l n s l k 1 t l while s0 do begin j j 1 b j n mod l n n div l end for i 10 k 1 to 10 do write chr ord A b i END 输入 5 257 二 分析公式 规律二 分析公式 规律 1 Var g integer k t real m integer Begin K 0 g 0 For m 1 to 49 do Begin g g 1 k k 1 g g 1 end writeln k 10 2 End 2 var n i integer total longint function work a b integer longint var c d e longint i integer begin c 1 for i 2 to a do c c i d 1 for i 2 to b do d d i e 1 for i 2 to a b do e e i exit c div d div e end begin read n 第 页19 total 0 for i 1 to n do total total work n i write total end 输入 输入 12 3 var a b c integer function D b integer integer var t integer begin if b 0 then D 1 else begin t D b div 2 t t t mod c if odd b then D t a mod c else D t end end begin readln a b c writeln D b end 输入 993 294 10 输出 4 Var M n I p k integer r array 1 200 of integer b Boolean begin m 6 n 2 for i 1 to m 1 do r i i 1 r m 1 i 0 p 1 b true while b do begin i i 1 k p P r p if k p then begin writeln p b false end else if i n 1 then begin write p i 0 p r p r k p end end end 5 var a array 1 10 of integer s n m longint flag set of byte procedure try dep integer var i integer begin 第 页20 for i 1 to n do if not i in flag then begin flag flag i a dep i if dep m then inc s else try dep 1 flag flag i end end begin readln m n flag s 0 try 1 writeln s end 输入 4 5 三 字符串处理三 字符串处理 1 Var N I tem t longint S string Begin readln n S 1 Repeat I length s While s i 1 do Begin S i 0 dec i End If i 0 then s i 1 else s 1 s Val s t tem Until t mod n 0 Writeln n t div n s End 输入 6 2 var s string n p q i integer a array 1 10 of char c char begin readln n s OIF Fly with the same dream p pos s s 第 页21 s copy s p 19 255 s copy s n 255 c a q 1 for i 1 to length s do if s i c then begin a q s i c a q inc q end dec q for i 1 to q do write a i end 输入 输入 2 3 var len n word string0 string function l st string i integer string begin len length st if len 0 or len n then l st else l copy st 1 n end function r st string n integer string begin len length st if len 0 or lenb then max a else max b end begin b 0 0 b 1 0 b 2 1 write n readln n for i 3 to n do begin min 999 for k 1 to i div 2 do begin buf max b i 2 k b k if min buf then min buf end b i 1 min end writeln b n end 输入 n 32 4 var x y z integer proedure silly x integer var y integer begin x 5 y 6 z 3 writeln x 2 y 2 z 2 end begin x 1 y 2 z 3 第 页23 silly x y writeln x 2 y 2 z 2 end 五 递归五 递归 1 Function f var x integer y z integer integer Begin X x y z F x End Begin x 1 y 2 z 3 y f x f x y z z x y Writeln x 4 y 4 z 4 End 2 Const n 10 Function fn n integer integer Begin If n 1 then fn 0 Else if n 1 then Fn 1 Else Fn fn n 1 n End Begin Writeln fn n Re