《计算机二级考试之数据库重点知识.doc》由会员分享，可在线阅读，更多相关《计算机二级考试之数据库重点知识.doc（14页珍藏版）》请在三一办公上搜索。
1、二级公共基础知识第一部分 数据结构(5-6个题目，占10分)*1.所谓算法是指解题方案的准确而完整的描述。严格来说，一个算法必须具有以下五个主要特征：n 有穷性 确定性 可行性 输入 输出（或说成：拥有足够的情报 ）2.算法的组成要素n 算法中对数据的运算和操作及算法的控制结构3.算法设计基本方法n 列举法 归纳法 递推 递归 减半递推 回溯法*4.算法的复杂度可分为时间复杂度和空间复杂度，是衡量算法优劣的量度。（1）算法的时间复杂度：算法的时间复杂度是指执行算法所需要的工作量。一般情况下，算法的时间复杂度为算法中的基本操作重复执行的次数。是问题规模n的某个函数f(n)。（2）算法的空间复杂度
2、：算法的空间复杂度是指执行这个算法所需要的内存空间。5.数据结构的定义 是指相互有关联的数据元素的集合。（一定要注意是数据元素的集合，不是数据的集合）*6. 数据结构主要研究三个方面的问题： 1) 逻辑结构是各数据元素之间的逻辑关系。它与在计算机中的存储位置无关，是独立于计算机的。2)在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。3)对各种数据结构进行的运算。7. 常见的存储结构：n 顺序存储结构 链式存储结构 索引存储结构 散列存储结构n 一般分为：线性存储和非线性存储8. 线性表的顺序存储结构用一组地址连续的存储单元依次存放线性表中的数据元素，即以“存储位置相邻”表
3、示“存储，表中第一个元素的存储位置作称作线性表的基地址。 所有数据元素的存储位置均可由第一个数据元素的存储位置得到 ADR(ai) = ADR(a1) + (i-1)C 基地址 一个数据元素所占存储量 9. 线性表的插入和删除运算最坏的时间复杂度为O(n-1),最好为O(o).10. 栈是限定仅在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入，也是最后被删除的元素。栈是一种后进先出的线性表。通常用指针top指示栈顶位置，用指针bottom指示栈底位置。11. 栈的操作有：n 入栈：
4、在栈顶位置插入一个新元素，栈顶指针top加1。n 退栈：取出栈顶元素并赋值给一个指定的变量，栈顶指针top减1。n 取栈顶元素：将栈顶元素的值赋给一个指定的变量，不删除栈顶元素，栈顶指针不变。12. 如果某栈的入栈顺序是ABCDEF，则出栈顺序不可能是哪个（C） （此类型的题目一定要会推导）A、DCEFBA B、ABCDEF C、EDFCAB D、CBAEDF13. 队列是一种先进先出的线性表，它只允许在表的一端插入元素(队尾)，在另一端删除元素(队头)。通常定义头指针front指向队头元素的前一个位置，定义尾指针rear指向队尾元素的位置。队列是一种先进先出的数据结构。14. 循环队列是将队
5、列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。容量的计算： *当rearfront时，元素个数rearfront ；*当rear1时，其余的结点可分为m个互不相交的子集T1,T2,Tm，其中每个有限子集本身又是一棵树。*22. 树的的几个重要术语： 树的度 叶节点 双亲、孩子和兄弟 层次 深度*23. 二叉树是另一种树型结构，其特点是每个结点至多有两棵子树，并且二叉树的子树有左右之分，其顺序不能任意颠倒。几个重要的性质： 性质1 在二叉树的第i层上至多有2i-1个结点（i1）性质2 深度为k的二叉树至多有2k -1个结点（k1）性质3 对任何一棵二叉树T，如果其终端结点数为n0
6、，度为2的结点数为n2 ，则：n0 =n2+1(叶子节点数=度为2的节点数+1)性质4 具有n个结点的二叉树，其深度至少为log2n +1常考:总节点数度为0的节点数度为1的节点数度为2的节点数24.满二叉树除最后一层外，每一层上的所有结点都有两个子节点，也就是说每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。*25.完全二叉树除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，其深度为log2n +1。（一定要会计算结点的个数）26. 二叉树的链式存储结构中，每个结点设置三个域，即
7、数据域，左指针域和右指针域，两个指针域分别存储左右子树根节点的存储位置，即指针。*27. 二叉树的遍历指不重复地访问二叉树的所有结点。分为：先序、后序和中序遍历。一定要明白由先序和中序推出后序，和由后序和中序推出先序！28. 顺序查找是指在一个给定的数据结构中查找某个指定的元素。最好情况查找长度为1，最坏为n，所以平均查找长度为（n+1)/2。时间复杂度为O(n)。29二分查找法只适用于顺序存储的有序表。查找过程为：给定值首先和处于待查区间“中间位置”的关键字进行比较，若相等，则查找成功，否则将查找区间缩小到“前半个区间” 或 “后半个区间” 之后继续进行查找。平均查找长度小于等于 log2
8、(n+1) ，时间复杂度为O(log2n)。在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是O(log2n).*30. 排序方法有：插入排序：包括简单插入排序法和希尔排序法等交换排序：包括冒泡排序和快速排序法等选择排序：包括简单选择排序和堆排序等在最坏情况下，快速排序、冒泡排序和直接插入排序需要的比较次数都是n(n1)/2，堆排序需要比较的次数为nlog2n。31. 冒泡排序最坏情况下运算的次数为：n*(n-1)/2（即时间复杂度）。最好情况下为：n-1。*32.排序部分应该掌握的几点： 1.当原表有序或基本有序时,直接插入排序和冒泡排序最好，时间复杂度可降至O(n)。（也就是
9、最好情况下） 。如果选择快速排序则相反，达到最坏时间复杂度。2.空间复杂度最坏的是归并排序O（n) ，其次是基数排序O（rd) 。3.平均时间最好的是快速、堆、归并排序O（nlgn)。4.稳定排序和不稳定排序（希尔、堆、直接选择，快速）。5.最坏情况下，时间复杂度最小的是：堆和归并排序。 第二部分 程序设计基础（1-2题）和软件工程（4-5题）n 1. 程序设计主要经历了结构化的程序设计和面向对象的程序设计阶段。在程序设计中，通常采用“自顶向下，逐步求精”的方法。结构化程序设计由三种基本控制结构组成：顺序结构、选择结构和循环结构。2.程序风格也是非常重要的。良好的程序设计风格概括起来包括以下4
10、个方面：n 源程序文档化（1） 标识符的命名:要有一定的实际含义。（2）程序的注释：分为序言性注释和功能性注释。（3）程序的视觉组织：一定要层次清晰n 数据说明的方法 （1）数据说明的次序应该规范化（2）说明语句中变量的安排有序化：如多个变量出现在同一个说明语句中，要按顺序排列。（3）使用注释说明复杂的数据结构n 语句的结构（几个重要的方面）（1）除非对效率有特殊要求，程序编写要做到清晰第一，效率第二（2）尽可能使用库函数，且避免使用复杂的条件语句(3)要模块化，且要利用信息隐蔽，确保每一个模块的独立性n 输入和输出对所有输入数据检验合法性和输入数据时，应允许使用自由格式*3. 对象是面向对象
11、程序设计中的基本单位。对象可以表示客观世界中的任何实体，是对问题域中某个实体的抽象。对象通常由对象名、属性和操作三部分组成。4. 类是对一组具有共同属性和相似行为的对象的一种抽象，类是对象的抽象，而对象是类的具体实例。类是抽象的，不占用内存，而对象是具体的，占用存储空间。5. 对象的特点: 标识唯一性、分类性、封装性、模块独立性、多态性和继承（分为单重基础和多重继承）。6. 方法也可称为操作或服务，它描述了对象执行的功能，它是对象的动态属性。*7. 消息：面向对象系统中的对象之间是通过消息机制彼此相互合作的。消息由三部分组成： 消息标识符、零个或多个参数、接受消息对象的对象名8. 面向对象程序
12、设计的特点：稳定性好、可重用性好、易于开发大型软件、可维护性好。 9. 计算机软件是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。10. 所谓软件危机是指在计算机软件开发和维护过程中所遇到的一系列严重问题。主要表现在以下几个方面：软件需求的增长得不到满足；软件开发成本和进度无法控制；软件质量难以保证；软件可维护性差；软件的成本不断提高；软件开发生产率的提高赶不上硬件的发展和应用需求的增长。11. 为了消除软件危机，提出了软件工程学。软件工程是应用于计算机软件定义、开发和维护的一整套方法、工具、文档、实践标准和工序。*12. 软件工程的三要素：方法、工具、过程。13
13、. 软件工程过程是指为获得软件产品，在软件工具支持下由软件工程师完成的一系列工程活动。包括四种基本活动：P(Plan)：软件规格说明、D(Do)：软件开发、C(Check)：软件确认、A(Action)：软件演进。14. 软件工程的基本原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。*15. 软件工程的理论和技术性研究的内容包括：n 软件开发技术：软件开发方法学、开发过程、开发工具和软件工程环境n 软件工程管理：软件管理学、软件工程经济学、软件心理学*16. 衡量软件的指标：高内聚（模块内）、低耦合（模块间）。17. 计算机辅助软件工程(CASE):是一组工具和方法集合
14、。包括5个方面的集成：平台集成、数据集成、表示集成、控制集成、过程集成。*18.软件的生命周期是软件从提出、实现、使用、维护到停止使用的过程，一般包括以下几个阶段：u 可行性研究：其实质是要进行一次简化、压缩了的需求分析u 需求分析：任务就是导出目标系统的逻辑模型，解决“做什么”的问题（即系统功能）。 u 软件设计：包括概要设计和详细设计。 u 软件实现：把软件设计转换成计算机可以接受的程序代码。 u 软件测试:为发现错误而进行的活动。u 运行和维护：软件生命周期中所花费最多的阶段是软件运行维护阶段。19. 需求分析阶段的主要工作：需求获取、需求分析、编写需求规格说明书(SRS)和需求评审。数
15、据流图DFD图20. 需求规格说明书是需求分析应交付的主要文档，也是需求分析的最后成果。需求规格说明书的特点是：（1）正确性（2）无岐义性（3）完整性 （4）可验证性 （5）一致性 （6）可理解性（7）可追踪性。*21. 结构化分析方法是一种建模技术。其实质着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。面向对象程序设计的3个主要特征是：封装性、继承性和多态性。*22. 结构化分析常用的工具：数据流图DFD， 数据字典DD ，判定树，判定表。（有时也用结构化语言）*23. 数据流图（DFD）：就是采用图形方式来表达系统的逻辑功能、数据在
16、系统内部的逻辑流向和逻辑变换过程。数据流图的基本元素有：数据源（终点) 、 数据流、 处理(加工) 、 数据存储。n 处理（加工）过程至少有一个输入数据流和一个输出数据流。n 数据流程图上的每个元素都必须有名字。*24. 数据字典（DD）是对数据流图中的各个元素进行完整的定义和说明，本质是一个数据库。作用是对数据流图中出现的被命名的图形元素的确切解释。 n 数据字典通常包含5个部分：数据项、数据结构、数据流、数据存储和处理过程 。n 数据字典是结构化分析的核心。*25. 从技术角度出发软件设计包括：软件结构设计、数据设计、接口设计、过程设计。*26从结构化设计角度看，软件设计分概要设计和详细设
17、计两步完成。n 概要设计，即总体设计。将需求分析得到的DFD转化为转化为软件系统结构和全局数据结构、确定数据库模式（即概要设计的功能）。n 概要设计的工具是结构图(SC)，结构图基本组成成分：模块、数据和调用.。n 详细设计即过程设计。功能是为软件结构图（SC）中的每一个模块确定采用的算法，模块内数据结构，用某种选定的表达工具（如N-S图等）给出清晰的描述。27. 需求分析的工具：（不要与方法弄混了，也不要与结构化分析工具弄混！） 问题分析图 （ PAD ）、程序流程图 （PFD ）、 N-S 图（盒图）n 程序流程图（PFD）中的箭头代表的是：控制流n 数据流图中的箭头代表：数据的流向n 结
18、构图（sc):箭头代表模块的调用*28. 软件测试是为了发现错误而执行程序的过程。软件测试的目的是暴露错误，评价程序的可靠性。软件调试的目的是发现错误的位置，并改正错误。测试的分类：l 从是否需要执行被测试软件的角度，可将测试分为静态测试和动态测试。l 按照功能划分，可将软件测试分为黑盒测试和白盒测试。（有时也称白箱和黑箱测试）29. 测试用例包括合理的和不合理的输入条件。好的测试用例指可能找到迄今为止尚未发现的错误的用例。30. 静态测试主要包括代码检查、静态结构分析、代码质量度量等，它可以由人工进行 。31动态测试是通常意义上的测试，也就是运行和使用软件。是根据软件开发的各个阶段的规格说明
19、和程序的内部结构而精心设计的一批测试用例，并利用这些测试用例去运行程序，以发现程序错误的过程。*32. 黑盒测试将测试对象看作一个黑盒，不考虑程序内部的逻辑结构和内部特性，只依据程序的需求规格说明书，检查程序的功能是否符合它的功能说明。这种测试又称为功能测试或数据驱动测试。n 黑盒测试的方法：等价类划分法、边界值分析法、错误推测法、因果图法等。*33. 白盒测试把测试对象看作一个透明的盒子，利用程序内部逻辑机构及有关信息，设计或选择测试用例，对程序的所有逻辑路径进行测试，确定实际的状态是否与预期的一致。又称为结构测试或逻辑驱动测试。n 白盒测试的方法：逻辑覆盖、基本路径测试等。*34软件测试按
20、四个步骤（不同阶段）进行：单元测试、集成测试、确认测试、系统测试n 单元测试：对软件设计的最小单位模块进行正确性的测试，其目的是发现各模块内部可能存在的各种错误。是在代码编写阶段可进行的测试，它是整个测试工作的基础。n 确认测试是验证软件的功能和性能是否满足需求规格说明中得各种需求，以及软件配置是否完全、正确。*35、程序调试的任务是诊断和修正程序中的错误。调试的方法：强行排错法、回溯法、原因排除法*36、软件维护主要是指根据需求变化或硬件环境的变化对应用程序进行部分或全部的修改。 分类： 1.适应性维护 2.改善性维护 3.纠错性维护 4.预防性维护 （备注：每样维护要明白什么意思）37、维
21、护的副作用有编码副作用、数据副作用、文档副作用三种。第三部分 数据库设计基础（2-4题）3.1 数据库系统的基本概念1、数据、数据库、数据管理系统（1）数据：实际上就是描述事物的符号记录。（2）数据库（DB）：是有组织的相互关联数据的集合，具有集成与共享的特点。（3）数据库管理系统（DBMS）：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库的核心。数据库管理系统功能：1）数据模式定义。2）数据存取的物理构建。3）数据操纵。4）数据的完整性、安生性定义与检查。5）数据库的并发控制与故障恢复。6）数据的服务。（4）数据库管理员（DBA）：对数据库进行规划
22、、设计、维护、监视等的专业管理人员。（5）数据库系统（DBS）：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。（6）数据库应用系统：由数据库系统、应用软件及应用界面三者组成。*：数据库技术的根本目标是解决数据的共享问题。*2、数据库系统的发展经历了三个阶段：人工管理阶段、文件系统阶段和数据库系统阶段。3、数据库系统的基本特点（1）数据的高集成性。（2）数据的高共享性与低冗余性。*：数据库系统可以减少数据冗余，但无法避免一切冗余。*（3）数据独立性：数据独立性一般分为物理独立性与逻辑独立性两级。1）物理独立性：物理独立性
23、即是数据的物理结构（包括存储结构，存取方式等）的改变，如存储设备的更换、物理存储的更换、存取方式改变等都不影响数据库的逻辑结构，从而不致引起应用程序的变化。2）逻辑独立性：数据库总体逻辑结构的改变，如修改数据模式、增加新的数据类型、改变数据间联系等，不需要相应修改应用程序，这就是数据的逻辑独立性。*4、数据库系统的三级模式：1）概念模式：数据库系统中全局数据逻辑结构的描述，是全体用户（应用）公共数据视图。2）外模式：也称用户模式，它是用户的数据视图，用户所见到的数据模式，它由概念模式推导而出。3）内模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法。5、数据库系统的两级映射：1）概念
24、模式/内模式的映射：保证数据具有很高的物理独立性。2）外模式/概念模式的映射：保证数据具有较高的逻辑独立性。*3.2 数据模型1、数据模型是数据特征的抽象，它从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表示与操作提供一个抽象的框架。n 数据模型所描述的内容有三个部分，它们是数据结构、数据操作与数据约束。n 数据模型分为概念模型、逻辑数据模型和物理模型三类：2、概念数据模型：简称概念模型，是对客观世界复杂事物的结构描述及它们之间的内在联系的刻画。概念模型主要有：E-R模型(实体联系模型)、扩充的E-R模型、面向对象模型及谓词模型等。3、逻辑数据模型：又称数据模型，是一
25、种面向数据库系统的模型，该模型着重于在数据库系统一级的实现。逻辑数据模型主要有：层次模型、网状模型、关系模型、面向对象模型等。4、物理数据模型：又称物理模型，给出了数据模型在计算机上物理结构的表示。5、E-R模型的基本概念：1）实体：现实世界中的事物。2）属性：事物的特性。3）联系：现实世界中事物间的关系。实体集的关系有一对一、一对多、多对多的联系。E-R图：实体-联系图：实体 矩形 联系 菱形 属性 椭圆 *：E-R模型的基本成分是实体和联系。6、数据库管理系统常见的数据模型有层次模型、网状模型和关系模型三种。7、关系模型的一些概念和特征：（自己再看看！）u 关键字（不能取空值）、属性、元组
26、、外部关键字、域、关系模式u 一些约束（特征）：不能有相同元组、列不可分解等等。8、关系中的数据约束：1）实体完整性约束。2）参照完整性约束 3）用户定义的完整性约束9、关系操纵（即数据操纵）是建立在关系上的数据操纵，一般有查询、增加、删除和修改四种操作。10、传统的集合运算（1）并（） （2）差（）（3）交（）专门的关系运算：选择、投影、连接运算广义笛卡尔积（）*3.3 数据库设计方法和步骤1）需求分析阶段：这是数据库设计的第一个阶段，任务主要是收集和分析数据。2）概念设计阶段：分析数据间内在语义关联，在此基础上建立一个数据的抽象模型，即形成E-R图。*：数据库概念设计的过程包括选择局部应用、视图设计和视图集成。3）逻辑设计阶段：将E-R图转换成指定RDBMS中的关系模式。4）物理设计阶段：对数据库内部物理结构作调整并选择合理的存取路径。
