软件技术基础课程复习教学提纲.ppt
软件技术基础课程复习第一章第一章 知识点知识点l计算机软件的概念l程序、数据和文档的集合l软件=程序+数据+文档l软件分类：系统软件和应用软件l操作系统（不需要其他软件支持）。l语言处理、服务和数据库管理。l软件设计方法l面向数据流l面向数据结构l面向对象第二章第二章 知识点知识点l数据、数据元素、数据对象、数据项关系l数据元素是数据的基本单位l数据项是数据的最小单位l数据对象是相同属性的数据元素的集合l数据结构：DS=(D,R)l数据结构包括数据的逻辑结构和物理结构l逻辑结构：线性结构和非线性结构。l物理结构：顺序存储和链式存储。l算法的特征l有穷性、确切性、输入、输出、可行性l算法的时间复杂度l问题规模n的函数，频度最大的语句来度量l算法、程序和数据结构l算法是一系列解决问题的指令集合l程序是指一组指示计算机每一步动作的指令，通常用某种程序设计语言编写，运行于某种目标体系结构上。l数据结构是指同一数据对象中各数据元素间存在的一种或几种关系。l程序=算法+数据结构第二章第二章 知识点知识点l分析算法的时间复杂度i=1;while(i=1)LinkedList *p=L;int j=0;while(p!=NULL&jnext；j+；q=(LinkedList*)malloc(sizeof(LinkedList);qdata=x;qnext=pnext;pnext=q;不带头结点的链表的第不带头结点的链表的第i个元素前个元素前插入插入一个元素一个元素xai-1aiai+1xqpint delete(LinkList*h,int i)/i=1int delete(LinkList*h,int i)/i=1 LinkList*p=h,*q;LinkList*p=h,*q;int j=0;int j=0;while(p!=NULL&jnext；j+；q=p-next;p-next=q-next;/拆下拆下 free(q);/释放释放 return 1;return 1;删除第删除第i个结点的算法个结点的算法ai-1aiai+1pfree(q)ql空链表：h-next=NULLl堆栈的操作：lIIOOOIOI,IOOIOIIO()lIIIOOIOO,IOIIOIOO()l操作规则：先进后出；输出的数目小于等于输入的数目l循环队列：操作方便、避免浪费存储单元l队满:(rear+1)%M=front;l队空:rear=front;l入队:Arear=x;rear=(rear+1)%M;第四章第四章 知识点知识点l树：前驱唯一、后继不唯一。空树(n=0)l术语：结点的度、叶子结点、双亲、兄弟、孩子、结点的层数、树的深度、树的度、有序树、无序树。l二叉树：树的度不大于2，有序树（子树分左右）l树与二叉树的区别与联系：l都有仅有一个根，根无前驱，叶子无后继。二叉树的每个结点的度小于等于2，二叉树的子树有左右之分。l二叉树五种基本形态：0，D，DL，DR，DLRl满二叉树：有2h-1个结点，h为树的度l完全二叉树：结点都在该层最左边最左边l第i层上至多有2i-1（i1）个结点。l叶子结点数n0，度2结点数n2，满足n0=n2+1l二叉树的遍历：lDLRlLDRlLRDlHuffman树（最优树）l取最小和次小概率合并。从根到叶子编码。练习题练习题l已知：LRDDEACB，LDRDEABC。求DLR遍历，并画出二叉树。DEACBDEABCBCDEADEADEAADEDEEDBCAEDDLR：BAEDC1.000.190.210.400.600.280.170.110.050.020.030.060.070.100.3201000000111111bcfdahe0.070.190.020.060.320.030.210.10 a b c d e f g hg1010 00 10000 1001 11 10001 01 1011 0.320.210.190.070.060.030.020.10第五章第五章 知识点知识点l任意两个结点都可能相关，即邻接关系任意。l概念：G=(V,E)l无向图、有向图、完全图l无向安全图：n(n-1)/2l有向完全图：n(n-1)l顶点的度、入度和出度l边的权、网图、路径、路径长度、回路、子图、连通图、连通分量l邻接矩阵：判定顶点的度（无向、有向图）l邻接表：表头结点、表结点。l图的遍历：DFS/BFS（图、矩阵、邻接表）l最小生成树(网图的权值总和最小)：Prim（扩充顶点）、Kruskal（扩充边）。l拓扑排序第八章第八章 知识点知识点l操作系统：定义、五大功能、四个特征l进程与程序：区别，定义，三个状态，状态转换l死锁：定义、原因、必要条件l虚拟存储管理：页式、段式、段页式。第九章第九章 知识点知识点l软件=程序+数据+文档l软件生命周期：定义、模型（瀑布模型）l需求分析l软件设计l软件测试：定义、步骤、方法l请大家结合课后习题以及作业认真复习！l祝考试顺利！此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢
