计算机2级C公共基础知识.ppt
《计算机2级C公共基础知识.ppt》由会员分享,可在线阅读,更多相关《计算机2级C公共基础知识.ppt(268页珍藏版)》请在三一办公上搜索。
1、计算机等级考试公共基础知识,温俊香,第2页,计算机二级考试公共基础知识大纲,数据结构与算法 程序设计基础 软件工程基础 数据库设计基础,这四个方面在试卷中出现的情况是:选择题10个(20分),填空题5个(10分),总分值占到了试卷卷面分的30,是一个不小的比例。,第3页,计算机二级考试公共基础知识试卷分析,第4页,算法 算法的基本概念 2.算法复杂度的概念和意义,一、基本数据结构与算法,数据结构 数据结构的概念 线性表 栈和队列 树与二叉树 查找技术 排序技术,对于等级考试,这个部分的考核重点主要在算法和数据结构的基本概念、二叉树(遍历、结点),还有排序和查找考试中也经常会涉及到。,第5页,算
2、法的定义对解题方案准确而完整的描述称为算法。,算法是程序设计的核心,算法的基本概念,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计算机解题的过程(计算的方法)。在这个过程中,无论是形成解题思路(推理实现的算法)还是编写程序(操作实现的算法),都是在实施某种算法。,例:n个数从大到小进行排序。有多种排序方法,常用的有冒泡排序、选择排序等。,算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。,讲课说课,第6页,2.算法的基本特征一个算法应该具有以下五个重要的特征:,有穷性 确定性 输入 输出 可行性,拥有足够的情报,第7页,算法与计算机程序 算法_是一组
3、逻辑步骤 程序用计算机语言描述的算法,3.算法的表示,INPUT rS=3.14*r*rPTINT S,问题:输入园的半径,计算园的面积,一个算法的表示需要使用一些语言形式。传统的算法-图形法,如“流程图”和N-S图目前常用的方法-使用伪码描述算法。,第8页,冒泡排序的方法:1.扫描整个线性表,逐次对相邻的两个元素进行比较,若为逆序,则交换;第一趟扫描的结果使最大的元素排到表的最后;2.除最后一个元素,对剩余的元素重复上述过程,将次大的数排到表的倒数第二个位置;3.重复上述过程;对于长度为n的线性表,冒泡排序需要对表扫描n-1遍。,算法举例:n个数排序,第9页,4.算法的两个基本要素:,基本运
4、算和操作 算术运算 关系运算 逻辑运算 数据传输,控制结构 顺序 选择 循环,一是对数据对象的运算和操作;二是算法的控制结构。,算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法,第10页,5.算法的复杂度 评价一个算法优劣的主要标准是算法的执行效率和存储需求:时间复杂度:执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量 空间复杂度:执行这个算法所需要的内存空间 算法在执行过程中临时占用的存储空间 时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积。一个算法在计算机存储器上所占用的存储空间,包括
5、存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分,第11页,(1)在计算机中,算法是指_。A.查询方法 B.加工方法 C.解题方案的准确而完整的描述 D.排序方法(2)下列叙述中正确的是(07年4月)A)算法的效率只与问题的规模有关,而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需要的计算工作量C)数据的逻辑结构与存储结构是一一对应的D)算法的时间复杂度与空间复杂度一定相关(3)算法的有穷性是指(08年4月)A)算法程序的运行时间是有限的 B)算法程序所处理的数据量是有限的 C)算法程序的长度是有限的 D)算法只能被有限
6、的用户使用,(c),(B),算法习题:,(A),第12页,(4)算法的时问复杂度是指(2010年3月)A)算法的执行时间B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的基本运算次数(5)算法的空间复杂度是指(09年9月)A)算法在执行过程中所需要的计算机存储空间B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的临时工作单元数(6)下列叙述中正确的是(06年9月)A)一个算法的空间复杂度大,则其时间复杂度也必定大B)一个算法的空间复杂度大,则其时间复杂度必定小C)一个算法的时间复杂度大,则其空间复杂度必定小 D)上述三种说法都不对,(
7、D)计算工作量,(A),(D),算法的时间复杂度是指A)执行算法程序所需要的时间 B)算法程序的长度C)算法执行过程中所需要的基本运算次数 D)算法程序中的指令条数算法的基本特征是可行性、确定性、【1】和拥有足够的情报。算法的空间复杂度是指 A)算法程序的长度 B)算法程序中的指令条数 C)算法程序所占的存储空间 D)执行过程中所需要的存储空间在计算机中,算法是指 A)加工方法B)解题方案的准确而完整的描述 C)排序方法D)查询方法,例题讲解,有穷性,算法分析的目的是 A)找出数据结构的合理性 B)找出算法中输入和输出之间的关系 C)分析算法的易懂性和可靠性 D)分析算法的效率以求改进算法的工
8、作量大小和实现算法所需的存储单元多少分别称为算法的【1】。,时间复杂度和空间复杂度,第15页,计算机在进行数据处理时,实际需要处理的数据元素一般有很多,而这些大量的数据元素都需要存放在计算机中,因此,大量的数据元素在计算机中如何组织,以便提高数据处理的效率,并且节省计算机的存储空间,这是进行数据处理的关键问题。,二、数据结构,程序=算法+数据结构,数据结构是指相互有关联的数据元素的集合。一般来说,人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素,对于具有不同特征的数据元素总是分别进行处理。一般情况下,在具有相同特征的数据元素集合中,各个数据元素之间存在有某种关系(即联系),这种
9、关系反映了该集合中的数据元素所固有的一种结构。,超市的物品如何存放才好找且节省空间呢?,第16页,二.数据结构,数据结构是指相互有关联的数据元素的集合。数据结构是研究数据和数据之间关系的一门学科,它包括三个方面。(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;(3)对各种数据结构进行的运算。,第17页,1.逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含:(1)表示数据元素的信息;(2)表示各数据元素之间的前后件关系。例:1.一年四季的数据结构 B=(D,R)D=春,
10、夏,秋,冬 R=(春,夏),(夏,秋),(秋,冬)2.家庭成员的数据结构 B=(D,R)D=父亲,儿子,女儿 R=(父亲,儿子),(父亲,女儿),春,夏,秋,冬,数据结构的图形表示,第18页,常见的逻辑结构有:线性结构、树形结构和图形结构。,线性结构 结构中的每个元素之间存在一个对一个的关系;树形结构 结构中的每个元素之间存在一个对多个的关系;图形结构或网状结构 结构中的每个元素之间存在多个对多个的关系。其中,树形结构和图形结构统称为非线形结构。数据的逻辑结构可以用二元关系表示,也可以直观地用图形来表示。,第19页,2.存储结构(物理结构)计算机在实际进行数据处理时,被处理的各数据元素总是被存
11、放在计算机的存储空间中,并且,各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的,而且一般也不可能相同。如:一年四季 家庭成员 计算机存储空间怎样存放?存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有:顺序存储结构 链式存储结构 索引存储结构,只抽象地反映数据元素之间的关系的结构,而不管其存储方式的数据结构称为逻辑结构。一种数据结构可以根据需要表示成一种或多种存储结构。,第20页,3.数据的运算 检索 插入 删除 更新 排序,通常,一个数据结构中的元素结点可能是动态变化的。根据需要或在处理过程中,可以在一个数据结构中增加一个新结点(插入运算),也可以删除某个结点(
12、删除运算),除此之外,对数据结构的运算还有查找、分类、合并、分解、复制和修改。在对数据结构的处理过程中,不仅数据结构中结点的个数在动态变化,而且,各数据元素之间的关系也有可能在动态地变化。如:无序表变有序表,数据结构是研究数据和数据之间关系的一门学科,研究以下三方面内容:数据的逻辑结构 数据的存储结构 数据的运算,第21|92页,常见的数据结构,数据结构分类 线性结构与非线性结构两大类型,线性结构:一个非空的数据结构若满足下面的两个条件,则这种数据结构即为线性结构。有且仅有一个根结点;除第一个结点外,每一个结点最多有一个前件;除最后一个结点外,每一个结点最多有一个后件。,常见的线性结构有:线性
13、表、栈、队列、线性链表等,第22|92页,常见的非线性结构有树、二叉树、图等,非线性结构:一个数据结构不是线性结构。,第23页,线性表(Linear List),线性表是由n(n0)个数据元素 a1,a2,ai,an组成的一个有限序列。,简单的线性表,复杂的线性表,记录1 02011001 张三 男,记录2 02011003 李四 女,记录3,记录4,第24页,线性表的顺序存储结构,特点:顺序存储结构把逻辑上相邻的数据元素存储在物理上相邻的存储单元里,顺序存储结构只存储结点的值,不存储结点间的关系,结点间的关系由存储单元的邻接关系来体现。,存储地址,2000,2004,2000+4*(i-1)
14、,2000+4*(n-1),占4个字节,Loa(ai)=Loa(a1)+L*(i-1),第i个数的地址,第一个数的地址,L为该类型数所占的字节,线性表的存储结构,线性表的存储结构有两种:顺序存储结构 链式存储结构,第25页,顺序表的插入运算 顺序表的删除运算,顺序表的插入和删除运算,在线性表顺序存储情况下,要插入或删除一个元素,都会由于数据元素的移动而消耗大量的处理时间,所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。,线性表的顺序存储结构称为顺序表。,第26页,插入运算,插入算法的分析:假设线性表中含有n个数据元素,在进行插入操作时,若假定在n+1个位置上插入元素的可能
15、性均等,则平均移动元素的个数为:,第27页,删除运算,删除算法的分析:在进行删除操作时,若假定删除每个元素的可能性均等,则平均移动元素的个数为:,总结:顺序存储结构表示的线性表,在做插入或删除操作时,平均需要移动大约一半的数据元素。当线性表的数据元素量较大,并且经常要对其做插入或删除操作时,这一点需要值得考虑。,第28页,线性表的链式存储结构,线性表的链式存储结构称为线性链表。链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻,而且各数据元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。链式存储结构的每一个存储结点不仅存储结点的值,而且存储结点之间的关系:链式存储结构分为
16、单链表、双向链表、循环链表线性链表不能随机存取,第29页,设线性表为(a1,a2,a3,a4,a5),HEAD,3,线性链表的物理状态,线性表的顺序存储结构,注意:1 2 3 此类编号不代表所在的地址单元的地址编码,线性表的链式存储结构及其插入与删除操作,第30页,单链表,第31页,单链表的插入运算,在P所指向的结点之后插入新的结点,单链表删除运算,要求:删除结点ai。,第32页,循环链表:首尾相接的链表。将最后一个结点的空指针改为指向头结点,从任一结点出发均可找到其它结点。,L,.,带头结点的单链表,L,.,循环单链表,特点:可以从任何一个结点开始访问链表的所有结点.,第33页,双向链表的存
17、储结构 在每个结点中设置两个指针,一个指向后继,一个指向前驱。可直接确定一个结点的前驱和后继结点。可提高效率。,提问:单向链表的缺点是什么?提示:如何寻找结点的直接前趋。双向链表可以克服单链表的单向性的缺点。在双向链表的结点中有两个指针域,其一指向直接后继,另一指向直接前趋。,双向循环链表,第34页,线性表的应用:应用最广的数据结构。.高级语言中的数组;计算机的文件系统;计算机的目录系统;电话号码查询系统(可采用顺序表或单链表结构);各种事务处理(可采用顺序表或单链表结构);,第35页,2.栈和队列,栈和队列是两种特殊的线性表,它们是运算时要受到某些限制的线性表,故也称为限定性的数据结构。栈(
18、Stack)及其基本运算 队列(Queue)及其基本运算 循环队列及其基本运算,第36页,1.栈,栈是限定仅在表尾进行插入或删除操作的线性表。栈顶表尾。栈底表头。空栈不含元素的空表。,进栈,出栈,栈s=(a1,a2,an),后进先出或先进后出(LIFO),第37页,栈的物理存储结构可以用顺序结构,也可以用链表结构。下面讨论顺序存储结构中栈元素的插入和删除运算。顺序栈的进栈和出栈运算 栈的基本运算有三种:入栈、退栈和读栈顶元素,在顺序栈中插入和删除运算不需要移动表中其他数据元素。,第38页,2.栈的顺序存储结构及其基本运算,用顺序存储结构表示的栈:顺序栈用一组连续的存储单元存放自栈底到栈顶的数据
19、元素,一般用一维数组表示,设置一个简单变量top指示栈顶位置,称为针栈顶指,它始终指向待插入元素的位置。,基本运算:压(进)栈:PUSH出栈:POP读栈顶元素:gettop,第39页,例子:,空桟:topbase非空桟:top始终在桟顶元素的后一个位置,桟的元素个数:,top-base,上溢,下溢,第40页,2、队列定义:一种特殊的线性结构,限定只能在表的一端进行插入,在 表的另一端进行删除的线性表。此种结构称为先进先出(FIFO)表。,先进先出后进后出(LIFO),第41页,队列的顺序存储结构及其基本运算,空队列:非空队列:队列元素个数:,rear=front=-1,front始终指向队头元
20、素前一个位置,而rear始终指向队尾元素的位置,rear-front,第42页,队列的物理存储结构可以用顺序结构,也可以用链式结构。顺序队列的运算,栈有三种操作:入栈出栈读栈顶元素队列有三种操作:入队出队读队首元素,例:有入栈元素序列:ABCD,求可能的出栈序列如是队列又是什么情况呢?,第43页,循环队列 把队列的存储空间在逻辑上看作一个环,当R指向存储空间的末端后,就把它重新置于始端。循环队列的运算,进行删除的一端称做队首(front)。队列中进行插入的一端称做队尾(rear),习题:数据结构分为逻辑结构和存储结构,循环队列属于【】结构。(2005年9月),答案:存储结构。,第44页,第45
21、页,上溢,下溢,front=rear队满,front=rear队空,第46页,数据存储结构方面的考题,1:数据的存储结构是指(2005年4月)A)存储在外存中的数据 B)数据所占的存储空间量C)数据在计算机中的顺序存储方式 D)数据的逻辑结构在计算机中的表示2.下列叙述中正确的是(2009年3月)A)栈是“先进先出”的线性表 B)队列是“先进后出”的线性表 C)循环队列是非线性结构 D)有序线性表既可以采用顺序存储结构,也可以采用链式存储结构 3.数据结构分为线性结构和非线性结构,带链的队列属于。4.下列数据结构中,属于非线性结构的是A)循环队列 B)带链队列C)二叉树 D)带链栈,答案:D。
22、,答案:D。,答案:线性结构。,答案:c,第47页,5。下列叙述中正确的是()。(2008年9月)A)顺序存储结构的存储一定是连续的,链式存储结构的存储空间不一定是连续的 B)顺序存储结构只针对线性结构,链式存储结构只针对非线性结构 C)顺序存储结构能存储有序表,链式存储结构不能存储有序表 D)链式存储结构比顺序存储结构节省存储空间,答案:A。,6。下列关于栈的叙述正确的是(2008年4月)A)栈按“先进先出”组织数据 B)栈按“先进后出”组织数据 C)只能在栈底插入数据 D)不能删除数据,答案:B。,7.一个队列的初始状态为空。现将元素A,B,C,D,E,F,5,4,3,2,1依次入队,然后
23、再依次退队,则元素退队的顺序为【1】。(2010年3月),答案:A,B,C,D,E,F,5,4,3,2,1,第48页,9.设某循环队列的容量为50,如果头指针front=45(指向队头元素的前一位置),尾指针rear=10(指向队尾元素),则该循环队列中共有【2】个元素。(2010年3月),8。假设用一个长度为50的数组(数组元索的下标从0到49)作为栈的存储空间,栈底指针bottom指间栈底元素,栈顶指针top指向栈顶元素,如果bottom=49,top=30(数组下标),则栈中具有【】个元素。(2009年3月),答案:19,答案:15,4650110,链表不具有的特点是A)不必事先估计存储
24、空间 B)可随机访问任一元素C)插入删除不需要移动元素D)所需空间与线性表长度成正比数据结构分为逻辑结构与存储结构,线性链表属于【1】。数据结构中,与所使用的计算机无关的是数据的 A)存储结构B)物理结构 C)逻辑结构D)物理和存储结构 数据的逻辑结构有线性结构和【1】两大类。数据的存储结构是指A)数据所占的存储空间B)数据的逻辑结构在计算机中的表示C)数据在计算机中的顺序存储方式D)存储在外存中的数据,例题讲解,存储结构,非线性结构,顺序存储方法是把逻辑上相邻的结点存储在物理位置【2】的存储单元中。数据处理的最小单位是 A)数据 B)数据元素 C)数据项D)数据结构数据结构作为计算机的一门学
25、科,主要研究数据的逻辑结构、对各种数据结构进行的运算,以及 A)数据的存储结构 B)计算方法 C)数据映象 D)逻辑存储线性表的顺序存储结构和线性表的链式存储结构分别是 A)顺序存取的存储结构、顺序存取的存储结构 B)随机存取的存储结构、顺序存取的存储结构 C)随机存取的存储结构、随机存取的存储结构 D)任意存取的存储结构、任意存取的存储结构,相邻,根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分成 A)动态结构和静态结构 B)紧凑结构和非紧凑结构 C)线性结构和非线性结构 D)内部结构和外部结构 数据结构包括数据的逻辑结构、数据的【2】以及对数据的操作运算。数据的基本单位是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 公共 基础知识
链接地址:https://www.31ppt.com/p-6201583.html