tceic.com
简单学习网 让学习变简单
相关标签
当前位置:首页 >> 学科竞赛 >>

江苏省南通中学NOIP初赛练习题之一(选择题) 2


江苏省南通中学 NOIP 初赛练习题之一(选择题)
前言: 每年的 NOIP 初赛第一部分都是选择题,其中初中组二十道全是单选题,高中组前十道 为单选后十道为多项选择题,总分 30。主要考查一些基础知识,包括操作系统、计算机基 本原理、数据结构、网络等方面的知识,这主要在于平时的积累。 单选题 多选题

相关知识点与参考答案 一、单选题
1

、下列软件均属于操作系统的是( ) A.WPS 与 PC DOS B.WINDOWS 与 MS DOS C.Unix 与 Word D.FOXBASE 与 OS/2 2、微机内的存储的地址是以( )编址的。( ) A.二进制位 B.字长 C.字节 D.微处理器的型号 3、启动计算机引导操作系统是将操作系统( ) A.从磁盘调入中央处理器 B.从内存储器调入高速缓冲存储器 C.从软盘调入硬盘 D.从系统盘调入内存储器 4、 不同类型的存储器组成了多层次结构的存储器体系, 按存取速度从快到慢排列的是( A.快存/辅存/主存 B.外存/主存/辅存 C.快存/主存/辅存 D.主存/辅存/外存 5、下列诸因素中,对微机工作影响最小的是( ) A.尘土 B.噪声 C.温度 D.湿度 6、计算机能直接执行的指令包括两部分,它们是( ) A.源操作数与目标操作数 B.操作码与操作数 C.ASCII 码与汉字代码 D.数字与字符 7、在微机中,通用寄存器的位数是( ) A.8 位 B.16 位 C.计算机字长 D.32 位 8、不同的计算机,其指令系统也不相同,这主要取决于( ) A.所用的 CPU B.所用的操作系统 C.所用的程序设计语言 D.系统的总体结构 9、RAM 中的信息是( ) A.生产厂家预先写入的 B.计算机工作时随机写入的 C.防止计算机病毒侵入所使用的 D.专门用于计算机开机时自检用的 10、WINDOWSXP 是一种( )操作系统( ) A.单任务字符方式 B.单任务图形方式 C.多任务字符方式 D.多任务图形方式 11、操作系统是重要的系统软件,下面几个软件中不属于操作系统的是( ) A.Unix B.Linux C.PASCAL D.WINDOWS 98 12、在 24*24 点阵的字库中,汉字“一”与“编”的字模占用字节数分别是( ) A.72、72 B.32、32 C.32、72 D.72、32 13、计算机主机是由 CPU 与( )构成的 A.控制器 B.运算器 C.输入、输出设备 D.内存储器 14、计算机系统总线上传送的信号有( ) A.地址信号与控制信号 B.数据信号、控制信号与地址信号 C.控制信号与数据信号 D.数据信号与地址信号
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

)

1

15、在计算机内部用来传送、存贮、加工处理的数据或指令(命令)都是以( )形式进行的。 A.十进制码 B.智能拼音码 C.二进制码 D.五笔字型码 16、将 Windows 应急启动盘插入 A 驱动器启动机器,随后使用一批应用软件,在此过程中, 系统盘( ) A.必须始终插入在 A 驱动器中 B.不必再用 C.可能有时要插入 A 驱动器中 D.可能有时要插入 B 驱动器中 17、在计算机中,ASCII 码是( )位二进制代码 A.8 B.7 C.12 D.16 18、在外部设备中,绘图仪属于( ) A.辅(外)存储器 B.主(内)存储器 C.输入设备 D.输出设备 19、某台计算机的基本内存容量是 512MB,这里的 512MB 容量是指( )个字节 A.512*1000*1000 B.512*1000 C.512*1024*1024 D.512*1024 20、计算机的运算速度取决于给定的时间内,它的处理器所能处理的数据量。处理器一次能 处理的数据量叫字长。已知 64 位的奔腾处理器一次能处理 64 个信息,相当于( )字节 A.8 个 B.1 个 C.16 个 D.2 个 21、一个完整的计算机系统包括( ) A.计算机及其外部设备 B.主机、键盘、显示器 C.系统与应用软件 D.硬件与软件系统 22、操作系统的作用是( ) A.把源程序译成目标程序 B.便于进行数据管理 C.控制和管理系统资源 D.实现硬件之间的连接 23、断电时计算机( )中的信息会丢失 A.软盘 B.硬盘 C.RAM D.ROM 24、数据和程序是以( )形式存储在磁盘上的 A.集合 B.文件 C.目录 D.记录 25、各种应用软件都必须在( )的支持下运行 A.编程程序 B.计算机语言程序 C.字处理程序 D.操作系统 26、计算机之所以称为“电脑” ,是因为( ) A.计算机是人类大脑功能的延伸 B.计算机具有逻辑判断功能 C.计算机有强大的记忆能力 D.计算机有瞬息万变我控制功能 27、在计算机领域中,通常用英文单词“BYTE”来表示( ) A.字 B.字长 C.二进制位 D.字节 28、计算机病毒是指( ) A.能传染给用户的磁盘病毒 B.已感染病毒的磁盘 C.具有破坏性的特制程序 D.已感染病毒的程序 29、既是输入设备又是输出设备的是( ) A.磁盘驱动器 B.显示器 C.键盘 D.鼠标器 30、以下哪种方式属于微机的冷启动方式( ) A.按 CTRL+ALT+DEL 键 B.按 CTRL+BREAK 键 C.按 RESET 键 D.打开电源开关启动 31、CAI 是指( ) A.系统软件 B.计算机辅助教学软件 C.计算机辅助管理软件 D.计算机辅助设计软件 32、所谓媒体是指( ) A.表示和传播信息的载体 B.字处理软件
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

2

C.计算机输入与输出信息 D.计算机屏幕显示的信息 33、下列说法正确的是( ) A.在微机性能中,CPU 的主频越高,其运算速度越快 B.存储器具有记忆能力,其中信息任何时候都不会丢失 C.点阵打印机的针数越多,则能打印的汉字字体就越多 D.两个显示器屏幕尺寸相同,则它们的分辨率必定相同 34、文件型病毒传染的主要对象是( ) A.文本文件 B.系统文件 C.可执行文件 D..EXE 和.COM 文件 35、 针打印机的分辨率约为 180dpi。 数越大, 24 Dpi 打印精度越高。 其中单位 dpi 是指( ) A.印点/厘米 B.印点/毫米 C.印点/英寸 D.印点/寸 36、内存地址的最重要特点是( ) A.随机性 B.唯一性 C.顺序性 D.连续性 37、直接通过总线与 CPU 连接的部件是( ) A.显示器 B.内存储器 C.磁盘驱动器 D.键盘 38、计算机的运算速度可以用 MIPS 来描述,它的含义是( ) A.每秒执行百万条指令 B.每秒处理百万个字符 C.每秒执行千万条指令 D.每秒处理千万个字符 39、在计算机行业中,MIS 是指( ) A.管理信息系统 B.数学教学系统 C.多指令系统 D.查询信息系统 40、多媒体计算机是指( ) A.具有多种功能的计算机 B.具有多种外设的计算机 C.能处理多种媒体的计算机 D.能借助多种媒体操作的计算机 41、我国第一台电子计算机于( )年试制成功 A.1953 B.1958 C.1964 D.1978 42、计算机所具有的存储程序和程序原理是( )提出的 A.图灵 B.布尔 C.冯·诺依曼 D.爱因斯坦 43、微型计算机系统中的中央处理器通常是指( ) A.内存储器和控制器 B.内存储器和运算器 C.运算器和控制器 D.内存储器、控制器和运算器 44、存储器可分为两类( ) A.RAM 和 ROM B.硬盘和软盘 C.内存储器和外存储器 D.ROM 和 EPROM 45、最早的计算机的用途是用于( ) A.科学计算 B.自动控制 C.系统仿真 D.辅助设计 46、CPU 中( )机构相当于运算器中的一个存储单元,它的存取速度比存储器要快得多。 A.存放器 B.辅存 C.主存 D.寄存器 47、存储器的 1MB 单位相当于( )KB 单位。 A.1024 B.1024^2 C.1024^4 D.512 48、计算机软件我们一般指的是( ) A.系统软件和实用软件 B.实用软件和自由软件 C.培训软件和管理软 D.编辑软件和科学计算软件 49、国产银河型数字式电子计算机是属于( )机 A.中型 B.微型 C.小型 D.巨型 50、微型计算机在工作中电源突然中断,则计算机中( )全部丢失,再次通电后也不能恢复 A.ROM 和 RAM 中的信息 B.ROM 中的信息 C.RAM 中的信息 D.硬盘中的信息
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

3

51、一般 3.5 英寸高密软盘的容量是( ) A.1.0MB B.1.2MB C.1.4MB D.1.44MB 52、在未击键时,左手无名指应放在什么键上( ) A.S 键 B.D 键 C.J 键 D.K 键 53、下列选项属于软件的是( ) A.主机 B.键盘 C.操作系统 D.显示器 54、硬盘工作时应特别注意避免( ) A.噪声 B.震动 C.潮湿 D.日光 55、针式打印机术语中,24 针是指( ) A.24*24 点阵 B.信号线插头有 24 针 C.打印头有 24*24 根针 D.打印头有 24 根针 56、办公自动化是计算机的一项应用,按计算机应用的分类,它属于( ) A.科学计算 B.实时控制 C.数据处理 D.辅助设计 57、在计算机应用中, “计算机辅助设计”的英文缩写是( ) A.CAD B.CAM C.CAE D.CAI 58、下面列出的四项中,不属于计算机病毒特征的是( ) A.潜伏性 B.激发性 C.传播性 D.免疫性 59、磁盘处于写保护状态,那么磁盘中的数据( ) A.不能读出,不能删改,也不能写入新数据 B.可以读出,不能删改,也不能写入新数据 C.可以读出,可以删改,但不能写入新数据 D.可以读出,不能删改,但可以写入新数据 60、操作系统在第几代计算机开始应用( ) A.第一代 B.第二代 C.第三代 D.第四代 61、下面四个不同的进制的数,最小的一个数是( ) A.(11011001)2 B.(75)10 C.(37)8 D.(A7)16 62、小张用十六进制、八进制和十进制写了如下的一个等式:52-19=33。式中三个数是各不 相同进位制的数,试问 52、19、33,分别为( ) A.八进制,十进制,十六进制 B.十进制,十六进制,八进制 C.八进制,十六进制,十进制 D.十进制,八进制,十六进制 63、已知小写字母“m”的十六进制的 ASCII 码值是 6D,则小写字母“c”的十六进制数据 的 ASCII 码值是( ) A.98 B.62 C.99 D.63 64、计算机中的数有浮点与定点两种,其中用浮点表示的数,通常由( )这两部分组成( ) A.指数与基数 B.尾数与小数 C.阶码与尾数 D.整数与小数 65、十进制算术表达式:3*512+7*64+4*8+5 的运算结果,用二进制表示为( ) A.10111100101 B.11111100101 C.11110100101 D.11111101101 66、组成“教授”(JIAO SHOU), “副教授”(FU JIAO SHOU)与“讲师”(JIANG SHI)这三个 词的汉字,在 GB2312-80 字符集中都是一级汉字,对这三个词排序的结果是( ) A.副教授,讲师,教授 B.教授,副教授,讲师 C.副教授,教授,讲师 D.讲师,副教授,教授 67、GB2312-80 规定了一级汉字 3755 个,二级汉字 3008 个,其中二级汉字字库中的汉字是 以( )为序排列的 A.以笔划的多少 B.以部首 C.以 ASCII 码 D.以机内码 68、下列无符号数中最小的数是( )
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

