python二级公共基础知识_python计算机二级公共基础知识

python二级公共基础知识

一、算法和数据结构
算法及其基本特征：
　　算法是对解题方法的准确而完整的描述。
　　算法的四个基本特征：可行性，确定性，有穷性，拥有足够的情报。
 算法的复杂度：
　　算法的时间复杂度是指执行算法所需的计算工作量，而计算工作量一般通过基本运算次数来衡量
　　算法的空间复杂度是指执行算法所需要的内存空间
 数据结构：
　　数据结构是指有关联的数据元素的集合。数据元素一般有共同的特征，例如早餐，午餐，晚餐构成一日三餐名的集合。而结构指的是数据元素之间的关系，继续引用前面的例子，早餐是午餐的前件，晚餐是午餐的后件，这就是这三个元素的关系。
 数据结构的表示：
　　B = (D,R),B表示数据结构，D表示数据元素的集合，R是D中元素间关系的集合。此外数据结构还能用图形来表示，用箭头来表示元素间的关系。
 线性结构和非线性结构：
　　线性结构指有且只有一个根节点(指起始元素)，每个节点最多只有一个前件也最多只有一个后件的非空数据结构
　　不满足线性结构条件的就是非线性结构
 线性表：
　　数据结构中，线性结构习惯性称为线性表。线性表若没有元素，则称为空表。若有元素，可表示为(a1,a2,a3,a4……)
 线性表的两种储存结构：
　　顺序储存：将线性表中的元素一个接一个的储存在相邻的存储区域中，按顺序储存的线性表也称为顺序表。这种表有两个特征：表中元素所占存储空间是连续的；表中元素在存储空间中是按逻辑顺序存放的
　　链接储存：链表
　　
栈和队列：
　　栈是一种特殊的线性表，它所有的插入和删除都在表的同一端进行，允许插入与修改的一端为栈顶，另一端为栈底。当栈中没有元素时，称为空栈。
　　栈的修改原则是后进先出或先进后出。栈的基本运算包括：入栈、退栈、读栈顶元素。
　　队列是指允许在一端进行插入另一端进行删除的线性表，允许删除的那一端称为队头，允许插入那一端称为队尾。
　　队列的修改原则是先进先出或后进后出。队列可用顺序存储的线性表来表示，用排头指针front指示退队运算的队头位置，用队尾指针rear指示入队运算的队尾位置。队列的顺序存储结构一般采用循环队列的形式，也就是将队列存储的最后一个位置绕到第一个位置，形成逻辑上的环状空间。当front=rear时，队列要么为满要么为空（选择题可能会考），实际使用时会用标志s来指示，s=1时为满，s=0时为空。
 线性链表：
　　线性链表指线性表的链式存储结构。指向链表中第一个节点的指针称为链表的头指针（HEAD），最后一个元素没有后件，所以最后一个节点的指针域为空，用null或0表示。
　　线性链表的存储单元是任意的。
　　在某些应用中，对线性链表中的每个节点设置两个指针，一个指针存放前件地址，称为左指针，一个指针存放后件地址，称为右指针。这样的线性链表称为双向链表。
　　栈和队列也可以用链式存储结构表示，只做了解。
 顺序表和链表的比较：
　　顺序表：优点：可以随机存取表中任意节点
　　　　　　　　　无须为表示节点间的逻辑关系额外增加存储空间
　　　　　　缺点：插入和删除的运算效率很低
　　　　　　　　　存储空间不利于扩充和动态分配
　　链表： 优点：进行插入和删除运算时，只需要改变指针即可，不需要移动元素
　　　　　　　　　存储空间易于扩充和动态分配
　　　　　　缺点：需要额外的空间（指针域）表示数据元素之间的逻辑关系
　　　　　　　　　存储密度较低
 
循环链表：
　　将单链表的第一个节点前增加一个表头节点。队头指针指向表头节点，最后一个节点的指针域由null改为指向表头节点，形成环状链。
　　循环链表中由于有表头指针存在，所以在表中没有元素时也至少要有一个节点存在
 树：
　　树是一种简单的非线性结构。图形就类似于族谱。
　　根节点：每个树只有一个没有前件的节点，称为根节点
　　父节点：在树形结构中，每个节点最多只有一个前件，该前件称为父节点
　　子节点：每个节点可以有多个后件，称为该节点的子节点
　　叶子节点：没有后件的节点称为叶子节点
　　度：一个节点拥有的后件个数称为度
　　深度：树的根节点为第一层，总层数就是树的深度
　　子树：以某节点的子节点为根构成的树称为该节点的子树　　
　　在树中，树的节点等于树中所有节点的度之和再加一（选择题中可能会用这个特性求某种节点的个数）
 二叉树：
