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

全国计算机等级考试二级公共根底知识考点公共根底知识 根本要求 1．掌握算法的根本概念 2．掌握根本数据构造及其操作 3．掌握根本排序和查找算法 4．掌握逐步求精的构造化程序设计方法 5．掌握软件工程的根本方法，具有初步应用相关技术进展软件开发的能力 6．掌握数据库的根本知识，了解关系数据库的设计 考试内容 一、根本数据构造及算法 1．算法的根本概念；算法复杂度的概念和意义(时间复杂度及空间复杂度〕 2．数据构造的定义；数据的逻辑构造及存储构造；数据构造的图形表示；线性构造及非线性构造的概念 3．线性表的定义；线性表的顺序存储构造及其插入及删除运算 4．栈和队列的定义；栈和队列的顺序存储构造及其根本运算 5．线性单链表、双向链表及循环链表的构造及其根本运算 6．树的根本概念；二叉树的定义及其存储构造；二叉树的前序、中序和后序遍历 7．顺序查找及二分法查找算法；根本排序算法(交换类排序，选择类排序，插入类排序) 二、数据库设计根底 1．数据库的根本概念：数据库，数据库管理系统，数据库系统 2．数据模型，实体联系模型及E―R图，从E―R图导出关系数据模型 3．关系代数运算，包括集合运算及选择、投影、连接运算，数据库标准化理论。

4．数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略三、程序设计根底 1．程序设计方法及风格 2．构造化程序设计 3．面向对象的程序设计方法，对象，方法，属性及继承及多态性 四、软件工程根底 1．软件工程根本概念，软件生命周期概念，软件工具及软件开发环境 2．构造化分析方法，数据流图，数据字典，软件需求规格说明书 3．构造化设计方法，总体设计及详细设计 4．软件测试的方法，白盒测试及黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试 5．程序的调试，静态调试及动态调试 全国计算机等级考试二级公共根底讲义之一算法及数据构造本章应考点拨：本章内容在笔试中会出现5-6个题目，是公共根底知识局部出题量比拟多的一章，所占分值也比拟大，约10分1、算法的根本概念：是指解题方案的准确而完整的描述 算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计 2、算法的根本特征〔1〕可行性 针对实际问题而设计的算法，执行后能够得到满意的结果〔2〕确定性 每一条指令的含义明确，无二义性并且在任何条件下，算法只有唯一的一条执行路径，即一样的输入只能得出一样的输出。

〔3〕有穷性 算法必须在有限的时间内完成有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成〔4〕拥有足够的情报 算法中各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这就是算法执行的起点或依据因此，一个算法执行的结果总是及输入的初始数据有关，不同的输入将会有不同的结果输出当输入不够或输入错误时，算法将无法执行或执行有错一般说来，当算法拥有足够的情报时，此算法才是有效的；而当提供的情报不够时，算法可能无效综上所述，所谓算法，是一组严谨地定义运算顺序的规那么，并且每一个规那么都是有效的，且是明确的，此顺序将在有限的次数下终止3、算法复杂度主要包括时间复杂度和空间复杂度〔1〕算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需根本运算的执行次数来度量同一个算法用不同的语言实现，或者用不同的编译程序进展编译，或者在不同的计算机上运行，效率均不同这说明使用绝对的时间单位衡量算法的效率是不适宜的撇开这些及计算机硬件、软件有关的因素，可以认为一个特定算法"运行工作量"的大小，只依赖于问题的规模〔通常用整数n表示〕，它是问题规模的函数。

即算法的工作量〔n〕〔2〕算法空间复杂度是指执行这个算法所需要的内存空间一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间其中额外空间包括算法程序执行过程中的工作单元以及某种数据构造所需要的附加存储空间如果额外空间量相对于问题规模来说是常数，那么称该算法是原地工作的在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间算法习题】1、算法的时间复杂度是指 CA) 执行算法程序所需要的时间 B) 算法程序的长度C) 算法执行过程中所需要的根本运算次数 D) 算法程序中的指令条数2、算法的根本特征是可行性、确定性、 有穷性 和拥有足够的情报3、算法的空间复杂度是指 CA) 算法程序的长度 B) 算法程序中的指令条数C) 算法程序所占的存储空间 D) 执行过程中所需要的存储空间4、在计算机中，算法是指 BA) 加工方法 B) 解题方案的准确而完整的描述 C) 排序方法 D) 查询方法5、算法的工作量大小和实现算法所需的存储单元多少分别称为算法的 【1】 时间复杂度和空间复杂度 1.2 数据构造的根本概念1、数据构造是指相互有关联的数据元素的集合。