4

A.(11011001)2 B.(75)10 C.(37)8 D.(2A)16 69、如果用一个字节来表示整数,最高位用作符号位,其他位表示数值。例如:00000001 表示+1,10000001 表示-1,试问这样表示法的整数 A 的范围应该是( ) A.-127<=A<=127 B.-128<=A<=128 C.-128<=A<128 D.-128 70、如果用一个字节来表示整数,最高位用作符号位,其他位表示数值。例如:00000001 表示+1,10000001 表示-1,在这样的表示法中,以下( )说法是正确的( ) A.范围内的每一个数都只有唯一的格式 B.范围内每一个数都有两种格式 C.范围内的一半数有两种格式 D.范围内只有一个数有两种表示格式 71、已知在某进位制计数下,2*4=11,根据这个运算规则,5*16 的结果是( ) A.80 B.61 C.122 D.212 72、下列各无符号十进制整数中,能用八位二进制表示的是( ) A.296 B.333 C.256 D.199 73、执行下列二进制算术加法运算 11001001+00100111 其运算结果是( ) A.11101111 B.11110000 C.00000001 D.10100010 74、二进制数 1110111.11 转换成十进制数是( ) A.119.375 B.119.75 C.119.125 D.119.3 75、二进制数(1)0.0111;(2)0.1110;(3)+0.001101*2^0;(4)0.110100*2^-10 中,规格化形 式的数有( ) A.(2)(4) B.(1) C.(1)(2)(4) D.(1)(2) 76、下列四种不同数制表示的数中,数值最小的一个是( ) A.八进制数 247 B.十进制数 169 C.十六进制数 A6 D.二进制数 10101000 77、用拼音法输入汉字“国” ,拼音是“guo” 。那么, “国”的汉字内码占字节的个数是( ) A.1 B.2 C.3 D.4 78、用补码表示的、带符号的八位二进制数,可表示的整数范围是( ) A.-128 至+127 B.-128 至+128 C.-127 至+127 D.-127 至+128 79、下列四个不同进制的数中,数值最大的是( ) A.二进制数 1001001 B.八进制数 110 C.十进制数 71 D.十六进制数 4A 80、有一个数值 152,它与十六进制数 6A 相等,那么该数值是( ) A.二进制数 B.八进制数 C.十进制数 D.四进制数 81、 已知计算机 C:\DOS 下有一个正确的 FORMAT.COM 文件, 当执行如下命令: C:\FORMAT A:< 回车>得到的回答是 BAD COMMAND OR FILE NAME 提示信息,下面解释正确的是( ) A. 根目录中没有 AUTOEXEC.BAT 文件 B. 在执行该命令前操作者没有执行过 PATH 命令 C.C:\DOS 中的 FORMAT.BAT 文件有错 D.由于 AUTOEXEC.BAT 或操作者最后执行过的 PATH 命令缺少路径 C:\DOS,或者根本没 有执行 PATH 命令 82、以下 DOS 命令中,有可能在磁盘上建立子目录的是( ) A.TYPE B.DIR C.XCOPY D.CD 83、对具有隐含属性(H)的当前目录下的文件 AB.TXT,能成功执行的 DOS 命令是( ) A.TYPE AB.TXT B.COPY AB.TXT XY.TXT C.DIR AB.TXT D.REN AB.TXT XY.TXT 84、INTERNET 的规范译名应为( ) A.英特尔网 B.因特网 C.万维网 D.以太网 85、将 A 盘上 50 个文件用 C:\COPY A:*.*命令复制到 C 盘的当前目录中,在复制到某个文 件时,由于读数据出错,屏幕显示:ABORT,RETRY,IGNORE,FAIL?键入“I”后,继续复 制没再出现过错误信息,最后复制的结果是( )
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

5

A.读数据出错文件不正确,其他文件正确 B.读数据出错文件不正确其他文件也不正确 C.读数据出错的文件正确,其他文件不正确 D.复制的文件完全正确 86、在 CONFIG.SYS 文件中,装入特定可安装设备驱动器程序的命令是( ) A.BUFFER B.FILES C.DRIVER D.DEVICE 87、执行 DOS 命令:C:\ATTRIB A:*.*的功能是( ) A.查看 A 盘上所有文件的属性 B.查看 A 盘上当前目录中所有文件的属性 C.查看 A 盘上所有系统文件的属性 D.删去 A 盘上所有隐含文件的属性 88、执行下列 DOS 命令,效果等价的是( ) A.COPY *.FOR 与 COPY *.FOR CON B.COPY A:*.* B:与 XCOPY A:*.* B: C.COPY FILE1.TXT+FILE2.TXT 与 COPY FILE2.TXT+FILE1.TXT D.XCOPY A:*.* B:/S 与 DISKCOPY A: B: 89、下列文件名中,属于 DOS 中的保留设备名的为( ) A.AUX B.COM C.CON1 D.PRN1 90、下列哪些计算机网络不是按覆盖地域划分的( ) A.局域网 B.都市网 C.广域网 D.星型网 91、DOS 系统文件中 COMMAMD.COM 文件的作用是( ) A.负责基本的设备输入输出功能 B.直接向计算机发出命令,满足用户需要 C.解释用户输入的命令,并协调执行该命令 D.编译解释执行程序命令 92、要把当前系统提示符 c:\>改变为 C>要用( )命令( ) A.PROMPT $P$G B.PROMPT $N$G C.PROMPT $G D.PROMPT $P 93、 使用 DIR 命令查看一个目录下的文件, 查看清单最后总会有总共列举的几个文件的提示, 那么文件个数最少是( ) A.0 B.1 C.2 D.3 94、在 DOS 提示符下不能执行的是以( )为扩展名的文件 A.BAT B.BAK C.EXE D.COM 95、下列关于 DEL 命令的四条叙述中正确的是( ) A.一次只能删除一个文件 B.一次可以删除一个或多个文件 C.可以删除隐含文件 D.可以删除只读文件 96、命令 PATH C:\DOS 有何作用( ) A.标记 C 盘 DOS 子目录 B.将 C 盘 DOS 子目录置为当前目录 C.指明 C:\DOS 为当前路径 D.搜寻 C 盘 DOS 子目录下的可执行文件 97、在 MSDOS 的根目录中,有如下文件:TIME.EXE、TIME.COM、TIME.BAT,则 C:\TIME<回 车>执行的是( ) A.TIME.EXE B.TIME.COM C.TIME.BAT D.内部命令 98、以下列举 INTERNET 的各种功能中,错误的是( ) A.编译程序 B.传送电子邮件 C.查询信息 D.数据库检索 99、计算机网络最突出的优点是( ) A.传送信息速度高 B.共享资源 C.内存容量大 D.交互性好 100、信息高速公路传送的是( ) A.二进制数据 B.多媒体信息 C.程序数据 D.各种数字信息 101、根据 DOS 系统关于文件名的命名规则,下列四个文件名中合法的一个是( ) A.AB TXT B.AB&CD C.A/B D.AB].COM 102、下面四条叙述中,正确的一条是( ) A.DOS 是单用户、多任务操作系统 B.在 DOS 系统启动后,其内部命令和外部命令都已装入内存的指定区域中 C.在连接好打印机后,执行 DOS 命令:TYPE A.TXT>PRN,可将文件 A.TXT 的内容在打印机
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

6

中打印出来 D.若在 DOS 系统启动盘的根目录中找不到系统配置文件 CONFIG.SYS,则 DOS 系统无法正确 启动 103、如果 A 驱动器中的软盘已经写保护,则下列 DOS 命令中可以正确执行的一条是( ) A.MD A:\A B.COPY A:*.* C: C.DEL A:\*.BAK D.FORMAT A: 104、MD-DOS 操作系统的主要功能可以分为两个方面,它们是( ) A.设备管理功能和文件管理功能 B.设备管理功能和处理机管理功能 C.文件管理功能和存储器管理功能 D.处理机管理功能和作业管理功能 105、下面是关于 DOS 系统内部命令的四条叙述,其中正确的一条是( ) A.内部命令主要是机器管理人员内部使用的 B.内部命令以文件形式存储在磁盘上 C.内部命令不能在批处理文件中使用 D.内部命令包含在 COMMAND.COM 文件中 106、在 WINDOWS 中,将一个应用程序窗口最小化之后,该应用程序( ) A.仍在后台运行 B.暂时停止运行 C.完全停止运行 D.出错 107、在 INTERNET 中电子公告板的缩写是( ) A.FTP B.WWW C.BBS D.E-mail 108、用户在网上最常用的一类信息查询工具叫做( ) A.ISP B.搜索引擎 C.网络加速器 D.离线浏览器 109、在 WINDOWS 的窗口的右上角,可以同时显示的按钮是( ) A.最小化、还原和最大化 B.还原、最大化和关闭 C.最小化、还原和关闭 D.还原和最大化 110、在 WINDOWS 中,如果想同时改变窗口的高度和宽度,可以拖放什么来实现( ) A.窗口角 B.窗口边框 C.滚动条 D.菜单 111、算法是指( ) A.为解决问题而编写的计算机程序 B.为解决问题而采取的方法与步骤 C.为解决问题而需要采用的计算机语言 D.为解决问题而采用的计算方法 112、设栈 S 的初始状态为空,现有 5 个元素组成的序列{1,2,3,4,5},对该序列在 S 栈上依次进行如下操作(从序列中的 1 开始,出栈后不再进栈):进栈、进栈、进栈、出栈、 进栈、出栈、进栈。试问出栈的元素序列是( ) A.{5,4,3,2,1} B.{2,1} C.{2,3} D.{3,4} 113、 设循环队列中数组的下标范围是 1-n, 其中头尾指针分别是 f 和 r, 则其元素个数是( ) A.r-f B.r-f+1 C.(r-f) MOD n+1 D.(r-f+n) MOD n 114、在待排序的数据表已经为有序时,下列排序算法中花费时间反而多的是( ) A.堆排序 B.希尔排序 C.冒泡排序 D.快速排序 115、在有 n 个子叶节点的哈夫曼树中,其节点总数为( ) A.不确定 B.2n-1 C.2n+1 D.2n 116、 某数列有 1000 个各不相同的单元, 由低到高按序排列, 现要对该数列进行二分法检索, 在最坏的情况下,需要检视( )个单元( ) A.1000 B.10 C.100 D.500 117、已知数组 A 中,每个元素 A[I,J]在存储时要占 3 个字节,设 I 从 1 变化到 8,J 从 1 变化到 10,分配内存时是从地址 SA 开始连续按行存储分配的。试问:A[5,8]的起始地址 为( ) A.SA+141 B.SA+180 C.SA+222 D.SA+225 118、线性表若采用链表存储结构,要求内存中可用存储单元地址( ) A.必须连续 B.部分地址必须连续 C.一定不连续 D.连续不连续均可 119、下列叙述中,正确的是( )
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

