Noip初赛复习的指南.题目分类解析.doc

《Noip初赛复习的指南.题目分类解析.doc》由会员分享，可在线阅读，更多相关《Noip初赛复习的指南.题目分类解析.doc（32页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、NOIP初赛复习指By.Snowpole 2010-10-1初赛考的知识点就是计算机基本常识、基本操作和程序设计基础知识。其中选择题考查的是知识，而问题解决类型的题目更加重视能力的考查。一般说来，选择题只要多用心积累就可以了。问题解决题目的模式比较固定，大家应当做做以前的题目。写运行结果和程序填空也需要多做题目，并且培养良好的程序阅读和分析能力，就像语文的阅读理解一样。近几年来，初赛的考查围有了很大的变化，越来越紧跟潮流了。这就需要大家有比较广泛的知识，包括计算机硬件、软件、网络、简单的数据结构（例如栈、队列、树和图等）和简单的算法（例如排序、查找和搜索等），程序设计语言以及一些基本的数学知识

2、和技巧。知识点复习：第一部分 计算机基础知识红旗中学网站U32?g6IvCL1.计算机的发展h.i%sL4Jk t.Z0知识点:1.计算机的发展阶段(4代,标志及主要特点)红旗中学网站4Aoj3qW 2.ENIAC,图灵,.诺依曼,Ada Lovelace(第一个程序员)红旗中学网站;n)HyC4Z x V(e2.计算机系统红旗中学网站E g ee9i27|(v1.计算机硬件C7M2H9EF2K-?0a.组成:运算器,控制器,存储器,IO设备;红旗中学网站i?,J&Y Xqb.CPU:字长,主频(时钟频率),总线;红旗中学网站hquMH$KY Rc.存储器:(ROM,RAM),外存储器,种类,

3、单位,存取速度;红旗中学网站 R5tSZz ,Jd.输入输出设备:扫描仪,数字化仪,绘图仪,打印机(种类)W5?2cEnx02.计算机软件:红旗中学网站!t95Uy$r_5Ya. BIOS (功能);红旗中学网站 f8kqDsVi:b.系统软件(包括操作系统:DOS,LINUX,UNIX,WINDOWS,OS/2,MAC/OS和语言的解释或编译程序);红旗中学网站i$*W7B2r m+m g:v(R解释程序:高级语言翻译的一种,它将源语言(如basic)书写的源程序作为输入,解释一句后就提交计算机执行一句,并不形成目标程序.红旗中学网站?Nf#k翻译程序: (编译程序)一类很重要的语言处理程序

4、,它把高级语言(如FORTRAN,COBOL,pascal,c等)源程序作为输入,进行翻译转换,产生出机器语言的目标程序,然后再让计算机去执行这个目标程序,得到计算结果.红旗中学网站 T*y9oC.G-B语言:机器语言 汇编语言 高级语言(面向对象,面向过程)红旗中学网站+ZdONV9P(MJMc.应用软件红旗中学网站bO B&Y;p ?E# wp数据库管理软件:Foxpro，Access，Orale，Sybase，DB2和Informix等。字处理软件: WPS, word3.计算机的主要性能指标红旗中学网站co.(0K1.字长红旗中学网站S)eg!E$z:s2.速度3.存储系统容量(bit

5、,B,KB,MB,GB,TB)红旗中学网站4cj33u LJ6j$q3. 数据在计算机中的表示红旗中学网站,s(0Nj O$?1.数值的表示:二进制,八进制,十六进制,十进制(包括小数部分的转化)红旗中学网站O0Dx p y-B原码,反码,补码的表示红旗中学网站9vZ T Bealn2.字符的表示: ASCII码(128个)红旗中学网站p2eo5q%sC)R+WV0-48 A-65 a-97红旗中学网站?!fU,_X0j 汉字的表示: 2个字节(Byte) :机码,输入码,字型码3.图像的表示4.声音的表示红旗中学网站I2/ZU8G w6A w0s6o4.计算机的维护与使用安全1. 计算机的维

6、护与安全使用常识红旗中学网站B l ;p,w(电源,温度,湿度,开关机)红旗中学网站aeqz.x7q2. 计算机病毒的预防与消除红旗中学网站+WNcOl0(何谓病毒,病毒的特点,杀毒方式及软件)第二部分 计算机网络1.计算机网络的定义:红旗中学网站!Xk s b e 计算机网络，就是把分布在不同地理区域的计算机与专门的外部设备用通信线路互连成一个规模大、功能强的网络系统，从而使众多的计算机可以方便地互相传递信息，共享信息资源。红旗中学网站4C&UP7KPT*$k$s2.计算机网络名词: 红旗中学网站&q)G%I9g,aD(YpISP: 因特网服务提供商,能提供拨号上网服务、网上浏览、下载文件、

7、收发电子等服务。即为用户提供Internet接人和(或)Internet信息服务的公司和机构。如”中国电信”等;DNS: 域名服务器;红旗中学网站0cqa!O,RpFTP: 文件传输协议;红旗中学网站3n i v$OY!qLk8EHTTP:超文本传输协议;SMTP:简单系统传输协议;红旗中学网站Y9miG$IZzWWW: 万维网;POP3: 传输协议红旗中学网站 c BjgARP: 地址解析协议红旗中学网站/K C rX |3.两种网络参考模型红旗中学网站_5a: ?Kn%rjOSI开放式系统互联模型参考模型: (七层)J1Wo YF2gjA.R#由下到上:物理层、数据链路层、网络层、传输层、

8、会话层、表示层、应用层；wR;mM!g ASi3n0 TCP/IP参考模型(五层)Z|:JT$N_#由下到上:、物理层、数据链路层，互联网层、传输层、应用层红旗中学网站 S0G+S:a8jHD4.网络软件7U* X-g+Vy V01.计算机协议: (TCP/IP)红旗中学网站1A+Wf/G aqaD |Sa.TCP : Transfer Control Protocol,传输控制协议红旗中学网站rB2A2k|Hb.IP: Internet Protocol,网际协议红旗中学网站$C(|w t9A nng9pzc.三类IP地址: IPV4| m$I s5V(r#ze02.应用软件:红旗中学网站N

9、(Nt|红旗中学网站(fu.?0r%IT|8e5.网络硬件5QLS!r(网卡, MODEM,光纤,双绞线,同轴电缆,无线信道)红旗中学网站 y7hG9juY. L,Cr红旗中学网站N&X ;?7&N _ n0R6.网络分类%R(y NM2?6my0 计算机网络的类型有很多，而且有不同的分类依据。4i3)vt ?0 按拓扑结构:总线型、星型、环形、树形红旗中学网站y6n%#uAI 按地域:局域网、城域网、广域网和网间网5RU3D_7.域名的表示 红旗中学网站;I,X8p9JgQ2hyF红旗中学网站m;(h:I *HX第三部分 数据结构红旗中学网站q r-SnpH C1.简单数据类型:a数值: i

10、nteger, real, longint红旗中学网站3mC(8r;.KCb字符: char红旗中学网站jWBv:t_ti7w.pc布尔类型: Boolean红旗中学网站A.#|,l5z2Id数组:一维,二维红旗中学网站j6W e jA;u7k0Ke字符串: stringzE yz(z102.线性表红旗中学网站*S isC?5cYT3?l栈、队列3.树二叉树、哈弗曼树4.图图的最小生成树、最短路径第四部分 基本及常用算法红旗中学网站%a e Lq-F第五部分 问题求解队列、栈、二叉树等数据结构、数学问题、归纳法、数列和逻辑推理、排列组合等题型归类：第一部分：选择题（30分=20*1.5）一般是

11、比较容易得分的，不可错过！程序设计方面的知识多是平时计算机课堂教学或课外活动中学到的，建议大家找全国计算机等级考试（一、二级）的题目做做，一般不超过二级的知识点，知识要复习的系统一些。新大纲和最近两年的考试不再考DOS，但有DOS经验的选手可能会占一点便宜，因为有些题目可以根据经验判断。另外，往更高层次发展的过程中，必要的DOS知识和命令还是必须的。类型1：计算机原理：NOIP1999：1、微机的存储器的地址是以( C )编址的。A. 二进制位 B. 字长 C. 字节 D. 微处理器的型号2、下列诸因素中,对微机工作影响最小的是 ( B )A. 尘土 B. 噪声 C. 温度 D. 湿度3、在2

12、4*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

13、. 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

14、. 副教授、教授、讲师 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.不同类

15、型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢的排列是（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）

16、电子管电路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）109NOIP2003：1. 图灵 (Alan Turing) 是 （ B ）。 A） 美国人 B） 英国人 C） 德国人 D） 匈牙利人 E） 法国人2. 第一个给计算机写程序的人是（ B ）。 A） Alan Mathison Turin

17、g B） Ada Lovelace C） John von Neumann D） John Mc-Carthy E） Edsger Wybe Dijkstra11. 下列分辨率的显示器显示出的图像，最清晰的是（ D ）。 A） 800*600 B） 1024*768 C） 640*480 D） 1280*1024 E） 800*100012. 下列说法中，哪个（些）是错误的（ BDE ）。 A）程序是指令的序列，它有三种结构：顺序、分支和循环。 B）数据总线决定了中央处理器CPU所能访问的最大存空间的大小。 C）中央处理器CPU部有寄存器组，用来储存数据。 D）不同厂家生产的CPU所能处理的指

18、令集是相同的。 E）数据传输过程中可能会出错，奇偶校验法可以检测出数据中那一为在传输中出了差错。17. 下列哪个（些）不是个人计算机的硬件组成部分（ B ）。 A）主板 B）虚拟存 C）电源 D）硬盘 E）总线NOIP2004：7.下面哪个部件对于个人桌面电脑的正常运行不是必需的（ C ）。A.CPU B. 图形卡（显卡） C. 光驱 D. 主板 E. 存11.美籍匈牙利数学家诺依曼对计算机科学发展所做出的贡献包括（ BC ）。A.提出理想计算机的数学模型，成为计算机科学的理论基础。B.提出存储程序工作原理，对现代电子计算机的发展产生深远影响。C.设计出第一台具有存储程序功能的计算机EDVAC

19、。D.采用集成电路作为计算机的主要功能部件。E.指出计算机性能将以每两年翻一番的速度向前发展。12.下列哪个（些）是64位处理器（ ACDE ）。A. Intel Itanium B. Intel Pentium III C. AMD Athlon64D. AMD Opteron E. IBM Power 515.下列哪个（些）不是计算机的存储设备（ AC ）。A. 文件管理器 B. 存 C. 显卡 D. 硬盘 E. U盘18.彩色显示器所显示的五彩斑斓的色彩，是由哪三色混合而成的（ ACD ）。A. 红 B. 白 C. 蓝 D. 绿 E. 橙NOIP2005：7. Intel的首颗64 位处

20、理器是（ E ）。A. 8088 B. 8086 C. 80386 D. 80486 E. Pentium18. 以下断电之后将不能保存数据的有（ BCDE ）。A. 硬盘B. 寄存器C. 显存D. 存E. 高速缓存20. 下列关于高级语言的说确的有（ BDE ）。A. Ada 是历史上的第一个高级语言B. Pascal和C都是编译执行的高级语言C. C+是历史上的第一个支持面向对象的语言D. 编译器将高级语言程序转变为目标代码E. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上NOIP2006：1. 在以下各项中。（ E ）不是 CPU 的组成部分。A. 控制器B. 运算器

21、C. 寄存器D. ALUE. RAM2. 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.

22、 算术逻辑单元(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禁止在程序使用递归， 原因之一是该方法可能会占用更多的存空间.

23、B. 和非递归算法相比， 解决同一个问题， 递归算法一般运行得更快一些 C. 对于较复杂的问题， 用递归方式编程往往比非递归方式更容易一些 D. 对于已定义好的标准数学函数sin(x)， 应用程序中的语句“y=sin(sin(x);”就是一种递归调用NOIP2008：1. 在以下各项中，（ C ）不是操作系统软件。A. Solaris B. Linux C. Sybase D. Windows Vista E. Symbian11. 在下列关于图灵奖的说法中，正确的有（ ABD ）。A. 图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人B. 图灵奖有“计算机

24、界诺贝尔奖”之称C. 迄今为止，还没有华裔计算机科学家获此殊荣D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰图灵NOIP2009：2、关于BIOS下面的说法哪个是正确的：AA)BIOS是计算机基本输入输出系统软件的简称。B)BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。C)BIOS一般由操作系统厂商来开发完成。D)BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。3、已知大写字母A的ASCII编码为65（十进制），则大写字母J的 十六进制 ASCII编码为：DA) 48 B) 49 C) 50 D) 以上都不是类型2：操作系统与应用软件：N

