昆明学院公共基础知识讲义

1、昆明学院公共基础考试主要是在笔试出现，上机没有。笔试分数分布：选择题：有10个小题，共计20分填空题：有5个小题，共计10分公共基础知识总计30分在笔试。第一章 数据结构与算法1.1 算法考点1：算法的基本概念算法概念：所谓算法是指解题方案的准确而完整的描述。程序设计中的算法概念：算法是指解决某一个问题的方法和步骤。1、算法的基本特征（1）可行性：是指问题可以在现有的条件下解决（2）确定性：是指问题是确定的，不是模棱两可的（3）有穷性：是指有限的步骤（4）拥有足够的情报：处理该问题的所必须的数据考点2：算法的复杂度有关算法的复杂度主要掌握：（1）算法的时间复杂度时间复杂度的概念：是指执行该算法

2、所需要的计算工作量时间复杂度的概念分析：时间复杂度其实就是指执行该算法的循环次数的一个量值我们一般衡量算法的时间复杂度的时候，有这么两种情况：第一种：是指最好的情况下第二种：是指最坏的情况下（2）算法的空间复杂度空间复杂度的概念：是指在执行该算法是所占用的内存空间。空间复杂度的概念分析：空间复杂度主要是衡量算法在执行的过程中，所占有的内存空间大小，并不是其他所占内存空间大小。例如：算法在没有执行的情况下，占有的内存，不是空间复杂度。一定要注意是在执行的过程中，所占有的内存空间大小。注意：算法的时间复杂度大，其空间复杂度不一定大算法的时间复杂度晓，其空间复杂度不一定小1.2 数据结构的基本概念考

3、点3：数据的逻辑结构与存储结构1、数据的逻辑结构概念：是指反映数据元素之间逻辑关系的数据结构常用的逻辑结构：顺序、链接、索引等结构。注意：结构的概念：是指数据元素之间前后件的关系。比如：1,2,3,4,5春、夏、秋、冬2、数据的物理结构(存储结构)概念：是指数据的数据结构在计算机存储空间中的存放形式也可以称之为：数据的存储结构考点4：线性结构与非线性结构重点掌握线性结构与非线性结构的概念在数据结构中，将数据分为两种结构：线性结构和非线性结构线性结构：满足一下两个条件，第一：有且只有一个根节点；第二：每一个节点最多有一个前件，也最多有一个后件。概念解释：前件：是指某一个元素，离这个元素最近的前一

4、个元素后件：是指某一个元素，离这个元素最近的后一个元素前件，有的书本上面称之为前驱后件，有的书本上面称之为后驱非线性结构：不是线性结构的就是非线性结构1.3 线性表、栈和队列考点5：线性表和栈1、线性表的基本概念线性表是n(n=0)个元素a1,a2,a3,an组成的一个有限序列，表中除了第一个以外的每一个元素，有且只有一个前件；除最后一个元素外每一个元素，有且只有一个后件。也可以表示为：（a1,a2,a3,an）2、线性表的顺序存储结构线性表的顺序存储结构具有的特点： 线性表中所有元素所占的存储空间是连续的 线性表中各数据元素在存储空间中是按逻辑顺序依次存储的3、栈的定义栈是一种特殊的线性结构

5、栈的概念：栈是一种先进后出或后进先出的线性结构栈的概念分析：栈其实就是一个死胡同4、栈的顺序存储及运算栈有三个基本的运算：入栈、读栈、退栈总结：栈中指向栈底的指针是用bottom来表示栈中指向栈顶的指针是用top来表示栈顶指针是可以来回移动的，栈底指针不能移动栈可以顺序存储，也可以链式存储考点6：队列及其基本运算1、队列的定义队列的概念：是指允许在一端进行插入而另一端进行阐述的线性表。允许插入的一端称为队尾，通常使用指针rear表示。尾指针总是指向最后插入的元素；允许删除的一端称为排头，通常使用指针front表示，排头指针指向排头元素的前一个位置。队列的概念就是先进先出2、循环队列及其运算1.

6、4 线性链表考点7：线性链表的基本概念重点掌握概念在链式存储结构中，存储数据结构的存储空间可以不连续，各数据节点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式既可以用于表示线性结构，也可以表示非线性结构。总结：链式存储所占有的空间一般情况是比顺序存储所占的空间要大1.5 树与二叉树考点8：树与二叉树1、树的基本概念需要掌握以下树的基本概念：根节点：没有前件的节点，称为根节点兄弟节点：拥有同一个前件的节点，称为兄弟节点叶子节点：没有后件的节点，称为叶子节点节点的度：该节点所拥有的后件的个数，或某一个节点所拥有子节点的个数。树的度：在一个树结

