计算机等级考试培训公共基础(一)

《计算机等级考试培训公共基础(一)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机等级考试培训公共基础算法与数据结构计算机基础教研室内容提要算法的基本概念数据结构的基本概念线性表栈和队列线性链表二叉树极其遍历查找技术排序技术算法的基本概念算法——对解决问题方案的准确而完整的描述（解决问题的操作步骤），流程图、N-S图、文字说明和伪代码。对数据对象的运算和操作。包括算数运算、逻辑运算、关系运算和数据赋值传输。运算和操作的控制结构。确定运算和操作的执行顺序，有三种基本结构：顺序结构、选择结构和循环结构，C和VF都支持这三种结构。特征——可行性、确切性和有穷性（解密算法）算法

2、的基本概念算法的复杂度——运行算法所消耗的计算机资源量的多少时间复杂度：执行算法所需要的计算工作量，即算法执行的基本运算次数，特别提醒，它和算法执行的时间长短是无关的，复杂度=f(n)，一般考虑平局复杂度和最坏情况复杂度。（1）s=0O(1)(2)for(i=1;i<=n;i++)s=s+IO(n)空间复杂度：执行一个算法所需要的内存空间，包括三个方面：数据占用空间、程序占用空间、额外空间占用。数据结构的基本概念数据结构——研究非数值计算的程序设计问题中的数据以及它们之间的关系和运算逻辑关系（结构

3、）：数据元素本身和它们的前后件关系物理关系（结构）：逻辑结构在计算机存储空间的存储方式，顺序结构和链式结构运算：实现的处理方法线性表线性表——n(n>=0)个数据元素构成的有限序列，表中除第一个元素，有且只有一个前件，除最后一个元素，有且只有一个后件。表示为(a1,a2,…ai-1,ai,…,an)。基本特征有：元素个数n—表长度，n=0空表1

4、（数组）链式存储结构：用节点来存储数据和逻辑相邻数据的地址，逻辑上相邻，物理上未必相邻（线性链表，双向链表,循环链表）栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表栈（stack）——限定在表的一端插入和删除元素的线性表，遵循“先进后出，后进先出”原则，可以逆序改变元素的顺序出栈操作和进栈操作ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)栈和队列队列——限定只能在表的一端进行插入，在表的另一端进行删除的线性表，遵循“先进先出，后进后出”原则，入队操作和进队操作

5、。a1a2a3…………………….an入队出队headtail队列Q=(a1,a2,……,an)树的基本概念定义：树(tree)是n(n>0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根(root)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点：树中至少有一个结点——根树中各子树是互不相交的集合树的基本概念结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支根（root)——

6、无前件的节点度——一个节点拥有的后件个数，树中节点的最大度数叶子(leaf)——度为0的结点深度——树的层次数ABCDEFGHIJKLM二叉树二叉树——二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成基本性质：在二叉树的K层上，最多有2K-1(K>=1)个节点深度为K的二叉树中，最多有2K-1个节点叶子节点比度数为2的节点多1个完全二叉树：除最后一层外，每层上的节点数达到最大值，最后一层上只缺少右边若干节点满二叉树：每层的节

7、点数都达到其最大值，i层上的节点数为2i-1二叉树的遍历先序遍历：先访问根结点,然后分别先序遍历左子树、右子树中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点按层次遍历：从上到下、从左到右访问各结点-+/a*b-efcd查找查找——在某数据结构中，找出满足指定条件的元素顺序查找从线性表的第一个元素开始，逐一的将表中的每个元素与查找元素比较，若成功，便停止，若到表尾都未找出，查找失败若有n个元素，平均查找次数为n/2，时间复杂度为O(n)，

8、一般用于无序表和链式存储结构的查找二分查找（折半查找）要求查找的数据结构必须是有序的顺序结构，对于元素个数为n的有序表，查找过程是：先找出中间元素，若匹配，查找成功；若比中间值大，则丢掉前半部分，在后半部继续二分查找；若比中间值小，则丢掉后半部分，在前半部分继续二分查找，时间复杂度为O(lon2n),比顺序查找少。排序排序——将一个无序序列整理成按值非递减排列的有序序列方法很多，主要的方法有：冒泡排序法：比较相邻元素，若逆序，则交换，O(n2),n(n-1)/2快速排序法：指定一个