计算机access公共基础知识一

《计算机access公共基础知识一》由会员分享，可在线阅读，更多相关《计算机access公共基础知识一（49页珍藏版）》请在金锄头文库上搜索。

1、数据结构与算法o第1章 数据结构与算法 1.1 算法1 算法的基本概念 2 算法复杂度 1.2 数据结构的基本概念1 什么是数据结构 2 数据结构的图形表示 3 线性结构与非线性结构 1.3 线性表及其顺序存储结构1 线性表的基本概念 2 线性表的顺序存储结构3 顺序表的插入运算 4 顺序表的删除运算 1.4 栈和队列1 栈及其基本运算 2 队列及其基本运算 1.5 线性链表1 线性链表的基本概念 2 线性链表的基本运算 3 循环链表及其基本运算 1.6 树与二叉树1 树的基本概念 2 二叉树及其基本性质3 二叉树的存储结构 4 二叉树的遍历 1.7 查找技术1 顺序查找 2 二分法查找 1.

2、8 排序技术1 交换类排序法 2 插入类排序法 3 选择类排序法1、 算法o算法 算法是指为解决某个特定问题而采取的确定且有限的步骤的一 种描述，它是有限的指令序列，在有限的时间内被求解。o算法的复杂度 可分为时间复杂度和空间复杂度，是衡量算法优劣的量度。n时间复杂度：是指执行算法所需要的计算工作量。 常见时间复杂度有：n空间复杂度：一般是指执行此算法所需要的内存空 间量。n有穷性：一个算法应包含有限个操作步骤 。n确定性：算法中每一条指令必须有确切的 含义。n有效性（可行性） ：算法中的每一步骤 都应当能有效地执行，并得到结果。n有输入：执行算法时从外界取得的信息， 有零个或多个输入。n有输

3、出：算法得到的结果就是算法的输出 ，有一个或多个输出。 算法的基本特性n算法中对数据的运算和操作：对于所有算法都 是按照要求从环境能够运行的所有操作中选择合适的 操作所组成的一组指令序列。共四类p算术运算：主要包括加、减、乘、除等运算 。p逻辑运算：主要包括“与”、“或”、“非 ”等运算。p关系运算：主要包括“大于”、“小于”、 “等于”、和“不等于”等运算。p数据传输：主要包括赋值、输入和输出等操 作。n算法的控制结构：算法中各操作之间的执行顺序 。（顺序、选择、循环）算法的基本要素o算法的描述方法 用自然语言表示 用传统流程图表示 用N-S流程图表示 用伪代码表示 o算法设计的方法：n列举

4、法n归纳法n递推n递归n回溯n正确性（Correctness）：算法应满足具体 问题的需求。n可读性（Readability）：算法主要是为了 人的阅读与交流，其次才是及其执行，可 读性好有助于人对算法的理解。n健壮性（Robustness）：当输入非法是， 算法应能适当的作出反应或进行处理。n高效性：有效使用存储空间和有较高的时 间效率。算法设计的要求举例 o计算机算法指的是_。 A.计算方法 B.调度方法 C.排序方法 D.解决某一问题的有限运算序列o算法的时间复杂度取决于_。 A.问题的规模 B.待处理的数据的初始状态 C.问题的困难度 D.A和Bo算法的空间复杂度是指_。 A.算法程序

5、中的指令条数。 B.算法执行过程中所需要的存储空间。 C.算法程序的长度。 D.算法程序所占有的存储空间。o描述算法的常用方法有_。自然语言、传统流程图、N- S流程图、伪代码描述语言o数据（Data）的概念是对客观事物的符号表示，在计算机科学中是指 能输入到计算机中并被计算机程序处理的符号的 总称。o数据元素（Data Element）是数据的基本单位，在计算机程序中通常作为一 个整体进行考虑和处理。2 数据结构o数据对象（Data Object）是性质相同的数据元素的集合，是数据的一个子 集。o数据结构（Data Structure）是相互之间存在一种或多种特定关系的数据元素 的集合，即带

