VF资料(公共基础)

《VF资料(公共基础)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章数据结构与算法1.1算法算法：是指解题方案的准确而完整的描述基算法的基本特征：可行性、确定性、有穷性(有限的时间)、拥有足够的情报本算法的对数据对象的操作和运算：算术运算、逻辑运算、关系运算、数据传输概基本要素算法的控制结构定义：算法中各操作之间的执行顺序念类型：顺序、选择、循环算法设计基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法算法时间复杂度：算法所需要的计算工作量（算法所执行的基本运算次数）复杂度空间复杂度：执行这个算法所需要的内存空间1.2数据结构的基本概念逻辑结构：指反应数据元素之间逻辑关系的数据结构数据结构研究

2、的三个问题存储结构（物理结构）：数据的逻辑结构在计算机存储空间中的存放形式。（常用：顺序、链接、索引等结构）对各种数据结构进行的运算数据处理是指对数据集合中的各元素以各种方式进行运算包括插入、删除、查找、更改等运算，也包括对数据元素进行分析在数据结构中没有前件的结点称为根结点，没有后件的结点为叶子结点。空的数据结构：一个元素都没有的数据结构。定义：是指带有结构的数据元素的集合。数据结构类型线性结构：有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件。非线性结构1.3线性表及其顺序存储线性表是最简单、最常用的一种线性结构。有且只有

3、一个根结点，无前件非空线性表结构特征有且只有一个终端（叶子）结点，无后件除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件线性表顺序存储结构的基本特点所有元素所占的存储空间是连续的各元素在存储空间中是按逻辑顺序依次存放的1.4栈和队列限定在一端进行插入与删除的线性表栈顶：允许插入与删除的一端栈栈底：不允许插入与删除的一端先进后出或后进先出基本运算：入栈运算（上溢）、退栈运算（下溢）、读栈顶元素允许在一端进行插入、而在另一端进行删除的线性表队尾：允许插入的一端队中元素个数：队尾—对头队队头：允许删除的一端列先进先出或后进后

4、出基本运算：入队运算、退队运算循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间1.5线性链表线性表的链式存储结构称为线性链表栈和队列也可采用链式存储结构线性链表基本运算：插入、删除、合并、分解、逆转、复制、排序、查找1.6树与二叉树父结点：每一个结点只有一个前件，称为父结点。没有前件的结点只有一个，称为根。子结点：每一个结点可以有多个后件，这些后件称为子结点。没有后件的结点称为叶子结点。结点的度：一个结点所拥有的后件个数树的度：所有结点中的最大的度树的深度：树的最大层次根结点在第1层。叶子结点没有子树。特点：只有一

5、个根结点，每一个结点最多有2颗子树（左子树、右子树）在二叉树的第k层上，最多有2k-1（k>=1）个结点深度为m的二叉树最多有2m-1个结点二性质度为0的结点（叶子结点）是比度为2的结点多一个叉具有n个结点的二叉树，其深度至少为[log2n]+1树具有n个结点的完全二叉树，深度为[log2n]+1存储结构：链式存储结构前序遍历：根左右遍历中序遍历：左根右后序遍历：左右根当完全二叉树总结点n为偶数时，叶子节点的个数为：n/2当完全二叉树总结点n为奇数时，叶子节点的个数为：(n+1)/21.7查找技术查顺序查找：n（最坏）找二分法查找：loag

6、2n（最坏）1.8排序技术交换类排序冒泡排序法：n(n-1)/2（最坏）快速排序法：n(n-1)/2（最坏）O(nlog2n)（平均）排插入类排序简单插入排序法：n(n-1)/2（最坏）序希尔排序法：O(n1.5)（最坏）选择类排序简单选择排序法：n(n-1)/2（最坏）堆排序法：O(nlog2n)（最坏）第2章程序设计基础程序设计风格：清晰第一，效率第二注释一般分为：序言性注释和功能性注释结构化程序设计的原则：自顶向下，逐步求精，模块化，限制使用goto语句结构化程序的基本结构：顺序结构、选择结构、重复结构（循环结构）面向对象方法的优点：

7、与人类习惯的思维方法一致、稳定性好、可重用性好、易于开发大型软件产品、可维护性好对象：客观世界中的任何实体对象特点：标志唯一性、分类性、多态性、封装性、模块独立性好对象是类的一个实例。消息：是一个实例与另一个实例之间传递的信息，请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。在面向对象方法中，类之间共享属性和操作的机制称为：继承继承性的优点：相似的对象可以共享程序的代码和数据结构,从而大大减少了程序中的冗余信息,提高软件的可重用性,便于软件修改维护第3章软件工程基础软件：包括程序、数据及相关文档的完整集合软件按功能分为：应

8、用软件、系统软件、软件软件工程概念的出现源自软件危机软件危机：是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。软件危机归结为成本、质量、生产率等问题方法：完成软件工程