　　二叉树和树形结构略有不同，特点如下：
　　　　二叉树可以为空，空的二叉树没有节点，非空二叉树有且只有一个根节点。
　　　　每个节点最多有两棵子树，即二叉树中不存在度大于2的节点。
　　　　二叉树的子树有左右之分，不能任意颠倒
　　二叉树的性质：
　　　　在二叉树的第k层上，最多有2的k-1次方个节点
　　　　深度为m的二叉树中，最多有2的m次方-1个节点
　　　　对任何二叉树，度为0的节点总是比度为2的节点多一个（选择题可能会用该特性求总节点个数）
　　　　具有n个节点的二叉树，其深度至少为log2n + 1，log2n取整数部分
　　　　具有n个节点的完全二叉树的深度为log2n + 1
 满二叉树和完全二叉树：
　　满二叉树是指除最后一层外，每一层的所有节点都有两个子节点的二叉树。
　　完全二叉树是指除最后一层外，每一层上的节点数均达到最大值，在最后一层只缺少右边的若干节点的二叉树。
 二叉树的存储结构：
　　二叉树通常采用链式存储结构，存储二叉树中元素的存储节点由数据域和指针域两部分构成。
 二叉树的遍历：
　　前序遍历：首先访问根节点，然后遍历左子树，最后遍历右子树，遍历子树时依旧按照此顺序
　　中序遍历：首先遍历左子树，然后访问根节点，最后遍历右子树，遍历子树时依旧按照此顺序
　　后序遍历：首先遍历左子树，然后遍历右子树，最后访问根节点，遍历子树时依旧按照此顺序
 查找技术：
　　顺序查找：从线性表的第一个元素开始，逐个将线性表中的元素与被查元素进行比较。最好情况查找一次，最差查找n次，平均查找n/2次。当线性表为无序表或采用链式结构的有序表只能使用顺序查找。
　　二分法查找：通过和中间值比较确定值在前半段还是后半段，然后再不断比较直到找出值。只有采用顺序存储结构的有序表才能使用二分法查找。
 排序技术：
　　交换类排序法：
　　　　冒泡排序：两两比较和交换，直到所有数据元素有序为止。最坏情况下需要排n(n-1)/2次
　　　　快速排序：取一个随机元素并通过与之比较大小将线性表分为两个子表，对子表不断进行该步骤直到分割的子表长度为1为止。最坏情况下要进行n(n-1)/2次比较，但实际上该方法效率比冒泡排序效率高。
　　插入类排序法：
　　　　简单插入排序：将n个元素分为两组，一组一个元素，为有序表，另一组n-1个元素，为无序表，通过将无序表中的元素与有序表中的元素进行比较再插入合适的位置来进行排序，当无序表为空，排序完成。最坏情况下需要n(n-1)/2次比较。
　　　　希尔排序：先取一个整数d<n，把所有元素分为d个组，所有距离为d的倍数的元素为一组，组成一个子序列。对每个子序列进行简单插入排序。然后取d1<d重复上述步骤，直到所有记录在一组中为止。最坏情况下比较的次数为n的r次方，1<r<2。
　　选择类排序法：
　　　　简单选择排序：从n个元素中选出最小的元素与第一个元素交换位置，在剩下的n-1个元素中选出最小的元素与第二个元素交换，重复该操作直到所有元素有序为止。最坏情况下要比较n(n-1)/2次。
　　　　堆排序：将元素排列成一颗完全二叉树，当所有节点按照大小顺序排列时称为堆。所有节点的值大于或等于左右节点的值，称为大根堆，所有节点的值小于或等于左右节点的值，称为小根堆。最坏情况需要nlog2n次比较。
 
 二、程序设计基础　　　　
 程序设计风格：
　　程序的质量受到程序设计的方法，技术，和风格等因素的影响。“清晰第一，效率第二”是当今主导的程序设计风格。
　　形成良好的程序设计风格需要的因素：
　　　　源程序文档化
　　　　数据说明风格
　　　　语句的结构
　　　　输入和输出
 结构化程序设计：