25、OIP1999：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：

26、4、在树型目录结构中，不允许两个文件名相同主要指的是( D )A)同一个磁盘的不同目录下 B)不同磁盘的同一个目录下C)不同磁盘的不同目录下 C)同一个磁盘的同一个目录下10、以下对Windows的叙述中，正确的是( A )A)从软盘上删除的文件和文件夹，不送到回收站B)在同一个文件夹中，可以创建两个同类、同名的文件C)删除了某个应用程序的快捷方式，将删除该应用程序对应的文件D)不能打开两个写字板应用程序NOIP2002：7 计算机病毒传染的必要条件是：（ B ）。 A）在存中运行病毒程序 B）对磁盘进行读写操作C）在存中运行含有病毒的可执行的程序 D）复制文件8 在磁盘上建立子目录有许多优点

27、，下列描述中不属于建立子目录优点的是（ D ）。 A）便于文件管理 B）解决根目录中目录项个数有限问题C）加快文件查找速度 D）节省磁盘使用空间12资源管理器的目录前图标中增加“+”号，这个符号的意思是（ B ）。A）该目录下的子目录已经展开 B）该目录下还有子目录未展开C）该目录下没有子目录 D）该目录为空目录13在WORD文档编辑中实现图文混合排版时，关于文本框的下列叙述正确的是（ C ）。A）文本框中的图形没有办法和文档中输入文字叠加在一起，只能在文档的不同位置B）文本框中的图形不可以衬于文档中输入的文字的下方C）通过文本框，可以实现图形和文档中输入的文字的叠加，也可以实现文字环绕D）将

