计算机二级公共基础知识.pdf
《计算机二级公共基础知识.pdf》由会员分享,可在线阅读,更多相关《计算机二级公共基础知识.pdf(86页珍藏版)》请在咨信网上搜索。
1、1.1算法考点1算法的基本概念计算机解题的过程实际上是在实施某种算法,这种算法称为计算 机算法。算法(algorit h m)是一组严谨地定义运算顺序的规则,并且每一个 规则都是有效的,同时是明确的;此顺序将在有限的次数后终止。算 法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每 一条指令表示一个或多个操作。1算法的基本特征(1)可行性(effectiveness):针对实际问题而设计的算法,执行后能够得到满意的结果。(2)确定性(definiteness):算法中的每一个步骤都必须有明 确的定义,不允许有模棱两可的解释和多义性。(3)有穷性(finiteness):算法必需在有限
2、时间内做完,即算 法必需能在执行有限个步骤之后终止。(4)拥有足够的情报:要使算法有效必需为算法提供足够的 情报当算法拥有足够的情报时,此算法才最有效的;而当提供的情报 不够时,算法可能无效。2算法的基本要素(1)算法中对数据的运算和操作:每个算法实际上是按解题 要求从环境能进行的所有操作中选择合适的操作所组成的一组指令 序列。计算机可以执行的基本操作是以指令的形式描述的。一个计算机 系统能执行的所有指令的集合,称为该计算机系统的指令系统。计算 机程序就是按解题要求从计算机指令系统中选择合适的指令所组成 的指令序列在一般的计算机系统中,基本的运算和操作有以下4类:算术运算:主要包括加、减、乘、
3、除等运算;逻辑运算:主要包括“与”、“或”、“非”等运算;关系运算:主要包括“大于”、“小于”、“等于”、“不等于”等运算;数据传输:主要包括赋值、输入、输出等操作。(2)算法的控制结构:一个算法的功能不仅仅取决于所选用 的操作,而且还与各操作之间的执行顺序有关。算法中各操作之间的 执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架,它不仅决定了算法中各 操作的执行顺序,而且也直接反映了算法的设计是否符合结构化原 则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描 述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结 构组合而成。(3)算法设计的基本方法计算机算
4、法不同于人工处理的方法,下面是工程上常用的几种算 法设计,在实际应用时,各种方法之间往往存在着一定的联系。(1)列举法列举法是计算机算法中的一个基础算法。列举法的基本思想是,根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验 哪些是需要的,哪些是不需要的。列举法的特点是算法比较简单。但当列举的可能情况较多时,执 行列举算法的工作量将会很大。因此,在用列举法设计算法时,使方 案优化,尽量减少运算工作量,是应该重点注意的。(2)归纳法归纳法的基本思想是,通过列举少量的特殊情况,经过分析,最 后找出一般的关系。从本质上讲,归纳就是通过观察一些简单而特殊 的情况,最后总结出一般性的结论。(3
5、)递推递推是指从已知的初始条件出发,逐次推出所要求的各中间结 果和最后结果。其中初始条件或是问题本身已经给定,或是通过对问 题的分析与化简而确定。递推本质上也属于归纳法,工程上许多递推 关系式实际上是通过对实际问题的分析与归纳而得到的,因此,递推 关系式往往是归纳的结果。对于数值型的递推算法必须要注意数值计 算的稳定性问题。(4)递归人们在解决一些复杂问题时,为了降低问题的复杂程度(如问题 的规模等),一般总是将问题逐层分解,最后归结为一些最简单的问 题。这种将问题逐层分解的过程,实际上并没有对问题进行求解,而 只是当解决了最后那些最简单的问题后,再沿着原来分解的逆过程逐 步进行综合,这就是递
6、归的基本思想。递归分为直接递归与间接递归两种。(5)减半递推技术实际问题的复杂程度往往与问题的规模有着密切的联系。因此,利用分治法解决这类实际问题是有效的。工程上常用的分治法是减半 递推技术。所谓“减半”,是指将问题的规模减半,而问题的性质不变;所 谓“递推”,是指重复“减半”的过程。(6)回溯法在工程上,有些实际问题很难归纳出一组简单的递推公式或直观 的求解步骤,并且也不能进行无限的列举。对于这类问题,一种有效 的方法是“试通过对问题的分析,找出一个解决问题的线索,然 后沿着这个线索逐步试探,若试探成功,就得到问题的解,若试探失 败,就逐步回退,换别的路线再逐步试探。4算法设计的要求通常一个
7、好的算法应达到如下目标:正确性(correct ness)正确性大体可以分为以下4个层次:程序不含语法错误;程序对于几组输入数据能够得出满足规格说明要求的结 果;程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果;程序对于一切合法的输入数据都能产生满足规格说明要求的结果。(2)可读性(readabilit y)算法主要是为了方便入的阅读与交流,其次才是其执行。可读性 好有助于用户对算法的理解;晦涩难懂的程序易于隐藏较多错误,难 以调试和修改。(3)健壮性(robustness)当输入数据非法时,算法也能适当地做出反应或进行处理,而不会产生莫名其妙的输出结果。(
8、4)效率与低存储量需求效率指的是程序执行时,对于同一个问题如果有多个算法可 以解决,执行时间短的算法效率高;存储量需求指算法执行过程中所 需要的最大存储空间考点2算法的复杂度1算法的时间复杂度算法的时间复杂度,是指执行算法所需要的计算工作量。同 一个算法用不同的语言实现,或者用不同的编译程序进行编译,或者 在不同的计算机上运行,效率均不同。这表明使用绝对的时间单位衡 量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素,可以认为一个特定算法“运行工作量”的大小,只依赖于问题的规模(通常用整数n表示),它是问题的规模函数。即算法的工作量二f(n)例如,在NXN矩阵相乘的算法中,整个算法的
9、执行时间与该基 本操作(乘法)重复执行的次数n3成正比,也就是时间复杂度为n3,即f(n)=0(n3)在有的情况下,算法中的基本操作重复执行的次数还随问题的输 入数据集不同而不同。例如在起泡排序的算法中,当要排序的数组a 初始序列为自小至大有序时,基本操作的执行次数为氏当初始序列为 自大至小有序时,基本操作的执行次数为n(n-1)/20对这类算法 的分析,可以采用以下两种方法来分析。(1)平均性态(Average Beh avior)所谓平均性态是指各种特定输入下的基本运算次数的加权平均 值来度量算法的工作量。设X是所有可能输入中的某个特定输入,p(x)是X出现的概率(即 输入为X的概率),t
10、(x)是算法在输入为X时所执行的基本运算次数,则算法的平均性态定义为其中Dn表示当规模为n时,算法执行的所有可能输入的集合。(2)最坏情况复杂性(Worst-case Complexity)所谓最坏情况分析,是指在规模为n时,算法所执行的基本运算 的最大次数。2算法的空间复杂度算法的空间复杂度是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初 始数据所占的存储空间以及算法执行中所需要的额外空间。其中额外 空间包括算法程序执行过程中的工作单元以及某种数据结构所需要 的附加存储空间。如果额外空间量相对于问题规模来说是常数,则称 该算法是原地(in place
11、)工作的。在许多实际问题中,为了减少算法 所占的存储空间,通常采用压缩存储技术,以便尽量减少不必要的额 外空间。考点3数据结构的定义数据结构(data structure)是指相互之间存在一种或多种特定关 系的数据元素的集合,即数据的组织形式。数据结构作为计算机的一门学科,主要研究和讨论以下三个方 面:数据集合中个数据元素之间所固有的逻辑关系,即数据的 逻辑结构;(2)在对数据元素进行处理时,各数据元素在计算机中的存 储关系,即数据的存储结构;(3)对各种数据结构进行的运算。讨论以上问题的日的是为了提高数据处理的效率,所谓提高数 据处理的效率有两个方面:提高数据处理的速度;(2)尽量节省在数据
12、处理过程中所占用的计算机存储空间。数据(data):是对客观事物的符号表示,在计算机科学中是指所 有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(data element):是数据的基本单位,在计算机程序中 通常作为一个整体进行考虑和处理。数据对象(data object):是性质相同的数据元素的集合,是数 据的一个子集。在一般情况下,在具有相同特征的数据元素集合中,各个数据元 素之间存在有某种关系(即连续),这种关系反映了该集合中的数据元 素所固有的一种结构。在数据处理领域中,通常把数据元素之间这种 固有的关系简单地用前后件关系(或直接前驱与直接后继关系)来描 述。前后件关系是数
13、据元素之间的一个基本关系,但前后件关系所表 示的实际意义随具体对象的不同而不同。一般来说,数据元素之间的 任何关系都可以用前后件关系来描述。1数据的逻辑结构数据结构是指反映数据元素之间的关系的数据元素集合的表示。更通俗地说,数据结构是指带有结构的数据元素的集合。所谓结构实 际上就是指数据元素之间的前后件关系。一个数据结构应包含以下两方面信息:(1)表示数据元素的信息;(2)表示各数据元素之间的前后件关系。数据的逻辑结果是对数据元素之间的逻辑关系的描述。它可以用 一嘎数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构包括集合、线性结构、树型结构和图形结构四 种。线性结构:数据元素之间
14、构成一种顺序的线性关系。树型结构:数据元素之间形成一种树型的关系数据的逻辑结构有两个要素:一是数据元素的集合,通常记为 D;二是D上的关系,它反映了数据元素之间的前后件关系,通常记 为R。一个数据结构可以表示成B=(C,R)其中B表示数据结构。为了反映D中各元素之间的前后件关系,一般用二元组来表示。例如,复数是一种数据结构,在计算机科学中,复数可取如下定义:B=(C,R)其中,C是含有两个实数的集合cl,c2;R是定义在集合C上 的一种关系,其中有序偶表示cl是复数的实部,c2是复数的虚部。2数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式,称为数据的存 储结构(也称为数据的物理结构)
15、。由于数据元素在计算机存储空间中的位置关系可能与逻辑关系 不同,因此,为了表示存放在计算机存储空间中的各数据元素之间的 逻辑关系(即前后件关系),在数据的存储结构中,不仅要存放各数 据元素的信息,还需要存放各数据元素之间的前后件关系的信息。一种数据的逻辑结构根据需要可以表示成多种存储结构,常用 的结构有顺序、链接、索引等存储结构而采用不同的存储结构,其数 据处理的效率是不同的。因此,在进行数据处理是,选择合适的存储 结构是很重要的。考点4数据结构的图形表示数据结构除了用二元关系表示外,还可以直观地用图形表示。在数据结构的图形表示中,对于数据集合D中的每一个数据元 素用中间标有元素值的方框表示,
16、一般称之为数据结点,并简称为结 点;为了进一步表示各数据元素之间的前后件关系,对于关系R中的 每一个二元组,用一条有向线段从前件结点指向后件结点。在数据结构中,没有前件的结点称为根结点;没有后件的结 点称为终端结点(也称为叶子结点)。一个数据结构中的结点可能是在动态变化的。根据需要或在处理 过程中,可以在一个数据结构中增加一个新结点(称为插入运算),也 可以删除数据结构中的某个结点(称为删除运算)。插入与删除是对数 据结构的两种基本运算。除此之外,对数据结构的运算还有查找、分 类、合并、分解、复制和修改等。考点5线性结构与非线性结构如果在一个数据结构中一个数据元素都没有,则称该数据结构为 空的
17、数据结构。根据数据结构中各数据元素之间前后件关系的复杂程度,一般将 数据结构分为两大类型:线性结构与非线性结构。非空数据结构满足:有且只有一个根结点;(2)每一个结点最多有一个前件,也最多有一个后件。则称该数据结构为线性结构。线性结构又称为线性表。一个线性 表是n个数据元 素的有限序列。至于每个元素的具体含义,在不同 的情况下各不相同,它可以是一个数或一个符号,也可以是一页书,甚至其他更复杂的信息。如果一个数据结构不是线性结构,称之为非 线性结构。线性结构与非线性结构都可以是空的数据结构。对于空的 数据结构,如果对该数据结构的运算是按线性结构的规则来处理的,则属于线性结构;否则属于非线性结构。
18、1.3线性表及顺序存储结构考点6线性表的定义线性表是n(nNO)个元素构成的有限序列(al,a2,,an)。表 中的每一个数据元素,除了第一个外,有且只有一个前件,除了最后 一个外,有且只有一个后件。即线性表是一个空表,或可以表示为(al,a2,,an)其中ai(i=l,2,,n)是属于数据对象的元素,通常也称其为线 性表中的一个结点。其中,每个元素可以简单到是一个字母或是一个数据,也可能是 比较复杂的由多个数据项组成的。在复杂的线性表中,由若干数据项 组成的数据元素称为记录(record),而由多个记录构成的线性表又称 为文件(file)。在非空表中的每个数据元素都有一个确定的位置,如 al
19、是第一个元素,an是最后一个数据元素,ai是第i个数据元素,称i为数据元素ai在线性表中的位序。非空线性表有如下一些结构特 征:(1)有且只有一个根结点al,它无前件;(2)有且只有一个终端结点an,它无后件;(3)除根结点与终端结点外,其他所有结点有且只有一个前件,也 有且只有一个后件。线性表中结点的个数n称为线性表的长度。当 n=0时称为空表。考点7线性表的顺序存储结构线性表的顺序表指的是用一组地址连续的存储单元依次存储线 性表的数据元素。线性表的顺序存储结构具备如下两个基本特征:线性表中的所有元素所占的存储空间是连续的;(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。假设线性
20、表的每个元素需要占用k个存储单元,并以所占的存储 位置ADR(ai+l)和第i个数据元素的存储位置ADR(ai)之间满足下列 关系:ADR(ai+l)=ADR(ai)+k线性表第i个元素ai的存储位置为ADR(ai)=ADR(a l)+(i-l)Xk式中ADR(ai)是线性表的第一个数据元素a,的存储位置,通常 称做线性表的起始位置或基址。线性表的这种表示称做线性表的顺序存储结构或顺序映像,这种 存储结构的线性表为顺序表。表中每一个元素的存储位置都和线性表 的起始位置相差一个和数据元素在线性表中的位序成正比例的常数。如图1-4所示。由此只要确定了存储线性表的起始位置,线性表中任 一数据元素都可
21、以随机存取,所以线性表的顺序存储结构是一种随机 存取的存储结构。在程序设计语言中,通常定义一个一维数组来表示线性表的顺序存储 空间。在用一维数组存放线性表时,该一维数组的长度通常要定义得 比线性表的实际长度大一些,以便对线性表进行各种运算,特别是插 入运算。在线性表的顺序存储结构下,可以对线性表做以下运算:在线性表的指定位置处加入一个新的元素(即线性表的插入);(2)在线性表中删除指定的元素(即线性表的删除);(3)在线性表中查找某个(或某些)特定的元素(即线性表的查找);(4)对线性表中的元素进行整序(即线性表的排序);(5)按要求将一个线性表分解成多个线性表(即线性表的分解);(6)按要求
22、将多个线性表合并成一个线性表(即线性表的合并);(7)复制一个线性表(即线性表的复制);(8)逆转一个线性表(即线性表的逆转)等。考点8顺序表的插入运算线性表的插入运算是指在表的第i(lWiWn+l)个位置上,插入一 个新结点x,使长度为n的线性表(al,,ai-1,ai,,an)变成长度为n+1的线性表(al,,ai-1,x,ai,,an)现在分析算法的复杂度。这里的问题规模是表的长度,设它的值 为n。该算法的时间主要花费在循环结点后移语句上,该语句的执行 次数(即移动结点的次数)是n-i+1。由此可看出,所需移动结点的次数 不仅依赖于表的长度,而且还与插入位置有关。当i=n+l时,由于循环
23、变量的终值大于初值,结点后移语句将不 进行;这是最好情况,其时间复杂度0(1);当i=l时,结点后移语句,将循环执行n次,需移动表中所有结 点,这是最坏情况,其时间复杂度为0(n)。由于插入可能在表中任何位置上进行,因此需分析算法的平均复 杂度。在长度为n的线性表中第i个位置上插入一个结点,令Eis(n)表示移动结点的期望值(即移动的平均次数),则在第i个位置上插入 一个结点的移动次数为n-i+1。故不失一般性,假设在表中任何位置(I WiWn+l)上插入结点的机会是均 等的,则p l=p2=p3=.=pn+l=l/(n+1)因此,在等概率插入的情况下,也就是说,在顺序表上做插入运算,平均要移
24、动表上一半的结点。当表长n较大时,算法的效率相当低。虽然Eis(n)中n的的系数较小,但就数量级而言,它仍然是线性级的。因此算法的平均时间复杂度为O(n)o考点9顺序表的删除运算线性表的删除运算是指将表的第i(lWiWn)个结点删除,使长度 为n的线性表:(al,,ai-1,ai,ai+L,an)变成长度为n-1的线性表(al,,ai-1,ai+L,an)该算法的时间分析与插入算法相似,结点的移动次数也是由表长 n和位置i决定。若i二n,则由于循环变量的初值大于终值,前移语句 将不执行,无需移动结点;若i=L则前移语句将循环执行n l次,需移动表中除开始结点外的所有结点。这两种情况下算法的时间
25、复杂 度分别为0(1)和0(n)。删除算法的平均性能分析与插入算法相似。在长度为n的线性表 中删除一个结点,令Ede(n)表示所需移动结点的平均次数,删除表 中第i个结点的移动次数为n-i,故式子中,pi表示删除表中第i个结点的概率。在等概率的假设下,pl=p2=p3=.=pn=l/n由此可得:即在顺序表上做删除运算,平均要移动表中约一半的结点,平均 时间复杂度也是0(n)。1.4栈和队列考点10栈及其基本运算1什么是栈栈实际也是线性表,只不过是一种特殊的线性表。栈(Stack)是 只能在表的一端进行插入和删除运算配线性表,通常称插入、删除的 这一端为栈顶(Top),另一端为栈底(Bottom
- 配套讲稿:
如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。