计算机2级公共基础知识考前必看参考课件

计算机等级考试公共基础知识1第2页计算机二级考试公共基础知识大纲数据结构与算法程序设计基础软件工程基础数据库设计基础这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个（10分），总分值占到了试卷卷面分的30％，是一个不小的比例。第3页算法⒈算法的基本概念2.算法复杂度的概念和意义一、基本数据结构与算法数据结构⒈数据结构的概念⒉线性表⒊栈和队列⒋树与二叉树⒌查找技术⒍排序技术对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概念、二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。第4页算法的定义对解题方案准确而完整的描述称为算法。算法是程序设计的核心⒈算法的基本概念算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程(计算的方法)。在这个过程中，无论是形成解题思路(推理实现的算法)还是编写程序(操作实现的算法)，都是在实施某种算法。例：n个数从大到小进行排序。有多种排序方法，常用的有冒泡排序、选择排序等。第5页2.算法的基本特征一个算法应该具有以下五个重要的特征：有穷性确定性输入输出可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成第6页算法与计算机程序算法____是一组逻辑步骤程序——用计算机语言描述的算法3.算法的表示INPUTrS=3.14*r*rPTINTS开始输入RS=3.14*R*R输出S结束问题：输入园的半径，计算园的面积一个算法的表示需要使用一些语言形式。传统的算法-------图形法，如“流程图”和N-S图目前常用的方法-------使用伪码描述算法。第7页4.算法评价评价一个算法优劣的主要标准是算法的执行效率和存储需求：时间复杂度：执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量空间复杂度：执行这个算法所需要的内存空间算法在执行过程中临时占用的存储空间时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分第8页总结对解题方案准确而完整的描述称为算法。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法评价：时间复杂度：执行这个算法所需要的计算工作量空间复杂度：执行这个算法所需要的内存空间第9页(1)在计算机中，算法是指______。A.查询方法B.加工方法C.解题方案的准确而完整的描述D.排序方法(2)下列叙述中正确的是A)算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需要的计算工作量C)数据的逻辑结构与存储结构是一一对应的D)算法的时间复杂度与空间复杂度一定相关(3)算法的有穷性是指A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户使用(c)(B)算法习题:(A)第10页(4)算法的时问复杂度是指A)算法的执行时间B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的基本运算次数(5)算法的空间复杂度是指A）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数(6)下列叙述中正确的是A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间复杂度必定小D）上述三种说法都不对(D)计算工作量(A)(D)第11页计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。二、数据结构程序=算法+数据结构数据结构是指相互有关联的数据元素的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。第12页二.数据结构数据结构是指相互有关联的数据元素的集合。数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。第13页1.逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。例：1.一年四季的数据结构B=(D,R)D={春，夏，秋，冬}R={(春，夏),(夏，秋),(秋，冬)}2.家庭成员的数据结构B=(D,R)D={父亲，儿子，女儿}R={(父亲，儿子),(父亲，女儿)}春夏秋冬数据结构的图形表示父亲儿子女儿第14页常见的逻辑结构有：线性结构、树形结构和图形结构。线性结构树形结构图形结构①线性结构结构中的每个元素之间存在一个对一个的关系；②树形结构结构中的每个元素之间存在一个对多个的关系；③图形结构或网状结构结构中的每个元素之间存在多个对多个的关系。其中，树形结构和图形结构统称为非线形结构。数据的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。第15页常见的数据结构1.线性表2.栈和队列3.树第16页１．线性表（LinearList）线性表是由n（n≥0）个数据元素a1，a2，…，ai，…，an组成的一个有限序列。简单的线性表春夏秋冬复杂的线性表记录102011001张三男…记录202011003李四女…记录3记录4第17页2.栈和队列栈和队列都是特殊的线性表。栈（Stack）及其基本运算队列（Queue）及其基本运算循环队列及其基本运算第18页栈（Stack）是一种特殊的线性表。其特点是插入和删除运算都只能在线性表的一端进行。栈是按照“先进后出”或“后进先出”的原则组织数据的线性表。栈的物理存储结构可以用顺序结构，也可以用链表结构。下面讨论顺序存储结构中栈元素的插入和删除运算。顺序栈的进栈和出栈运算栈的基本运算有三种：入栈、退栈和读栈顶元素在顺序栈中插入和删除运算不需要移动表中其他数据元素。第19页队列（Queue）是一种特殊的线性表。其特点是所有的插入都在表的一端进行，所有的删除运算都在表的另一端进行。队列是按照“先进先出”或“后进后出”的原则组织数据的线性表。队列的物理存储结构可以用顺序结构，也可以用链式结构。顺序队列的运算栈有三种操作：入栈＼出栈＼读栈顶元素队列有三种操作：入队＼出队＼读队首元素例：有入栈元素序列：ABCD，求可能的出栈序列．如是队列又是什么情况呢？第20页循环队列把队列的存储空间在逻辑上看作一个环，当R指向存储空间的末端后，就把它重新置于始端。循环队列的运算队列中进行插入的一端称做队尾(rear),进行删除的一端称做队首(front)。习题：数据结构分为逻辑结构和存储结构，循环队列属于【】结构。（2005年9月）答案：存储结构。第21页常见数据结构的逻辑结构线性表线性结构栈是特殊的线性表队列也是一种操作受限的特殊的线性表树（树型结构）是一种重要的非线形数据结构第22页数据存储结构方面的考题1：数据的存储结构是指A)存储在外存中的数据B)数据所占的存储空间量C)数据在计算机中的顺序存储方式D)数据的逻辑结构在计算机中的表示2.下列叙述中正确的是A）栈是“先进先出”的线性表B）队列是“先进后出”的线性表C）循环队列是非线性结构D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构3.数据结构分为线性结构和非线性结构，带链的队列属于[]。4.下列数据结构中，属于非线性结构的是A）循环队列B)带链队列C)二叉树D）带链栈答案：D。答案：D。答案：线性结构。答案：c第23页5。下列叙述中正确的是（）。A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间答案：A。6。下列关于栈的叙述正确的是A）栈按“先进先出”组织数据B)栈按“先进后出”组织数据C）只能在栈底插入数据D）不能删除数据答案：B。7.一个队列的初始状态为空。现将元素A，B，C，D，E，F，5，4，3，2，1依次入队，然后再依次退队，则元素退队的顺序为【1】。（2010年3月）答案：A，B，C，D，E，F，5，4，3，2，1第24页一个非空的数据结构若满足下面的两个条件，则这种数据结构即为线性结构。①有且仅有一个根结点；②除第一个结点外，每一个结点最多有一个直接前驱结点；③除最后一个结点外，每一个结点最多有一个直接后继结点。线性结构与非线性结构线性表、栈和队列都是线性结构一个数据结构不是线性结构，则称其为非线性结构。a1a2a5a3a4HEAD319510线性链表的逻辑状态第25页树型结构是一种重要的非线性结构。树的概念二叉树的概念二叉树的存储二叉树的遍历3.树与二叉树第26页树的概念树的定义：n个结点的有限集。（n=0）ABDFECGHIJKM根：onlyone若n=0，则称为空树；否则，当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，...，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归的。Question：如何辨别根？A只有一个结点的树第27页树型结构的常用术语ABDFECGHIJKM结点的度一个结点的子树的个数；Q：结点A、G的度数？树的度树中所有结点度的最大值；Q：右图中树的度？终端结点度为0的结点；Q：图中叶子结点有几个？7非终端结点度不为0的结点；Q：图中非终端结点有几个？5孩子结点、双亲结点、兄弟结点、结点的子孙、结点的祖先第28页树型结构的常用术语ABDFECGHIJKM结点的层次树中根结点的层次为1，根结点子树的根为第2层，以此类推；Q：图中结点F的层次？树的深度树中所有结点层次的最大值；Q：图中树的深度？有序树、无序树如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。①②③④第29页二叉树的概念定义：二叉树是一种有序的树形结构。它与一般树形结构的区别是：每个结点最多有两棵子树；子树有左右之分，次序不能任意颠倒。二叉树的5种基本形态第30页二叉树的性质【性质1】在二叉树的第i层上最多有2i-1个结点（i≥1）ABCDFEHG第31页【性质2】深度为h的二叉树最多有2h-1个结点（h≥1）满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。第32页满二叉树完全二叉树完全二叉树是满二叉树满二叉树也是完全二叉树第33页非完全二叉树深度为4的完全二叉树第34页【性质3】二叉树上叶子结点数比度为2的结点数多1ABCDFEHG度为2的结点叶子结点第35页1：在深度为7的满二叉树中,叶子结点的个数为A)32B)31C)64D)632：在深度为7的满二叉树中，度为2的结点个数为【】。3：一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为A）219B）2