28、图形放入文本框后，文档中输入的文字不能环绕图形NOIP2004：14.下列哪个（些）不是数据库软件的名称（ D ）。A. MySQL B. SQL Server C. Oracle D. Outlook E. Foxpro16.下列哪个（些）软件属于操作系统软件（ BE ）。A. Microsoft Word B. Windows XP C. Foxmail D. 金山影霸 E. Red Hat Linux19.下列哪个（些）程序设计语言支持面向对象程序设计方法（ ABDE ）。A. C+ B. Object Pascal C. C D. Smalltalk E. JavaNOIP2006：1

29、5. 下列外设接口中可以通过无线连接的方式连接设备的是（ ABCD ）。A. USB 2.0 高速版B. 红外C. 蓝牙D. 串口E. IEEE 802.11g 无线网卡类型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）FTP10多媒体计算机是指（ D ）

30、计算机。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. 网桥NOI

31、P2005：8. 常见的传输服务器使用（ B ）协议发送。A. HTTP B. SMTP C. TCP D. FTP E. POP39. 不能在Linux 上使用的网页浏览器是（ A ）。A. Internet Explore B. Netscape C. Opera D. Firefox E. MozillaNOIP2008：14Web2.0是近年来互联网的热门概念之一，其核心思想是互动与分享。下列中，（ B ）是典型的Web2.0应用。 A. Sina B. Flickr C. Yahoo D. Google4、关于计算机网络，下面的说法哪些是正确的：CA)网络协议之所以有很多层主要是由于

