当前位置:文档之家› 知识点大纲全国计算机等级考试数据结构和算法

知识点大纲全国计算机等级考试数据结构和算法

全国计算机等级考试二级office二级公共基础知识部分(10分*10题)第一章. 算法与数据结构考点1:算法概念● 算法算法:指解题方案准确而完整的描述。

算法不等于程序,也不是计算方法。

程序编制通常不优于算法设计。

考点2:算法的四个基本特征可行性、确定性(算法步骤有明确定义)、有穷性、拥有足够情报考点3:算法的时间复杂度和空间复杂度1. 时间复杂度:执行算法所需的工作量。

算法执行的基本次数是问题规模的函数,固定规模下还与输入有关。

2. 空间复杂度:算法执行需要的存储空间(算法程序、输入初始数据、某种数据结构所需空间)● 数据结构(反映数据元素之间关系的数据元素集合,即带有结构的数据元素的集合,结构指数据元素之间的前后件(前驱、后继)关系)。

目的是提高数据处理的效率(速度/空间)数据的逻辑结构:是反映数据元素之间逻辑关系的数据结构。

可以表示成:B=(D ,R )B 表示数据结构;D 表示数据元素集合;R 表示数据元素之间的前后件关系【例:一年四季的数据结构可以表示成B=(D ,R );D=(春,夏,秋,冬);B={(春,夏),(夏,秋),(秋,冬)}】数据结构的图形表示:数据元素:用中间标有元素值的方框表示,称为结点。

逻辑关系:用有向线段从前件指向后件。

没有前件的结点称为根结点;没有后件的结点称为终端结点(叶子结点)B=(D ,R ) D={di|1≤i ≤7}={d1,d2,d3,d4,(d1,d3),(d1,d7),(d2,d4),(d3,d6),(d4,d5)}考点4:数据的存储结构数据的存储结构:指数据的逻辑结构在计算机储存空间的存放形式。

既储存数据元素的信息,还有元素的前后件关系信息。

数据的逻辑关系与数据的存储结构不一定相同。

数据结构一般可以表示成多种存储结构,常见的存储结构有顺序、链接、索引等。

采用不同的存储结构,其数据处理效率不同。

考点5:线性结构和非线性结构(逻辑结构而言)线性结构(线代表):● 有且只有一个根结点,它无前件;● 有且只有一个终端(叶子)结点,无后件;● 除根结点和终端结点外,其他所有结点有且只有一个前件和一个后件。

线性表中结点个数n 称为线性表的长度;n=0表示空表。

常见的线性结构有线性表、栈、队列(循环队列)。

线性表是最简单、常见数据结构。

可用顺序存储结构、链式存储结构。

顺序储存结构特点:线性表中所有元素存储空间连续,按逻辑顺序依次存放。

非线性结构:一个数据结构不是线性结构,称为非线性结构(树、图)。

空的数据结构可能是线性结构,也可能是非线性结构。

考点6:顺序表的插入运算例:在第二个元素(18)之前插入一个元素87,过程如下:1、29;2、18;3、56;4、63 1、29;2、18;3、56;4、 ;5、63 1、29;2、18;3、 ; 4、56;5、63 1、29;2、;3、18 ;4、56;5、63 1、29;2、87;3、18 ;4、56;5、63【在平均情况下,插入运算在第i 个(1≤i ≤n )元素之前进行,需要移动一半的元素;最坏情况下需移动所有元素】例:线性表的删除运算 删除线性表中的第一个元素(29),过程如下:1、29;2、18;3、56 1、 ;2、18;3、56 1、18;2、 ;3、56 1、18;2、56【在一般情况下,要删除第i 个(1≤i ≤n )元素时,在平均情况下,需要移动一半的元素。

因此,在线性表顺序存储情况下,要删除一个数据,效率很低】考点7:栈栈:是限定在一端进行插入和删除或删除操作的一端称为栈顶,另一端称为栈底。

原则是:栈具有记忆功能。

1. 栈底指针 bottom (指向最底部)2. 栈顶指针 top (始终指向最顶部)3. 栈空 即top=0(不能退栈,否则 下溢错误)4. 入栈(元素苹果、桔子、西瓜、草莓依次入栈,top 指针上移)5. 栈满 (top6. 出栈(草莓、西瓜、桔子、苹果依次出栈进行退栈操作,top 考点8:队列队列:允许在一端进行插入,另一端进行删除的线性表。

1. 尾指针 rear :插入一端称队尾,rear 指向队尾元素且始终指向最后入队元素。

2. 排头指针 front : 出队一端称为排头(队头),用front 考点9:循环队列 rear=front=m (队头、队尾指针同时指向同一个元素)。

入队运算:初始状态下,F 和R 都指向1,随着ABC 元素的入队,R F 不变。

当R 指向最后一个元素C 之后,R 最终回到指向1出队运算:在初始状态下RF 都在1,一个元素退出,F 上移一格 R 如:当F 上移一格,第一个元素A 就会退出,被赋值给其它元素如队头指针F 继续上移一格,B 退出赋值给b ,以此类推。

队尾指针始终不变指向1,rear 指向位置才是队尾。

此时,队尾可以继续进行入队操作,元素E 、F 可以继续入队直到队满。

此时,Rear 和Front 同时指向时队满。

即rear=front=m 。

因此,仅凭rear=front=m ,不能确定对空或者队满。

因此,我们定义标记S 。

S=0 表示队列空;S=1 表示队列非空(不一定是满)因此,我们可以得到:队列为空条件为s=0,rear=front ;队列满条件为s=1,rear=front 。

队列满,不能进行入队操作,否则“上溢”;队列空不能进行退队操作,否则“下溢”。

考点10:线性链表● 线性链表是线性表的链式存储结构。

● 线性链表中每一个存储结点分为两部分:● 例:在线性链表的结点X 之前插入一个新元素b,1) 取得一个结点,设该结点号为p ,其数据域为2) 使结点p 指向包含X 的结点。

