计算机公共基础讲义.docxVIP

计算机公共根底：

数据结构与算法

算法

算法的复杂度〔描述方法好不好〕：

算法的时间复杂度〔解决一个问题所消耗的工作量〕

执行该算法所需要的工作量的大小。

算法的空间复杂度

执行该算法所需的内存空间。

数据结构

分法一：

逻辑结构

物理结构〔空间位置〕

！物理结构是数据的逻辑结构在计算机中的存放形式。

分法二：用前、后件的关系分

线性结构春?夏?秋?冬

如：线性表、线性链表、栈、带链的栈、队列、循环队列、……

非线性结构

如：二叉树

区别：线性结构，前后件唯一

线性表

顺序存储的线性表〔逻辑关系与物理位置一一对应〕

运算：

1〕插入：在有n个数据的线性表中，最坏情况下，需移动数据n次。

2〕删除：在有n个数据的线性表中，最坏情况下，需移动数据n-1次。

链式存储的线性表〔逻辑关系与物理位置不一定对应〕

顺序存储与链式存储的区别：

1〕顺序存储中，逻辑关系与物理位置一一对应，而链式存储不一定；

2〕链式存储中，插入或删除一个数据比顺序存储更容易；

3〕链式存储存储数据比顺序存储消耗的空间大。

栈

“先进后出、后进先出”〔栈顶开，栈底闭〕

队列

“先进先出、后进后出”

Front指第一个值前一个值，rear指最后一个值。

循环队列中，数据元素的个数由front〔队头指针〕和rear〔队尾指针〕共同决定。

！循环队列中，后面无处插入那么插到前面，首尾相连。

循环队列中，数据元素个数的计算方法：rear-front

情况1：rear-front0差即为元素个数

情况2：rear-front0差+存储单元=元素个数

情况3：rear-front=0元素个数或空或满

二叉树

什么是二叉树？

度：子节点个数的多少

深度：层数

叶子节点：下面再无节点

根节点：最初的节点

父节点：下面还有节点

树的度：所有节点中最大的个数

二叉树的度为2

满二叉树：每个节点都有两节

完全二叉树：前几层必须为满二叉树，最后一层可无子树、可有两个子树、可有左子树无右子树。〔不可有右无左〕

二叉树的性质：

第k层上节点最多有2k-1个；

深度为m的二叉树，总共最多有2m-1个节点；

叶子节点总是比度为2的节点多1个。

二叉树的遍历

遍历：再不重复的情况下，从头到尾浏览一遍。

前序遍历〔父?左?右〕〔A在第一个〕

中序遍历〔左?父?右〕〔A在中间〕

后序遍历〔左?右?父〕〔A在最后一个〕

查找技术

顺序查找

适用对象：顺序存储、链式存储

速度：在有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分

结构化程序设计的原那么

自顶向下

逐步求精

模块化

限制使用goto〔无条件返回〕语句

结构化程序设计的结构

顺序结构

选择结构

循环结构〔重复结构〕

对象的根本特点

标识的唯一性

分类性

多态性

封装性

模块独立性

软件工程根底

软件生命周期

定义阶段〔可行性研究?需求分析〕?开发阶段〔概要设计?详细设计?实现?测试〕?维护阶段〔使用?维护?退役〕

结构化分析方法〔定义阶段的需求分析阶段〕：

数据流图DFD

加工〔转换〕

数据流

存储文件〔数据源〕

源〔潭〕

数据字典DD

判定树

判定表

三.开发阶段的详细设计常用工具：

程序流程图

加工步骤

控制流

逻辑条件

N-S图

PAD图〔问题分析图〕

PDL〔过程设计语言〕

四.软件测试

静态测试〔主要通过人工进行〕

动态测试〔基于计算机的测试〕

白盒测试〔内部测试〕

黑盒测试〔外部测试〕

五．软件测试步骤

1.单元测试

2.集成测试

3.确认测试

4.系统测试

六．软件调试

第四章数据库设计根底

1.数据库系统(DBS)的组成：

数据库(DB)

数据库管理系统(DBMS)

数据库管理员(DBA)

硬件

软件

2.数据库系统的开展：

人工管理阶段?文件系统阶段?数据库系统阶段〔层次数据库?网状数据库?关系数据库〕

3.数据库系统的根本特点：

〕数据的集成性

〕数据的高共享性和低冗余性

〕数据独立性

〕数据统一管理与控制

4.数据库系统的内部结构体系：

三级模式和二级映射。

三级模式：

外模式〔子模式、用户模式〕

概念模式

内模式〔物理模式〕

二级映射：

外模式?概念模式的映射

概念模式?内模式的映射

5