7、构中，该节点拥有的最大子节点个数，称为该树的度。树的深度：树的最深层次数，就称之为树的深度2、什么是二叉树二叉树的概念：该树中的最大节点的度为2二叉树中有：度为0的节点(叶子节点)、度为1的节点、度为2的节点二叉树的特点： 非空的二叉树只有一个根节点 每一个节点最多有两个子树，且分别称为该节点的左子树和右子树3、二叉树的性质（1）在二叉树的第k层上，最多有2k-1（k=1）个节点分析：第k层，最多拥有2k-1（k=1）个节点是指该层处于满节点情况。每一层能够容纳的最大节点个数。（2）深度为m的二叉树最多有2m-1个节点。深度为m是指二叉树有m层。分析：深度为m的二叉树最多有2m-1个节点，是指

8、该二叉树是满二叉树的情况。（3）在任意一颗二叉树中，度为0的节点（叶子节点）总是比度为2的节点多1个。4、满二叉树与完全二叉树（1）满二叉树概念：满二叉树是指该树每一层节点数都满足性质1（2）完全二叉树概念：完全二叉树是指该树的最后一层从右边开始缺少叶子节点，其他层的节点数满足性质1总结：计算二叉树中节点总数的公式：节点总数 = 度为0的节点数 + 度为1的节点数 + 度为2的节点数计算二叉树中叶子节点总数的公式：度为0的节点总数 = 度为2的节点总数 + 1计算二叉树中度为2的节点的总数的公式：度为2的节点总数 = 度为0 的节点总数 1考点9：二叉树的遍历二叉树的遍历有三种：前序遍历、中序

9、遍历、后序遍历（1）前序遍历先根，后左(左子树)，再右(右子树)（2）中序遍历先左(左子树)，后根，再右(右子树)（3）后序遍历先左(左子树)，后右(右子树)，再根1.6 查找技术重点掌握时间复杂度考点10：顺序查找顺序查找的时间复杂度：如果顺序的线性表长度为n，那么，查找其中满足条件的元素，最好的情况下，时间复杂度为：1最坏的情况下，时间复杂度为：n没有找到的时间复杂度：n考点11：二分查找二分查找的时间复杂度：最坏的情况下的时间复杂度为：log2n注意：时间复杂度也可以表示为数学的函数形式：二分查找的时间复杂度为：log2n 或 O(log2n)1.7 排序技术考点12：各种排序方法1、冒

10、泡排序法时间复杂度：最坏情况下：n(n-1)/2 或 On(n-1)/22、快速排序法时间复杂度：最坏的情况下：Cmax = n(n-1)/2 或 On(n-1)/2其中Cmax是指比较次数达到最大次数3、简单插入排序法时间复杂度：最坏的情况下：n(n-1)/2 或 On(n-1)/24、希尔排序时间复杂度：最坏的情况下：n1.5 或 O(n1.5)5、简单选择排序法时间复杂度：最坏的情况下：n(n-1)/2 或 On(n-1)/26、堆排序法时间复杂度：nlog2n 或 O(nlog2n)第二章 程序设计基础2.1 程序设计风格考点1：程序设计风格1、源程序文档化需要考虑的情况有：（1） 符

11、号名的命名（2） 程序注释程序的注释分为两种： 功能性注释 序言性注释（3）视觉组织2、数据说明的方法3、语句的结构重点掌握：清晰第一、效率第二4、输入和输出注意：掌握，程序必须要符合高内聚，底耦合2.2 结构化程序设计考点2：结构化程序设计的原则主要的原则有四点：（1） 自顶向下（2） 逐步求精（3） 模块化（4） 限制使用goto语句 考点3：结构化程序的基本结构与特点程序设计中有三大基本结构：（1） 顺序结构（2） 选择结构（3） 重复结构（循环结构）考点4：结构化程序设计原则和方法的应用结构化程序设计的原则主要把握以下内容：（1）尽量使用顺序结构、选择结构、重复结构来表示程序（2）选用