7

A.线性表的线性存储结构优于链表存储结构 B.队列的操作方式是先进后出 C.栈的操作方式是先进先出 D.二维数组是指它的每个数据元素为一个线性表的线性表 120、电线上停着两种鸟(A,B),可以看出两只相邻的鸟就将电线分为了一个线段。这些线 段可公为两类:一类是两端的小鸟相同;另一类是两端的小鸟不相同。已知:电线上两个顶 点上正好停着相同的小鸟,试问两端为不同小鸟的线段数目一定是( ) A.奇数 B.偶数 C.可奇可偶 D.数目固定 121、在列车转辙网络中,有四个车皮编号为 1,2,3,4,并按此顺序送入栈中进行调度, 这些车皮取出的顺序是( ) A.4123 B.3241 C.3412 D.4312 122、从未排序序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端,这种 排序方法称为( ) A.插入排序 B.归并排序 C.选择排序 D.快速排序 123、在计算递归函数时,如不使用递归过程,则一般情况下必须借助于( )数据结构( ) A.栈 B.树 C.双向队列 D.广义表 124、使用双向链表存放数据的优点是( ) A.提高检索速度 B.很方便地插入和删除数据 C.节约存储空间 D.很快回收存储空间 125、对一个满二叉树,m 个树叶,l 分枝结点,n 个结点,则( ) A.n=l+m B.l+m=2n C.m=l-1 D.n=2l-1 126、一维数组与线性表的区别是( ) A.前者长度固定,后者长度可变 B.后者长度固定,前者长度可变 C.两者长度均固定 D.两者长度均可变 127、用某种排序方法对线性表 25,84,21,47,15,27,68,35,20 进行排序,结点变化如下: (1)25,84,21,47,15,27,68,35,20;(2)20,15,21,25,47,27,68,35,84;(3)15,20,21,25,35,2 7,47,68,84;(4)15,20,21,25,27,35,47,68,84.那么,排序方法是( ) A.选择排序 B.希尔排序 C.合并排序 D.快速排序 128、具有 12 个记录的序列,采用冒泡排序最少的比较次数是( ) A.1 B.144 C.11 D.66 129、下面关于二叉树的叙述正确的是( ) A.一棵二叉树中叶子结点的个数等于度为 2 的结点个数加 1 B.一棵二又树中的结点个数大于 0 C.二叉树中任何一个结点要么是叶,要么恰有两个子女 D.二叉树中,任何一个结点的左子树和右子树上的结点个数一定相等 130、先序序列和中序序列相同的二叉树为空树或( ) A.任一结点均无右孩子的非空二叉树 B.仅有两个结点的二叉树 C.任一结点均无左孩子的非空二叉树 D.不存在这样的二叉树 131、 设有三个元素 A、 C 顺序进栈, B、 在进栈过程中可以出栈, 出栈次序错误的排列是( ) A.ABC B.BCA C.CAB D.CBA 132、下面四种内排序方法中,要求内存容量最大的是( ) A.插入排序 B.选择排序 C.快速排序 D.归并排序 133、设有序列 F: (49,38,65,97,76,13,27,50) ,使用快速排序法,其趟数为( ) A.3 B.2 C.1 D.4 134、给出一组整型数 28、10、37、63、35、30、23,请用二叉树对它进行排序。为此,首 先要生成一棵二叉树,规则是把第一数放在根处,接着凡比它小的数放在左子树,比它大的
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

8

数放在右子树,直到把所有的数均安排好。然后对此二叉树进行( ),得到的就是按照升序 排列好的序列。 A.前序遍历 B.中序遍历 C.后序遍历 D.横向遍历 135、用某种排序方法对线性表(84,47,25,15,21)进行排序时,结点序列的变化如下: (1)84,47,25,15,21;(2)15,47,25,84,21;(3)15,21,25,84,47;(4)15,21,25,47,84.那么, 所 采用的排序方法是( ) A.选择排序 B.冒泡排序 C.插入排序 D.快速排序 136、设二叉树根结点的层次为 0,一棵高度为 b 的满二叉树中结点的个数是( ) A.2^b B.2^(b-1) C.2^b-1 D.2^(b+1)-1 137、深度为 5 的二叉树至多有( )个结点 A.16 B.32 C.31 D.10 138、下面关于线性表的描述,错误的是( ) A.栈是线性表的一种 B.任给一个索引 I(1<=I<=表中元素个数) ,就能在线性表中唯一确定一个元素 C.线性表的任一元素都有前驱和后继 D.线性表是一个线性序列 139、带权路径长度最小的二叉树是( ) A.顺序二叉树 B.二叉排序树 C.判定树 D.哈夫曼树 140、有 12 个结点的平衡二叉树的最大深度是( ) A.4 B.5 C.6 D.3 141、若用冒泡排序法对序列 18,14,6,27,8,12,16,52,10,26,47,29,41,24 从小到大进行排序,共要进行( )次比较。 A.33 B.45 C.70 D.91 142、设 n,m 为某二叉树上的两个结点,在中序遍历时,n 在 m 前的条件是( ) A.n 在 m 右方 B.n 是 m 祖先 C.n 在 m 左方 D.n 是 m 子孙 143、下列四种排序方法,如果被排序的序列中诸元素恰好已经按要求(由小到大或由大到 小排序,就元素的比较次数和移动次数而言,哪种方法最少?( ) A.冒泡排序 B.直接选择排序 C.直接插入排序 D.归并排序 144、如果某二叉树的前序为 STUWV,中序为 UWTVS,那么该二叉树的后序是( ) A.WUVTS B.UWVTS C.VWUTS D.WUTSV 145、按照二叉树的定义,具有 3 个结点的二叉树有( ) A.3 种 B.4 种 C.5 种 D.6 种 146、对以下关键字序列用快速排序法进行排序,速度最慢的情况是( ) A.{19,23,3,15,7,21,8} B.{23,21,28,15,19,3,7} C.{19,7,15,28,23,21,3} D.{3,7,15,19,21,23,28} 147、数组 A 中,每个元素 A[I,j]的长度为 3 个字节,行下标 I 为 1 到 8,列下标 j 从 1 到 10。从首地址 SA 开始连续存放在存储器中,存放该数组至少需要的单元数是( ) A.80 B.100 C.240 D.270 148、树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍 历、中序遍历和后序遍历。这里,我们把由树转化得到的二叉树叫做这棵树对应的二叉树。 正确的结论是( ) A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 C.树的后根遍历序列与其对应的二叉树的先序遍历序列相同 D.树的后根遍历序列与其对应的二叉树的后序遍历序列相同
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

9

149、在数据结构中,从逻辑上可以把数据结构分成( ) A.动态结构和静态结构 B.线性结构和非线性结构 C.内部结构和外部结构 D.紧凑结构和非紧凑结构 150、 如果 T2 是由有序树 T 转换而来的二叉树, 那么 T 中结点的后序就是 T2 中结点的( ) A.前序 B.中序 C.后序 D.层次序 151、 某二叉树的前序遍历结点访问顺序是 abdgcefh, 中序遍历的结点访问顺序是 dgbaechf, 则其后序遍历的结点访问顺序是( ) A.bdgcefha B.gdbecfha C.bdgaechf D.gdbehfca 152、从未排序序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端,这种 排序方法称为( ) A.插入排序 B.选择排序 C.归并排序 D.快速排序 153、快速排序方法在( )情况下最不利于发挥其长处 A.被排序的数据量太大 B.被排序数据中含有多个相同值 C.被排序数据已基本有序 D.被排序数据数目为奇 154、下面关于数据结构的叙述中,正确的叙述是( ) A.顺序存储方式的优点是存储密度大,且插入、删除运算效率高 B.链表中的每一个结点都包含一个指针 C.包含 n 个结点的二叉排序树的最大检索长度为 log\-2n D.将一棵树转换为二又树后,根结点没有右子树 155、在计算机科学领域中,算法分为两类:数值型算法和非数值型算法。下面的算法,哪一 个属于数值算法类( ) A.迭代法 B.冒泡法 C.黑盒法 D.杂凑(Hash)法 156、若已知一个栈的输入序列为 1,2,3?,n,其输出序列为 P1,P2,?,Pn。若 P1=n, 则 Pi 为( ) A.I B.n+I C.n-I+1 D.不确定 157、带头结点的单链表 Head 为空的判定条件是( ) A.Head=NIL B.Head^.Next=NIL C.Head^.Next=Head D.Head=Head 158、二维数组 a 的成员是 6 个字符组成的串,行下标 I 的范围从 0 到 8,列下标 j 的范围 从 1 到 10,则存放 a 至少需要( )个字节 A.90 B.180 C.240 D.540 159、由 3 个结点可以构造出多少种不同的有向树( ) A.2 B.3 C.4 D.5 160、二维数组 M[I,j]的元素是 4 个字符(每个字符占一个存储单元)组成的串,行下标 I 的范围从 0 到 4,列下标 j 的范围从 0 到 5。M 按行存储元素 M[3,5]的起始地址与 M 按列存 储时元素( )的起始地址相同。 A.m[2,4] B.m[3,4] C.m[3,5] D.m[4,4] 161、判断一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用( ) A.求关键路径的方法 B.求最短路径的方法 C.广度优先遍历方法 D.深度优先遍历方法 162、在一非空二叉树的中序遍历序列中,根结点的右边( ) A.只有右子树上的所有结点 B.只有右子树上的部分结点 C.只有左子树上的所有结点 D.只有左子树上的部分结点 163、一个队列的入列序列是 1,2,3,4,则队列的输出序列是( ) A.4,3,2,1 B.1,2,3,4 C.1,4,3,2 D.3,2,4,1 164、邻接表存储结构下图的深度优先遍历算法结构类似于二叉树的( ) A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历 165 、 设 待 排 序 的 记 录 为 (20,16,13,14,19) , 经 过 下 列 过 程 将 这 些 记 录 排 序 : (1)20,16,13,14,19;(2)16,20,13,14,19;(3)13,16,20,14,19;(4)13,14,16,20,19;(5)13,1
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

10

4,16,19,20.所用的排序方法是( ) A.直接插入排序 B.冒泡排序 C.希尔排序 D.堆排序 166、计算机算法一般被划分为数值算法和非数值算法两大类,下列叙述中,哪个不属于数 值算法( ) A.迭代法 B.直接法 C.杂凑(Hash)法 D.消去法 167、用归并排序方法对线性表(49,38,65,97,76,13,27,49,55,04)进行排序时, 其第三趟的排序结果为( ) A.12,27,38,49,49,65,76,97,04,55 B.38,49,65,97,13,27,49,76,04,55 C.38,49,65,97,13,76,27,49,04,55 D.01,13,27,38,49,49,55,65,76,97 168、栈和队列都是( ) A.顺序存储的线性结构 B.链式存储的非线性结构 C.限制存取点的线性结构 D.限制存取点的非线性结构 169、对 N 个结点的线性表进行查找,用顺序查找的时间复杂性为( ) A.N*N B.Nlog2n C.n D.log2n 170、若进栈序列为 1,2,3.4 假定进栈和出栈可以穿插进行,则可能的出栈序列是( ) A.2,4,1,3 B.3,1,4,2 C.3,4,1,2 D.1,2,3,4 171、设计一个判别表达式中左、右括号是否配对的算法,采用( )数据结构最佳( ) A.线性表的顺序存储结构 B.栈 C.队列 D.线性表的链式存储结构 172、设一棵二叉树,其叶子结点分别带权 10,12,4,7,5,18,2 则其带权路径长度最小 为( ) A.120 B.130 C.140 D.150 173、以下关于数据结构的叙述,正确的是( ) A.线性表的线性存储结构优于链式结构 B.二叉树的第 I 层上有 2 的(I-1)次幂个结点,深度为 K 的二叉树上有 2 的(k-1) 次幂个结点 C.二维数组是其数据元素为线性表的线性表 D.栈的操作方式是先进先出 174、循环队列用数组 A[0?m-1]存放其元素值,已知其头尾指针分别是 front 和 rear,则 当前队列中的元素个数是( ) A. (rear-front+m)MOD m B.rear-front-1 C.rear-front+1 D.rear-front 175、把一般树转化为二叉树的方法是:对每一结点的子树,在其根之间加水平连线,然后 仅保留( )而抹掉该结点和其它子树之间的连线,最后以树的根结点为轴,将树顺时针转 45 度即可 A.最右子树 B.右子树 C.左子树 D.最左子树 176、下列哪一种图的邻接矩阵是对称矩阵( ) A.有向图 B.无向图 C.AOV 网 D.AOE 网 177、计算机算法必须具备的三个特性是( ) A.可执行性、可移植性和可扩充性 B.可执行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 178、对长度为 10 的有序表进行折半查找,设在等概率时查找成功的平均查找长度是( ) A.2.9 B.3.1 C.3.4 D.2.6 179、设有 6 个结点的无向图,该图至少应该有( )条边才能确保是一个连通图( ) A.5 B.6 C.7 D.8 180、有 6 个元素按 6,5,4,3,2.1 的顺序进栈,问下列哪一个不是合法的出栈序列( )
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

11

A.5,4,3,6,1,2 B.4,5,3,1,2,6 C.3,4,6,5,2,1 D.2,3,1,4,5,6 181.设全集 I = {a, b, c, d, e, f, g},集合 A = {a, b, c},B = {b, d, e},C = {e, f, g},那么集合 。 ( A ? B) ? (~ C ? B) 为( ) A. {a, b, c, d} B. {a, b, d, e} C. {b, d, e} D. {b, c, d, e} E. {d, f, g} 182.由 3 个 a,5 个 b 和 2 个 c 构成的所有字符串中,包含子串“abc”的共有( )个。 A. 40320 B. 39600 C. 840 D. 780 E. 60 183.某个车站呈狭长形,宽度只能容下一台车,并且只有一个出入口。已知某时刻该车站状 态为空,从这一时刻开始的出入记录为: “进,出,进,进,出,进,进,进,出,出,进, 出” 。假设车辆入站的顺序为 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 184.满二叉树的叶结点个数为 N,则它的结点总数为( ) 。 N A. N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2 – 1 185.二叉树 T,已知其前序遍历序列为 1 2 4 3 5 7 6,中序遍历序列为 4 2 1 5 7 3 6,则其后 序遍历序列为( ) 。 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 186.十进制数 100.625 等值于二进制数( ) 。 A. 1001100.101 B. 1100100.101 C. 1100100.011 D. 1001100.11 E. 1001100.01 187.下面哪个部件对于个人桌面电脑的正常运行不是必需的( ) 。 A. CPU B. 图形卡(显卡) C. 光驱 D. 主板 E. 内存 188.下列哪个网络上常用的名字缩写是错误的( ) 。 A. WWW(World Wide Web) B. URL(Uniform Resource Locator) C. HTTP(Hypertext Transfer Protocol) D. FTP(Fast Transfer Protocol) E. TCP(Transfer Control Protocol) 。 189.用静电吸附墨粉后转移到纸张上,是哪种输出设备的工作方式( ) 。 A. 针式打印机 B. 喷墨打印机 C. 激光打印机 D. 笔式绘图仪 E. 喷墨绘图仪 190.一台计算机如果要利用电话线上网,就必须配置能够对数字信号和模拟信号进行相互转 换的设备,这种设备是( ) 。 A. 调制解调器 B. 路由器 C. 网卡 D. 网关 E. 网桥 191. 图灵 (Alan Turing) 是 ( ) 。 A) 美国人 B) 英国人 C) 德国人 D) 匈牙利人 E) 法国人 192. 第一个给计算机写程序的人是( ) 。 A) Alan Mathison Turing B) Ada Lovelace C) John von Neumann D) John Mc-Carthy E) Edsger Wybe Dijkstra 193. 十进制数 2003 等值于二进制数( ) 。 A) 0100000111 B) 10000011 C) 110000111 D) 11111010011 E) 1111010011 194. 假设 A=true,B=false,C=ture,D=ture,逻辑运算表达式 A∧B∨C∧D 的值是( ) 。 A) ture B) false C) 0 D) 1 E) NULL 195. 一个高度为 h 的二叉树最小元素数目是( ) 。 A) 2h+1 B) h C) 2h-1 D) 2h E) 2h-1 196. 已知队列(13,2,11,34,41,77,5,7,18,26,15) ,第一个进入队列的元素是 13,则第五个出队列的元素是( ) 。 A) 5 B) 41 C) 77 D) 13 E) 18
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理 12

