计算机二级公共基础(超级)

《计算机二级公共基础(超级)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章算法与数据结构1.1算法l定义：指解题方案的准确而完整的描述。（不等于程序，也不等于计算方法）l基本特征可行性确定性有穷性——有限个步骤后终止（有限时间内终止）拥有足够的情报l四种基本运算与操作：算术运算逻辑运算关系运算数据传输l三种基本控制结构：顺序结构选择结构循环结构l基本设计方法列举法归纳法逆推逆归减半递推技术回溯法l指令系统：一个计算机系统能执行所有指令的集合。l复杂度时间复杂度——执行算法所需的计算工作量空间复杂度——执行算法所需的内存空间l一种逻辑结构可以有多种存储结构l不同存储结构影响效率l逻辑结构：对数据元素之间的逻辑关系的描述l存储结构（物理结构）：数据的逻

2、辑结构在计算机存储空间中的存放形式1.2.1数据结构l定义：相互关联的数据元素的集合l研究的三个方面逻辑结构一对多顺序存储结构链接索引等l顺序存储方式——主要用于线性的数据结构——它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的相邻衔接关系来体现l链式存储结构——在每个节点中至少包含一个指针域，用指针来体现数据元素之间逻辑上的联系1.2.2线性结构和非线性结构l根据数据元素结构中的各数据元素之间前后件关系的复杂程度l对于一个非空的数据结构线性结构有且只有一个根结点（线性表）每个结点最多有一个前件，也最多有一个后件非线性结构：不是线性结构l在一个线性结

3、构中插入或删除任何一个结点后还是线性结构l线性结构：栈、队列、串；循环队列、带链队列、带链栈l非线性结构：数组、广义表、树（例二叉树）和图l线性表是最简单的最常用的一种线性结构，线性链表指的是采用链式存储结构的线性表，栈和列是一种特殊的线性表，树是一种简单的非线性结构，二叉树是树的一种。l线性与非线性是从数据的逻辑结构角度来讲，与该数据结构中含有多少个元素无关，即使是空的二叉树也是非线性结构14/14l有序线性表既可以采用顺序存储结构，又可以采用链式存储结构l线性表的顺序存储结构具有以下两个基本特点：1)线性表中所有元素所占的存储空间是连续的2)线性表中各元素所占的存储空间中是按逻

4、辑顺序依次存放的3)元素ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,ADR(a1)为第一个元素地址，k代表每个元素占的字节数l顺序表的运算：查找、插入、删除3种1.3栈（先进后出）（后进先出）（子弹匣）l限定在一端进行插入与删除的线性表（既可以顺序存储，又可以链式存储）l栈顶——允许插入与删除元素的一端l栈底——封闭的一端，栈底指针不变l栈顶总是最先被删除的一端l栈底总是最先被插入的一端l栈的基本运算入栈——栈顶插入退栈——取栈顶元素并赋给一个指定变量读栈顶元素：将栈顶元素赋给一个指定的变量。l栈具有记忆作用l在栈中，栈底指针不变，栈中元素随栈顶指针变化而动态变

5、化l与栈结构关联：子程序的调用1.4队列（先进先出）（后进后出）（火车进隧道）l只允许一段插入，另一端删除的顺序表（顺序存储）l队头——允许删除l队尾——允许插入l队列运算入队——插入元素退队——删除元素l与队列结构有关联：“先到先服务”的作业调度l循环队列1)定义：队列存储空间的最后一个位置绕到第一个位置形成逻辑上的环状空间，供队列循环使用2)循环队列作为特殊的队列，也是线性结构3)循环队列中，队尾指针既可以大于队头指针，也可以小于。4)队列是一种逻辑结构，而循环队列是一种顺序存储结构的队列5)循环队列中的元素个数由队头指针和队尾指针共同决定6)※求循环队列中的元素个数？队尾指针

6、（rear)队头指针（front）m为队列容量入队（rear=rear+1）退队（front=front+1）元素个数为rear-front,rear>front;rear-front+m,rear

7、序表也可以存储无序表l在线性链表中，各数据元素结点的存储空间可以是不连续的，且各数据元素的存储顺序与逻辑顺序可以不一致（且各元素的存储顺序是任意的）l在线性链表中进行插入与删除，不需要移动链表中的元素l线性单链表中，HEAD称为头指针，HEAD=NULL（或0）称为空表l如果是双项链表的两指针：左指针（Llink）指向前件结点，右指针（Rlink）指向后件结点l线性链表的基本运算：查找、插入、删除l带链的栈1)栈也是线性表，也可以采用链式存储结构2)可利用栈：带链的栈