12、的控制结构只允许有一个入口和一个出口（3）程序语句组成容易识别的模块，每一个模块只有一个入口和一个出口（4）复杂的结构应该使用三大基本来嵌套（5）语句中没有的控制语句，则前后一致进行模拟（6）严格控制goto语句2.3 面向对象的程序设计注意：到目前为止，程序设计主要分为两种：第一种：结构化程序设计第二种：面向对象的程序设计考点5：面向对象方法的基本概念1、对象(Object)（1）标识唯一性（2）分类性（3）多态性：相同的消息对不同的对象有不同的动作（4）封装性：这里需要注意：封装性与隐藏性的不同（5）模块独立性较好注意：模块与其他不同模块联系越少，就说明独立性越好2、类将属性、操作(方法)

13、相似的对象归为一类3、消息概念：面向对象的世界是通过对象与对象彼此的合作来推动的，对象之间的这种相互合作需要一个机制来协助进行，这种机制就称之为“消息”4、继承相似生物学中的遗传继承是指子类承接了父类的某一些特性和方法也就是说，子类具有一些父类共同的特征5、多态性概念：对象根据所接收的消息而做出的动作第三章 软件工程基础3.1 软件工程的基本概念考点1：软件的定义与分类软件的分类：按功能分类：应用软件、系统软件和支撑软件(工具)软件工程的概念：是应用于计算机软件的定义、开发和维护的一整套的方法、工具、文档、实践标准和工序软件危机：主要是指软件的开发过程当中，软件的质量不好控制、预算经常超支、软

14、件开发不规范、软件开发的效率比较低下。软件工程有三要素：方法、工具和过程在第三章中，重点掌握方法和工具软件的分类：系统软件：主要是指操作系统应用软件：我们在操作系统中一般使用的软件大多都属于应用软件支撑软件：一般是对某一种应用或服务的支持，这类软件称之为支持软件，例如：手机或固定电话的收费系统在第三章中，重点掌握，软件工程的执行过程当中的，每一个阶段的方法和工具，也就是在每一个阶段使用的什么方法、使用了什么工具，这里是需要重点掌握的。考点2：软件的生命周期软件开发的周期主要包括三大阶段：（1）定义阶段可行性分析、需求分析（2）开发阶段概要设计、详细设计、实现(编码写程序)、调试3）维护阶段使用

15、、维护、退役“不可与夏虫语冰”3.2 结构化分析方法考点3：关于结构化分析的常用工具重点掌握数据流图和数据字典结构化分析方法是结构化程序设计理论在软件需求阶段的运用，是使用数据流图(DFD)、数据字典（DD）、结构化语言和判定树、判定表等工具。1、数据流图数据流图（DFD）：是描述数据处理工程的工具重点掌握，数据流图中的箭头图元。箭头这个图元是指数据流2、数据字典数据字典（DD）：是结构化分析方法的核心概念：数据字典是对数据流图中出现的所有元素的具体的命名总结：在软件工程的定义阶段，需求分析需要使用的工具：数据流图、数据字典数据流图中的所有定义的元素，在数据字典中解释考点4：软件需求规格说明书

16、软件需求规格说明书：是需求分析阶段的最后成果，是软件开发过程中的重要文档之一。1、软件需求规则说明书的作用（1）便于哟用户、开发人员进行理解和交流（2）反映出用户问题的结构，可以作为软件开发工作的基础和依据（3）作为确认测试和验收的依据2、软件需求规则说明书的内容(了解)3、软件需求规则说明书的特点（1）正确性（2）无歧义性（3）完整性（4）可验证性（5）一致性（6）可理解性（7）可修改性（8）可追踪性3.3 结构化设计方法考点5：有关软件设计的基本内容1、软件设计的基础掌握此处的概念2、软件设计的基本原理（1）抽象：是指抛开表面现象，取得其本质性的内容，是一种分析方法（2）模块化（3）信息隐

17、蔽内聚性：是指一个模块内部结构之间联系的紧密程度耦合性：是指若干个模块之间的联系的紧密程度高内聚，低耦合总结：在软件工程的过程当中，软件设计是指开发阶段中的概要设计和详细设计考点6：结构化设计方法的详细设计详细设计的过程中，我们所使用的工具：图形工具：程序流程图、NS盒式图、PAD、HIPO表格工具：判断表语言工具：PDL（伪代码、伪码）（1）程序流程图重点掌握程序流程图中的图元： 箭头：是指控制流 棱形：是指逻辑条件总结：在数据流图的工具中，箭头是指数据流在程序流程图的工具中，箭头是指控制流（2）NS盒式图NS盒式图是对程序流程图的改进（3）PAD图PAD图是问题分析图（4） PDL过程设计

