第一篇：计算机等级考试二级公共基础知识总结_数据结构与算法
2011年全国计算机等级考试二级公共基础知识总结：数据结构与算法
1.1 算法
算法：是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程。算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。
(1)确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；
(2)有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止；
(3)可行性，算法原则上能够精确地执行；
(4)拥有足够的情报。
算法效率的度量—算法复杂度：算法时间复杂度和算法空间复杂度。★★★
算法时间复杂度：指执行算法所需要的计算工作量。即算法执行过程中所需要的基本运算次数。
算法空间复杂度：指执行这个算法所需要的内存空间。
1.2 数据结构的基本概念
数据结构：指相互有关联的数据元素的集合。
数据结构研究的三个方面：
(1)数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；
(2)在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；
(3)对各种数据结构进行的运算。
线性结构的条件，(一个非空数据结构)：
(1)有且只有一个根结点；(2)每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
1.3 线性表及其顺序存储结构
线性表的顺序存储结构具有以下两个基本特点：
(1)线性表中所有元素所占的存储空间是连续的；
(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
顺序表的运算：查找、插入、删除。
1.4线性链表
数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。
结点由两部分组成：
(1)用于存储数据元素值，称为数据域；
(2)用于存放指针，称为指针域，用于指向前一个或后一个结点。
在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
链式存储方式即可用于表示线性结构，也可用于表示非线性结构。
线性链表的基本运算：查找、插入、删除。
1.5栈和队列★★★★
栈：限定在一端进行插入与删除的线性表。
其允许插入与删除的一端称为栈顶，用指针top表示栈顶位置。
不允许插入与删除的另一端称为栈底，用指针bottom表示栈底。
栈按照―先进后出‖(FILO)或―后进先出‖(LIFO)组织数据，栈具有记忆作用。
栈的存储方式有顺序存储和链式存储。
栈的基本运算：
(1)入栈运算，在栈顶位置插入元素；
(2)退栈运算，删除元素(取出栈顶元素并赋给一个指定的变量)；
(3)读栈顶元素，将栈顶元素赋给一个指定的变量，此时指针无变化。
队列：指允许在一端(队尾)进入插入，而在另一端(队头)进行删除的线性表。
用rear指针指向队尾，用front指针指向队头元素的前一个位置。
队列是―先进先出‖(FIFO)或―后进后出‖(LILO)的线性表。
队列运算：
(1)入队运算：从队尾插入一个元素;
(2)退队运算：从队头删除一个元素;
计算循环队列的元素个数：
―尾指针减头指针‖，若为负数，再加其容量即可。
即:
当 尾指针-头指针>0 时,尾指针-头指针
当 尾指针-头指针<0 时,尾指针-头指针+容量
计算栈的个数:
栈底 –栈顶 +1
1.6 树与二叉树 ★★★★★
1、树的基本概念
树是一种简单的非线性结构，其所有元素之间具有明显的层次特性。
在树结构中，每一个结点只有一个前件，称为父结点。
没有前件的结点只有一个，称为树的根结点，简称树的根。
每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。
在树结构中，一个结点所拥有的后件的个数称为该结点的度。
所有结点中最大的度称为树的度。
树的最大层次称为树的深度。
2、二叉树及其基本性质
满足下列两个特点的树,即为二叉树
(1)非空二叉树只有一个根结点；
(2)每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
二叉树基本性质：★★★★
性质1 在二叉树的第k层上，最多有
个结点。
性质2 深度为m的二叉树最多有个 个结点。
性质3 在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。
性质4 具有n个结点的二叉树，其深度至少为数部分
3、满二叉树与完全二叉树
满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。
，其中
表示取
的整
完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
下图a表示的是满二叉树，下图b表示的是完全二叉树：
4、二叉树的遍历 ★★★★
二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为以下三种：
(1)前序遍历(DLR)：若二叉树为空，则结束返回。否则：首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
(2)中序遍历(LDR)：若二叉树为空，则结束返回。否则：首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。
(3)后序遍历(LRD)：若二叉树为空，则结束返回。否则：首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点.该二叉树前序遍历为:F C A D B E G H P
该二叉树中序遍历为:A C B D F E H G P
该二叉树后序遍历为:A B D C H P G E F
1.7 查找技术
查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。
查找结果：（查找成功：找到；查找不成功：没找到。）
平均查找长度：查找过程中关键字和给定值比较的平均次数。
查找分为: 顺序查找 二分法查找对于长度为n的有序线性表，最坏情况只需比较查找需要比较n次。
1.8 排序技术
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。
1、交换类排序法（冒泡排序，快速排序）
2、插入类排序法（简单插入排序，希尔排序）
3、选择类排序法（简单选择排序，堆排序）
冒泡排序法,快速排序法,简单插入排序法,简单选择排序法,最坏需要比较的次数为n(n-1)/2
次，而顺序
希尔排序,最坏需要比较的次数为
堆排序,最坏需要比较的次数为
第二篇：计算机等级考试二级MS-Office基础知识 （1）
第一部分
公共基础知识
第1章
数据结构与算法
1.1算法
1.算法的基本概念
(1)概念：算法是指一系列解决问题的清晰指令。
(2)4个基本特征：可行性、确定性、有穷性、拥有足够的情报。
(3)两种基本要素：对数据对象的运算和操作、算法的控制结构(运算和操作时问的顺序)。
(4)设计的基本方法：列举法、归纳法、递推法、递归法、减半递推技术和回溯法。
2.算法的复杂度
(1)算法的时间复杂度：执行算法所需要的计算工作量。
(2)算法的空间复杂度：执行算法所需的内存空间。
1.2数据结构的基本概念
数据结构指相互有关联的数据元素的集合，即数据的组织形式。其中逻辑结构反映数据元素之间逻辑关系;存储结构为数据的逻辑结构在计算机存储空间中的存放形式，有顺序存储、链式存储、索引存储和散列存储4种方式。
数据结构按各元素之间前后件关系的复杂度可划分为：
(1)线性结构：有且只有一个根节点，且每个节点最多有一个直接前驱和一个直接后继的非空数据结构。
(2)非线性结构：不满足线性结构的数据结构。
1.3线性表及其顺序存储结构
1.线性表的基本概念
线性结构又称线性表，线性表是最简单也是最常用的一种数据结构。
2.线性表的顺序存储结构
•元素所占的存储空间必须连续。
•元素在存储空间的位置是按逻辑顺序存放的。
3.线性表的插入运算
在第i个元素之前插入一个新元素的步骤如下：
步骤一：把原来第n个节点至第i个节点依次往后移一个元素位置。
步骤二：把新节点放在第i个位置上。
步骤三：修正线性表的节点个数。
在最坏情况下，即插入元素在第一个位置，线性表中所有元素均需要移动。
4.线性表的删除运算
删除第i个位置的元素的步骤如下：
步骤一：把第i个元素之后不包括第i个元素的n-i个元素依次前移一个位置;
步骤二：修正线性表的结点个数。
1.4栈和队列
1.栈及其基本运算
(1)基本概念：栈是一种特殊的线性表，其插入运算与删除运算都只在线性表的一端进行，也被称为“先进后出”表或“后进先出”表。
•栈顶：允许插入与删除的一端。
•栈底：栈顶的另一端。
•空栈：栈中没有元素的栈。
(2)特点。
•栈顶元素是最后被插入和最早被删除的元素。
•栈底元素是最早被插入和最后被删除的元素。
•栈有记忆作用。
•在顺序存储结构下，栈的插入和删除运算不需移动表中其他数据元素。
•栈顶指针top动态反映了栈中元素的变化情况
(3)顺序存储和运算：入栈运算、退栈运算和读栈顶运算。
2.队列及其基本运算
(1)基本概念：队列是指允许在一端进行插入，在另一端进行删除的线性表，又称“先进先出”的线性表。
•队尾：允许插入的一端，用尾指针指向队尾元素。
•排头：允许删除的一端，用头指针指向头元素的前一位置。
(2)循环队列及其运算。
所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。
入队运算是指在循环队列的队尾加入一个新元素。
当循环队列非空(s=1)且队尾指针等于队头指针时，说明循环队列已满，不能进行人队运算，这种情况称为“上溢”。
退队运算是指在循环队列的队头位置退出一个元素并赋给指定的变量。首先将队头指针进一，然后将排头指针指向的元素赋给指定的变量。当循环队列为空(s=0)时，不能进行退队运算，这种情况称为“下溢”。
1.5线性链表
在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。
在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域;另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。
1.6树和二叉树
1.树的基本概念
树是简单的非线性结构，树中有且仅有一个没有前驱的节点称为“根”，其余节点分成m个互不相交的有限集合T1，T2，…，T}mm，每个集合又是一棵树，称T1，T2，…，T}mm为根结点的子树。
•父节点：每一个节点只有一个前件，无前件的节点只有一个，称为树的根结点(简称树的根)。
•子节点：每～个节点可以后多个后件，无后件的节点称为叶子节点。
•树的度：所有节点最大的度。
•树的深度：树的最大层次。
2.二叉树的定义及其基本性质
(1)二叉树的定义：二叉树是一种非线性结构，是有限的节点集合，该集合为空(空二叉树)或由一个根节点及两棵互不相交的左右二叉子树组成。可分为满二叉树和完全二叉树，其中满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。二叉树具有如下两个特点：
•二叉树可为空，空的二叉树无节点，非空二叉树有且只有一个根结点;
•每个节点最多可有两棵子树，称为左子树和右子树。
(2)二叉树的基本性质。
性质1：在二叉树的第k层上至多有2k-1个结点(k≥1)。
性质2：深度为m的二叉树至多有2m-1个结点。
性质3：对任何一棵二叉树，度为0的结点(即叶子结点)总是比度为2的结点多一个。
性质4：具有n个结点的完全二叉树的深度至少为[log2n]+1，其中[log2n]表示log2n的整数部分。
3.满二叉树与完全二叉树
(1)满二叉树：满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。满二叉树在其第i层上有2i-1个结点。
从上面满二叉树定义可知，二叉树的每一层上的结点数必须都达到最大，否则就不是满二叉树。深度为m的满二叉树有2m-1个结点。
(2)完全二叉树：完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
如果—棵具有n个结点的深度为k的二叉树，它的每—个结点都与深度为k的满二叉树中编号为1～n的结点——对应。
3.二叉树的存储结构
二叉树通常采用链式存储结构，存储节点由数据域和指针域(左指针域和右指针域)组成。二叉树的链式存储结构也称二叉链表，对满二叉树和完全二叉树可按层次进行顺序存储。
4.二叉树的遍历
二叉树的遍历是指不重复地访问二叉树中所有节点，主要指非空二叉树，对于空二叉树则结束返回。二叉树的遍历包括前序遍历、中序遍历和后序遍历。
(1)前序遍历。
前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树;并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。前序遍历描述为：若二叉树为空，则执行空操作;否则①访问根结点;②前序遍历左子树;③前序遍历右子树。
(2)中序遍历。
中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树;并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。中序遍历描述为：若二叉树为空，则执行空操作;否则①中序遍历左子树;②访问根结点;③中序遍历右子树。
(3)后序遍历。
后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。后序遍历描述为：若二叉树为空，则执行空操作;否则①后序遍历左子树;②后序遍历右子树;③访问根结点。
1.7查找技术
(1)顺序查找：在线性表中查找指定的元素。
(2)最坏情况下，最后一个元素才是要找的元素，则需要与线性表中所有元素比较，比较次数为n。
(2)二分查找：二分查找也称折半查找，它是一种高效率的查找方法。但二分查找有条件限制，它要求表必须用顺序存储结构，且表中元素必须按关键字有序(升序或降序均可)排列。对长度为n的有序线性表，在最坏情况下，二分查找法只需比较log2n次。
1.8排序技术
(1)交换类排序法。
•冒泡排序：通过对待排序序列从后向前或从前向后，依次比较相邻元素的排序码，若发现逆序则交换，使较大的元素逐渐从前部移向后部或较小的元素逐渐从后部移向前部，直到所有元素有序为止。在最坏情况下，对长度为n的线性表排序，冒泡排序需要比较的次数为n(n-1)/2。
•快速排序：是迄今为止所有内排序算法中速度最快的一种。它的基本思想是：任取待排序序列中的某个元素作为基准(一般取第一个元素)，通过一趟排序，将待排元素分为左右两个子序列，左子序列元索的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。最坏情况下，即每次划分，只得到一个序列，时间效率为O(n2)。
(2)插人类排序法。
•简单插入排序法：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。在最坏情况下，即初始排序序列是逆序的情况下，比较次数为n(n-1)/2，移动次数为n(n-1)/2。
•希尔排序法：先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序。待整个序列中的元素基本有序(增量足够小)时，再对全体元素进行一次直接插入排序。
(3)选择类排序法。
•简单选择排序法：扫描整个线性表。从中选出最小的元素。将它交换到表的最前面;然后对剩下的子表采用同样的方法，直到子表空为止。最坏情况下需要比较n(n-1)/2次。
•堆排序的方法：首先将一个无序序列建成堆;然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，将该子序列调整为堆。反复做步骤②，直到剩下的子序列空为止。在最坏情况下，堆排序法需要比较的次数为0(nlog2n)
第2章
程序设计基础
2.1程序设计方法与风格
(1)设计方法：指设计、编制、调试程序的方法和过程，主要有结构化程序设计方法、软件工程方法和面向对象方法。
(2)设计风格：良好的设计风格要注重源程序文档化、数据说明方法、语句的结构和输入输出。
2.2结构化程序设计
1.结构化程序设计的原则
结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。
(1)自顶向下：即先考虑总体，后考虑细节;先考虑全局目标，后考虑局部目标。
(2)逐步求精：对复杂问题，应设计一些子目标做过渡，逐步细化。
(3)模块化：把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块;
(4)限制使用GOT0语句。
2.结构化程序的基本结构与特点
(1)顺序结构：自始至终严格按照程序中语句的先后顺序逐条执行，是最基本、最普遍的结构形式。
(2)选择结构：又称为分支结构，包括简单选择和多分支选择结构。
(3)重复结构：又称为循环结构，根据给定的条件，判断是否需要重复执行某一相同的或类似的程序段。
结构化程序设计中，应注意事项：
(1)使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑。
(2)选用的控制结构只准许有一个人口和一个出口。
(3)程序语言组成容易识别的块，每块只有一个入口和一个出口。
(4)复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现。
(5)语言中所没有的控制结构，应该采用前后一致的方法来模拟。
(6)尽量避免GOT0语句的使用。
2.3面向对象的程序设计
面向对象方法的本质是主张从客观世界固有的事物出发来构造系统，强调建立的系统能映射问题域。
•对象：用来表示客观世界中任何实体，可以是任何有明确边界和意义的东西。
•类：具有共同属性、共同方法的对象的集合。
•实例：一个具体对象就是其对应分类的一个实例。
•消息：实例间传递的信息，它统一了数据流和控制流。
•继承：使用已有的类定义作为基础建立新类的定义技术。
•多态性：指对象根据所接受的信息而作出动作，同样的信息被不同的对象接收时有不同行动的现象。面向对象程序设计的优点：与人类习惯的思维方法一致、稳定性好、可重用性好、易于开发大型软件产品、可维护性好。
第三篇：计算机等级考试二级ACCESS数据库基础知识
计算机等级考试二级ACCESS数据库基础知识
1.1 数据库基础知识
1.1.1 计算机数据管理的发展 一．数据与数据处理 数据：
是指存储在某种 媒体上能够识别的物理符号。数据处理：
是指将数据转换成信息的过程。
从数据处理的角度而言，信息是一种被加工成特定形式的数据，这种数据形式对于数据接受者来说是有意义的。二．计算机数据管理
计算机数据管理 是指对数据的 分类、组织、编码、存储、检索和维护。计算机数据管理 发展的几个阶段： 1 ．人工管理 世纪 50 年代中期以前，计算机主要用于科学计算。
外部存储器 只有纸带、卡片、磁带，无像磁盘这样的可以随机访问、直接存取的外部存储设备。软件的状况 是没有操作系统，没有专门管理数据的软件，数据由计算或处理它的程序自行携带。数据管理任务，包括存储结构、存储方法、输入/输出方式等完全由程序设计者负责。特点：
数据与程序不具有独立性，一组数据对应一组程序。数据不能长期保存。
一个程序中的数据无法被其他程序使用。程序之间存在大量重复数据，数据冗余大。2 ．文件系统 世纪 50 年代后期到 60 年代中期。计算机不仅用于科学计算 , 而且还用于大量的数据处理。直接存储设备，高级语言，操作系统。
程序和数据有一定的独立性，数据文件可以长期保存。
数据和程序相互依赖。数据文件是为满足特定的业务，或某部门的专门需要而设计，服务于某一特定的应用程序。
同一数据项可能重复出现在多个文件中，数据冗余度大。数据容易造成不一致。3 ．数据库系统 世纪 60 年代后期。计算机用于管理的规模更加庞大，应用越来越广泛。同时多种应用、多种语言共享数据集合的要求越来越强烈。
标志： 1968年IBM的 IMS 是一个层次模型数据库。1969年美国数据系统语言协会公布的 DBTG 报告，对研制开发网状数据库系统起到了推动作用。自1970年 IBM 公司的研究成果奠定了关系数据库理论基础。数据库技术的主要目的：
有效地 管理和存储 大量的数据资源，包括：提高数据的 共享性，使多个用户能够同时访问数据库中的数据； 减少数据冗余，以提高数据的 一致性和完整性 ；提高数据与程序的 独立性，从而 减少 应用程序的 开发和维护代价。4 ．分布式数据库 20 世纪 70 年代以后，网络技术的发展为数据库提供了分布式的运行环境，从主机—终端结构发展到 C/S（客户 / 服务器）系统结构。
数据库技术与网络技术的结合分为 紧密结合 与 松散结合 两大类。
分布式数据库系统又分为 物理上分布、逻辑上集中 的分布式数据结构和 物理上分布、逻辑上分布 的分布式数据库结构两种。
物理上分布、逻辑上集中的分布式数据结构是逻辑上统一、地域上分布的数据集合，是计算机网络环境中各个节点局部数据库的逻辑集合，同时受分布式数据库管理系统的统一控制和管理。物理上分布、逻辑上分布 的分布式数据库结构是把多个集中式数据库系统通过网络连接起来，各个节点上计算机可以利用网络通信功能访问其他节点上的数据库资源。5 ．面向对象数据库系统
面向对象数据库吸收了面向对象程序设计方法的核心概念和基本思想，采用面向对象的观点来 描述现实世界实体（对象）的逻辑组织、对象之间的限制和联系等。克服了传统数据库的局限性，能够自然地存储复杂的数据对象以及这些对象之间的关系，从而大幅度地提高了 数据库管理效率、降低了用户使用的复杂性。1.1 数据库基础知识 1.1.2 数据库系统 一．有关数据库的概念 1 ．数据（Data）
描述事物的符号记录。2 ．数据库（Data Base）
存储在计算机存储设备中的、结构化的相关数据的集合。它不仅包括描述事物的数据本身，而且包括相关事物之间的关系。
数据库中的数据不只是面向某项特定的应用，而是面向多种应用，可以被多个用户、多个应用程序共享。3 ．数据库应用系统
利用数据库系统资源开发的面向某一类实际应用的软件系统。如：学生管理系统、人事管理系统等。．数据库管理系统（DataBase Management System,DBMS）
位于用户与操作系统之间的数据管理软件，为数据库的建立、使用和维护而配置的软件。使用户能方便地定义数据和操纵数据库，并能报证数据的安全性、完整性、多用户对数据的并发使用及发生故障后的系统恢复。．数据库系统（DataBase System, DBS）
指引进数据库技术后的计算机系统，能实现有组织地、动态地存储大量相关数据、提供数据处理和信息资源共享的便利手段。有 5 部分：硬件系统、数据库集合、数据库管理系统和相关软件、数据库管理员（DataBase Administrator , DBA）和用户。二．数据库系统的特点 1 ．实现数据共享，减少冗余 2 ．采用特定的数据模型 3 ．具有较高的数据独立性 4 ．有统一的数据控制功能 三．数据库管理系统
支持用户对数据库的基本操作，是数据库系统的核心软件。主要目标是使数据成为 方便用户使用 的资源，易于为各种用户所 共享，并增进数据的 安全性、完整性和可用性。● 功能主要包括： 1．数据定义
定义数据库的结构。
2.数据操纵
更新（插入、修改、删除）和检索。
3.数据库运行管理
对数据库进行 并发控制、安全性检查、完整性约束条件的检查和执行 及 数据库的内部维护（索引、数据字典的自动维护）等。
4.数据组织、存储和管理
采用统一的组织方式，并提高效率。
5.数据库的建立和维护
初始数据的输入与数据转存。
数据库的转储与恢复、数据库的重组与重构、性能的监视与分析。
6.数据通信接口
提供与其他软件系统进行通信的功能。
● 4 部分组成：
■ 数据定义语言及翻译处理程序
■ 数据操纵语言及其编译（或解释）程序
■ 数据库运行控制程序
■ 实用程序
1.1 数据库基础知识
1.1.3 数据模型
数据模型就是从现实世界到机器世界的一个中间层次。是数据管理系统用来表示实体及实体间联系的方法。
一．实体描述．实体
客观存在并相互区别的事物成为实体。如：学生、教师、课程。．实体的属性
描述实体的特性。如学生实体用学号、姓名、性别等属性描述。．实体集和实体型
属性值的集合表示一个实体，而属性的集合表示一种实体的类型，称为实体型。同类型的实体的集合，称为实体集。
二．实体间联系及种类
实体之间的对应关系称为联系。如：一个学生可以选修多门课程，同一门课程可以由多名教师讲授。
有三种类型：．一对一联系
如：人事部门的教师表和财务部门的工资表之间就存在一对一联系。．一对多联系
如：部门表与教师表之间就存在一对多的联系。．多对多联系
如：学生表和课程表之间存在多对多的联系。
三．数据模型简介
数据模型是数据库管理系统用来表示实体间联系的方法。
任何一个数据库管理系统都是基于某种数据模型的。数据管理系统所支持的数据模型有三种：层次模型、网状模型、关系模型。．层次模型
用树型结构表示各类实体以及实体之间的联系。典型代表： IBM 的 IMS。
（1）有且仅有一个节点无双亲，这个节点称为“根节点”。
（2）其他节点有且仅有一个双亲。
特点：对一对多的层次关系描述非常自然、直观、容易理解，但不能直接表示出多对多的联系。．网状模型
（1）允许一个以上的节点无双亲。
（2）一个节点可以有多于一个的双亲。
典型代表： DBTG 系统，也称 CODASYL 系统。
特点是：能直接表示非树型结构。．关系数据模型
IBM E.F.Codd 于 1970 首次提出。
用二维表结构来表示实体以及实体间联系的模型。
特点是：理论基础完备、模型简单、说明性的查询语言和使用方便。
1.2 关系数据库
1.2.1 关系数据模型
一．关系术语
．关系
一个关系就是一个二维表，每个关系有一个关系名。在 Access 中，一个关系存储为一个表，具有一个表名。
对关系的描述称为 关系模式，一个关系模式对应一个关系的结构。其格式为：
关系名（属性名 1，属性名 2，…，属性名 n）
在 Access 中：
表名（字段名 1，字段名 2，…，字段名 n）．元组
二维表（关系）中的每一行。对应在表中为记录。．属性
二维表（关系）中的每一列。对应在表中为字段。．域
属性的取值范围。如：性别只能取“男”和“女”。．关键字
唯一地标识一元组的属性或属性集合。如：教师表中的编号。在 Access 中，主关键字和候选关键字就起唯一标识一个元组的作用。．外部关键字
如果一个表的字段不是本表的主关键字，而是另外一个表的主关键字和候选关键字，这个字段（属性）就称为外关键字。
二．关系的特点．关系必须规范化
是指关系模型中的每一个关系模式都必须满足一定的要求。最基本的要求是每个属性必须是不可分割的数据单元，即表中不能再包含表。．在同一个关系中不能出现相同的属性名。．关系中不允许有完全相同的元组，即冗余。4 ．在一个关系中元组的次序无关紧要。5 ．在一个关系中列的次序无关紧要。
1.2 关系数据库
1.2.2 关系运算
一．传统的集合运算．并
两个结构相同的关系的并是由属于这两个关系的元组组成的集合。．差
两个结构相同的关系 R 和 S 的差是由属于 R 但不属于 S 的元组组成的集合。．交
两个结构相同的关系 R 和 S 的交是由既属于 R 又属于 S 的元组组成的集合。二．专门的关系运算．选择
从关系中找出满足给定条件的元组的操作。．投影
从关系模式中指定若干属性组成新的关系。．联接
将两个关系模式拼接成为一个更宽的关系模式，生成的新的关系中包含满足联接条件的元组。．自然联接
在联接运算中，按照字段值对应相等为条件进行的联接操作。去掉重复字段。
1.3 数据库设计基础
1.3.1 数据库的设计步骤
一．设计原则 ．关系数据库的设计应遵从概念单一化“一事一地”的原则．避免在表之间出现重复字段 ．表中的字段必须是原始数据和基本数据元素．用外部关键字保证有关联的表之间联系
二．设计步骤．需求分析
（1）信息需求
（2）处理需求
（3）安全性和完整性需求．确定需求的表
遵从概念单一化“一事一地”的原则，即一个表描述一个实体或实体间的一种联系，并将这些信息分成各种基本实体。．确定所需字段
（1）每个字段直接和表的实体相关
（2）以最小的逻辑单位存储信息
（3）表中的字段必须是原始数据
（4）确定主关键字字段．确定联系
对于一对多的联系，可以将其中“一方”表的主关键字放到“多方”表中作为外关键字。“一方”用索引关键字，“多方”使用普通索引关键字。
对于一对一的联系，两个表中使用同样的主关键字字段。
对于多对多的联系，为了避免数据重复，一般建立第三个表，把多对多的联系分解两个一对多的联系。这个第三个表可以看成纽带。纽带表不一定需要自己的主键，如果需要，可以将它所联系的两个表的主关键字做为组合关键字指定为主关键字。．设计求精
检查可能存在的缺陷和需要改进的地方，这些缺陷可能会使数据难以使用和维护。
（1）是否忘记了字段？
（2）是否存在大量空白字段？
（3）是否包含了同样字段的表？
（4）表中是否带有大量不属于某实体的字段？
（5）是否在某个表中重复输入同样的数据？
（6）是否为每个表选择了合适的主关键字？
（7）是否有字段很多而记录很少的表，并且许多记录中的字段值为空？
1.4 SQL 基本命令
SQL（Structure Query Language，结构化查询语言）是在数据库系统中应用广泛的数据库查询语言，它包括了数据定义、查询、操纵和控制 4 种功能。
SQL 中的两个基本概念：
基本表：本身独立存在的表。
视图：从一个或多个基本表导出的表。它本身不独立存储在数据库中，即数据库中存放视图的定义，而不存放视图对应的数据。
1.4.1 SQL 基本语句
最常见的 SQL 语句是 SELECT。
基本格式：
SELECT [ALL/DISTINCT] *|< 字段列表 >
FROM < 表名 > [WHERE < 条件表达式 >]
[ORDER BY < 列名 > {[ASC|DESC]}]
例：在 Access 中，在教师表中查询姓名为“王”的教师，并按照姓名升序排列。命令为：
SELECT * FROM 教师 WHERE 姓名 LIKE “ 王 %” ORDER BY 姓名 ASC 1.5 Access 简介
Access 是一种关系型的桌面数据库管理系统，是 Microsoft Office 套件产品之一。
1992 年 11 月推出 Access 1.0，Microsoft 先后推出 2.0，7.0/95，8.0/97，9.0/2000，10.0/2002，直到 Access 2003。
特点： ．具有方便实用的强大功能。．可以利用各种图例快速获取数据。．可以利用报表设计工具，方便生成报表。．能处理多种数据类型。．采用 OLE 技术，能方便创建和编辑多媒体数据库。．支持 ODBC 标准的 SQL 数据库的数据。．设计过程自动化，大大提高了数据库的工作效率。．具有较好的集成开发环境。．提供了断点设置、单步执行等调试功能。．与 Internet/Intranet 的集成。．可以将数据库应用程序的建立移进用户环境，并最终使用户和应用程序开发者之间的关系淡化。
数据库的系统结构：
Access 数据库由数据库对象和组两部分组成，如图 1-2 所示。其中对象分为 7 种：表、查询、窗体、报表、数据访问页、宏、模块。
表是数据库的核心与基础，存放中数据库中的全部数据。报表、查询和窗体都是从数据库中获取数据信息，以实现用户的某一特定的需要。
表是用来存储数据的对象，是数据库的核心与基础。表中的列为字段，行为记录。
查询是用来操作数据库中的记录对象，利用它可以按照一定的条件或准则从一个或多个表中筛选出需要操作的字段，并可以把它们集中起来，形成所谓的动态数据集，并显示在一个虚拟的数据表窗口中。
窗体：数据库与用户进行交互操作的界面。其数据源可以是表或查询。
报表：数据的输出方式，可以将数据库中需要的数据提取出来进行分析、整理和计算，并将数据以格式化的方式打印输出。
数据访问页：是一种特殊的 Web 页，用户可以在此 Web 页与 Access 数据库中的数据进行联接，查看、修改 Access 数据库中的数据。
宏：一系列操作的集合。
模块：将 Visual Basic for Application 声明和过程作为一个单元进行保存的集合。
1.6 启动和关闭 Access 1.6.1 启动 Access
“开始 / 程序 /Microsoft Access”
1.6 启动和关闭 Access 1.6.2 关闭 Access 4 种方法：
（1）单击 Access 右上角的“关闭”按钮
（2）选择“文件”菜单中的“退出”命令
（3）使用 Alt+F4 快捷键
（4）使用 Alt+F+X 快捷键
一、填空题
1.计算机数据管理的发展分 _______________________________________ 等几个阶段。．数据库技术的主要目的是有效地管理和存储大量的数据资源，包括：_____________，使多个用户能够同时访问数据库中的数据； ______________，以提高数据的一致性和完整性；___________________，从而减少应用程序的开发和维护代价。．数据库技术与网络技术的结合分为 _____________ 与 _____________ 两大类。.分布式数据库系统又分为 ____________________ 的分布式数据库结构和 ______________________ 的分布式数据库结构两种。．数据库系统的 5 个组成部分： _________________________________________________。． 实体之间的对应关系称为联系，有如下三种类型： _______________________________。．任何一个数据库管理系统都基于某种数据模型的。数据库管理系统所支持的数据模型有三种： ___________________________。．两个结构相同的关系 R 和 S 的 _______ 是由属于 R 但不属于 S 的元组组成的集合。． SQL（Structure Query Language，结构化查询语言）是在数据库系统中应用广泛的数据库查询语言，它包括了 _____________________________4 种功能。.Access 数据库由数据库对象和组两部分组成。其中对象分为 7 种： ___________________。
二、选择题 ．下列说法错误的是（）。
A 人工管理阶段程序之间存在大量重复数据，数据冗余大。
B 文件系统阶段程序和数据有一定的独立性，数据文件可以长期保存。
C 数据库阶段提高了数据的共享性，减少了数据冗余。
D 上述说法都是错误的。． 从关系中找出满足给定条件的元组的操作称为（）。
A ．选择
B ．投影
C ．联接
D ．自然联接
3.关闭 Access 可以方法不正确的是（）。
A ．选择“文件”菜单中的“退出”命令。
B ．使用 Alt+F4 快捷键。
C ．使用 Alt+F+X 快捷键。
D ．使用 Ctrl+X 快捷键。．数据库技术是从 20 世纪（）年代中期开始发展的。
A.60
B.70
C.80
D.90 ．使用 Access 按用户的应用需求设计的结构合理、使用方便、高效的数据库和配套的应用程序系统，属于一种（）。
A.数据库
B.数据库管理系统
C.数据库应用系统
D.数据模型．二维表由行和列组成，每一行表示关系的一个（）。
A.属性
B.字段
C.集合 D.记录．数据库是（）。
A.以—定的组织结构保存在辅助存储器中的数据的集合。
B.一些数据的集合。
C.辅助存储器上的一个文件。
D.磁盘上的一个数据文件。．关系数据库是以（）为基本结构而形成的数据集合。
A．数据表
B．关系模型
C．数据模型
D．关系代数 9 ．关系数据库中的数据表（）。
A.完全独立，相互没有关系。
B.相互联系，不能单独存在。
C.既相对独立，又相互联系。
D.以数据表名来表现其相互间的联系。10 ．以下叙述中，正确的是（）。
A.Access 只能使用菜单或对话框创建数据库应用系统。
B.Access 不具备程序设计能力。
C.Access 只具备了模块化程序设计能力。
D.Access 具有面向对象的程序设计能力，并能创建复杂的数据库应用系统。
答案 填空题
1．人工管理、文件系统、数据库系统、分布式数据库、面向对象数据库系统
2．提高数据的共享性、减少数据冗余、提高数据与程序的独立性
3．紧密结合、松散结合
4．物理上分布、逻辑上集中；物理上分布、逻辑上分布
5．硬件系统、数据库集合、数据库管理系统和相关软件、数据库管理员（DataBase Administrator , DBA）和用户。
6．一对一联系、一对多联系、多对多联系。
7．层次模型、网状模型、关系模型。
8．差
9．数据定义、查询、操纵和控制
10.表、查询、窗体、报表、数据访问页、宏、模块。
选择题
D A D A B D A B C D
第四篇：全国计算机等级考试二级公共基础知识模拟试题及解析
全真模拟试卷(1)
(1)栈和队列的共同特点是
A)都是先进先出 B)都是先进后出
C)只允许在端点处插入和删除元素 D)没有共同点
(2)已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是
A)acbed B)decab C)deabc D)cedba
(3)链表不具有的特点是
A)不必事先估计存储空间 B)可随机访问任一元素
C)插入删除不需要移动元素 D)所需空间与线性表长度成正比
(4)结构化程序设计的3种结构是
A)顺序结构、选择结构、转移结构 B)分支结构、等价结构、循环结构
C)多分支结构、赋值结构、等价结构 D)顺序结构、选择结构、循环结构
(5)为了提高测试的效率，应该
A)随机选取测试数据 B)取一切可能的输入数据作为测试数据
C)在完成编码以后制定软件的测试计划 D)集中对付那些错误群集的程序
(6)算法的时间复杂度是指
A)执行算法程序所需要的时间 B)算法程序的长度
C)算法执行过程中所需要的基本运算次数 D)算法程序中的指令条数
(7)软件生命周期中所花费用最多的阶段是
A)详细设计 B)软件编码 C)软件测试 D)软件维护
(8)数据库管理系统DBMS中用来定义模式、内模式和外模式的语言为
A)C B)Basic C)DDL D)DML
(9)下列有关数据库的描述，正确的是
A)数据库是一个DBF文件 B)数据库是一个关系
C)数据库是一个结构化的数据集合 D)数据库是一组文件
(10)下列有关数据库的描述，正确的是
A)数据处理是将信息转化为数据的过程
B)数据的物理独立性是指当数据的逻辑结构改变时，数据的存储结构不变
C)关系中的每一列称为元组，一个元组就是一个字段
D)如果一个关系中的属性或属性组并非该关系的关键字，但它是另一个关系的关键字，则称其为本关系的外关键字
(11)算法的基本特征是可行性、确定性、【1】 和拥有足够的情报。
(12)在长度为n的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为 【2】。
(13)在面向对象的程序设计中，类描述的是具有相似性质的一组 【3】。
(14)通常，将软件产品从提出、实现、使用维护到停止使用退役的过程称为 【4】。
(15)数据库管理系统常见的数据模型有层次模型、网状模型和 【5】 3种。
全真模拟试卷(1)解析
1、解析：栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种“后进先出”的线性表;而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种“先进先出”的线性表。
2、解析： 依据后序遍历序列可确定根结点为c;再依据中序遍历序列可知其左子树由deba构成，右子树为空;又由左子树的后序遍历序列可知其根结点为e，由中序遍历序列可知其左子树为d，右子树由ba构成，如下图所示。求得该二叉树的前序遍历序列为选项D)。
3、解析： 链表采用的是链式存储结构，它克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放;它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。但是链式存储结构也有不足之处：① 每个结点中的指针域需额外占用存储空间;② 链式存储结构是一种非随机存储结构。
4、解析： 顺序结构、选择结构和循环结构(或重复结构)是结构化程序设计的3种基本结构。
5、解析： 测试的目的是发现软件中的错误。经验表明，程序中存在错误的概率与该程序中已发现的错误数成正比。这一现象说明，为了提高测试效率，测试人员应该集中对付那些错误群集的程序。
6、解析： 算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度。所谓算法的时间复杂度是指执行算
1法所需要的计算工作量;算法的空间复杂度一般是指执行这个算法所需要的内存空间。
7、解析： 软件生命周期分为软件定义、软件开发及软件运行维护3个阶段。本题中，详细设计、软件编码和软件测试都属于软件开发阶段;维护是软件生命周期的最后一个阶段，也是持续时间最长，花费代价最大的一个阶段，软件工程学的一个目的就是提高软件的可维护性，降低维护的代价。
8、解析： 选项A)、B)显然不合题意。数据定义语言(Data Definition Language，简称DDL)负责数据的模式定义与数据的物理存取构建;数据操纵语言(Data Manipulation Language，简称DML)负责数据的操纵，包括查询及增、删、改等操作。
9、解析： 数据库(Database，简称DB)是数据的集合，它具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序所共享。数据库中的数据具有“集成”、“共享”之特点。
10、解析： 数据处理是指将数据转换成信息的过程，故选项A)叙述错误;数据的物理独立性是指数据的物理结构的改变，不会影响数据库的逻辑结构，故选项B)叙述错误;关系中的行称为元组，对应存储文件中的记录，关系中的列称为属性，对应存储文件中的字段，故选项C)叙述错误。
11.解析： 算法是指解题方案的准确而完整的描述。它有4个基本特征，分别是可行性、确定性、有穷性和拥有足够的情报。
12.解析： 对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。
13.解析： 将属性、操作相似的对象归为类，也就是说，类是具有共同属性、共同方法的对象的集合。
14.解析： 软件产品从考虑其概念开始，到该软件产品不能使用为止的整个时期都属于软件生命周期。一般包括可行性研究与需求分析、设计、实现、测试、交付使用以及维护等活动。
15.解析： 数据库管理系统是位于用户与操作系统之间的一层系统管理软件，是一种系统软件，是用户与数据库之间的一个标准接口。其总是基于某种数据模型，可以分为层次模型、网状模型和关系模型。
全真模拟试卷(2)
(1)已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为
A)GEDHFBCA B)DGEBHFCA
C)ABCDEFGH D)ACBFEDHG
(2)树是结点的集合，它的根结点数目是
A)有且只有1 B)1或多于1 C)0或1 D)至少
2(3)如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是
A)e3,e1,e4,e2 B)e2,e4,e3,e
1C)e3,e4,e1,e2 D)任意顺序
(4)在设计程序时，应采纳的原则之一是
A)不限制goto语句的使用 B)减少或取消注解行
C)程序越短越好 D)程序结构应有助于读者理解
(5)程序设计语言的基本成分是数据成分、运算成分、控制成分和
A)对象成分 B)变量成分
C)语句成分 D)传输成分
(6)下列叙述中，不属于软件需求规格说明书的作用的是
A)便于用户、开发人员进行理解和交流
B)反映出用户问题的结构，可以作为软件开发工作的基础和依据
C)作为确认测试和验收的依据
D)便于开发人员进行需求分析
(7)下列不属于软件工程的3个要素的是
A)工具 B)过程
C)方法 D)环境
(8)单个用户使用的数据视图的描述称为
A)外模式 B)概念模式
C)内模式 D)存储模式
(9)将E-R图转换到关系模式时，实体与联系都可以表示成A)属性 B)关系
C)键 D)域
(10)SQL语言又称为
A)结构化定义语言 B)结构化控制语言
C)结构化查询语言 D)结构化操纵语言
(11)数据结构分为逻辑结构与存储结构，线性链表属于 【1】。
(12)在面向对象方法中，类之间共享属性和操作的机制称为 【2】。
(13)耦合和内聚是评价模块独立性的两个主要标准，其中 【3】 反映了模块内各成分之间的联系。
(14)一个项目具有一个项目主管，一个项目主管可管理多个项目，则实体“项目主管”与实体“项目”的联系属于 【4】 的联系。
(15)数据库设计分为以下6个设计阶段：需求分析阶段、【5】、逻辑设计阶段、物理设计阶段、实施阶段、运行和维护阶段。
全真模拟试卷(2)解析
1.解析： 利用前序和中序遍历的方法可以确定二叉树的结构，具体步骤如下：① 前序遍历的第一个结点A为树的根结点;② 中序遍历中A的左边的结点为A的左子树，A右边的结点为A的右子树;③ 再分别对A的左右子树进行上述两步处理，直到每个结点都找到正确的位置。
2.解析： 树是一个或多个结点组成的有限集合，其中一个特定的结点称为根，其余结点分为若干个不相交的集合。每个集合同时又是一棵树。树有且只有1个根结点。
3.解析： 由栈“后进先出”的特点可知：A)中e1不可能比e2先出，C)中e3不可能比e4先出，且e1不可能比e2先出，D)中栈是先进后出的，所以不可能是任意顺序。B)中出栈过程如图所示：
4.解析： 滥用goto 语句将使程序流程无规律，可读性差，因此A)不选;注解行有利于对程序的理解，不应减少或取消，B)也不选;程序的长短要依照实际情况而论，而不是越短越好，C)也不选。
5.解析： 程序设计语言是用于书写计算机程序的语言，其基本成分有以下4种，数据成分：用来描述程序中的数据。运算成分：描述程序中所需的运算。控制成分：用来构造程序的逻辑控制结构。传输成分：定义数据传输成分，如输入输出语言。
6.解析： 软件需求规格说明书(SRS，Software Requirement Specification)是需求分析阶段的最后成果，是软件开发中的重要文档之一。它有以下几个方面的作用：① 便于用户、开发人员进行理解和交流;② 反映出用户问题的结构，可以作为软件开发工作的基础和依据;③ 作为确认测试和验收的依据。
7.解析： 软件工程包括3个要素，即方法、工具和过程。方法是完成软件工程项目的技术手段;工具支持软件的开发、管理、文档生成;过程支持软件开发的各个环节的控制、管理。
8.解析： 选项A)正确，外模式是用户的数据视图，也就是用户所见到的数据模式;选项B)不正确，全局数据视图的描述称为概念模式，即数据库中全部数据的整体逻辑结构的描述;选项C)不正确，物理存储数据视图的描述称为内模式，即数据库在物理存储方面的描述;选项D)不正确，存储模式即为内模式。
9.解析： 数据库逻辑设计的主要工作是将E-R图转换成指定RDBMS中的关系模式。首先，从E-R图到关系模式的转换是比较直接的，实体与联系都可以表示成关系，E-R图中属性也可以转换成关系的属性。实体集也可以转换成关系。
10.解析： 结构化查询语言(Structured Query Language，简称SQL)是集数据定义、数据操纵和数据控制功能于一体的数据库语言。
11.解析： 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构;数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。
12.解析： 类是面向对象语言中必备的程序语言结构，用来实现抽象数据类型。类与类之间的继承关系实现了类之间的共享属性和操作，一个类可以在另一个已定义的类的基础上定义，这样使该类型继承了其超类的属性和方法，当然，也可以定义自己的属性和方法。
13.解析： 内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量，内聚是从功能角度来度量模块内的联系;耦合性是模块间互相连接的紧密程度的度量。
14.解析： 两个实体集间的联系实际上是实体集间的函数关系，这种函数关系可以有3种，即一对一(1∶1)的联系、一对多(1∶N)或多对一(N∶1)的联系和多对多(N∶N)的联系。
15.解析： 数据库设计分为以下6个设计阶段：需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、实施阶段及数据库运行和维护阶段。
全真模拟试卷(3)
(1)算法的空间复杂度是指
A)算法程序的长度 B)算法程序中的指令条数
C)算法程序所占的存储空间 D)执行过程中所需要的存储空间
(2)用链表表示线性表的优点是
A)便于随机存取 B)花费的存储空间较顺序存储少
C)便于插入和删除操作 D)数据元素的物理顺序与逻辑顺序相同
(3)数据结构中，与所使用的计算机无关的是数据的A)存储结构 B)物理结构
C)逻辑结构 D)物理和存储结构
(4)结构化程序设计主要强调的是
A)程序的规模 B)程序的效率
C)程序设计语言的先进性 D)程序易读性
(5)软件设计包括软件的结构、数据接口和过程设计，其中软件的过程设计是指
A)模块间的关系 B)系统结构部件转换成软件的过程描述
C)软件层次结构 D)软件开发过程
(6)检查软件产品是否符合需求定义的过程称为
A)确认测试 B)集成测试
C)验证测试 D)验收测试
(7)数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。下列图符名标识的图符不属于数据流图合法图符的是
A)控制流 B)加工
C)数据存储 D)源和潭
(8)应用数据库的主要目的是
A)解决数据保密问题 B)解决数据完整性问题
C)解决数据共享问题 D)解决数据量大的问题
(9)在数据库设计中，将E-R图转换成关系数据模型的过程属于
A)需求分析阶段 B)逻辑设计阶段
C)概念设计阶段 D)物理设计阶段
(10)在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是
A)数据库系统 B)文件系统
C)人工管理 D)数据项管理
(11)数据的逻辑结构有线性结构和 【1】 两大类。
(12)顺序存储方法是把逻辑上相邻的结点存储在物理位置 【2】 的存储单元中。
(13)一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件的 【3】。
(14)软件工程研究的内容主要包括： 【4】 技术和软件工程管理。
(15)关系操作的特点是 【5】 操作。
全真模拟试卷(3)解析
1.解析： 算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度。所谓算法的时间复杂度是指执行算法所需要的计算工作量;算法的空间复杂度一般是指执行这个算法所需要的内存空间。
2.解析： 链式存储结构克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放;它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。故链式存储结构下的线性表便于插入和删除操作。
3.解析： 数据结构概念一般包括3个方面的内容，数据的逻辑结构、存储结构及数据上的运算集合。数据的逻辑结构只抽象的反映数据元素之间的逻辑关系，而不管它在计算机中的存储表示形式。
4.解析： 结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、模块化及限制使用goto语句，总的来说可使程序结构良好、易读、易理解、易维护。
5.解析： 软件设计包括软件结构设计、数据设计、接口设计和过程设计。其中结构设计是定义软件系统各主要部件之间的关系;数据设计是将分析时创建的模型转化为数据结构的定义;接口设计是描述软件内部、软件和操作系统之间及软件与人之间如何通信;过程设计则是把系统结构部件转换成软件的过程性描述。
6.解析： 确认测试的任务是验证软件的功能和性能，以及其他特性是否满足需求规格说明定的各种需求;集成测试的主要目的是发现与接口有关的错误。
7.解析： 数据流图包括4个方面，即加工(转换)(输入数据经加工变换产生输出)、数据流(沿箭头方向传送数据的通道，一般在旁边标注数据流名)、存储文件(数据源)(表示处理过程中存放各种数据的文件)、源和潭(表示系统和环境的接口，属系统之外的实体)。不包括选项中的控制流。
8.解析： 数据库中的数据具有“集成”与“共享”的特点，亦即是数据库集中了各种应用的数据，进行统一构造与存储，而使它们可以被不同应用程序所使用，故选项C)正确。
9.解析： E-R模型即实体-联系模型，是将现实世界的要求转化成实体、联系、属性等几个基本概念，以及它们之间的两种联接关系。数据库逻辑设计阶段包括以下几个过程：从E-R图向关系模式转换，逻辑模式规范化及调整、实现规范化和RDBMS，以及关系视图设计。
10.解析： 人工管理阶段是在20世纪50年代中期以前出现的，数据不独立，完全依赖于程序;文件系统是数据库系统发展的初级阶段，数据独立性差;数据库系统具有高度的物理独立性和一定的逻辑独立性。
11.解析： 数据的逻辑结构有线性结构和非线性结构两大类。
12.解析： 常用的存储表示方法有4种，顺序存储、链式存储、索引存储、散列存储。其中，顺序存储方法是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中。
13.解析： 本题考查了继承的优点：相似的对象可以共享程序代码和数据结构，从而大大减少了程序中的冗余，提高软件的可重用性。
14.解析： 基于软件工程的目标，软件工程的理论和技术性研究的内容主要包括：软件开发技术和软件工程管理。软件开发技术包括：软件开发方法学、开发过程、开发工具和软件工程环境，其主体内容是软件开发方法学。软件工程管理包括：软件管理学、软件工程经济学，以及软件心理学等内容。
15.解析： 在关系操作中，所有操作对象与操作结果都是关系。而关系定义为元数相同的元组的集合。因此，关系操作的特点是集合操作。
第五篇：计算机VB二级公共基础知识总结
数据结构的基础知识
数据结构的定义:指数据对象及其相关关系和构造方法。
结构是指结点之间的关系，数据结构就是在结点的优先集合和关系的有限集合。
数据结构的逻辑结构是指结点和结点间的相互关系。
数据结构在计算机的存储内容，一般包括结点的值和结点间的关系，数据结构的存储形式就是数据的存储结构。
数据结构按逻辑关系的不同分为线形结构和非线性结构两大类，非线性又分为树形结构和图结构，树形结构又分为树结构和二叉树结构。2 线性表
线性表是最简单、最常用的一种数据结构，它是由相同类型的结点组成的有限序列。线性表最重要的性质是线性表中结点的相对位置是确定的。
线性表常用的运算有4种：查找运算、插入运算、删除运算和其他运算。
线性表的存储方式主要有：
1）顺序存储：能直接访问线性表中的任意一个结点。2）链接存储：用单链表存储线性表。3 栈和队列的含义
栈是只允许在同一端进行插入和删除运算的线性表。
队列是只允许在一端进行插入运算，另一端进行删除运算的线性表。4 数组和字符串的特点 数组是最常用的数据结构之一，一般用于描述顺序存储的线性表。数组有固定个数的元素组成，全部元素的类型相同，元素按照顺序存储。每个元素对应一个下标，数组元素按数组名和元素的下标引用，引用数组元素的下标个数称为数组的维数。最常用的是二维数组。5 树的基本概念、存储结构和遍历
树是一种多分支、多层次的数据结构，有一组结点组成。树是由一个结点或多个结点组成的有限集T，满足以下两个条件： 1）有一个特定的结点，称为根结点
2）其余的结点分成m个互不相交的有限集T0等，每个集合都是根结点的子树。
树的定义是递归的，即一棵树是由子树组成，子树由更小的子树构成。树的存储结构：树是非线性的结构，有多种实用的存储结构，最常用的是标准存储形式和带逆存储形式。
树的遍历方法有4种：树的前序遍历、树的后序遍历、树的层次遍历、访问树中所有的叶子特点。6 二叉树的基本概念及遍历
二叉树是一个有限的结点集合，该集合或者为空，或者有一个结点及其两棵树不相交的左右二叉子树组成。
二叉树的遍历：前序遍历，中序遍历、后序遍历。7二叉查找树
查找树便于链接存储，还能实现快速查找。或者为空，或者满足以下3个条件：A 该树根结点的左子树非空，其左子树所有结点的键值都小于该树根结点的键值。B该树根结点的右子树非空，其右子树所有结点的键值都大于该树根结点的键值C该树的根结点的左子树和右子树均为查找树。8 关于排序与查找，散列表
对于有N个结点的线性表，将结点中某些数据项的值按递增或递减的次序，重新排列线性表结点的过程，称为排序。
查找就是在案某种数据结构形式存储的数据集合中，找出满足指定条件的结点。
散列表又称杂凑表是一种非常实用的查找技术。由于查找码与结点在数据结构中的位置不存在确定关系，查找只能通过对查找码与结点的关键码的反复比较来实现。第二章 程序设计基础知识 1程序设计的方法与风格
程序设计的方法主要是结构化程序的设计，集体有面向数据流的方法和面向数据结构的方法。数据结构既影响程序处理的结构又影响程序处理的过程。
程序设计风格主要是指面向过程的程序设计和面向对象的程序设计。面向过程的程序设计主要是指根据事物本身的逻辑过程进行编程的一种方法，而面向对象的主要是强调程序的功能模块化，同时引入了继承、多态的概念，使程序易于编写和维护，最适合规模较大的软件。2 结构化的程序设计
结构化的程序（SP）设计采取自顶向下逐步求精的设计方法和单入口单出口的控制结构。其设计方法符合抽象和分解的原则。其控制结构使程序的静态结构和动态结构执行过程一致。3面向对象的设计方法及相关概念
面向对象方法是一种支持模块化设计和软件重用的编程方法。它把程序设计的主要活动集中在建立对象和对象之间的联系上，其基本思想是封装性和可扩展性。以软件设计的对象为基础。
对象：在计算机系统中，指一组属性以及这组属性上的专用操作的封装体。一个对象通常可由对象名，属性和操作3个部分组成。封装：是一种信息隐蔽技术，用户只能看见对象封装界面上的信息，对象的内部实现对用户是隐蔽的。其目的是使对象的使用者和生产者分离，使对象的定义和实现分开。
属性：对象的特性，是对象外观及行为的特征。
方法：对象所具有的功能。每一个对象的属性，只能通过特定的操作来存取或者修改，这种特定的操作就是方法。
继承：在某个类的层次关联中，不同的类共享属性和操作的一种机制。一个子类可以只有唯一的一个父亲，被称为单一继承，一个子类也可以由多个父亲，从多个父亲中继承特性，叫多重继承。
多态性：指同一个操作作用于不同对象可以有不同的解释，产生不同的执行结果。
动态绑定：在运行过程中，当一个对象发送信息请求服务时，要根据接收对象的具体情况将请求的操作与实现方法连接。
第三章 软件工程基础知识 1软件生存周期各阶段的任务
软件生存周期指软件定义、软件开发和软件维护等阶段组成的全过程。
A定义阶段;确定系统的逻辑模型，产生有需求规格说明书
B开发阶段：软件设计、编码和测试3部分。软件设计分为概要设计和详细设计。编码是用某种程序语言为每个模块编写程序，产生的文档有程序清单。软件测试的任务是发现软件中的错误加以纠正。C维护阶段：适应外界环境的变化，或扩充其功能，改善其质量，产生的文档有维护计划和维护报告。2 软件设计的原则
1）抽象原则;抽象的最低层次就是实现该软件的源程序代码。过程抽象和数据抽象是常有的两种抽象手段。2）模块化原则：
3）信息隐蔽原则：对提高软件的可修改性、可测试性和可移植性有重要作用。4）模块独立的原则 3软件测试
软件测试的目的是尽可能多的发现软件产品中的错误和缺陷。白盒测试主要检查程序中的逻辑通路
黑盒测试主要检查程序的功能是否符合规格说明书的要求。大多的软件生产者使用Alpha测试和Beta测试，后者的开发者通常不在场。4软件开发工具和环境 软件工具是指用来辅助软件开发、运行、维护、管理和支持等过程中活动的软件。大多包括检测机制。
软件开发环境则把一组相关的工具集成在环境中，提供数据集成、控制集成和界面集成等机制。第四章 数据库的基础知识 1数据库
数据库：是存储在一起的相关数据的集合，能为各种用户共享，具有最下冗余度，数据间的联系密切，由较高的程序与数据独立性。数据库管理系统：指位于用户和操作系统之间的一层数据管理软件，为用户或应用程序提供访问数据库的方法，包括数据库的建立、查询、更新及各种数据控制。它是DBS的核心部分。
数据库系统：是实现有组织地，动态的存储大量关联数据，方便多用户访问的计算机软、硬资源组成的系统，即采用了数据库技术的计算机系统。2 数据模型
常有的数据模型有两种：一种是独立于任何计算机系统的模型，完全不涉及信息在计算机系统中的表示，称为“概念数据模型”。最著名的模型是“实体联系E-R模型”。另一种数据模型直接面向数据库的逻辑数据结构，被称为“基本数据模型”。
基本数据模型主要有层次、网状、关系三种模型。层次模型时用树型结构来表示实体类型及实体间联系的数据模型。网状模型用丛结构表示，关系模型用表格结构表示实体集，用键表示实体间的联系。网状模型采用有向图，层次模型采用树，关系模型采用二维表。在搜索数据时，层次模型采用单向搜索法，网状模型采用可从任一结点开始且沿任何路径搜索，关系模型则是通过对关系进行运算实现的。3 关系代数
关系数据库的数据与更新操作必须遵循实体完整性规则、引用完整性原则、用户定义完整性原则。
关系代数是以集合代数为基础发展起来的，以关系为运算对象的一组高级运算的集合。
关系代数的5种基本操作;并、差、笛卡儿积、投影和选择。关系代数的4种组合操作;交、联接、自然联接和除法。
4在数据库中，用概念模式描述全部数据的整体逻辑结构，负责物理结构与逻辑结构的定义和修改的人员是数据库管理员。数据库管理系统提供的数据定义语言的功能是描述数据库的结构，为用户建立数据库提供手段。在人事管理系统中，规定工程师的基本工资和奖金不能超过1500元，这样的数据完整性约束条件称之为用户定义完整性。在关系数据库的逻辑设计阶段，需将E-R模型转换为关系数据模型。
点击咨询 