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