18、语言，也称为结构化的英语和伪码补充：在软件工程中，软件系统结构图的宽度、深度要求掌握宽度的概念：是指软件系统结构图中，某一层拥有最大的模块数深度的概念：是指软件系统结构图中，所拥有最大层次数3.4 软件测试考点7：软件测试的目的软件测试的目的：使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求或是弄清楚预期结果与实际结果之间的差别。软件测试的目的（简单的）：就是发现错误而执行程序的过程考点8：软件测试的方法与技术1、静态测试和动态测试软件测试从是否需要执行被测试软件的角度来分类，分为两种：静态测试和动态测试（1） 静态测试：使用人工的方式来静态检查软件的代码（2）

19、 动态测试：使用计算机来执行测试软件2、黑盒测试和白盒测试白盒测试：主要是指在测试的过程中可以看到软件内部的代码黑盒测试：主要是指在测试的过程中不可以看到软件内部的代码白盒测试的基本原则：保证所测试的模块中每一个独立路径至少执行一次；保证所测试模块所有判断的每一个分支至少执行一次；保证所测试模块每一个循环都在边界条件和一般条件下至少执行一次；验证所有内部数据结构的有效性。白盒测试的主要方法有：（1） 逻辑覆盖测试（2） 基本路径测试3、黑盒测试黑盒测试也称为功能测试或数据驱动测试。黑盒测试主要有：等价类划分、边界值分析法、错误推测法、因果图等。（1） 等价类划分法（2） 边界值分析法（3） 错

20、误推测法考点9：软件测试的实施软件测试的一般过程按照4个步骤：单元测试、集成测试、验收测试和系统测试（1）单元测试单元测试是指对软件中的最小模块进行测试（2）集成测试集成测试是指测试与组装软件的过程（3）验收测试验收测试是指验证软件的功能与性能（4）系统测试系统测试是指软件在一定具体的环境下运行的过程测试3.5 程序的调试考点10：基本概念重点掌握：调试的目的和任务调试的任务：就是诊断和修改程序中的错误简单来说：改错误调试的目的：更正错误第四章 数据库设计基础4.1 数据库系统的基本概念考点1：数据库与数据库管理系统VF是一个数据库管理系统，DBMS数据(Data):数据库(DataBase)

21、:数据定义语言(DDL)：create、drop、alter数据操纵语言(DML)：select、insert、update、delete数据控制语言(DCL)：考点2：数据库系统数据库系统（简称为DBS）：由以下部分组成：数据库、数据库管理系统、数据库管理员、系统平台(软件平台和硬件平台)数据库系统包含数据库和数据库管理系统DBS包含DB和DBMS考点3：数据库系统的发展数据库系统的发展阶段主要有三种：人工管理阶段、文件系统阶段、数据库系统阶段考点4：数据库系统的基本特点1、数据的集成性主要表现在三个方面2、数据的高共享性和低冗余性3、数据独立性数据的独立性的概念：是指数据与程序之间相互不依

22、赖数据独立性分为物理独立性和逻辑独立性物理独立性的概念：物理独立性是指数据的物理结构的改变，不影响数据库的逻辑结构。逻辑独立性的概念：数据库总体逻辑结构的概念，不需要相应修改程序4、数据的统一管理与控制（1）数据的完整性检查（2）数据的安全性保护（3）并发控制考点5：数据模式数据库系统内部具有三级模式和二级映射其中，三级模式是指概念模式、内部模式和外部模式其中，二级映射是指概念模式到内部模式的映射、外部模式到概念模式的映射（1）概念模式概念模式是数据库系统中全局数据逻辑结构的描述，是全体用户的公共数据视图（2）外模式外模式一般又称之为“子模式”或“用户模式”数据库的外模式，一般是指数据库的操作界面（3）内模式内模式又称为物理模式，给出数据库物理存储结构与物理存取方法。4.2 数据模型考点6：E-R模型(实体联系模型)1、E-R模型的基本概念（1）实体（2）属性（3）联系在VF中的联系一共有三个：一对一联系：可以表示为1:1一对多联系：可以表示1：n多对多联系：可以表示m：n2、E