2021计算机应用基础知识.docx

本文格式为Word版，下载可任意编辑
第PAGE\*MERGEFORMAT5页共NUMPAGES\*MERGEFORMAT5页

2021计算机应用基础学问
2021计算机应用基础学问1.1数据结构与算法借助于计算机解决问题，首先需要了解所处理对象的性质和特点即所操作对象的数据结构，然后再设计解决问题的方法和步骤即设计一个合理的算法，即通常所说的“程序=数据结构+算法”。1.1.1算法的基本概念“算法”〔Algorithm〕一词最早来自公元9世纪波斯数学家比阿勒·霍瓦里松的一本影响深远的著作《代数对话录》。20世纪的英国数学家图灵提出了出名的图灵论点，并抽象出了一台机器，这台机器被我们称之为图灵机。图灵的思想对算法的进展起到了重要的作用。一般来说，算法是指完成一个任务或解决一个问题所需要的具体步骤和方法的描述。在这里我们说的算法是指计算机能执行的算法。1.算法分类计算机算法可分为两大类，一类是数值运算算法，另一类是非数值运算算法。数值运算算法主要是求数值解，如求方程的解、求函数的定积分等，非数值运算的范围则特殊广泛，如人事管理、图书检索等。2.算法特征一个科学的算法必需具备以下特征：(1)有穷性：一个算法必需保证执行有限步之后结束，而不能是无限的。这是显而易见的。更进一步说，有穷性是指在合理的范围内结束运算，假如一个算法需计算机执行几百年或更长时间才结束，这明显是不合理的。(2)确定性：算法的每一步骤必需有精确的定义而不能模棱两可，算法中不能消灭诸如“一个比较大的数”等模糊描述。(3)有零个或多个输入(4)有一个或多个输出。算法的目的是为了解决问题,一个没有输出的算法是不能解决任何问题因此它是没有意义的.(5)有效性。算法中的每一个步骤都都应当能有效地执行，并得到确定的结果。例如，若n=0则执行m/n是无法有效执行的。3.算法表示一个计算机算法可以用自然语言、流程图、N-S图等来表示。4.算法分析算法分析的任务是对设计出的每一个具体的算法，利用数学工具，协商 各种冗杂度，以探讨某种具体算法适用于哪类问题，或某类问题宜接受哪种算法。算法的冗杂度分时间冗杂度和空间冗杂度。．时间冗杂度：在运行算法时所耗费的时间为f(n)(即n的函数)。．空间冗杂度：实现算法所占用的空间为g(n)〔也为n的函数〕。称O(f(n))和O(g(n))为该算法的冗杂度。1.1.2数据结构的定义数据结构是计算机科学与技术领域上广泛被使用的术语。尽管它至今还未有一个被全都公认的定义，但其内容是大家全都公认的。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有规律上的数据结构和物理上的数据结构之分。规律上的数据结构反映成分数据之间的规律关系，而物理上的'数据结构反映成分数据在计算机内部的存储支配。数据结构是数据存在的形式。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。一般数据结构可接受下面两类主要的存储方式，大多数数据结构的存储表示都接受其中的一类方式，或两类方式的结合。1.挨次存储结构这种存储方式的主要用于线性数据结构，它把规律上相邻的数据元素存储在物理上相邻的存储单元内，结点之间的关系由存储单元的邻接关系来实现。挨次存储结构的主要特点是：〔1〕结点中只有自身信息域，没有连接信息域，因此存储密度大，存储空间利用率高；〔2〕可以通过计算直接确定数据结构中第i个结点的存储地址Li，计算公式为Li=L0+(i-1)*m，其中L0为第一个结点的存储地址，m为每个结点所占用的存储单元个数；〔3〕插入、删除运算不便，会引起大量结点的移动。2.链式存储结构链式存储结构就是在每个结点中至少包括一个指针域，用指针来表达数据元素之间规律上的联系。这种存储结构可把规律上相邻的两个元素存放在物理上不相邻的存储单元中；还可以在线性编址的计算机存储器中表示结点之间的非线性联系。链式存储结构的主要特点是：〔1〕结点中除自身外，还有表示连接信息的指针域，因此比挨次结构的存储密度小，存储空间利用率低；〔2〕规律上相邻的结点物理上不必邻接，可用于线性表、树、图等多种规律结构的存储表示；〔3〕插入、删除操作灵敏便利，不必移动结点，只要转变结点中的指针即可。除上述两种主要存储方式外，散列法也是在线性表和集合的存储表示中常用的一种存储方式。1.1.3线性表结构1.线性表的定义线性表〔LinearList〕是最常用并且最简洁的一种数据结构。它是由n〔n≥0〕个数据元素〔结点〕a1，a2，…，an组成的有限序列。①数据元素的个数n定义为表的长度〔n=0时称为空表〕。②将非空的线性表〔n＞0〕记作：〔a1，a2，…，an〕③数据元素ai〔1≤i≤n〕只是个