Noip初赛综合练习情况总结复习资料(考点和例题)第二版.doc

,. NOIP 初赛复习指南 第二版 知识点和例题 By.褚家言 2017-10-13 ,. 初赛考的知识点就是计算机基本常识、基本操作和程序设计基础知识。其中选择题考查的是知识，而问题 解决类型的题目更加重视能力的考查。一般说来，选择题只要多用心积累就可以了。问题解决题目的模式比较 固定，大家应当做做以前的题目。写运行结果和程序填空也需要多做题目，并且培养良好的程序阅读和分析能 力，就像语文的阅读理解一样。近几年来，初赛的考查范围有了很大的变化，越来越紧跟潮流了。这就需要大 家有比较广泛的知识，包括计算机硬件、软件、网络、简单的数据结构（例如栈、队列、树和图等）和简单的 算法（例如排序、查找和搜索等） ，程序设计语言以及一些基本的数学知识和技巧。 知识点复习： 第一部分第一部分 计算机基础知识计算机基础知识 1. 计算机的发展计算机的发展 知识点:1>.计算机的发展阶段(4 代,标志及主要特点) 2>.ENIAC,图灵,冯.诺依曼,Ada Lovelace(第一个程序员) 2. 计算机系统计算机系统 1>.计算机硬件计算机硬件 a. 组成:运算器,控制器,存储器,IO 设备; b. CPU:字长,主频(时钟频率),总线; c. 存储器:内(ROM,RAM),外存储器,种类,单位,存取速度; ,. d. 输入输出设备:扫描仪,数字化仪,绘图仪,打印机(种类) 2>.计算机软件计算机软件: a. BIOS (功能); b.系统软件(包括操作系统:DOS,LINUX,UNIX,WINDOWS,OS/2,MAC/OS 和语言的解释或编译程序); 解释程序:高级语言翻译的一种,它将源语言(如 basic)书写的源程序作为输入,解释一句后就提交计算机执行 一句,并不形成目标程序. 翻译程序: (编译程序)一类很重要的语言处理程序,它把高级语言(如 FORTRAN,COBOL,pascal,c 等)源程序 作为输入,进行翻译转换,产生出机器语言的目标程序,然后再让计算机去执行这个目标程序,得到计算结果. 语言:机器语言 汇编语言 高级语言(面向对象,面向过程) ,. c.应用软件 数据库管理软件:Foxpro，Access，Orale，Sybase，DB2 和 Informix 等。 字处理软件: WPS, word 3>.计算机的主要性能指标计算机的主要性能指标 1. 字长 2. 速度 3. 存储系统容量(bit,B,KB,MB,GB,TB) ,. 3. 数据在计算机中的表示数据在计算机中的表示 1>.数值的表示:二进制,八进制,十六进制,十进制(包括小数部分的转化) 原码,反码,补码的表示 2>.字符的表示: ASCII 码(128 个) ,. 0-48 A-65 a-97 汉字的表示: 2 个字节(Byte) :机内码,输入码,字型码 3>.图像的表示 4>.声音的表示 4.计算机的维护与使用安全计算机的维护与使用安全 1>. 计算机的维护与安全使用常识 (电源,温度,湿度,开关机) 2>. 计算机病毒的预防与消除 ,. (何谓病毒,病毒的特点,杀毒方式及软件) 第二部分第二部分 计算机网络计算机网络 1.计算机网络的定义计算机网络的定义: 计算机网络计算机网络，就是把分布在不同地理区域的计算机与专门的外部设备用通信线路互连成一个规模大、功 能强的网络系统，从而使众多的计算机可以方便地互相传递信息，共享信息资源。 2.计算机网络名词计算机网络名词: ISP: 因特网服务提供商,能提供拨号上网服务、网上浏览、下载文件、收发电子邮件等服务。即为用户提 供 Internet 接人和(或)Internet 信息服务的公司和机构。如”中国电信”等; DNS: 域名服务器; FTP: 文件传输协议; HTTP:超文本传输协议; SMTP:简单邮件系统传输协议; WWW: 万维网; POP3: 邮件传输协议 ARP: 地址解析协议 3.两种网络参考模型两种网络参考模型 OSI 开放式系统互联模型参考模型开放式系统互联模型参考模型: (七层七层) 由下到上:物理层、数据链路层、网络层、传输层、会话层、表示层、应用层； TCP/IP 参考模型参考模型(五层五层) ,. 由下到上:、物理层、数据链路层，互联网层、传输层、应用层 4.网络软件网络软件 1>.计算机协议计算机协议: (TCP/IP) a. TCP : Transfer Control Protocol,传输控制协议传输控制协议 b. IP: Internet Protocol,网际协议网际协议 c. 三类 IP 地址: IPV4 2>.应用软件应用软件: 5.网络硬件网络硬件 ,. (网卡网卡, MODEM,光纤光纤,双绞线双绞线,同轴电缆同轴电缆,无线信道无线信道) 6.网络分类网络分类 计算机网络的类型有很多，而且有不同的分类依据。计算机网络的类型有很多，而且有不同的分类依据。 按拓扑结构按拓扑结构:总线型、星型、环形、树形 按地域按地域:局域网、城域网、广域网和网间网 7.域名的表示域名的表示 第三部分第三部分 数据结构数据结构 ,. ,. 1.简单数据类型简单数据类型: a 数值数值: integer, real, longint b 字符字符: char c 布尔类型布尔类型: Boolean d 数组数组:一维一维,二维二维 e 字符串字符串: string 2.线性表线性表 ,. 栈、队列栈、队列 3.树树 二叉树、哈弗曼树 4.图图 图的最小生成树、最短路径 第四部分第四部分 基本及常用算法基本及常用算法 ,. 第五部分第五部分 问题求解问题求解 队列、栈、二叉树等数据结构、数学问题、归纳法、数列和逻辑推理、排列组合等 题型归类：题型归类： 第一部分：选择题（第一部分：选择题（3030 分分=20*1.5=20*1.5） 一般是比较容易得分的，不可错过！ 程序设计方面的知识多是平时计算机课堂教学或课外活动中学到的，建议大家找全国计算机等级考试（一、 二级）的题目做做，一般不超过二级的知识点，知识要复习的系统一些。新大纲和最近两年的考试不再考 DOS，但有 DOS 经验的选手可能会占一点便宜，因为有些题目可以根据经验判断。另外，往更高层次发展的过 程中，必要的 DOS 知识和命令还是必须的。 类型类型 1 1：计算机原理：计算机原理： NOIP1999： 1、微机内的存储器的地址是以( C )编址的。 A. 二进制位 B. 字长 C. 字节 D. 微处理器的型号 2、下列诸因素中,对微机工作影响最小的是 ( B ) A. 尘土 B. 噪声 C. 温度 D. 湿度 3、在 24*24 点阵的字库中，汉字“一 ”与“编”的字模占用字节数分别是（ C ） A. 32、32 B. 32、72 C. 72、72 D. 72、32 7、计算机能直接执行的指令包括两部分,它们是（ B ） A. 源操作数与目标操作数 B. 操作码与操作数 C. ASC码与汉字代码 D. 数字与字符 8、在微机中，通用寄存器的位数是 （ C ） A. 8 位 B. 16 位 C. 计算机字长 D. 32 位 9、在计算机,字符编码通常采用( C ) A. 原码 B. 反码 C. ASCII 码 D. 补码 13、已知小写字母“M”的十六进制的 ASC码值是 6D，则小写字母“C”的十六进制数的 ASC码值是 （ D ） A. 98 B. 62 C. 99 D. 63 14、计算机中的数有浮点与定点数两种，其中用浮点数表示的数，通常由（ C ）这两部分组成。 A. 指数与基数 B. 尾数与小数 C. 阶码与尾数 D. 整数与小数 16、启动计算机引导 DOS 是将操作系统 ( D ) A. 从磁盘调入中央处理器 B. 从内存储器调入高速缓冲存储器 C. 从软盘调入硬盘 D. 从系统盘调入内存储器 18、组成“教授” （JIAO SHOU）,“副教授” （FU JIAO SHOU）与“讲师”(JIANG SHI)这三个词的汉字，在 GB2312-80 字符集中都是一级汉字，对这三个词排序的结果是（ D ） A. 教授、副教授、讲师 B. 副教授、教授、讲师 C. 讲师、副教授、教授 D. 副教授、讲师、教授 19、不同的计算机，其指令系统也不相同，这主要取决于 （ C ） A. 所用的操作系统 B. 系统的总体结构 C. 所用的 CPU D. 所用的程序设计语言 NOIP2000： ,. 8.计算机系统总线上传送的信号有（ B ） A.地址信号与控制信号 B. 数据信号、控制信号与地址信号 C.控制信号与数据信号 D. 数据信号与地址信号 9.计算机的运算速度取决于给定的时间内，它的处理器所能处理的数据量。处理器一次能处理的数据量叫字长。 已知 64 位的奔腾处理器一次能处理 64 个信息位，相当于（ A ）字节。 A.8 个 B.1 个 C.16 个 D. 2 个 14.不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢的排列是（ C ） A.快存/辅存/主存 B. 外存/主存/辅存 C. 快存/主存/辅存 D. 主存/辅存/外存 NOIP2001： 1、中央处理器 CPU 能访问的最大存储器容量取决于( A ) A)地址总线 B)数据总线 C)控制总线 D)内存容量 7、若我们说一个微机的 CPU 是用的 PII300，此处的 300 确切指的是( A ) A)CPU 的主时钟频率 B)CPU 产品的系列号 C)每秒执行 300 百万条指令 D)此种 CPU 允许最大内存容量 NOIP2002： 1 微型计算机的问世是由于（ C ）的出现。 A）中小规模集成电路 B）晶体管电路 C） （超）大规模集成电路 D）电子管电路 2 中央处理器（CPU）能访问的最大存储器容量取决于（ A ） 。 A）地址总线 B）数据总线 C）控制总线 D）实际内存容量 11微型计算机中， （ C ）的存取速度最快。 A）高速缓存 B）外存储器 C）寄存器 D）内存储器 14一个向量第一个元素的存储地址是 100，每个元素的长度是 2，则地 5 个元素的地址是（ B ） 。 A）110 B）108 C）100 D）109 NOIP2003： 1. 图灵 (Alan Turing) 是 （ B ） 。 A） 美国人 B） 英国人 C） 德国人 D） 匈牙利人 E） 法国人 2. 第一个给计算机写程序的人是（ B ） 。 A） Alan Mathison Turing B） Ada Lovelace C） John von Neumann D） John Mc-Carthy E） Edsger Wybe Dijkstra 11. 下列分辨率的显示器显示出的图像，最清晰的是（ D ） 。 A） 800*600 B） 1024*768 C） 640*480 D） 1280*1024 E） 800*1000 12. 下列说法中，哪个（些）是错误的（ BDE ） 。 A）程序是指令的序列，它有三种结构：顺序、分支和循环。 B）数据总线决定了中央处理器 CPU 所能访问的最大内存空间的大小。 C）中央处理器 CPU 内部有寄存器组，用来储存数据。 D）不同厂家生产的 CPU 所能处理的指令集是相同的。 E）数据传输过程中可能会出错，奇偶校验法可以检测出数据中那一为在传输中出了差错。 17. 下列哪个（些）不是个人计算机的硬件组成部分（ B ） 。 A）主板 B）虚拟内存 C）电源 D）硬盘 E）总线 NOIP2004： 7.下面哪个部件对于个人桌面电脑的正常运行不是必需的（ C ） 。 A.CPU B. 图形卡（显卡） C. 光驱 D. 主板 E. 内存 11. 美籍匈牙利数学家冯诺依曼对计算机科学发展所做出的贡献包括（ BC ） 。 A.提出理想计算机的数学模型，成为计算机科学的理论基础。 B.提出存储程序工作原理，对现代电子计算机的发展产生深远影响。 C.设计出第一台具有存储程序功能的计算机 EDVAC。 ,. D.采用集成电路作为计算机的主要功能部件。 E.指出计算机性能将以每两年翻一番的速度向前发展。 12. 下列哪个（些）是 64 位处理器（ ACDE ） 。 A. Intel Itanium B. Intel Pentium III C. AMD Athlon64 D. AMD Opteron E. IBM Power 5 15. 下列哪个（些）不是计算机的存储设备（ AC ） 。 A. 文件管理器 B. 内存 C. 显卡 D. 硬盘 E. U 盘 18. 彩色显示器所显示的五彩斑斓的色彩，是由哪三色混合而成的（ ACD ） 。 A. 红 B. 白 C. 蓝 D. 绿 E. 橙 NOIP2005： 7. Intel 的首颗 64 位处理器是（ E ） 。 A. 8088 B. 8086 C. 80386 D. 80486 E. Pentium 18. 以下断电之后将不能保存数据的有（ BCDE ） 。 A. 硬盘 B. 寄存器 C. 显存 D. 内存 E. 高速缓存 20. 下列关于高级语言的说法正确的有（ BDE ） 。 A. Ada 是历史上的第一个高级语言 B. Pascal 和 C 都是编译执行的高级语言 C. C+是历史上的第一个支持面向对象的语言 D. 编译器将高级语言程序转变为目标代码 E. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 NOIP2006： 1. 在以下各项中。 （ E ）不是 CPU 的组成部分。 A. 控制器B. 运算器C. 寄存器D. ALU E. RAM 2. BIOS（基本输入输出系统）是一组固化在计算机内（ C ）上一个 ROM 芯片上的程序。 A. 控制器B. CPUC. 主板 D. 内存条E. 硬盘 18. 在下列关于计算机语言的说法中，正确的有（ AB ） 。 A. Pascal 和 C 都是编译执行的高级语言 B. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 C. C+是历史上的第一个支持面向对象的计算机语言 D. 高级语言比汇编语言更高级，是因为它的程序的运行效率更高 NOIP2007： 1. 在以下各项中。 （ D ）不是 CPU 的组成部分。 A. 控制器 B. 运算器 C. 寄存器 D. 主板 E. 算术逻辑单元(ALU) 3.在下列各项中，只有（ D ）不是计算机存储容量的常用单位。 A. Byte B. KB C. MB D. UB E. TB 4ASCII 码的含义是（ B ） 。 A. 二十进制转换码 B. 美国信息交换标准代码 C. 数字的二进制数码 D. 计算机可处理字符的唯一编码 E. 常用字符的二进制编码 20. 近 20 年来， 许多计算机专家都大力推崇递归算法，认为它是解决较复杂问题的强有力的工具. 在下列关 于递归的说法中， 正确的是（ AC ） 。 A. 在 1977 年前后形成标准的计算机高级语言"FORTRAN77"禁止在程序使用递归， 原因之一是该方法可 能会占用更多的内存空间. B. 和非递归算法相比， 解决同一个问题， 递归算法一般运行得更快一些 C. 对于较复杂的问题， 用递归方式编程往往比非递归方式更容易一些 D. 对于已定义好的标准数学函数 sin(x)， 应用程序中的语句“y=sin(sin(x);”就是一种递归调用 NOIP2008： ,. 1. 在以下各项中， （ C ）不是操作系统软件。 A. Solaris B. Linux C. Sybase D. Windows Vista E. Symbian 11. 在下列关于图灵奖的说法中，正确的有（ ABD ） 。 A. 图灵奖是美国计算机协会于 1966 年设立的，专门奖励那些对计算机事业作出重要贡献的个人 B. 图灵奖有“计算机界诺贝尔奖”之称 C. 迄今为止，还没有华裔计算机科学家获此殊荣 D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰图灵 NOIP2009： 2、关于 BIOS 下面的说法哪个是正确的：A A)BIOS 是计算机基本输入输出系统软件的简称。 B)BIOS 里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。 C)BIOS 一般由操作系统厂商来开发完成。 D)BIOS 能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。 3、已知大写字母 A 的 ASCII 编码为 65（十进制） ，则大写字母 J 的 十六进制 ASCII 编码为：D A) 48 B) 49 C) 50 D) 以上都不是 类型类型 2 2：操作系统与应用软件：操作系统与应用软件： NOIP1999： 10、计算机的软件系统通常分为 （ A ） A. 系统软件与应用软件 B. 高级软件与一般软件 C. 军用软件与民用软件 D. 管理软件与控制软件 NOIP2000： 4.计算机病毒的特点是（ C ） A. 传播性、潜伏性、易读性与隐蔽性 B. 破坏性、传播性、潜伏性与安全性 C. 传播性、潜伏性、破坏性与隐蔽性 D. 传播性、潜伏性、破坏性与易读性 5.WINDOWS 9X 是一种（ D ）操作系统 A. 单任务字符方式 B. 单任务图形方式 C. 多任务字符方式 D. 多任务图形方式 7.计算机网络是一个（ D ）系统 A.管理信息系统 B.管理数据系统 C.编译系统 D. 在协议控制下的多机互连系统 NOIP2001： 4、在树型目录结构中，不允许两个文件名相同主要指的是( D ) A)同一个磁盘的不同目录下 B)不同磁盘的同一个目录下 C)不同磁盘的不同目录下 C)同一个磁盘的同一个目录下 10、以下对 Windows 的叙述中，正确的是( A ) A)从软盘上删除的文件和文件夹，不送到回收站 B)在同一个文件夹中，可以创建两个同类、同名的文件 C)删除了某个应用程序的快捷方式，将删除该应用程序对应的文件 D)不能打开两个写字板应用程序 NOIP2002： 7 计算机病毒传染的必要条件是：（ B ） 。 A）在内存中运行病毒程序 B）对磁盘进行读写操作 C）在内存中运行含有病毒的可执行的程序 D）复制文件 8 在磁盘上建立子目录有许多优点，下列描述中不属于建立子目录优点的是（ D ） 。 A）便于文件管理 B）解决根目录中目录项个数有限问题 C）加快文件查找速度 D）节省磁盘使用空间 12资源管理器的目录前图标中增加“+”号，这个符号的意思是（ B ） 。 ,. A）该目录下的子目录已经展开 B）该目录下还有子目录未展开 C）该目录下没有子目录 D）该目录为空目录 13在 WORD 文档编辑中实现图文混合排版时，关于文本框的下列叙述正确的是（ C ） 。 A）文本框中的图形没有办法和文档中输入文字叠加在一起，只能在文档的不同位置 B）文本框中的图形不可以衬于文档中输入的文字的下方 C）通过文本框，可以实现图形和文档中输入的文字的叠加，也可以实现文字环绕 D）将图形放入文本框后，文档中输入的文字不能环绕图形 NOIP2004： 14. 下列哪个（些）不是数据库软件的名称（ D ） 。 A. MySQL B. SQL Server C. Oracle D. Outlook E. Foxpro 16. 下列哪个（些）软件属于操作系统软件（ BE ） 。 A. Microsoft Word B. Windows XP C. Foxmail D. 金山影霸 E. Red Hat Linux 19. 下列哪个（些）程序设计语言支持面向对象程序设计方法（ ABDE ） 。 A. C+ B. Object Pascal C. C D. Smalltalk E. Java NOIP2006： 15. 下列外设接口中可以通过无线连接的方式连接设备的是（ ABCD ） 。 A. USB 2.0 高速版 B. 红外 C. 蓝牙 D. 串口 E. IEEE 802.11g 无线网卡 类型类型 3 3：多媒体与网络：多媒体与网络： NOIP2000： 11.下面哪些计算机网络不是按覆盖地域划分的（ A ） A.局域网 B. 都市网 C.广域网 D. 星型网 NOIP2001： 12、TCP/IP 协议共有( C )层协议 A)3 B)4 C)5 D)6 NOIP2002： 9 在使用 E-mail 前，需要对 Outlook 进行设置，其中 ISP 接收电子邮件的服务器称为（ A ）服务器。 A）POP3 B）SMTP C）DNS D）FTP 10多媒体计算机是指（ D ）计算机。 A）专供家庭使用的 B）装有 CD-ROM 的 NOIP2004： 8.下列哪个网络上常用的名字缩写是错误的（ D ） 。 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） 。 10. 一台计算机如果要利用电话线上网，就必须配置能够对数字信号和模拟信号进行相互转换的设备，这种设 备是（ A ） 。 A. 调制解调器 B. 路由器 C. 网卡 D. 网关 E. 网桥 NOIP2005： 8. 常见的邮件传输服务器使用（ B ）协议发送邮件。 A. HTTP B. SMTP C. TCP D. FTP E. POP3 9. 不能在 Linux 上使用的网页浏览器是（ A ） 。 A. Internet Explore B. Netscape C. Opera D. Firefox E. Mozilla NOIP2008： ,. 14Web2.0 是近年来互联网的热门概念之一，其核心思想是互动与分享。下列网站中， （ B ）是典型的 Web2.0 应用。 A. Sina B. Flickr C. Yahoo D. Google 4、关于计算机网络，下面的说法哪些是正确的：C A)网络协议之所以有很多层主要是由于新技术需要兼容过去老的实现方案。 B)新一代互联网使用的 IPv6 标准是 IPv5 标准的升级与补充。 C)TCP/IP 是互联网的基础协议簇，包含有 TCP 和 IP 等网络与传输层的通讯协议。 D)互联网上每一台入网主机通常都需要使用一个唯一的 IP 地址，否则就必须注册一个固定的域名来标 明其地址。 5、关于 HTML 下面哪些说法是正确的：BD A)HTML 全称超文本标记语言，实现了文本、图形、声音乃至视频信息的统一编码。 B)HTML 不单包含有网页内容信息的描述，同时也包含对网页格式信息的定义。 C)网页上的超链接只能指向外部的网络资源，本网站网页间的联系通过设置标签来实现。 D)点击网页上的超链接从本质上就是按照该链接所隐含的统一资源定位符（URL）请求网络资源或网络 服务。 类型类型 4 4：数据结构与算法：数据结构与算法： NOIP2000： 12.在有 N 个叶子节点的哈夫曼树中，其节点总数为（ B ） A.不确定 B. 2N-1 C. 2N+1 D. 2N 解法一解法一: 设叶子节点个数为 n，度为 1 的节点个数为 m，度为 2 的节点个数为 l. 显然易知：一颗二叉树的节点数 这个树的度加 1（因为每个节点都是前一个节点的度，根节点除外， 所以要加 1） 故有 l + m + n = 2l + m + 1 -> n = l + 1 由于哈夫曼树没有度为 1 的节点，在 m 0 总节点 n m l 2n 1 解法二解法二: 第 1 次必定是 2 个叶子组成二叉树，产生 1 新结点，接下来有 2 种情况： 1.此新结点与原剩下的叶子再组成二叉树又产生 1 新结点，这样就只有第 1 次时由 2 个叶子产生 1 新结点， 以后每次由 1 叶子与新结点产生新结点，故 n 个叶子共有 2n-1 个结点。 2.剩下的叶子中又有 2 个叶子(比第 1 次产生的新结点权小)结合产生新结点，其它类似，那么必然会由 2 个都是新结点再产生新结点，所以实际上数量与第 1 种一样，共有 2n-1 个。 具体证明用一个构造哈夫曼树的算法。 13.已知数组中 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 15.某数列有 1000 个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索（binary-search） ，在 最坏的情况下，需检视（ B ）个单元。 A.1000 B. 10 C. 100 D. 500 NOIP2001： 13.若已知一个栈的入栈顺序是 1，2，3，n，其输出序列为 P1，P2，P3，Pn，若 P1 是 n，则 Pi 是(C) A)i B)n-1 C)n-i+1 D)不确定 15.下面关于算法的错误说法是( B ) A)算法必须有输出 B)算法必须在计算机上用某种语言实现 ,. C)算法不一定有输入 D)算法必须在有限步执行后能结束 17.以下哪一个不是栈的基本运算( B) A)删除栈顶元素 B)删除栈底的元素 C)判断栈是否为空 D)将栈置为空栈 18.在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找 12，所需的关键码比较的次数为( C) A)2 B)3 C)4 D)5 19.一棵二叉树的高度为 h，所有结点的度为 0，或为 2，则此树最少有( B)个结点 A)2h-1 B)2h-1 C)2h+1 D)h+1 20.无向图 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) 对该图进行深度优先遍历,得到的顶点序列正确的是(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 NOIP2002： 17按照二叉数的定义，具有 3 个结点的二叉树有（ C ）种。 A）3 B）4 C）5 D）6 18在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。 A） 1/2 B）1 C）2 D）4 解析: 在有向图的邻接表中，从一顶点出发的弧链接在同一链表中，邻接表中结点的个数恰为图中弧的数 目，所以顶点入度之和为弧数和的一倍，若为无向图，同一条边有两个结点，分别出现在和它相关的两 个顶点的链表中，因此无向图的邻接表中结点个数的边数的 2 倍 19要使 1 8 号格字的访问顺序为：8、2、6、5、7、3、1、4，则下图中的空格中应填入（ C ） 。 12345678 461-1732 A）6 B）0 C）5 D）3 NOIP2003： 5. 一个高度为 h 的二叉树最小元素数目是（ B ） 。 A） 2h+1 B） h C） 2h-1 D） 2h E） 2h-1 6. 已知队列（13，2，11，34，41，77，5，7，18，26，15） ，第一个进入队列的元素是 13，则第五个出队列 的元素是（ B ） 。 A） 5 B） 41 C） 77 D） 13 E） 18 19. 已知元素（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，8，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 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 NOIP2004： 3.某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时 刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出” 。假设车辆入站的顺序为 1，2，3，则车辆出站的顺序为（ E ） 。 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 ,. 4.满二叉树的叶结点个数为 N，则它的结点总数为（ C ） 。 A. N B. 2 * N C. 2 * N 1 D. 2 * N + 1 E. 2N 1 5.二叉树 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 20. 某大学计算机专业的必修课及其先修课程如下表所示： 课程代号C0C1C2C3C4C5C6C7 课程名称高等数学程序设计语言离散数学数据结构编译技术操作系统普通物理计算机原理 先修课程C0, C1C1, C2C3C3, C7C0C6 请你判断下列课程安排方案哪个（些）是合理的（ BCE ） 。 A. C0, C1, C2, C3, C4, C5, C6, C7 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 NOIP2005： 4. 完全二叉树的结点个数为 4 * N + 3，则它的叶结点个数为（ E ） 。 A. 2 * N B. 2 * N - 1 C. 2 * N + 1 D. 2 * N - 2 E. 2 * N + 2 5. 平面上有五个点 A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以这五点作为完全图 G 的顶点， 每两点之间的直线距离是图 G 中对应边的权值。图 G 的最小生成树中的所有边的权值 综合为（ D ） 。 A. 8 B. 7+ 5 C. 9 D. 6+ 5 E. 4+2 2 + 5 13. 二叉树 T 的宽度优先遍历序列为 A B C D E F G H I，已知 A 是 C 的父结点，D 是 G 的 父结点，F 是 I 的父结点，树中所有结点的最大深度为 3（根结点深度设为 0） ，可知 E 的父结点可能是（ BC ） 。 A. A B. B C. C D. D E. F 14. 设栈 S 的初始状态为空，元素 a, b, c, d, e, f, g 依次入栈，以下出栈序列不可能出现的有 （ CE ） 。 A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, c, b, d, f, g D. d, c, f, e, b, a, g E. g, e, f, d, c, b, a NOIP2006： 4在编程时（使用任一种高级语言，不一定是 Pascal） ，如果需要从磁盘文件中输入一个很大的二维 数组（例如 1000*1000 的 double 型数组） ，按行读（即外层循环是关于行的）与按列读（即外层循 环是关 于列的）相比，在输入效率上（ E ） 。 A. 没有区别 B. 有一些区别，但机器处理速度很快，可忽略不计 C. 按行读的方式要高一些 D. 按列读的方式要高一些 E. 取决于数组的存储方式。 7某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从 这一时 刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出” 。假设车辆入站的 顺序为 1，2，3，则车辆出站的顺序为（ C ） 。 A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2 E. 1, 4, 3, 7, 5 8高度为 n 的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为 n-1 的满二叉树。 在这里，树高等于叶结点的最大深度，根结点的深度为 0，如果某个均衡的二叉树共有 2381 个结点， 则该 树的树高为（ B ） 。 A. 10B. 11C. 12D. 13E. 210 1 解析: 均衡二叉树就是：任意两个度不为 2 的节点的深度之差不大于 1 例如： ,. 1 / 2 3 / 4 5 是均衡二叉树 而 1 / 2 3 / 4 5 6 / 7 就不是，2 和 7 的深度差 2. 因为 211 = 2048；所以一颗满二叉树从深度为 0（根节点）到深度 10 的总节点数是 2047，剩下 2381- 2047 = 334 个节点，这剩下的节点的深度都是 11。 所以答案为 B 10将 5 个数的序列排序，不论原先的顺序如何，最少都可以通过（ B ）次比较，完成从小到大的排序。 A. 6 B. 7 C. 8 D. 9 E. 10 13. 设栈 S 的初始状态为空，元素 a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（ C ） 。 A. a, b, c, e, d B. b, c, a, e, d C. a, e, c, b, d D. d, c, e, b, a 14. 已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6（数字为结点的编号，以下同） ，后根遍历是 3 2 5 6 4 1，则该二叉树的可能的中根遍历是（ BC ） A. 3