下载文档原格式
二级公共基础知识总结第一章数据结构与算法1.1 算法算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。
算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。
特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。
算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。
指令系统：一个计算机系统能执行的所有指令的集合。
基本运算包括：算术运算、逻辑运算、关系运算、数据传输。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。
算法时间复杂度是指执行算法所需要的计算工作量。
算法空间复杂度是指执行这个算法所需要的内存空间。
1.2 数据结构的基本概念数据结构研究的三个方面：（1（2（3）对各种数据结构进行的运算。
数据结构是指相互有关联的数据元素的集合。
数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。
数据的存储结构有顺序、链接、索引等。
线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
1．3 线性表及其顺序存储结构非空线性表的结构特征：（1）且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
结点个数nn=0线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。
计算机二级公共基础知识总结第一章数据结构与算法1.1算法算法：是指解题方案的准确而完整的描述。
算法不等同于程序，也左右计算机方法，程序的基本建设不可能将强于算法的设计。
算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。
特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能够在非常有限的时间内略过，即为能够在继续执行非常有限个步骤后中止，包含合理的继续执行时间的含义；（4）拥有足够的情报。
算法的基本要素：一就是对数据对象的运算和操作方式；二就是算法的控制结构。
指令系统：一个计算机系统能够继续执行的所有指令的子集。
基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。
算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列出法、归纳法、关系式、递回、减斗关系式技术、追溯法。
算法复杂度：算法时间复杂度和算法空间复杂度。
算法时间复杂度就是指继续执行算法所须要的排序工作量。
算法空间复杂度就是指继续执行这个算法所须要的内存空间。
1.2数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据展开处置时，各数据元素在计算机中的存储关系，即为数据的存储结构；（3）对各种数据结构展开的运算。
数据结构是指相互有关联的数据元素的集合。
数据的逻辑结构包含：（1）则表示数据元素的信息；（2）表示各数据元素之间的前后件关系。
数据的存储结构有顺序、链接、索引等。
线性结构条件：（1）存有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
1．3线性表及其顺序存储结构线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
计算机二级公共基础知识总结复习指导第一章数据结构与算法1.1 算法算法：是指解题方案的准确而完整的描述。
算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。
算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。
特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。
算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。
指令系统：一个计算机系统能执行的所有指令的集合。
基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。
算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。
算法复杂度：算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。
算法空间复杂度是指执行这个算法所需要的内存空间。
1.2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。
数据结构是指相互有关联的数据元素的集合。
数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。
数据的存储结构有顺序、链接、索引等。
线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
1．3 线性表及其顺序存储结构线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。
计算机二级公共基础常见知识1.计算机硬件-CPU（中央处理器）：计算机的核心部件，负责执行指令和处理数据。
-内存：临时存储计算机运行时所需要的数据和指令。
-硬盘：长期存储数据的设备。
-显示器：用于显示计算机的输出结果。
-键盘和鼠标：输入设备，用于输入指令和数据。
-主板：将各个硬件组件连接在一起的电路板。
2.计算机软件-操作系统：控制和管理计算机硬件和软件资源的程序。
-应用程序：用来完成特定任务的软件，如办公软件、图像处理软件等。
- 编程语言：一种用于编写计算机程序的语言，如C、Python等。
3.计算机网络-互联网：全球范围内的计算机网络系统。
-局域网：在同一地区内互连的计算机网络。
-IP地址：互联网协议地址，用于标识计算机的唯一标识符。
4.数据结构-数组：一种线性数据结构，用于存储相同类型的数据。
-链表：一种非连续的数据结构，由一组节点组成。
-栈：一种先进后出的数据结构。
-队列：一种先进先出的数据结构。
-树：一种非线性的数据结构，由节点和边组成。
5.数据库- 关系数据库：使用表格来组织和管理数据的数据库系统，如MySQL、Oracle等。
-SQL（结构化查询语言）：用于与关系数据库进行通信和操作的语言。
-数据库管理系统（DBMS）：用于管理和操作数据库的软件。
6.算法和数据处理-排序算法：如冒泡排序、插入排序、选择排序等。
-查找算法：如线性查找、二分查找等。
-数据压缩：用于减小数据存储空间和传输带宽的技术。
-数据加密：用于保护数据安全的技术。
7.操作系统- Windows：微软推出的操作系统。
- Linux：一种开源的操作系统。
- macOS：苹果公司的操作系统。
8.办公软件- Microsoft Office：包括Word、Excel、PowerPoint等应用程序。
- WPS Office：金山软件开发的办公软件套装。
9.图像处理- Photoshop：Adobe公司开发的图像处理软件。
-GIMP：一种开源的免费图像处理软件。
计算机二级公共基础知识总结第一章数据结构与算法1.1算法算法：是指解题方案的准确而完整的描述。
算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。
算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的, 此顺序将在有限的次数下终止。
特征包括：（1）可行性；（2）确定性，算法屮每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥冇足够的情报。
算法的基本耍素：一是对数据对彖的运算和操作；二是算法的控制结构。
指令系统：一个计算机系统能执行的所有指令的集合。
基本运算和操作包括：算术运算、逻辑运算、尖系运算、数据传输。
算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。
算法复杂度：算法吋间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。
算法空间复杂度是指执行这个算法所需要的内存空间。
1.2数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素z间所固冇■的逻辑尖系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元索在计算机屮的存储尖系，即数据的存储结构；（3）对各种数据结构进行的运算。
数据结构是指相互冇尖联的数据元索的集介。
数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元索之间的前后件尖系。
数据的存储结构有顺序、链接、索引等。
线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件5也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
1.3线性表及其顺序存储结构线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素z间的相对位置是线性的。
在复杂线性表中，由若干项数据元索组成的数据元索称为记录，而由多个记录构成的线性表又称为文件。
第一章数据结构与算法算法1、算法：是指解题方案的准确而完整的描述。
算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。
2、算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。
特征包括：（1）可行性；（2）确定性（3）有穷性（4）拥有足够的情报。
3、算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。
4、指令系统：一个计算机系统能执行的所有指令的集合。
5、基本运算包括：算术运算、逻辑运算、关系运算、数据传输。
6、算法的控制结构：顺序结构、选择结构、循环结构。
7、算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。
8、算法复杂度：算法时间复杂度和算法空间复杂度。
9、算法时间复杂度是指执行算法所需要的计算工作量。
10、算法空间复杂度是指执行这个算法所需要的内存空间。
数据结构的基本基本概念1、数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。
数据结构是指相互有关联的数据元素的集合。
2、数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。
数据的存储结构有顺序、链接、索引等。
3、线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
线性表及其顺序存储结构1、线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。
2、非空线性表的结构特征：（1）且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
二级公共基础知识总结(30分：10选择+5填空)复习及应试建议：1.考生的复习必须遵守：“ 80/20的原则”二级考试的公共知识部分的覆盖面广，至少涵盖了计算机应用专业的四门核心课程：算法及数据结构、程序设计基础、软件工程基础和数据库。
事实上，这些课程本身的涉及面就很广，难度系数较大。
因此，这些课程甚至也是计算机专业学生最头疼的课程，对大多数考生来说其难度之大不言而喻。
所以，考生应把80%的时间用在20%勺重点知识点上，争取用20%勺重点知识点来答对 80%勺考题，这是考生复习二级考试的公共知识部分的总体思路。
2.复习的关键是考生必须准确判断和掌握常见考点考生必须能够准确判断和掌握常见考点，例如：算法部分主要考查算法的概念及算法的复杂度；数据结构部分主要考查最基本的概念、最典型的数据结构和最常见的操作；程序设计部分主要考查程序设计风格的基本要求、结构化程序设计的最基本知识和面向对象程序设计的最常见概念；软件工程基础部分主要考查软件工程的基本概念及软件生命周期的各个阶段的基础知识；数据库基础部分主要考查数据库基本概念、数据模型、关系代数基础知识、数据库设计方法和步骤。
对常见考点的准确把握会使考生避免盲目学习，从而能够轻松面对考试。
二级考试中要求的知识点都是最基本的、最简单的，真正需要“灵活”掌握的考点极少。
很多考生在考试过程中可能已经发现，该部分的题目“会做就是不懂”。
所以建议在复习过程中不要急于“灵活”，其实等到把基本的知识点掌握后自然就“灵活”了。
公共知识部分仅占30%分，题目相对简单。
因此，在答题过程中，这部分要争取速度快、准确度高。
总的原则是如果一道题在两分钟没有任何思路，就应该跳过此题，把时间给后面的题目。
记住：二级考试是一种合格考试，不是竞赛，及格就行了。
公共基础的复习没有技巧，就是背诵、背诵、再背诵，就是要把这10页纸背下来。
划线字体是至关重要的部分，框起来的字体为填空题的常考词汇，一定要背熟牢记，这里面有100分里30分的原题。
二级计算机公共基础知识计算机公共基础知识是指涉及计算机硬件、软件、网络和安全等方面的知识，是计算机科学与技术的基础。
在二级计算机考试中，考生需要掌握一些基本的计算机知识以及相关的术语和概念。
下面我将从计算机硬件、软件、网络和安全等方面为您介绍二级计算机公共基础知识。
一、计算机硬件知识1.计算机的组成：计算机由中央处理器（CPU）、内存、输入设备、输出设备和存储设备等构成。
2.中央处理器：中央处理器是计算机的核心部件，负责执行程序的指令和进行数据处理。
3.内存：内存是计算机的临时存储空间，用于存储正在执行的程序和数据。
4.输入设备：输入设备用于将外部信息输入到计算机中，如键盘、鼠标、摄像头等。
5.输出设备：输出设备用于将计算机处理的结果显示给用户，如显示器、打印机、扬声器等。
6.存储设备：存储设备用于永久保存数据和程序，如硬盘、固态硬盘（SSD）、光盘、U盘等。
二、计算机软件知识1.操作系统：操作系统是计算机系统的核心软件，负责管理计算机硬件资源和提供基本的系统服务。
2.应用软件：应用软件是为满足特定任务需求而开发的软件，如办公软件、图像处理软件、视频播放器等。
3.开发软件：开发软件是用于开发和编程的软件，如集成开发环境（IDE）、编译器、调试器等。
三、计算机网络知识1.网络基础概念：IP地址、子网掩码、网关、DNS等是计算机网络的基础概念，了解这些概念对理解网络通信很重要。
2.网络协议：网络协议是计算机网络中用于传输和处理数据的规则和约定，如TCP/IP协议、HTTP协议、FTP协议等。
3.网络拓扑结构：网络拓扑结构描述了计算机网络中各个设备之间的连接方式，常见的拓扑结构有星型、环型和总线型等。
四、计算机安全知识1.防病毒和防火墙：为了保护计算机不受病毒和恶意攻击的影响，需要安装防病毒软件和防火墙，并定期更新维护。
2.数据备份：数据备份是防止数据丢失的重要手段，可以利用外部存储设备或云存储对数据进行备份。
第1章数据结构与算法经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找,读者应对此部分进行重点学习。
详细重点学习知识点：1．算法的概念、算法时间复杂度及空间复杂度的概念2．数据结构的定义、数据逻辑结构及物理结构的定义3．栈的定义及其运算、线性链表的存储方式4．树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历5．二分查找法6．冒泡排序法1.1算法考点1 算法的基本概念考试链接：考点1在笔试考试中考核的几率为30%，主要是以填空题的形式出现，分值为2分，此考点为识记内容，读者还应该了解算法中对数据的基本运算。
计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法.1．算法的基本特征:可行性、确定性、有穷性、拥有足够的情报。
2．算法的基本要素：（1）算法中对数据的运算和操作一个算法由两种基本要素组成：一是对数据对象的运算和操作;二是算法的控制结构。
在一般的计算机系统中，基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算和数据传输。
（2)算法的控制结构:算法中各操作之间的执行顺序称为算法的控制结构.描述算法的工具通常有传统流程图、N—S结构化流程图、算法描述语言等。
一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。
考点2 算法复杂度考试链接：考点2在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%，主要是以选择的形式出现，分值为2分,此考点为重点识记内容，读者还应该识记算法时间复杂度及空间复杂度的概念。
1.算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。
同一个算法用不同的语言实现,或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。
这表明使用绝对的时间单位衡量算法的效率是不合适的。
撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法"运行工作量”的大小，只依赖于问题的规模（通常用整数n表示），它是问题规模的函数。
计算机二级考试公共基础知识是计算机二级考试的一部分，主要考察考生对计算机基础知识的掌握情况，下面是一些常见的考点和知识点：
1. 计算机基础知识：包括计算机的硬件组成、计算机的工作原理、操作系统的基本概念、常见的应用软件以及网络基础知识等方面的内容。
2. 计算机操作系统：包括常见的计算机操作系统和其特点、操作系统的安装和配置以及文件管理、进程管理、内存管理等方面的内容。
3. 网络基础知识：包括计算机网络的基本概念、网络拓扑结构、常用网络协议、IP地址的分类和子网划分、TCP/IP协议的基本原理以及网络安全等方面的内容。
4. 数据库基础知识：包括数据模型的基本概念、关系模型、SQL语言的基本语法、数据库的设计与实现以及数据备份与恢复等方面的内容。
5. 程序设计基础知识：包括常见的编程语言、程序设计的基本思路与方法、程序设计的基本流程以及程序的调试和测试
等方面的内容。
6. 办公自动化软件：包括文字处理软件、电子表格软件和演示文稿软件的基本概念、常用功能和使用方法。
7. 计算机安全基础知识：包括计算机病毒的种类和防范方法、网络攻击的方式和防范方法、数据安全和隐私保护等方面的内容。
以上仅是计算机二级考试公共基础知识的一些常见考点和知识要点，实际考试中还可能涉及其他方面的内容。
考生在备考时应该根据具体情况，选择适合自己的学习和练习方式，并且要多做真题和模拟题，加强对知识点的掌握和理解，提高考试的准确性和速度。
二级公共基础知识总结（30 分：10 选择+5 填空）第一章数据结构与算法．算法1.概念：是解题方案的准确而完整的描述。
算法不等于程序，也不等于计算方法。
2. 基本特征：（1）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；（2）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止；（3）可行性，算法原则上能够精确地执行；（4）拥有足够的情报。
3.基本要素：一是对数据对象的运算和操作；二是算法的控制结构。
4.指令系统：一个计算机系统能执行的所有指令的集合。
5.基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。
6.基本控制结构：顺序结构、选择结构、循环结构。
7.基本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。
8.算法复杂度（算法效率的度量）（1）算法时间复杂度：指执行算法所需要的计算工作量。
即算法执行过程中所需要的基本运算次数。
通常，一个算法所用的时间包括编译时间和运行时间。
（2）算法空间复杂度：指执行这个算法所需要的内存空间。
包括算法程序所占的空间，输入的初始数据所占的空间，算法执行过程中所需的额外空间。
二．数据结构1. 数据的基本单位是数据元素2.数据结构：指相互有关联的数据元素的集合。
3.数据的存储结构(也称数据物理结构) ：数据的逻辑结构在计算机存储空间中的存放形式4.数据的存储结构有顺序、链接、索引、散列。
5.数据结构类型(按各元素之间前后件关系的复杂度划分) ：(1)线性结构的条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件。
( 2)非线性结构：不满足线性结构条件的数据结构。
6. 线性结构：( 1 )线性表①记录：由若干项数据元素组成的数据元素②文件：由多个记录构成的线性表。
③线性表的顺序存储结构基本特点：a)线性表中所有元素所占的存储空间是连续的；b)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的④线性链表(线性表的链式存储结构)数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。
结点由两部分组成：a）用于存储数据元素值，称为数据域；b）用于存放指针，称为指针域，用于指向前一个或后一个结点。
★在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
★链式存储方式即可用于表示线性结构，也可用于表示非线性结构。
★链式存储结构需要更多地存储空间）栈①限定在一端（即栈顶）进行插入与删除的线性表。
②栈顶位置用指针top 表示。
栈底位置用指针bottom 表示。
③栈按照“先进后出”（FILO）或“后进先出” （LIFO）组织数据，栈具有记忆作用。
④栈的存储方式有顺序存储和链式存储。
⑤栈的基本运算：a）入栈运算，在栈顶位置插入元素；b）退栈运算，删除元素（取出栈顶元素并赋给一个指定的变量）；c）读栈顶元素，将栈顶元素赋给一个指定的变量，此时指针无变化。
⑥ 栈的元素个数=bottom-top+13）队列①指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。
用rear 指针指向队尾，用front 指针指向队头元素的前一个位队列是“先进先出”(FIFO)或“后进后出”(LILO)的线性表。
队列运算包括：a) 入队运算：从队尾插入一个元素；b) 退队运算：从队头删除一个元素。
⑤队列的顺序存储结构一般采用队列循环的形式。
循环队列s=0表示队列空；s=1且front=rear 表示队列满。
⑥循环队列的元素个数：front<rear 时，元素个数=rear-front ；front>rear 时，元素个数=n (循环队列容量)-front+rear7．非线性结构(1)树①每一个结点只有一个前件，称为父结点。
②没有前件的结点只有一个，称为树的根结点，简称树的根。
③每一个结点可以有多个后件，称为该结点的子结点。
④没有后件的结点称为叶子结点。
⑤一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。
⑥树的最大层次称为树的深度。
( 2)二叉树① 特点：a) 非空二叉树只有一个根结点；b) 每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
②满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。
完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。
③基本性质：a)在二叉树的第k层上，最多有2k-1(k > 1)个结点；b)深度为m的二叉树最多有2m-1个结点；c)度为0的结点(即叶子结点) =度为2 的结点数+1；d)二叉树总结点数=度为0的结点数+度为1 的结点数+度为2 的结点数e)具有n个结点的二叉树，其深度至少为[Iog2n]+1,其中[Iog2n]表示取log2n 的整数部分f)具有n 个结点的完全二叉树的深度为[Iog2n]+1 ；g)完全二叉树中度为1 的节点只可能是0或1 个补充：增加度为1 的结点不会影响二叉树的叶子结点数，每增加一个度为2 的结点便会增加一个叶子结点，没有度为2 的结点时叶子结点数为1。
④二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。
⑤二叉树的遍历：a)前序遍历(DLR，首先访问根结点，然后遍历左子树，最后遍历右子树；b ）中序遍历（LDR ,首先遍历左子树，然后访问根结点，最后遍 历右子树；C ）后序遍历（LRD首先遍历左子树，然后访问遍历右子树，最 后访问根结点。
以下遍历以该树为例前序遍历结果为 a b d e h i c f g;中序遍历结果为 d b h e ia f c g;后序遍历结果为 d h i e b f g c a例2 :图1.13的二叉树。
（1）前序遍历T11;在访问T11时，也以先序遍历原则，先访问T11的根结点D,然后再先访问整棵二叉树的根结点 A ，然后再先序遍历左子树 T1；在访问T1时， 也以先序遍历原则，先访问T1的根结点B,然后再先序遍历T1的左子树a先序遍历T11的左子树。
由于此时T11的左子树只有H结点，所以访问H 结点，T11 的左子树先序遍历结束，根据先序遍历的原则，进行先序遍历T11 的右子树。
由于T11 的右子树只有I 结点，故访问此结点后T11 的右子树的先序遍历结束。
先序遍历完T11 子树后，返回T1 子树，先序遍历T1的右子树。
先序遍历完T1子树后，接着先序遍历根结点A的右子树T2。
先序遍历完T2后，该二叉树的所有结点都已经访问过，各结点被访问的顺序为：ABDHIECFG（2）中序遍历：先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树。
对图1.12 的二叉树进行中序遍历，访问各个结点的顺序为：HDIBEAFCG（3）后序遍历：先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点。
对图1.12 的二叉树进行后序遍历，访问各个结点的顺序为：HIDEBFGC A下面树的先序、中序、后续遍历的结果依次为__ abdcef _、bdaecf _、_ dbefca 小结：逻辑结构可分为线性表和非线性表。
线性表包括栈、队列，其存储方式为顺序存储、链式存储均可。
链式型有：线性链表，带链的栈，带链的队列，循环链表等。
非线性表包括树（二叉树），其存储方式为链式存储。
8. 查找技术只能使用顺序查找的两种情况：（1）线性表为无序表，不管是顺序存储还是链式存储；（2）表采用链式存储结构，即使是有序线性表。
★★二分法查找只适用于顺序存储的有序表，对于长度为n的有序线性表，最坏情况只需比较Iog2n次，而顺序查找需要比较n次9.排序技术排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。
★相比以上几种（除希尔排序法外），堆排序法的时间复杂度最小。
第二章程序设计基础」.程序设计设计方法和风格1•“清晰第一、效率第二”已成为当今主导的程序设计风格。
2.形成良好的程序设计风格需注意：（1）源程序文档化；（2）数据说明的次序要规范化；（3）语句的结构应该简单直接，不要为提高效率而复杂化；（4）输入数据前要有提示信息和输出信息符合规范。
3.注释：序言性注释和功能性注释。
结构化程序设计1. 基本原则：（1）自顶向下；（2）逐步求精；（3 ）模块化；（4）限制使用goto 语句。
2. 基本结构：（1）顺序结构：一种简单的程序设计，最基本、最常用的结构；（2）选择结构：又称分支结构，包括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分支来执行相应的语句序列；（3）循环结构：又称重复结构，可根据给定条件，判断是否需要重复执行某一相同或类似的程序段。
3. 基本工具：程序流程图，N-S 图4.特点：只有一个入口和出口三．面向对象的程序设计（主要考虑的是提高软件的可重用性）1.面向对象的程序设计的首次提出以60 年代末挪威奥斯陆大学和挪威计算机中心研制的SIMULA语言为标志。
2.面向对象方法的优点：（1）与人类习惯的思维方法一致；（2）稳定性好；（3）可重用性好；（4）易于开发大型软件产品；（5）可维护性好。
3.面向对象技术的基本特征：（1）抽象性（2）继承性①继承具有传递性，一个类实际上继承了他上层的全部基类的特性。
②继承分单继承和多重继承。
单继承指一个类只允许有一个父类，即类等级为树形结构；多重继承指一个类允许有多个父类。
* ：类的继承性是类之间共享属性和操作的机制，它提高了软件的可重用性。
（3）多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象（4）封装性4.对象是属性和方法的封装体，一个对象由对象名、属性和操作三部分组成，对象是实体的抽象。
（1）基本特点：标识唯一性，分类性，多态性，封装性（实现信息屏蔽）和模块独立性（2）属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。
操作描述了对象执行的功能，是对象的动态属性，操作也称为方法或服务。
5.类是指具有共同属性、共同方法的对象的集合。
所以类是对象的抽象，对象是对应类的一个实例。
6.消息是一个实例与另一个实例之间传递的信息。
对象间的通信靠消息传递。
它统一了数据流和控制流。
* ：在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送消息。
第三章软件工程基础软件工程基本概念1.计算机软件是包括程序、数据及相关文档的完整集合。
2.软件按功能分为：应用软件：教务管理系统系统软件：操作系统支撑软件（或工具软件）：编译软件，汇编软件3.软件危机主要表现在成本、质量、生产率等问题。
4.软件工程的核心思想是把软件产品看作是一个工程产品来处理。