197. 下面一段程序是用( )语言书写的。 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

198. 设全集 E={1,2,3,4,5},集合 A={1,4},B={1,2,5},C={2,4},则集合(A ∩B) ∪~C 为( )。 A) 空集 B) {1} C) {3,5} D){1,5} E) {1,3,5} 199. 表达式(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-*/ 200. 下列计算机设备,即是输入设备,又是输出设备的是( ) 。 A) 键盘 B) 触摸屏 C) 扫描仪 D)投影仪 E) 数字化仪

二、多项选择题(下列题至少有一个正确答案)
1. 下列分辨率的显示器显示出的图像,最清晰的是( ) 。 A) 800*600 B) 1024*768 C) 640*480 D) 1280*1024 E) 800*1000 2. 下列说法中,哪个(些)是错误的( ) 。 A)程序是指令的序列,它有三种结构:顺序、分支和循环。 B)数据总线决定了中央处理器 CPU 所能访问的最大内存空间的大小。 C)中央处理器 CPU 内部有寄存器组,用来储存数据。 D)不同厂家生产的 CPU 所能处理的指令集是相同的。 E) 数据传输过程中可能会出错, 奇偶校验法可以检测出数据中那一为在传输中出了差错。 3. CPU 访问内存的速度比访问下列哪个(些)存储设备要慢( ) 。 A)寄存器 B)硬盘 C)软盘 D)高速缓存 E)光盘 4. 下列电子邮件地址,哪个(些)是正确的( ) 。 A)wang@hotmail.com B) cai@jcc.pc.tool.rf.edu.jp C) 162.105.111.22 D) ccf.edu.cn E)http://www.sina.com 5. 数字图像文件可以用下列哪个(些)软件来编辑( ) 。 A)画笔(Paintbrush) B)记事薄(Notepad) C) Photoshop D) WinRAR E)Midisoft 6. 下列哪个(些)软件不是操作系统软件的名字( ) 。 A)WindowsXP B) DOS C) Linux D) OS/2 E) Arch/Info 7. 下列哪个(些)不是个人计算机的硬件组成部分( ) 。 A)主板 B)虚拟内存 C)电源 D)硬盘 E)总线 8. 运算式(2008)10-(3723)8 的结果是( ) 。 A)(-1715)10 B) (5)10 C) (5)16 D) (101)2 E) (3263)8 9. 已知元素(8,25,14,87,51,90,6,19,20) ,问这些元素以怎样的顺序进入栈, 才能使出栈的顺序满足:8 在 51 前面;90 在 87 的后面;20 在 14 的后面;25 在 6 的前面; 19 在 90 的后面。 ( ) 。 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 10. 假设我们用 d=(a1,a2,...,a5),表示无向图 G 的 5 个顶点的度数,下面给出的哪(些)组 d 值合理( ) 。
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理 13

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} 11.下列属于操作系统的是( ) A)MSDOS B) OS/2 C) Linux D)Delphi E)C++ 12. 正确的 IP 地址有() A)192.168.123.5 B) 1.2.3.4 C) 100.100.100.300 D)1.1.1.1 E)2.0.0.1 13.属于线性排序法的有() A) 选择排序 B)插入排序 C)计数排序 D)快速排序 E)基数排序 F)桶排序 14. 一棵二叉树的深度为 4,下列数字可以是其结点数的是( ) A) 14 B)15 C)16 D)17 E)18 15.一棵二叉树先序遍历的结果为 ABCD,后序遍历结果为 DCBA,它中序遍历的结果可能为: A)ABCD B)ABDC C)ADCB D)DBAC E)DCBA 16.美籍匈牙利数学家冯·诺依曼对计算机科学发展所做出的贡献包括( ) 。 A. 提出理想计算机的数学模型,成为计算机科学的理论基础。 B. 提出存储程序工作原理,对现代电子计算机的发展产生深远影响。 C. 设计出第一台具有存储程序功能的计算机 EDVAC。 D. 采用集成电路作为计算机的主要功能部件。 E. 指出计算机性能将以每两年翻一番的速度向前发展。 17.下列哪个(些)是 64 位处理器( ) 。 A. Intel Itanium B. Intel Pentium III C. AMD Athlon64 D. AMD Opteron E. IBM Power 5 18.(2004)10 + (32)16 的结果是( ) 。 A. (2036)16 B. (2054)10 C. (4006)8 D. (100000000110)2 E. (2036)10 19.下列哪个(些)不是数据库软件的名称( ) 。 A. MySQL B. SQL Server C. Oracle D. Outlook E. Foxpro 20.下列哪个(些)不是计算机的存储设备( ) 。 A. 文件管理器 B. 内存 C. 显卡 D. 硬盘 E. U 盘 21.下列哪个(些)软件属于操作系统软件( ) 。 A. Microsoft Word B. Windows XP C. Foxmail D. 金山影霸 E. Red Hat Linux 22.下列说法中正确的有( ) 。 A. CPU 的基本功能就是执行指令。 B. CPU 的主频是指 CPU 在 1 秒内完成的指令周期数, 主频越快的 CPU 速度一定越快。 C. 内部构造不同的 CPU 运行相同的机器语言程序,一定会产生不同的结果。 D. 在一台计算机内部,一个内存地址编码对应唯一的一个内存单元。 E. 数据总线的宽度决定了一次传递数据量的大小,是影响计算机性能的因素之一。 23.彩色显示器所显示的五彩斑斓的色彩,是由哪三色混合而成的( ) 。 A. 红 B. 白 C. 蓝 D. 绿 E. 橙 24.下列哪个(些)程序设计语言支持面向对象程序设计方法( ) 。 A. C++ B. Object Pascal C. C D. Smalltalk E. Java 25.某大学计算机专业的必修课及其先修课程如下表所示: C0 C1 C2 C3 C4 C5 C6 C7 课程代号 课程名称 高等数学 程序设计语言 离散数学 数据结构 编译技术 操作系统 普通物理 计算机原理 C0, C1 C1, C2 C3 C3, C7 C0 C6 先修课程 请你判断下列课程安排方案哪个(些)是合理的( ) 。 A. C0, C1, C2, C3, C4, C5, C6, C7 B. C0, C1, C2, C3, C4, C6, C7, C5
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理 14

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 26. 下列分辨率的显示器显示出的图像,最清晰的是( ) 。 A) 800*600 B) 1024*768 C) 640*480 D) 1280*1024 E) 800*1000 27. 下列说法中,哪个(些)是错误的( ) 。 A)程序是指令的序列,它有三种结构:顺序、分支和循环。 B)数据总线决定了中央处理器 CPU 所能访问的最大内存空间的大小。 C)中央处理器 CPU 内部有寄存器组,用来储存数据。 D)不同厂家生产的 CPU 所能处理的指令集是相同的。 E)数据传输过程中可能会出错,奇偶校验法可以检测出数据中那一为在传输中出了差错。 28. CPU 访问内存的速度比访问下列哪个(些)存储设备要慢( ) 。 A)寄存器 B)硬盘 C)软盘 D)高速缓存 E)光盘 29. 下列电子邮件地址,哪个(些)是正确的( ) 。 A)wang@hotmail.com B) cai@jcc.pc.tool.rf.edu.jp C) 162.105.111.22 D) ccf.edu.cn E)http://www.sina.com 30. 数字图像文件可以用下列哪个(些)软件来编辑( ) 。 A)画笔(Paintbrush) B)记事薄(Notepad) C) Photoshop D) WinRAR E)Midisoft 31. 下列哪个(些)软件不是操作系统软件的名字( ) 。 A)WindowsXP B) DOS C) Linux D) OS/2 E) Arch/Info 32. 下列哪个(些)不是个人计算机的硬件组成部分( ) 。 A)主板 B)虚拟内存 C)电源 D)硬盘 E)总线 33. 运算式(2008)10-(3723)8 的结果是( ) 。 A)(-1715)10 B) (5)10 C) (5)16 D) (101)2 E) (3263)8 34. 已知元素(8,25,14,87,51,90,6,19,20) ,问这些元素以怎样的顺序进入栈, 才能使出栈的顺序满足:8 在 51 前面;90 在 87 的后面;20 在 14 的后面;25 在 6 的前面; 19 在 90 的后面。 ( ) 。 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 35. 假设我们用 d=(a1,a2,...,a5),表示无向图 G 的 5 个顶点的度数, 下面给出的哪 (些) d 值 组 合理( ) 。 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}

