全国计算机二级公共基础知识要点.ppt
《全国计算机二级公共基础知识要点.ppt》由会员分享,可在线阅读,更多相关《全国计算机二级公共基础知识要点.ppt(135页珍藏版)》请在三一办公上搜索。
1、全国计算机等级考试 二级公共基础知识主讲人:韩静2023年6月16日星期五,基本要求,1.掌握算法的基本概念。2.掌握基本数据结构及其操作。3.掌握基本排序和查找算法。4.掌握逐步求精的结构化程序设计方法。5.掌握软件工程的基本方法,具有初步应用相关技术进行软件开发的能力。6.掌握数据库的基本知识,了解关系数据库的设计。,一、基本数据结构与算法,1.算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复杂度)。2.数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。3.线性表的定义;线性表的顺序存储结构及其插入与删除运算。4.栈和队列的定义;栈和队列的
2、顺序存储结构及其基本运算。5.线性单链表、双向链表与循环链表的结构及其基本运算。6.树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法;基本排序算法(交换类排序,选择类排序,插入类排序)。,二、程序设计基础,1.程序设计方法与风格。2.结构化程序设计。3.面向对象的程序设计方法,对象,方法,属性及继承与多态性。,三、软件工程基础,1.软件工程基本概念,软件生命周期概念,软件工具与软件开发环境。2.结构化分析方法,数据流图,数据字典,软件需求规格说明书。3.结构化设计方法,总体设计与详细设计。4.软件测试的方法,白盒测试与黑盒测试,测试用例设计,软
3、件测试的实施,单元测试、集成测试和系统测试。5.程序的调试,静态调试与动态调试。,四、数据库设计基础,1.数据库的基本概念:数据库,数据库管理系统,数据库系统。2.数据模型,实体联系模型及E-R图,从E-R图导出关系数据模型。3.关系代数运算,包括集合运算及选择、投影、连接运算,数据库规范化理论。4.数据库设计方法和步骤:需求分析、概念设计、逻辑设计和物理设计的相关策略。,考试方式,1、公共基础的考试方式为笔试,与C语言(VisualBASIC、Visual FoxPro、Java、Access、Visual C+)的笔试部分合为一张试卷。公共基础部分占全卷的30分。2、公共基础知识有10道选
4、择题和5道填空题。,学习方法,理解基本概念多做练习适当记忆一些名词与所学的VFPcAccess程序设计知识结合起来,以增加对知识的理解能力,9,1.基本数据结构与算法,10,算法的基本特征:(1)可行性(2)确定性(3)有穷性(4)输入和输出(拥有足够的情报),1.1 算法,11,1.2 算法复杂度,1.2.1 时间复杂度是指执行算法所需要的计算工作量。通常有事后统计法和事前分析估算法。算法在执行过程中所需基本运算的执行次数来度量算法的工作量.算法所执行的基本运算次数与问题的规模n有关.,执行算法所需要的计算工作量和f(n)同步增长,记为:,算法的工作量=f(n),时间复杂度=O(f(n),1
5、2,1.2.2 算法的空间复杂度 一般是指执行这个算法所需要的内存空间一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及某种数据结构所需要的附加存储空间 一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外,也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。,13,算法的时间复杂度是指A)执行算法程序所需要的时间 B)算法程序的长度C)算法执行过程中所需要的基本运算次数 D)算法程序中的指令条数算法的基本特征是可行性、确定性、【1】和拥有足够的情报。算法的空间复杂度是指 A)算法程序的长度 B)算法程序中的指令条数
6、C)算法程序所占的存储空间 D)执行过程中所需要的存储空间在计算机中,算法是指 A)加工方法B)解题方案的准确而完整的描述 C)排序方法D)查询方法,例题讲解,有穷性,14,算法分析的目的是 A)找出数据结构的合理性 B)找出算法中输入和输出之间的关系 C)分析算法的易懂性和可靠性 D)分析算法的效率以求改进算法的工作量大小和实现算法所需的存储单元多少分别称为算法的【1】。,时间复杂度和空间复杂度,15,1.2 数据结构,数据结构的定义数据的逻辑结构和存储结构数据结构的图形表示线性结构与非线性结构,16,1.2.1 数据结构研究的主要内容,(1)数据集中数据之间的逻辑关系,(2)数据的存储结构
7、,(3)各种数据结构的运算,17,(1)数据元素(Data Element),数据元素是数据的基本单位,即数据集合中的个体。有时一个数据元数可由若干数据项(Data Item)组成。数据项是数据的最小单位。,数据元素亦称节点或记录。,18,19,A.线性结构,(A,B,C,,X,Y,Z),例:学生成绩表,线性表,栈后进先出队列先进先出,例:英文字母表,20,树形结构,例:全校学生档案管理的组织方式,例:计算机文件管理系统也是典型的树形结构,B非线性结构,21,例:数据结构B(D,R)D=1,2,3,4 R=(1,2),(1,3),(1,4),(2,3),(3,4),(2,4),例:数据结构C(
8、D,R)D=1,2,3 R=,图形结构,22,Loc(ai)=Lo+(i-1)*m,1、顺序存储,每个元素所占用的存储单元个数,(3)存储结构,23,例:线性表(zhao,qian,sun,li,zhou,wu,zheng,wang),顺序存储结构:,顺序存储结构,将逻辑上相邻的数据元素存储在物理上相邻的存储单元里,具有以下特点:1.随机存取。2.作插入或删除操作时,需移动大量元数。3.长度变化较大时,需按最大空间分配。4.表的容量难以扩充。,24,2、链式存储,每个节点都由两部分组成:数据域和指针域。数据域存放元素本身的数据,指针域存放指针。数据元素之间逻辑上的联系由指针来体现。,例:线性表
9、(zhao,qian,sun,li,zhou,wu,zheng,wang),链式存储结构:,25,通常我们把链表画成用箭头相链接的结点的序列,结点之间的箭头表示链域中的指针。,26,1.比顺序存储结构多用空间(存储密度小)(每个节点都由数据域和指针域组成)。2.逻辑上相邻的节点物理上不必相邻。3.插入、删除灵活(不必移动节点,只要改变节点中的指针)。4.非随机存取。,链接存储结构特点:,27,链表不具有的特点是A)不必事先估计存储空间 B)可随机访问任一元素C)插入删除不需要移动元素D)所需空间与线性表长度成正比数据结构分为逻辑结构与存储结构,线性链表属于【1】。数据结构中,与所使用的计算机无
10、关的是数据的 A)存储结构B)物理结构 C)逻辑结构D)物理和存储结构 数据的逻辑结构有线性结构和【1】两大类。数据的存储结构是指A)数据所占的存储空间B)数据的逻辑结构在计算机中的表示C)数据在计算机中的顺序存储方式D)存储在外存中的数据,例题讲解,存储结构,非线性结构,28,顺序存储方法是把逻辑上相邻的结点存储在物理位置【2】的存储单元中。数据处理的最小单位是 A)数据 B)数据元素 C)数据项D)数据结构数据结构作为计算机的一门学科,主要研究数据的逻辑结构、对各种数据结构进行的运算,以及 A)数据的存储结构 B)计算方法 C)数据映象 D)逻辑存储线性表的顺序存储结构和线性表的链式存储结
11、构分别是 A)顺序存取的存储结构、顺序存取的存储结构 B)随机存取的存储结构、顺序存取的存储结构 C)随机存取的存储结构、随机存取的存储结构 D)任意存取的存储结构、任意存取的存储结构,相邻,29,根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分成 A)动态结构和静态结构 B)紧凑结构和非紧凑结构 C)线性结构和非线性结构 D)内部结构和外部结构 数据结构包括数据的逻辑结构、数据的【2】以及对数据的操作运算。数据的基本单位是【5】。下列叙述中,错误的是 A)数据的存储结构与数据处理的效率密切相关 B)数据的存储结构与数据处理的效率无关 C)数据的存储结构在计算机中所占的空间不
12、一定是连续的 D)一种数据的逻辑结构可以有多种存储结构,存储结构,数据元素,30,1.7 栈和队列,1.7.1 栈和队列的定义 栈和队列是两种特殊的线性表,它们是运算时要受到某些限制的线性表,故也称为限定性的数据结构。,31,1.栈,栈是限定仅在表尾进行插入或删除操作的线性表。栈顶表尾。栈底表头。空栈不含元素的空表。,进栈,出栈,栈s=(a1,a2,an),后进先出(LIFO),32,3.队列定义:一种特殊的线性结构,限定只能在表的一端进行插入,在 表的另一端进行删除的线性表。此种结构称为先进先出(FIFO)表。,33,栈和队列的共同特点是 A)都是先进先出 B)都是先进后出 C)只允许在端点
13、处插入和删除元素 D)没有共同点如果进栈序列为e1,e2,e3,e4,则可能的出栈序列是 A)e3,e1,e4,e2 B)e2,e4,e3,e1 C)e3,e4,e1,e2D)任意顺序一些重要的程序语言(如C语言和Pascal语言)允许过程的递归调用。而实现递归调用中的存储分配通常用 A)栈B)堆 C)数组 D)链表,例题讲解,34,栈底至栈顶依次存放元素A、B、C、D,在第五个元素E入栈前,栈中元素可以出栈,则出栈序列可能是 A)ABCED B)DCBEA C)DBCEA D)CDABE 栈通常采用的两种存储结构是 A)线性存储结构和链表存储结构B)散列方式和索引方式 C)链表存储结构和数组
14、 D)线性存储结构和非线性存储结构栈和队列通常采用的存储结构是【1】。下列数据结构中,按先进后出原则组织数据的是 A)线性链表 B)栈 C)循环链表 D)顺序表当循环队列非空且队尾指针等于队头指针时,说明循环队列已满,不能进行入队运算。这种情况称为【2】。,链表存储结构和数组,上溢,35,由两个栈共享一个存储空间的好处是A)减少存取时间,降低下溢发生的机率 B)节省存储空间,降低上溢发生的机率C)减少存取时间,降低上溢发生的机率 D)节省存储空间,降低下溢发生的机率下列关于栈的叙述中正确的是)在栈中只能插入数据 B)在栈中只能删除数据C)栈是先进先出的线性表 D)栈是后进先出的线性表下列关于队
15、列的叙述中正确的是)在队列中只能插入数据 B)在队列中只能删除数据C)队列是先进先出的线性表 D)队列是后进先出的线性表,36,1.6.1 树的定义 由一个或多个结点组成的有限集合。仅有一个根结点,结点间有明显的层次结构关系。,现实世界中,能用树的结构表示的例子:学校的行政关系、书的层次结构、人类的家族血缘关系等。,1.6 树,37,介绍几个概念:结点(Node):树中的元素,包含数据项及若干指向其子树的分支。结点的度(Degree):结点拥有的子树数。结点的层次:从根结点开始算起,根为第一层。叶子(Leaf):度为零的结点,也称端结点。孩子(Child):结点子树的根称为该结点的孩子结点。兄
16、弟(Sibling):同一双亲的孩子。双亲(Parent):孩子结点的上层结点,称为这些结点的 双亲。树的深度(Depth):树中结点的最大层次数。树的度:结点所具有的最大的度.森林(Forest):M棵互不相交的树的集合。,38,1.6.2 二叉树(Binary Tree),1、二叉树的定义及其性质(1)二叉树的定义,二叉树的五种基本形态,二叉树一种特殊的树形结构,特点是树中每个结点最多只能有两棵子树(即二叉树中不存在度大于2的结点),且子树有左右之分,次序不能颠倒。,39,性质1:二叉树的第i层上至多有2 i-1(i 1)个结点。,(2)二叉树的基本性质,第三层上(i=3),有23-1=4
17、个节点。第四层上(i=4),有24-1=8个节点。,性质2:深度为k的二叉树中至多含有2k-1个结点。,40,性质:对任何一棵二叉树T,如果其终端结点数为n0,度 为2的结点数为n2,则n0=n2+1。,证明:设n1为二叉树T中度为1的结点数;二叉树中所有结点的度均小于或等于2 其结点总数为:n=n0+n1+n2 二叉树中除了根结点外,其余结点都有一个分支进入 设分支总数为B;则 n=B+1;二叉树的分支是由度为1或2的结点射出的 B=n1+2*n2 n=n1+2*n2+1=n0+n1+n2 n0=n2+1,41,满二叉树,特点:每一层上都含有最大结点数。,完全二叉树,特点:(1)除最后一层外
18、,每一层都取最 大结点数,(2)最后一层结点都集中在该层最左边的若干位置。,42,性质:具有n个结点的完全二叉树的深度为,例:n=2 k=2 n=6 k=3 n=7 k=3 n=8 k=4 n=12 k=4,43,性质:如果对一棵有n个结点的完全二叉树的结点按层 序编号,则对任一结点i(1=i=n)有:,(2)如果2in,则结点i无左孩子(结点i为叶子结点);否则其左孩子Lchild(i)是结点2i。(3)如果2i+1n,则结点i无右孩子;否则其右孩子Rchild(i)是结点2i+1。,44,例:,i=1 是树的根,无双亲;其左孩子为2*i=2,右孩子为2*i+1=3.,2*i=1812 2*
19、i+1=1912 其无左、右孩子。,2*i+1=1312 其无右孩子。,45,1.6.3 二叉树的遍历 查找某个结点,或对二叉树中全部结点进行某种处理,就需要遍历。(1)遍历定义及遍历算法 遍历是指按某条搜索路线寻访树中每个结点,且每个结点只被访 问一次。按先左后右的原则,一般使用三种遍历:先序遍历(D L R):访问根结点,按先序遍历左子树,按先序遍历右子树。中序遍历(L D R):按中序遍历左子树,访问根结点,按中序遍历右子树。后序遍历(L R D):按后序遍历左子树,按后序遍历右子树,访问根结点。二叉树为空时,执行空操作,即空二叉树已遍历完。,46,(2)遍历算法,先序遍历:D L R中
20、序遍历:L D R后序遍历:L R D,A,D,B,C,D L R,以先序遍历D L R为例演示遍历过程,ABDC,BDAC,DBCA,47,已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是 A)acbed B)decab C)deabc D)cedba 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为 A)GEDHFBCA B)DGEBHFCA C)ABCDEFGH D)ACBFEDHG树是结点的集合,它的根结点数目是 A)有且只有1B)1或多于1 C)0或1D)至少2下列叙述中正确的是 A)线性表是线性结构B)
21、栈与队列是非线性结构 C)线性链表是非线性结构D)二叉树是线性结构,例题讲解,48,在深度为5的满二叉树中,叶子结点的个数为 A)32B)31 C)16 D)15 若某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是 A)bdgcefha B)gdbecfha C)bdgaechf D)gdbehfca在树结构中,树根结点没有【1】。具有3个结点的二叉树有 A)2种形态 B)4种形态 C)7种形态 D)5种形态设一棵二叉树中有3个叶子结点,有8个度为1的结点,则该二叉树中总的结点数为 A)12 B)13 C)14D)15,双亲结点,4
22、9,设有下列二叉树:对此二叉树前序遍历的结果为A)ZBTTCPXA B)ATBZXCTP C)ZBTACTXP D)ATBZXCPT设有下列二叉树:对此二叉树的中序遍历的结果为A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA,50,设树T的度为4,其中度为1、2、3、4的结点个数分别为4、2、1、1。则T中的叶子结点数为A)8 B)7 C)6 D)5设一棵完全二叉树共有700个结点,则该二叉树中有()个叶子结点。在一个容量为15的循环队列中,若头指针front=6,尾指针rear=9,则该循环队列中共有()个元素。设一棵二叉树的中序遍历结果为DBEAFC,前序遍历结果为A
23、BDECF,则后序遍历结果为()。,350,3,DEBFCA,51,1.7 查找和排序,顺序查找与二分查找算法基本排序算法(交换类排序、选择类排序、插入类排序),52,1.7.1 顺序查找(线性查找),查找过程:对给定的一关键字K,从线性表的一端开始,逐个进行记录的关键字和K的比较,直到找到关键字等于K的记录或到达表的另一端。可以采用从前向后查,也可采用从后向前查的方法。在平均情况下,大约要与表中一半以上元素进行比较,效率较低。平均查找长度较大。最好情况:1 最坏情况:n在下面两种情况下只能采取顺序查找:a.线性表为无序表(元素排列是无序的);b.即使是有序线性表,但采用的是链式存储结构。,5
24、3,1.7.1 折半查找(二分法查找),思想:先确定待查找记录所在的范围,然后逐步缩小范围,直到找到或确认找不到该记录为止。前提:必须在具有顺序存储结构的有序表中进行。分三种情况:1)若中间项的值等于x,则说明已查到。2)若x小于中间项的值,则在线性表的前半部分查找;3)若x大于中间项的值,则在线性表的后半部分查找。特点:比顺序查找方法效率高。最坏的情况下,需要比较 log2n次。,54,排序方法,插入排序,选择排序,交换排序,归并排序,简单插入排序,希尔排序,简单选择排序,堆排序,起泡排序,快速排序,1.7.2 排序,55,在长度为n的有序线性表中进行二分查找。最坏的情况下,需要的比较次数为
25、【2】。假设线性表的长度为n,则在最坏情况下,冒泡排序需要的比较次数为 A)log2n B)n2 C)O(n1.5)D)n(n-1)/2,例题讲解,log2n,冒泡排序算法在最好的情况下的元素交换次数为【1】。在最坏情况下,堆排序需要比较的次数为【2】。排序是计算机程序设计中的一种重要操作,常见的排序方法有插入排序、【1】和选择排序等。,0,nlog2n,交换排序,56,2.程序设计基础,57,2.1 程序设计方法与风格,2.1.1 程序设计方法结构化设计方法面向对象程序设计方法,58,2.2 结构化程序设计,基本概念三种基本结构顺序结构选择结构循环结构三种基本结构的特点只有一个入口只有一个出
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全国计算机 二级 公共 基础知识 要点
链接地址:https://www.31ppt.com/p-5233541.html