计算机公共基础讲义

1、计算机公共基础：数据结构与算法算法算法的复杂度：算法的时间复杂度执行该算法所需要的工作量的大小。算法的空间复杂度执行该算法所需的内存空间。数据结构分法一：逻辑结构物理结构物理结构是数据的逻辑结构在计算机中的存放形式。分法二：用前、后件的关系分线性结构 春夏秋冬如：线性表、线性链表、栈、带链的栈、队列、循环队列、非线性结构 如：二叉树线性表顺序存储的线性表（逻辑关系与物理位置一一对应）运算：1）插入：在有n个数据的线性表中，最坏情况下，需移动数据n次。2）删除：在有n个数据的线性表中，最坏情况下，需移动数据n-1次。链式存储的线性表（逻辑关系与物理位置不一定对应）顺序存储与链式存储的区别：1）顺

2、序存储中，逻辑关系与物理位置一一对应，而链式存储不一定；2）链式存储中，插入或删除一个数据比顺序存储更容易；3）链式存储存储数据比顺序存储耗费的空间大。栈“先进后出、后进先出”队列“先进先出、后进后出”循环队列中，数据元素的个数由front（队头指针）和rear（队尾指针）共同决定。循环队列中，数据元素个数的计算方法：rear-front情况1：rear-front0 差即为元素个数情况2：rear-front0 差+存储单元=元素个数情况3：rear-front=0 元素个数或空或满二叉树什么是二叉树？什么是满二叉树、完全二叉树？二叉树的性质：第k层上节点最多有2k-1个；深度为m的二叉树，

3、总共最多有2m-1个节点；叶子节点总是比度为2的节点多1个。二叉树的遍历前序遍历（父左右）中序遍历（左父右）后序遍历（左右父）查找技术顺序查找适用对象：顺序存储、链式存储速度：在有n个存储单元的线性表中，最坏情况下，需比较n次。二分法查找（折半查找）适用对象：有序、顺序存储速度：在有n个存储单元的线性表中，最坏情况下，需比较log2n次排序技术交换类排序 8冒泡排序法 n(n-1)/2快速排序法 n(n-1)/2插入类排序简单插入排序法 n(n-1)/2希尔排序法 O(n1.5)选择类排序简单选择排序法 n(n-1)/2堆排序法 O(nlog2n)程序设计基础 1-2分结构化程序设计的原则自顶

4、向下逐步求精模块化限制使用goto语句结构化程序设计的结构顺序结构选择结构循环结构（重复结构）对象的基本特点标识的唯一性分类性多态性封装性模块独立性软件工程基础 软件生命周期定义阶段（可行性研究需求分析）开发阶段（概要设计详细设计实现测试）维护阶段（使用维护退役）结构化分析方法（定义阶段的需求分析阶段）：数据流图 DFD 加工（转换） 数据流 存储文件（数据源） 源（潭）数据字典 DD判定树判定表三.开发阶段的详细设计常用工具：程序流程图 加工步骤 控制流 逻辑条件N-S图PAD图（问题分析图）PDL（过程设计语言）四.软件测试静态测试（主要通过人工进行）动态测试（基于计算机的测试）白盒测试（

5、内部测试）黑盒测试（外部测试）五软件测试步骤1.单元测试2.集成测试3.确认测试4.系统测试六软件调试第四章 数据库设计基础 1.数据库系统(DBS)的组成：数据库(DB)数据库管理系统(DBMS)数据库管理员(DBA)硬件软件2.数据库系统的发展：人工管理阶段文件系统阶段数据库系统阶段（层次数据库网状数据库关系数据库） 3.数据库系统的基本特点：）数据的集成性）数据的高共享性和低冗余性）数据独立性）数据统一管理与控制4.数据库系统的内部结构体系： 三级模式和二级映射。 三级模式：外模式（子模式、用户模式）概念模式内模式（物理模式）二级映射：外模式概念模式的映射概念模式内模式的映射5.数据模型

6、： 概念模型逻辑模型物理模型6.E-R模型（实体联系模型）： 实体：行、记录、元组 实体集：二维表、关系 -用“矩形”表示 属性：列、字段 -用“椭圆”表示 联系： -用“菱形”表示 一对一联系 1:1 一对多联系 1:m 多对多联系 m:n 关键字（主键-key-键）7.关系代数：基本运算插入（并）R U RRABC013852RABC456R U R=?ABC013852456删除（差）R-RRABC013852487RABC013456R-R=?ABC852487修改（R-R）U RRABC013852487RABC013RABC999（R-R）U RABC852487999查询投影（针对列）RABCD156324873659AC162835选择（针对行）RABCD156324873659ABCD3659笛卡尔积R X SRAB1349SCDE865039451R X S=?ABCDE138651303913451498654903949451扩展运算交R SRABC013852487SABC013999R S=?ABC013除（笛卡尔积的逆运算）R/S 或 RSRABCD12347856783412561242S1CD3456S2CD34S3CD345642RS1=？A