计算机三级数据库考点串讲剖析剖析.doc

数据库 一、基础知识 1．计算机系统的组成和应用领域。 计算机系统由(硬件)系统、(软件)系统两部份组成。 　　计算机的硬件基本上由五大部分组成：运算器、控制器、存储器、输入设备、输出设备。 软件系统分为(系统)软件、(应用)软件两部分。 计算机的应用领域包括什么? 　　1、科学计算 2、数据通信与数据处理、3、自动控制4、计算机辅助设计 5、计算机人工智能 2．计算机软件的基础知识。 软件系统分为(系统)软件、(应用)软件两部分 二、数据结构与算法 1．数据结构、算法的基本概念。 数据：是信息的载体，是指能够被计算机识别、存储和加工的信息的载体。 数据元素：是数据的基本单位，一个数据元素可以由一个或若干个数据项组成，在计算机程序中通常作为一个整体考虑和处理。 数据项: 数据的不可分割的最小单位。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。 数据元素与数据项的区别： 1、数据元素是数据的基本单位，它在计算机存储器上的映像是结点。 2、数据项是数据的最小标识单位，它在计算机存储器上的映像是数据域。 数据结构（data-structure）：是相互之间存在的一种或多种特定关系的数据元素的集合。它反映一个数据的内部构成，即一个数据由哪些成份构成，以什么方式构成，呈什么结构。 基本数据结构：线性结构、树、图、集合 数据结构的形式定义为：DS=（D，S） 如“复数”表示为：Complex=(C,R) 其中：C是含两个实数的集合{c1,c2},R是定义在集合上的一种关系{c1,c2}。 数据结构包含的三方面： 数据的逻辑结构、数据的物理存储结构和数据的运算。 算法的设计取决与数据的逻辑结构， 算法的实现取决与数据的物理存储结构。 数据的逻辑结构：是“数据结构”定义中的关系，指数据间的逻辑关系。包括：线性结构和非线性结构，其中非线性结构又包括：树型结构和网状结构。通常所说的数据结构就是指数据的逻辑结构。 Ａ、线性结构：除了第一个和最后一个元素以外，其他元素有且仅有一个直接前驱元素，有且仅有一个直接后继元素。 Ｂ、树型结构：是一种层次关系，数据元素只能与上一层中的一个数据元素相关，但可以和下一层的多个数据元素相关。 Ｃ、网状结构：任何两个数据元素间都可以相关。 数据的存储结构：是数据的逻辑结构的计算机存储器里的实现（亦称为映象），即数据元素及其关系在计算机中的表示。包括：顺序、链式、索引、散列等存储方式。 A：顺序存储结构：逻辑结构中相邻的数据元素在存储器中存放的位置是相邻的。 B：链式存储结构：逻辑结构中相邻的数据元素在存储器中存放的位置是不相邻的。是通过指针进行联系的。 数据运算：施加于数据的操作。 算法：是指解决特定问题的方法，是由若干条指令组成的有穷序列。 算法的基本特征： （1）输入：0个或多个输入； （2）输出：1个或多个输出； （3）有穷性：算法必须在有限步内结束；每步有限时间内完成。 （4）确定性：组成算法的操作必须无二义性。 （5）可行性：组成算法的操作必须能够在计算机上实现。 算法的分析：主要是算法复杂度的分析方法及其运用。 评价算法的标准：正确性，可读性，健壮性，效率与低存储要求。 2．线性表的定义、存储和运算。 线性表的定义： 线性表(linear list)是由n(n=0)个数据元素(结点) a1,a2,…,an组成的有限序列。 1）、数据元素的个数n定义为表的长度（n=0时为空表）。 2）、将非空的线性表（n0）记作:( a1,a2,…,an)。 3) 、数据元素ai(1=I=n)只是一个抽象符号,其具体含义在具体情况下是不同的。 线性表的基本操作: 1、存取操作：存取线性表中第i 个数据元素； 2、查找操作：在线性表中查找满足条件元素； 3、插入操作：在线性表的第i个元素之前插入一个新元素； 4、删除操作 ：删除线性表的第i个元素； 5、分解操作 ：将一个线性表拆分为多个线性表； 6、合并操作: 7、排序 线性表的存储结构：顺序表、链式存储 3．树形结构的定义、存储和运算。 树形结构是一种重要的非线性结构，讨论的是层次和分支关系。树是n个结点的有限集合，当n=0时，称为空树,在任一棵非空树中： （1）有且仅有一个称为根的结点。 （2）如果n1，除根结点外的其余结点可分成m(m0)个不相交的集合T1,T2,…,Tm,其中每一个集合都是一棵树。树T1,T2,…,Tm称为这个根结点的子树。 4．排序的基本概念和排序算法。 排序定义 将一组记录按某排序码递增或递减排列的过程，称为排序。内部排序：指的是待排序记录存放在计算机随机存储器进行的排序过程。外部排序：