数据库三级知识要点归纳_2012年9月全国计算机三级数据库知识要点.doc

2012年9月全国计算机三级数据库知识要点 一、基础知识 1．计算机系统的组成和应用领域。 计算机系统由(硬件)系统、(软件)系统两部份组成。 　　计算机的硬件基本上由五大部分组成：运算器、控制器、存储器、输入设备、输出设备。 软件系统分为(系统)软件、(应用)软件两部分。 计算机的应用领域包括什么? 　　1、科学计算 2、数据通信与数据处理、3、自动控制4、计算机辅助设计 5、计算机人工智能 2．计算机软件的基础知识。 软件系统分为(系统)软件、(应用)软件两部分 二、数据结构与算法 1．数据结构、算法的基本概念。 数据：是信息的载体，是指能够被计算机识别、存储和加工的信息的载体。 数据元素：是数据的基本单位，一个数据元素可以由一个或若干个数据项组成，在计算机程序中通常作为一个整体考虑和处理。 数据项: 数据的不可分割的最小单位。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。 数据元素与数据项的区别： 1、数据元素是数据的基本单位，它在计算机存储器上的映像是结点。 2存储器上的映像是数据域。 包括：顺序、链式、索引、散列等存储方式。 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)只是一个抽象符号,其具体含义在具体情况下是不同的。 3．树形结构的定义、存储和运算。 树形结构是一种重要的非线性结构，讨论的是层次和分支关系。树是n个结点的有限集合，当n=0时，称为空树,在任一棵非空树中： （1）有且仅有一个称为根的结点。 （2）如果n1，除根结点外的其余结点可分成m(m0)个不相交的集合T1,T2,…,Tm,其中每一个集合都是一棵树。树T1,T2,…,Tm称为这个根结点的子树。 4．排序的基本概念和排序算法。 排序定义 将一组记录按某排序码递增或递减排列的过程，称为排序。内部排序：指的是待排序记录存放在计算机随机存储器进行的排序过程。外部排序：在进行内部排序时还要访问外存。本节讨论内部排序 稳定与不稳定 对于具有同一排序码的多个记录来说，若采用的排序方法 稳定的排序方法 直接插入排序、冒泡排序、归并排序 不稳定的排序方法 直接选择排序、希尔排序、快速排序、堆排序 5 关键字:指的是数据元素中用以标识该数据元素的某个数据项的值，如学生成绩表中，学生可以同名，同分等，只有学号是各不相同的，一个学号就对应一个学生，所以学号是关键字。如果某数据元素只有一个数据项，那么该数据元素的值就是关键字。 检索方法包括：顺序查找；二分查找（又称折半查找）；索引查找（又称分块查找）；Hash查找（哈希表，散列表）。 三、操作系统 1．操作系统的基本概念、主要功能和分类。 操作系统可分为(批处理操作系统)、(分时操作系统)、(实时操作系统)三种操作系统。个人、网络、分布式操作系统。 操作系统的特征：(并发)、(资源共享)、(虚拟)、(异步)。 操作系统的五大功能(处理机管理)、(设备管理)、(存储器管理)、(文件管理)、(提供友好的用户接口)。 操作系统发展的过程：(无操作系统)、(单道批处理系统)、(多道批处理系统)、(分时系统)、(实时系统)、(网络操作系统)、(分布式系统)。 2．进程、线程、进程间通信的基本概念。 进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，进程是系统进行资源分配的一个独立的单位，进程是动态产生， 动态消亡的，每一个进程都有一个数据结构