当前位置:首页 >> 初中教育 >>

noip复习资料!!!


关于联赛及初赛的有关知识内容: 联赛分两个年龄组:初中组和高中组。每组竞赛分两轮:初试和复 试。 .初试形式为笔试,侧重考察学生的计算机基础知识和编程的基本 能力,并对知识面的广度进行测试。程序设计的描述语言采用Pascal。 各省市初试成绩在本赛区前百分之十五的学生进入复赛,其分数不 计入复赛的成绩。初赛时间为10月的的第3个星期六举行。(具体日 期可到www.noi.cn查阅

) .复试形式为上机,侧重考察学生对问题的分析理解能力,数学抽 象能力,驾驭编程语言的能力和编程技巧、想象力和创造性等。程 序设计语言可采用 Pascal、C/C++或Java。各省市竞赛的等第奖在复试 的优胜者中产生。时间为 3 小时。只进行一试,在11 月的第3个星期 六进行。 试题形式 每次联赛的试题分四组:初中组初试赛题;初中组复试赛题; 高中组初试赛题;高中组复试赛题。其中,初中组初试赛题和高中 组初试赛题类型相同,初中组复试赛题和高中组复试赛题类型相同, 但初中组和高中组的题目不完全相同,高中组难度略高;以体现年 龄特点和层次要求。

.初试:初试全部为笔试,满分100分。试题由四部分组成: 1、选择题:共20题,每题1.5分,共30分。每题有5个备选方案;前10个题为单 选题,每题有且只有一个正确答案),后 10题为复选题(即每题有1至5个正确答案, 只有全部选对才得分)。试题内容包括计算机基本组成与原理、计算机基本操作、 信息科技与人类社会发展的关系等等。 2、问题求解题:共2题,每题5分,共10分。试题给出一个叙述较为简单的问 题,要求学生对问题进行分析,找到一个合适的算法,并推算出问题的解。答案 以字符串方式给出,考生给出的答案与标准答案的字符串相同,则得分;否则不 得分。 3、程序阅读理解题:共4题,每题8分,共32分。题目给出一段程序(没有关 于程序功能的说明),有时也会给出程序的输入,要求考生通过阅读理解该段程 序给出程序的输出。输出以字符串的形式给出,如果与标准答案一致,则得分; 否则不得分。 4、程序完善题:共 2题,每题 14分,共 28分。题目给出一段关于程序功能的 文字说明,然后给出一段程序代码,在代码中略去了若干个语句并在这些位臵给 出空格,要求考生根据程序的功能说明和代码的上下文,填出被略去的语句。填 对的,则得分;否则不得分。 .复试:复试的题型和形式向全国信息学奥赛(NOI)靠拢,全部为上机编程题, 但难度略低。复试为决出竞赛成绩的最后一个环节。题目包括 4道题,每题 100分, 共计 400分。难度有易有难,既考虑普及面,又考虑选拔的梯度要求。每一道试题 包括:题目、问题描述、样例说明(输入、输出及必要的说明)。测试时,测试 程序为每道题提供了十组测试数据,考生程序每答对一组得10 分;累计分即为该 道题的得分。

1988年4月《科学美国人》刊登了一篇文章,声称:考古学家发现 了使用绳索和滑轮构造的第一代数字计算机。这篇文章详细介绍了 Aprahulians的古人如何使用滑轮和绳索来建造复杂的设备。这些 设备装在一个巨大的黑色的木箱中,它们可以用来处理复杂的计 算。有一些设备非常巨大,以至于要使用大象来牵引以获得必须的 动力。 使用绳索和滑轮能够构造计算机吗?或许你已经猜到了,这只不过 是愚人节的笑话。^-^如果一台这样的设备,可以称为数字计算机 的话,你也可以使用其他的方法来构造计算机了。 现在将向你介绍现代计算机系统的概貌,你将会认识计算机的基本 概念。 计算机基础包括: ?电子计算机硬件与软件。 ?网络基础。 ?数据结构基础。

第一部分 一、计算机硬件与软件 ?电子计算机是一种数字化的信息处理设备。 ?世界上第一台电子计算机(ENIAC)于1946年诞生于美国。 ?电子计算机从诞生至今发展经历的四代:电子管、晶体管(20世纪 50年代)、集成电路(20世纪60年代)、大规模和超大规模集成电 路(20世纪70年代至今)。其发展遵循“摩尔定律”。(操作系统 和微型计算机均于第三代问世) ?集成电路是一个充满了微小的电路器件如电线、晶体管、电容和电 阻的晶片。 ?电子计算机从原来的数值计算发展到对多种媒体(文字、声音、图 形图像等)的处理。 ?电子计算机包括:巨型机、大型机、中型机、小型机和微型机等。 ?目前电子计算机的发展趋势:巨型化、微型化和网络化。 1、电子计算机的构成: ?完整的电子计算机系统由硬件和软件两大部分构成。 ?计算机硬件包括:输入设备、输出设备、存储器、运算器、控制器 五大部分。

运算器
数 据

输入信息 输

入 设 备

内存储器
指 令
输 入 输 出 数 据

输 输出信息 出 设 备

控制器

辅助存储器 数据与指令流向 控制信息流向

计算机的基本结构

计算机的功能如此强大,似乎无所不能,是因为计算机是人发明的 ,到目前为止它还只能听从设计者的指挥,按照设计者事先安排好 的程序进行工作。 ?计算机的软件就是使计算机运行的各种程序及其文档资料,包括系 统软件和应用软件两大类。 2、计算机硬件 1)输入设备:从外部获取信息的计算机设备。(如扫描仪) 2)输出设备:把计算机对信息的处理结果以人们能够识别的形式表 现出来的设备。(如打印机、触摸屏、绘图仪) 输入设备、输出设备和外存储器统称为外部设备。 3)存储器:保存数据和程序指令的电子器件。存储器可分为内存储 器和外存储器。把与处理器直接相连的存放数据的器件称为内存, 不直接与处理器相连的介质如磁盘称为外存储器。 ?内存储器又包括:随机存储器和只读存储器。 ?常见的外存储器包括:软盘、硬盘(固定与移动)、光盘和U盘等。 ?存储器存储容量的基本单位是:字节。(B)最小单位是一个二进 制位。(bit)(1B=8bit) ?存储器的主要技术指标:容量、速度和价格。

分辨率概念释疑

分辨率是一个表示平面图像精细程度的概念,通常它是以横向和纵向点的数量来衡量的,表示成水平点数× 垂直点数的形式。在一个固定的平面内,分辨率越高,意味着可使用的点数越多,图像越细致。分辨率有多 种,在显示器上有表示显示精度的显示分辨率,在打印机上有表示打印精度的打印分辨率,在扫描仪上有表 示扫描精度的扫描分辨率。下面分述如下: 显示分辨率 显示分辨率是显示器在显示图像时的分辨率,分辨率是用点来衡量的,显示器上这个“点”就是指像 素(pixel)。显示分辨率的数值是指整个显示器所有可视面积上水平像素和垂直像素的数量。例如800×600的 分辨率,是指在整个屏幕上水平显示800个像素,垂直显示600个像素。显示分辨率的水平像素和垂直像素的 总数总是成一定比例的,一般为4:3、5:4或8:5。每个显示器都有自己的最高分辨率,并且可以兼容其它较低 的显示分辨率,所以一个显示器可以用多种不同的分辨率显示。显示分辨率虽然是越高越好,但是还要考虑 一个因素,就是人眼能否识别。例如,在14英寸最高分辨率为1024×768的显示器上800×600是人眼能识别 的最高分辨率(我们暂时称为最佳分辨率),在1024×768这个分辨率下显示器虽然可以精确的显示图像,但人 眼已不能准确的识别屏幕信息了。在相同大小的屏幕上,分辨率越高,显示就越小。由于显示器的尺寸有大 有小,而显示分辨率又表示所有可视范围内像素的数量,所以相同的分辨率对不同的显示器显示的效果也是 不同的,例如:800×600的分辨率,14英寸的显示器比以相同分辨率显示的17英寸显示器的显示精度要高一 大截。有些质量较好的显示器(如:Philips 15A、14A),14英寸显示器可达1280×1024,15英寸显示器可达 1600×1200。 打印分辨率 打印分辨率直接关系到打印机输出图像或文字的质量好坏。在这里我们只考虑喷墨打印机和激光打印 机的打印分辨率。打印分辨率用dpi(dot per inch)来表示,即指每英寸打印多少个点。喷墨和激光打印的水平 分辨率和垂直分辨率通常是相同的。例如:在打印分辨率为600dpi是指打印机在一平方英寸的区域内垂直打 印600个点,水平打印600个点,总共可打360000个点。但是,720dpi的喷墨打印机不一定比600dpi的激光打 印机产生更好的打印质量。这是因为喷墨打印机打印的每一个墨点只是近似相等,每个墨点在干燥之前还会 向四周扩散,没有激光打印机产生的点那样均匀。 扫描分辨率 决定扫描仪性能的主要因素有三个:扫描分辨率、最大扫描页面、颜色位数。扫描分辨率是一种输入 分辨率,而显示分辨率和打印分辨率都是输出分辨率。我们在使用扫描仪扫描图形时可以根据需要调节扫描 的精度,不像显示分辨率和打印分辨率是固定的或只有几种可选。扫描分辨率也用dpi来表示,但它不像打印 机那样垂直分辨率和水平分辨率是一致的,扫描仪的水平分辨率是垂直分辨率的一半。 扫描分辨率分为两种:光学分辨率和插值分辨率。光学分辨率是扫描仪在扫描时读取源图形的真实点数 。通常扫描仪的光学分辨率从300×600dpi到1000×2000dpi。另外有些扫描仪的分辨率为1200×1200dpi,这 类扫描仪是利用硬件功能提升水平分辨率的精度。插值分辨率是指在真实的扫描点基础上插入有些点后形成 的分辨率。它是扫描图像时可以调节的分辨率的最大值,通常是光学分辨率的4-16倍,以4倍、8倍、16倍 最常见。例如光学分辨率为300×600dpi的扫描仪插值分辨率可达4800×9600dpi。选购扫描仪时应考虑光学 分辨率,而不是插值分辨率。插值分辨率毕竟是生成的点而不是真实的扫描点数,虽然提高分辨率使图像更 细致,但细节上跟原来的图形会有一定程度的差异,它并不代表扫描的真实度。而光学分辨率虽然数值较小 ,但它代表扫描的真实精度。插值分辨率为4800dpi的扫描仪,其光学分辨率可能为300×600dpi,也可能为 600×1200dpi,所以选购四一定要弄清光学分辨率的大小,对于扫描要求不高的图形,使用300dpi的精度即 可。对于精度要求较高的图形,用使用600dpi以上的精度。

?存储器的读写速度比CPU的速度慢。 ?在存储器中,每一个存放数据的基本单位称为一个存储单元,一个 存储器是许许多多存储单元的集合。为了能准确高效地存取数据, 每个存储单元都有一个唯一的编号——存储单元的地址。 ?除此而外,还有虚拟内存、CMOS存储器和高速缓存。 如果随机存储器不够用怎么办? 操作系统会使用硬盘来扩充内存,即将最近最少使用的程序从内存 移动到磁盘上。计算机使用磁盘模拟的内存被称为虚拟内存。 CMOS存储器中保存了计算机的配臵信息,例如日期和时间、硬盘 的容量和内存容量等。 4)运算器:进行算术运算和逻辑运算的部件。包括ALU(算术逻 辑单元)和寄存器。 5)控制器:从存储器中取出操作指令并进行分析,向计算机个各个 部件发出控制信息,使计算机按照人们的指令完成任务。(计算机 系统的大脑)运算器和控制器合称为中央处理器。(CPU) 影响CPU性能的主要技术指标: 1)主频,也就是CPU的时钟频率,简单地说也就是CPU的工作频率 。CPU的主频表示在CPU内数字脉冲信号震荡的速度。

一般说来,一个时钟周期完成的指令数是固定的,所以主频 越高,CPU的速度也就越快了。不过由于各种CPU的内部结构也 不尽相同,所以并不能完全用主频来概括CPU的性能。 关于高速缓存(CACHE) 由于CPU的速度比内存和硬盘的速度要快得多,所以在存取数据 时会使CPU等待,影响计算机的速度。SRAM的存取速度比其它 内存和硬盘都要快,所以它被用作电脑的高速缓存(快存)(Cache)。

有了高速缓存,可以先把数据预写到其中,需要时直接从它读 出,这就缩短了CPU的等待时间。高速缓存之所以能提高系统 的速度是基于一种统计规律,主板上的控制系统会自动统计内 存中哪些数据会被频繁的使用,就把这些数据存在高速缓存中, CPU要访问这些数据时,就会先到Cache中去找,从而提高整体 的运行速度。一般说来,256K的高速缓存能使整机速度平均提 高10%左右。 主板上通常都会提供256K到1M的缓存。在CPU内部也有高速缓 存,如486CPU有8K的高速缓存,Pentium有16K的高速缓存。 Pentium II有32K 一级缓存,AMD K6-2中有64K的一级Cache,AMD K6-3中有64K 的一级 Cache,和256K 的二级 Cache,Cyrix MII 中有 64K的Cache。 为了区分它们,CPU内部的缓存叫内部高速缓存(Internal Cache)或 一级高速缓存,主板上的缓存叫外部高速缓存(External Cache)或二 级高速缓存。不过现在的Pentium II 的CPU已经将主板上的二级 缓存封装在CPU的盒子中,AMD K6-3的CPU内部也集成了256K 的二级Cache,对于这类CPU来说,主板上提供的已是三级缓存 了。

2)L1高速缓存,也就是我们经常说的一级高速缓存。在CPU里面内 臵了高速缓存可以提高CPU的运行效率。 3)L2高速缓存,指CPU第二层的高速缓存,第一个采用L2高速缓存 的是奔腾Pro处理器,它的L2高速缓存和CPU运行在相同频率下的, 但成本昂贵,市场生命很短,所以其后奔腾II的L2高速缓存运行在 相当于CPU频率一半下的。 处理器运算的位数: CPU的位宽对CPU性能的影响绝不亚于主频。位宽是指微处理器一次 执行指令的数据带宽。处理器的寻址位宽增长很快,业界已使用过 4、8、16位寻址再到目前主流的32位,而64位寻址浮点运算已经逐步 成为CPU的主流产品。 对于计算机的使用者而言,他们正在经历一个变革时期。他们除了 要把自己的计算机升级到64位,也开始为向多颗“心脏”升级作准 备。一直以来,使用者都在追逐更高的性能,希望计算机能做更多 的事情,而英特尔、AMD这些芯片巨头之间的激烈争夺,让这样的 局面提前到来了。

论CPU技术的发展史

推荐网站:http://cpu.zol.com.cn/22/226166.html http://bbs.yyup.com/Announce/Announce.asp?BoardID=35&ID=261859等。 关于CPU的基础知识:CPU的常识 CPU从最初发展至今已经有二十多年的历史了,这期间,按照其处 理信息的字长,CPU可以分为:四位微处理器、八位微处理器、十六位 微处理器、三十二位微处理器以及六十四位微处理器等等。 如今,Intel的CPU和其兼容产品统治着微型计算机——PC的大半江 山,但是除了Intel或AMD的CPU,还是你可能听说过的其他一些CPU, 如HP的PA-RISC,IBM的Power4和Sun的UltraSparc等,只是它们都是精简 指令集运算(RISC)处理器,使用Unix的专利操作系统,例如IBM的 AIX和Sun的Solaris等。 虽然设计方式和工作原理的过程有区别,但不同处理器依然有很多 相似之处。从外表看来,CPU常常是矩形或正方形的块状物,通过密密 麻麻的众多管脚与主板相连。不过,你看到的不过是CPU的外衣—— CPU的封装。而内部,CPU的核心是一片大小通常不到1/4英寸的薄薄的 硅晶片(其英文名称为die,核心)。在这块小小的硅片上,密布着数以百 万计的晶体管,它们好像大脑的神经元,相互配合协调,完成着各种复 杂的运算和操作。

Intel 486

CPU的溯源可以一直去到1971年。在那一年,当时还处在发展阶段的INTEL公 司推出了世界上第一台微处理器4004。这不但是第一个用于计算器的4位微处 理器,也是第一款个人有能力买得起的电脑处理器!4004含有2300个晶体管, 功能相当有限。 1978年,Intel公司再次领导潮流,首次生产出16位的微处理器,并命名i8086, 同时还生产出与之相配合的数学协处理器i8087。 1979年,INTEL公司推出了8088芯片,它仍旧是属于16位微处理器,内含 29000个晶体管,时钟频率为4.77MHz,地址总线为20位,可使用1MB内存。 8088内部数据总线都是16位,外部数据总线是8位,而它的兄弟8086是16位。 1985年INTEL推出了80386芯片,它是80X86系列中的第一种32位微处理器, 此时的CPU技术,真正发展到了32位时代。而且制造工艺也有了很大的进步, 与80286相比,80386内部内含27.5万个晶体管,时钟频率为12.5MHz,后提高 到20MHz,25MHz,33MHz。80386的内部和外部数据总线都是32位,地址总 线也是32位,可寻址高达4GB内存。 1989年,大家耳熟能详的80486芯片由INTEL推出,这种芯片的伟大之处就在 于它实破了100万个晶体管的界限,集成了120万个晶体管。80486的时钟频率 从25MHz逐步提高到33MHz、50MHz。 1997年4月7日 。英特尔发布了Pentium II处理器。内部集成了750万个晶体管, 也就是影响力最大的CPU——奔腾 Ⅱ。 1999年1月,Intel推出奔腾III处理器。 2000年11月21日,Intel 在全球同步发布了其最新一代的微处理器—Pentium4 (奔腾4)。