相关知识点与参考答案
一.单项选择题 1、操作系统是系统软件的核心,是有效利用计算机的硬件、软件、数据等各种资源的好管 家, 它还向用户提供一套容易学习使用的操作命令。 常用的操作系统有: MS-DOS、 PC-DOS、 WINDOWS、UNIX、LINUX、OS/2 等。WORD、WPS 是字处理软件,FOXBASE 是数据库管理软件。 2、字长表示一个存储单元由多少位二进制数组成,八位机一个字长就是一个字节,十六位 机一个字长可以表示两个字节。字长位的多少,表明可访问存储器的地址多少。 3、操作系统一般存放在系统盘,计算机启动引导系统后,系统中的常用命令就驻留在内存 中, 方便用户使用计算机。 所以启动计算机引导系统就是把操作系统从系统盘中调入内存 储器。
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

15

4、我们要清楚,快存实质是高速缓存,主存即内存,辅存也就是外存。在这三种存储器中, 以高速缓存最快,故此,通常常用的程序都是存放在高速缓存区里。而主存的速度当然是 比辅存要快了。 5、一般,对计算机工作有较大影响的有尘土、温度、湿度。 6、计算机的指令系统是由操作码与操作数组成。 7、通用寄存器的位数跟机器有关,取决于计算机的字长。 8、计算机能实现的全部指令的集合合称为指令系统。执行各条指令所规定的操作是由指挥 工作的控制器和执行运算的部件共同完成。而控制器与运算器合起来称为 CPU。 9、RAM(random access memory)随时读写存储器,供计算机工作时随机写入,计算机一旦断 电后,其中的信息就会消失。 10、INDOWS9X 是一种多任务的可视化的操作系统,它可以同时打开多个窗口,执行多个任 务,而这些操作无论是应用程序还是文档编辑窗口,都可以利用图标、菜单或工具进行 操作,即所见即所得。所以称之为多任务图形方式的操作系统。 1-10 参考答案:BBDCBBCABD 11、常用的操作系统有:MS-DOS、PC-DOS、WINDOWS、UNIX、LINUX、OS/2 等。PASCAL 是程 序设计的语言系统软件。 12、在汉字编码中,每个汉字无论笔画多少,它们字模所占的字节数总是相同的,一个字节 可以存储 8 位二进制,24 点就需要用 3 个字节存储,24 行则需要 3*24 即 72 个字节。 13、主机与中央处理器(CPU)是两个不同的概念。CPU 由控制器与运算器组成,而主机则由 CPU 和内存储器组成,输入、输出设备属于计算机的处围设备。 14、计算机系统总线分为:地址总线、控制总线、和数据总线,因此计算机系统在总线上传 送的信号,按其类型,分别通过地址总线、控制总线和数据总线。 15、 计算机内部无论是数据还是命令, 都需要转换成二进制代码才能传送、 存贮、 加工处理。 16、操作系统是为用户提供使用和管理计算机的软件,一旦启动后,常用的命令驻留在内存 中,此时用户可以运行自己的应用软件,一般不需要将系统盘插入在 A 驱中,但若需要调 用操作系统中的外部命令,则需要将系统盘插入 A 驱中。 17、7 位二进制可表示 2^7 个状态,因此有 128 个不同的二进制编码,国际上按照这样的编 码来表示控制符号、十进制数、字符、英文字母在大小写以及一些特殊符号等。由于一个 字节长度是八位二进制数,所以用一个字节表示 ASCII 码,则最高位为 0;汉字编码是用 两个字节表示,最高位为 1。 18、外部设备包括了输入设备、输出设备。绘图仪是受计算机控制,将处理信息的结果以绘 出图形的方式表示出来的一种外部设备。 19、1MB=1024KB,1KB=1024B,所以 512MB=512*1024*1024 个字节。 20、 一个字节由 8 位二进制数组成, 位的奔腾处理器一次能处理 64 位信息相当于 8 字节。 64 11-20 参考答案:CADBCCBDCA 21、计算机系统由硬件系统和软件系统组成。 22、操作系统是系统软件的核心,是有效利用计算机的硬件、软件、数据等各种资源。 23、RAM(random access memory)随时读写存储器,供计算机工作时随机写入,计算机一旦 断电后,其中的信息就会消失。 24、在电脑中,各种各样的数据都是以文件的形式存放的。 25、 计算机系统是由硬件和软件两部分组成, 有效的使用和管理计算机的各种输入和输出设 备,应用各种软件,必须借助于计算机的操作系统。 26、 计算机的工作原理跟人的大脑很相似, 而且还是大脑功能的延伸, 所以习惯上叫它电脑。 27、存储容量是指存储的信息量,它用字节(BYTE)作用基本单位。
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

16

28、计算机病毒是一种程序,是人为设计的具有破坏性的程序。计算机病毒具有破坏性、传 播性、可激发性、潜伏性、隐蔽性等特点。 29、磁盘驱动器是既能输入又能输出的设备。显示器是输出设备,键盘与鼠标是输入设备。 30、在关机状态下开机就是冷启动。 21-30 参考答案:DCCBDADCAD 31、CAI,Computer Assisted Instruction,计算机辅助教学。 32、媒体是指表示和传播信息的载体。 33、微机的性能取决于 CPU 的性能,CPU 主频越快,其运算速度也就越快。存储器中的 RAM 中的信息会在断电后丢失。 打印机的打印字体与针数无关。 显示器分辨率与屏幕尺寸无关。 34、文本型病毒感染的主要对象是.EXE 和.COM 文件。 35、24 针打印机的分辨率单位 dpi 是指印点/英寸。 36、内存中的每一个基本单位,都被赋予一个唯一的序号,称为地址。 37、总线是用于连接计算机中各部件(CPU、内存、外设接口)的一组公共信号线。显示器、 磁盘驱动器、键盘都属于外设,故此,通过总线与 CPU 相连的是内存储器。 38、计算机运算速度是指每秒执行指令的条数。M 表示百万,IP 表示指针寄存器,S 表示秒, 即每秒执行百万条指令。 39、MIS(Management Information System)信息管理系统 40、 多媒体计算机一般指能够同时接受、 处理、 存储和展示多种不同类型信息媒体的计算机。 31-40 参考答案:BAADCBBAAD 41、 我国 1956 年开始电子计算机的科研和教学工作, 1958 年研制成功第一台电子计算机(103 型电子管计算机) 42、存储程序原理是由美籍匈牙利数学家冯·诺依曼于 1946 年指出的。 43、 一般地, 通过电路集成化后, 运算器和控制器结合在一起, 并称之为中央处理器(Central Processing Unit),简称 CPU。 44、存储器分为内部存储器和外部存储器两部分。 45、第一代电脑是电子管计算机,开始于 1946 年,结构上以存储器为中心,使用机器语言, 存储量小,主要用于数值计算。 46、CPU 主要由运算器、控制器和寄存器组成。寄存器是 CPU 内部的临时存储单元,可以存 放数据和地址,也可以存放控制信息和 CPU 工作的状态信息。 47、1MB=1024KB 48、软件系统一般都含有很多个软件,这些软件分属于系统软件和应用软件两大类。 49、1983 年 12 月,每秒运算 1 亿次的“银河”巨型计算机在中国国防科技大学问世。 50、RAM(random access memory)随时读写存储器,供计算机工作时随机写入,计算机一旦 断电后,其中的信息就会消失。 41-50 参考答案:BCCCADAADC 51、3.5 英寸高密软盘的容量一般是 1.44MB。 52、 标准指法中, 个基本健是 ASDFJKL;与空格键。 9 当未击键时, 十个手指都放在基本键上, 左手尾指 A、左手无名指 S、左手中指 D、左手食指 F、右手食指 J、右手中指 K、右手无 名指 L、右手尾指;、两只大拇指空格。 53、主机、键盘、显示器是构成计算机的三大硬件,操作系统是软件。 54、硬盘工作时应特别注意震动,因为高速运行时,震动会使硬盘的磁头划花磁盘片。 55、打印机术语中的 24 针是指打印头有 24 根针。 56、办公室自动化应用了计算机的信息处理自动化的特点。 57、计算机辅助设计(Computer Assisted Design)
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

