《公共基础知识》.ppt
《《公共基础知识》.ppt》由会员分享,可在线阅读,更多相关《《公共基础知识》.ppt(51页珍藏版)》请在课桌文档上搜索。
1、,1,全国计算机等级考试,二级公共基础知识,2,公共基础知识,内容:考试大纲数据结构与算法程序设计基础软件工程基础数据库设计基础,3,考试大纲,基本要求1、掌握算法的基本概念。2、掌握基本数据结构及其操作。3、掌握基本排序和查找算法。4、掌握逐步求精的结构化程序设计方法。5、掌握软件工程的基本方法,具有初步应用相关技术进行软件开发的能力。6、掌握数据库的基本知识,了解关系数据库的设计。,4,考试大纲,考试内容一、基本数据结构与算法1、算法的基本概念;算法复杂度的概念和意义(空间复杂度与时间复杂度)。2、数据结构的定义;数据的逻辑结构和存储结构;数据结构的图形表示;线性结构与非线性结构的概念。3
2、、线性表的定义;线性表的顺序存储结构及其插入删除运算。4、栈和队列的定义;栈和队列的顺序存储结构及其基本运算。5、线性单链表,双向链表与循环链表的结构及其基本运算。6、树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。7、顺序查找与二分查找算法;基本排序算法(交换类排序、选择类排序、插入类排序)。,5,考试大纲,考试内容二、程序设计基础1、程序设计方法与风格。2、结构化程序设计。3、面向对象的程序设计方法,对象,方法,属性及继承与多态性。,6,考试大纲,考试内容三、软件工程基础1、软件工程的基本概念;软件生命周期概念;软件工具与软件开发环境。2、结构化分析方法;数据流图,数
3、据字典,软件需求规格说明书。3、结构化设计方法;总体设计,详细设计。4、软件测试的方法;白盒测试,黑盒测试,测试用例设计;软件测试的实施;单元测试,集成测试,系统测试。5、程序的调试,静态调试与动态调试。,7,考试大纲,考试内容四、数据库设计基础1、数据库的基本概念;数据库,数据库管理系统,数据库系统。2、数据模型;实体联系模型及E-R图,从E-R图导出关系数据模型。3、关系代数运算,包括集合运算及选择、投影、连接运算;数据库规范化理论。4、数据库设计方法和步骤;需求分析、概念设计、逻辑设计和物理设计的相关策略。,8,考试大纲,考试题型选择题10 题每题 2 分共 20 分填空题5 题每题 2
4、 分共 10 分合计30 分,9,数据结构与算法,关键考点算法基本概念及算法复杂度数据的存储结构栈和队列线性链表二叉树基本概念及其特性查找技术,10,数据结构与算法,算法的基本概念1、算法算法是指解题方案的准确而完整的描述。注意:算法与数学上的计算方法不是同一个概念。算法要考虑计算机的特点,要考虑计算方法的可行性。算法也不等于程序。算法不考虑具体的机器及编程语言。解决问题时,总是先设计算法,然后进行编程。2、算法的基本特征可行性确定性有穷性拥有足够的情报算法是一个动态概念,强调实际的执行过程。数学上的计算方法是一个静态概念,注重理论上的正确性。数学上的计算方法是设计算法的基础。,11,数据结构
5、与算法,算法的基本概念3、算法的基本要素算法中对数据的运算和操作基本的运算和操作有:算术运算、逻辑运算、关系运算、数据传输。算法的控制结构控制结构决定操作的执行顺序。要求符合结构化原则,强调易读性。4、算法设计基本方法列举法 列举所有可能情况,检测其中符合条件的结果。归纳法 列举若干特殊情况,分析归纳出一般规律。递推 从已知初始条件出发,逐步推导出中间及最后结果。递归 将复杂问题归结为简单问题,在归结为更简单问题,。减半递推技术 将问题规模“减半”,并重复该“减半”的过程。回溯法 分析问题,找出某些线索,沿线索逐步试探。若试探成功,则继续,若试探失败,则回退。直至问题解决。,12,数据结构与算
6、法,算法的基本概念5、算法的时间复杂度指执行算法所需要的计算工作量算法工作量的度量应与计算机、编程语言、编程细节等无关。算法的工作量用算法所执行的基本运算次数衡量。算法工作量是问题规模的函数:算法的工作量=f(n)度量方法有:平均性态分析 计算其加权平均值最坏情况分析 计算其基本运算的最大次数6、算法的空间复杂度指执行算法所需要的存储空间包括:算法程序所占据的存储空间待处理数据所占据的存储空间算法程序执行中所需要的额外存储空间如果额外存储空间大小不随问题规模变化,则称之为算法原地工作。降低算法的空间复杂度,应从数据的存储空间和额外空间入手。,13,算法,定义特征复杂度(时间/空间),数据结构,
7、1.数据的逻辑结构,2.数据的存储结构,3.数据的运算,线性线性表栈、队列,非线性树形结构二叉树(满二叉树、完全二叉数),顺序存储链式存储,索引存储散列存储,查找(顺序、二分),修改,排序(交换、插入、选择),插入,删除修改,14,数据结构与算法,数据结构的基本概念1、数据结构数据结构是指相互有关联的数据元素的集合数据结构是指带有结构的数据元素的集合。结构 通常指前后件关系。主要研究:数据元素间的固有逻辑关系 数据元素在计算机中的存储关系 对各种数据结构进行的运算2、数据的逻辑结构指反映数据元素之间逻辑关系的数据结构前后件(直接前驱和直接后继)关系就是指逻辑关系3、数据的存储结构数据的逻辑结构
8、在计算机中的存储形式存储结构也称为物理结构同一种逻辑结构可以有不同的存储结构常用的有:顺序、链接、索引等形式,15,数据结构与算法,数据结构的基本概念4、数据结构的表示二元关系表示:两个要素:数据元素的集合D,该集合上的关系R。即:B=(D,R)如:D=春,夏,秋,冬 R=(春,夏),(夏,秋),(秋,冬)图形表示:标有元素值的方框表示结点,有向线段表示逻辑关系。春 夏 秋 冬5、线性结构和非线性结构线性结构:一个非空的线性结构有且只有一个根结点,每个结点最多只有一个直接前驱、最多只有一个直接后继。非线性结构:不是线性结构的数据结构。,16,数据结构与算法,线性表及其顺序存储结构1、线性表线性
9、表是由 n(n0)个元素组成的有限序列:(a1,a2,ai,an)有且只有一个根结点,它无直接前驱。有且只有一个终端结点,它无直接后继。除根结点和终端结点外,其他所有结点都有且只有一个直接前驱和直接后继。结点个数n称为线性表的长度。n=0时,称为空表。2、线性表的顺序存储顺序存储也称为顺序分配线性表中所有元素所占的存储空间是连续的线性表中各元素在存储空间中按照逻辑顺序依次存储3、顺序表的运算线性表的顺序存储结构通常称为顺序表包括:插入、删除、查找、分解、合并、复制、逆转等。在高级语言中,顺序表对应一维数组。顺序表的查找方便,插入和删除较麻烦。,17,数据结构与算法,线性表及其顺序存储结构注意:
10、线性表属于线性结构。线性表的顺序存储结构通常称为顺序表。在顺序表中,所有元素按照其逻辑顺序连续存储,前后件元素紧邻,前件元素一定存储在后件元素的前面。逻辑上相邻的数据元素物理上也相邻 在程序设计语言中,线性表的顺序存储结构对应了一维数组。因为在程序设计语言中,一维数组与计算机中实际的存储空间结构是一致的。在顺序表中,如果要在第 i 个位置插入一个新元素,则原第 i 个元素以及之后的所有元素都要依次后移一个位置。在平均情况下,在顺序表中插入一个新元素,需要移动 n/2 个元素。在顺序表中,如果要删除第 i 个位置的元素,则原第 i 个元素之后的所有元素都要依次前移一个位置。在平均情况下,在顺序表
11、中删除一个元素,需要移动 n/2 个元素。,18,数据结构与算法,栈及其基本运算1、栈栈(stack)是限定在一端进行插入和删除的线性表允许进行插入或删除的一端称为栈顶。不允许进行插入或删除的另一端称为栈底。其特点为“先入后出”(FILO)或“后入先出”(LIFO)。(记忆作用)通常设置指针top指向栈顶,指针bottom指向栈底。2、栈的顺序存储结构栈的各个数据元素按其逻辑顺序依次连续存储。由于插入删除操作只能在栈顶一端进行,所以不需要移动数据元素。3、栈的基本运算入栈:在栈顶位置插入新元素。出栈:取出栈顶位置的元素。读栈顶元素:读出栈顶位置的元素。“上溢”:入栈时堆栈已满。“下溢”:出栈时
12、堆栈已空。,19,数据结构与算法,队列及其基本运算1、队列队列(queue)是限定在一端进行插入另一端进行删除的线性表允许进行插入的一端称为队尾。允许进行删除的另一端称为队头。其特点为“先入先出”(FIFO)或“后入后出”(LILO)。(先来先服务)通常设置指针rear指向队尾,指针front指向队头。2、队列的顺序存储结构队列的各个数据元素按其逻辑顺序依次连续存储。由于插入删除操作只能在队列的两端进行,所以不需要移动数据元素。3、队列的基本运算在实际应用中常常使用循环队列。入队:在队尾位置插入新元素。出队:取出队头位置的元素。“上溢”:入队时队列已满。“下溢”:出队时队列已空。,20,数据结
13、构与算法,线性链表1、链式存储方式 结点由两部分组成:数据域(存储数据)、指针域(指向其前件或后件)。数据结构的存储空间可以不连续,存储顺序与逻辑关系可以不一致。链式存储方式既可以用来表示线性结构,也可以表示非线性结构。2、线性链表线性表的链式存储结构称为线性链表。(栈的链式存储结构称为链栈、队列的链式存储结构称为链队列)常用的线性链表有:单链表(一个指针域,指向直接后继)双向链表(两个指针域,指向直接后继及后继)循环链表(所有结点的指针构成循环链)3、线性链表的基本运算查找:在线性链表中查找指定元素。插入:在线性链表中插入新结点。删除:在线性链表中删除指定结点。,21,单链表(Singly
14、Linked List),每个元素(表项)由结点(Node)构成。逻辑上相邻的元素物理上不需要相邻;不可随机存取,顺序存取;插入、删除时不需要移动大量元素,表头指针,22,(插入前)(插入后),链表插入 newnodenext=pnext;pnext=newnode;,newnode,p,newnode,p,23,链表删除 pnext=q next,24,数据结构与算法,树的基本概念1、树树是一种简单的非线性结构。元素间的关系具有明显的层次结构。2、相关的术语根结点叶节点父结点子结点子树结点的度树的度树的深度,25,数据结构与算法,二叉树1、二叉树的特点非空二叉树只有一个根结点。每个结点最多有
15、左右两棵子树。2、二叉树的基本性质第 k 层上最多有 2 k-1个结点深度为 m 的二叉树最多有 2m-1个结点任何二叉树叶结点总比度为 2 的节点多一个n 个节点的二叉树的深度为 log2n+13、满二叉树4、完全二叉树5、二叉树的遍历先序遍历 中序遍历后序遍历ABDEGCFHI DBGEACHFIDGEBHIFCA,26,数据结构与算法,查找技术1、顺序查找从线性表的第一个元素开始,依次与指定数据比较,若相等则查找成功,若比较的所有元素都不相等,则查找失败。最坏情况的比较次数为表长n,平均情况为n/2。无序顺序表的查找只能采用顺序查找的方法。线性表在链式存储时也只能采用顺序查找的方法。2、
16、二分法查找在顺序存储的线性表为有序的情况下,可以使用二分法查找。方法为:将待查数据与线性表的中间项比较:若相等,则查找成功;若小于,则在线性表的前半部分进行二分法查找;若大于,则在线性表的后半部分进行二分法查找;反复进行直到相等(查找成功)或子表长度为0(查找失败)。,27,数据结构与算法,排序技术1、交换类排序起泡排序最坏情况下的比较次数为 n(n-1)/2。快速排序最坏情况下的比较次数为 n(n-1)/2。2、插入类排序简单插入排序最坏情况下的比较次数为 n(n-1)/2。希尔排序最坏情况下的比较次数为 O(n 1.5)。3、选择类排序简单选择排序最坏情况下的比较次数为 n(n-1)/2。
17、堆排序最坏情况下的比较次数为 O(n log2n)。,28,数据结构与算法,本章重点1、算法是问题处理方案正确而完整的描述,算法的效率与数据的存储结构有密切的关系。2、数据的逻辑结构在计算机中的表示(存储方式)称为数据的存储结构(物理结构)。一种逻辑结构可以有多种存储结构。3、在长度为 n 的顺序表中,插入或删除一个元素平均需要移动一半元素。4、栈是特殊的线性表,具有记忆作用。特点是“先进后出(后进先出)”。栈顶指针动态反映了栈中元素的变化情况。5、队列是特殊的线性表。特点是“先进先出(后进后出)”。队头和队尾指针动态地反映了队列中元素的变化情况。6、线性链表是线性表的链式存储结构。在线性链表
18、中,各元素节点的存储空间可以不连续,存储顺序也可以与逻辑顺序不一致。线性链表的插入删除操作不需要移动数据元素。7、二叉树是一种非线性结构。主要性质有:第k层上最多有 2 k-1 个结点深度为 m 时,最多有2 m 1 个结点度为0的结点比度为2的多一个深度至少为 log2n+1,29,数据结构与算法,本章重点8、满二叉树是二叉树的特殊形态,满二叉树的各层结点都达到最大值,叶结点只出现在最后一层。9、完全二叉树是二叉树的特殊形态,完全二叉树除最后一层外,各层结点都达到最大值,叶结点只出现在最后两层。满二叉树属于完全二叉树。10、根据扫描根结点的顺序,按照先左后右的原则,遍历二叉树有三种方法:前序
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 公共基础知识 公共 基础知识
链接地址:https://www.desk33.com/p-263690.html