2003年美国时间 9 月 23 日,全球第一款桌面系统 64bit 处理器在美国正式发 布。几经波折, Athlon 64 终于在人们期待的目光中揭开了神秘面纱。Athlon 64 的诞生对于桌面处理器领域具有划时代的意义。对于 AMD 来说,这更是具有战 略意义的关键一步。AMD——终于打破了最近时期的不利局面——按照原定布局 领先对手步入了 64bit 时代。跳开对手在架构和制造工艺等方面的追击,另辟战 场利用 Athlon 64 再度出击。 Athlon64 的发布,使得桌面电脑可以迅速迈入64-bit 时代,目前操作系统、 软件都已经逐渐成熟。AMD 正在迎来丰收时期。

3、计算机软件 ?指令:指出计算机所能完成的基本操作的一组代码。 ?程序:指令的有序集合称为程序。 ?软件:程序和有关的文档资料。 ?指令的基本格式:操作码和地址码(操作数) 指令中的地址码指出的是参加指定操作的数据地址,操作码指出 机器所能进行的基本操作。

ALU(算术逻辑部件)

运算器
CPU 主机 硬件 计 算 机 系 统 主存 控制器 RAM 寄存器

ROM 外存(辅助存储器)
输入/输出设备

外部设备

程序语言,如:C++、BASIC等 系统软件 操作系统,如:Windows、UNIX、LINUX 数据库管理程序,如:FoxPro、ORACLE 软件 sybase、MYSQL、SQL Sever 应用软件 系统软件与应用软件之间的关系是:应用软件是建立在系统软件基 础之上的。

4、关于冯· 诺依曼的“存储程序”的思想——计算机之父 在电子计算机发展初期,美籍匈牙利数学家冯· 诺依曼就提出了“存 储程序”的思想:把程序作为数据存储在计算机的存储器中,也就 是预先把程序输入、存储在存储器中,执行时不用人的干预,计算 机的控制器自动依次取出程序中的一条条指令,经过分析和解释, 指挥计算机各部件自动、高速地依次完成一系列预定操作。这一 著名的设计思想让计算机硬件不必为某一应用而专门设计,只要改 变软件就可以是计算机完成各种应用。迄今为止的电子计算机基本 上都是按照冯· 诺依曼的“存储程序”的思想设计的。 5、关于计算机的操作系统 操作系统是计算机最基本的系统软件。 现代计算机为什么要把操作系统作为最基本的系统软件? 1)操作系统的作用: ?管理和控制计算机的硬件设备。包括主机、显示器、键盘、鼠 标、磁盘驱动器、打印机等。 ?管理安装在计算机中的各种软件,管理文件在计算机中的存储 和使用。 ?在人机之间建立直观方便、简洁友好的操作界面。

2)常用的操作系统: DOS、Windows、UNIX、LINUX(Red Hat Linux)OS/2等。 DOS系统的单用户、单任务、字符界面的操作系统。 Windows是Microsoft公司研制的窗口式图形界面多任务系统。 Linux是目前全球最大的一个自由软件,它是一个可与UNIX和 Windows相媲美的操作系统,具有完备的网络功能。 常用的数据库软件:Access,SQL Server,Oracle My SQL Visual Foxpro sybase等。 二、关于二进制及数值间的转换 在计算机内部对信息的存储、处理和传输都是用二进制进行的。 1)将二进制数转换为十进制数:按权展开再求和。 11010.11(2)=1*24+1*23+0*22+1*21+0*20+1*2-1+1*2-2=26.75 2)十进制整数转换成二进制整数:2除取余法。 23 ÷ 2 11 ÷ 2 5 ÷ 2 2 ÷ 2 1 ÷ 2 0 1 1 1 0 1 23=10111(2)

n(n≠10)转换为十进制:按权展开再求和。 十进制整数转换为n (n≠ 10):n除取余法。 3)十进制纯小数转换为二进制纯小数:二乘取整法

0.625

×2

0.25

×2

0.5

×2

0.0 0.625=0.101(2)

1 0 1 二进制数与十六进制数互换时,可以将二进制数按四位一组划, 每组用一个十六进制数表示,不足“0”补齐后替换。
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 0 1 2 3 4 5 6 7 8 9 A B C D E F

例:将二进制数101100.101转换为十六进制数。 00101100.1010 101100.101(2)=2C.A(16) 2 C . A 三、ASCII码与汉字编码 美国(国家)信息交换标准(代)码,ASCII码于1968年提出,用于在不 同计算机硬件和软件系统中实现数据传输标准化。标准ASCII码用7 位二进制表示,占一个字节,最高位为奇偶校验共有128种不同的组 合。第0~32号及第127号(共34个)是控制字符或通讯专用字符,如 控制符:LF(换行)、CR(回车)、FF(换页)、DEL(删除)、 BEL(振铃)等;通讯专用字符:SOH(文头)、EOT(文尾)、 ACK(确认)等; 第33~126号(共94个)是字符,其中第48~57号为0~9十个阿拉伯数

字;65~90号为26个大写英文字母,97~122号为26个小写英文字母 ,其余为一些标点符号、运算符号等。 注意:在计算机的存储单元中,一个ASCII码值占一个字节(8个二 进制位),其最高位(b7)用作奇偶校验位。 四、计算机的语言——人和计算机进行交流的一种工具 1、程序设计语言 包括:机器语言、汇编语言和高级语言。 由于电子计算机的内存储器的基本结构是电子开关,而一个电子 开关的稳定状态只有两种,那么这两种状态所对应的编码就分别 是0和1。因此,计算机内部的所有数据,指令和地址等都是用二 进制数编码的。 ?机器语言:一台计算机的全部指令的集合。用机器语言编写的程 序,称为机器语言程序。机器语言程序是计算机唯一能直接识别 和执行的程序。 缺点:难学、难理解、易出错、直观性差、通用性差。 优点:执行速度快。 ?汇编语言:采用易于记忆的“指令符号”来代替冗长的机器指令 代码。

由于计算机只能直接执行机器语言程序,因此必须把用汇编语言编 写的程序(源程序)“翻译”成机器语言程序(目标程序)。 缺点:较难学习理解,通用性差。 优点:执行速度快。 ?高级语言:较为接近人类语言(英语)与具体计算机指令系统无 关的计算机语言。常用的有:Fortran(世界上第一个高级程序设 计语言)、COBOL、BASIC、Pascal、C、C++、VisualBASIC、 VC、 Java、Visual C#.NET、Delphi、Prolog等。 由于计算机仍不能直接识别用高级语言编写的程序,因此必须把高 级语言程序(源程序)“翻译”成机器语言程序(目标程序)。翻 译的方式有:编译方式和解释方式。(Pascal:编译方式,BASIC:解释 方式)(注:解释方式不生成目标程序,而是翻译一句,执行一句。) 优点:易于学习,通用性强。 在离散数学中,∧ (或∩)表示逻辑与,∨(或∪)表示逻辑或,~表示 逻辑非。三种运算的优先级别是:逻辑非?逻辑与?逻辑或。 2、结构化程序设计方法: ?程序由:顺序结构、分支结构和循环结构组成。 ?一个大型程序应按其功能分解成若干模块。