17

58、计算机病毒是一种程序,是人为设计的具有破坏性的程序。计算机病毒具有破坏性、传 播性、可激发性、潜伏性、隐蔽性等特点。 59、 写保护的作用是防止意外的写操作而破坏原存储的信息。 磁盘写保护后只能读而不能修 改、不能写、也不能删 60、操作系统在第三代计算机开始应用。 51-60 参考答案:DACBDCADBC 61.基本方法是把任意进制数转换成十进制数后进行比较。 (11011001)2=1*2^7+1*2^6+1*2^4+1*2^3+1*2^0=(217)10、(37)8=3*8^1+7*8^0=(31)10、 (A7)16=10*16^1+7*16^0=(167)10,可以看出(37)8 数最小。 62.根据题意,算式结果为 33,而 33 不可能是十进制数,否则 52、19 都必须是十进制数, 与题意不合;计算机结果也不可能是十六进制数,否则,52 必须是 8 进制,减出十进制 19 的结果不可能是十六进制 33。 故选择 B, 运算为(52)10-(19)16=(33)8→52-(16+9)=(3*8+3) 63.由 m 的十六进制 ASCⅡ码值是 6D,而我们知道小写 c 与 m 相差十进制数 10,相当于十六 进制数 A,将 6D-A=63(16 进制数减法)。 64.浮点数的表示同数学中的科学计数法有相似之处, 由小数及 10 的 N 次幂表示, 计算机中 的的浮点数则将小数部分表示为尾数,将 10 的 N 次幂的 N 作为阶码。 65. 先 求 得 2021 再 化 二 进 制 。 较 快 的 方 法 有 两 种 , 1 、 转 成 二 进 制 , 即 : 3*512+7*64+4*8+5=(2^1+2^0)*2^9+(2^2+2^1+2^0)*2^6+2^2*2^3+2^2+2^0=2^10+2^9+2^8+2 ^7+2^6+2^5+2^2+2^0 → (11111100101)2 ; 2 、 写 成 八 进 制 再 转 换 成 二 进 制 , 3*8^3+7*8^2+4*8^1+5*8^0→(3745)8→11111100101。 66. 计算机对字符的排序是按照字符的 ASCⅡ码值的大小进行排序的,汉字的排序则是根据 汉语拼音的字母的 ASCⅡ码值进行排序。 67. GB2312-80 方案是我国于 1981 年颁布的《信息交换用汉字编码字符集》 ,共收录了 6763 个汉字,其中一级汉字 3775 个是按照拼音排序,二级汉字 3008 个是按部首排序,另外还 有 682 个图文字符。 68. 基 本 方 法 是 把 任 意 进 制 数 转 换 成 十 进 制 数 后 进 行 比 较 。 (11011001)2=(217)10 、 (37)8=(31)10、(2A)=(42)10,故(37)8 最小。 69.因为正整数的范围仅能用 7 位的二进制数表示,由于最高位是零,当 7 位后全为 1 时, 表示整数 127,再加 1,需要进位,则符号位变为 1,数据发生质的变化,数据由正变为 负;而负数道理基本一样。故为-127 至+127。 70. 因为正数与负数都有唯一的表示格式, 而零可以有两种格式, 00000000 和 10000000。 即: 61-70 参考答案:CBDCBABCAD 71. 由 2*4=11 可知道,十进制数时 2*4=8,而等于 11 则这个进位制一定比 8 小,而且这个 进位除以 8 商为 1 余 1,则可以判定这是 7 进制数。(5*16)7→(5*13)10=(65)10,运用除 7 取余法可得 122。 72. 在计算机内数的表示中,有符号与没有符号的表示即为一个字节表示的内容,一个字节 为 8 位二进制,没有符号就是最高可以表示 11111111,也就是最高可以表示 255。 73.二进制加法法则中说明了,0+0=0,0+1=1,1+0=1,1+1=10(有进位)。 74. 带小数的二进制转换成十进制: 1110111.11=2^6+2^5+2^4+2^2+2^1+2^0+2^(-1)+2^(-2)=64+32+16+4+2+1+0.5+0.25=119.75 75. 规格代形式对尾数的限制是:1/2<=|M|<1,浮点运算后,若结果的尾数绝对值大于等于 1 时,要进行右规,即尾数右移一位,阶码加 1;若结果的尾数的绝对值小于 1/2 时要进 行左规,即尾数左移一位,阶码减 1。 76. 基 本 方 法 是 把 任 意 进 制 数 转 换 成 十 进 制 数 后 进 行 比 较 。 (247)8=(167)10 、
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

18

(A6)16=(166)10、(10101000)2=(168)10,所以 A6 最小。 77.汉字无论笔画多少、拼音是什么,它的内码一般都只占两个字节。 78.求补码的方法:设 X,若 X>=0,则符号位为 0,X 其余各位取值照抄;若 X<0,则符号位 为 1,X 其余各位取值求反,最低位加 1。故此,原码中 X 取值范围是-127 至+127,由于 补码表示时负数的最低位要加 1,即最小数可比原数绝对值大 1,故为-128 至 127。 79. 基 本 方 法 是 把 任 意 进 制 数 转 换 成 十 进 制 数 后 进 行 比 较 。 (1001001)2=(73)10 、 (110)8=(72)10、(4A)16=(74)10 所以 4A 最大。 80.先把 6A 转换成十进制数:(6A)16=(106)10,另外,由于 152 中各位上最大数值为 5,故 不可能为 2、4 进制数,所以肯定为 8 进制数。 71-80 参考答案:CDBBACBADB 81. 由于执行 C:\FORMAT A:<回车>命令时,出错信息显示“命令失败或文件名错” ,这里的 文件名是正确的,说明当前中径下无此命令。如果在执行此命令前曾执行过 PATH c:\DOS(或 AUTOEXEC.BAT 文件中含有此命令),则计算机不会报错,它会自动搜索路径, 执行 C:\DOS 中的 FORMAT.COM 命令。 82.TYPE 是显示文本文件的内容;DIR 显示磁盘的文件目录;CD 是进入或退出子目录(显示 当前目录),只有 XCOPY 命令能够在拷贝文件夹及其子文件夹的内容,因此只有这个命令 有可能在磁盘上建立子目录。 83.只有 TYPE 显示文本文件内容的命令能够成功执行,其他命令都说没有发现该文件。 84. 因特网又称国际互联网。我国于 1994 年正式联入因特网。全国科学技术名词审定委员 会于 1997 年 7 月 8 日为 INTERNET 作出了命名,中文名词为“因特网” ,注释是“指全球 最大的、开放的、由众多网络相互连接而成的计算机网络” 。 85.在许多文件复制过程中,某一个文件读错误,当键入“I”后,忽略错误,继续复制文件, 因此仅此文件无法读取,而其他文件是正确复制且能读取。 86.BUFFER 是开辟缓冲区;FILES 是数据库系统中定义所需要建立的文件数;DEVICE 是指装 置数;DRIVER 是驱动程序命令。 87.ATTRIB 的作用是查看当前目录下的文件属性。 88.A 中左边是错误的命令,右边是将文件内容复制到显示器;B 才是等效的;C 中两个是无 效的命令, D 前面一个命令虽然可以将 A 盘的内容全部拷贝到 B 盘但跟磁盘拷贝命令执 而 行的结果还是不一样的,因为磁盘拷贝不仅内容相同而且位置也相同。 89 CON1 表示接外设端口,其他都和保留设备名无关。 90 一般的计算机网络按网络的涉及范围及范围的距离划分为广域网和局域网,广域网即 WAN,城域网即 MAN,局域网即 LAN,都市网属于城域网。如果按网络的层次结构划分有总 线型、星型、环型等形式。 81-90 参考答案:DCABACBDCD 91 COMMAND.COM 是命令处理程序模块, 为用户提供一个行命令式的界面, 负责接收、 识别、 解释和执行键入的命令行。 92 PROMPT 是改变系统提示符的内部命令。$N$G 表示系统提示符为>前面只有当前驱动器, 显示为 C>;$P$G 表示设置系统提示符为>前面带有当前驱动器和路径,显示为 C:\>。 93 DIR 命令查看一个目录下的文件时,会显示当前目录下的文件总数,最小的情况下是 2 个,也就是说当前目录下没有文件,只有.和..两个目录标识符。 94 在 DOS 提示符下可执行的文件类型一共有 3 种,分别是:.COM、.EXE、.BAT。 95 DEL 是删除文件的内部命令,当 DEL 后跟一个文件的文件名则只删除指定的文件,如果 DEL 后跟通配符,则删除合符要求的多个文件。但不能删除隐含、只读、系统文件。 96 PATH 是指定可执行文件的查找路径的内部命令。
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

19

97