即结点p 的指针域为原结点q 的指针域(X3)使结点p 指针域改为p ,即指向元素b,顺序表和链表的优缺点比较● 树(tree ):非线性结构,具有明显的层次结构● 父结点:在树结构中,每一个结点只有一个前件,这个前件称为父结点。

● 根结点(F ):没有前件的结点称为根节点,一个树只有一个。

● 子节点:在树结构中,每一个结点可以有多个后件,这些后件都称为子节点。

● 叶子结点:没有后件的结点,称为叶子结点。

● 结点的度:一个结点拥有的后件个数称该结点的度。

(叶子结点度为0)F 度为3 ● 树的度:在树结构中,所有结点中最大的度称为树的度。

结点F 3● 树的深度:树的最大层次称为树的深度。

4 (树)● 子树:以某结点的一个子结点为根构成的树称为该结点的子树(图框内是以C 为根结点的子树)。

✧ 树的存储结构:树在计算机中用多重链表示。

多重链表中的每个结点描述了树中对应结点的信息,件进行依次说明,这是对于树当中每个结点必须存在的存储形式。

✧ 二叉树特点:非空二叉树只有一个根结点;每一个结点最多有两颗子树,且分别称为该结点的左子树和右子树。

在二叉树中,每一个结点的度最大为2,所有子树均为二叉树。

考点11-13:二叉树的性质1、2、3性质1:二叉树的第i 层上至多有2i-1(i ≥1)个结点。

性质2:深度为h 的二叉树中至多含有2h -1个结点。

性质3:在任意二叉树中,度为0结点(叶子结点)比度为2结点多一个。

例:某二叉树中度为2的结点有18个,则叶子结点有 个。

(19)。

如上图所示,二叉树第4层有24-1=8个结点(性质1);深度为4的该二叉树最多有24-1=15个结点(性质2)。

完全二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。

如下图,如果把10移到右侧也不算完全二叉树,必须保持左侧相对完整。

满二叉树:出最后一层叶子结点外,每一层上所有结点都有两个子结点。

在满二叉树中,每一层的结点数都达到最大值。

二叉树通常采用链式存储结构,每个存储结点由两部分组成:数据域和指针域。

其中指针域有两个:左指针域和右指针域。

BT 指针称为二叉链表的头指针,用于指向根结点。

二叉树存储结点结构:Lchild Value Rchildi指向左子结点的指针域 数据域 指向左子结点的指针域考点14:二叉树的遍历二叉树的遍历:不重复的访问二叉树中的所有结点。

【总原则:先左后右】● 前序遍历(DLR ):根-左-右 以右图为例,访问顺序为:FCADBEGHP● 中序遍历(LDR ):左-根-右 以右图为例,遍历顺序为:ACBDFEHGP● 后序遍历(LRD ):左-右-根 以右图为例,遍历顺序为:ABDCHPGEF(注:所谓的前中后遍历是根据访问根的顺序决定的;遍历左右子树时,仍采用以上原则)宝宝定理:对于完全二叉树而言➢ 如果它的结点个数为偶数n ,则该二叉树中:叶子结点个数=非叶子结点个数=n/2➢ 如果它的结点个数为奇数m ,则该二叉树中:叶子结点个数=非叶子结点个数+1=(m+1)/2(即叶子结点个数比非叶子结点个数多一个)查找技术:根据给定值,在查找表中确定一个其关键字等于给定值的数据元素。

● 查找结果:1.查找成功:找到;2.查找不成功:没找到● 平均查找长度:查找过程中关键字和给定值进行比较的平均次数。

考点15:顺序查找➢顺序查找的基本思想:从表中的第一个元素开始,将给定值与表中逐个元素的关键字进行比较,直到两者相符,查到所需元素为止。

否则就是查找不成功,表中无要找元素。

➢平均要与表中一半以上元素进行比较,最坏情况下需要比较全部元素n次。

➢以下两种情况下只能采用顺序查找:1.如果线性表是无序表,则只能采用顺序查找。

2.即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。

考点16:二分法查找➢思想:先确定待查找记录所在范围,然后逐步缩小范围,直到找到或确认找不到该记录为止。

➢前提:必须在具有顺序存储结构的有序表中进行。

➢特点:比顺序查找方法效率更高。

最坏情况下,需要比较log2 n次。

n指线性表长度二分法举例:在下图长度为11的线性表中查找22过程1 2 3 4 5 6 7 8 9 10 11如上图所示:在上述顺序存储结构的有序表中,low指针指向最小元素7,high指针指向最大元素94,mid指针指向中间元素56。

用中间元素56跟目标元素22比可知22一定在56左侧。

(a)如此,我们把high指针移到56左侧的最大位置40,low指针不动,mid指针重新设定为小数据表的中间位置,即元素18所在位置,再用18与22进行比较可知22在18右侧。

(b)如此,我们将low指针移到18右侧的最小结点22处,high指针不动。

此时Mid指针指向中间偏左位置指向22,在进行比较,找到。

●交换类排序法:指借助数据元素的交换来进行排序的一种方法,主包括冒泡排序法和快速排序法。

➢冒泡排序法:最简单的一种交换类排序方法,在数据元素的序列中,对于某个元素,如果其后存在一个元素小于它,则称之为存在一个逆序。

相关主题