32、新技术需要兼容过去老的实现方案。B)新一代互联网使用的IPv6标准是IPv5标准的升级与补充。C)TCP/IP是互联网的基础协议簇，包含有TCP和IP等网络与传输层的通讯协议。D)互联网上每一台入网主机通常都需要使用一个唯一的IP地址，否则就必须注册一个固定的域名来标明其地址。5、关于HTML下面哪些说法是正确的：BDA)HTML全称超文本标记语言，实现了文本、图形、声音乃至视频信息的统一编码。B)HTML不单包含有网页容信息的描述，同时也包含对网页格式信息的定义。C)网页上的超只能指向外部的网络资源，本网页间的联系通过设置标签来实现。D)点击网页上的超从本质上就是按照该所隐含的统一资源定位符

33、（URL）请求网络资源或网络服务。类型4：数据结构与算法：NOIP2000：12.在有N个叶子节点的哈夫曼树中，其节点总数为（B）A.不确定B. 2N-1C. 2N+1D. 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.此新结点与原剩下的叶子再组成

34、二叉树又产生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+141B. SA+180C. SA+222D. SA+22515.某数列有100

35、0个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索（binary-search），在最坏的情况下，需检视（B）个单元。A.1000B. 10C. 100D. 500NOIP2001：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)判断栈是否为空