DOS 执行命令的先后顺序是:内部命令—>COM 文件—>EXE 文件—>BAT 文件。TIME 是显 示和设置系统时间的内部命令。 98 编译程序是程序语言软件的功能。 99 计算机网络是计算机技术与通信技术相结合而形成的一种新的通信形式。 把不同地理位 置、具有独立功能的多台计算机、终端及附属设备,用通信链路连接起来,并配备相应的 网络软件, 以实现资源共享为目标而形成的通信系统。 所以网络最突出的优点是共享资源。 100 INTERNET 上可以传输各种多媒体的信息。 91-100 参考答案:CBCBBDDABB 101 DOS 规定,文件名:由 1-8 个字符组成。必须使用 DOS 规定的合法字符。合法字符有: 26 个英文字母(大、小写)、0-9 十个数字和一些特殊字符。另外,文件名中不能有空格、 *、?、[]、( )、/ \、.等符号。 102 A:DOS 是单任务操作系统;B:外部命令并不装在内存中;C:TYPE A.TXT>PRN 是指把 文件 A.TXT 的内容输出到打印中;D:没有 CONFIG.SYS 系统一样可以启动。 103 软盘写保护后,不能写、不能修改、不能删除,更不能格式化,但可以读。 104 操作系统对资源的管理可以分为处理机管理、存储管理、设备管理、文件管理、作业 管理五个主要部分。其中最主要的是设备管理与文件管理。 105 内部命令:指启动时由装入程序从磁盘读入内存并常驻内存的命令。内部命令对应的 程序都放在 COMMAND.COM 中,无需读盘可随时使用。 106 在 WINDOWS 中,将一个应用程序窗口最小化后,这个程序并没有停止运行,只是在后 台继续运行,但窗口被最小化了,所以我们看不见它的运行过程。 107 FTP:文件传输;WWW:信息浏览;BBS:电子公告牌;E-mail:电子邮件。 108 用户在网上最常用的信息查询工具叫搜索引擎。 109 WINDOWS 窗口的右上角的按钮一共有四种:最小化、最大化、还原、关闭。其中最大 化与还原不可能同时出现。 110 WINDOWS 窗口中窗口角可以调整窗口的宽度和高度,窗口边框只能调整宽度或高度, 滚动条可以实现窗口内容的滚动,菜单提供各种菜单命令给用户使用。 101-110 参考答案:BCBADACBCA 111 算法是指人们为了解决问题而选取的方法和实施步骤,而程序设计只是用计算机去实 现问题求解的一种手段。 计算机语言则是程序设计的基础, 计算方法是在解决问题过程中 所需要的数学模式等。 112 栈是一个后进先出的线性表,根据题意,可得,1、2、3 进栈,然后是 3 出栈,4 进栈, 4 出栈,最后 5 进栈,此时出栈的元素次序为 3、4。 113 在容量为 N 的循环队列中,有可能出现两种情况,一种是尾指针 R 比头指针 F 大,则 其元素个数为 R-F;另一种情况是尾指针比头指针小,则其元素个数为 R-F+N。为了更好 地表示队列中元素的个数,可以用通用公式(r-f+n) MOD n 来表示任意情况下的元素个数。 114 在通常情况下,数据的徘序,常用快速排序法,然而当数据已经有序时,再用快速排 序方法,就不能体现少比较数据、交换数据的特点,需要将数据进行一一比较,这样快速 排序就蜕化为冒泡排序了。 115 哈夫曼树是一种特殊的满二叉树,因此若有 N 个叶子节点,则其总节点数也是 2N-1。 116 二分法查找元素其基本思想: 将数据元素对半分, 将待查找的数与中间位置数相比较, 若大于该中间位置的数,则在数据段的后半段检索,否则在前半段检索。重复上述步骤, 最坏的情况下需要查看 10 个单元。 117 数组地址计算问题,只要掌握数据是顺序存储并占用连续的存储空间。注意问题的要 求按行存储还是按列存储,就能计算任意单元的起始地址。如题:按行分配空间,则 A[5,
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

20

8]前 4 行共 40 个单元,第 5 行开始 A[5,1]至 A[5,7]共 7 个单元,即 A[5,8]前有 47 个单元,其地址是 SA+(47*3)=SA+141 118.线性表中的链接存储的特点: 是将零散的存储空间通过指针域连接起来, 因此链接存储 单元一般至少有两个域:数据域和指针域,通过指针将结点链接后生成链接表。所以存储 单元地址可以连续也可以不连续。 119.二维数组本身是一个 M 行 N 列的矩阵,每行、每列都可以看做一个线性表。而其中其个 元素可以看成一个列向量的线性表, 也可以看成一个行向量的线性表。 所以二维数组每个 数据元素可以看作一个线性表的线性表。 120.由于线段两端相同,故此,增加一只不同鸟,产生两条两端不同小鸟的线段,增加两只 不同鸟,可以产生两条或四条两端不同小鸟的线段。增加 N 只不同小鸟,由于线段两端是 相同鸟,通过对称排列,必定是偶数个两端为不同小鸟的线段。 111-120 参考答案:BDDDBBADDB 121.列车转辙网络是一个栈,数据进入栈中可以随时出栈,但其必须遵循后进先出的规则。 故此,A 中既然 4 最先出栈则,1 不可能第二个出栈;C 中既然 3、4 在前面出栈,1 就不 可能在 2 前出栈;D 中原因同上。 122.选择排序的基本思想: 每次从待排序的记录中选择出关键码值最小(或最大)的记录, 顺 序放在已排序的记录序列的一端,直到全部排完。 123.栈是使用最广泛的数据结构之一,表达式求值、递归过程实现都是栈应用的典型例子。 124.链表的一个重要特点是插入、删除运算灵活,不需移动结点,只要改变结点中指针域的 值就可以了。 125.树叶: 度为 0 的结点; 分枝结点: 度不为 0 的结点;结点:树中的每一个元素都叫结点。 所以无论是什么二叉树,树叶+分枝结点=结点。 126.一维数组长度固定, 在定义时都必须指出其下标的范围。 线性表是一个相当灵活的数据 结构,它的长度可以根据需要增加或缩短。 127.选择排序的基本思想: 每次从待排序的记录中选择出关键码值最小(或最大)的记录, 顺 序放在已排序的记录序列的一端,直到全部排完。 128.冒泡排序的基本思想: 对待排序的记录的关键字进行两两比较, 发现两个记录是反序的, 则进行交换, 直到无反序排序的记录为止。 最理想的情况就是原来已经没有反序排序的记 录,那么只需要比较 n-1 次就可以完成了。 129.二叉树的性质:对于任意一棵二叉树,如果其端结点数为 N,而其度为 2 的结点总数为 M 时,有 N=M+1。 130.二叉树的先序序列顺序为:根左右;中序序列顺序为:左根右;要其两个序列的结果相 同,必须是缺少了左子树,即大家都变成了根右的顺序了。 121-130 参考答案:BCABAADCAC 131.栈是一个后进先出的线性表,C:如果 C 先出栈,则必定是 A、B 均在栈中,而且 B 比 A 后进栈,所以出栈必须是 B 比 A 先出。 132.几种排序需要内存容量的比较:插入排序:1;选择排序:1;快速排序:以 2 为底 n 的对数;归并排序:n。所以最大的是归并排序。 133. 快速排序:第一趟:{27,38,13},49,{76,96,65,50};第二趟:13,27,38,49,{76,96, 65,50}(对左子表排序);第三趟:13,27,,38,49,50,65,76,96(对右子表排序)。 134.利用二叉树对一组数进行排序,先生成一棵二叉排序树,然后进行中序遍历,所得的结 果就是按升序排列的数据。 135.选择排序的基本思想: 每次从待排序的记录中选择出关键码值最小(或最大)的记录, 顺 序放在已排序的记录序列的一端,直到全部排完。这是一个典型的选择排序。
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

21

136.在二叉树中,第 I 层的结点总数不超过 2^(I-1);而深度为 K 的二叉树的结点总数不超 过 2^k-1。故满二叉树的结点总数为:2^k-1(k 为二叉树的深度) 137.满二叉树的结点总数为:2^k-1(k 为二叉树的深度)。由此得:2^5-1=31。 138.线性表的第一个元素没有前趋元素,线性表的最后一个元素没有后继元素。 139.哈夫曼树,又称最优树,是一类带权路径最短的树。 140.平衡二叉树,又称 AVL 树。它或者是一棵空树,或具有下列性质的二叉树:(1)左子树 和右子树都是平衡二叉书树;(2)左子树和右子树的深度之差的绝对值不超过 1。由此, 12 个结点的平衡二叉树的深度最多可以为 5 层。 131-140 参考答案:CDABACCCDB 141.冒泡排序:对待排序的记录进行逐个比较,如发现两个记录是反序的,则进行交换,直 到无反序排列的记录为止,即当一次比较后没有进行交换则排序完成。由此可得,当第七 趟排序时就没有出现交换了,所以只比较了 70 次就可以完成排序。 142.中序遍历的顺序是左根右;故此要 n 在 m 前,必须 n 在 m 的左方。 143.直接插入排序的比较的次数为 n-1 次,交换次数为 0。 144.由于已知二叉树的前序与中序后,可画出二叉树,并得出后序。由于前序为 STUWV,所 以根必然是 S,由于中序是 UWTVS,故此此二叉树没有右子树。左子树前序为 TUWV 可得左 子树根为 T,中序为 UWTV 可得左子树根 T 有一右子根 V,左子树 T 的左子树根为 U,U 有 一右子树 W。故此后序为 A。 145.具有 3 个结点的的二叉树有 5 种。分别是:左孙、左子、根;右孙、左子根;左子、根、 右子;根、右子、左孙;根、右子、右孙。 146.快速排序适用了原数列没有序的情况,如果原数大部分成序的话,速度越慢。最慢的情 况就是所有数据已经成序。 147.该数组一共有 80 个元素, 一个元素需要 3 个字节, 故存放该数组至少需要 240 个字节。 148.因为把树转化为二叉树时,把所有原来同层的子树都变成了原来的左子树的右子树了。 故此,树的先根遍历序列与其对应的二叉树的先序遍历序列相同。 149.在数据结构中,从逻辑上把数据结构分成线性结构和非线性结构。 150. 因为把树转化为二叉树时,把所有原来同层的子树都变成了原来的左子树的右子树了。 故此,有序树的后序就是其转化成得的二叉树的中序。 141-150 参考答案:CCCACDCABB 151.通过二叉树的先序与中序可以写出二叉树,并由此可以得出后序为 gdbehfca。 152.选择排序的基本思想是: 每次从待排序的记录中选择出最小(或最大)的记录, 顺序放在 已排好的记录序列的最后。 153.快速排序在被排序数据中已基本有序的情况下最不利于发挥其长处。 154. A:顺序存储插入、删除运算效率低;B:链表中的最后一个结点的指针域为空。C:包 含 n 个结点的二叉排序树的平均检索长度为(log2n)2 为底 n 的对数。 ?? 151-160:DBCDACBDAB 161-170:DABAACAACD 171-180:BCBADBBAAC 说明:第 1 题到第 60 题为基础知识; 第 61 题到第 80 题为数与编码; 81-110 为基本操作与网络; 111-180 为数据结构与算法。 181-190(04 高中组题) :ADECBBCDCA 191-200(03 高中组题)BBDABBCECB 二、多项选择题 1-10 D BDE AD AB AC E B BCD D BE 11-15 ABC ABDE CEF AB BCE 16-25(04 高中组题)BC ACDE BCD D AC BE ADE ACD ABDE BCE 26-35(03 高中组题)D BDE AD AB AC E B BCD D BE
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理 22

南通中学 NOIP 初赛练习之二(解答题)
前言:如何做解答题 解答题一般是根据要求写出表达式或画出图等, 涉及的知识点主要有数学方面的基本知 识、数据结构方面的如树和图等、逻辑推理等,难点主要在写出递推公式。写出公式之前要 先从起始值开始进行摸索,写出若干个结果之后再观察其中的规律,再写出公式,一般是 F (N)=??,省略号部分可能是 F(N-1) 、F(N-2)??等的数学表达式。最后再验证公 式的正确性,时间允许的话可从数学等方面加以证明(当然不要写出证明过程,除非要求你 说明其正确性) 。 有时是图形的变换,如正方形、三角形、圆等的旋转,先前给出了几个点相应的坐标, 求旋转若干周后的各点坐标,这种情况一般用到求余的运算,当以 N 为一个周期时往往是 用对 N 求余(mod n)的运算;如果是正反两种情况可以使用(-1)的若干次方的形式来转 换两种状态,即用某一表达式乘以-1 的若干次方。 有时是有关组合数学的知识,如排列或组合,确定是(分步)乘法原理还是(分类)加法 原理。对于排列分次序,而组合不分各元素的次序: 组合:C(m, n)=n*(n-1)*….*(n-m+1)/m! 排列:P (m, n)= n*(n-1)*….*(n-m+1) 数据结构方面要对堆栈的先进后出原理、队列的先进先出原理、二叉树(结点)的遍历、 图的邻接矩阵表示法熟悉。 至于逻辑推理方面的要将各个条件(描述)一一列出,排除矛盾情况,列举出可能的情 况,写出符合条件的结果。

