搜索
个人简介姓名：谭夏秋记诺教育学校二级ACCESS、二级MS-Office讲师联系电话：13109799091交流QQ：879150342计算机二级考试公共基础知识大纲数据结构与算法程序设计基础软件工程基础数据库设计基础全国计算机等级考试二级公共基础知识不单独考试，与其他二级科目组合在一起，作为二级科目考核内容的一部分。考试方式:上机考试题型：选择题（注：10道选择题，占总分值的10%）第一章数据结构与算法(30%)考试大纲1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5.线性单链表、双向链表与循环链表的结构及其基本运算。6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。算法的定义对解题方案准确而完整的描述称为算法。算法是程序设计的核心算法的基本概念算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程(计算的方法)。在这个过程中，无论是形成解题思路(推理实现的算法)还是编写程序(操作实现的算法)，都是在实施某种算法。例：n个数从大到小进行排序。有多种排序方法，常用的有冒泡排序、选择排序等。算法的基本特征一个算法应该具有以下五个重要的特征：有穷性确定性输入输出可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成算法的两个基本要素：基本运算和操作算术运算关系运算逻辑运算数据传输控制结构顺序选择循环一是对数据对象的运算和操作；二是算法的控制结构。算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法算法的复杂度评价一个算法优劣的主要标准是算法的执行效率和存储需求：时间复杂度：执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量空间复杂度：执行这个算法所需要的内存空间算法在执行过程中临时占用的存储空间时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。数据结构程序=算法+数据结构数据结构是指相互有关联的数据元素的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。数据结构是指相互有关联的数据元素的集合。数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。1.数据的逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。春夏秋冬数据结构的图形表示父亲儿子女儿数据逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。与数据在计算机中的存储位置无关，是独立于计算机的。常见的逻辑结构有：线性结构、树形结构和图形结构。①线性结构结构中的每个元素之间存在一个对一个的关系；②树形结构结构中的每个元素之间存在一个对多个的关系；③图形结构或网状结构结构中的每个元素之间存在多个对多个的关系。其中，树形结构和图形结构统称为非线形结构。数据的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。数据的存储结构（物理结构）计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有：顺序存储结构链式存储结构索引存储结构•只抽象地反映数据元素之间的关系的结构，而不管其存储方式的数据结构称为逻辑结构。•一种数据结构可以根据需要表示成一种或多种存储结构。常见的数据结构：1.线性表2.栈和队列3.树线性结构和非线性结构线性结构在数据元素的非空有限集合中，线性结构的逻辑特征如下：存在一个唯一的被称为“第一个”的数据元素存在一个唯一的被称为“最后一个”的数据元素除第一个之外，集合中的每个数据元素均有且只有一个直接前驱除最后一个之外，集合中的每个数据元素均有且只有一个直接后继非线性结构非线性结构的逻辑特征是：一个结点可能有多个直接前驱和直接后继，树和图都属于非线性结构。１．线性表线性表是由n（n≥0）个数据元素a1，a2，…，ai，…，an组成的一个有限序列。简单的线性表春夏秋冬复杂的线性表记录102011001张三男…记录202011003李四女…记录3记录4线性表的存储结构有两种：顺序存储结构、链式存储结构线性表的顺序存储线性表的顺序存储结构用一组地址连续的存储单元依次存放线性表中的数据元素，即以“存储位置相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址。所有数据元素的存储位置均可由第一个数据元素的存储位置得到ADR(ai)=ADR(a1)+(i-1)×C↑↑基地址一个数据元素所占存储量顺序表的插入和删除运算线性表的顺序存储结构称为顺序表。顺序表的插入运算顺序表的删除运算在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。线性表的链式存储结构线性表的链式存储结构称为线性链表。链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：单链表的插入运算单链表的删除运算线性链表的插入和删除运算采用链式存储结构，存储空间开销较大，但是进行插入和删除运算不会造成大量元素的移动。循环链表是加一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。a1a2a5a3a4HEAD319510双向链表的存储结构HEAD31510a2a3a4a1双向链表可以克服单链表的单向性的缺点。在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。线性表的存储结构有两种顺序存储结构注意：数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。一个逻辑数据结构可以有多种存储结构，且不同的存储结构影响数据处理的效率。链式存储结构线性表:{a1，a2，a3，a4，a5}栈和队列栈和队列都是特殊的线性表。栈（Stack）及其基本运算队列（Queue）及其基本运算循环队列及其基本运算栈顺序栈的进栈和出栈运算：栈是限定仅在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入，也是最后被删除的元素。因此，栈是一种先进后出（后进先出）的线性表。通常用指针top指示栈顶位置，用指针bottom指示栈底位置。……a2a1an栈顶top栈底bottom入栈出栈栈的物理存储结构可以用顺序结构，也可以用链表结构。栈的基本运算有三种：入栈、退栈和读栈顶元素队列队列是一种先进先出的线性表，它只允许在表的一端插入元素(队尾)，在另一端删除元素(队头)。通常定义头指针front指向队头元素的前一个位置，定义尾指针rear指向队尾元素的位置。队列是一种先进先出的数据结构。向队尾插入一个元素的操作称为入队，从队头删除一个元素的操作称为退队。ABEDCF入队退队FrontRear栈的物理存储结构可以用顺序结构，也可以用链表结构。队列的基本运算有三种：入队＼出队＼读队首元素循环队列将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，当R指向存储空间的末端后，就把它重新置于始端。循环队列的运算队列中进行插入的一端称做队尾(rear),进行删除的一端称做队首(front)。线性表线性结构栈是特殊的线性表队列也是一种操作受限的特殊的线性表树（树型结构）是一种重要的非线形数据结构常见数据结构的逻辑结构一个非空的数据结构若满足下面的两个条件，则这种数据结构即为线性结构。①有且仅有一个根结点；②除第一个结点外，每一个结点最多有一个直接前驱结点；③除最后一个结点外，每一个结点最多有一个直接后继结点。线性结构与非线性结构线性表、栈和队列都是线性结构一个数据结构不是线性结构，则称其为非线性结构。a1a2a5a3a4HEAD319510线性链表的逻辑状态树型结构是一种重要的非线性结构。树的概念二叉树的概念二叉树的存储二叉树的遍历树与二叉树树及其基本概念树是一种简单的非线性结构，在树中，所有的数据元素之间具有明显的层次性关系。树是(n≥0)个结点的有限集合，在任意一棵非空树中：(1)有且仅有一个特定的结点称为根结点。(2)当n1时，其余的结点可分为m个互不相交的子集T1,T2,…Tm，其中每个有限子集本身又是一棵树，并且称为根的子树。集合为空的树简称为空树；树中的元素称为结点。树型结构的常用术语ABDFECGHIJKM1)度：结点拥有的子树数。2)叶子节点(终端结点)：度为0的结点。3)层次：结点的层次从根开始定义，根为第一层，根的孩子为第二层。4)深度：树中结点的最大层次称为树的深度或高度。5)结点的层次树中根结点的层次为1，根结点子树的根为第2层，以此类推；6)树的深度树中所有结点层次的最大值；①②③④二叉树二叉树是n(n≥0)个数据元素的有限集，它或为空集,或者含有唯一的称为根的元素，且其余元素分成两个互不相交的子集，每个子集自身也是一棵二叉树，分别称为根的左子树和右子树。二叉树是另一种树型结构，其特点是每个结点至多有两棵子树，并且二叉树的子树有左右之分，其顺序不能任意颠倒。定义：二叉树是一种有序的树形结构。它与一般树形结构的区别是：1)每个结点最多有两棵子树；2)子树有左右之分，次序不能任意颠倒。二叉树的基本性质【性质1】在二叉树的第K层上最多有2k-1个结点（k≥1）【性质2】深度为h的二叉树最多有2h-1个结点（h≥1）【性质3】二叉树上叶子结点数比度为2的结点数多1ABCDFEHG度为2的结点叶子结点满二叉树最大层的结点均向左靠齐完全二叉树ADCBEF满二叉树和完全二叉树满二叉树：如果一个深度为h的二叉树拥有2h-1个结点，则将它称为满二叉树。完全二叉树：有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1~n的结点位置一一对应，则称这棵二叉树为完全二叉树。二叉树的存储结构在计算机中，二叉树通常采用链式存储结构。Ll