知识点大纲全国计算机等级考试-数据结构和算法.docx

《知识点大纲全国计算机等级考试-数据结构和算法.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、全国计算机等级考试二级office二级公共基础知识部分（10分*10题）第一章.算法与数据结构考点1：算法概念l算法算法：指解题方案准确而完整的描述。算法不等于程序，也不是计算方法。程序编制通常不优于算法设计。考点2：算法的四个基本特征可行性、确定性（算法步骤有明确定义）、有穷性、拥有足够情报考点3：算法的时间复杂度和空间复杂度1.时间复杂度：执行算法所需的工作量。算法执行的基本次数是问题规模的函数，固定规模下还与输入有关。2.空间复杂度：算法执行需要的存储空间（算法程序、输入初始数据、某种数据结构所需空间）l数据结构（反映数据元素之间关系的数据元素集合，即带有结构的数据元素的集合，结构

2、指数据元素之间的前后件（前驱、后继）关系）。目的是提高数据处理的效率（速度/空间）数据的逻辑结构：是反映数据元素之间逻辑关系的数据结构。可以表示成：B=（D，R）B表示数据结构；D表示数据元素集合；R表示数据元素之间的前后件关系【例：一年四季的数据结构可以表示成B=（D，R）；D=（春，夏，秋，冬）；B={（春，夏），（夏，秋），（秋，冬）}】数据结构的图形表示：数据元素：用中间标有元素值的方框表示，称为结点。逻辑关系：用有向线段从前件指向后件。没有前件的结点称为根结点；没有后件的结点称为终端结点（叶子结点）B=（D，R）D={di

3、1≤i≤7}={d1,d2,d3,d4,d5.d6.d

4、7}R={（d1,d3）,（d1,d7）,（d2,d4）,（d3,d6）,（d4,d5）}考点4：数据的存储结构数据的存储结构：指数据的逻辑结构在计算机储存空间的存放形式。既储存数据元素的信息,还有元素的前后件关系信息。数据的逻辑关系与数据的存储结构不一定相同。数据结构一般可以表示成多种存储结构，常见的存储结构有顺序、链接、索引等。采用不同的存储结构，其数据处理效率不同。考点5：线性结构和非线性结构（逻辑结构而言）线性结构（线代表）：l有且只有一个根结点，它无前件；l有且只有一个终端（叶子）结点，无后件；l除根结点和终端结点外，其他所有结点有且只有一个前件和一个后件。线性表中结点个数n称

5、为线性表的长度；n=0表示空表。常见的线性结构有线性表、栈、队列（循环队列）。线性表是最简单、常见数据结构。可用顺序存储结构、链式存储结构。顺序储存结构特点：线性表中所有元素存储空间连续，按逻辑顺序依次存放。非线性结构：一个数据结构不是线性结构，称为非线性结构（树、图）。空的数据结构可能是线性结构，也可能是非线性结构。考点6：顺序表的插入运算例：在第二个元素（18）之前插入一个元素87，过程如下：1、29；2、18；3、56；4、631、29；2、18；3、56；4、；5、631、29；2、18；3、；4、56；5、631、29；2、；3、18；4、56；5、631、29；2、87；3、

6、18；4、56；5、63【在平均情况下，插入运算在第i个（1≤i≤n）元素之前进行，需要移动一半的元素；最坏情况下需移动所有元素】例：线性表的删除运算删除线性表中的第一个元素（29），过程如下：1、29；2、18；3、561、；2、18；3、561、18；2、；3、561、18；2、56【在一般情况下，要删除第i个（1≤i≤n）元素时，在平均情况下，需要移动一半的元素。因此，在线性表顺序存储情况下，要删除一个数据，效率很低】考点7：栈入出栈：是限定在一端进行插入和删除的线性表，其特殊性体现在它的插入和删除运算都在线性表的一端进行，而另一端是封闭的，不进行任何操作。在栈中，允许插入或删除操

7、作的一端称为栈顶，另一端称为栈底。原则是：先进后出（或后进先出）。栈具有记忆功能。Top1.栈底指针bottom（指向最底部）2.栈顶指针top（始终指向最顶部）栈空3.栈空即top=0（不能退栈，否则下溢错误）bottom4.入栈（元素苹果、桔子、西瓜、草莓依次入栈，top指针上移）5.栈满（top指针指向顶部元素草莓栈满，栈满再入栈则出现溢出错误Rear6.出栈（草莓、西瓜、桔子、苹果依次出栈进行退栈操作，top依次下移）考点8：队列队列：允许在一端进行插入，另一端进行删除的线性表。先进先出（或后进后出）Front1.尾指针rear：插入一端称队尾，rear指向队尾元素且始终指向最后

8、入队元素。RearRearRear2.排头指针front：出队一端称为排头（队头），用front指向排头元素的前一个位置。考点9：循环队列RearFront/队列的顺序储存结构一般采用循环队列的形式。循环队列初始状态为空，即rear=front=m（队头、队尾指针同时指向同一个元素）。入队运算：初始状态下，F和R都指向1，随着ABC元素的入队，R依次上移，F不变。当R指向最后一个元素C之后，R最终回到指向1，使之构成循环。RearF