练习:
1.公式推导(10 分)1999 年初中组初赛题 根据 Nocomachns 定理, 任何一个正整数 n 的立方一定可以表示成 n 个连续的奇数的和。 如: 3 1= 1 23= 3+ 5 33= 7+ 9 +11 43=13 十 15+17+19 在这里,若将每一个式中的最小奇数称为 X,那么当给出 n 之后,请写出 X 与 n 之间 的关系表达式:___ 2、问题解答: (每题 7 分,共 14 分) 2000 初中组 (1).已知,按中序遍历二叉树的结果为:abc 问:有多少种不同形态的二叉树可以得到这一遍历结果,并画出这些二叉树。 (2).有 2×n 的一个长方形方格,用一个 1×2 的骨牌铺满方格。例如 n=3 时,为 2×3 方格。此时用一个 1×2 的骨牌铺满方格,共有 3 种铺法。 试对给出的任意一个 n (n>0) ,求出铺法总数的递推公式。 3.问题求解: (6+6=12 分) 2000 高中组 (1).已知,按中序遍历二叉树的结果为:abc 问:有多少种不同形态的二叉树可以得到这一遍历结果,并画出这些二叉树。 (2).设有一个共有 n 级的楼梯,某人每步可走 1 级,也可走 2 级,也可走 3 级,用递推 公式给出某人从底层开始走完全部楼梯的走法。 例如: n=3 时, 当 共有 4 种走法, 1+1+1, 即 1+2,2+1,3。 4、问题求解(5+7=12 分) 2001 年初中组
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理 23

(1) 在 a,b,c,d,e,f 六件物品中,按下面的条件能选出的物品是: (1)a,b 两样至少有一样 (2)a,d 不能同时取 (3)a,e,f 中必须有 2 样 (4)b,c 要么都选,要么都不选 (5)c,d 两样中选一样 (6)若 d 不选,则 e 也不选 (2) 平面上有三条平行直线,每条直线上分别有 7,5,6 个点,且不同直线上三个点都 不在同一条直线上。问用这些点为顶点,能组成多少个不同三角形? 5、问题求解(5+7=12 分) 2001 年高中组 (1).已知一棵二叉树的结点名为大写英文字母,其中序与后序遍历的顺序分别为: CBGEAFHDIJ 与 CGEBHFJIDA 则该二叉树的先序遍历的顺序为:ABCEGDFHIJ (2)平面上有三条平行直线,每条直线上分别有 7,5,6 个点,且不同直线上三个点都 不在同一条直线上。问用这些点为顶点,能组成多少个不同四边形? 6. 问题求解 每题 5 分 (2003 年高中组) (1) 无向图 G 有 16 条边,有 3 个 4 度顶点、4 个 3 度顶点,其余顶点的度均小于 3,则 G 至少_______个顶点。 (2) 某年级学生共选修 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 门课程。 7. 问题求解(共 2 题,每题 5 分,共计 10 分,2004NOIP 初赛提高组) (1) 5 名儿童到游乐场去玩。他们可以骑旋转木马,坐滑行铁道,乘宇宙飞船。已知其 中 20 人这三种东西都玩过,55 人至少玩过其中的两种。若每样乘坐一次的费用是 5 元,游乐场总共收入 700,可知有 名儿童没有玩过其中任何一种。 (2) 知 a, b, c, d, e, f, g 七个人中,a 会讲英语;b 会讲英语和汉语;c 会讲英语、意大利 语和俄语;d 会讲汉语和日语;e 会讲意大利语和德语;f 会讲俄语、日语和法语;g 会讲德语和法语。能否将他们的座位安排在圆桌旁,使得每个人都能与他身边的人 交谈?如果可以,请以“a b”开头写出你的安排方案: 。 参考答案: 1、x=n*n-n+1 2、(1) 5 种,图略 (2) 对 给 出 的 任 意 一 个 n(n>0) , 用 F(n) 表 示 其 铺 法 的 总 数 的 递 推 公 式 为 : F(1)=1 F(2)=2 F(n)=F(n-2)+F(n-1) (n≥3) 3、(1) 5 种 图略 (2) f(1)=1 f(2)=2 f(3)=4 f(n)=f(n-1)+f(n-2)+f(n-3) (n>3) 4、 (1) a、b、c、f (2) 751 5、(1) ABCEGDFHIJ (2) 2250 C(7,2)*C(5,2)+C(7,2)*C(6,2)+C(5,2)*C(6,2)+C(7,2)*5*6+C(5,2)*7*6+C(6,2)*7*5 6、 (1) 11 (2) 4
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理 24

7、 (1)75-55-(700/5-20*3-35*2)=10 (2) a b d f g e c

江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

25

阅读材料: 递推公式的推导
历年的信息学 (计算机) 奥林匹克分区联赛初赛的试题中均有根据要求写出递推公式(数 学上又叫通项公式)的题目。如 2000 年高中组的题目是:一个人上楼梯,一步可以跨一阶、 可以跨两阶、也可以跨三阶,假设有N阶楼梯,此人有多少种走法? 许多同学在推导公式时往往采用尝试法,从N=1,2,3?的情况依次算出有多少种 情况,然后观察出其中的规律,最后写出递推公式。如此上楼梯的走法可以转化为一个数字 的有序拆分: N=1 1=1 (只能一步跨一阶楼梯)共有1种走法,即 F(1)=1; N=2 2=1+1 (一步一阶) =2 (一步两阶) 共有2种走法,即 F(2)=2; N=3 3=1+1+1 (每一步一阶) =1+2 (第一步一阶,第二步两阶) =2+1 (第一步两阶,第二步一阶) =3 (一步三阶) 共有 4 种走法,即 F(3)=4; N=4 4=1+1+1+1 =1+1+2 =1+2+1 =1+3 以上 4 种走法除了第一步为一阶,后面的组合与 N=3 同 =2+1+1 =2+2 以上 2 种走法除了第一步为两阶,后面的组合与 N=2 同 =3+1 此走法除了第一步为三阶,后面的组合与 N=1 同 共有 7 种走法,即 F(4)=F(3)+F(2)+F(1)=7; N=5 5=1+1+1+1+1 =1+1+1+2 =1+1+2+1 =1+1+3 =1+2+1+1 =1+2+2 =1+3+1 以上 7 种走法除了第一步为一阶,后面的组合与 N=4 同 =2+1+1+1 =2+1+2 =2+2+1 =2+3 以上 4 种走法除了第一步为两阶,后面的组合与 N=3 同 =3+1+1 =3+2 以上 2 种走法除了第一步为三阶,后面的组合与 N=2 同 共有 13 种走法,即 F(5)=F(4)+F(3)+F(2)=13; ?? 由此推导出递推公式为: F(N)=F(N-1)+F(N-2)+F(N-3) (N>3) F(1)=1,F(2)=2,F(3)=4 这种推导方法主要靠排列准确、观察仔细,从而才能正确地写出递推公式。许多情况下
江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

26

写出的排列组合不是少几种就是多一到几种, 很难写出正确的递推公式, 特别是排列组合的 种类较多时,人工的机械地排列组合就更难实现了,如N封信装在N个信封全装错的问题。 另外,通过观察写出的递推公式还不能证明是正确的,要证明其正确性,还要借助于数学归 纳法。其实我们可以直接用数学归纳法的思想来推导递推公式,还是来看楼梯的走法: 假设上 N 阶楼梯的过程已经进行到最后一步,因为每一步可以有三种走法,因此最后 一步也无非是跨一阶、 跨二阶或跨三阶。 如果最后一步跨一阶, 前面的 N-1 阶的走法有 F(N-1) 种;如果最后一步跨两阶,前面的 N-2 阶走法有 F(N-2)种;如果最后一步跨3阶,前面的 N-3 阶有 F(N-3)种。根据有关原则可以知道最后总的走法数目应是这三种走法的和。从而可 以推导出 F(N)=F(N-1)+F(N-2)+F(N-3)。 在这种构造推导公式时要考虑到是否全面, 如N封信装在N个信封全装错的问题: N封 写给N个人的信,有N个信封已经写好了地址,本来这 N 封信和 N 个信封是一一对应的, 假设N封信全都装错信封,有多少种不同的装法? 在构造时一般都能做出以下步骤的推导: 假设 N-1 封信全装错在 N-1 个信封里(N>2),有 F(N-1)种。现有第 N 封信和第 N 个 信封,对于 F(N-1)的某一种全装错的装法而言,把第 N 封信依次装在第一个信封、第二 个信封??第 N-1 个信封,而把原来第一个信封、第二个信封??第 N-1 个信封里的信装 在第 N 个信封里,这样的 N-1 种装法都符合要求。原 F(N-1)种都用此法,共有(N-1) *F(N-1)种,由此推出 F(N)=(N-1)。 ! 以上的构造并没有包括所有的情况,假设原 N-1 封信有 1 封信是装对的,而其它的 N-2 封是全装错的,此时把第 N 封信装在原装对的信封里, 而原信封里的信装在第 N 个信封里, 这样 N 封信全装错了信封。当第一封信装对信封,其它的 N-2 封信全装错共有 F(N-2)种 装法,当第二封信装对信封,其它的 N-2 封信全装错也有 F(N-2)种装法??,这种情况 总共有(N-1)*F(N-2)种装法。 所以 N 封信全装错信封的方法的个数的递推公式为: F(N)=(N-1)*F(N-1)+(N-1)*F(N-2) (N>2) F(1)=0, F(2)=2 因此,要在相对较短的时间里推导出相应的公式,用观察尝试法写出公式虽然简单,但 往往容易多写或少写几种情况, 从而写出错误的公式。 使用构造法, 即由 F N-1)F N-2) ( 、 ( ?? 的情况推导出 F(N) ,才是最终的目的。最后提醒别忘了写上初始值: F(1)=??;F(2)=??;??。 这是递推的起点。 有些问题虽然写不出递推公式, 但是实际操作的过程中有递推的思想, 可以通过文字描 述出其递推的过程。 思考题: 1、有 N 个黑棋子和 N 个白棋子如下图排列(N>=4) : ●●●●??●○○○○??○ 现在让你移动棋子, 每次只能移动相邻的两个棋子放到空白位置 (最左边或最右边 没棋子的地方也认为是空白位置) 。最终移成如下黑白相间的状态: ●○●○●○●○??●○ 写出移动方案。 (提示:先想出 N=4 时的移动方案,N>4 的情况都可以由 N-1 的推 导出。 2、将一个正方形分成 n 个小正方形(n>5)。

江苏省南通中学信息学奥林匹克联赛初赛系列练习 岳军编辑整理

27


推荐相关:

初赛复习题_NOIP_江苏省南通中学信息学奥林匹克联赛初赛

初赛复习题_NOIP_江苏省南通中学信息学奥林匹克联赛...南宁十六中 NOIP 初赛练习题之一(选择题) 前言...( ) A.0 B.1 C.2 D.3 94、在 DOS 提示符...


江苏省南通中学高二年级电化学原理及应用单元检测题

初赛复习题_NOIP_江苏省南... 51页 2财富值 江苏省南通第一中学2008届......江苏省南通中学高二年级电化学原理及应用单元检测题 2004.5 第Ⅰ卷 (选择题 共...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com