?程序设计采用“自顶向下、逐步求精”的方法。 3、面向对象的程序设计 简单地说,面向对象的程序设计把我们所处的世界看成是由一组 彼此相关并互通信息的实体(即对象)组成的。 目前常用的面向对象的程序设计语言有:Borland C++、Visual C++ 、Java、Delphi等。 第二部分 一、网络基础
掌握一些网络术语是必须的。下面列出了一些常见的网络术语: Internet: Internet是由遍布全世界的大大小小网络组成的一个松散结合的全球互联网络。目前Internet 上的主机数已多达数千万个。 www:www是Word Wide Web的简称,译为万维网或全球网,是指在因特网上以超木为基础形成的 信息网。它为用户提供了一个可以轻松驾驭的图形化界面,用户通过它可以查阅Internet上的信息资源。 URL:描述了Web浏览器请求和显示某个特定资源所需要的全部信息,包括使用的传输协议、提供 Web服务的主机名、HTML文档在远程主机帆上的路径和文件名以及客户与远程主机连接时使用的端口号。 TCP/IP协议:世界上有各种不同类型的计算机,也有不同的操作系统,要想让这些装有不同操作系 统的不同类型计算机互相通讯,就必须有统一的标准。 TCP/IP议就是目前被各方面遵从的网际互联工业标 准。 IP地址:为了能在网络上准确地找到“一台计算机,TCP/IP协议为每个连到Internet上的计算机分配 了“一个唯一的用32位进制数字表示的地址的字、为便于管理,将它们分割为四部分并转换为进制餐字,就 是我们常说的IP地址。如:220.96.128.110 DNS: TCP/IP提供了一种域名系统(Domain Name System〕,它为每个IP地址提供了一个便于记 忆的域名,如http://www.cce.com.cn/。我们上网时键人城名后, DNS就会将它翻译成IP地址让计算机辨 识,如http://www.cce.com.cn/的IP地址为192.9.188.1。 Java:由Sun公司开发的新一代而面向对象的网络编程语言,可以交叉支持不同的平台。 ISP:全称为Interner service Provider。即因特网服务提供商,能提供拨号上网服务,网上浏览、下 载文件、收发电子邮件等服务。 ICP:网上信息内容服务商.它为上网用户提供包括新闻,娱乐,购物等方面的信息。 按号上网:用户通过调制解调器使用电话线拨打ISP的上网电话号码,从而连接internet的方式。 E-mail:电子邮件,即我们通过计算机接发的各种电子信息(如文本、图片、软件等)的一种工具 。 BBS:因特网上信息实时发布系统。相当于现代生活中的公告牌,上网用户可以在此发布各种各样 的信息。 下载:将网络上其他计算机中的信息(文本、图片、软件等)拷贝到本地计算机中的过程。

1、网络的分类: 广域网:其覆盖范围可能是一个省或者一个地区或若干个省区,甚 至整个国家。广域网采用远距离通信介质(如电话线、卫星、微波 、光纤等)将距离很远的计算机联接起来。 局域网:覆盖一个较小区域的网络,比如一幢大楼或一个教室内部 的网络。 因特网(Internet,又称国际互联网):是由分布在世界各地的千百 万台计算机和网络组成的开放的全球性的广域网。 2、网络的功能: 数据传输、资源共享和分布式处理功能。 分布式处理功能是指通过网络将一件较大的工作分配给网络上各台 计算机去完成。 3、常见的网络硬件: 网络服务器、网络工作站、传输介质和网络设备等。 传输介质是网络通信的线路,有双绞线、同轴电缆和光纤,此外 还有短波、卫星等无线的传输方式。在局域网的组网中,网线和 终端上的网卡一一对应。无线传输还有红外技术、蓝牙技术(一种 使用无线电波进行传输的技术和设备)

网络设备包括:网卡、调制解调器(Modem)、集线器(Hub)、 交换机(Switch)、路由器(Router)等,负责网络中数据中转、 信号放大以及网络互联的设备。其中, 调制解调器:在发送方从计算机取得需要传送的数据并将其转换成 电话线能够接受的形式(模拟信号);在接收方再将其转换成计算 机能够识别的数字信号送给计算机。(数据传送的速度单位:bps) 3、局域网的拓扑结构: 服务器、工作站等设备在物理上连接起来的形式,称为网络的拓扑 结构,有总线型,树形,环型和星型。 4、网络协议: 为了能使不同地点、装有不同操作系统的计算机之间有效地通信, 必须有一种为各类计算机都能够认可的通信方法,任一方所表达的 信息均能被其他方所认同。这就需要指定一种标准,即:计算机之 间进行通信的规则。 TCP/IP(Transmission Control Protocol/Internet Protocol传输控制协 议和网际协议)协议是目前因特网应用最广泛的协议之一。在数据 传送中,按照TCP/IP协议的规定,要把传递的信息划分成若干段, 每段除包含一定长度的正文外,还含有它将被送往的地址(即IP地

址)。接收数据时,再按照TCP/IP协议的规定把每段信息按发送前 的顺序还原并校验,发现差错则要求重发,以确保传送信息 的准确 。 4、因特网及提供的基本服务: 因特网:是世界上最大的国际互联网络。因特网以TCP/IP协议为基 础通信协议。根据协议,在因特网上进行通信,需要通过IP地址寻 址,因此,必须对IP地址的格式有所了解。 IP地址的格式由四段0~255的数字组成,各段之间用“.”分隔,用一 个32位的二进制数来表示。 近年来,随着国际互联网的迅速发展,以四段0~255的数字表示的 网络地址(IPv4)已经不能满足越来越多的计算机进入网络的需求 了。目前,一种使用48位二进制表示的、可容纳更多的地址方案 (IPv6)正在研究试验中。 因特网提供的基本服务包括: 远程登录:允许用户用个人计算机登录到某台远程的大、中型计算 机,成为这台计算机的一个终端。(Telnet) 文件传输:让用户联接上一个运行着FTP服务器程序的远程计算机 ,然后将文件上传到该远程计算机,也可将远程计算机内的文件下

载到本地计算机,实现文件共享。(FTP-File Transfer Protocol) 电子邮件:本质上是一个磁盘文件。是利用计算机网络收发信息 的 一种服务,具有快速、费用低和可传送文字、图象、声音等特点, 已成为因特网上应用最为广泛的服务之一。(E-mail) E-mail地址的格式由三部分组成: (1)用户名;(2)“@”符号;(3)用户所联接的主机地址。 TCP/IP除了本身的两个协议外,还包括SMTP(电子邮件协议)、 FTP(文件传输协议)、TELNET(远程登录协议)等协议。 5、信息安全 信息安全是指人为因素对计算机以及存储的信息进行有意或无意 破坏的行为。 目前,对信息安全危害最大的是计算机病毒和黑客非法入侵。 1)计算机病毒(Computer Virus) 是人为编制的、可能对计算机及其存储的信息造成危害的计算机程 序。这种特殊的计算机程序能够在计算机系统或网络中通过自我复 制来进行传播,在一定条件下被激活,并对计算机系统及存储的信 息造成破坏。计算机病毒具有隐蔽性、传染性、潜伏性和破坏性。

什么是TCP/IP协议 TCP/IP(Transmission Control Protocol/Internet Protocol的简写,中文 译名为传输控制协议/互联网络协议)协议是Internet最基本的协议, 简单地说,就是由底层的IP协议和TCP协议组成的。 在Internet没有形成之前,各个地方已经建立了很多小型的网络, 称为局域网,Internet的中文意义是“网际网”,它实际上就是将全 球各地的局域网连接起来而形成的一个“网之间的网(即网际网)” 。然而,在连接之前的各式各样的局域网却存在不同的网络结构 和数据传输规则,将这些小网连接起来后各网之间要通过什么样的 规则来传输数据呢?这就象世界上有很多个国家,各个国家的人说 各自的语言,世界上任意两个人要怎样才能互相沟通呢?如果全世 界的人都能够说同一种语言(即世界语),这个问题不就解决了吗 ?TCP/IP协议正是Internet上的“世界语”。TCP/IP协议的开发工作始 于70年代,是用于互联网的第一套协议。 TCP/IP协议共有5层协议。

2)计算机病毒的防治 ?不使用未经查杀病毒的软盘和光盘。 ?不到网上随意下载来历不明的各种软件(包括游戏软件) ?不随意打开来历不明的电子邮件附件。 ?安装杀毒软件及防火墙并经常进行升级。 对重要的数据经常进行备份 3)黑客程序和黑客入侵 很多黑客程序也具有病毒的特征,如:传染性、隐蔽性和破坏性等 。它们二者的主要区别在于黑客程序的目的是窥视用户的隐私、窃 取用户的信息,对用户计算机的资源进行远程控制。 黑客程序很容易和计算机病毒相混淆,如果计算机在上网时出现以 下这些现象:系统死机或有时无故重启、没有让计算机读写磁盘的 操作却频繁出现硬盘读写指示、程序自动关闭、鼠标指针自动移动 等等,则有可能是黑客入侵,应立即离线检查。 新的《计算机软件保护条例》已经与2002年1月1日取代可旧的《计 算机软件保护条例》,成为我国计算机软件保护的法规。《条例》 规定,中国公民和单位对其开发的软件,不论是否发表,不论在何 地发表,均享有著作权。

