公共基础知识点合集.doc

第一章数据结构与算法考点1:算法(概念、特征、组成、方法、算法的复杂度)算法的概念(1)概念:是指解题方案的准确而完整的描述。【考题1】在计算机中,算法是指()A查询方法B加工方法C对解题方案的准确而完整的描述D排序方法【答案】:C【考题2】问题处理方案的正确而完整的描述称为。【答案】:算法算法的特征(1)算法的特征具有4种:可行性、确定性、有穷性、拥有足够的情报。①可行性:在算法的执行过程中,每一个步骤都要可行,可通。经过执行能够得到一个结果。②确定性:算法中的每一个步骤都要有确切的含义,不能有二义性,对于相同的输入必须能得出相同的执行结果。③有穷性:一个算法包含的操作步骤是有限的。也就是说,在执行若干个操作步骤之后算法结束,而且每一个步骤都要在合理的时间内完成。④拥有足够的情报:即拥有足够的输入数据。通过大量的给算法输入数据来验证算法输出的结果是否有误。【考题1】下列选项中不属于算法特征的是()A无穷性B确定性C可行性D拥有足够的情报【答案】:A【考题2】对于一个算法,它必须要在有限步骤合理时间内完成,这属于算法的()A可行性B确定性C有穷性D拥有足够的情报【答案】:C【考题3】在算法中,算法的特征具有可行性、确定性、、拥有足够的情报。【答案】:有穷性算法的组成(1)算法的组成有两种:对数据对象的运算和操作、算法的控制结构。(2)算法的控制结构有3种:顺序结构、选择结构、循环结构。算法的方法(1)在算法中,对问题描述的方法有6种:列举法、归纳法、递推、递归、减半递推技术、回溯法。算法的复杂度(1)算法的复杂度是对算法中的各种方法进行衡量的标准。(2)算法的复杂度有两种:算法的时间复杂度和算法的空间复杂度。①算法的时间复杂度:是指执行算法所需要的(计算工作量)基本运算次数。②算法的空间复杂度:是指执行算法所需要的内存空间。【知道】算法时间复杂度的好与坏不会影响空间复杂度的好与坏。【考题1】算法的时间复杂度是指()A执行算法程序所需要的时间B算法程序的长度C算法执行过程中所需要的基本运算次数D算法程序中的指令条数【答案】:C【考题2】算法的空间复杂度是指()A算法程序的长度B算法程序中的指令条数C算法程序所占的存储空间D算法执行过程中所需要的存储空间【答案】:D【考题3】下列叙述中正确的是()A一个算法的空间复杂度大,则其时间复杂度也必定大B一个算法的空间复杂度大,则其时间复杂度必定小C一个算法的时间复杂度大,则其空间可复杂度必定小D上述三种说法都不对【答案】:D【解析】:算法时间复杂度的好与坏不会影响空间复杂度的好与坏。考点2:数据结构(逻辑结构、存储结构、线性表、栈、队列、树和二叉树、查找和排序)数据结构(1)数据结构主要研究和讨论三个方面的内容:逻辑结构、存储结构、运算。【考题1】数据结构包括数据的和数据的存储结构。【答案】:逻辑结构逻辑结构满足逻辑结构的的条件:①表示数据元素的信息;②表示各数据元素之间的前后件关系。逻辑结构的分类:线性结构、非线性结构。线性结构:有且只有一个根结点;每一个结点最多有一个前件,也最多有一个后件。在本书中,线性结构主要讲到的有:线性表、栈、队列。非线性结构:不满足线性结构条件的就属于非线性结构。在本书中,非线性结构主要讲到的有:树、二叉树。【考题1】数据结构中,与所使用的计算机无关的是数据的()A存储结构B物理结构C逻辑结构D物理和存储结构【答案】:C【解析】:逻辑结构讨论的是现实世界中数据与数据之间的关系;存储结构也叫物理结构,指的是逻辑结构在计算机存储空间的存放形式。所以存储结构和计算机有关。A、B和D都不选。【考题2】以下数据结构中不属于线性结构的是()A队列B线性表C二叉树D栈【答案】:C【考题3】数据的逻辑结构有线性结构和两大类。【答案】:非线性结构存储结构(1)概念:数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)(2)数据的逻辑结构在计算机存储空间中的存储形式通常有两种:顺序存储结构、链式存储结构。①顺序存储结构:数据在存储空间中必须连续,且元素之间一定要有前后件的关系。②链式存储结构:数据在存储空间中不一定连续,且各元素的存储顺序是任意的。(3)两种存储结构的优缺点:①顺序存储结构:优点是查找方便。缺点是插入、删除不方便。②链式存储结构:优点是插入、删除方便。缺点是查找不方便。【考题1】数据的存储结构是指()A存储在外存中的数据B数据所占的存储空间C数据在计算机中的顺序存储D数据的逻辑结构在计算机中的表示【答案】:D【考题2】下列叙述正确的是()A一个逻辑数据结构只能有一种存储结构 B数据的逻辑结构属于线性结构,存储结构属于非线性结构 C一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理的效率 D一个逻辑数据结构可以有多种存储