公共基础复习重点

《公共基础复习重点》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、K第二部分》二级公共基础历年试题分布：数据结构M算法（3-5个选择题，一般4题；1-3个填空题，一般2题，约12分）程序设计基础（1・2个选择题，一般1题；0-2个填空题，一般0・1个，约4分）软件工程基础（2-3个选择题，一般2题；1-2个填空题，一般2个，约8分）数据库设计基础（2・3个选择题，一般2题；1・2个填空题，一般2个，约8分）第一章数据结构与算法第一部分算法大纲要求：算法的基本概念；算法复杂度的概念和意义（时间与空间复杂度）一、算法的基本概念算法：是指一组有穷的指令集，是解题方案的准确而完整的描述。通俗的说，算法就是计算机解题的过程。注：程序的编制不可能优于算法。二、算法的

2、基本特征（★）1、可行性：能够得到满意的结果。2、确定性：算法的每一个步骤都必须有明确的定义。3、有穷性：一个算法必须在执行有穷步后结束，即算法必须能够终止。即必须能在有限的时间内做完。4、拥有足够的情报（有零个输入或多个输入，有一个或多个输出）：算法是否有效，取决于算法捉供的情报是否足够。例：1•算法的有穷性是指（）【08年4月】A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户使用三、算法设计基本方法1、列举法2、归纳法3、递推法4、递归法5、减半递推技术6、冋溯法四、算法复杂度（时间复杂度和空间复杂度）（★★）1、时间复

3、杂度：执行算法所需要的计算工作量，也就是耗费的时间量。是对算法时间效率的度量。2、空间复杂度：执行这个算法所需要的内存空间，是对算法所需存储空间的度量。3、空间复杂度•空间复杂度是从两个方面对算法的效率进行度量，两者Z间没有必然的联系。例：1.算法的空间复杂度是指（）。【09年9月】A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序屮的语句或指令条数D.算法在执行过程中所需要的临时工作单元数2.算法复杂度主要包括时间和【05年9月】复杂度。3.下列叙述中正确的是（）【06年9刀】则其时间复杂度也必定人则其时间复杂度必定小则其空I'可复杂必定小A）一个算法的空间复杂

4、度人,B）—•个算法的空间复杂度大,C）一个算法的时间复杂度人,0）上述三种说法都不对第二部分数据结构大纲要求：数据结构的定义，数据的逻辑结构与存储结构，数据结构的图形表示；线性结构与非线性结构的概念。一、数据结构的相关概念1、数据结构——是指市某一数据对彖及该对彖中所有数据成员Z间的关系组成的集合。通常也指带有结构的数据元素的集合。数据结构可分为数据的逻辑结构和数据的存储结构两种。2、数据的逻辑结构——反映数据元素之间逻辑关系的数据结构。（★★★）3、数据的存储结构——数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，即各数据元素在计算机屮的存储关系。（★★★）4、数据存储结

5、构不仅要存放各数据元素的信息，还要存放各数据元素之间的前后件关系的信息。5、逻辑结构与存储结构Z间的关系（★★★）一种数据的逻辑结构根据盂要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。采用不同的存储结构，其数据处理的效率是不同的。例：1.下列描述中止确的是（）【05年9月】A）—个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，H.各种存储结构不影响数据处理的效率D）—个逻辑数据结构可以有多种存储结构，H各种存储结构彩响数据处理的效率2.下列叙述正确的是（）【07年4月】A）算法的效率只与问

6、题的规模有关，而与数据的存储结构无关B）算法的时间复杂度是指执行算法所需要的计算工作量C）数据的逻辑结构与存储结构是一一对应的D）算法的时间复杂度与空间复杂度一定相关3.下列叙述中正确的是（）【07年9刀】°A）数据的逻辑结构与存储结构必定是一一对应的B）由丁•计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C）程序设计语言屮的数组一般是顺序存储结构，因此，利川数组只能处理线性结构D）以上三种说法都不对4.数据的存储结构是指（）【05年4月】A）存储在外存中的数据B）数据在外存中的数据C）数据在计算机屮的顺序存储方式D）数据的逻辑结构在计算机屮的表示6、数据结构的符号表

7、示：B二（D,R）B：数据结构，D：数据元素的集合，R：数据元素Z间的前后件关系。7、数据结构的图形表示：①方框：表示数据元素②有向线段：表示数据元索的前后件关系。如：一年四季的数据结构用图形表示为8、根据数据结构各数据元素Z间前后件关系的复杂程度，将数据结构分为：（按逻辑结构的分类）（★★★）①线性结构②非线性结构9、线性结构所满足的条件：①有H-只有一个根结点；②每一个结点瑕多有一个前件，也最多有一个后件；线性结构又