资源描述：
《知识点大纲全国计算机等级考试-数据结构和算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、全国计算机等级考试二级office二级公共基础知识部分（10分*10题）第一章.算法与数据结构考点1:算法概念•算法算法：指解题方案准确而完整的描述。算法不等于程序，也不是计算方法。程序编制通常不优于算法设计。考点2：算法的四个基本特征可行性、确定性（算法步骤有明确定义）、有穷性、拥有足够情报考点3：算法的时间复杂度和空间复杂度1.时间复杂度：执行算法所需的工作量。算法执行的基本次数是问题规模的函数，固定规模下还与输入有关。2.空间复杂度：算法执行需要的存储空间（算法程序、输入初始数据、某种数据结构所需空间）•数据结构（反映数据元素之
2、间关系的数据元素集合，即带有结构的数据元素的集合，结构指数据元素之间的前后件（前驱、后继）关系）。目的是提高数据处理的效率（速度/空间）线性表线性结构-・数据的逻辑结构数据的存储结构（物理结构）J非线性结构「顺序存储队列（循环队列）树形结构图形结构-链式存储-数据的运算■检索、排序、插入、删除、修改等数据的逻辑结构：是反映数据元素之间逻辑关系的数据结构。可以表示成：B=（D,R）B表示数据结构；D表示数据元素集合；R表示数据元素之间的前后件关系【例：一年四季的数据结构可以表示成B二（D,R）；D二（春，夏，秋，冬）；B={（春，夏），
3、（夏，秋），（秋，冬）}】数据结构的图形表示：数据元素：用中间标有元素值的方框表示，称为结点。ryiryiE逻辑关系：用有向线段从前件指向后件。没有前件的结点称为根结点；没有后件的结点称为终端结点（叶子结点）B二（D,R）ryiEED二{di
4、lWiW7}={dl,d2,d3,d4,d5.d6.d7}R={（dl,d3）,（dl,d7）,（d2,d4）,（d3,d6）,（d4,d5）}考点4：数据的存储结构数据的存储结构：指数据的逻辑结构在计算机储存空间的存放形式。既储存数据元素的信息,述有元素的前后件关系信息。数据的逻辑关系与数据的
5、存储结构不一定相同。数据结构一般可以表示成多种存储结构，常见的存储结构有顺序、链接、索引等。采用不同的存储结构，其数据处理效率不同。考点5：线性结构和非线性结构（逻辑结构而言）线性结构（线代表人•有且只有一个根结点，它无前件；•有且只有一个终端（叶子）结点，无后件；•除根结点和终端结点外，其他所有结点有且只有一个前件和一个后件。线性表中结点个数n称为线性表的长度；n=0表示空表。常见的线性结构有线性表、栈、队列（循环队列）。线性表是最简单、常见数据结构。可用顺序存储结构、链式存储结构。顺序储存结构特点：线性表中所有元素存储空间连续，按
6、逻辑顺序依次冇放。非线性结构：一个数据结构不是线性结构，称为非线性结构（树、图）。空的数据结构可能是线性结构，也可能是菲线性结构。考点6：顺序表的插入运算例：在第二个元素（18）Z前插入一个元素87,过程如下:1、29；2、18；3、56；4、63—1、29；2、18；3、56；4、；5、63il、29；2、18；3、4、56；5、63il、29；2、；3、18；4、56；5、63—►1、29；2、87；3、18；4、56；5、63【在平均情况下，插入运算在第i个（lWiWn）元素之前进行，需要移动一半的元素；最坏情况下需移动所有元素
7、】例：线性表的删除运算删除线性表中的第一个元素（29）,过程如下：1、29；2、18；3、56—1、；2、18；3、56—1、1&2、；3、56—1、18；2、56【在一般情况下，要删除第i个（lWiWn）元素时，在平均情况下，需要移动一半的元素。因此,在线性表顺序存储情况下，要删除一个数据，效率很低】考点7：栈栈：是限定在一端进行插入和删除的线性表，其特殊性体现在它的插入和删除运算都在线性表的一端进行，而另一端是封闭的，不进行任何操作。在栈屮，允许插入或删除操作的一端称为栈顶，另一端称为栈底。原则是：先进后出（或后进先出）。栈具有记
8、忆功能。123456栈底指针bottom（指向最底部）栈顶指针top（始终指向最顶部）栈空入栈栈满岀栈即top=0（不能退栈，否则下溢错误）（元素苹果、桔子、西瓜、草莓依次入栈，top指针上移）（top指针指向顶部元素草莓栈满，栈满再入栈则出现溢出错误（草莓、西瓜、桔子、苹果依次出栈进行退栈操作，top依次下移）•草莓•西瓜•桔子•苹果7bottom—>栈空—考点8：队列队列：允许在一端进行插入，另一端进行删除的线性表。先进先出1.尾指针rear：插入一端称队尾，rear指向队尾元素且始终指向最后入队元素。2.排头指针front：出队
9、一端称为排头（队头），用front指向排头元素的前一个位置。考点9：循环队列队列的顺序储存结构一般釆用循环队列的形式。循环队列初始状态为空，:rcar=front=m（队头、队尾指针同时指向同一个元素）。打入队运算：初始
