全国计算机二级公共基础知识--复习.doc
《全国计算机二级公共基础知识--复习.doc》由会员分享,可在线阅读,更多相关《全国计算机二级公共基础知识--复习.doc(32页珍藏版)》请在咨信网上搜索。
1、(word完整版)全国计算机二级公共基础知识-复习全国计算机二级公共基础知识一、数据结构与算法数据结构指的是数据之间的相互关系,即数据的组织形式。数据结构用来反映一个数据的内部构成,即一个数据由哪些成分构成、以什么方式构成、呈现什么样的结构。数据结构有逻辑上的数据结构和物理上的数据结构之分.逻辑上的数据结构反映数据之间的逻辑关系,而物理上的数据结构反映数据在计算机内部的存储安排。数据结构是数据存在的形式.算法是解题的步骤,是指令的有限序列。它们规定了解决某一特定类型问题的一系列运算,是对解题方案的准确与完整的描述。一个问题的解决方案要以算法为基础。1.1 概念介绍 算法的时间复杂度:算法的时间
2、复杂度是指执行算法所需要的计算工作量.算法的工作量用算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数,即 算法的工作量=f(n)其中n是问题的规模。 例如,两个n阶矩阵相乘所需要的基本运算(即两个实数的乘法)次数为n3,即计算工作量为n3,也就是时间复杂度为n3。 算法的空间复杂度:算法的空间复杂度一般是指执行这个算法所需要的内存空间。数据的逻辑结构数据元素相互之间的关系,称为结构.数据的逻辑结构:是指反映数据元素之间逻辑关系的数据结构。数据的存储结构数据的存储结构:是数据的逻辑结构在计算机存储空间中的存放形式。也称数据的物理结构。各数据元素在计算机存储空间中的位置关
3、系与它们的逻辑关系不一定是相同的.同一种数据的逻辑结构可以根据需要表示成任意一种或几种不同的存储结构.数据的顺序存储方式:是将逻辑上相邻的结点存储在物理位置上亦相邻的存储单元里。也就是将所有存储结点相继存入在一个连续相邻的存储区里。数据的链式存储方式:是在存储每个结点信息的同时,增加一个指针来表示结点间的逻辑关系。该方式不要求逻辑上相邻结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。因此,链式存储结构中的每个结点都由两部分组成:一部分用于存储结点本身的信息,称为数据域;另一部分用于存储该结点的后继结点(或前驱结点)的存储单元地址,称为指针域.指针域可以包含一个或多个指针,这由
4、结点之间的关系所决定。线性结构和非线性结构如果在一个线性结构中,一个数据元素都没有,则称该数据结构为空数据结构。线性结构的逻辑特征:在一个非空的数据结构中,除第一个数据元素只有一个后继没有前驱、最后一个数据元素只有一个前驱没有后继外,其他的每一个数据元素仅有一个前驱和一个后继.线性结构也称为线性表。注:某个元素直接相邻的前一个元素称为此元素的前驱、直接相邻的后一个元素称为此元素的后继。非线性结构的逻辑特征:在一个非空的数据结构中,某数据元素可能有多于一个前驱或后继。如树型结构等。习题:(一)选择题(单选)1. 算法的时间复杂度是指(D)A) 算法的执行时间B) 算法所处理的数据量C) 算法程序
5、中的语句或指令条数D) 算法在执行过程中所需要的基本运算次数1。2线性表线性表是由同一类型的数据元素构成的一种线性的数据结构.是一种最基本、最常用的数据结构。线性表常用的存储方式有两种:顺序存储方式和链接存储方式.线性表的数学定义:L=(a1,a2,a3,an)说明:线性表是具有相同类型的n(n0)个数据元素组成的有限序列。L:为表的名称。ai(i=1,2, ,n):为表的元素,也称为线性表中的一个结点。它可以是一个数、一个字符、一个字符串,也可以是一条记录,还可以是复杂的数据对象。a1是a2的前驱、a2是a1的后继, a2是a3的前驱、a3是a2的后继,,依次类推。n:为线性表的长度(元素个
6、数),当n=0时称线性表为空表。线性表的特点:在非空的线性表中:存在唯一的一个“第一个元素”(根结点).存在唯一的一个“最后一个元素”(终端结点)。除第一个元素外,其他的元素均有唯一的前驱。除最后一个元素外,其他的元素均有唯一的后继。1。3栈和队列栈和队列本质上也是线性表,只是它们的操作受到了限制。1。3。1栈栈是限定仅在表尾进行插入和删除操作的线性表。表尾称为栈顶(top),表头称为栈底(bottom)。栈这种数据结构,类似于子弹夹,底端是封闭的,最后压入的子弹总是最先被弹出,最先压入的子弹只能最后被弹出.栈顶元素总是最后被插入的元素,从而也是最先能被删除的元素;栈底元素总是最先被插入的元素
7、,从而也是最后能被删除的元素.即栈是按照“先进后出”或“后进先出”的原则组织数据的。因此,栈也被称为“先进后出”表或“后进先出”表。由此可以看出,栈具有记忆作用。1。3。2队列队列是指只允许在表的一端插入元素、在另一端删除元素的线性表.允许插入的一端称为队尾(rear),允许删除的一端称为队头(front)。在队列这种数据结构中,最先插入的元素将最先能够被删除,反之最后插入的元素将最后才能被删除。因此,队列又称为“先进先出”或“后进后出”的线性表。1。4树和二叉树1.4。1树树形结构是数据结构中一种很重要的非线性结构。在树形结构中,所有数据元素之间的关系具有明显的层次特性。树形结构很像自然界中
8、的树,像一棵倒长的树。在现实生活中,能用树形结构表示的例子很多。参见下面的图形:树形结构的基本特征及基本术语:以下图为例:树的根:在树形结构中,没有前驱的结点只有一个,称为树的根结点,简称为树的根。如:上图中的“R.父结点:在树形结构中,每一个结点(除了树的根结点)只有一个前驱,称为父结点.如:上图中的“R是K、P、Q、D的父结点;“N”是X、Y的父结点。子结点:在树形结构中,每个结点可以有多个后继,称为该结点的子结点.如:上图中的K、P、Q、D是“R”的子结点;X、Y是“N”的子结点。叶子结点:在树形结构中,没有后继的结点称为叶子结点,也称终端结点。如:上图中的C、M、F、E、X、G、S、L
9、、Z、A均为叶子结点。结点的度:在树形结构中,一个结点所拥有的后继个数称为该结点的度。如:上图中根结点R的度是4;结点T的度是3;结点P、Q、D、O、Y、W的度都为1。叶子结点的度为0。树的度:在树形结构中,所有结点中的最大的度称为树的度.如:上图中树的度为4,因为结点R的度最大,是4。树的深度:在树形结构中,树的最大层数称为树的深度(或高度)。如:上图中树的深度是5。说明:树形结构具有明显的层次关系,即树是一种层次结构.在树形结构中一般按如下原则分层:1) 根结点在第1层。2) 其余结点的层数等于其父结点的层数加1。子树:在树形结中,以某结点的一个子结点为根构成的树称为该结点的一棵子树。如:
10、上图中,结点R有4棵子树,它们分别以K、P、Q、D为根结点;结点P有1棵子树,其根结点为N;结点T有3棵子树,它们分别以W、Z、A为根结点.在树形结构中,子树间互不相交,叶子结点没有子树。森林:森林是M(M0)棵互不相交的树的集合.删去一棵树的根,就得到一个森林;反之,加上一个结点作树根,森林就变为一棵树。1.4.2二叉树(1) 二叉树的特点 非空二叉树只有一个根结点。 二叉树中的每个结点,最多有两棵子树,分另称为该结点的左子树与右子树。当一个结点即没有左子树也没有右子树时,该结点就是叶子结点。在下面的图中,左面是只有根结点的二叉树,右面是深度为4的二叉树: (2) 满二叉树与完全二叉树1)
11、满二叉树:满二叉树是指除最后一层外,每一层上的所有结点都有两个子结点。就是说,在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第k层上有2i-1(k1)个结点,且深度为k的满二叉树有2k1(k1)个结点.在下图中分别是深度为2、3、4的满二叉树:满二叉树中不存在度数为1的结点,每个分支结点均有两棵深度相同的子树,且叶子结点都在最下一层.2) 完全二叉树:若一棵二叉树最多只有最下面的两层上结点的度数可以小于2,并且最下一层上的所有结点都集中在该层最左边的若干位置上,则此二叉树称为完全二叉树.在下图的4棵二叉树中,分别是深度为3和4的完全二叉树:满二叉树是完全二叉树,完全二叉树不一定是满
12、二叉树.在满二叉树的最下一层上,从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树.在完全二叉树中,若某个结点没有左子结点,则它一定没有右子结点,即该结点必是叶子结点。(3) 二叉树的性质假设定义根结点的层数为1(注意:有些资料中规定根结点的层数为0)。性质1:在二叉树的第i层上,最多有2i1(i1)个结点。性质2:深度为k的二叉树最多有2k-1(k1)个结点。性质3:在任意二叉树中,若度为0的结点(即叶子结点)的个数为n0,度为2的结点的个数为n2,则:n0= n2+1(对于完全二叉树还有如下属性)性质4:具有n个结点的完全二叉树,其深度为log2n+1。注:log2n表示取lo
13、g2n的整数部分.性质5:如果将一棵有n个结点的完全二叉树自顶向下、同一层自左向右连续给结点编号1、2、3、n,则对于任意结点i(1in)有如下结论:1) 如果i=1,此结点为根结点,无前驱(即无父结点);如果i1,则该结点的父结点编号为Int(i/2)。也可表示成i/2,都表示取整数。2)如果2in,则结点i无左子结点,显然也没有右子结点,是叶子结点。如果2in,则结点i的左子结点是编号为2i的结点。3) 如果2i+1n,则结点i无右子结点。如果2i+1n,则结点i的右子结点的编号为2i+1。(4) 二叉树的遍历二叉树的遍历就是遵从某种次序,访问二叉树中的所有结点,使得每个结点仅被访问一次.
14、一棵非空二叉树是由根结点、左子树和右子树三部分组成。因此遍历一棵非空二叉树的问题就可以分解为三项“子任条”: 访问根结点(假设用D表示)。 遍历左子树(假设用L表示)。 遍历右子树(假设用R表示)。在遍历二叉树的过程中,一般先遍历左子树,然后再遍历右子树。在先左后右的原则下,根据访问根结点的次序,二叉树的遍历可分为三种:前序遍历(DLR)、中序遍历(LDR)、后序遍历(LRD)。 以下图中的二叉树为例: 前序遍历(DLR): 首先访问根结点,然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问子树的根结点,然后遍历其左子树,最后遍历其右子树。即,前序遍历是指访问所有的根结点(包括子树
15、的根结点)都在遍历其左、右子树之前。 前序遍历的操作: 若二叉树为空,则结束反返回.否则: 访问根结点 前序遍历左子树 前序遍历右子树如,对上图中的二叉树进行前序遍历的结果是:F C A D B E G H P 中序遍历(LDR): 首先遍历左子树,然后访问根结点,最后遍历右子树。在遍历左、右子树时,仍然先遍历其左子树,然后访问子树的根结点,最后遍历其右子树.即,中序遍历是指访问所有的根结点(包括子树的根结点)都在遍历其左子树之后、在遍历其右子树之前。 中序遍历的操作: 若二叉树为空,则结束反返回。否则: 中序遍历左子树 访问根结点 中序遍历右子树如,对上图中的二叉树进行中序遍历的结果是:A
16、C B D F E H G P 后序遍历(LRD): 首先遍历左子树,然后遍历右子树,最后访问根结点。在遍历左、右子树时,仍然先遍历其左子树,然后遍历其右子树,最后访问子树的根结点。即,后序遍历是指访问所有的根结点(包括子树的根结点)都在遍历其左、右子树之后。 后序遍历的操作: 若二叉树为空,则结束反返回。否则: 后序遍历左子树 后序遍历右子树 访问根结点如,对上图中的二叉树进行后序遍历的结果是:A B D C H P G E F1.5查找查找又称检索。查找是指在一个给定的数据结构中查找某个指定的元素。通常,根据不同的数据结构,应采用不同的查找方法。1。5.1 顺序查找顺序查找又称顺序搜索或线
17、性查找.顺序查找一般是指在线性表中查找指定的元素。顺序查找的基本思想:在n个结点组成的线性表中,从线性表的一端开始,依次将线性表中的元素与被查元素进行比较,若相等则表示找到,即查找成功;若线性表中所有的元素都与被查元素进行了比较但都不相等,则表示线性表中没有要找的元素,即查找失败。在顺序查找中,查找成功时最多需要比较n次、最少比较1次、平均比较次数约为表长的一半。查找失败时比较n+1次.顺序查找的时间复杂度为O(n)。对于无序表(即表中的元素的排列是无序的)和链式存储结构的线性表(有序的和无序的),只能用顺序查找。顺序查找的优点:算法简单而适用范围广。对表中元素的排列次序无要求,既可以是按关键
18、字排列的有序表,也可以是无序表;对表的存储结构也无任何要求,既适用于顺序存储的顺序表,也适用于链接存储的链表. 顺序查找的缺点: 查找效率低,平均查找长度较大。当n很大时不宜采用顺序查找.1.5.2 二分查找二分查找又称折半查找。它是一种查找效率较高的查找方法.该方法只适用于顺序存储结构的有序表。通常是指有序表中的元素按值升序排列(非递减有序排列).二分查找不能用于链式存储结构的线性表. 二分查找的基本思想:参见“C语言程序设计”或“VB程序设计课件的相应内容动画。 对于长度为n的有序线性表,查找成功时最多需要比较log2(n+1)次、最少比较1次、平均查找长度近似log2n。当查找失败时,比
19、较log2n或log2(n+1)次。 不管二分查找成功与否,其时间复杂度均为O(log2n)。 二分查找的最坏性能和平均性能相当接近。1.6 排序 排序就是将文件中的记录进行整理,使之按照关键字进行递增或递减的顺序排列起来,成为一个有序序列的过程。在本节所介绍的排序方法中,其排序的对象一般认为是顺序存储的线性表,在程序设计语言中就是一维数组。 这里的排序算法,都是针对升序排序.1。6.1 交换排序 交换排序是两两比较待排序记录的关键字,若发现两个记录关键字的次序相反时即进行交换,直到没有反序的记录为止。下面介绍两种常用的交换排序。(1) 冒泡排序冒泡排序的基本思想:参见“C语言程序设计”或“V
20、B程序设计”课件的相应内容动画. 对于长度为n的线性表,在最坏情况下,冒泡排序需要经过n/2遍的扫描,比较次数为n(n-1)/2. 冒泡排序算法的平均时间复杂度为O(n2),空间复杂度为O(1)。(2) 快速排序快速排序的基本思想: 参见下图: 从线性表中选取一个元素,设为T,将线性表后面小于T的元素移到前面,将线性表前面大于T的元素移到后面,结果就把线性表分成了两部分(称为两个子表),T插入到其分界线的位置处,这个过程称为线性表的分割。通过对线性表的一次分割,就以T为分界线,将线性表分成了前后两个子表,且前面子表中的所有元素均不大于T,后面子表中的所有元素均不小于T。 如果对分割后的各子表再
21、按上述原则进行分割,并且这种分割过程可以一直做下去,随着对各子表不断地进行分割,划分出的子表会越来越多(一次只能对一个子表进行再分割处理),直到所有子表中的元素都排好序为止,则此时的线性表就变成了有序表. 对于长度为n的线性表:在最坏情况下,快速排序比较次数为n(n-1)/2。算法的时间复杂度为O(n2),空间复杂度为O(n)。 在最好情况下,快速排序算法的时间复杂度为O(nlog2n),空间复杂度为O(log2n).快速排序算法的平均时间复杂度是O(nlog2n),平均比较次数不大于(n+1)log2n1。6。2 插入排序 插入排序是每次将一个待排序的记录按其关键字大小,插入到前面已排好的序
22、列中的适当位置,直到全部记录插入为止。(1) 直接插入排序 快速排序的基本思想:请查看相关资料。 对于长度为n的线性表:在最坏情况下,直接插入排序比较次数为n(n-1)/2。算法的时间复杂度为O(n2)。(2) 希尔排序 希尔排序的基本思想:请查看相关资料。 对于长度为n的线性表:在最坏情况下希尔排序比较次数为O(n1。5)。1.6。3 选择排序 选择排序的基本思想是:每一遍在n-i+1(i=1,2,n-1)个待排序记录中选取关键字最小的记录作为有序序列中第i个记录,直到全部记录排完为止。(1) 直接选择排序 选择排序的基本思想:参见“C语言程序设计”或“VB程序设计课件的相应内容动画. 在最
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全国计算机 二级 公共 基础知识 复习
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【二***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【二***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。