　　结构化程序设计方法的重要原则：自顶向下，逐步求精，模块化和限制使用goto语句
　　结构化程序设计的基本结构：顺序结构，选择结构，循环结构。共同特征是：只有一个入口和一个出口
　　结构化程序设计的优点：程序易于理解，使用和维护；提高了编程工作的效率，降低了软件开发成本。
　面向对象的程序设计：
　　优点：与人类思维方式一致
　　　　　稳定性好
　　　　　可重用性好
　　　　　容易开发大型项目
　　　　　可维护性好
　　基本概念：
　　　　　对象：由数据（属性）和方法（操作）两部分组成。特点：标识唯一性，分类性，多态性，封装性，模块独立性好
　　　　　类和实例：类是具有共同属性，共同方法的对象的集合，是关于对象的抽象描述，一个具体对象则是其对应类的一个实例
　　　　　消息：对象间的通信
　　　　　继承：类和类之间可以继承，子类可以继承父类的全部描述（数据和操作）
　　　　　多态性：子类对象可以像父类对象那样使用，同样的消息既可以发送给父类对象也可以发送给子类对象
 三、软件工程基础
软件工程的基本概念：
　　软件定义：计算机软件是由程序，数据及相关文档构成的完整集合，它与计算机硬件一起组成计算机系统
　　软件特点：软件是一种逻辑实体，具有抽象性
　　　　　　　软件没有明显的制作过程
　　　　　　　软件在使用期间不存在磨损老化问题
　　　　　　　对硬件和环境具有依赖性
　　　　　　　软件复杂度高，成本昂贵
　　　　　　　软件开发涉及诸多的社会因素
　　软件的分类：
　　　　计算机软件按功能分为应用软件，系统软件，支撑软件（工具软件）
　　软件工程：
　　　　三要素：方法，工具，过程
　　　　原则：抽象，信息隐蔽，模块化，局部化，确定性，一致性，完备性和可验证性。
　　软件过程：
　　　　软件过程是把输入转化为输出。
　　软件生命周期：
　　　　软件定义期，软件开发期，运行维护期。
　　　　  各阶段主要任务：
　　　　  　　问题定义：确定要解决的问题是什么
　　　　　　  可行性研究：解决该问题是否存在一个可行的解决方法，制定完成开发任务的实施计划
　　　　　　  需求分析：对待开发软件提出的需求进行分析并给出详细定义。编写软件规格说明书及初步的用户手册，提交评审
　　　　　　  软件设计：通常又分为概要设计和详细设计两个阶段，给出软件的结构、模块的划分、功能的分配以及处理流程。
　　　　　　  软件实现：在软件设计的基础上编写程序。
　　　　　　  软件测试：在设计测试用例的基础上，检验软件的各个组成部分。编写测试分析报告
　　　　　　  运行维护：将已交付的软件投入运行，同时不断地维护，进行必要而且可行的扩充和删改
 需求分析及其方法：
　　需求分析：
　　　　需求分析的任务是发现需求，求精，建模和定义需求的过程。
　　　　需求分析可分为四个方面：需求获取，需求分析，编写需求规格说明书和需求评审
　　　　需求分析方法可分为结构化分析方法和面向对象分析方法
　　数据化分析方法是使用数据流图，数据字典，结构化英语，判定表和判定树等工具来为结构化规格说明的目标文档。
　　数据流图注意事项：
　　　　每个元素都必须命名
　　　　对加工处理建立唯一，层次性的编号，且每个加工处理通常要求既有输入，又有输出
　　　　数据存储间不应有数据流
　　　　输入输出和读写相对应（一致性）
　　　　子图不大于父图中的处理个数，所有子图的输入输出数据流和父图中相对应处理的输入输出数据流必须一致
　软件设计及其方法：
　　软件设计的基本概念：
　　　　软件设计是确定系统的物理模型
　　　　从工程管理的角度来看可以分为两步：概要设计和详细设计
　　　　从技术观点来看可分为软件结构设计，数据设计，接口设计，过程设计
　　　　模块的独立程度由内聚性和耦合性衡量，耦合衡量不同模块彼此间互相依赖的紧密程度，内聚衡量一个模块内部各个元素彼此结合的紧密程度，模块的内聚性越高，耦合性越低，好的软件要做到高内聚低耦合。
　　概要设计：
　　　　概要设计又称总体设计，基本任务如下：设计软件系统结构，数据结构及数据库设计，编写概要设计文档（包括概要设计说明书，数据库设计说明书和集成测试计划）
　　　　结构图：
　　　　　　上级模块是控制其他模块的模块
　　　　　　从属模块是被另一个模块调用的模块
　　　　　　原子模块是没有从属节点的模块，相当于树中的叶子节点
　　　　　　深度表示控制的层数
　　　　　　宽度是最大模块数的层的控制跨度
　　　　　　扇入是调用一个给定模块的模块个数
　　　　　　扇出是由一个模块直接调用的其他模块个数
　　详细设计：
　　　　详细设计的任务是为软件结构图中的每一个模块确定实现算法和局部数据结构，用工具表示算法和数据结构的细节
 
