软件技术基础要点总结

《软件技术基础要点总结》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第一章1.算法的基本要素：一是要做哪些事（算法对数据的操作）二是决定做这些事情的先后顺序（控制结构）2.算法的基本特征：（1）能行性（2）确定性（3）有穷性（4）拥有足够的情报3.算法评价的标准（算法的复杂度主要包括）：时间复杂度和空间复杂度4.算法的时间复杂度：执行算法所需要的计算工作量算法的空间复杂度：执行这个算法所需要的内存空间5.用算法在执行过程中所需基本运算的执行次数来度量算法的工作量6.算法所执行的基本运算次数与问题规模相关7.对于一个固定规模，算法所执行的基本运算次数可能与特定的输入有关用①平均性态（平均时间复杂度）②最坏情况复杂性（最坏时间复杂度）来描述第二章1.数据结构研究

2、的主要问题：①分析数据的特征②选择逻辑结构和物理存储结构③在存储结构的基础上实现对数据的操作2.数据逻辑结构指数据元素前后件的关系，与它们在计算机中的存储位置无关；数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）3.常用的存储结构有顺序、链接、索引等存储结构顺序存储结构连续存放；逻辑上相邻，物理上也相邻结构简单，易实现插入、删除操作不便（需大量移动元素）链式存储结构非连续存放，借助指针来表示元素间关系结构较复杂，需要额外存储空间插入、删除操作简单，只要修改指针即可索引存储结构非连续存放检索速度快增、删操作简单散列存储结构散列存储结构数据元素无内在联系存储形式

3、不定哈希表就是这样结构4.5.数据运算是指对存放在物理结构上的数据，按定义的逻辑结构进行的各种操作（输入、检索、插入、删除、修改、排序）6.线性表：n（n≥0）个数据元素的有限序列线性表特点：均匀性有序性除了第一个元素，每一个元素都有一个前驱，除了最后一个元素每个元素都有一个后继7.线性表中所有元素所占的存储空间是连续的线性表中的各数据元素在存储空间中是按逻辑顺序依次存放8.顺序表：将线性表中的元素相继存放在一个连续的存储空间中；存储结构：数组；特点：线性表的顺序存储方式。逻辑上相邻，物理上相邻；存取方式：随机存取。9.栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶（top），表头

4、称为栈底（bottom）。10.栈的物理存储可以用顺序存储结构，也可以用链式存储结构。11.队列：一种特殊的线性表，遵守FIFO（FirstInFirstOut）规则。队列的数据元素重视从表末尾加入，从表头取出。队列的物理存储可以用顺序存储结构，也可用链式存储结构。12.frontRear13.循环队列区分队空队满长采用两种方法①增加一个标志位S；S=0队空S=1且rear==front队满14.程序中front==（rear+1）%MAXSIZE来判断队满15.二叉树的性质：①在二叉树的第i层上至多有2^(i-1)个结点（i≥1）②深度为k的二叉树至多有2^k-1个结点（k≥1）③对任何一

5、颗二叉树T，如果其叶结点数为n0，度为2的结点数为n2，则n0=n2+1④具有n个结点的二叉树，其深度至少为log2n+1⑥在编号完全的完全二叉树中，编号为i的结点，若存在做孩子，则其编号为2i；若存在有孩子，则其编号为2i+1；若存在父结点，则其编号为i/216.图是对结点的前驱和后继个数不加限制的数据结构。有向图：图中每条边都是顶点的有序对。无向图：图中每条边都是顶点的无序对。17．顶点间的关系边可描述为顶点的偶对，边是无序的。弧：顶点间的边是有序的。弧头：弧的终点（方向前方）。弧尾：弧的起始点称为弧尾（方向后方）。Vx（弧尾）→Vy弧头18.无向图中：顶点的度是以该顶点为一个端点的边的

6、条数。有向图中有入度和出度。19.路径：从顶点Vx到顶点Vy的顶点序列称为从Vx到Vy的路径。路径的长度是该路径上边或弧的数目。20.连通图：在无向图中，若每一对顶点间都有路径，称此图是连通图。第三章1.平均查找长度（ASL）：与关键字进行比较的平均次数。它是用来评价一个算法好坏的一个依据。顺序查找优点对结点的逻辑次序和存储结构无要求；缺点ASL较长。2.二分查找的先决条件是查找表中的数据元素必须有序。优点：ASL≤log2n；缺点：因要求有序，所以对所有数据元素按大小排序是非常费时的操作。3.分块查找又称索引顺序查找，这是顺序查找的一种改进方法。优点：插入、删除操作方便；只要找到对应的块，

7、在块中任意位置操作均可。缺点：索引表增加了辅助存储空间。4.哈希查找也成为散列查找，哈希查找则是通过计算存储地址的方法进行查找的。在哈希元素（地址）求解过程中，不同关键字值对应到同一个存储地址的现象称为冲突。即关键字K1≠K2，但哈希函数值H(K1)=H(K2)。处理冲突的方法：开放定址法Hi=(H(key)+di)MODm，再哈希法，链地址法。线性探测再散列di=1,2，…m-1二次探测再散列di=1^2,