36、D)将栈置为空栈18.在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的关键码比较的次数为( C)A)2 B)3 C)4 D)519.一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有( B)个结点A)2h-1 B)2h-1 C)2h+1 D)h+120.无向图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,fB)a,c,f,e,b,dC)a,e,b,c,f,dD)a,b,

37、e,d,f,cNOIP2002：17按照二叉数的定义，具有3个结点的二叉树有（ C ）种。 A）3 B）4 C）5 D）618在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。A） 1/2 B）1 C）2 D）4解析: 在有向图的邻接表中，从一顶点出发的弧在同一链表中，邻接表中结点的个数恰为图中弧的数目，所以顶点入度之和为弧数和的一倍，若为无向图，同一条边有两个结点，分别出现在和它相关的两个顶点的链表中，因此无向图的邻接表中结点个数的边数的2倍19要使1 8号格字的访问顺序为：8、2、6、5、7、3、1、4，则下图中的空格中应填入（ C ）。12345678461-173

38、2A）6 B）0 C）5 D）3NOIP2003：5. 一个高度为h 的二叉树最小元素数目是（ B ）。 A） 2h+1 B） h C） 2h-1 D） 2h E） 2h-16. 已知队列（13，2，11，34，41，77，5，7，18，26，15），第一个进入队列的元素是13，则第五个出队列的元素是（ B ）。 A） 5 B） 41 C） 77 D） 13 E） 1819. 已知元素（8，25，14，87，51，90，6，19，20），问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足：8在51前面；90在87的后面；20在14的后面；25在6的前面；19在90的后面。（ D ）。 A）20

39、，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，2020. 假设我们用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，2NOIP2004：3.某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为

40、空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”。假设车辆入站的顺序为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, 74.满二叉树的叶结点个数为N，则它的结点总数为（ C ）。A. N B. 2 * N C. 2 * N 1 D. 2 * N + 1 E. 2N 15.二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为（ B ）。A.

41、 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 120.某大学计算机专业的必修课及其先修课程如下表所示：课程代号C0C1C2C3C4C5C6C7课程名称高等数学程序设计语言离散数学数据结构编译技术操作系统普通物理计算机原理先修课程C0, C1C1, C2C3C3, C7C0C6请你判断下列课程安排方案哪个（些）是合理的（ BCE ）。A. C0, C1, C2, C3, C4, C5, C6, C7 B. C0, C1, C2, C3, C4, C6, C7, C5C. C0, C1, C6, C7, C2, C3, C4, C5 D. C0, C1, C6, C7, C5, C2, C3, C4E. C0, C1, C2, C3, C6, C7, C5, C4NOIP2005：4. 完全二叉树的结点个数为4 * N + 3，则它的叶结点个数为（ E ）。A. 2 * N B. 2 * N - 1 C. 2 * N + 1 D. 2 * N - 2 E. 2 * N + 25. 平面上有五个点A(5, 3), B(3, 5), C(2,