软件技术基础课程复习PPT课件

-,1,软件技术基础总复习-串讲,数据的逻辑结构,数据的操作：遍历、查找、删除、插入,数据结构,操作系统,软件工程,软件技术基础,算法与数据结构概述,操作系统的五大管理功能,瀑布模型,-,3,第一章知识点,计算机软件的概念程序、数据和文档的集合软件=程序+数据+文档软件分类：系统软件和应用软件操作系统（不需要其他软件支持）。语言处理、服务和数据库管理。软件设计方法面向数据流面向数据结构面向对象,-,4,第二章知识点,数据、数据元素、数据对象、数据项关系数据元素是数据的基本单位数据项是数据的最小单位数据对象是相同属性的数据元素的集合数据结构：DS=(D,R)数据结构包括数据的逻辑结构和物理结构逻辑结构：线性结构和非线性结构。物理结构：顺序存储和链式存储。算法的特征有穷性、确切性、输入、输出、可行性算法的时间复杂度问题规模n的函数，频度最大的语句来度量,-,5,算法、程序和数据结构算法是一系列解决问题的指令集合程序是指一组指示计算机每一步动作的指令，通常用某种程序设计语言编写，运行于某种目标体系结构上。数据结构是指同一数据对象中各数据元素间存在的一种或几种关系。程序=算法+数据结构,第二章知识点,-,6,分析算法的时间复杂度i=1;while(i=1)LinkedList*p=L;intj=0;while(p!=NULL,不带头结点的链表的第i个元素前插入一个元素x,ai-1,ai,ai+1,x,q,p,-,10,intdelete(LinkList*h,inti)/i=1LinkList*p=h,*q;intj=0;while(p!=NULL,删除第i个结点的算法,ai-1,ai,ai+1,p,free(q),q,-,11,空链表：h-next=NULL堆栈的操作：IIOOOIOI,IOOIOIIO()IIIOOIOO,IOIIOIOO()操作规则：先进后出；输出的数目小于等于输入的数目循环队列：操作方便、避免浪费存储单元队满:(rear+1)%M=front;队空:rear=front;入队:Arear=x;rear=(rear+1)%M;,-,12,第四章知识点,树：前驱唯一、后继不唯一。空树(n=0)术语：结点的度、叶子结点、双亲、兄弟、孩子、结点的层数、树的深度、树的度、有序树、无序树。二叉树：树的度不大于2，有序树（子树分左右）树与二叉树的区别与联系：都有仅有一个根，根无前驱，叶子无后继。二叉树的每个结点的度小于等于2，二叉树的子树有左右之分。二叉树五种基本形态：0，D，DL，DR，DLR满二叉树：有2h-1个结点，h为树的度完全二叉树：结点都在该层最左边,-,13,第i层上至多有2i-1（i1）个结点。叶子结点数n0，度2结点数n2，满足n0=n2+1二叉树的遍历：DLRLDRLRDHuffman树（最优树）取最小和次小概率合并。从根到叶子编码。,-,14,练习题,已知：LRDDEACB，LDRDEABC。求DLR遍历，并画出二叉树。,DLR：BAEDC,-,15,1.00,0.19,0.21,0.40,0.60,0.28,0.17,0.11,0.05,0.02,0.03,0.06,0.07,0.10,0.32,0,1,0,0,0,0,0,0,1,1,1,1,1,1,b,c,f,d,a,h,e,0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10,abcdefgh,g,1010001000010011110001011011,0.32,0.21,0.19,0.07,0.06,0.03,0.02,0.10,-,16,第五章知识点,任意两个结点都可能相关，即邻接关系任意。概念：G=(V,E)无向图、有向图、完全图无向安全图：n(n-1)/2有向完全图：n(n-1)顶点的度、入度和出度边的权、网图、路径、路径长度、回路、子图、连通图、连通分量,-,17,邻接矩阵：判定顶点的度（无向、有向图）邻接表：表头结点、表结点。图的遍历：DFS/BFS（图、矩阵、邻接表）最小生成树(网图的权值总和最小)：Prim（扩充顶点）、Kruskal（扩充边）。拓扑排序,-,18,第八章知识点,操作系统：定义、五大功能、四个特征进程与程序：区别，定义，三个状态，状态转换死锁：定义、原因、必要条件虚拟存储管理：页式、段式、段页式。