第三部分 数据结构基础 一、基本概念和术语 数据(Data) 是对客观事物的符号表示,在计算机中是指所有能输入 到计算机中并被计算机处理的符号的总称。数据的含义极为广泛, 如图象、声音等都可以通过编码而归之于数据的范畴。 数据元素(Data element) 是数据的基本单位,在计算机程序中通常作 为一个整体进行考虑和处理。数据元素也称为结点、记录。 数据元素相互之间的关系称为结构(Structure)。根据数据元素之间 关系的不同特性,通常有下列四类基本结构: (1)集合 结构中的数据元素之间除了“同属于一个集合”的关系外 ,别无其他关系; (2)线性结构 结构中的元素之间存在着一个对一个的关系; (3)树形结构 结构中的数据元素之间存在一个对多个的关系; (4)图状结构或网状结构 结构中的数据元素之间存在着多个对多 个的关系。 算法(Algorithm) 是对特定问题求解步骤的一种描述,它是指令的有 限序列,其中每一条指令表示一个或多个操作。一个算法具有下列 四个重要特性:

(1)有穷性 一个算法必须总是在执行有穷步并在有穷时间内完成; (2)确定性 算法中每一条指令必须有确切的含义,理解是不会产 生二义性。 (3)可行性 一个算法是能行的,即算法中描述的操作都是可以通 过已经实现的基本运算执行有限次来实现的。 (4)输入和输出 一个算法有零个或多个输入,有一个或多个输出 。 集合 线性





四类基本结构关系图

算法设计的要求: (1)正确性 正确大体可分为:a.程序不含语法错误;b.程序对于几 组输入数据能够得出满足要求的结果;c.程序对于精心选择的典型 、苛刻而带有刁难性的几组输入数据能够得出满足要求的结果;d. 程序对于一切合法输入数据都能产生满足要求的结果。 (2)可读性 易于阅读与交流、调试与修改。 (3)健壮性 当输入数据非法时,能作出适当的反映与处理。 (4)效率与低存储量需求 效率是指算法的执行时间,存储量需求 指算法执行过程中所需要的最大存储空间。 二、常见的数据结构(简述) 堆栈、队列、链表、树和图。 1、堆栈 堆栈是一种线性表对它的插入和删除都在表的同一端进行,操作的 一端叫做栈顶,另一端叫栈底。根据堆栈的定义,每次删除的 总是 栈中最顶上的元素,而最先插入的元素则被放在栈的底部。因此, 堆栈又被称为后进先出表(LIFO)。通常栈可以用顺序的方式存储 ,分配一块连续的存储区域存放栈中的元素,并用一个变量t指向当 前栈顶。

2、队列 队列是不同于堆栈的另一种线性表。在日常生活中,无论是购物 、定票还是候车,都有可能要排队。排队所遵循的原则是“先来先服 务”,后来者总是排在对尾,排在前面者总是先离开队伍。所谓队列 就是指允许在一端进行插入操作,在另一端进行删除操作的线性表 。元素插入的一端称为队尾,通常用一个队尾指针r来指示;元素删 除的一端称为队首,通常用一个队首指针f来表示。因此队列又称为 “先进先出”(FIFO)的线性表。 堆栈和队列的顺序存储空间都可以用一维数组来模拟。 3、链表 前面介绍的堆栈和队列以及数组等顺序存储结构的线性表具有数据 元素存储方便等特点。但也存在一些缺点:在插入和删除操作时要 移动大量的元素;在给定长度变化比较大的情况下,内存浪费比较 严重;存储容量扩充比较困难。因此引入一种新的数据结构——链 式存储的线性表即链表。 链表是这样一种线性表,它的元素由数据和指针两部分组成,数据 部分存放结点的有关信息,指针部分存放下一个结点的地址。 4、树

12.4 树和二叉树 12.4.1 概念 磁盘文件与目录(文件夹)的结构(树型结构) C:\

Windows

Program Files

TP

My Documents

All Users

Command

Adobe

Microsoft Office

Turbo.exe

Graph.tpu

My Pictures



Format.com



Office

Templates

汉诺塔.gif

Win.jpg





树的定义和基本术语 T1 A E K
(a)只有一个根结点 的树

层次 1

A

B
F L

C
G H

D
I J

2

3

T2
(b)一般的树

M
T3

4

有关树的八个概念: ?树:是n(n≥0)个元素的有限集。N=0时称为空树。

?根和子树:在任一非空子树中,有且仅有一个称为根的元素;其余元素可分为m(m≥0)个互不 相交的有限集T1,T2,…Tm,其中每个集合本身又是一棵树,并且称为根的子树。

例如:(b)是有13个结点的树,其中A是根,其余结点分成三个互不相交的子集: T1={B,E,F,K,L},T2={C,G},T3={D,H,I,J,M}

根 A B E 根的子树T1 T1={B,E, K F,K,L} L 根的子树T2 T2={C,G} F C G H D I J

对于子树T1
T1的根

B E K L F

M

根的子树T3 T3={D,H, I,J,M}

T1的子树T11 T11={E,K,L}

T1的子 树T12 T12={F}

T1,T2,T3都是根A的子树,且本身也是一棵树。例如:T1:其根是B,其余结点分为两个互不相 交的子集: T11={E,K,L},T12={F},T11和T12都是B的子树。而T11中E是根,{K},{L}是两棵互不相交的子 树其本身又是只有一个根结点的树。

?结点的度、终端结点、非终端结点:树的结点包含一个数据元素及若干指向其子树的分支。结点 拥有子树数目称为结点的度。度为0的结点称为叶子(Leaf)或终端结点。度不为0的结点称为非终 端结点或分支结点。

例如:结点A的度是3,结点C的度是1,结点E的度是2 结点K,L,F,G,M,I,J为叶子结点,结点A,B,C,D,E,H为非终端结点。 ?树的度:树内各结点度的最大值。例如: (b)树的度是3。 ?有序树和无序树:如果将树中的各子树看成是从左到右有次序的(即不能互换),则称该树为有 序树,否则称为无序树。 ?结点的孩子:结点的子树的根称为该结点的孩子,相应地,该结点称为孩子的双亲。

结点A的孩子

A B E F C G

孩子{B,C,D}的双亲 孩子{H,I,J}的双亲

D H I J

K

L

M
结点D的孩子

例如:结点B,C,D是结点A的孩子,结点A是B,C,D的双亲;结点E,F是结点B的孩子,结点B 是E,F的双亲。 ?结点的层次:根为第一层;若某结点在第P层,则其子树的根就在第P+1层。 ?树的高度(或深度):树中结点的最大层次称为树的高度(或深度)。例如:(b)树的高度为4。

练习 1.已知下图是一个有14个结点的树,请回答下面问题: (1)哪个是根结点? A

A B D I M N E F J C G K L H

(2)哪些是叶子结点?哪些是非终端 结点? D、M、N、F、J、K、L。 A、B、C、E、G、H、I。 (3)哪个是结点G的双亲? C (4)哪些是结点G的孩子? J、K。 (5)结点B和N的层次号分别是什么? 2、5。 (6)结点C和E的度分别是什么?树的度是 什么? 3、1。3。 (7)树的高度是多少? 5。

2.(填空)有一棵树如图所示,回答下面的问题:(1)这棵树的根结点是_______。 K1 K2,K4,K5,K7 (2)这棵树的叶子结点是_______________。 K1 2 (3)结点K3的度是_______。 3 (4)这棵树的度是_______。 4 (5)这棵树的深度是_______。 K2 K3 K4 K5,K6 (6)结点K3的孩子是_______。 K1 (7)结点K3的双亲是_______。 K5 K6

K7

12.4.2 二叉树(重点)
一、二叉树的定义: 二叉树(Binary Tree)是另一种树型结构,它的特点是每个结点至多只有二棵子树(即二叉 树中不存在度大于2的结点),并且,二叉树的子树有左右之分,分别称为左子树和右子树,其 次序不能任意颠倒。
1 2 4 6 5 7 3 4 2 5

1
3 6

(a)

(b)

1 2 4 8 9 10 5 11 12 6 13 14 3 7 15 8 4 9 10 2 5 11

1 3 6 12 7

(c) 特殊形态的二叉树 二、二叉树具有下列重要性质:

(d)

性质1 在二叉树的第i层至多有

2i-1 个结点。 (i≥1)

性质2 高度为k的二叉树至多有 2k-1 个结点。 性质3 对任何一棵二叉树,若叶子结点数为n0,度为2的结点数为n2,则n0=n2+1。(二叉树的叶 子结点数总比度为2的结点数多1)
证明:设n1为二叉树T中度为1的结点数,因为二叉树中所有结点的度均≤2,所以其结点总数为 n=n0+n1+n2 (1) 再看二叉树的分支数,除了根结点外,其余结点都有一个分支进入,设B为分支总数,则 n=B+1,由于这些分支是由度为1或2的结点射出的,所以B=n1+2n2。于是得: n=n1+2n2+1 (2) 由(1)和(2)得: n0=n2+1

