2010.9二级Access笔试机试真题串讲--韩相军新1.ppt

二级串讲2 公共基础知识 笔试真题 机试真题 考试注意事项 1.1 算法的基本概念 算法的定义：一个有穷的指令集，这些指令为解决某一特定问题规定了一个运算序列，即方法和步骤，在计算机学科中，算法就是计算机解决问题的过程或步骤。 算法是解题方案的准确而完整的描述。 算法等于程序？等于计算方法？ 结构化程序算法的特性如下。 （1）可行性算法中的操作能够用已经实现的基本运算执行有限次来实现。 （2）确定性算法中的每一步都有确切的含义。 （3）有穷性一个算法（对任何合法的输入）在执行有穷步后能够结束，并且在有限的时间内完成。 （4）拥有足够的情报当算法拥有足够的情报，此算法才是有效的。 算法的时间复杂度指算法的时间耗费，算法时间是由控制结构和原操作的决定的。 数据的逻辑结构：用来描述数据元素之间的逻辑关系。 数据的存储结构：用来描述数据元素及数据元素之间的关系在存储器中的存储形式。 *重点提示： 同一逻辑结构的数据可以采用不同存储结构，但影响数据处理效率。 数据的运算：即对数据元素施加的操作。 数据结构的图形表示：用图形来直观地表示数据及其之间的关系。 数据的逻辑结构分为线性结构和非线性结构两类： 线性结构：数据元素之间构成一种顺序的线性关系，如图1-2所示。线性结构包括线性表、堆栈、队列和串。 1.3 线 性 表 1.3.1 线性表的顺序存储结构 线性表是最常用且最简单的一种数据结构。 采用顺序存储结构的线性表也叫做顺序表，如n个元素的线性表可以记为：L=（a1，a2，…，an）。 顺序表有插入和删除两种基本操作。 1.3.2 线性表的链式存储结构 链式存储是指用一组地址任意的存储单元存放线性表中的数据元素。 *重点提示：线性链表不能随机存取。 链式存储采用结点来表示数据元素。一个结点由两个部分构成：数据域和指针域。 （1）单链表及其基本操作 （2）双向链表及其基本操作 1.4 栈 和 队 列 1.4.1 栈及其基本操作 栈是规定只能在表的一端进行插入和删除的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。当表中没有元素时称为空栈。由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先被删除，所以又把栈称为后进先出（Last In First Out，简称LIFO）或先进后出（FILO）表。栈有插入（即进栈）和删除（即出栈）两种基本操作。 栈顶元素总是最后被插入的元素，最先删除的元素；栈底元素总是最先被插入的元素，最后被删除的元素。 栈具有记忆作用。 1.4.2 队列及其基本操作 队列可以看作是插入在一端进行，删除在另一端进行的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。 队列又称为先进先出（First_In_First_Out, FIFO）或后进后出（LILO）表。队列的基本操作有插入（即入队）和删除（即出队）两种。 队列只能在队尾插入元素，在队头删除元素。 1.5.2 二叉树的基本概念 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。在二叉树中，每一个结点的度最大为2，即所有子树（左子树或右子树）也均为二叉树。 1.5.3 二叉树的存储结构 （1）顺序存储结构 1．中序遍历 中序遍历的算法过程如下。 （1）若二叉树为空，则空操作，返回。 （2）否则依次执行：中序遍历左自树（L）；访问根结点（V）；中序遍历右自树（R）。 1.6 排 序 排序是将一组杂乱无章的数据按一定的规律顺次排列起来。 排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。 通常数据对象有多个属性域，即由多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域称为关键字（key）。 排序的时间开销是衡量算法好坏的最重要的标志。 要形成良好的程序设计风格，主要应注意和考虑下述的一些因素。（1）在一行内只写一条语句。 （2）程序编写应优先考虑清晰性。 （3）除非对效率有特殊要求，程序编写要做到清晰第一，效率第二。 （4）首先要保证程序正确，然后才要求提高速度。（5）避免使用临时变量而使程序的可读性下降。（6）避免不必要的转移。 （7）尽可能使用库函数。 （8）避免采用复杂的条件语句。 （9）尽量减少使用“否定”条件的条件语句。（10）数据结构要有利于程序的件化。（11）要模块化，使模块功能尽可能单一化。（12）利用信息隐蔽，确保每一个模块的独立性。（13）从数据出发去构造程序。（14）不要修补不好的程序，要重新编写 2.2 结构化程序设计 结构化程序设计的主要思想是功能分解并逐步求精。当一些任务十分复杂不易描述时，可以将它拆分为一系列较小的功能部件，直到这些子任务