公共基础知识

第一章数据结构与算法一、算法：是对题求解步骤的一种描述，它是指令的有限序列。1、算法的基本特征：（1）可行性：针对实际问题而设计的算法，执行后能够得到满意的结果。（2）确定性：每一个步骤必须有明确的定义，不允许有模棱两可的解释和多义性。（3）有穷性：必须在有限时间内做完，即必须在执行有限个步骤之后停止。（4）拥有足够的情报。2、算法的基本要素（1）对数据的运算和操作：算术运算逻辑运算关系运算数据传输（2）算法的控制结构：顺序选择循环3、算法设计的基本方法：列举法、归纳法、递推法、递归法、减半递推、回溯法4、算法的复杂度（1）算法的时间复杂度：指执行算法所需要的计算工作量（2）算法的空间复杂度：执行这个算法所需要的内存空间公共基础知识全文共24页，当前为第1页。二、数据结构：1、数据结构：相互之间存在一种或多种特定关系和数据元素的集合，即数据的组织形式，它主要研究三个方面：逻辑结构：数据集合中各数据元素之间固有的逻辑关系数据结构主要分为线性结构与非线性结构存储结构：各数据元素在计算机中的存储关系对各种数据结构进行运算2、线性结构：非空数据结构满足有且只有一个根结点，每个结点至少有一个前件，也最多有一个后件公共基础知识全文共24页，当前为第2页。3、线性表的顺序存储线性表是最简单、最常用的一种数据结构。（1）线性表的所有元素所占的存储空间是连续的。（2）各数据元素在存储空间是按逻辑顺序存放的。它是一种随机存取的存储结构公共基础知识全文共24页，当前为第3页。4、栈：只能在表的一端进行插入和删除运算的线性表，能进行插入和删除操作的为栈顶，另一端为栈底，表中没有元素为空栈。特点：先进后出栈的操作：入栈、退栈、读取栈的元素-入栈运算是指在栈顶位置插入一个新的元素-退栈运算是指取出栈顶元素并赋给一个指定变量-读栈顶元素是指将栈顶元素赋给一个指定的变量。当栈顶指针为0时，说明栈空，不可能进行退栈操作。称为“下溢”错误。公共基础知识全文共24页，当前为第4页。例1：ABCD依次入栈又依次出栈，出栈顺序是___例2：若进栈序列为1、2、3、4，进栈过程可以出栈，则（）不可能是一个出栈序列。A、1、4、3、2 B、2、3、4、1 C、3、1、4、2D、3、4、2、1公共基础知识全文共24页，当前为第5页。

2

1公共基础知识全文共24页，当前为第6页。5、队列：只允许在一端删除，另一端插入的顺序表，允许删除的一端叫队头(front头指针)，允许插入的一端叫队尾(rear尾指针)，队中没有元素叫空队。特点：先进先出操作：进队，退队公共基础知识全文共24页，当前为第7页。循环队列及其计算队列的顺序存储结构一般采用循环队列的形式。所谓循环队列，就是将队列存储空间的最后一个位置绕道第一个位置，形成逻辑上的环状空间，供队列循环使用。-入队运算（rear=rear+1）-退队运算（front=front+1）当循环队列为空（s=0）时，不能进行退队运算，称为“下溢”*计算公式：*（非循环队列）元素的个数＝尾指针－头指针

（循环队列）元素的个数＝[（尾指针－头指针+容量）除以容量]所得的余数

公共基础知识全文共24页，当前为第8页。6、线性链表：线性表的链式存储结构称为线性链表。在存储时，每个结点有两部分组成，一部分用于存放数据元素值，称为数据域，另一部分用来存放指针，称为指针域，其中指针用来指向该结点的前一个或后一个结点。（即前件或后件）分为线性单链表与线性双向链表操作：插入、删除7、循环链表：最后一个结点的指针域不是空而是指向表头结点，即在循环链表中，所有结点的指针构成了一个环状链。公共基础知识全文共24页，当前为第9页。8、树与二叉树（1）树：是一种简单的非线性结构根结点，只有直接后件没有直接前件除根结点以外的其它结点可以划分为M（M>=0）个互不相交的有限集合，每个集合又是一棵树，称为根的子树。度：一个结点所拥有的后件个数称为该结点的度，所有结点中的最大度称为树的度。树的深度：指最大层次数。（2）二叉树：树的每个结点最多只能有两棵子树，并且分别称为该结点的左子树与右子树公共基础知识全文共24页，当前为第10页。满二叉树：除最后一层外，每一层所有结点都有两个子结点完全二叉树：除最后一层外，每一层的结点都达到最大值，在最后的一层上只缺少右边的若干个结点。(图36页)公共基础知识全文共24页，当前为第11页。二叉树的性质：1、在二叉树的第k层上，最多有2k-1（k≥1）个结点。2、深度为m的二叉树最多有2m-1个结点。3、在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。4、具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分。公共基础知识全文共24页，当前为第12页。（3）二叉树的遍历：前序：根左右中序：左根右后序：左右根二叉树的存储：二叉树通常采用链式存储结构ABDEGCFDBGEACFDGEBFCA公共基础知识全文共24页，当前为第13页。例前序遍历：abdgcefh中序遍历：dgbaecfh后序遍历：gdbehfcaDBEAFCABDECFABCDEF公共基础知识全文共24页，当前为第14页。公共基础知识全文共24页，当前为第15页。题：1.设树T的度为4，其中度为1、2、3、4的结点个数分别为4,2,1,1,则T中的叶子结点数为A:8B:7C:6D:52.设一棵完全二叉树共有700个结点，则在该二叉树中有个叶子结点。3.设一棵二叉树的中序遍历结果为DBEAFC,前序为ABDECF,后续4.在一个容量为15的循环队列中，若头指针FRONT=6，尾指针REAR=9，则该循环队列中共有元素。5.深度为5的满二叉树中，叶子结点的个数为A.32B.31C.16D.15公共基础知识全文共24页，当前为第16页。9、查找（1）、顺序查找，在最坏情况下，顺序查找需要比较n次例：ABCDEF39页（2）、二分查找，在最坏情况下，二分查找需要比较log2n次计算规则：39页例：已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当使用二分法查找值为90的元素时，查找成功的比较次数为B

。

A.1

B.2

C.3

D.4

公共基础知识全文共24页，当前为第17页。1731694286531674286911532674689公共基础知识全文共24页，当前为第18页。10、排序（1）交换类排序1）冒泡排序n(n-1)/2例41页公共基础知识全文共24页，当前为第19页。2）快速排序n(n-1)/2例：对序列{15、9、7、8、20、-1、4}用快速排序方法进行排序（按递增序），以第一个元素作为划分的基准，在第一次划分后数据的排列是（）。A、9，7，8，4，-1，15，20 B、20，15，8，9，、-1，4，7C、-1，4，7，8，9，15，20 D、4，9，7，8，-1，15，20公共基础知识全文共24页，当前为第20页。（2）插入类排序1）简单插入排序n(n-1)/2例：初始为5|17316

一次插入排序，把第一个1插入前边已排序部分，得

15|7316

后边依次是

157|316

1357|16

11357|6

113567|例：5173169428643页2）希尔排序O(n1.5)公共基础知识全文共24页，当前为第21页。（3）选择类排序

1）简单的选择排