满二叉树:一个高度为k且有2k-1个结点的二叉树称为满二叉树。

1 2 3 5 6 7

可以对满二叉树的结点进行连续编号,约定编号从根结点 起,自上而下,从左至右。从而引出: 完全二叉树:高度为k,有n个结点的二叉树,当且仅当 其每一个结点都与高度为 k的满二叉树中编号从1至n的 结点一一对应时,称之为完全二叉树。 完全二叉树的另一个定义:再一棵二叉树中,除最后一层 8 外,若其余各层都是满的,并且最后一层或者是满的,或 者是在右边缺少若干连续结点,则此二叉树称为完全二叉树。 性质4:具有 n个结点的完全二叉树的高度为 log2 n +1
( x 表示不大于x的最大整数)

4

9

10

11

12

13

14

15

满二叉树
1 2 4 8 9 5 10 11 12 6 3 7

性质5:如果对一棵有n个结点的完全二叉树的结点编号 (根为1,然后自上而下,从左到右),则对任一结点i (1≤i≤n),有: (1)如果i=1,则结点i是二叉树的根,无双亲;如果i大于 1,则其双亲结点为 i/2 。 (2)结点i的左孩子是2i,右孩子是2i+1;如果2i>n,则 i无左孩子;若2i=n,则i无右孩子。 树的存储结构包括: 静态结构:用一个数组按完全二叉树的结构存放。 动态存储:利用指针类型实现。

完全二叉树

练习(单项选择题) C A 3. 如图所示的4棵二叉树中,_____不是完全二叉树,_____是满二叉树。

(A) (B) (C) (D) B 4.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中包含的结点至少为_____。 A.2h B.2h-1 C.2h+1 D.h+1 C 5.按照二叉树的定义,具有3个结点的二叉树有_____种。 A.3 B.4 C.5 D.6

C 6.深度为5的二叉树至多有_____个结点。 A.16 B.32 C.31 D.10 C 7.树最适合用来表示_______。 A.有序数据元素 B.无序数据元素 C.元素之间有分支层次关系的数据 D.元素之间无联系的数据



h=1

h=2

h=3

h=4

8.对于一个满二叉树,有m个树叶,n个结点,深度为h,则_______。 D A.n=h+m B.h+m=2n C.m=h-1 D.n=2h-1

回答: 9.深度为k的完全二叉树至少有多少个结点?至多有多少个结点?若按自上而下、从左到右的次序给 结点编号(从1开始),则第k层编号最小的叶子结点的编号是多少? 答:2k-1、2k-1、2k-1 填空: n2+1 10.在一棵二叉树中,度为零的结点个数为n0,度为2的结点个数为n2,则有n0=_______。 11.结点共有13的完全二叉树共有_______个叶子结点。 7

12.4.3 二叉树的链式存储结构
用二重链表表示一般的二叉树,可以采用动态数据结构(指针)。由于二叉树中每个结点通常包括数 据元素和两个分支,因此,二叉树对应的二重链表中每个结点应有三个域: 值域: :data 左指针域: lch 右指针域: rch 这种链表也称为二叉链表。二叉链表头指针bt指向二叉树的根结点:

Type bitreptr=^benode; benode=record data:datatype; lch,rch:bitreptr; end; Var bt:bitreptr;
例如:用下图(b)所示的二叉链表存储二叉树 (a):

a

a

^

Lch data rch

b

b d ^ f g c ^ ^ e ^ g d ^ ^ f ^

c e

(a)
12.4.4 二叉树的遍历

(b)

按照一定的规律不重复地访问二叉树中的每一个结点。在访问到每个结点时,可以取出结点中的信 息,亦可对结点作其它处理。 如果用L、D、R分别表示遍历左子树,访问根结点,遍历右子树,则对二叉树的遍历有如下六种组 合: LDR、LRD、DLR、DRL、RDL、RLD 若再限定先左后右的次序,则只剩下三种组合: LDR、LRD、DLR 这三种遍历规则分别称为:中(根)序遍历、后(根)序遍历、先(根)序遍历。

复习题选讲 一、选择题部分 SA 第一套(2000) SA+1 8、参阅《数据结构》P~43“顺序 SA+2 队列”。 SA+3 14、因为29<=1000<=210, SA+4 所以选B。 15、先观察右图: 然后总结规律。 所以选A 19、正确答案是B。这题可以通过 SA+30 归纳的方法来得出结论,假定在 这根两端停着相同小鸟A: A——————B 线段为不同小鸟的线段数 A——A———A 0 SA+120 A——B———A 2 A—A—B——A 2 A—B—B——A 2 SA+141 A—A—A—B—A 2 A—B—A—B—A 4

A[1,1]

A[1,2] …… A[1,10]

占 30 个 字 节
占 120 个 字 节

A[2,1] …… A[2,10] …… A[5,1] …… A[5,8]

A—A—B—A—A 2 由以上增加一只鸟、二只鸟、三只鸟的情况,可推断出:在两端小 鸟相同的情况下,两端为不同小鸟和线段数一定是偶数。 第二套: 20、依题意,入栈顺序是1,2,……n,则出栈顺序必为P1=n, P2=n-1,……Pn=1。则Pi应为n-i+1。所以选C。 第三套: 12、十化十六(小数):16乘取整法。 0.5 *16 0.0 0.5(10)=0.8(16) 所以选C。

8 14、3FF(16)=3*162+15*16+15=1023 2000(8)=2*83=1024 2047-1023+1024=2048 所以选A。 17、参阅:“关于选择题.doc”

第四套: 16、二叉树是有向树,即有左、右之分。试画出高度为3的所有最 小元素数目的二叉树:

所以选B。 第五套: 13、本题属于组合问题,将3个a,1个b,2个c中取出一个“abc” 将其“捆绑在”一起,剩下的2个a、1个c的所有排法有3种可能: □a□a□c□ □a□c□a□ □c□a□a□ 将“abc”插入空格位臵,每种有4种插入法,共有12种。 14、本题要求同学们理解和掌握堆栈及其“后进先出”的存放原则 。依题意:1进1出2进3进3出4进5进6进6出5出7进7出,故选E。

15、按照二叉树的前序、中序遍历的定义: 1)确定1为根,4、2为左子树;5、7、3、6为 右子树; 2)左子树4,2中,前序为2,4,中序为4,2 故可确定左子树为: 3)右子树5,7,3,6中,3为根,5,7为左 子树,6为右子树; 4)前根与中根都是5,7,故最后确定 出整个二叉树的形状。 按后序遍历的定义 ,应为: 4,2,7,5,6,3,1 所以选B。 4
练习:给出一棵二叉树的中序 遍历:DBGEACHFI与后序遍 历:DGEBHIFCA,画出此二 叉树。

1 4,2 5,7,3,6

(1)
1
2 5,7,3,6

4

1 2 5 3 2

(2)
1 3 5,7

6

4
7

6

(4)

(3)

20、若某门课程的先修课程没有学习就学本门课程,即为不合理。 D选项中,C5的先修课程有C3和C7,而C3位于C5之后,故选D。 第六套: 2、A ∩B ∩~C={a,b,c,d,e,f}∩{c,d,e}∩{,b,c,e,f,g,h}={c,e},故选A。 4、画出该完全二叉树如右图: 故应选E。 7、设处理器B处理指令的速度为 v条/秒,则 处理器A处理指令的速度为2v条/秒 。又设特定程序P在处理器B上编译 结果的指令条数为x条,则 特定程序P在处理器A上编译结果的指令条数为4x条。 对于处理器A,有 2v=4x/3600,x=1800v 对于处理器B,有 v=x/t,t=x/v=1800v/v=1800s=1/2h 故选D。

19、依题意,画出该二叉树为:

A

则F的父结点为C,故选C。 20、因为g最先出栈,此时 e应在f之下,不可能在f之 D 前出栈。故选E。 二、问题求解 G 第一套: 1、共有五种不同形态的二叉树:
c b a a b c a c

B
E F

C

H

I

a c

a b c

b

b

2、用F(n)表示其铺法的总数的递推公式为: F(1)=1 F(2)=2 F(n)=F(n-2)+F(n-1) (n≥3) 第二套: 1、将题目给定的六个条件描述为:

