计算机二级公共基础知识考点串讲汇总
- 格式:doc
- 大小:96.00 KB
- 文档页数:10
全国计算机二级公共基础知识汇总计算机二级公共基础知识是指计算机技术基础知识和应用能力的考核指标,主要包括计算机硬件知识、操作系统知识、计算机网络知识和应用软件知识等多个方面。
下面是对这些知识的详细汇总。
一、计算机硬件知识1.计算机硬件组成:CPU、内存、硬盘、显示器、键盘、鼠标等。
2.计算机的基本原理:二进制原理、信息表示与处理、逻辑门电路等。
3.中央处理器(CPU):主频、Cache、指令集、微架构等。
4.内存:主存和辅存的区别、存储器的层次结构、内存管理等。
5.硬盘:磁盘的组成、磁头的读写过程、磁盘的分区与格式化等。
6.显示器:分辨率、刷新率、色彩深度、投影仪等。
7.输入输出设备:键盘、鼠标、打印机、扫描仪、摄像头等。
8.扩展设备:声卡、显卡、网卡、USB接口等。
二、操作系统知识1.操作系统的功能和分类:任务管理、文件管理、内存管理、设备管理等。
2.Windows操作系统:常见的Windows版本、桌面环境、文件系统、任务管理等。
3.Linux操作系统:常见的Linux发行版、命令行界面、文件系统、用户管理等。
4.进程管理:进程的概念、进程调度、进程同步与互斥等。
5.线程管理:线程的概念、线程与进程的区别、线程同步与互斥等。
6.文件管理:文件的操作、文件的属性、文件系统的结构等。
7.输入输出管理:设备的管理、设备驱动程序、中断和DMA等。
8.网络管理:网络的概念、协议栈、IP地址、路由等。
三、计算机网络知识1.网络的分类:局域网、广域网、互联网、因特网等。
2.数据通信和网络协议:数据的发送和接收、分组交换、网络协议的分层等。
3.网络体系结构:TCP/IP体系结构、OSI参考模型等。
4.网络通信设备:路由器、交换机、集线器、网卡等。
5.网络地址:IP地址、子网掩码、默认网关、DNS等。
6.网络安全:网络攻击与防范、防火墙、VPN等。
7.网络应用:常用的网络服务和应用协议、浏览器、电子邮件等。
8.网络管理:网络配置、故障排除、网络性能监测等。
全国计算机二级公共基础知识汇总计算机二级公共基础知识是计算机专业人员必备的基本知识,包括计算机基本原理、操作系统、网络原理、数据库原理和计算机应用等方面的知识。
下面是全国计算机二级公共基础知识的完整汇总。
一、计算机基本原理:计算机硬件的组成和工作原理,包括中央处理器、存储器、输入输出设备等。
1.中央处理器:控制计算机的运算和控制活动,包括运算单元和控制单元。
2.存储器:计算机的主要组成部分,包括内存和外存。
3.输入输出设备:与计算机进行交互的设备,包括键盘、鼠标、显示器、打印机等。
二、操作系统:计算机的核心软件,负责管理和控制计算机的资源。
1.操作系统的功能:包括进程管理、内存管理、文件管理、设备管理和用户界面等。
2. 常见的操作系统:Windows、Linux、Unix等。
三、网络原理:计算机网络的基本原理和常用协议,包括网络拓扑、网络协议和安全性等。
1.网络拓扑:指网络中计算机的物理连接方式,包括星型、总线型、环型等。
2.网络协议:指计算机网络中不同计算机之间通信的规则和约定,常见的协议有TCP/IP、HTTP、FTP等。
3.网络安全性:指保护计算机网络不受到非法侵入和攻击的能力,包括防火墙、加密技术等。
四、数据库原理:数据库的基本原理和常用操作,包括数据模型、关系数据库和SQL语言等。
1.数据模型:指描述数据结构、数据操作和数据约束的概念工具,常见的数据模型有层次模型、网状模型和关系模型等。
2. 关系数据库:采用关系模型进行数据组织和管理的数据库,常见的关系数据库有Oracle、MySQL、SQL Server等。
3.SQL语言:结构化查询语言,用于对关系数据库进行查询、更新和管理。
五、计算机应用:计算机在不同领域应用的基本知识,包括办公软件、图像处理、网页设计等。
1.办公软件:包括文字处理、电子表格和演示文稿等。
3. 网页设计:指网页的布局、设计和开发,需要掌握HTML、CSS和JavaScript等技术。
全国计算机等级考试二级公共基础知识讲义前言全国计算机等级考试是由教育部主管,中国人民大学教育部考试中心具体组织实施的一项全国性计算机应用能力和技术水平的考试,是中国计算机技术领域最具影响的考试之一。
本文主要介绍二级公共基础知识的相关考试内容以及备考方法。
考试内容一、计算机的基本概念计算机的基本概念包括计算机体系结构、计算机组成与工作原理、计算机性能指标等方面内容。
此部分主要考察考生对计算机硬件的基本概念的掌握能力。
二、操作系统基础知识操作系统基础知识包括操作系统的概念、基本功能、历史和发展、Windows 操作系统的使用和管理等方面内容。
此部分主要考察考生对操作系统的相关知识的掌握能力。
三、计算机网络基础知识计算机网络基础知识包括计算机网络的基本概念、计算机网络的体系结构、网络协议和标准、网络设备等方面内容。
此部分主要考察考生对计算机网络的相关知识的掌握能力。
四、Office 办公软件的应用Office 办公软件的应用包括 Word、Excel、PowerPoint 等软件的使用,涵盖了文档编辑、数据处理、图形处理、演示制作等方面内容。
此部分主要考察考生对Office 软件的基本操作和应用能力。
备考方法一、系统学习考生需要系统学习各部分考点的相关知识,并逐个进行掌握。
同时,应重点关注考试的难点部分,加强理解和记忆。
二、辅助练习在掌握理论知识的基础上,考生应进行相关练习,巩固所学知识,提高应用能力。
可通过课后习题、模拟试题等方式进行,以便更好地检验自己的掌握情况。
三、复习在备考期间,考生应根据自身复习情况进行复习,重点回顾掌握不足的内容,及时弥补知识盲点,同时也可以对已掌握的知识进行巩固,加深印象。
全国计算机等级考试二级公共基础知识的考试内容多元,备考需求时间充足和精力投入。
通过以上几条备考方法,希望考生能更好地备考,达到理想的考试成绩。
1。
1 算法考点1 算法的基本概念计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法.算法(algorithm)是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,同时是明确的;此顺序将在有限的次数后终止。
算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作.1算法的基本特征(1)可行性(effectiveness):针对实际问题而设计的算法,执行后能够得到满意的结果。
(2)确定性(definiteness):算法中的每一个步骤都必须有明确的定义,不允许有模棱两可的解释和多义性。
(3)有穷性(finiteness):算法必需在有限时间内做完,即算法必需能在执行有限个步骤之后终止。
(4)拥有足够的情报:要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时,此算法才最有效的;而当提供的情报不够时,算法可能无效。
2算法的基本要素(1)算法中对数据的运算和操作:每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列.计算机可以执行的基本操作是以指令的形式描述的。
一个计算机系统能执行的所有指令的集合,称为该计算机系统的指令系统。
计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中,基本的运算和操作有以下4类:①算术运算:主要包括加、减、乘、除等运算;②逻辑运算:主要包括“与”、“或”、“非"等运算;③关系运算:主要包括“大于"、“小于”、“等于”、“不等于"等运算;④数据传输:主要包括赋值、输入、输出等操作。
(2)算法的控制结构:一个算法的功能不仅仅取决于所选用的操作,而且还与各操作之间的执行顺序有关.算法中各操作之间的执行顺序称为算法的控制结构.算法的控制结构给出了算法的基本框架,它不仅决定了算法中各操作的执行顺序,而且也直接反映了算法的设计是否符合结构化原则。
计算机二级公共基础知识总结1.计算机基本概念计算机是一种用于处理和存储信息的工具,由硬件和软件组成。
硬件包括中央处理器(CPU)、内存、硬盘、显卡等,而软件包括操作系统、应用程序等。
常见的计算机有个人电脑、服务器、手机等。
2.计算机的组成与工作原理计算机由硬件和软件组成。
硬件包括中央处理器(CPU)、内存、硬盘、显卡等,而软件包括操作系统、应用程序等。
计算机的工作原理是通过执行指令实现对数据的处理和存储。
计算机执行指令的基本步骤是获取指令、解码指令、执行指令、存储结果。
3.计算机数学基础计算机数学基础是计算机科学与技术中的基础学科,包括离散数学、线性代数、概率论和统计等。
离散数学是一种研究离散结构的数学学科,常用于描述计算机科学中的数据结构和算法。
线性代数是一种研究向量空间和线性映射的数学学科,常用于计算机图形学和数据分析中。
概率论和统计是一种研究随机事件和随机变量的数学学科,常用于计算机网络和机器学习中。
4.数据表示与计算机编码计算机中的数据是以二进制形式表示的,每个二进制位称为一个比特(Bit)。
计算机中的数据类型包括整数、浮点数、字符等。
常见的数据表示方法有原码、反码和补码表示法。
计算机中的编码方式有ASCII码、Unicode、UTF-8等。
5.计算机网络与通信计算机网络是一种将多台计算机连接起来,实现数据传输与共享的技术。
计算机网络有局域网、广域网和互联网等不同的类型。
计算机网络中的常见协议有TCP/IP协议、HTTP协议、FTP协议等。
6.操作系统操作系统是一种管理计算机硬件和软件资源的软件,它提供了管理、调度和控制计算机的基本功能。
常见的操作系统有Windows、Linux、Unix等。
7.数据库与数据库管理系统数据库是一种用于存储和管理数据的软件,它提供了数据的增删改查等功能。
数据库管理系统是一种用于管理数据库的软件,它提供了数据的组织、存储和维护等功能。
常见的数据库有关系型数据库和非关系型数据库。
二级计算机公共基础知识1. 计算机硬件基础
- 计算机硬件组成
- 的工作原理
- 内存的种类和作用
- 存储设备的种类和特点
- 输入输出设备的种类和功能
2. 操作系统基础
- 操作系统的概念和作用
- 操作系统的主要功能
- 常见操作系统的种类
- 文件管理和磁盘管理
- 进程和线程管理
3. 网络基础
- 计算机网络的概念和分类
- 网络拓扑结构
- 网络协议和网络模型
- 互联网的工作原理
- 网络安全和加密技术
4. 数据库基础
- 数据库的概念和作用
- 数据库管理系统的种类 - 数据库设计和规范化
- 语言基础
- 数据库安全和备份
5. 算法和数据结构
- 算法的概念和特性
- 常见算法的分析和设计 - 数据结构的种类和应用 - 算法复杂度分析
- 递归和动态规划
6. 程序设计基础
- 程序设计语言的种类
- 程序设计基本概念
- 程序设计流程控制
- 函数和模块化编程
- 面向对象程序设计
7. 信息安全基础
- 信息安全的概念和重要性 - 密码学基础
- 访问控制和身份认证
- 恶意软件和防御措施
- 网络安全和防火墙
以上内容涵盖了二级计算机公共基础知识的主要方面,可以作为学习和复习的参考。
全国计算机等级考试二级教程——公共基础知识一、操作系统基础知识1.操作系统是什么?请简要说明其作用和功能。
操作系统是计算机系统中的一种软件,它负责管理和控制计算机硬件资源,并为用户程序提供运行环境。
其主要功能包括进程管理、内存管理、文件系统管理和设备管理等。
2.请列举几种常见的操作系统。
常见的操作系统包括Windows、Linux、Mac OS、Android等。
3.什么是进程?什么是线程?进程是正在执行的程序的实例,是操作系统资源分配与调度的基本单位。
线程是进程中的一个执行单元,一个进程可以包含多个线程。
4.什么是文件系统?文件系统是一种组织和管理计算机存储设备上数据的方法,用于存储和检索文件,并提供对文件的访问控制和保护。
二、计算机网络基础知识1.什么是IP地址?IP地址的作用是什么?IP地址是因特网协议(IP)的网络接口的标识,用于唯一地标识和定位网络上的计算机设备。
IP地址的作用是用于在数据通信中确定源和目标的地址。
2. 请简述Internet的结构。
Internet的结构是由成千上万个相互连接的计算机网络组成的,形成一个全球性的网络。
它使用一种称为互联网协议(IP)的通信协议进行数据传输,通过路由器相互连接。
3.什么是HTTP协议?HTTP协议有哪些特点?HTTP协议(Hypertext Transfer Protocol)是一种用于从服务器传输超文本到客户端的协议。
它的特点包括无连接性、无状态性和可扩展性。
三、数据库基础知识1.什么是数据库?数据库的作用是什么?数据库是存储、管理和组织数据的集合,它提供了一种结构化的方式来组织和存储数据,以便于数据的存取和处理。
数据库的作用是存储和管理大量的数据,并为用户提供数据查找、插入、更新和删除等功能。
2.请简述关系数据库的特点和优点。
关系数据库是一种以关系为基础的数据模型。
它的特点包括数据的结构化、数据间的关系建立、数据的操作和约束等。
关系数据库的优点是数据的一致性、数据的可扩展性、数据的安全性和数据的完整性。
计算机二级公共基础知识重点讲解汇总章节名称内容简介第一章数据结构与算法本章主要介绍算法的基本概念、数据结构的定义、线性表、树等重点知识的讲解。
第二章程序设计基础本章主要介绍程序设计风格、结构化程序设计、面向对象程序设计等重点知识的讲解。
第三章软件工程基础本章主要介绍软件工程的基本概念、结构化分析方法、软件设计等重点知识的讲解。
第四章数据库设计基础本章主要介绍数据库、数据库管理系统(DBMS)、数据库系统、数据模型、关系运算、专门关系运算、数据库设计步骤等重点知识的讲解。
第一章数据机构与算法数据结构与算法◆算法的基本概念1. 算法:是对问题处理方案的正确而完整的描述,是求解问题的方法,是指令的有效序列。
2. 具有5个特性:(1)有穷性(在有穷步后完成)算法程序的运行时间是有限的(2)确定性(每一步都有确定的含义)(3)可行性(4)输入(一个算法有零个或多个输入)(5)输出(一个算法有一个或多个输出)3. 算法的复杂度包括:时间复杂度和空间复杂度。
二者没有必然的联系。
时间复杂度:执行算法所需要的计算工作量或基本运算次数。
空间复杂度:算法所需要的空间的度量。
◆数据结构的定义1. 数据结构包括数据的逻辑结构、数据的存储结构、数据的操作数据的逻辑结构:数据的外部结构,指各数据元素之间的逻辑关系,反映人们对数据含义的解释。
包括:线性结构(线性表、栈、队列)和非线性结构(树和图)数据的存储结构:数据的物理结构,指数据的逻辑结构在计算机中的表示。
一个逻辑结构可以有多种存储结构。
◆线性表:线性表中元素的个数n(n>=0)定义为线性表的长度。
顺序存储是线性表的一种最常用的存储方式。
线性表的顺序存储结构和线性表的链式存储结构分别是随机存取的存储结构和顺序存取的存储结构。
1.栈:是限定在表尾进行插入和删除操作的线性表。
具有记忆功能只能顺序存储(错)允许插入和删除的一端叫栈顶。
另一端叫栈底。
后进先出的线性表2队列:是限定在一端插入而在另一端删除,插入端叫队尾,删除端叫对头。
计算机2级公共基础知识点与考点计算机二级考试是一种全国性的计算机应用能力考试,是我国普通高等学校招生考试计算机标准化考试试炉。
计算机二级考试分为两个科目:基础知识和应用能力,其中基础知识考试内容主要包括计算机硬件、操作系统、网络基础、数据库、程序设计与开发基础等方面的知识。
下面是计算机二级考试基础知识点和考点的详细介绍。
1.计算机硬件-计算机的基本组成:中央处理器(CPU)、内存、外存、输入输出设备等;-CPU的工作原理和功能:运算、控制、存储;-存储器的分类和特点:主存、辅存、内存、外存;-输入输出设备的分类和特点:键盘、鼠标、显示器、打印机等;-主板的组成和功能:芯片组、总线、接口等;-硬盘、内存、显卡、声卡的作用和主要参数。
2.操作系统-操作系统的基本概念和作用:资源管理、任务管理、文件管理等;-操作系统的分类和特点:批处理系统、分时操作系统、实时操作系统等;- 常见的操作系统:Windows、Linux、Mac OS等的特点和使用方法;-文件系统的管理和访问:文件的创建、读取、写入、删除等操作;-进程的管理和调度:进程的创建、运行、调度、终止等;-内存管理:内存的分配、回收、虚拟内存的概念等。
3.网络基础-计算机网络的概念和分类:局域网、广域网、互联网等;-网络传输协议:TCP/IP协议、HTTP协议、FTP协议等;-IP地址的分类和作用:IPv4、IPv6、私有IP地址、公有IP地址等;-子网掩码和网关的概念和作用;-常用网络设备:路由器、交换机、网卡等的作用和配置方法;-网络安全与防护:防火墙、代理服务器、VPN等的功能和原理。
4.数据库-数据库的基本概念和作用:数据的集中管理、共享和保护;-关系数据库和非关系数据库的区别和特点;-数据库的设计和规范化:实体、属性、关系、主键、外键等的概念和使用方法;-SQL语言的使用:数据的检索、修改、删除、插入等操作;-关系代数和关系演算的基本概念和运算;-数据库的备份和恢复:全备份、差异备份、增量备份等方法。
第一章数据结构与算法(P1—P38)1.1 算法1.1.1 算法的基本概念(P1—P4)所谓算法是指解题方案的准确完整的描述。
1.算法的基本特征(1)可行性(2)确定性(3)有穷性(4)拥有够的情报2.算法的基本要素一个算法通常由两种基本要素组成:一是对数据对象的运算和操作,二是算法的控制结构。
(1)算法中对数据的运算和操作(插入、删除)(2)算法的控制结构一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。
1.1.2 算法复杂度(P4—P6)算法的复杂度主要包括时间复杂度和空间复杂度。
1.算法的时间复杂度所谓算法的时间复杂度,是指执行算法所需要的计算工作量。
可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。
3.算法的空间复杂度一个算法的空间复杂度,一般是指执行这个算法所需要的内存空间。
1.2数据结构的基本概念数据结构,主要研究和讨论以下三个方面的问题:①数据的逻辑结构;②数据的存储结构;③对各种数据结构进行的运算。
(插入、删除)主要目的是为了提高数据处理的效率。
所谓提高数据处理的效率,主要包括两个方面:一是提高数据处理的速度,(时间复杂度)二是尽量节省在数据处理过程中所占用的计算机存储空间。
(空间复杂度)1.2.1什么是数据结构(P6—P11)1.数据的逻辑结构所谓数据的逻辑结构,是指反映数据元素之间逻辑关系的数据结构。
2.数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称为数据的物理结构)一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序、链接、索引等存储结构。
而采用不同的存储结构,其数据处理的效率是不同的。
1.2.3线性结构与非线性结构(P12)一般将数据分为两大类型:线性结构与非线性结构。
线性结构又称线性表如果一个数据结构不是线性结构,则称之为非线性结构。
1.3线性表及其顺序存储结构1.3.1线性表的基本概念(P12—P13)线性表是由n (n≥0)个数据元素a1,a2,…,a n组成的一个有限序列,表中的每一个数据元素,除了第一个外,有且只有一个前件,除了最后一个外,有且只有一个后件。
即线性表或是一个空表,或可以表示为。
(a1,a2,…,a i,…,a n)非空线性表有如下一些结构特征:①有且只有一个根结点a1,它无前件;②有且只有一个终结点a n,它无后件;③除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。
1.3.2线性表的顺序存储结构 (P13—P14)在计算机中存放线性表,一种最简单的方法是顺序存储,也称为顺序分配。
线性表的顺序存储结构具有以下两个基本特点:①线性表中所有元素据所占的存储空间是连续的;②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
假设线性表中的第一个数据元素的存储地址为ADR(a1),每一个数据元素占K个字节,则线性表中第i 个元素a i在计算机存储空间中的存储地址为ADR(a1)=ADR(a1)+(i-1)K1.3.3顺序表的插入运算 (P14—P15)在平均情况下,要在线性表中插入一个新元素,需要移动表中一半的元素。
因此,在线性表顺序存储的情况下,要插入一个新元素,其效率是很低的。
1.3.4顺序表的删除运算 (P15—P16)在平均情况下,要在线性表中删除一个元素,需要移动表中表中一半的元素。
因此,在线性表顺序存储的情况下,要删除一个元素,其效率也是很低的。
由线性表在存储结构下的插入与删除运算可以看出,线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适的,因为顺序存储的结构比较简单。
但这种顺序存储的方式对于元素经常需要变动的大线性表就不太合适了,因为插入删除的效率比较低。
1.4栈和队列1.4.1栈及其基本运算 (P16—P18)1.什么是栈栈是限定在一端进行插入与删除的另一端称为栈底。
即栈是按照“先进后出”(FILO)或“后进先出”(LIFO)的原则组织数据的,因此,栈也被称为“先进后出”表或“后进先出”表。
由此可以看出,栈具有记忆作用。
2.栈的顺序存储及其运算(采用顺序存储结构的栈称为顺序栈)栈的基本运算有三种:入栈、退栈与读栈顶元素。
(1)入栈运算(2)退栈运算(3)读栈顶元素1.4.2队列及其基本运算 (P18—P20)1.什么是队列队列(queue)是指允许在一端进行插入、而在另一端进行删除的线性表。
允许插入的一端称为队尾,通常用一个称为尾指针(rear)的指针指向队尾元素,一端称为排头(也称为队头)通常也用一个排头指针(front)指向排头元素的前一个位置。
队列双称为“先进先出”或“后进后出”的线性表。
3.循环队列及其运算在实际应用中,队列的顺序存储结构一般采用循环队列的形式。
所谓循环队列,就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。
(1)入队运算(2)退队运算1.5线性链表1.5.1线性链表的基本概念 (P20—P23)由于线性表的顺序存储结构存在以上这些缺点,对于大的线性表,特别是元素变动频繁的大线性表不宜采用顺序存储结构,而是采用下面要介绍的链式存储结构。
在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元素值,称为数据域;另一部分用于存放指针,称为指针域。
在链式存储结构中,存储数据结构的存储空间可以下连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。
链式存储方式既可用于表示线性结构,也可以用于表示非线性结构。
1.线性链表线性表的链式存储结构称为线性链表。
2.带链的栈栈也是线性表,也可以采用链式存储结构。
3.带链的队列与栈类似,队列也是线性表,也可以采用链式存储结构。
1.5.2线性链表的基本运算 (P23—P25)线性链表在插入过程中不发生数据元素移动的现象,只需改变有关结点的指针即可,从而提高了插入的效率。
从线性链表的删除过程可以看出,在线性链表中删除一个元素后,不需要移动表的数据元素,只需改变被删除元素所在结点的前一个结点的指针域即可。
1.5.3循环链表及其基本运算 (P25—P26)循环链表具有以下两个特点:(1)在循环链表中增加了一个表头结点,指针域指向线性表的第一个元素的结点。
循环链表的头指针指向表头结点。
(2)循环链表中最后一个结点的指针域不是空,而是指向表头结点。
即在循环链表中,所有结点的指针构成了一个环状链。
1. 6树与二叉树1.6.1树的基本概念 (P26—P28)在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称为树的根。
在树结构中,每一个结点可以有多个后件,它们都称为该结点的子结点。
没有后件的结点称为叶子结点。
在树结构中,一个结点所拥有的后件个数称为该结点的度在树中,所有结点中的最大的度称为树的度。
根结点在第1层。
树的最大层次称为树的深度。
1.6.2二叉树及其基本性质 (P28—P31)1.什么是二叉树二叉树具有以下两个特点:①非空二叉树只有一个根结点;②每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。
2.二叉树的基本性质性质1在二叉树的第K层上,最多有2K-1(K≥1)个结点。
性质2深度为m的二叉树最多有2m-1个结点。
性质3在任意一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个。
3.满二叉树与完全二叉树(1)满二叉树所谓满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点,这就是说,在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第K层上有2K-1个结点,且深度为m的满二叉树有2m-1个结点。
(2)完全二叉树所谓完全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边若干结点。
满二叉树也是完全二叉树,而完全二叉树一般不是满二叉树。
性质6设完全二叉树共有n个结点。
从根结点开始,按层序用自然数1,2,…,n给结点进行编号,则对于编号为k(k=1,2,…,n)的结点有以下结论:①若k=1,则该结点为根结点,它没有父结点;若k>1,则该结点的父结点编号为INT(k/2)。
②若2k≤n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点。
③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。
1.6.3二叉树的存储结构 (P31—P32)在计算机中,二叉树通常采用链式存储结构。
1.6.4二叉树的遍历 (P32—P33)二叉树的遍历可以分为三种:前序遍历、中序遍历、后序遍历。
1.前序遍历(DLR)2.中序遍历(LDR)3.后序遍历(LRD)1.7查找技术1.7.1顺序查找 (P33)顺序查找又称顺序搜索。
对于大的线性表来说,顺序查找的效率是很低的。
虽然顺序查找的效率不高,但在下列两种情况下也只能采用顺序查找:(1)线性表无序表,则不管是顺序存储结构还是链式存储结构,都只能用顺序查找。
(2)即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。
1.7.2二分法查找 (P33—P34)二分法查找只适用于顺序存储的有序表。
显然,当有序线性表为顺序存储时都能采用二分查找,并且,二分查找的效率要比顺序查找高得多。
可以证明,对于长度为n的有序线性表,在最坏情况下,二分查找只需要比较log2n次,而顺序查找需要比较n次。
1.8排充技术1.8.1交换类排序法 (P34—P35)1.冒泡排序法冒泡排序法是一种最简单的交换类排序方法。
假设线性表的长度为n,则在最坏情况下,冒泡排序需要的比较次数为n(n-1)/2。
2.快速排序法快速排序法也是一种互换类的排序方法,但由于它比冒泡排序法的速度快,因此称之为快速排序法。
1.8.2插入类排序法 (P35—P37)1.简单插入排序法自以为插入排序,是指将无序序列中的各元素依次插入到已经有序的线性表中。
在简单插入排序法中,这种排序方法的效率与冒泡排序法相同。
在最坏情况下,证券交易插入排序需要n(n-1)/2次比较。
2.希尔排序法希尔排序法属于插入类排序,但它对简单插入排序做了较大的改进。
1.8.3选择类排序法 (P37—P38)1.简单选择排序法从中选出最小的元素,将它交换到表的最前面。
简单选择排序法在最坏情况下需要比较n(n-2)/2次。
2.堆排序法堆排序法属于选择类的排序方法。
堆排序的方法对于规模较小的线性表并不合适,但对于较大规模的来说是很有效的。
分享到搜狐微博第2章程序设计基础(P40—P45)2.1程序设计方法与风格程序设计的风格总体而言应该强调简单和清晰,程序必须是可以理解的。
可以认为,著名的“清晰第一,效率第二”的论点已成为当今主导的程序设计风格。