二级公共基本知识速成.doc

第一节 数据结构与算法 1 1.1 算法 1 1.2数据结构 2 1.2.1数据结构的基本概念 2 1.2.2线性表 2 1.3 栈和队列 2 1.4 树和二叉树 2 1.5查找和排序 3 1.5.1查找 3 1.5.2排序 4 第二节 程序设计基础 4 2.1程序设计的方法与风格 4 2.2结构化程序设计 4 2.3面向对象方法 5 第三节 软件工程基础 5 3.1软件工程基本概念 5 3.2 软件定义期 6 3.3软件开发期 6 3.3.1概要设计 7 3.3.2详细设计 7 3.4软件测试 7 3.5程序的调试 7 第四节数据库基础 7 4.1数据库的基本概念 7 4.2数据库系统的发展和基本特点 8 4.3 数据库系统的内部体系结构 8 4.4 数据模型的基本概念 9 4.5 E-R模型 9 4.6 关系模型 9 4.7关系代数 10 4.8数据库设计与原理 10 第一节 数据结构与算法 1.1 算法★★★ 算法：一系列解决问题的清晰指令。 4个特征：可行性、确定性、有穷性、拥有足够情报。 (1) 可行性，例如 10+1-10的问题(2) 确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；例在特殊情况时，数学公式是正确的，但计算机就是无法操作。 (3) 有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义。例如 1/3 的无理数问题。 (4) 拥有足够的情报。所有的各种可能情况都要考虑到。 时间复杂度 执行算法所需要的计算工作量 空间复杂度 执行算法所需要的内存空间 1.2数据结构 1.2.1数据结构的基本概念★ 数据结构：相互有关联的数据元素的集合。 研究以下3方面的内容： 1、数据的逻辑结构：数据元素之间的逻辑关系 2、数据的存储结构：数据的逻辑结构在计算机内的存放形式，不仅存储各数据元素的信息还需要存放数据元素间前后件关系的信息。 3、各种数据结构的运算 常用的存储结构有：顺序存储、链式存储、索引存储、散列存储 1.2.2线性表★★ 根据元素之间前后件关系的复杂程度划分数据结构为：线性结构和非线性结构。 线性结构（线性表）：有且只有一个根节点，每个节点最多有一个前驱和一个直接后继。（就像火车）常见的有：线性表，栈，队列，循环队列和线性链表等。常见的有：数组、广义表、树、二叉树和图都是非线性结构。线性表的存储结构有两种：顺序存储（称为线性表）和链式存储（线性链表）。线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构。Stack）又称堆栈FILO），后进先出（LIFO））人们把此端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底。向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。（Queue）允许在表的一端进行插入操作，而在表的另一端进行删除操作。我们把允许插入的一端称作队尾（rear），允许删除的一端称作队首（front）。 () 向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除队首元素称为离队或出队，该元素离队后，其后继元素就成为新的队首元素。 (2) 由于队列的插入和删除操作分别是在各自的一端进行的，每个元素必然按照进队的次序离队，所以又把队列称为先进先出表（First In First Out，简称 FIFO）。循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，其实质还是顺序存储结构。在循环队列中，用队尾指针 rear 指向队列中的队尾元素，用排头指针 front 指向排头元素的前一个位置。 树是一种简单的非线性结构，所有元素之间具有明显的层次特性。 在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。度为 2 的树就是二叉树。非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的性质 (1) 在二叉树中，第 层的结点总数不超过 2-1(k ≥ 1)。 (2) 深度为 的二叉树总计最多有 2个结点(≥1)，最少有 个结点。(3) 对于任意一棵二叉树，如果其叶子结点数为 N，而度数为 2 的结点总数为 ，则N=+1，即叶子数总比度为 2 的节点数多 1。 (4) 具有 n 个结点的完全二叉树的深度为 int(log2n)+1。除了叶子结点外二叉树。有 N 个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系： 若 k 为结点编号，