6、有结构的数据元素之间的前后件关 系。2 数据结构o 数据结构（问题的数据模型）作为计算机的一门学科，它主要研究和讨论3个方面的问题：n 数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；n 对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。n 对各种数据结构进行的运算。数据结构研究的问题数据的逻辑结构是指数据元素之间的逻辑关系，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示。数据的逻辑结构是从逻辑关系上描述数据，它与数据在计算机中的存储位置无关，是独立于计算机的。数据的逻辑结构线性结构树形结构网状结构 （图形）集合结构o数据逻辑结构有四类：n集合结构：数

7、据元素之间的关系是“属于同一个集合” ，集合是元素关系极为松散的一种。n线性结构：该结构数据元素之间存在一对一的关系。n树形结构：元素之间存在一对多的关系。n图形结构：数据元素之间存在多对多的关系。数据的存储结构是数据元素及其关系在计算 机存储空间中的表示。存储结构的主要内容是指 在存储空间中使用一个存储结构点来存储一个数 据元素；在存储空间中建立各存储结构点之间的 关联，以表示数据元素之间的逻辑关系。 常用数据的存储结构有如下4种： 顺序存储方式。 链式存储方式。 索引存储方式。 散列存储式。数据的存储结构o用二元关系表示：B=(D,R) 其中B表示数据结构， D 表示数据元素的集合， R反

8、映数据元素之间的前后 件关系。例如 家庭成员数据结构可表示成：B=(D,R) D=父亲，儿子，女儿R=（父亲，儿子）,(父亲，女儿) o用图形表示：对关系R中的每个二元组，用一条有向 线段从前件结点指向后件结点，上述结构可表示如 下：数据结构的表示父亲儿子女儿线性结构与非线性结构 o根据结构中各数据元素之间前后件关系的复杂程 度，将数据结构分为两个类型：线性结构和非线 性结构。n线性结构：在数据元素的非空有限集中，线性结构有如下 特征： 存在唯一的一个被称作“第一个”的数据元素。 存在唯一的一个被称作“最后一个”的数据元素。 除第一个之外，集合中的每个数据元素均只有一个前驱 。 除最后一个之外

9、，集合中的每个数据元素均只有一个后 继。n非线性结构：其特征是一个结点可能有多个直接前驱和直 接后继，例如，树和图都是非线性结构。举例o数据在计算机内存中的表示是指_。 A 数据的存储结构 B 数据结构 C 数据的逻辑结构 D 数据元素之间的关系o数据的_包括集合、线性结构、树形结构和图形 结构四种基本类型。 A 算法描述 B 基本运算 C 逻辑结构 D 存储结构o在数据结构中，从逻辑上可以把数据结构分成_ 。 线性结构和非线性结构o数据的存储结构包括顺序、_、索引和散列四种 基本类型。 链式o_中任何两个结点之间都没有逻辑关系。 集合线性表（Linear_List）的概念线性表是n个具有相同

10、数据类型的数据元素的有 限序列。数据元素可以是一个数，一个符号，一页 书，或是其他更复杂的信息。n为表长。 线性表的顺序存储结构是指在内存中用一组地址连续的存储单元依次 存储线性表中的数据元素，也称为顺序表。 顺序表的基本运算插入运算是指在表中的某指定位置上增加一个 新结点；而删除运算是指将表中某个结点从线性表 中去掉。3 线性表及其顺序存储结构栈（Stack）是限定仅在表尾进行插入 和删除操作的线性表。对栈来说，表尾端有 其特殊的含义，称为栈顶（top），表头端 称为栈底（bottom）。栈顶元素总是被最后 插入的元素，也是最先能被删除的元素；栈 底元素总是最先被插入的元素，也是最后能 被删