1) ⑴选a或⑵选b或⑶选a与b。 2) ⑷选a不选b或⑸选b不选a。 3) ⑹选a与e或⑺选a与f或⑻选e与f。 4) ⑼选b与c或⑽不选b也不选c。 5) ⑾选c不选d或⑿不选c选d。 6) ⒀若不选d,则也不选e。 (1)由1)⑴设选a,由2)⑷选a,由3)⑹,选a,e,由4)⑼选a,b,c e,由5)⑾选a,b,c,e,到6)被推翻。 (2)退至5)⑿选a,b,d,e与2)矛盾,被推翻。 (3)退至4)⑽选a,e,到5)⑾选a,c,e,到6)又被推翻。 (4)退至5)⑿选a,d,e,与2)矛盾,又被推翻。 (5)退至3)⑺选a,f,到4)⑼选a,b,c,f,到5)⑾选a,b,c,f ,到6)选a,b,c,f。结束。 第三套: 1、可以通过穷举列9种可能排列,它们分别是: 35421 32541 34521 32451 32145 34251 32415 32154 34215

2、参阅SH3结尾例题。 第四套: 1、解:A车每年花费油钱为600美圆,B车每年花费400美圆,故 两年内购买B车节省的油钱为400美圆。依题意,B的最高价格为 2.04万美圆。 2、顶点x的度:与顶点x相关联的边的数目称为顶点x的度。 可按题意画出该无向图如下: 因此填11。 第五套: 1、解:4张桌子用80个单位的木材需120 元, 2张椅子用32个单位的木材需40元, 所以最多可以卖160元。 2、解:依题意,20人三种东西都玩过 总费用为: 20*15=300元 35人玩过其中2种,总费用为 35*10=350元

700-(300+350)=50元 50/5=10人,即10人仅玩其中一种。 75-(20+35+10)=10人,即10人没玩过其中任何一种。 第六套: 1、解:原始:{32,74,25,53,28,43,86,47} ① {25,74,32,53,28,43,86,47} ② {25,28,32,53,74,43,86,47} ③ {25,28,32,43,74,53,86,47} ④ {25,28,32,43,47,53,86,74} ⑤ {25,28,32, 43, 47, 53, 74,86} 最少要交换5次。 2、解:依题意:物{张、王},化{张,李,赵},生{李、赵、陈} 穷举每种情况: 当物理组选张时,有四种选择方案: {张,李,赵},{张,李,陈},{张,赵,李},{张,赵,陈} 当物理组选王时,有七种选择方案: {王,张,李},{王,张,赵},{王,张,陈},{王,李,赵} {王,李,陈},{王,赵,李},{王,赵,陈},共11种选择方案。

补充一,填空: 我国先后自行研制成功“银河”系列的巨型计算机,其中: “银河”于1983年问世,其运算速度为每秒_______次; 1亿 10亿 “银河II”于1992年诞生,其运算速度为每秒_______次; 130亿 “银河III”于1997年通过国家鉴定,其运算速度为每秒______次。 补充二,选择题: 已知A=16H,B=31H,C=20H,那么(A∨B)∧(A∨C)的值是 C A、44H B、45H C、46H D、47H 解:A=16H=00010110B,B=31H=00110001B,C=20H=00100000B 00010110 00010110 ∨ 00110001 ∨ 00100000 -----------------------00110111 00110110 00110111 ∧ 00110110 -----------00110110

一、完善程序题选讲 1、初赛模拟题(二)第1题:
【问题描述】 倒蛇形矩阵填数。任给一个正整数 N(N≤20),将 1 至 N*N 的数分别填入矩阵,在显示器上输出如 下格式的矩阵。例如: N=3,输出矩阵为: N=5,输出矩阵为: 9 7 6 25 23 22 16 15 8 5 2 24 21 17 14 7 4 3 1 20 18 13 8 6 19 12 9 5 2 11 10 4 3 1 【算法分析】 由于图案是正方形,所以只需把矩阵分割成两部分,即左上角部分和右下角部分。对于左上角部分,将 其斜向分割,可以把它看作一个三角形,即第 i 行有 i 个元素。对于行数 i 为奇数时,j 的变化为 i?1; 为偶数时,j 的变化为 1?i。每个元素在矩阵中的坐标位置也容易得到。对右下角部分,情况恰好相反, 可类似地解决。 将左上角和右下角的解决方法合在一起就得到问题的解。

【程序清单】 program test41; var t:array[1..20,1..20] of integer; k,n,i,j:integer; begin fillchar(t,sizeof(t),0); writeln(?Please input n:?); readln(n); if (n<1) or (n>20) then begin writeln(?Input data ERROR!?); halt; end; k:= ① for i:=1 to n do if not odd(i) then for j:=1 to i do begin ② dec(k); end else for j:=i downto 1 do begin ③

dec(k); end; k:=1; for i:=1 to ④ do if not odd(i) then for j:=1 to i do begin ⑤ inc(k); end else for j:=i downto 1 do begin ⑥ inc(k); end; for i:=1 to n do begin for j:=1 to n do write(t[i,j]:4); writeln end; end.

解题策略: 1、从头至尾通读程序(至少三遍),找出程序中:1)各变量的含 义;2)程序由哪几个模块(自然段)组成。 本程序中: t数组:存放蛇行矩阵各个数据元素;n:蛇行矩阵的边长;

i,j:循环变量;k:生成蛇行矩阵时的倒(正)计数器,即生成左上 角各元素时(沿斜线)赋值从大到小,生成右下角时(沿斜线)赋 值从小到大。 程序共有四个模块: ①判输入矩阵边长是否合法; ②根据当前行是奇偶行对矩阵的左上角各元素进行赋值; ③根据当前行是奇偶行对矩阵的右下角各元素进行赋值; ④输出结果。 2、前后连贯地通读某一模块,从易到难推敲各个填空部分应填入 的内容: 1)因为左上角部分三角形赋值变化从大到小,所以①应填入n*n; 2)若当前行(斜向)是偶数行例如:i=4时分析t数组应给哪些下标 变量赋值: i=4 : j=1 j=2 j=3 j=4 t[4,1]=19 t[3,2]=18 t[2,3]=17 t[1,4]=16 总结规律, ②应填入t[i-j+1,j]:=k;同理可得③也应填入t[i-j+1,j]:=k; 3、对于给定的n,下三角只有n-1行,所以④应填入n-1。

4、对于右下角矩阵各元素赋值时,也分为奇数与偶数(斜)行分 别处理,处理时,也是从三角形的顶点(右下角)开始,例如i=4 时,t数组的下标变化如下: i=4 j=1 j=2 j=3 j=4 t[2,5]=7 t[3,4]=8 t[4,3]=9 t[5,2]=10 (还要结合其它行的变化),总结出一般规律,⑤应填入: t[n-i+j,n-j+1]:=k;同理,⑥也应填入:t[n-i+j,n-j+1]:=k; 二、阅读程序写出程序运行结果题选讲 输入99 输出: 1、初赛题模拟题1: program t1; [分析] var n:integer; 1)本题属于递归调用,传入 function count(n:integer):integer; 的实参为99; begin if n=1 then count:=0 else 2)仔细观察,发现与角谷猜 if n mod 2=0 then count:=count(n div 2)+1 else 想十分相象; count:=count(n*3+1)+1; 3)递归调用分两步完成: end; begin (1)递推进栈过程:将所有 readln(n); 局部变量的值与下一步执行 writeln(count(n)); 的地址压入堆栈; end.

(2)回推出栈过程:将压入堆栈的变量按“后进先出”的原则依次弹出 堆栈并执行后续语句,直至栈空为止。 4)按角谷猜想,有 n=99时: 99*3+1=298 298/2=149 149*3+1=448 448/2=224 224/2=112 112/2=56 56/2=28 28/2=14 14/2=7 7*3+1=22 22/2=11 11*3+1=34 34/2=17 17*3+1=52 52/2=26 26/2=13 13*3+1=40 40/2=20 20/2=10 10/2=5 5*3+1=16 16/2=8 8/2=4 4/2=2 2/2=1 M=25 即经过25步以后n的值变成1,此为递推过程,此时,count的值为0。 5)再进行回推阶段:每次出栈,count的值都要加1,当最后一个 变量的值出栈时,count的值正好加到25,所以输出的结果为25。 6)可以输入本程序后,按CTRL+F3,按CTRL+F7,输入n,然后 单步执行程序,观察执行过程。 2、初赛题模拟题2:

program t2; var hi,lo:integer; procedure p1(m,n:integer;var hi,lo:integer); var i:integer; begin i:=n;hi:=0;lo:=0; Repeat i:=i-1;lo:=lo+m; if lo>=10000 then begin lo:=lo-10000; hi:=hi+1; end; until i=0; write(hi:4,',',lo:4); end;

