LOGO二级公共基础知识二级公共基础知识二级公共基础知识二级公共基础知识lxz0126126.com目目目目 录录录录第第1章章 数据结构与算法数据结构与算法1第第2章章 程序设计基础程序设计基础2第第3章章 软件工程基础软件工程基础3第第4章章 数据库设计基础数据库设计基础4第第第第1 1章章章章 数据结构与算法数据结构与算法数据结构与算法数据结构与算法1.1 算法算法11.2 数据基本概念数据基本概念21.3 线性表、栈和队列线性表、栈和队列31.4 线性链表线性链表 41.1 1.1 算法算法算法算法考点考点1：算法的基本概念：算法的基本概念算法：算法：是指对解题方案的准确而完是指对解题方案的准确而完整的描述整的描述1. 算法的基本特征算法的基本特征（1）可行性）可行性（2）确定性）确定性（3）有穷性）有穷性（4）拥有足够的情报）拥有足够的情报 1.1 1.1 算法算法算法算法2. 算法的基本要素算法的基本要素（1）对数据对象的基本操作）对数据对象的基本操作 算术运算、逻辑运算、关系运算、数据算术运算、逻辑运算、关系运算、数据传输传输（2）算法的控制结构）算法的控制结构1.1 1.1 算法算法算法算法考点考点2：算法的复杂度：算法的复杂度 1.算法的时间复杂度算法的时间复杂度 即指执行算法所需要的计算工作量。即指执行算法所需要的计算工作量。（1）平均性态）平均性态 即指用各种特定输入条件下的基本运算即指用各种特定输入条件下的基本运算次数的加权平均值来度量算法的工作量。次数的加权平均值来度量算法的工作量。1.1 1.1 算法算法算法算法1.算法的时间复杂度算法的时间复杂度 即指执行算法所需要的计算工作量。即指执行算法所需要的计算工作量。（1）平均性态）平均性态 即指用各种特定输入条件下的基本运算即指用各种特定输入条件下的基本运算次数的加权平均值来度量算法的工作量。次数的加权平均值来度量算法的工作量。计算公式：计算公式：A(n)=1.1 1.1 算法算法算法算法（2）最坏情况复杂性）最坏情况复杂性 即指在规模为即指在规模为n时，算法所执行的基本时，算法所执行的基本运算的最大次数。运算的最大次数。计算公式：计算公式：W(n)=maxt(x)W(n) 比比A(n) 好计算好计算2.算法的空间复杂度算法的空间复杂度指执行这个算法所需要的内存空间。指执行这个算法所需要的内存空间。1.2 1.2 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念考点考点3：数据的逻辑结构与存储结构：数据的逻辑结构与存储结构 简单地说，数据结构是指相互关联的数据元素的集简单地说，数据结构是指相互关联的数据元素的集合，即数据组织形式。所谓结构，就是指数据元素合，即数据组织形式。所谓结构，就是指数据元素之间的前后件关系。之间的前后件关系。 1.数据的逻辑结构数据的逻辑结构 指反指反映数据元素之间逻辑关系的数据结构。映数据元素之间逻辑关系的数据结构。 2.数据的存储结构数据的存储结构 数据的逻辑结构在计算机存储空间中的存数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。放形式称为数据的存储结构。 1.2 1.2 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念考点考点4：线性结构与非线性结构：线性结构与非线性结构 如果一个非空的数据结构满足下列两个条件：第一，如果一个非空的数据结构满足下列两个条件：第一，有且只有一个根结点；第二，每一个结点最多有一有且只有一个根结点；第二，每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线个前件，也最多有一个后件，则称该数据结构为线性结构。性结构。 如果一个数据结构不是线性结构，则称之为非线性如果一个数据结构不是线性结构，则称之为非线性结构。结构。 1.3 1.3 线性表、栈和队列线性表、栈和队列线性表、栈和队列线性表、栈和队列考点考点5：线性表和栈：线性表和栈 1. 线性表的基本概念线性表的基本概念 2. 线性表的顺序存储结构线性表的顺序存储结构 3. 栈的定义栈的定义 栈是限定在一端进行插入与删除的线性表栈是限定在一端进行插入与删除的线性表 4. 栈的顺序存储及运算栈的顺序存储及运算 (1) 入栈运算入栈运算 (2) 出栈运算出栈运算 (3) 读栈顶运算读栈顶运算1.3 1.3 线性表、栈和队列线性表、栈和队列线性表、栈和队列线性表、栈和队列考点考点6：队列及其基本运算队列及其基本运算 1. 队列的定义队列的定义 2. 循环队列及其运算循环队列及其运算 3. 栈的定义栈的定义 栈是限定在一端进行插入与删除的线性表栈是限定在一端进行插入与删除的线性表 4. 栈的顺序存储及运算栈的顺序存储及运算 (1) 入栈运算入栈运算 (2) 出栈运算出栈运算 (3) 读栈顶运算读栈顶运算1.4 1.4 线性链表线性链表线性链表线性链表*考点考点7：线性链表的基本概念：线性链表的基本概念 线性表的链式存储结构称为线性链表。线性表的链式存储结构称为线性链表。1.5 1.5 树与二叉树树与二叉树树与二叉树树与二叉树考点考点8：树与二叉树树与二叉树 1. 树的基本概念树的基本概念 2. 什么是二叉树什么是二叉树 3. 二叉树的的基本性质二叉树的的基本性质 4. 满二叉树与完全二叉树满二叉树与完全二叉树1.5 1.5 树与二叉树树与二叉树树与二叉树树与二叉树*考点考点9：二叉树的遍历二叉树的遍历 1. 前序遍历（前序遍历（DLR） 2. 中序遍历（中序遍历（LDR） 3. 后序遍历（后序遍历（LRD） DiagramDiagramGuild Design is one of aligned company with Microsoft Ltd, and we develop and provide the design templates for Office 97, 2000, and XP.ThemeGallery is a Design Digital Content & Contents mall developed by Guild Design Inc.TitleAdd your text Cycle DiagramCycle DiagramTextTextTextTextTextCycle nameAdd Your TextDiagramDiagramTextTextTextAdd YourTitle TextText 1Text 2Text 3Text 4Text 5Add YourTitle TextText 1Text 2Text 3Text 4Text 5TextTextDiagramDiagramConceptAdd Your TextTextTextTextTextTextTextDiagramDiagramAdd Your TextAdd Your TextAdd Your TextAdd Your TextAdd Your TextAdd Your TextAdd Your TextAdd Your TextDiagramDiagramAdd Your TextAdd Your TextAdd Your TextAdd Your Add Your TitleTitleDiagramDiagramAdd Your TextAdd Your TextAdd Your TextAdd Your TextAdd Your TextAdd Your TextTextTextTextDiagramDiagramTextTextTextTextAdd Your TitleAdd Your TitleDiagramDiagramTitleAdd Your TextAdd Your TextAdd Your TextAdd Your TextAdd Your TextAdd Your TextDiagramDiagram1ThemeGallery is a Design Digital Content & Contents mall developed by Guild Design Inc.2ThemeGallery is a Design Digital Content & Contents mall developed by Guild Design Inc.3ThemeGallery is a Design Digital Content & Contents mall developed by Guild Design Inc.DiagramDiagramYour TextYour TextYour TextYour TextYour TextYour TextYour TextYour Text2001200220032004Progress DiagramProgress DiagramPhase 1Phase 2Phase 3Block DiagramBlock DiagramTEXTTEXTTEXTTEXTTEXTTEXTTEXTTEXTTableTableTEXTTEXTTEXTTEXTTEXTTitle ATitle BTitle CTitle DTitle ETitle F3-D Pie Chart3-D Pie ChartTEXTTEXTTEXTTEXTTEXTTEXT