二级公共基础经典课件

《二级公共基础经典课件》由会员分享，可在线阅读，更多相关《二级公共基础经典课件（137页珍藏版）》请在金锄头文库上搜索。

1、全国计算机等级考试二级公共基础知识热烈欢迎你们来共同学习，有问题随时联系！2011年3月二级公共基础知识点分布第一章 数据结构与算法(30%)n 考试大纲1. 算法的基本概念；算法复杂度的概念和意义（时间 复杂度与空间复杂度）。 2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图 形表示；线性结构与非线性结构的概念。 3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、 中序和后序遍历。 7. 顺序

2、查找与二分法查找算法；基本排序算法（交换类排序，选 择类排序，插入类排序）。一.算法的基本概念*1.所谓算法是指解题方案的准确而 完整的描述。严格来说，一个算法必须 具有以下五个主要特征：n有穷性 确定性 可行性 输入 输出n输出或输出可说成：拥有足够的情报 2.算法的组成要素n算法中对数据的运算和操作n算法的控制结构一.算法的基本概念3.算法设计的要求 通常设计一个“好”的算法，应考虑达到以下目标。n正确性：算法应当满足具体问题的需求。n可读性：算法主要是为了人的阅读与交流，其次才是机 器执行。可读性好有助于人对算法的理解。n健壮性：当输入数据非法时，算法也能适当地做出反应 或进行处理，而不

3、会产生莫明其妙的输出结果。 n效率与低存储量需求。 效率指的是算法执行时间。对于同一个问题如果有多个 算法可以解决，执行时间短的算法效率高。低存储量需求 指算法执行过程中所需要的最大存储空间。一.算法的基本概念4.算法设计基本方法n列举法n归纳法n递推n递归n减半递推n回溯法一.算法的基本概念*5.算法的复杂度可分为时间复杂度 和空间复杂度，是衡量算法优劣的量度 。 （1）算法的时间复杂度n算法的时间复杂度是指执行算法所需 要的工作量。一般情况下，算法的时间 复杂度为算法中的基本操作重复执行的 次数。是问题规模n的某个函数f(n)。一.算法的基本概念n何估算算法的时间复杂度？任何一个算法都是由

4、一个“控制结构 ”和若干“原操作”组成的，因此一个算 法的执行时间可以看成是所有原操作的执 行时间之和( 原操作(i)的执行次数原操作 (i)的执行时间 )nFor i=1 to 100for j=1 to 100s=i*j 。 算法时间复杂度为：O（n2)一.算法的基本概念AQ21（2）算法的空间复杂度n算法的空间负杂度是指执行这个算法 所需要的内存空间。空间复杂度作为算 法所需存储空间的量度，记作： S(n)=O(g(n)，其中n为问题的规模， 表示随问题规模的增大，算法运行所需 存储量的增长率与g(n)的增长率相同。n一般不估计空间复杂度典型例题1.一个算法是对某类给定的问题求解过程的精

5、确描述，算法中的操作都 可能 通过将已经实现的基本操作执行有限次来实现，这句话说明算法具有什么特性？A 有穷性 B 可行性 C 确定性 D 健壮性 2.算法的时间复杂度是指（） A）执行算法程序所需要的时间 B）算法程序的长度 C）算法执行过程中所需要的基本运算次数 D）算法程序中的指令条数 3.下面叙述正确的是（） A）算法的执行效率与数据的存储结构无关 B）算法得空间复杂度是指 算法程序中指令（或语句）的条数 C）算法得有穷性是指算法必须能在执行 有限个步骤之后终止 D）以上三种描述都不对 4.算法能正确地实现预定功能的特性称为算法的（ ）。A正确性 B易读性 C健壮性 D高效率 5. 算

6、法的计算量的大小称为计算的（ ）。A效率 B. 复杂性 C. 现实性 D. 难度 二.数据结构1.数据结构的定义：是指相互有关联的数据元素的集合。备注： 1）数据元素：是数据的基本单位，由数据项组成。通俗的说 ：数据元素就是现实世界中的一个实体的抽象。 2）数据项：数据的最小单位。 *2. 数据结构主要研究三个方面的问题：1)数据集合中各数据元素之间的逻辑关系，即数 据的逻辑结构。 2)在对数据进行处理时，各数据元素在计算机中 的存储关系，即数据的存储结构。 3)对各种数据结构进行的运算。数据结构简单实例Student Student zhangsan Student lisi name; z

7、hangsan; lisi;Sno; s20081001; s20081001; class; 计算机1班； 计算机1班 ；Rscore; 515； 501； 数据的逻辑结构n数据逻辑结构是对 数据元素之间存在的 逻辑关系的描述（本 身固有的），它可以 用一个数据元素的集 合和定义在此集合上 的若干关系表示。n与数据在计算机中 的存储位置无关，是 独立于计算机的。 数据的存储结构n数据的存储结构是数据元素及其关系在计算机存 储器中的表示。存储结构的主要内容是指在存储空间 中使用一个存储结点来存储一个数据元素，在存储空 间中建立各存储结点之间的关联，来表示数据元素之 间的逻辑关系。n常见的存储结

8、构：n顺序存储结构n链式存储结构n索引存储结构n散列存储结构典型例题（1）数据结构中，与所使用的计算机无关的是数据的 A）存储结构 B）物理结构 C）逻辑结构 D）物理和存储结构 （2）数据在计算机中的存储位置改变了，（）不变。 A.数据的存储地址 B.数据间的逻辑关系 C.数据的物理存储结构 D.逻辑结构和物理结构线性结构和非线性结构线性结构n在数据元素的非空有限集合中，线性结构的逻辑 特征如下：n存在一个唯一的被称为“第一个”的数据元素n存在一个唯一的被称为“最后一个”的数据元素n除第一个之外，集合中的每个数据元素均有且只 有一个直接前驱n除最后一个之外，集合中的每个数据元素均有且 只有一

