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

《二级公共基础知识全国计算机等级考试》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、全国计算机等级考试NationalComputerRankExamination二级·公共基础知识二级公共基础知识考试内容数据结构和算法程序设计基础软件工程数据库设计基础全国计算机等级考试2二级公共基础知识1、二级公共基础的考试方式为笔试，与各科语言的笔试部分合为一张试卷。公共基础部分占全卷的30分。2、公共基础知识有10道选择题和5道填空题。二级公共基础知识考试方式全国计算机等级考试3二级公共基础知识理解基本概念多做练习适当记忆一些名词与所学程序设计语言结合起来理解二级公共基础知识学习方法全国计算机等级考试4二级公共基础知识第一章数据结构和算法本章知识要点算法算法的定义算法的

2、特征算法复杂度数据结构数据结构的定义逻辑结构和物理结构线性结构和非线性结构顺序表、链表、堆栈队列、循环队列、树算法的基本要素全国计算机等级考试6二级公共基础知识算法是对特定问题求解步骤的一种描述。一、算法算法的特性：（1）有穷性：算法必须在有限的次数内完成。（2）确定性：算法的每一步必须是明确的。（3）可行性：算法的每一步必须是可以实现的。（4）拥有足够的情报：算法必须有一定的输入和输出。全国计算机等级考试7二级公共基础知识算法的基本要素：（1）对数据对象的运算和操作：A.算术运算B.逻辑运算C.关系运算D.数据传输（2）算法的控制结构：A.顺序结构B.选择结构C.循环结构全国

3、计算机等级考试8二级公共基础知识算法的复杂度：衡量算法优劣的量。（1）时间复杂度：算法的时间耗费。A.算法中基本操作重复执行次数和算法执行时间同步增长，称作算法的时间复杂度。B.算法中基本操作重复执行次数和问题规模有关，是问题规模的函数。C.算法的时间复杂度是指执行算法所需要的计算工作量。（2）空间复杂度：执行算法所需要的内存空间。全国计算机等级考试9二级公共基础知识1、问题处理方案的正确而完整的描述称为。2、算法的基本特征是可行性、确定性、和拥有足够的情报。3、算法具有4个特性，以下选项中不属于算法特性的是（）A)有穷性B)简洁性C)可行性D)确定性4、算法的时间复杂度是指（

4、）A)执行算法程序所需要的时间B)算法程序的长度C)算法执行过程中所需要的基本运算次数D)算法程序中的指令条数5、算法的空间复杂度是指（）A)算法程序的长度B)算法程序中的指令条数C)算法程序所占的存储空间D)执行过程中所需要的存储空间全国计算机等级考试10二级公共基础知识6、在计算机中，算法是指（）A)加工方法B)解题方案的准确而完整的描述C)排序方法D)查询方法7、下列叙述中正确的是（）A)算法的效率只与问题的规模有关，而与数据的存储结构无关。B)算法的时间复杂度是指执行算法所需要的计算工作量。C)数据的逻辑结构与存储结构是一一对应的。D)算法的时间复杂度与空间复杂度一定相

5、关。全国计算机等级考试11二级公共基础知识二、数据结构数据结构主要研究两方面的问题：（1）数据本身。（2）数据之间的前后件关系。数据结构数据本身数据之间的前后件关系数据结构表示为：DS={D，S}例：D={春，夏，秋，冬}S={(春,夏)，(夏,秋)，(秋,冬)，(冬,春)}全国计算机等级考试12二级公共基础知识数据的结构分为：（1）物理结构：数据在计算机存储介质中真正存储的结构，也被称为“存储结构”（2）逻辑结构：人们所理解的数据之间的结构，可以用图示的方法绘画出来的数据之间的结构。例：一个班由35名同学，他们的座位牌号就是物理结构，一次考试的排名是逻辑结构。1注意：逻辑结构

6、和物理结构没有必然的联系，也不一定是一一对应的。全国计算机等级考试13二级公共基础知识数据的结构分为：（1）线性结构：非空数据结构同时满足以下两个条件就是线性结构：A.有且仅有一个根结点；B.除头结点和尾结点外，任何结点有且仅有一个前件和一个后件。（2）非线性结构：除了线性结构都是非线性结构。全国计算机等级考试14二级公共基础知识全国计算机等级考试二级公共基础知识要求掌握的数据结构共有以下六种：线性表堆栈队列循环队列线性链表树和二叉树线性结构物理结构和逻辑结构相同物理结构和逻辑结构相同物理结构和逻辑结构相同物理结构和逻辑结构相同物理结构和逻辑结构不相同物理结构和逻辑结构不相同非

7、线性结构全国计算机等级考试15二级公共基础知识1020304050607080三、顺序表：顺序表就是数组1、顺序表也叫做线性表，属于线性结构。线性表的逻辑结构和物理结构相同。2、特点：（1）有且仅有一个头结点（根节点）和尾结点。（2）任意其他结点至多有一个前件，一个后件。（3）头结点没有前件，尾结点没有后件。全国计算机等级考试16二级公共基础知识四、堆栈栈顶top栈底入栈/压入出栈/弹出1、定义：只允许在栈顶位置插入数据和删除数据的线性结构是堆栈，简称为“栈”。2、堆栈属于线性结构。3、堆栈