二级C公共基础知识完整版.ppt
《二级C公共基础知识完整版.ppt》由会员分享,可在线阅读,更多相关《二级C公共基础知识完整版.ppt(199页珍藏版)》请在课桌文档上搜索。
1、1,一、涉及面广,但难度小,你应该知道,公共基础知识考题特点及复习建议,计算机等级二级理论考试中有关公共知识部分的题目共有15道,涉及算法及数据结构、程序设计基础、软件工程基础和数据库设计基础等四门课程,尽管知识面大,但是从整体上分析,考核的内容难度不大,考点也相对集中些。,2,二、考核重点为基本概念、基本方法 和基本运算,你应该知道,计算机等级二级理论考试中涉及的题目都是基本概念、基本方法和基本运算,考核以概念和认识性内容为主,理解性、应用性内容偏少。,3,三、考核重点是数据结构和算法,你应该知道,以下是对以往二级理论考试的大概统计:,算法及数据结构:34%程序设计基础:9%软件工程基础:2
2、5%数据库设计基础:29%,4,四、几点复习及应试建议,复习的关键是考生必须准确判断和掌握常见考点 公共基础知识部分的知识点多、杂,考生在学习过程中应理 清其中的脉络关系(即框架提纲),才能有效地组织和记住 各知识点考生一开始学习时不要太追求灵活掌握该部分的内容,经历一个“先熟记,再练习、熟能生巧”的过程,这是多数考生常用的一个方法。多做习题,强化知识点学习。,5,1、了解算法的基本概念和一些常用的算法,学会计算算法的时间复杂度;,2、掌握数据结构的基本概念,并了解数据的逻辑结构和存储结构,学会利 用图形的方式表示数据结构;,算法与数据结构:,3、了解线性表的基本概念,并掌握线性表的顺序存储结
3、构以及顺序存储的 线性表的基本运算;,4、了解栈和队列的基本概念,并掌握它们的基本运算;,5、了解线性链表的基本概念,并掌握线性链表的基本运算,同时,了解循 环链表的基本概念和基本操作;,6、理解树的概念,尤其是二叉树的基本概念和相关性质,掌握二叉树的存 储结构和遍历技术;,7、掌握查找技术,学会利用顺序查找和二分查找在数列中查找指定的数据;,8、学会利用相关的排序技术实现无序数列的排序操作。,6,1、了解软件工程的基本概念;,2、了解软件工程过程与软件的生命周期,以及软件工程的目标和原则;,软件工程:,3、了解利用结构化分析法进行软件工程中的需求分析的方法,并了解需 求分析的方法和需要完成的
4、任务;,4、了解数据流图的使用方法;,5、了解如何利用结构化设计方法进行软件设计,并了解软件设计的一些 常用工具;,6、了解软件测试的目的和方法,以及软件测试的准则,了解常用的软件 测试方法的区别和各自的功能与特点;,7、了解程序调试的方法和原则。,7,1、了解程序设计的方法,以及程序设计风格确立的一些因素,掌握程序 设计的基本规则;,2、了解结构化程序设计的基本原则,掌握结构化程序设计的基本结构与特点;,程序设计基础:,3、了解面向对象的程序设计方法,并理解面向对象方法的一些基本概念。,数据库系统:,1、了解数据库系统的基本概念,以及数据库系统的发展;,2、了解数据模型的基本概念,并对E-R
5、模型、层次模型、网状模型和关系模型 进行了解,并掌握关系模型的数据结构、关系的操作和数据约束等知识;,3、了解关系模型的基本操作,掌握关系模型的基本运算及扩充运算;,4、了解数据库的设计与管理,掌握数据库设计的几个阶段的方法和特点。,8,一、算法(algorithm),1、算法的基本概念(汉诺塔的例子),算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。它是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明确的,此顺序将在有限的次数下终止。算法具有可行性、确定性、有穷性、输入和输出(拥有足够的情报)等个重要特性。,汉 诺 塔,1-B 2-C
6、1-C 3-B 1-A 2-B 1-B,A,B,C,1,2,3,算法:,算法:对特定问题求解步骤的一种描述。,算法的描述方法:自然语言、专用工具或某种计算机语言。,返回,10,2、算法的基本要素,(1)对数据对象的运算和操作:算术运算、逻辑运算、关系运算、数据传输,算法中各操作之间的执行顺序;描述算法的工具通常有传统流程图、N-S结构化流程 图、算法描述语言等;一个算法一般可以用顺序、选择、循环三种基本结构 组合而成。,(2)算法的控制结构:,11,3、算法设计的基本方法及例子,列举法(列出所有可能,再逐一检验,得到符合条件的结果)百钱买百鸡 归纳法(通过特殊情况,经过分析,最后找出一般关系)
7、递推(从已知的初始条件出发,逐步推算,得到结果)猴子分食桃子 递归(将问题逐层分解,最后归结为一些最简单的问题)求年龄问题 减半递推(重复将问题的规模减半,而问题性质不变)二分法求方程实根 回溯法(以最优方式向前试探,如果失败,则后退再选)八皇后问题,12,3、算法的复杂度,(1)时间复杂度,依据算法编制的程序在计算机上运行时所消耗的时间 来度量。通常有事后统计法和事前分析估算法。一个算法是由控制结构(顺序、分支和循环)和原操 作构成的,算法时间取决于两者的综合效果。算法中基本操作重复执行次数n和算法执行时间同步 增长,称作算法的时间复杂度。,13,(2)空间复杂度,一般是指执行这个算法所需要
8、的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及某种数据结构所需 要的附加存储空间。一个上机执行的程序除了需要存储空间来寄存本身所用 指令、常数、变量和输入数据外,也需要一些对数据进 行操作的工作单元和存储一些为实现计算所需信息的辅 助空间。,14,3、例题讲解,算法的时间复杂度是指(C)A、执行算法程序所需要的时间 B、算法程序的长度 C、算法执行过程中所需要的基本运算次数 D、算法程序中的指令条数 算法的基本特征是可行性、确定性、【1】和拥有足够 的情报。【答案】:有穷性 算法的空间复杂度是指(D)A)算法程序的长度 B)算法程序中的指令条数 C
9、)算法程序所占的存储空间 D)执行过程中所需要的存储空间,15,在计算机中,算法是指(B)A)加工方法 B)解题方案的准确而完整的描述 C)排序方法 D)查询方法,算法分析的目的是(D)A)找出数据结构的合理性 B)找出算法中输入和输出之间的关系 C)分析算法的易懂性和可靠性 D)分析算法的效率以求改进 算法的工作量大小和实现算法所需的存储单元多少分别称 为算法的【1】。【答案】:时间复杂度和空间复杂度,16,二、数据结构(Data Structure),1、数据结构研究的主要内容,当今计算机应用的特点:1、所处理的数据量大且具有一定的关系;2、对其操作不再是单纯的数值计算,而更多地是需 要对
10、其进行组织、管理和检索。,对数据的讨论不单单是数据本身,还要包括数据与数据之间的关系。下面各例表示不同的数据采用不同的数据结构来组织。,17,特点:每个学生的信息占据一行,所有学生的信息按学号顺序依次排列构成一张表格;表中每个学生的信息依据学号的大小存在着一种前后关系,这就是我们所说的线性结构;对它的操作通常是插入某个学生的信息,删除某个学生的信息,更新某个学生的信息,按条件检索某个学生的信息等等。,应用举例1学籍档案管理假设一个学籍档案管理系统应包含如下表所示的学生信息。,18,应用举例2家庭血缘关系图 表示家庭成员的辈分关系,使用下图1-1所示的形式描述。,图 1-1 家庭血缘关系图,特点
11、:在求解过程中,所处理的数据之间具有层次关系,这是我们 所说的树形结构;对它的操作有:建立树形结构,输出最结点内容等等。,应用举例3制定教学计划 在制定教学计划时,需要考虑各门课程的开设顺序。有些课程需要先导课程,有些课程则不需要,而有些课程又是其他课程的先导课程。比如,计算机专业课程的开设情况如下表所示:,19,这种数据可以用下面的图来表示:,课程先后关系的图形描形式:,图 1-2 计算机专业必修课程开设先后关系,20,数据结构的主要研究问题:,21,2、基本概念和术语,数据结构是一门研究数据组织、存储和运算的一般方法的学科。,例:整数(1,2)、实数(1.1,1.2)字符串(Beijing
12、)、图形、声音。,计算机管理图书问题:在图书馆里有各种卡片:有按书名编排的、有按作者编排的、有按分类编排。如何将查询图书的这些信息存入计算机中既要考虑查询时间短,又要考虑节省空间。最简单的办法之一是建立一张表,每一本书的信息在表中占一行,如:,22,数据元素在计算机中的表示,数据结构是一门研究数据组织、存储和运算的一般方法的学科。,如何将0,1,2,3,4,5,6,7,8,9这10个数存放在计算机中能最快地达到你所需要的目的?目的不同,最佳的存储方方法就不同。从大到小排列:9,8,7,6,5,4,3,2,1,0输出偶数:0,2,4,6,8,1,3,5,7,9,对数据结构中的节点进行操作处理(插
13、入、删除、修改、查找、排序),23,数据元素(Data Element),数据元素是数据的基本单位,即数据集合中的个体。有时一个数据元素可由若干数据项(Data Item)组成。数据项是数据的最小单位。,数据元素亦称节点或记录。,数据结构可描述为 Group=(D,R),有限个数据元素的集合,有限个节点间关系的集合,24,25,数据结构可描述为 Group=(D,R),例1:一年四季的数据结构可表示成B=(D,R)D=春,夏,秋,冬 R=(春,夏),(夏,秋),(秋,冬)例2:家庭成员数据结构可表示成B=(D,R)D=父亲,儿子,女儿 R=(父亲,儿子),(父亲,女儿),26,数据结构也可用图
14、形表示,一年四季的数据结构可表示成家庭成员数据结构可表示成,(概念:结点、前件、后件、根结点、叶子),27,树形结构,全校学生档案管理的组织方式,计算机程序管理系统也是典型的树形结构。,28,D=1,2,3,4R=(1,2),(1,3),(1,4),(2,3),(3,4),(2,4),D=1,2,3 R=(1,2),(2,3),(3,2),(1,3),图形结构节点间的连结是任意的,29,3、例题讲解,数据处理的最小单位是(C)A)数据 B)数据元素 C)数据项 D)数据结构数据结构作为计算机的一门学科,主要研究数据的逻辑结构、对各种数据结构进行的运算,以及(A)A)数据的存储结构 B)计算方法
15、 C)数据映象 D)逻辑存储数据结构包括数据的逻辑结构、数据的【4】以及对数据的操作运算。【答案】物理结构(或存储结构),30,线性结构与非线性结构:线性结构:有且只有一个根结点;每一个结点最多有一个前件,也最多有一个后件。如:一年四季,26个英文字母非线性结构:线性以外的数据结构。如:反映家庭成员间辈分关系的数据结构,31,结点间是以线性关系联结,如前面提到的:一年四季26个英文字母 线性 有限 序列,4、线性表(Linear List),线性表:具有线性结构的有限序列。,32,学生成绩表,线性表,33,数据元素、结点、记录,数据项,线性表的定义:线性表是n个元素的有限序列,它们之间的关系可
16、以排成一个线性序列:a1,a2,ai,an 其中n称作表的长度,当n=0时,称作空表。,线性表的特点:1、线性表中所有元素的性质相同。2、除第一个和最后一个数据元素之外,其它数据元素有且 仅有一个前驱和一个后继。第一个数据元素无前驱,最 后一个数据元素无后继。3、数据元素在表中的位置只取决于它自身的序号。在线性表上常用的运算有:初始化、求长度、取元素、修改、前插、删除、检索、排序,34,35,线性表的 顺序存储结构 及其 插入 与 删除 操作,特点:1、线性表中数据元素类型一致,只有数据域,存储空间 利用率高。2、所有元素所占的存储空间是连续的。3、各数据元素在存储空间中是按逻辑顺序依次存放的
17、(a)做插入、删除时需移动大量元素。(b)空间估计不明时,按最大空间分配。,36,顺序存储,存储地址,存储内容,元素n,.,元素i,.,元素2,元素1,Lo,Lo+m,Lo+(i-1)m,Lo+(n-1)m,Loc(元素i)=Lo+(i-1)m,每个元素所占用的存储单元个数,线性表的 顺序存储结构:,首地址起始地址基地址,插入运算,ai-1,.,a2,a1,alength,ai+1,ai,alength,插入算法的分析 假设线性表中含有n个数据元素,在进行插入操作时,若假定在n+1个位置上插入元素的可能性均等,则平均移动元素的个数为:,37,X,ai-1,.,a2,a1,alength,ai+
18、1,ai,X,在进行删除操作时,若假定删除每个元素的可能性均等,则平均移动元素的个数为:分析结论 顺序存储结构表示的线性表,在做插入或删除操作时,平均需要移动大约一半的数据元素。当线性表的数据元素量较大,并且经常要对其做插入或删除操作时,这一点需要值得考虑。,删除算法的分析,38,线性表的例题讲解,顺序存储方法是把逻辑上相邻的结点存储在物理位置【1】的存储单元中。【答案】相邻 长度为n的顺序存储线性表中,当在任何位置上插入一个元 素概率都相等时,插入一个元素所需移动元素的平均个数 为【2】。【答案】n/2 线性表L=(a1,a2,a3,ai,an),下列说法正确的是(D)A)每个元素都有一个直
19、接前件和直接后件 B)线性表中至少要有一个元素 C)表中诸元素的排列顺序必须是由小到大或由大到小 D)除第一个元素和最后一个元素外,其余每个元素都有一 个且只有一个直接前件和直接后件,39,40,数据结构中,与所使用的计算机无关的是数据的(C)A)存储结构B)物理结构 C)逻辑结构D)物理和存储结构 下列叙述中,错误的是(B)A)数据的存储结构与数据处理的效率密切相关 B)数据的存储结构与数据处理的效率无关 C)数据的存储结构在计算机中所占的空间不一定是连续的 D)一种数据的逻辑结构可以有多种存储结构 数据的存储结构是指(B)A)数据所占的存储空间 B)数据的逻辑结构在计算机中的表示 C)数据
20、在计算机中的顺序存储方式 D)存储在外存中的数据,根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分成(C)A)动态结构和静态结构 B)紧凑结构和非紧凑结构 C)线性结构和非线性结构 D)内部结构和外部结构 数据的逻辑结构有线性结构和【2】两大类。非线性结构 当线性表采用顺序存储结构实现存储时,其主要特点是【1】。【答案】逻辑结构中相邻的结点在存储结构中仍相邻。,41,5、堆栈和队列,堆栈和队列的定义,栈和队列是两种特殊的线性表,它们是运算时要受到某些限制的线性表,故也称为限定性的数据结构。,堆栈的定义,堆栈:限定只能在表的一端进行插入和删除的特殊的线性表,此种 结构称为后进先
21、出。设栈s=(a1,a2,ai,an),其中a1是栈底元素,an是栈顶元素。栈顶(top):允许插入和删除的一端;约定top始终指向新数据元素将存放的位置。栈底(bottom):不允许插入和删除的一端。,42,队列的定义,队列:一种特殊的线性结构,限定只能在表的一端进行插入,在表的另一端进行删除的线性表。此种结构称为先进 先出(FIFO)表。,a1,a2,a3,a4,an-1,an,队 列 示 意 图,队头,队尾,队列的主要运算,(1)设置一个空队列;(2)插入一个新的队尾元素,称为进队;(3)删除队头元素,称为出队;(4)读取队头元素;,43,堆栈和队列的例题讲解,栈和队列的共同特点是(C)
22、A)都是先进先出 B)都是先进后出 C)只允许在端点处插入和删除元素 D)没有共同点如果进栈序列为e1,e2,e3,e4,则可能的出栈序列是(B)A)e3,e1,e4,e2 B)e4,e3,e2,e1 C)e3,e4,e1,e2 D)任意顺序,44,45,a=42+b,8,2,6,b=63+c,c=32+d,d=1+2,=8+b,=2+c,=6+d,=3,8,2,6,一些重要的程序语言(如C语言和Pascal语言)允许过程的递归调用。而实现递归调用中的存储分配通常用(A)A)栈B)堆 C)数组 D)链表,当循环队列非空且队尾指针等于队头指针时,说明循环队列已满,不能进行入队运算。这种情况称为【
23、2】。答案:上溢 由两个栈共享一个存储空间的好处是(B)A)减少存取时间,降低下溢发生的机率 B)节省存储空间,降低上溢发生的机率 C)减少存取时间,降低上溢发生的机率 D)节省存储空间,降低下溢发生的机率下列关于栈的叙述中正确的是(D))在栈中只能插入数据 B)在栈中只能删除数据C)栈是先进先出的线性表 D)栈是后进先出的线性表下列关于队列的叙述中正确的是(C)在队列中只能插入数据 B)在队列中只能删除数据C)队列是先进先出的线性表 D)队列是后进先出的线性表,46,两个栈共享只有两个栈都多时才溢出。不共享的话,两个栈只有一个栈多就溢出,,栈底至栈顶依次存放元素A、B、C、D,在第五个元素E
24、 入栈前,栈中元素可以出栈,则出栈序列可能是(B)A)ABCED B)DCBEA C)DBCEA D)CDABE,47,顺序存储结构常用于线性数据结构,将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。,顺序存储结构的三个缺点:1.作插入或删除操作时,需移动大量元数。2.长度变化较大时,需按最大空间分配。3.表的容量难以扩充。,存储内容,48,49,6、线性表的链式存储 线性链表,线性链表的基本概念:线性表的链式存储结构称为线性链表。为了适应线性表的链式存储结构,计算机存储空间被划分为一个一个小块,每一小块占若干字节,通常称这些小块为存储结点。,将存储空间中的每一个存储结点分为两部:一部分称
25、为数据域,用于存储数据元素的值;另一部分称为指针域,用于存放下一个数据元素的存储序号(即存储结点的地址),也就是指向后件结点.,线性链表中存储结点的结构如图2.20所示,50,1536,元素2,1400,元素1,1346,元素3,元素4,head,链式存储,1345,52,指向线性表中第一个结点的指针HEAD称为头指针。当HEAD=NULL(或0)时称为空表。对于线性链表,可以从头指针开始,沿着各个结点的指针扫描到链表中的所有结点。,线性链表的逻辑结构图所示,53,1、比顺序存储结构的存储密度小(每个节点都由数据域和指针域组成,所以相同空间内假设全存满的话顺序比链式存储更多)。2、逻辑上相邻的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二级 公共 基础知识 完整版
链接地址:https://www.desk33.com/p-264259.html