9、个直接后继 非线性结构n非线性结构的逻辑特征是：一个结点可能有多个 直接前驱和直接后继，树和图都属于非线性结构。线性表n通常以下列 n 个数据元素的序列” 表示线性表 ：(a1,a2 ,.,ai ,.,an) n序列中数据元素的个数 n 定义为线 性表的表长；n=0 时的线性表被称为空 表。称 i 为ai在线性表中的位序。线性表的顺序存储n线性表的顺序存储结构用一组地址连续的存储单元依次 存放线性表中的数据元素，即以“存储位置相邻”表示“位 序相继的两个数据元素之间的前驱和后继的关系，并以表中 第一个元素的存储位置作为线性表的起始地址，称作线性表 的基地址。 所有数据元素的存储位置均可由第一个

10、数据元素的存储位置得到 ADR(ai) = ADR(a1) + (i-1)C 基地址 一个数据元素所占存储量 线性表的插入和删除运算n插入运算是指在线性表的某个指定位置增加一 个新结点。n一般情况下，要在第i(1in)个元素之前插 入一个新元素时，首先要从最后一个元素开始， 直到第i个元素之间共n-i+1个元素依次向后移动 一个位置，然后将新元素插入到第i项。n删除运算是指撤销结构中的某个结点。n一般情况，要删除第i(1in)个元素，要从 第i+1个元素开始，直到第n个元素，共n-i个元 素依次向前移动一个位置。栈n栈是限定仅在表的一端进行插入和删除操作的线性表。允许插 入和删除的一端称为栈顶

11、，另一端称为栈底。n栈顶元素总是最后被插入的元素，从而也是最先被删除的元素 ；栈底元素总是最先被插入，也是最后被删除的元素。因此，栈 是一种后进先出的线性表。n通常用指针top指示栈顶位置，用指针bottom指示栈底位置。栈的顺序存储及运算n用一维数组S(1:m)作为栈的顺序存储空间， m为栈的最大容量。top=0表示栈为空，top=m 表示栈满。n栈的操作n入栈：在栈顶位置插入一个新元素，栈顶指针 top加1。n退栈：取出栈顶元素并赋值给一个指定的变量， 栈顶指针top减1。n取栈顶元素：将栈顶元素的值赋给一个指定的变 量，不删除栈顶元素，栈顶指针不变。栈n如果某栈的入栈顺序是ABCDEF，

12、则 出栈顺序不可能是哪个（）nA、DCEFBAnB、ABCDEFnC、EDFCABnD、CBAEDF队列n队列是一种先进先出的线性表，它只允许在表的一端 插入元素(队尾)，在另一端删除元素(队头)。通常定义头 指针front指向队头元素的前一个位置，定义尾指针rear 指向队尾元素的位置。n队列是一种先进先出的数据结构。n向队尾插入一个元素的操作称为入队，从队头删除一 个元素的操作称为退队。循环队列n将队列存储空间的最后一个位置绕到第一个位置 ，形成逻辑上的环状空间。n循环队列初始状态为空，即front=rear=0.nFront总是指示队头元素，rear指示队尾元素加1的位置。n入队操作时，

13、rear加1，若rear+1容量，则置rear=0；n退队操作时，front加1，若front+1容量，则置front=0 。n*当rearfront时，元素个数rearfront ；当 rear1时，其余的结点 可分为m个互不相交的子集 T1,T2,Tm，其中每个有限子集 本身又是一棵树，并且称为根的 子树。n集合为空的树简称为空树； 树中的元素称为结点。树的主要术语n结点的度：结点拥有的子树数。n叶节点(终端结点)：度为0的结点。n双亲、孩子和兄弟：结点的子树的根节点 称为该结点的孩子，该结点称为孩子结点的 双亲结点。同一个双亲结点的孩子互称为兄 弟。n层次：结点的层次从根开始定义，根为第

14、 一层，根的孩子为第二层。n深度：树中结点的最大层次称为树的深度 或高度。二叉树n二叉树是n(n0)个数据元 素的有限集，它或为空集,或 者含有唯一的称为根的元素， 且其余元素分成两个互不相交 的子集，每个子集自身也是一 棵二叉树，分别称为根的左子 树和右子树。n二叉树是另一种树型结构 ，其特点是每个结点至多有两 棵子树，并且二叉树的子树有 左右之分，其顺序不能任意颠 倒。二叉树的基本性质n性质1 在二叉树的第i层上至多有2i-1个结点（ i1）n性质2 深度为k的二叉树至多有2k -1个结点（ k1）n性质3 对任何一棵二叉树T，如果其终端结点数 为n0，度为2的结点数为n2 ，则：n0 =

15、n2+1n性质4 具有n个结点的二叉树，其深度至少为 log2n +1 例： 一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总 结点数为 A）221 B）219 C）231 D）229 例：一棵含18个结点的二叉树的高度至少为A）3 B）4 C）5 D）6满二叉树和完全二叉树n满二叉树除最后一层外，每一层上的所有结点都有两个子节点， 也就是说每一层上的结点数都达到最大值，即在满二叉树的第k层上 有2k-1个结点，且深度为m的满二叉树有2m-1个结点。n完全二叉树除最后一层外，每一层上的结点数均达到最大值，在 最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，其 深度为log2n +1。n从以上定义可知，满二叉树也是完全二叉树，反之则不然。满二叉树 最大层