11、除的元素。（LIFO） 栈的顺序存储结构 栈的基本运算4 栈和队列栈的顺序存储结构是利用一组地址连续的存储单 元依次存放自栈底到栈顶的数据元素，存时附设指针 指示栈顶元素在顺序栈中的位置。 如下图所示。栈的顺序存储结构a1a2an栈的顺序存储结构示意图其中，a1为栈底元素， an为栈顶元素。栈中的元素按照a1， a2，an为次序进栈，退栈的第一个元素为栈顶元素an。进栈出栈栈顶栈底栈的基本运算有3种：入栈、退栈和读栈顶元素。 入栈运算：是指在栈顶插入一个新元素。当栈 顶指针已经指向存储空间的最后一个位置时，说 明栈空间已满，不能再进行插入栈的操作。上溢 退栈运算：是指取出栈顶元素并赋给一个指定

12、 的变量。当栈顶为0时，说明栈空，不可能进行退 栈操作。下溢 读栈顶元素：是指将栈顶元素赋给一个指定的 变量。此处要注意，此运算不删除栈顶元素，只 是将它的值赋给一个变量，因此，在这个运算中 ，栈顶指针不会改变。栈的基本运算队列是限定仅在表的一端进行插入，而在表的另一端删除数据元素的线性表。在队列中，允许插入的一端叫做队尾（rear），允许删除的一端称为队头（front）。（FIFO） 队列的顺序存储结构 队列的基本运算4 栈和队列在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队头到队尾的元素之外，还需要附设两个指针，分别指示队头元素和队尾元素的位置。队列是一种先进先出的线性表

13、。它只允许在表的一端进行插入，而在另一端删除元素。队列的顺序存储结构循环队列：Q.front=Q.rear=0表示队列空(Q.rear+1)%maxqsize=Q.front表示队列满一般情况对满对空循环队列的基本运算有2种：入队和退队。假设循环队 列的初始状态为空，即s=0,且front=rear=m 入队运算：是指在循环队列的队尾加一个新元素。 这个运算有两个本操作，首先将队尾指针增一（ rear=rear+1），并当rear=m+1时置rear=1；然后将新 元素插入到队尾指针指向的位置。 退队运算：是指在队列的队头位置退出一个元素并 赋值给指定的变量。这个运算有两个基本操作，首先 将队

14、头指针增一（front=front+1），并当front=m+1 时置front=1；然后将队头指针指向的元素赋给指定的 变量。循环队列基本运算举例o在一个长度为n的顺序表中，向第i个元素(1next!=p) q=q-next;/*找p的直接前驱*/ s-next=q-next;q-next=s;时间复杂度o(n) 后插：s-next=p-next;p-next=s;时间复杂度o(1)5 线性链表2、删除运算：设p指向单链表中某结点，删除p。q为p的前驱结点q-next=p-next; free(p); 循环链表循环链表的特点是表中最后一个结点的指针域指 向头结点，整个链表形成一个环，由此，从

15、表中任一 结点出发均可找到表中其他结点。循环链表和单链表的差别仅在于判断链表中最后 一个结点的条件不再是“后继是否为空”，而是“后 继是否为头结点”。 基本运算同非循环链表相似在双向链表的结点中，有两个指针域，其一 指向直接后继，另一个指向直接前驱。 基本操作 1、插入结点：设p指向双向链表中某结点，s指向 待插入的值x的新结点，将s插入到 p的前面。s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s; 2、删除结点：设p指向双向链表中某结点，删除p 。p-prior-next=p-next;p-next-prior=p-prior;free(p);双向链表举例 o单链表要求内存中可用存储单元的地址_。 A.必须是连续的 B.一定不是连续的 C.部分地址必须是连续的 D.可以连续也可以是不连续o采用链接方式存储线性表的优点是_。 A.便于随机存取 B.花费的存储空间较顺序存储少 C.数据元素的物理顺序和逻辑顺序不同 D.便于插入和删除o在单链表中，头指针的作用是_。 A.方便运算的实现。 B.用于标识单链表。 C.使单链表至少有一个结点。 D.用于标识首结点位置。o在双向链表