2、数据构造主要研究和讨论以下三个方面的问题：〔1〕数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑构造数据的逻辑构造有两个要素：一是数据元素的集合；二是此集合上的关系，它反映了数据元素之间的前后件关系〔2〕在对数据进展处理时，各数据元素在计算机中的存储关系，即数据的存储构造数据的逻辑构造在计算机存储空间中的存放形式称为数据的存储构造〔也称数据的物理构造〕由于数据元素在计算机存储空间中的位置关系可能及逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系〔即前后件关系〕，在数据的存储构造中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息数据的存储构造有顺序、链接、索引等1〕顺序存储它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里由此得到的存储表示称为顺序存储构造2〕链接存储它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的由此得到的存储表示称为链式存储构造3〕索引存储：除建立存储结点信息外，还建立附加的索引表来标识结点的地址同一种逻辑构造的数据可以采用不同的存储构造，而采用不同的存储构造，其数据处理的效率是不同的。

因此，在进展数据处理时，选择适宜的存储构造是很重要的〔3〕对各种数据构造进展的运算3、数据构造的图形表示一个数据构造除了用二元关系表示外，还可以直观地用图形表示在数据构造的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点4、根据数据构造中各数据元素之间前后件关系的复杂程度，数据构造分为两大类型：线性构造和非线性构造〔1〕线性构造〔非空的数据构造〕条件：v 有且只有一个根结点[3] ；v 每一个结点最多有一个前件，也最多有一个后件常见的线性构造有线性表〔栈、队列是线性表的特例〕〔2〕非线性构造：不满足线性构造条件的数据构造常见的非线性构造有树、二叉树和图等数据构造根本概念习题】1、根据数据构造中各数据元素之间前后件关系的复杂程度，一般将数据构造分成A) 动态构造和静态构造 B) 紧凑构造和非紧凑构造C) 线性构造和非线性构造 D) 内部构造和外部构造 2、数据构造包括数据的逻辑构造、数据的 【2】 以及对数据的操作运算。

存储构造3、数据的根本单位是 【5】 数据元素4、以下表达中，错误的选项是A) 数据的存储构造及数据处理的效率密切相关B) 数据的存储构造及数据处理的效率无关C) 数据的存储构造在计算机中所占的空间不一定是连续的D) 一种数据的逻辑构造可以有多种存储构造5、数据的存储构造是指A〕数据所占的存储空间 C〕数据在计算机中的顺序存储方式B〕数据的逻辑构造在计算机中的表示 D〕存储在外存中的数据6、顺序存储方法是把逻辑上相邻的结点存储在物理位置 【2】 的存储单元中 相邻7、数据处理的最小单位是 A) 数据 B) 数据元素 C) 数据项 D) 数据构造8、数据构造作为计算机的一门学科，主要研究数据的逻辑构造、对各种数据构造进展的运算，以及 A) 数据的存储构造 B) 计算方法 C) 数据映象 D) 逻辑存储9、数据构造中，及所使用的计算机无关的是数据的A) 存储构造 B) 物理构造C) 逻辑构造 D) 物理和存储构造 10、数据的逻辑构造有线性构造和 【1】 两大类。

非线性构造1.3 线性表及其顺序存储构造1、线性表是由n(n≥0)个数据元素组成的一个有限序列，表中的每一个数据元素，除了第一个和最后一个外，有且只有一个前件、后件线性表中数据元素的个数称为线性表的长度线性表可以为空表线性表有两种存储方式：顺序和链式2、线性表的顺序存储构造〔也称为顺序表〕具有两个根本特点：〔1〕线性表中所有元素所占的存储空间是连续的；〔2〕线性表中各数据元素在存储空间中是按逻辑顺序依次存放的，即顺序表中逻辑上相邻的元素的物理位置必定紧邻〔即逻辑构造和物理存储构造是一致的、一一对应的〕3、顺序表的插入、删除运算〔1〕顺序表的插入运算：在一般情况下，要在第i〔1≤i≤n〕个元素之前插入一个新元素时，首先要从最后一个〔即第n个〕元素开场，直到第i个元素之间共1个元素依次向后移动一个位置，移动完毕后，第i个位置就被空出，然后将新元素插入到第i项插入完毕后，线性表的长度就增加了1插入运算时需要移动元素，在等概率情况下，平均需要移动2个元素〔2〕顺序表的删除运算：在一般情况下，要删除第i〔1≤i≤n〕个元素时，那么要从第1个元素开场，直到第n个元素之间共个元素依次向前移动一个位置。

删除完毕后，线性表的长度就减小了1删除运算时也需要移动元素，在等概率情况下，平均需要移动〔1〕/2个元素v 插入、删除运算不方便在长度为n的顺序表中插入、删除一个元素的时间复杂度都为O(n)〔3〕即查找操作：可实现随机访问、随机存取元素在顺序表中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面，即顺序存储构造通过元素的相对存储地址来表示元素之间的关系，可以通过计算机直接确定第i个结点的存储地址的存储地址为：()(a1)+(1)k,，(a1)为第一个元素的地址，k代表每个元素占的字节数线性表顺序存储的优点是可以随机访问、随机存取元素即实现查找操作比拟方便，换句话说，顺序表是一种随机存取的存储构造线性表顺序存储的缺点：〔1〕插入或删除数据元素时需要移动大量的数据元素，运算效率很低〔2〕顺序表的存储空间不便于扩大；〔3〕不便于对存储空间的动态分配1.4 线性链表线性表的链式存储构造称为线性链表，是一种物理存储单元上。