当前位置:首页 >> 学科竞赛 >> NOIP初赛相关知识点及参考答案

NOIP初赛相关知识点及参考答案


相关知识点与参考答案
一.单项选择题 1、操作系统是系统软件的核心,是有效利用计算机的硬件、软件、数据等各种资源的好管 家, 它还向用户提供一套容易学习使用的操作命令。 常用的操作系统有: MS-DOS、 PC-DOS、 WINDOWS、UNIX、LINUX、OS/2 等。WORD、WPS 是字处理软件,FOXBASE 是数据库管理软件。 2、字长表示一个存储单元由多少

位二进制数组成,八位机一个字长就是一个字节,十六位 机一个字长可以表示两个字节。字长位的多少,表明可访问存储器的地址多少。 3、操作系统一般存放在系统盘,计算机启动引导系统后,系统中的常用命令就驻留在内存 中, 方便用户使用计算机。 所以启动计算机引导系统就是把操作系统从系统盘中调入内存 储器。 4、我们要清楚,快存实质是高速缓存,主存即内存,辅存也就是外存。在这三种存储器中, 以高速缓存最快,故此,通常常用的程序都是存放在高速缓存区里。而主存的速度当然是 比辅存要快了。 5、一般,对计算机工作有较大影响的有尘土、温度、湿度。 6、计算机的指令系统是由操作码与操作数组成。 7、通用寄存器的位数跟机器有关,取决于计算机的字长。 8、计算机能实现的全部指令的集合合称为指令系统。执行各条指令所规定的操作是由指挥 工作的控制器和执行运算的部件共同完成。而控制器与运算器合起来称为 CPU。 9、RAM(random access memory)随时读写存储器,供计算机工作时随机写入,计算机一旦断 电后,其中的信息就会消失。 10、 WINDOWS 9X 是一种多任务的可视化的操作系统,它可以同时打开多个窗口,执行 多个任务,而这些操作无论是应用程序还是文档编辑窗口,都可以利用图标、菜单或工 具进行操作,即所见即所得。所以称之为多任务图形方式的操作系统。 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 位的奔腾处理器一次能处理 64 位信息相当于 8 字节。 11-20 参考答案:CADBCCBDCA 21、计算机系统由硬件系统和软件系统组成。 22、操作系统是系统软件的核心,是有效利用计算机的硬件、软件、数据等各种资源。 23、RAM(random access memory)随时读写存储器,供计算机工作时随机写入,计算机一旦 断电后,其中的信息就会消失。 24、在电脑中,各种各样的数据都是以文件的形式存放的。 25、 计算机系统是由硬件和软件两部分组成, 有效的使用和管理计算机的各种输入和输出设 备,应用各种软件,必须借助于计算机的操作系统。 26、 计算机的工作原理跟人的大脑很相似, 而且还是大脑功能的延伸, 所以习惯上叫它电脑。 27、存储容量是指存储的信息量,它用字节(BYTE)作用基本单位。 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、 标准指法中, 9 个基本健是 ASDFJKL;与空格键。 当未击键时, 十个手指都放在基本键上, 左手尾指 A、左手无名指 S、左手中指 D、左手食指 F、右手食指 J、右手中指 K、右手无 名指 L、右手尾指;、两只大拇指空格。 53、主机、键盘、显示器是构成计算机的三大硬件,操作系统是软件。 54、硬盘工作时应特别注意震动,因为高速运行时,震动会使硬盘的磁头划花磁盘片。 55、打印机术语中的 24 针是指打印头有 24 根针。 56、办公室自动化应用了计算机的信息处理自动化的特点。 57、计算机辅助设计(Computer Assisted Design) 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 、 (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 是指定可执行文件的查找路径的内部命令。 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, 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.选择排序的基本思想: 每次从待排序的记录中选择出关键码值最小(或最大)的记录, 顺 序放在已排序的记录序列的一端,直到全部排完。这是一个典型的选择排序。 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


更多相关文档:

NOIP初赛相关知识点及参考答案

NOIP初赛相关知识点及参考答案_学科竞赛_高中教育_教育专区。NOIP初赛相关知识点及参考答案 相关知识点与参考答案一.单项选择题 1、操作系统是系统软件的核心,是有效...

NOIP初赛知识点复习总结

抓住了它,得出答案就变得很容易了,而且对结果也会有信 心。写程序运行结果大纲...NOIP初赛试题分析及知识... 29页 1下载券 一元二次方程所有知识点... 80...

NOIP初赛理论知识复习资料要点摘录

NOIP初赛理论知识复习资料要点摘录_学科竞赛_高中教育_教育专区。要点摘录 ?计算机...计算机网络的功能 ?计算机网络分类 ?OSI 参考模型 ?TCP/IP 协议 ?IP 地址介绍...

信息学奥赛NOIP初赛复习知识点+基本函数

信息学奥赛 NOIP 初赛复习知识点+基本函数 1 被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯· 诺依曼 于 1945 年发表了一个全新的 " 存储程序...

信息学奥赛NOIP初赛复习知识点

信息学奥赛 NOIP 初赛复习知识点 1、计算机相关科学家: A: 被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯· 诺依曼 于 1945 年发表了一个 全新...

NOIP初赛知识汇总

13. 14. NOIP 初赛知识汇总 现代计算机的结构是由美籍匈牙利数学家“冯.诺依曼”提出来的“程序存储”结构,它包 括“运算器”“控制器”“存储器”“输入设备”...

信息学奥赛NOIP初赛复习知识点

信息学奥赛 NOIP 初赛复习知识点 1、计算机相关科学家: A:被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯 ·诺依曼 于 1945 年发表了一个 全新的...

NOIP初赛试题分析及知识点

NOIP初赛试题分析及知识点_IT/计算机_专业资料。NOIP初赛试题分析及知识点,初高中...所以答案就是 3465*264=914760 再看它的输出格式,输出的应该是:___9___1...

普及组NOIP初赛复习——基础知识STU

普及组NOIP初赛复习——基础知识STU_其它课程_高中教育_教育专区。分区联赛初赛...网关 E. 网桥 答案:1-4 BBCA 五、网络 1.关于网络的一些定义: 所谓计算机...

信息学奥赛NOIP初赛复习知识点

信息学奥赛 NOIP 初赛复习知识点 1、计算机相关科学家: A: :被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯· 诺依曼 于 1945 年发表了一个 ...
更多相关标签:
noip初赛知识点 | noip提高组初赛知识点 | noip2016初赛答案 | 2016noip初赛试题答案 | noip2015初赛答案 | noip2014初赛答案 | noip2016初赛 | noip2015提高组初赛 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com