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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机等级考试培训公共基础算法与数据结构,计算机基础教研室,内容提要,算法的基本概念,数据结构的基本概念,线性表,栈和队列,线性链表,二叉树极其遍历,查找技术,排序技术,算法的基本概念,算法,对解决问题方案的准确而完整的描述（解决问题的操作步骤），流程图、,N-S,图、文字说明和伪代码。,对数据对象的运算和操作。包括算数运算、逻辑运算、关系运算和数据赋值传输。,运算和操作的控制结构。确定运算和操作的执行顺序，有三种基本结构：顺序结构、选择结构和循环结构，,C,和,VF,都支持这三种结构。,特征,可行性、确切性和有穷性（解密算法）,算法的基本概念,算法的复杂度,运行算法所消耗的计算机资源量的多少,时间复杂度：执行算法所需要的计算工作量，即算法执行的基本运算次数，特别提醒，它和算法执行的时间长短是无关的，复杂度,=,f(n,),，一般考虑平局复杂度和最坏情况复杂度。,（,1,）,s=0 O(1),(2),for(i,=1;i=0),个数据元素构成的有限序列，表中除第一个元素，有且只有一个前件，除最后一个元素，有且只有一个后件。表示为,(a,1,a,2,a,i-1,a,i,a,n,),。,基本特征有：,元素个数,n,表长度，,n=0,空表,1,i0),个结点的有限集,T,，,其中：,有且仅有一个特定的结点，称为树的,根,(root),当,n1,时，其余结点可分为,m(m,0),个,互不相交,的有限集,T,1,T,2,T,m,，,其中每一个集合本身又是一棵树，称为根的,子树,(,subtree,),特点,：,树中至少有一个结点,根,树中各子树是互不相交的集合,树的基本概念,结点,(node),表示树中的元素，包括数据项及若干指向其子树的分支,根（,root),无前件的节点,度,一个节点拥有的后件个数，树中节点的最大度数,叶子,(leaf),度为,0,的结点,深度,树的层次数,A,B,C,D,E,F,G,H,I,J,K,L,M,二叉树,二叉树,二叉树是,n(n,0),个结点的有限集，它或为空树(,n=0),，,或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成,基本性质：在二叉树的,K,层上，最多有,2,K-1,(K=1),个节点,深度为,K,的二叉树中，最多有,2,K,-1,个节点,叶子节点比度数为,2,的节点多,1,个,完全二叉树：除最后一层外，每层上的节点数达到最大值，最后一层上只缺少右边若干节点,满二叉树：每层的节点数都达到其最大值，,i,层上的节点数为,2,i-1,二叉树的遍历,先序遍历：先访问根结点,然后分别先序遍历左子树、右子树,中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树,后序遍历：先后序遍历左、右子树，然后访问根结点,按层次遍历：从上到下、从左到右访问各结点,-,+,/,a,*,b,-,e,f,c,d,查找,查找,在某数据结构中，找出满足指定条件的元素,顺序查找,从线性表的第一个元素开始，逐一的将表中的每个元素与查找元素比较，若成功，便停止，若到表尾都未找出，查找失败,若有,n,个元素，平均查找次数为,n/2,，时间复杂度为,O(n,),，一般用于无序表和链式存储结构的查找,二分查找（折半查找）,要求查找的数据结构必须是有序的顺序结构，对于元素个数为,n,的有序表，查找过程是：先找出中间元素，若匹配，查找成功；若比中间值大，则丢掉前半部分，在后半部继续二分查找；若比中间值小，则丢掉后半部分，在前半部分继续二分查找，时间复杂度为,O(lon,2,n),比顺序查找少。,排序,排序,将一个无序序列整理成按值非递减排列的有序序列,方法很多，主要的方法有：,冒泡排序法：比较相邻元素，若逆序，则交换，,O(n,2,),n(n-1)/2,快速排序法：指定一个,K,元素，,HIGH,从后向前扫描，遇见第一个小于,K,的元素，和,K,元素交换，接着,LOW,从前往后扫描，遇见第一个大于,K,的元素，和,K,交换，直到,H,和,L,相等，,O(nlon,2,n),n,2,简单插入排序法：将某一元素插入到前面已经排好的有序子表中,O(n,2,),n(n-1)/2,希尔排序法：将元素分为若干组，组内简单插入排序，缩小分组，再继续，直到一个元素一组,简单选择排序法：在元素中选择最小的，和第一个元素交换，然后在剩下的,n-1,个元素中，重复此操作,O(n,2,),n(n-1)/2,排序效率的评估,很难说哪种排序是最好的，各种排序方式都有自己的优缺点,考虑的因素有：元素个数,n,的长度；稳定性要求；存储辅助空间的大小；数据元素本身的大小等等。,若,n,比较小，采用直接插入排序和选择排序,若元素已经基本有序，只有个别的逆序，采用简单插入排序和冒泡排序,若,n,比较大，采用快速排序和堆排序,稳定性：,选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。,思考题目,下列叙述中正确的是,A,算法的效率只与问题的规模有关，而与数据的存储结构无关,B,算法的时间复杂度是指执行算法所需要的计算工作量,C,数据的逻辑结构与存储结构是一一对应的,D,算法的时间复杂度与空间复杂度一定相关,下列对列的叙述正确的是,A,队列属于非线性表,B,队列按“先进后出”原则组织数据,C,队列在队尾删除数据,D,队列按“先进先出”原则组织数据,某二叉树中有,n,个度为,2,的结点，则该二叉树中的叶子结点为,A,n+1 B,n-1 C,2n D,n/2,下列叙述中，不符合良好程序设计风格要求的是,A,程序的效率第一，清晰第二,B,程序的可读性好,C,程序中要有必要的注释,D,输入数据前要有提示信息,下列叙述中正确的是,A,程序执行的效率与数据的存储结构密切相关,B,程序执行的效率只取决于程序的控制结构,C,程序执行的效率只取决于所处理的数据量,D,以上三种说法都不对,思考题目,下列叙述中正确的是,A,数据的逻辑结构与存储结构必定是一一对应的,B,由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构,C,程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构,D,以上三种说法都不对,冒泡排序在最坏情况下的比较次数是,A,(n,1)/2 B,nlog2 n C,n(n,1)/2 D,/2,一棵二叉树中共有,70,个叶子结点与,80,个度为,1,的结点，则该二叉树中的总结点数为,A,219 B,221 C,229 D,231,程序流程图中带有箭头的线段表示的是：,A,图元关系,B,数据流,C,控制流,D,调用关系,算法的有穷性是指,A,算法程序的运行时间是有限的,B,算法程序所处理的数据量是有限的,C,算法程序的长度是有限的,D,算法只能被有限的用户使用,思考题目,对长度为,n,的线性表排序，在最坏情况下，比较次数不是,n(n-1)/2,的排序方法是,A,快速排序,B,冒泡排序,C,直线插入排序,D,堆排序,下列关于栈的叙述正确的是,A,栈按“先进先出”组织数据,B,栈按“先进后出”组织数据,C,只能在栈底插入数据,D,不能删除数据,一个栈的初始状态为空。现将元素,1,、,2,、,3,、,4,、,5,、,A,、,B,、,C,、,D,、,E,依次入栈，然后再依次出栈，则元素出栈的顺序是,A,）,12345ABCDE B,）,EDCBA54321 C)ABCDE12345 D,）,54321EDCBA,下列叙述中正确的是,A,）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构,B,）在循环队列中，只需要队头指针就能反应队列中元素的动态变化情况,C,）在循环队列中，只需要队尾指针就能反应队列中元素的动态变化情况,D,）循环队列中元素的个数是由队头和队尾指针共同决定,在长度为,n,的有序线性表中进行二分查找，最坏情况下需要比较的次数是,A,）,O(N)B,）,O(n2)C,）,O(log2n)D,）,O(n,log2n),思考题目,下列叙述中正确的是,A,）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的,B,）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构,C,）顺序存储结构能存储有序表，链式存储结构不能存储有序表,D,）链式存储结构比顺序存储结构节省存储空间,以下数据结构中不属于线性表的结构是,A),队列,B),链表,C),二叉树,D),栈,对如下所示的二叉树进行遍历,A,B,C,D,E,F,G,