1公共基础知识

《1公共基础知识》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一公共基础知识第1章数据结构与算法1•1算法是指解决方案的准确而完整的描述。算法的基木要素：1对数据对象的运算和操作；2算法的控制结构。算法的基本运算：算术运算，逻辑运算，关系运算，数据传输。算法效率的度量一一算法复杂度：时间复杂度和空间复杂度。时间复杂度是指执行算法所需要的计算工作量。通常，一个算法所用的时间包括编译时间和运行时间。算法空间复杂度是指执行这个算法所需要的内存空间。包描算法程序所占的空间，输入的初始数据所占的空间，算法执行过程屮所需的额外空间。空间复杂度和时间复杂度并不相关。1•2数据结构的基木概念数据结构：只冇某一数据对彖屮所冇数据成员

2、Z间的关系组成的集合。数据存储结构和逻辑结构的关系：一种数据的逻辑结构可以表示成多种存储结构即数据的逻辑结构和存储结构不一定一一对应。采用不同的存储结构其数据处理的效率是不同的。线性结构条件（一个非空数据结构）；（1）冇月只冇一个根节占•（2）每一个结点最多有二入前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。线性表、栈、队列、线性链表是线性结构，树，二叉树为非线性结构。1.3线性表及线性链表线性表示冇一组数据元素构成，数据元素的位置只取决丁自己的序号，元素Z间的相对位置是线性的。线性表的顺序存储机构有以下两个基本特点：（1）线性表屮所

3、有元素所占的存储空间是连续的；（2）线性表中个数据元索在存储空间中是按逻辑顺序依次存放的；线性链表是线性表的链式存储结构，数据结构中的每一个节点对应于一个存储单元这种存储单元称为存储节点，简称节点。线性链表不能随机存储。在链式存储结构中，存储数据结构的存储空间可以不连续，链式存储方式既可用于表示线性结构，也可用于表示非线性结构。1.4栈和队列栈是一种特殊的线性表，只允许在表的一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈按照“先进后出”（FIFO或”后进先出气LIFO）组织数据,栈具有记忆功能。队列是一种特

4、殊的线性表，只允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。队列是“先进先出“（FIFO）或”后进后出“（LILO）的线性表。1.5树与二叉树树是一种简单的非线性结构，在树结构屮，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根节点，简称树的根。每一个结点可以有多个后件，称为该结点的了结点。没有后件的结点称为叶了结点。二叉树是一种特殊的树形结构，二叉树的特点：(1)非空二叉树只冇一个根结点；(2)每一个结点最多有两棵子树，口分别称为该结点的左子树与右子树。二叉树的基木性

5、质：1.在二叉树的第K层上，最多有2八K・1(k>=l)个结点；2.深度为m的二叉树最多(rm)-l个结点；5.具有n个结点的完全二叉树的深度为【log2F】+1;满二叉树是指除最后一层外，毎一层上所有结点有两个子结点，则k层上有2k・l个结点深度为m的满二叉树有2m・l个结点。完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。二叉树的遍历：(重点)p5此处略1.6查找技术二分法查找只适用于顺序存储的有序表，1・7查找与排序技术(1)

6、如杲线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找。(2)即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。二分查找的条件：(1)用顺序存储结构(2)线性表是有序表。排序是指将-个无序序列整理成按值非递减顺序排列的有序序列。1.交换排序(1)冒泡排序法，在最坏的情况匚冒泡排序需要比较次数为n(n-l)/2.(2)快速排序法，在最坏的情况下，快速排序需要比较次数为n(n-l)/2o2.插入类排序法，(1)简单插入排序法，最坏情况需要n(n-l)/2次比较；(2)希尔排序法，最坏情况需要o(iTl・5)次比较。(大写0是算法复杂

7、度的表示方法3.选择类排序方法：(1)简单选择排序法，最坏情况需要n(n-l)/2次比较；(2)堆排序法，最坏情况需要O(nlog2F)次比较.第2章程序设计基础注释分序言性注释和功能性注释，语句结构清晰第一、效率第二。2.2结构化程序设计结构化程序设计方法的四条原则是：1.自顶向下；2.逐步求精；3.模块化；4.限制使用goto语句。结构化程序的基本结构和特点：(1)顺序结构(2)选择结构(3)循环结构2.3血向対象的程序设计面向对彖的程序设计以对彖为核心强调对彖的抽彖性，封装性，继承性和多态性。对象的基木特点:(1)标识唯一性；(2)分类性(3)多态

8、性；(4)封装性(5)模块独立性好类是指具有共同属性、共同方法的对彖的集合。所以