软件测试：
　　软件测试就是在软件投入运行之前，尽可能多的发现软件中的错误，是保证软件质量和可靠性的关键步骤
　　软件测试准则：　　
　　　　所有测试都追溯到用户需求
　　　　在测试之前制定测试计划，并严格执行
　　　　充分注意测试中的群集现象
　　　　避免由程序的编写者测试自己的程序
　　　　不可能进行穷举测试
　　　　妥善保存测试计划，测试用例，出错统计和最终分析报告，为维护提供方便
　　软件测试的方法：
　　　　根据软件是否需要被执行，可以分为静态测试和动态测试。如果按照功能划分，可以分为黑盒测试和白盒测试
　　　　静态测试不实际运行软件，主要通过人工进行分析
　　　　动态测试是通过运行软件来检测正确性
　　　　白盒测试是测试者对软件十分了解然后测试软件功能
　　　　黑盒测试是测试者对软件完全不了解，然后进行测试
　　软件测试的实施：
　　　　单元测试：单元测试是对模块进行测试，可以采用动态测试和静态测试，动态测试以白盒测试为主，黑盒测试为辅
　　　　集成测试：集成测试是对模块组成的程序进行测试，目的是发现与接口有关的错误，通常使用黑盒测试
　　　　确认测试：确认测试的功能是检查软件的功能，性能及其他特征是否与用户的需求一致，通常采用黑盒测试
　　　　系统测试：系统测试是对软件系统的整体测试，在实际环境下进行一系列集成测试和确认测试
 
程序的调试：
　　基本概念：调试是在测试发现错误之后排除错误的过程，有两个步骤：根据错误的迹象确定程序中错误的确切性质，原因和位置；对程序进行修改，排除这个错误
　　调试方法：静态测试和动态测试
 四、数据库设计基础
数据库系统的基本概念：
　　数据：是描述事物的符号记录
　　数据库：是指长期储存在计算机内的，有组织的，可共享的数据集合
　　数据库管理系统：是管理数据库的系统软件，有三种数据语言：数据定义语言，数据操纵语言(查询或增删改)，数据控制语言（故障恢复，并发控制）
 数据库的基本特点：
　　数据的集成性、数据的高共享和低冗余，数据独立性，数据统一管理和控制（选择题会把数据库和文件管理系统作比较，这些基本特点文件系统都没有）
 数据库系统的内部结构体系：
　　数据库系统在其内部分为三级模式，概念模式，内模式和外模式
 数据模型的基本概念：
　　数据模型是对数据特征的抽象，他的三要素是数据结构，数据操作及数据约束
　数据模型的类别：
　　概念模型，数据模型，物理模型
 E-R模型：
　　基本概念:
　　　　实体：指客观存在并且可以相互区别的事物
　　　　属性：描述实体的特性称为属性
　　　　联系：实体之间的对应关系称为联系(一对一，一对多，多对多)
 
关系模型：
　　关系模型常用术语：
　　　　关系：一个二维表就是一个关系
　　　　属性：二维表中的一列称为属性，二维表中的属性个数称为属性元数
　　　　值域：每个属性的取值范围
　　　　元组：二维表中的一行称为元组
　　　　候选码：二维表中能唯一标识元组的最小属性集
　　　　主键或主码：有多个候选码则选择一个作为主键
　　　　外键或外码：表m中的某属性集是表n的候选键，则称该属性集为表m的外键或外码
　　关系模型中有3类完整性约束：
　　　　实体完整性约束，参照完整性约束和用户定义的完整性约束
 关系代数：
　　关系代数就是关系和关系之间的运算
　　差运算：关系R和关系S经过差运算后得到属于R但不属于S的元组，记为R-S
　　交运算：得出R和S共同拥有的元组，记为R∩S
　　并运算：由属于R或属于S的元组构成，记为R∪S
　　笛卡尔积运算：n元关系R有p个元组，m元关系S有q个元组，得出一个m+n元关系，元组个数为pq的元组。记为RS
　　投影运算：从关系模型中指定若干个属性组成新的元组，称为投影。记为πA®
　　选择运算：从关系中找出满足给定条件的元组的操作称为选择
　　除运算：笛卡尔积的逆运算
　　连接运算：对两个关系进行连接，根据条件来进行等值连接，大于连接，小于连接
　
数据库设计：
　　基本思想：过程迭代和逐步求精
　　方法：面向数据的方法和面向过程的方法
　　范式：
　　　　满足最低要求的叫做第一范式，在第一范式基础上进一步满足一定要求的叫做第二范式，以此类推
　　　　对于关系模式，若其中的每一个属性都已不能再分为简单项，则它属于第一范式，若在此基础上，存在每一个非主属性完全依赖于某个候选键，则它属于第二范式