1、一、 计算机的发展、类型及其应用领域。1. 计算机(computer)是一种能自动、高速进行大量算术运算和逻辑运算的电子设备。 其特点为：速度快、精度高、存储容量大、通用性强、具有逻辑判断和自动控制能力。2. 第一台计算机：ENIAC，美国，1946年 宾夕法尼亚大学 冯诺依曼 “存储程序”和“程序控制”3. 冯诺依曼思想的核心要点是： 1)计算机的基本结构应由五大部件组成：运算器、控制器、存储器、输入设备和输出设备。 2)计算机中应采用二进制形式表示数据和指令。 3)采用“存储程序”和“程序控制”的工作方式。 4. 计算机的发展过程阶段年份物理器件软件特征应用范围第一代1946-1959电子
2、管机器语言、汇编语言科学计算第二代1959-1964晶体管高级语言科学计算、数据处理、工业控制第三代1964-1970小规模集成电路操作系统科学计算、数据处理、工业控制、文字处理、图形处理第四代1970-至今大规模集成电路数据库网络等各个领域5. 主要特点：运算速度快、精确度高、具有记忆和逻辑判断能力6. 计算机的主要应用科学计算：例如：气象预报、海湾战争中伊拉克导弹的监测数据/信息处理：例如：高考招生中考生录取与统计工作，铁路、飞机客票的预定系统，银行系统的业务管理计算机控制计算机辅助系统：例如：用CAI演示化学反应人工智能：例如：代替人类到危险的环境中去工作办公自动化系统中的应用：例如：I
3、nternet发emailCBE:计算机辅助教育CAI:计算机辅助教学CMI:计算机管理教学CAD:计算机辅助设计CAT:计算机辅助翻译CAM:计算机辅助制造CAE:计算机辅助工程7. 计算机的分类：1）、根据规模大小分类：巨型机、大型通用机、微型机、工作站、服务器2）、根据用途分类：通用计算机、专用计算机3）、根据计算机处理数据的类型：模拟计算机、数字计算机、数字与模拟计算机8. 计算机科学研究与应用人工智能：研究如何让计算机来完成过去只有人才能做的智能的工作。网格计算：专门针对复杂科学计算的新型计算模式。中间件技术：是介于应用软件和操作系统之间的系统软件。云计算：是分布式计算、网格计算、并
4、行计算、网络存储及虚拟化计算机和网络技术发展融合的产物，或者说是它们的商业实现，。二、 计算机中数据的表示与存储。1 数制二进制的优点： 技术实现简单 简化运算规则 适合逻辑运算 易于进行转换各种进制的后缀 B：二进制 D：十进制 H：十六进制 O：八进制2数据的存储1) 数据：所有能够被计算机接受和处理的符号的集合都称为数据2) 信息：有意义的数据的内容。指数据经过加工处理后得到的有价值的知识。3) 位（Bit） 每一个能代表0和1的电子线路称为一个二进制位，是数据的最小单位。 4) 字节（Byte） 通常每8个二进制位组成一个字节，字节是最基本的存储单位。字节的容量一般用KB、MB、GB、
5、TB来表示，它们之间的关系如下： 1KB=1024B 1MB=1024KB 1GB=1024MB 1TB=1024GB 5) 字长（Word） 在计算机中作为一个整体被存取、传送、处理的二进制数字串叫做一个字或单元，每个字中二进制位数的长度，称为字长。一个字由若干个字节组成，不同的计算机系统的字长是不同的，常见的有8位、16位、32位、64位等。字长是计算机的一个重要指标，直接反映一台计算机的计算能力和精度。字长越长，存放数的范围越大，计算机的数据处理速度越快。 6) 地址(Address) 为了便于存取，每个存储单元必须有唯一的编号，这个编号就称为地址，通过地址可以找到所需的存储单元，取出或
6、存入信息。 1.4.3 编码1字符编码 目前国际上通用的字符编码是ASCII码，即美国标准信息交换代码。 ASCII码用七位二进制数表示一个字符，可表示27共128个字符。包括：32个通用控制符、10个十进制数字、52个大小写英文字母和34个专用符号。在一个字节（8个Bit）中后七位用于表示字符的编码，最高位为奇偶校验位，一般作0看待。 2. 汉字编码ASCII码只对英文字母、数字和标点符号进行了编码。同样，要想处理汉字，也要对汉字进行统一编码，给每个汉字一个惟一的编码，我国于1980年发布了国家汉字编码标准GB2312-1990。汉字数量庞大，用一个字节无法区分，故汉字编码采用2个字节。 一
7、个汉字占用二个字节 一个字符占用一个字节N*N点阵的汉字所用的空间是N*N/8国标码、机内码、区位码的关系国标码=区位码+2020H机内码=国标码+8080H机内码=区位码+a0a0H三、 计算机软硬件系统的组成及主要技术指标。计算机硬件系统均由运算器、控制器、存储器、输入设备和输出设备五大部分构成运算器：算术运算和逻辑运行的实际执行部件。控制器：统一指挥和控制计算机各部件按时序协调操作的部件中央处理器CPU=运算器+控制器 是计算机的核心部件内部存储器按其存储信息的方式可以分为只读存储器ROM(Read Only Memory)、随机存储器RAM(Random Access Memory)和
8、高速缓冲存储器CacheRAM：随机存储器 能读能写，断电后信息丢失 DRAM:动态RAM，相当于CACHE(高速缓冲存储器) CACHE:CPU与内存之间速度不彼配的问题 SRAM：静态RAM ROM：只读存储器 能读不能写，断电后信息不丢失输入设备：键盘、鼠标、扫描仪、光笔输出设备：显示器、音箱、打印机、绘图仪总线：数据总线、地址总线、控制总线软件：由程序、数据和文档三部分内容组成。 程序：是一系列有序指令的集合。 计算机之所以能够自动而连续地完成预定的操作，就是运行特定程序的结果。计算机程序通常是由计算机语言来编制，编制程序的工作称为程序设计。 数据：指各种信息集合，数值的与非数值的。文
9、档：用自然语言（汉语或英语）对程序进行描述的文本称为文档。 1. 系统软件：是指管理、监控和维护计算机资源（包括硬件和软件）的软件。系统软件主要包括操作系统、各种语言处理程序、数据库管理系统、网络系统及服务性程序。核心是：操作系统、语言处理程序和各种服务性程序。 (1) 操作系统 操作系统是管理、控制计算机的软、硬件和数据资源的大型程序，是用户和计算机之间的接口，并提供了软件的开发和应用环境。 微机操作系统当前主流是Microsoft公司的DOS（单用户单任务）操作系统和Windows（单用户多任务）操作系统(2) 语言处理程序 机器语言是用二进制代码编写，能够直接被机器识别的程序设计语言。高
10、级语言编写的程序（称为“源程序”）翻译成机器语言程序（称为“目的程序”），然后计算机才能执行。这种翻译过程一般有两种方式：解释方式和编译方式CPU的主要性能指标有两个：字长和主频。 字长(位)：CPU进行运算和数据处理的最基本、最有效的信息位长度。字长越长，性能越强。PC机的字长，已由8088的准16位(运算用16位，IO用8位)发展到现在的32位、64位。 主频(Mhz)：CPU工作的时钟频率。主频越高处理数据速度越快。 目前最常用的外存有软盘、硬盘和光盘 。 用于存放暂时不用的程序和数据，它不能直接被CPU访问，但它可以与内存成批交换信息，即外存中的信息只有被调入内存才能被CPU访问。外存
11、相对于内存而言，其特点是：存取速度较慢，但存储容量大，价格较低，信息不会因掉电而丢失。按工作原理鼠标可分为：机械式和光电式目前广泛使用的监视器是阴极射线管（CRT）监视器和液晶（LCD）监视器。后者主要用于笔记本电脑显示器最重要的性能指标是分辨率，打印机分为击打式和非击打式两大类。击打式打印机主要有针式打印机（又称点阵打印机），非击打式以喷墨打印机和激光打印机为代表。四、 多媒体技术的概念与应用。1多媒体的概念 多媒体一词来源于英文单词Multimedia，其中，Multi为“多”，media为“媒体”的意思。媒体也称介质或媒质，是信息表示和传播的载体，它在计算机领域中有两种含义，一是指用以存
12、储信息的实体，如磁盘、磁带、光盘和半导体存储器；另一种含义是指信息的载体，如数字、文字、声音、图形和图像。 多媒体技术是指把文字、音频、视频、图形、图像、动画等多媒体信息通过计算机进行数字化采集、获取、压缩/解压缩、编辑、存储等加工处理，再以单独或合成形式表现出来的一体化技术。 2多媒体的特征：交互性、集成性、多样性、实时性3. 媒体的数字化声音的数字化的过程：采样、量化、编码位图图像(bitmap)：位图放大称为点阵图像或绘制图像，是由称作像素（图片元素）的单个点组成的。这些点可以进行不同的排列和染色以构成图样。当放大位图时，可以看见赖以构成整个图像的无数单个方块。扩大位图尺寸的效果是增多单
13、个像素，从而使线条和形状显得参差不齐。然而，如果从稍远的位置观看它，位图图像的颜色和形状又显得是连续的。矢量图：矢量图使用直线和曲线来描述图形，这些图形的元素是一些点、线、矩形、多边形、圆和弧线等等，它们都是通过数学公式计算获得的。例如一幅花的矢量图形实际上是由线段形成外框轮廓，由外框的颜色以及外框所封闭的颜色决定花显示出的颜色。由于矢量图形可通过公式计算获得，所以矢量图形文件体积一般较小。矢量图形最大的优点是无论放大、缩小或旋转等不会失真。五、 计算机病毒的特征、分类与防治。1. 计算机病毒的概念计算机病毒（Computer Viruses CV）：是一种人为编制的具有破坏作用的计算机程序。
14、2. 计算机病毒的的特征（特点） 破坏性 传染性 隐蔽性 潜伏性 可激发性 3.计算机病毒的分类 根据病毒存在的媒体分类 根据病毒存在的媒体，病毒可以划分为网络病毒，文件病毒，引导型病毒 根据病毒破坏的能力分类 无害型：除了传染时减少磁盘的可用空间外，对系统没有其它影响。 无危险型：这类病毒仅仅是减少内存、显示图像、发出声音及同类音响。 危险型：这类病毒在计算机系统操作中造成严重的错误。 非常危险型：这类病毒删除程序、破坏数据、清除系统内存区和操作系统中重要的信息。 根据病毒特有的算法分类 伴随型病毒：这一类病毒并不改变文件本身，它们根据算法产生EXE文件的伴随体，具有同样的名字和不同的扩展名
15、（COM），例如：XCOPY.EXE的伴随体是XCOPY.COM。 蠕虫”型病毒：通过计算机网络传播，不改变文件和资料信息，利用网络从一台机器的内存传播到其它机器的内存，计算网络地址，将自身的病毒通过网络发送。有时它们在系统存在，一般除了内存不占用其它资源。 寄生型病毒：除了伴随和“蠕虫”型，其它病毒均可称为寄生型病毒，它们依附在系统的引导扇区或文件中，通过系统的功能进行传播，按算法分为： 练习型病毒：病毒自身包含错误，不能进行很好的传播，例如一些病毒在调试阶段，还不具备发作的条件 。诡秘型病毒：它们一般不直接修改DOS中断和扇区数据，而是通过设备技术和文件缓冲区等DOS内部修改，不易看到资源
16、，使用比较高级的技术。利用DOS空闲的数据区进行工作。 变型病毒（又称幽灵病毒）：这一类病毒使用一个复杂的算法，使自己每传播一份都具有不同的内容和长度。4. 计算机病毒的防治 病毒的防范 计算机病毒的传播途径主要有两个：软盘和网络。要防止病毒的侵入，就要以预防为主，堵塞病毒的传播途径。 病毒的检测和消除 检测和消除病毒的方法有两种，一是人工检测和消除，一是软件检测和消除。 六、 计算机网络的概念、组成和分类； 计算机网络概述1、计算机网络的定义 计算机网络指利用通信设备和线路将地理位置不同的功能、多个计算机系统互联起来，以功能完善的网络软件实现网络中资源共享和信息交换的系统。“资源共享”是计算
17、机网络的功能，资源包括计算机硬件资源和软件资源。2、计算机网络的主要功能 资源共享(基础) 信息交换 分布式处理 集中管理3、计算机网络的分类 依据不同有不同的分类。1）根据规模大小、距离远近分类：局域网（LAN）、城域网（MAN）、广域网（WAN） 2）根据网络操作系统分类： NIX网络、NOVELL网络、Windows NT网络3） 根据信息传输技术分类：广播式网络、点到点网络4）根据连接方式分类：总线型、星型、环型、树型和混合型等。4、计算机网络的基本组成 网络操作系统、网络适配器（网卡）、网络电缆（网络线）、服务器和工作站等。计算机网络的互联技术1、网络的拓扑结构：总线结构、星型结构、
18、环型结构、树型结构、混合型结构2、网络体系结构 1)通信协议在计算机网络中，信息传输顺序、信息格式和信息内容等都有一系列的约定，这些约定或规则统称为计算机网络通信协议。2)开放式系统互连OSI（Open System Interconnection）参考模型国际标准化组织ISO于1978年制定了OSI参考模型。3、常见的传输介质1）双绞线电缆三类线：最高传输速率为10Mbps 。五类线：最高传输速率为100Mbps 。六类线：传输速率至少为250Mbps 。七类线：传输速率至少为600Mbps 。2）同轴电缆同轴电缆由内、外两个导体组成。内导体可为单股线或多股线，外导体为金属编织网，内、外导体
19、之间有绝缘材料。3）光缆: 光缆分为单模光缆和多模光缆。4）无线传送介质：微波、红外线、卫星通信、激光等。4、互联网络设备1）计算机设备服务器：是网络的核心设备，负责网络资源管理和用户服务。工作站：是具有独立处理能力的个人计算机，负责用户的信息处理业务。共享设备：是指为众多用户提供共享的打印机、磁盘子系统等公用的设备。2）常用网络连接设备网络适配器：网络适配器也称网卡，它是网络中计算机与计算机之间互相通信的接口。中继器：在网络中起到扩展局域网络连网距离的作用，在OSI模型的最低层（物理层）。集线器：集线器（Hub）是网络中的中心设备，它为一组计算机用户提供网络连接。网桥：为网间连接设备，它对网
20、络中的数据包起到“过滤和转发”的作用，它工作在OSI模型的第二层（数据链路层）路由器：为不同类型的网络提供互联。不仅具有网桥的全部功能，还具有路径的选择功能，它属于OSI模型第三层设备（网络层）。七、 计算机与网络信息安全的概念和防控。 1. 计算机安全定义国际标准化组织（ISO）对计算机安全的定义是：为数据处理系统建立和采取的技术上和管理上的安全保护，保护计算机硬件、软件不因偶然的或恶意的原因而遭破坏、更改和暴露。 2. 计算机安全立法国务院于1994年2月18日颁布的中华人民共和国计算机信息系统安全保护条例第一章第三条的定义是：计算机信息的安全保护，应当保障计算机及其相关的配套设备设施（含
21、网络）的安全，运行环境的安全，保障信息的安全，保障计算机功能的正常发挥，以维护计算机信息系统的安全运行。 3计算机安全操作计算机使用环境：温度在室温15C 35C之间；相对湿度在20%80%之间；对电源一要要求稳，二是在机器工作时供电不能间断；在计算机的附近避免磁场干扰。 计算机的维护：要注意防潮、防水、防尘、防火，在使用时注意通风，不用时应盖好防尘罩，机器表面要用软布沾中性清洁剂经常擦拭。 开机顺序为：先对外设加电，再对主机加电；而关机顺序正好与此相反；每次开机与关机之间的间隔不应少于10秒。在加电情况下，机器的各种设备不要随意搬动，也不要插拔各种接口卡。应避免频繁开关机器，计算机要经常使用
22、，不要长期闲置不用。 4计算机安全管理为了保证计算机的安全使用，在日常工作中要做好以下方面的工作： 系统启动盘要专用，对来历不明的软件不应马上装入自己的计算机系统，要先检测，后安装使用。 对系统文件和重要数据，要进行备份和写保护。 对外来软盘和盗版光盘，必须进行检测方可使用。 不要轻易装入各种游戏软件，游戏软件通过存储介质将病毒带入计算机系统的可能性极大。 定期对所使用的磁盘进行病毒的检测与防治。 若发现系统有任何异常现象，及时采取措施。 对于连网的计算机，在下载软件时要特别注意，不要因此而将病毒一并带入计算机 八、 因特网网络服务的概念、原理和应用。1. Internet 的定义Intern
23、et （因特网）是由全球范围内的开放式计算机网络连接而成的计算机互联网。也可以简单定义为网络的网络、网络的集合。2. 我国Internet发展现状至2000年底，全国性的互联网有8个，其中经营性的5个，非经营性的3个。经营性的5个：中国公用计算机互联网（CHINANET）：由中国电信负责建设与经营管理。中国金桥信息网（CHINAGBNET）：由吉通通信有限公司建设与经营管理。中国联通公用计算机互联网（UNINET）：由中国联合通信有限公司负责建设与经营管理。中国网通公用互联网（CNCNET）：由中国网络通信有限责任公司负责建设与经营管理。中国移动互联网（CMNET）：中国移动通信集团公司负责建
24、设与经营管理。非经营性3个：中国教育科研网（CERNET）：中国教育科研网由国家投资建设，教育部负责管理。中国科技网（CSTNET）：中国科技网由国家投资和世界银行贷款建设，由中国科学院网络运行中心负责运行管理。中国国际经济贸易互联网（CIETNET）：面向全国外经贸系统事业单位的专用互联网。由外贸经济合作部下属的中国国际电子商务中心负责建设和管理。 Internet 的几个关键概念1、TCP/IP协议 TCP/IP协议是Internet互联网的信息交换、规则、规范的集合体。 分类：TCP传输控制协议和IP网间协议。四个层次：应用层、传输层、互联层、主机至网络层2、IP地址 Internet中
25、每一台计算机都有一个在世界范围内惟一的标记，这个标记我们称为IP地址。IP地址是一个32位的二进制数，一般用圆点分隔的十进制数表示，如：210.37.7.18 。范围02553、DNS域名系统 域名系统DNS是完成Internet 主机名和IP地址的映射，把域名翻译成IP地址的系统，同时也可以将IP地址翻译成域名。域名的一般格式为：.。机 构 com 商业机构 edu 教育机构 gov 政府机构 int 国际组织 mil 军事部门 net 网络机构 org 社会组织、专业协会Internet 接入方式1、拨号入网 主要适用于单位或家庭单机入网。除需要一台微机外，还需要： 1）一个调制解调器（M
26、odem）（传输速率33.6Kbps以上）； 2）电话线（脉冲、音频、直线、分机均可）； 3）拨号上网软件和IE浏览器； 4）账号。2、局域网接入方式 通过网络专线（一般为双绞线）连接局域网，从而进入Internet，适用于有局域网的单位。这种入网方式除需要一台微机外，还需要： 在计算机上安装一个网卡；上网软件和IE浏览器； IP地址。 Internet 的主要应用WWW服务WWW（World Wide Web）意译为“环球网”，音译为“万维网”，它是建立在TCP/IP基础上的，采用客户机/服务器工作模式的一种网络应用。它将分散在世界各地专门存放和管理WWW资源的Web服务器中的信息，用超文本
27、方式链接在一起，供互联网上的计算机用户查询和调用。WWW是当前应用最为广泛的Internet服务。1、WWW的工作原理 WWW系统采用客户/服务器的工作方式。2、关键术语解释1）超文本2）超媒体3）HTML（Hyper Text Markup Language）4）主页5）统一资源定位器（URL）3、IE浏览器 1）IE浏览器画面的组成 标题栏、菜单栏、飞行标志、地址栏、链接栏、电台栏、工作区、状态栏电子邮件1、什么是电子邮件 电子邮件（E-mail），指计算机之间通过网络及时传送信件、文档或图像等信息。2、电子邮件的工作原理 采取“存储转发”的方式：从始发计算机取出邮件，在网络传输过程中经过
28、多个计算机的中转，最后到达目标计算机，送进收信人的电子邮箱。 邮件地址格式：用户名收信服务器域名。如：lm 。3、电子邮件软件的应用4、免费电子邮件的申请文件传输文件传输是Internet为各主机间进行文件传输而提供的一种服务，指将一台计算机的文件传输到另一台计算机上去。在互联网上实现文件传输的软件是传输协议（File Transfer Protocol），简称为FTP。Internet其他应用网上聊天、网络寻呼（OICQ）、网上购物、 IP电话、网络游戏等。 第一部分公共基础知识第1章数据结构与算法11算法1算法的基本概念(1)概念：算法是指一系列解决问题的清晰指令。(2)4个基本特征：可行
29、性、确定性、有穷性、拥有足够的情报。(3)两种基本要素：对数据对象的运算和操作、算法的控制结构(运算和操作时问的顺序)。(4)设计的基本方法：列举法、归纳法、递推法、递归法、减半递推技术和回溯法。2算法的复杂度(1)算法的时间复杂度：执行算法所需要的计算工作量。(2)算法的空间复杂度：执行算法所需的内存空间。12数据结构的基本概念数据结构指相互有关联的数据元素的集合，即数据的组织形式。其中逻辑结构反映数据元素之间逻辑关系；存储结构为数据的逻辑结构在计算机存储空间中的存放形式，有顺序存储、链式存储、索引存储和散列存储4种方式。数据结构按各元素之间前后件关系的复杂度可划分为：(1)线性结构：有且只
30、有一个根节点，且每个节点最多有一个直接前驱和一个直接后继的非空数据结构。(2)非线性结构：不满足线性结构的数据结构。13线性表及其顺序存储结构1线性表的基本概念线性结构又称线性表，线性表是最简单也是最常用的一种数据结构。2线性表的顺序存储结构元素所占的存储空间必须连续。元素在存储空间的位置是按逻辑顺序存放的。3线性表的插入运算在第i个元素之前插入一个新元素的步骤如下：步骤一：把原来第n个节点至第i个节点依次往后移一个元素位置。步骤二：把新节点放在第i个位置上。步骤三：修正线性表的节点个数。在最坏情况下，即插入元素在第一个位置，线性表中所有元素均需要移动。4线性表的删除运算删除第i个位置的元素的
31、步骤如下：步骤一：把第i个元素之后不包括第i个元素的n-i个元素依次前移一个位置；步骤二：修正线性表的结点个数。14栈和队列1栈及其基本运算(1)基本概念：栈是一种特殊的线性表，其插入运算与删除运算都只在线性表的一端进行，也被称为“先进后出”表或“后进先出”表。栈顶：允许插入与删除的一端。栈底：栈顶的另一端。空栈：栈中没有元素的栈。(2)特点。栈顶元素是最后被插入和最早被删除的元素。栈底元素是最早被插入和最后被删除的元素。栈有记忆作用。在顺序存储结构下，栈的插入和删除运算不需移动表中其他数据元素。栈顶指针top动态反映了栈中元素的变化情况(3)顺序存储和运算：入栈运算、退栈运算和读栈顶运算。2
32、队列及其基本运算(1)基本概念：队列是指允许在一端进行插入，在另一端进行删除的线性表，又称“先进先出”的线性表。队尾：允许插入的一端，用尾指针指向队尾元素。排头：允许删除的一端，用头指针指向头元素的前一位置。(2)循环队列及其运算。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。入队运算是指在循环队列的队尾加入一个新元素。当循环队列非空(s=1)且队尾指针等于队头指针时，说明循环队列已满，不能进行人队运算，这种情况称为“上溢”。退队运算是指在循环队列的队头位置退出一个元素并赋给指定的变量。首先将队头指针进一，然后将排头指针指向的元素赋给指定的变量。当循环队列
33、为空(s=0)时，不能进行退队运算，这种情况称为“下溢”。15线性链表在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。16树和二叉树1树的基本概念树是简单的非线性结构，树中有且仅有一个没有前驱的节点称为“根”，其余节点分成m个互不相交的有限集合T1，T2，Tmm，每个集合又是一棵树，称T1，T2，Tmm为根结点的子树。父节点：每一个节点只有一个前件，无前件的节点只有一个，称为树的根
34、结点(简称树的根)。子节点：每个节点可以后多个后件，无后件的节点称为叶子节点。树的度：所有节点最大的度。树的深度：树的最大层次。2二叉树的定义及其基本性质(1)二叉树的定义：二叉树是一种非线性结构，是有限的节点集合，该集合为空(空二叉树)或由一个根节点及两棵互不相交的左右二叉子树组成。可分为满二叉树和完全二叉树，其中满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。二叉树具有如下两个特点：二叉树可为空，空的二叉树无节点，非空二叉树有且只有一个根结点；每个节点最多可有两棵子树，称为左子树和右子树。(2)二叉树的基本性质。性质1：在二叉树的第k层上至多有2k-1个结点(k1)。性质2：深度为
35、m的二叉树至多有2m-1个结点。性质3：对任何一棵二叉树，度为0的结点(即叶子结点)总是比度为2的结点多一个。性质4：具有n个结点的完全二叉树的深度至少为log2n+1，其中log2n表示log2n的整数部分。3满二叉树与完全二叉树(1)满二叉树：满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。满二叉树在其第i层上有2i-1个结点。从上面满二叉树定义可知，二叉树的每一层上的结点数必须都达到最大，否则就不是满二叉树。深度为m的满二叉树有2m-1个结点。(2)完全二叉树：完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若
36、干结点。如果棵具有n个结点的深度为k的二叉树，它的每个结点都与深度为k的满二叉树中编号为1n的结点对应。3二叉树的存储结构二叉树通常采用链式存储结构，存储节点由数据域和指针域(左指针域和右指针域)组成。二叉树的链式存储结构也称二叉链表，对满二叉树和完全二叉树可按层次进行顺序存储。4二叉树的遍历二叉树的遍历是指不重复地访问二叉树中所有节点，主要指非空二叉树，对于空二叉树则结束返回。二叉树的遍历包括前序遍历、中序遍历和后序遍历。(1)前序遍历。前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历
37、左子树，最后遍历右子树。前序遍历描述为：若二叉树为空，则执行空操作；否则访问根结点；前序遍历左子树；前序遍历右子树。(2)中序遍历。中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。中序遍历描述为：若二叉树为空，则执行空操作；否则中序遍历左子树；访问根结点；中序遍历右子树。(3)后序遍历。后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结
38、点。后序遍历描述为：若二叉树为空，则执行空操作；否则后序遍历左子树；后序遍历右子树；访问根结点。17查找技术(1) 顺序查找：在线性表中查找指定的元素。(2) 最坏情况下，最后一个元素才是要找的元素，则需要与线性表中所有元素比较，比较次数为n。(2)二分查找：二分查找也称折半查找，它是一种高效率的查找方法。但二分查找有条件限制，它要求表必须用顺序存储结构，且表中元素必须按关键字有序(升序或降序均可)排列。对长度为n的有序线性表，在最坏情况下，二分查找法只需比较log2n次。18排序技术(1)交换类排序法。冒泡排序：通过对待排序序列从后向前或从前向后，依次比较相邻元素的排序码，若发现逆序则交换，
39、使较大的元素逐渐从前部移向后部或较小的元素逐渐从后部移向前部，直到所有元素有序为止。在最坏情况下，对长度为n的线性表排序，冒泡排序需要比较的次数为n(n-1)2。快速排序：是迄今为止所有内排序算法中速度最快的一种。它的基本思想是：任取待排序序列中的某个元素作为基准(一般取第一个元素)，通过一趟排序，将待排元素分为左右两个子序列，左子序列元索的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。最坏情况下，即每次划分，只得到一个序列，时间效率为O(n2)。(2)插人类排序法。简单插入排序法：把n个待排序的元素看成为一个有
40、序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。在最坏情况下，即初始排序序列是逆序的情况下，比较次数为n(n-1)2，移动次数为n(n-1)2。希尔排序法：先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序。待整个序列中的元素基本有序(增量足够小)时，再对全体元素进行一次直接插入排序。(3)选择类排序法。简单选择排序法：扫描整个线性表。从中选出最小的元素。将它交换到表的最前面；然后对剩下的子
41、表采用同样的方法，直到子表空为止。最坏情况下需要比较n(n-1)2次。堆排序的方法：首先将一个无序序列建成堆；然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，将该子序列调整为堆。反复做步骤，直到剩下的子序列空为止。在最坏情况下，堆排序法需要比较的次数为0(nlog2n)第2章程序设计基础21程序设计方法与风格(1)设计方法：指设计、编制、调试程序的方法和过程，主要有结构化程序设计方法、软件工程方法和面向对象方法。(2)设计风格：良好的设计风格要注重源程序文档化、数据说明方法、语句的结构和输入输出。
42、22结构化程序设计1结构化程序设计的原则结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。(1)自顶向下：即先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。(2)逐步求精：对复杂问题，应设计一些子目标做过渡，逐步细化。(3)模块化：把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块；(4)限制使用GOT0语句。2结构化程序的基本结构与特点(1)顺序结构：自始至终严格按照程序中语句的先后顺序逐条执行，是最基本、最普遍的结构形式。(2)选择结构：又称为分支结构，包括简单选择和多分支选择结构。(3)重复结构：又称为循环结构，根据给定的条件，
43、判断是否需要重复执行某一相同的或类似的程序段。结构化程序设计中，应注意事项：(1)使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑。(2)选用的控制结构只准许有一个人口和一个出口。(3)程序语言组成容易识别的块，每块只有一个入口和一个出口。(4)复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现。(5)语言中所没有的控制结构，应该采用前后一致的方法来模拟。(6)尽量避免GOT0语句的使用。23面向对象的程序设计面向对象方法的本质是主张从客观世界固有的事物出发来构造系统，强调建立的系统能映射问题域。对象：用来表示客观世界中任何实体，可以是任何有明确边界和意义的东西。类：具有
44、共同属性、共同方法的对象的集合。实例：一个具体对象就是其对应分类的一个实例。消息：实例间传递的信息，它统一了数据流和控制流。继承：使用已有的类定义作为基础建立新类的定义技术。多态性：指对象根据所接受的信息而作出动作，同样的信息被不同的对象接收时有不同行动的现象。面向对象程序设计的优点：与人类习惯的思维方法一致、稳定性好、可重用性好、易于开发大型软件产品、可维护性好。第3章软件工程基础31软件工程基本概念1软件的定义与特点(1)定义：软件是指与计算机系统的操作有关的计算机程序、规程、规则，以及可能有的文件、文档和数据。(2)特点。是逻辑实体，有抽象性。生产没有明显的制作过程。运行使用期间不存在磨
45、损、老化问题。开发、运行对计算机系统有依赖性，受计算机系统的限制，导致了软件移植问题。复杂性较高，成本昂贵。开发涉及诸多社会因素。2软件的分类软件可分应用软件、系统软件和支撑软件3类。(1)应用软件是特定应用领域内专用的软件。(2)系统软件居于计算机系统中最靠近硬件的一层，是计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务的软件。(3)支撑软件介于系统软件和应用软件之间，是支援其它软件的开发与维护的软件。3软件危机与软件工程软件危机指在计算机软件的开发和维护中遇到的一系列严重问题。软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序，包括软件开发技术和软件工程管理。4软件生命周期软件产品从提出、实现、使用维护到停止使用的过程称为软件生命周期。在国家标准中，软件生命周期划分为8个阶段软件定义期：包括问题定义、可行性研究和需求分析3个阶段。软件开发期：包括概要设计、详细设计、实现和测试4个阶段。运行维护期：即运行维护阶段。5软件工程的原则软件工程的原则包括：抽象、信息隐蔽、模块化
