NCRE公共基础知识剖析.ppt

公共基础知识 主要内容 算法与数据结构 程序设计基础 软件工程基础 数据库设计基础 算法与数据结构 算法的概念、基本特征、基本要素 算法复杂度（时间、空间） 数据结构的概念（逻辑结构、存储结构） 数据结构的图形表示 线性结构和非线性结构 线性结构（数组、栈、队列、线性链表） 非线性结构（二叉树） 查找技术（顺序查找、二分查找） 排序技术（交换类排序 插入类排序 选择类排序） 2. 算法复杂度 空间复杂度：执行算法所占用的临时存储空间。 时间复杂度：设算法解决的问题的规模为n， 运行时间关于问题规模n的一个相对的数量级 就称为该算法的时间复杂度，记为： 0⑴，0(n)，0(n2)等。 [2007.9] 下列叙述中正确的是（ ） A）数据的逻辑结构与存储结构必定是一一 对应的。 B）由于计算机存储空间是向量式的存储结构， 因此，数据的存储结构一定是线性结构。 C）程序设计语言中的数组一般是顺序存储 结构，因此，利用数组只能处理线性结构。 D）以上三种说法都不对。 （三）线性表及其顺序存储结构 1. 基本概念 线性表由一组数据元素构成，数据元素的位置 只取决于自己的序号，元素之间的相对位置是 线性的。（有限且有序） 在复杂线性表中，由若干项数据元素组成的数 据元素称为记录，而由多个记录构成的线性表 又称为文件。 2. 线性表的结构特征： （1）有且只有一个根结点a1，它无前件。 （2）有且只有一个终端结点an，它无后件。 （3）除根结点与终端结点外，其他所有结点 有且只有一个前件，也有且只有一个后件。 （4）结点个数n称为线性表的长度，当n=0 时，称为空表。 线性表的常见存储方式： 顺序存储结构 链式存储结构 常见线性表： 顺序存储结构的顺序表 链式存储结构的线性链表 入栈运算：从当前栈顶部插入一个新元素。 具体操作：将栈顶指针加1，再将元素插入 到指针所指的位置。 出栈运算：从当前栈顶部取出栈顶元素。 具体操作：将当前栈顶元素取出，再将栈顶 指针减1。 说明： 1)栈顶用TOP表示，栈底用BOTTOM表示。 2)TOP=0,表示空栈；TOP=Maxsize,表示栈满。 3)栈顶会随着入栈和出栈操作不断变化。 顺序队列为空：Front=Rear 顺序队列满： Front= -1，Rear=Maxsize-1 假溢出： 队列的存储区中还有空间，但是却无法继续 做入队操作的现象。 解决方法： 1）所有元素整体平移 2）循环队列 2.2 循环队列 定义：在逻辑上将顺序队列想象成为一个首尾 相连的圆环。 Front指针：指向队头元素的前一个位置 Rear指针：指向队尾元素的位置 存储空间的编号：从0到Maxsize -1 基本操作：入队，出队 循环队列常用判别和计算公式： 设循环队列的存储空间为m ①队列为空：front=rear ②队列满：front=(rear +1) mod m ③出队：front=(front +1) mod m ④入队：rear=(rear -1) mod m ⑤元素个数= (m-front+rear) mod m 或 元素个数=rear-front (rearfront) 元素个数=m-front+rear (rearfront) 完全二叉树的性质： 性质5：具有n个结点的完全二叉树的深度为： k=[log2n]+1 （[log2n]为log2n的值取整） 性质6：设完全二叉树有n个结点。且从根结点 开始从左至右依次用自然数编号。对于编号为 k的结点有如下讨论： 若k=1，则结点是根结点； 若k1，则该结点的父结点编号为INT(k/2)。 插入排序具体算法步骤如下： 1）从第一个元素开始，该元素可以认为已经被排序 2）取出下一个元素，在已经排序的元素序列中从后向前扫描 3）如果该元素（已排序）大于新元素，将该元素移到下一位置 4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 5）将新元素插入到该位置中 重复步骤2~5 希尔排序（递减增量排序算法） 基本思想： 是对插入排序的一种改进。 先取一个小于n的整数d1作为第一个增量，把文 件的全部记录分成d1个组。所有距离为d1的倍 数的记录放在同一个组中。先在各组内进行直接 插入排序；然后，取第二个增量d2d1重复上述 的分组和排序，直至所取的增量dt=1，即所有记 录放在同一组中进行直接插入排序为止。 该方法实质上是一种分组插入方法。 堆排序 基本思想： 将数据元素用完全二叉树表示。通过比较二 叉树中根结点和它的左右儿子结点的大小， 调整二叉树，使根结点的值大于左右儿子结 点