计算机公共基础讲义.doc

《计算机公共基础讲义.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、计算机公共基础：第一章数据结构与算法%1.算法算法的复杂度（描述方法好不好）：1.算法的时间复杂度（解决一个问题所耗费的工作量）执行该算法所需要的工作量的大小。2.算法的空间复杂度执行该算法所需的内存空间。%1.数据结构分法一：1.逻辑结构2.物理结构（空间位置）!物理结构是数据的逻辑结构在计算机中的存放形式。分法二：用前、后件的关系分1.线性结构春夕夏T秋夕冬如：线性表、线性链表、栈、带链的栈、队列、循环队列、2.非线性结构如：二叉树3.区别：线性结构，前后件唯一%1.线性表1.2.顺序存储的线性

2、表（逻辑关系与物理位置运算：1）插入：在有n个数据的线性表中，最坏情况下，需移动数据n次。2）删除：在有n个数据的线性表中，最坏情况下，需移动数据次。链式存储的线性表（逻辑关系与物理位置不一定对应）对应）1)2)3)Front指第一个值前一个值,rear指最后一个值。顺序存储与链式存储的区别：顺序存储中，逻辑关系与物理位置一一对应，而链式存储不一定;链式存储中，插入或删除一个数据比顺序存储更容易；链式存储存储数据比顺序存储耗费的空间大。“先进后出、后进先出”（栈顶开，栈底闭）%1.队列“先进先出、后

3、进后出”循环队列中，数据元素的个数由front（队头指针）和rear（队尾指针）共同决定。!循环队列中，后面无处插入则插到前面，首尾相连。循环队列中，数据元素个数的计算方法:rear-front情况rear-front>0情况2：rear-front<0情况3：rear-front=0差即为元素个数差+存储单元=元素个数元素个数或空或满%1.二叉树1.什么是二叉树?度：子节点个数的多少深度：层数叶子节点：下面再无节点根节点：最初的节点2.3.4.父节点：下面还有节点树的度：所有节点中最大的个数二叉树

4、的度为2满二叉树：每个节点都有两节完全二叉树：前几层必须为满二叉树，最后一层可无子树、可有两个子树、可有左子树无右子树。（不可有右无左）二叉树的性质：1）第k层上节点最多有2"个；2）深度为m的二叉树，总共最多有2叭1个节点；3）叶子节点总是比度为2的节点多1个。二叉树的遍历遍历：再不重复的情况下，从头到尾浏览一遍。1）前序遍历（父夕左夕右）（A在第一个）2）中序遍历（左9父今右）（A在中间）3）后序遍历（左今右9父）（A在最后一个）u>.11*11*•tv%1.查找技术1•顺序査找适用对象：顺序存

5、储、链式存储速度：在有n个存储单元的线性表中，最坏情况下，需比较n次。1.二分法查找（折半查找）适用对象：有序、顺序存储速度：在有n个存储单元的线性表中，最坏情况下，需比较Iog2n次丿1・排序技术1.交换类排序81）冒泡排序法2）快速排序法2.插入类排序n(n-l)/2n(n-l)/21）简单插入排序法n（n-l）/22）希尔排序法0（n15）2.选择类排序1）简单选择排序法n（n-l）/22）堆排序法O（nlog2n）第二章程序设计基础1-2分%1.结构化程序设计的原则1.自顶向下2.逐步求精3

6、.模块化4.限制使用goto（无条件返回）语句%1.结构化程序设计的结构1•顺序结构2.选择结构3.循环结构（重复结构）三•对象的基本特点1.标识的唯一性2.分类性3.多态性4.封装性5.模块独立性第三章软件工程基础一.软件生命周期定义阶段（可行性研究夕需求分析）9开发阶段（概要设计夕详细设计少实现9测试）9维护阶段（使用9维护9退役）二•结构化分析方法（定义阶段的需求分析阶段）:1.2.数据流图DFDO加工（转换）—►数据流存储文件（数据源）I—I源（潭）数据字典DD3.判定树4.判定表三•开发阶

7、段的详细设计常用工具:1.程序流程图2.II加工步骤控制流.逻辑条件1.PAD图（问题分析图）2.PDL（过程设计语言）四•软件测试1.静态测试（主要通过人工进行）2.动态测试（基于计算机的测试）1）白盒测试（内部测试）五.软件测试步骤2）黑盒测试（外部测试）1•单元测试2•集成测试3•确认测试4•系统测试六.软件调试第四章数据库设计基础1•数据库系统（DBS）的组成：1）数据库（DB）2）数据库管理系统（DBMS）数据库管理员（DBA）硬件软件数据的集成性数据的高共享性和低冗余性数据独立性数据统一

8、管理与控制外模式（子模式、用户模式）概念模式内模式（物理模式）外模式9概念模式的映射概念模式T内模式的映射元组关系…用“矩形”…用“椭圆”…用“菱形99表示表示表示1:1l:mm:n关键字（主键・key■键）7•关系代数：1.基本运算1）插入（并）RUR'0138524562）删除（差）R・R、ABC013852487&ABC013456R-Rx=?ABC8524873)修改(R-ROUR''RABC013852487R，ABC013R、、ABC999(R・R、)UR