资源描述：
《《专升本计算机导论》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、知识点：练习题：模拟题：1本课程的主要研究内容什么是数据结构算法及其复杂性的概念算法的表达与数据表示抽象数据类型第一章引论2数据结构的主要研究内容机外表示处理要求问题逻辑结构基本运算存储结构算法建模求精数学模型实现3数据（data）数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数值性数据非数值性数据4数据元素(dataelement)数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。一个数据元素可以由若干数据项(DataItem)组成。数据项是具有独立含义的最小标识单位。数据元素又称为
2、元素、结点、记录。5数据对象(dataobject)数据对象是具有相同性质的数据元素的集合。整数数据对象N={0,1,2,…}学生数据对象6什么是数据结构定义:指某一数据对象及该对象中所有数据成员之间的关系。记为：Data_Structure={D,R}其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。7数据结构是数据的存在(组织)形式数据元素间的逻辑关系，即数据的逻辑结构；数据元素及其关系在计算机存储内的表示，即数据的存储(机内)表示；数据的运算，即对数据元素施加的操作。8数据的逻辑结构数据的逻辑结构从逻辑关系上描述数据，与数据
3、的存储无关；数据的逻辑结构可以看作是从具体问题抽象出来的数据模型；数据的逻辑结构与数据元素本身的形式、内容无关；数据的逻辑结构与数据元素的相对存储位置无关。9数据的逻辑结构分类线性结构线性表非线性结构多维数组广义表树图（或网络）10线性结构树形结构树二叉树二叉搜索树1413121123456789103158710119987456623131bindevetclibuser111堆结构“最大”堆“最小”堆12354871110291641012115123698712图结构网络结构1256431254361133181466516192113数据的存储
4、结构数据的存储结构是逻辑结构用计算机语言的实现；数据的存储结构依赖于计算机语言。顺序存储表示链接存储表示索引存储表示散列存储表示14算法的概念算法的定义：由若干条指令组成的一个有穷序列，这些指令为解决某一特定任务规定了一个运算序列特性：输入有0个或多个输入输出有一个或多个输出(处理结果)确定性每步定义都是确切、无歧义的有穷性算法应在执行有穷步后结束15程序与算法的区别程序可以不满足有穷性。16算法的性能标准正确性：要求算法能够正确地执行预先规定的功能和性能要求。这是最重要的标准，这要求算法的编写者对问题有正确的理解，并正确地、无歧义地描述和利用某种编程语
5、言正确地实现对算法的要求。可使用性：要求算法能够方便的使用。这个特性也叫用户友好性。为了便于用户使用，要求该算法具有良好的界面，完备的用户文档。因此，算法的设计必须符合抽象数据类型和模块化的要求，最好所有的输入和输出数据都通过参数表显式地传递，少用变量或全局变量，每个算法只完成一个功能。17算法的性能标准可读性：算法应当是可读的。这是理解、测试和修改算法的需要。为了达到这一要求，算法的逻辑必须是清晰的、简单的和结构化的。所有的变量名、函数名的命名必须有实际含义、让人见名知义。在算法中必须加入注释，简要说明算法的功能、输入与输出参数的使用规则、重要数据的作
6、用、算法中各程序段完成的功能等。效率：算法的效率是指算法执行时计算机资源的消耗。18算法的性能标准健壮性：要求在算法中加入对输入参数、打开文件、读文件记录、子程序调用状态进行自动检错、报错并通过与用户对话来纠错的功能，也叫容错性或例外处理。一个完整的算法必须具有健壮性，能够对不合理的数据进行检查。19算法复杂性的概念算法的复杂性：是运行算法所需要的计算机资源的量。时间复杂性：需要的时间资源的量。空间复杂性：需要的空间资源的量。算法复杂性分析的目的是评价算法的效率，对算法的设计或选用具有重要的指导义意和实用价值。20算法复杂性的度量度量算法复杂性的量应能集
7、中反映算法的效率,而从运行该算法的实际计算机中抽象出来。即这个量只依赖算法要解决问题的规模和算法的输入函数。设：n-问题规模;I-输入函数C-算法复杂性,应表示为C(n,I)。T(n,I)–时间复杂性S(n,I)–空间复杂性21算法复杂性的度量根据T(n,I)的概念，它是表示算法在一台抽象的计算机上运行所需的时间。设抽象的计算机所提供的元运算有k种，分别记为O1，O2，···,Ok。又设执行一次元运算所需的时间为t1，t2，···,tk。对于给定的算法A，用到的元运算Oi的次数为ei,i=1,2,···,k。则ei是n和I的函数，即ei=ei（n,I)。
8、T(n,I)=22算法复杂性的度量Tmin(n,I)=最好情况下的时间复杂性mi