begin p1(200,343,hi,lo); end. 将各个变量的值列表,观察并找 出变量的变化规律: m n hi lo i --------------------------200 343 0 0 343 200 342 400 341 600 340 800 339 …… …… 如下: 1)I从343起,每减少50,hi的值 变会增至10000, 2)此时,执行lo?lo-10000, hi?hi+1;……

3)当I减少至43时,hi的值为6,此后,当i的值减少到0时,lo的值 正好为8600; 4)输出结果为:6,8600。 while k<=n do 3、初赛模拟题4: begin program t4; x[k]:=i; var i,k,n:integer; k:=k+i; x,w:array[1..500] of integer; end; begin end; readln(n); for i:=n downto 1 do for i:=1 to n do if x[i]<>0 then begin begin x[i]:=0;w[i]:=1; w[x[i]]:=w[x[i]]+w[i]; end; w[i div x[i]]:=w[i div x[i]]+w[i]; for i:=2 to trunc(sqrt(n))+1 do w[i]:=0; if x[i]=0 then end; begin writeln(w[2],w[3]:5,w[5]:5); k:=i*i; end.

[分析] 本程序分两部分,第一部分:对x数组赋值部分,经细心计算,得出 x[4] x[6] x[8] x[10] x[14] x[16] x[18] x[20] x[9] x[12] x[15] x[18] 2 2 2 2 2 2 2 2 3 3 3 3 第二部分,经超细心计算,得出 w[2] w[3] w[5] 18 8 4 补充练习,若将本题的输出语句改为: writeln(w[1],w[7]:5,w[11]:5); 则输出结果为几? (本题实际上是计算20以内包括20的所有含有2的因子的个数的和)
4、初赛模拟题(二)第2题: 【问题描述】 以下程序完成对数组每个元素向后移动n个单位。数组元素的下标依次为0到 m-1,对任意一个数组元素a[i]而言,它的值移动后将存储在数组元素 a[(i+n) mod m]中。 例如,m=10,n=3,移动前数组中存储的数据如下面前一行所示,则程序运行后 数组中存储的数据如下面后一行所示。 0 3 86 20 27 67 31 16 37 42 16 37 42 0 3 86 20 27 67 31

program test42; const maxm=10000; var i,k,m,n,rest,start,temp:longint ; a:array[0..maxm] of longint; begin write(?input m,n:?); readln(m,n); for i:=0 to m-1do a[i]:=random(100); writeln(?before move?); for i:=0 to m-1 do write(a[i]:5); writeln; rest:=m;start:=0; while ① do begin k:=start;

repeat k:= ② until k<=start; if ③ then begin temp:=a[k]; repeat a[k]:=a[(m*n+k-n) mod m]; k:= ④


until k=start;


end;


end; writeln(?after move?); for i:=0 to m-1 do write(a[i]:5); writeln; end.

本题填空依次为 ①rest>0 ②(k+n)mod m; ③k=start ④(m*n+k-n)mod m; ⑤rest:=rest-1;⑥a[(k+n)mod m]:=temp; ⑦start:=start+1; 5、初赛模拟题(二)第3题: 【问题描述】 有甲、乙、丙三个人和A、B、C三项不同的工作,每人一天只能 干一项工作,且一项工作每天必须一个人干。下表表示的是甲、 乙、丙三个人在A、B、C三个不同的工作岗位上工作一天所能创 造的价值: ABC甲305025乙353020丙454030说明:甲在A岗位上干一天所创 造的价值为30,在B岗位上干一天所创造的价值为50… 请编程确定如何分配工作(甲、乙、丙三人在什么工作岗位), 三人一天共同创造的价值最多。 【程序清单】

program test43; var i,j,a,b,c,ma,mb,mc,s,m:integer; v:array [1..3,1..3] of integer; if s > m then begin begin m:=0; ③ for i:= 1 to 3 do ma:=a; for j:= 1 to 3 do mb:=b; read(v[i,j]); mc:=c for a:= 1 to 3 do end; for b:= 1 to 3 do end; begin end; c:= ① writeln('Jia:',CHR(64+ma),'Yi:':10, if a*b*c=6 then CHR(64+mb),'Bing:':10,CHR(64+mc)); begin writeln('M=',m) s:= ② end.

[分析] 本题算法采用“穷举法”,找出创造的最多价值?m,甲、乙、丙 所做的工作编号依次?ma、mb、mc。a,b,c依次表示甲、乙、丙 三人所做工作编号。 第一部分,读入数据: v[1,1] v[1,2] v[1,3] 30 50 25 v[2,1] v[2,2] v[2,3] 35 30 20 v[3,1] v[3,2] v[3,3] 45 40 30 第二部分,利用二重循环穷举三人工作的各种情况, ①应填入: 6-a-b; if a*b*c=6表示甲、乙、丙做了不同的工作,所以②应填入: v[1,a]+v[2,b]+v[3,c];即s表示在当前情况下甲、乙、丙三人共同创造 的价值;所以③应填入: m:=s; 第三部分,输出结果。

补充练习: 1、一棵二叉树的先序、中序和后序序列分别如下,其中有 一部分未显示出来。试求出空格处的内容,并画出该二叉树。 先序序列:__B__F__ICEH__G 中序序列:D__KFIA__EJC__ 后序序列:__K__FBHJ__G__A 解:由这些显示部分推出二叉树如下图所示。则 A B D K F I H E J C G

先序序列为ABDFKICEHJG;

中序序列为DBKFIAHEJCG;
后序序列为DKIFBHJEGCA。

2、平面上有五个点A(5,3),B(3,5),C(2,1),D(3,3),E(5,1)。以这 五个点作为完全图G的顶点,每两点之间的直线距离是图G中对应 边的权值。以下哪条边不是图G的最小生成树中的边( )。 A、AD B、BD C、CD D、DE E、EA 解:根据两点间距离公式:
| p1 p2 |? ( x1 ? x2 ) 2 ? ( y1 ? y2 ) 2
2 2

计算10条边的权值如右图所示: 由最小生成树的定义,生成树 中边的权值之和最小的生成树 称为最小生成树。知:
DE的权值 ? 2 2为最大,故选 。 D

2
17

2
2 2

5
13

2 5 2

3


相关文章:
NOIP复习资料(C++版)
NOIP复习资料(C++版)_学科竞赛_高中教育_教育专区。noip 前言NOIP 复习资料(C++版) 主 编 葫芦岛市一高中 李思洋 完成日期 2012 年 8 月 27 日 0 前言 前言...
NOIP复习资料
int max,p; for (int i=1;i<=n;i++) { max=p=0; for (int j=1;j<=i;j++) { // p表示终点的位置 36 NOIP 复习资料(C++版) f[i][j] ...
noip初赛复习资料(全)
noip初赛复习资料(全)_学科竞赛_高中教育_教育专区。noip初赛复习资料(全) 分区联赛初赛复习初赛考的知识点就是计算机基本常识、 基本操作和程序设计基础知识。 其中...
2016NOIP初赛复习资料
2016NOIP初赛复习资料_其它考试_资格考试/认证_教育专区。NOIP初赛复习资料 全国分区联赛初赛复习初赛考的知识点就是计算机基本常识、 基本操作和程序设计基础知识。 ...
noip复习资料(提高组c++版)
前言NOIP 复习资料(C++版) 主 编 葫芦岛市一高中 李思洋 完成日期 2012 年 8 月 27 日 0 前言 前言 有一天,我整理了 NOIP 的笔记,并收集了一些经典算法。...
NOIP提高组复习资料(C++版)
前言NOIP 复习资料(C++版) 主 编 葫芦岛市一高中 李思洋 完成日期 2012 年 8 月 27 日 0 前言 前言 有一天,我整理了 NOIP 的笔记,并收集了一些经典算法。...
noip复习资料
noip复习资料 隐藏>> 素数: function judge(p:longint):boolean; var i:longint; begin if i<2 then exit(false); if (i=2)or(i=3)then exit(true)...
NOIP复赛复习资料汇总
NOIP复赛复习资料汇总_IT认证_资格考试/认证_教育专区。noip复赛资料 NOIP 复赛知识总结 (一) Pascal 过程与函数调用 * abs(x):y 取 x 的绝对值,x 与 y ...
NOIP复习资料
G.基数排序 思想:对每个元素按从低位到高位对每一位进行一 次排序 Noip 复习资料 五、高精度计算高精度数的定义: type hp=array[1..maxlen] of integer; 1...
NOIP复习资料终极版
宜昌一中 2009NOIP 复习资料 宜昌一中 2009NOIP 复习资料 感谢唐弢(TT) ,刘炟呈(CRL) ,陈艺(衬衣) ,猫(向缪丹妮) 等众位大牛的倾力支持 特别感谢袁逸铭(...
更多相关标签: