《计算机二级考试之数据库重点知识》由会员分享，可在线阅读，更多相关《计算机二级考试之数据库重点知识（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):是一组工具和方法集合。包括5个方面的集成：平台集成、数据集成、表示集成、控制集成、过程集成。*18.软件的生命周期是软件从提出、实现、使用、维护到停止使用的过程，一般包括以下几个阶段：u 可行性研究：其实质是要进行一次简化、压缩了的需求分析u 需求分析：任务就是导出目标系统的逻辑模型，解决“做什么”的问题（即系统功能）。 u 软件设计：包括概要设计和详细设计。 u 软件实现：把软件设计转换成计算机可以接受的程序代码。 u 软件测试:为发
