全国计算机等级考试二级公共基础知识

全国计算机等级考试NationalComputerRankExamination+全国计算机等级考试NationalComputerRankExamination第一部分公共基础知识全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识3二级公共基础知识考试内容•数据结构和算法•程序设计基础•软件工程•数据库设计基础全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识41、二级公共基础知识不单独考试，与其他二级科目组合在一起，作为二级科目考核内容的一部分。公共基础部分占全卷的20分。2、公共基础知识考查方式为选择题共20道。二级公共基础知识考试方式全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识5•理解基本概念•多做练习•适当记忆一些名词•与所学程序设计语言结合起来理解二级公共基础知识学习方法第一章数据结构和算法全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识7本章知识要点算法算法的定义算法的特征算法复杂度数据结构数据结构的定义逻辑结构和物理结构线性结构和非线性结构顺序表、链表、堆栈队列、循环队列、树算法的基本要素全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识8算法是解决方案的准确而完整性描述。一、算法算法的特性：（1）有穷性：算法必须在有限的次数内完成。（2）确定性：算法的每一步必须是明确的。（3）可行性：算法的每一步必须是可以实现的。（4）拥有足够的情报：算法必须有一定的输入和输出。算法不等于程序，也不等于计算方法。全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识9算法的基本要素：（1）对数据对象的运算和操作：A.算术运算B.逻辑运算C.关系运算D.数据传输（2）算法的控制结构：A.顺序结构B.选择结构C.循环结构一、算法全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识10算法的复杂度：衡量算法优劣的量。（1）时间复杂度：算法的时间耗费。A.算法中基本操作重复执行次数和算法执行时间同步增长，称作算法的时间复杂度。B.算法中基本操作重复执行次数和问题规模有关，是问题规模的函数。C.算法的时间复杂度是指执行算法所需要的计算工作量。（2）空间复杂度：执行算法所需要的内存空间。一、算法全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识11例题1、算法的基本特征是可行性、确定性、和拥有足够的情报。2、算法具有4个特性，以下选项中不属于算法特性的是（）A)有穷性B)简洁性C)可行性D)确定性3、算法的时间复杂度是指（）A)执行算法程序所需要的时间B)算法程序的长度C)算法执行过程中所需要的基本运算次数D)算法程序中的指令条数4、算法的空间复杂度是指（）A)算法程序的长度B)算法程序中的指令条数C)算法程序所占的存储空间D)执行过程中所需要的存储空间一、算法有穷性BCD全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识125、在计算机中，算法是指（）A)加工方法B)解题方案的准确而完整的描述C)排序方法D)查询方法6、下列叙述中正确的是（）A)算法的效率只与问题的规模有关，而与数据的存储结构无关。B)算法的时间复杂度是指执行算法所需要的计算工作量。C)数据的逻辑结构与存储结构是一一对应的。D)算法的时间复杂度与空间复杂度一定相关。一、算法BB全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识13二、数据结构数据结构主要研究两方面的问题：（1）数据本身。（2）数据之间的前后件关系。数据结构数据本身数据之间的前后件关系数据结构表示为：DS={D，S}例：D={春，夏，秋，冬}S={(春,夏)，(夏,秋)，(秋,冬)，(冬,春)}全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识14数据的结构分为：（1）物理结构：数据在计算机存储介质中真正存储的结构，也被称为“存储结构”（2）逻辑结构：人们所理解的数据之间的结构，可以用图示的方法绘画出来的数据之间的结构。例：一个班由35名同学，他们的座位牌号就是物理结构，一次考试的排名是逻辑结构。注意：逻辑结构和物理结构没有必然的联系，也不一定是一一对应的。二、数据结构全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识15数据的结构分为：（1）线性结构：非空数据结构同时满足以下两个条件就是线性结构：A.有且仅有一个根结点；B.除头结点和尾结点外，任何结点有且仅有一个前件和一个后件。（2）非线性结构：除了线性结构都是非线性结构。二、数据结构全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识16全国计算机等级考试二级公共基础知识要求掌握的数据结构共有以下六种：•线性表•堆栈•队列•循环队列•线性链表•树和二叉树线性结构物理结构和逻辑结构相同物理结构和逻辑结构相同物理结构和逻辑结构相同物理结构和逻辑结构相同物理结构和逻辑结构不相同物理结构和逻辑结构不相同非线性结构二、数据结构全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识171020304050607080三、顺序表：顺序表就是数组1、顺序表也叫做线性表，属于线性结构。线性表的逻辑结构和物理结构相同。2、特点：（1）有且仅有一个头结点（根节点）和尾结点。（2）任意其他结点至多有一个前件，一个后件。（3）头结点没有前件，尾结点没有后件。全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识18四、堆栈栈顶top栈底入栈/压入出栈/弹出1、定义：只允许在栈顶位置插入数据和删除数据的线性结构是堆栈，简称为“栈”。2、堆栈属于线性结构。3、堆栈的逻辑结构和物理结构相同。4、特点：先进后出，后进先出所以堆栈也叫做先进后出表（FILO）5、堆栈具备存储功能：函数的递归调用和表达式求解都用到了堆栈。全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识19入栈顺序：a、b、c、d、e、f栈空abacbabadba…………..入a入b入c出c入d模拟堆栈的数据出入过程：四、堆栈全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识20【典型题型】假设一个堆栈，入栈顺序为abcde，认为在任何时刻均允许出栈，下列选项中不可能的出栈顺序为（）A）abcde（可能）B）edcba（可能）C）cdeba（可能）D）cdeab（不可能）如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是（）A)e3,e1,e4,e2B)e2,e4,e3,e1C)e3,e4,e1,e2D)任意顺序栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是（）A)ABCEDB)DCBEAC)DBCEAD)CDABE四、堆栈DBB全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识21五、队列队头front队尾rear入队出队1、队列属于线性结构。2、队列的逻辑结构和物理结构相同。3、定义：入队操作发生在队尾，出队操作发生在队头。4、特点：先进先出，后进后出，所以队列也叫做先进先出表（FIFO）。全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识221、栈和队列的共同特点是（）A)都是先进先出B)都是先进后出C)只允许在端点处插入和删除元素D)没有共同点2、一些重要的程序语言(如C语言和Pascal语言)允许过程的递归调用。而实现递归调用中的存储分配通常用（）A)栈B)堆C)数组D)链表3、下列关于栈的叙述中正确的是（）A)在栈中只能插入数据B)在栈中只能删除数据C)栈是先进先出的线性表D)栈是后进先出的线性表4、下列关于队列的叙述中正确的是（）A)在队列中只能插入数据B)在队列中只能删除数据C)队列是先进先出的线性表D)队列是后进先出的线性表五、队列CADC全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识23六、循环队列rearfront全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识24入队顺序：a、b、c、d、e、f模拟循环队列的数据出入过程：循环队列空front=rearrearfrontafrontrear数据a入队afrontrearb数据b入队frontrearb数据a出队入队运算是往队列队尾插入一个数据元素；退队运算是从队列的队头删除一个数据元素。六、循环队列全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识25七、线性链表1、链表属于线性结构。2、链表的逻辑结构和物理结构不相同。3、线性链表由结点组成：每个结点有两个区域：数据域，指针域。A.数据域，用来存储数据。B.指针域，用来指向下一个结点的位置。3、绘画一个由5个节点组成的线性链表，数据为1、2、3、4、5。链表的结点数据域指针域12345^单链表全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识26链表的种类：单链表、循环链表、双向链表。1234512345循环链表双向链表^12345^七、线性链表全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识271、链表不具有的特点是（）A)不必事先估计存储空间B)可随机访问任一元素C)插入删除不需要移动元素D)所需空间与线性表长度成正比2、数据结构分为逻辑结构与存储结构，线性链表属于。3、数据结构中，与所使用的计算机无关的是数据的（）A)存储结构B)物理结构C)逻辑结构D)物理和存储结构4、数据的逻辑结构有线性结构和两大类。七、线性链表BA存储结构非线性结构全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识28八、树与二叉树1、树的基本概念树是一种简单的非线性结构，是n个结点的有限集合。一般的树RKPQDBENOTCHXSWZAYMFGL根节点从逻辑结构看：1）树中只有根结点没有前趋；2）除根外，其余结点都有且仅有一个前趋；3）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一一条从根到该结点的路径；5）树是一种分支结构全国计算机等级考试NationalComputerRankExamination全国计算机等级考试二级公共基础知识29书第一章第二章第三章第四章1.1节1.1节1.1节1.1节1.1节1.1节1.1节1.1节1.1节书的层次结构注意:(1)树结构具有明显的层次关系，即树是一种层次结构。因此具有层次关系的数据都可以用树这种数据结构来描述。(2)在树结构中分层的原则是：根节点在第1层，同一层上所有结点的所有子结点都在下一层。(3)在树中，叶子结