国家二级公共根底学问考试要点 第一章 数据构造及算法1.1 算法 算法：是指解题方案的精确而完整的描述 算法不等于程序，也不等计算机方法，程序的编制不行能优于算法的设计 算法的根本特征：是一组严谨地定义运算依次的规那么，每一个规那么都是有效的，是明确的，此依次将在有限的次数下终止特征包括： 〔1〕可行性； 〔2〕确定性， 〔3〕有穷性， 〔4〕拥有足够的情报 算法的根本要素：一是对数据对象的运算和操作；二是算法的限制构造 指令系统：一个计算机系统能执行的全部指令的集合 根本运算和操作包括：算术运算, 逻辑运算, 关系运算, 数据传输 算法的限制构造：依次构造, 选择构造, 循环构造 算法根本设计方法：列举法, 归纳法, 递推, 递归, 减斗递推技术, 回溯法。
算法困难度：算法时间困难度和算法空间困难度 算法时间困难度是指执行算法所须要的计算工作量1.2 数据构造的根本根本概念 数据构造探讨的三个方面： 〔1〕数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑构造；* 〔2〕在对数据进展处理时，各数据元素在计算机中的存储关系，即数据的存储构造；[2007.9 ] 〔3〕对各种数据构造进展的运算 如：2007.9： 〔6〕以下表达中正确的选项是 [1.2]A〕数据的逻辑构造及存储构造必定是一一对应的 B〕由于计算机存储空间是向量式的存储构造，因此，数据的存储构造肯定是线性构造 C〕程序设计语言中的数组一般是依次存储构造，因此，利用数组只能处理线性构造 D〕以上三种说法都不对 数据构造是指相互有关联的数据元素的集合 数据的逻辑构造包含：线性表, 栈, 队列, 二叉树, 图 〔1〕表示数据元素的信息； 〔2〕表示各数据元素之间的前后件关系。
数据的存储构造有依次, 链接, 索引等 线性构造条件：数组, 线性表, 栈, 队列 〔1〕有且只有一个根结点； 〔2〕每一个结点最多有一个前件，也最多有一个后件 非线性构造：不满意线性构造条件的数据构造二叉树, 图 1．3 线性表及其依次存储构造 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的 在困难线性表中，由假设干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件 非空线性表的构造特征： 〔1〕且只有一个根结点a1，它无前件； 〔2〕有且只有一个终端结点an，它无后件； 〔3〕除根结点及终端结点外，其他全部结点有且只有一个前件，也有且只有一个后件。
结点个数n称为线性表的长度，当n=0时，称为空表 线性表的依次存储构造具有以下两个根本特点： 〔1〕线性表中全部元素的所占的存储空间是连续的； 〔2〕线性表中各数据元素在存储空间中是按逻辑依次依次存放的 ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数 依次表的运算：插入, 删除要进展大量的数据移动 〔详见14--16页〕 1．4 栈和队列 栈是限定在一端进展插入及删除的线性表，允许插入及删除的一端称为栈顶，不允许插入及删除的另一端称为栈底 栈的操作原那么依据“先进后出〞〔FILO〕或“后进先出〞〔LIFO〕组织数据，栈具有记忆作用用top表示栈顶位置，用bottom表示栈底 栈的根本运算：〔1〕插入元素称为入栈运算；〔2〕删除元素称为退栈运算；〔3〕读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无改变。
队列是指允许在一端〔队尾〕进入插入，而在另一端〔队头〕进展删除的线性表Rear指针指向队尾，front指针指向队头 队列是“先进先出〞〔FIFO〕或“后进后出〞〔LILO〕的线性表 队列运算包括〔1〕入队运算：从队尾插入一个元素；〔2〕退队运算：从队头删除一个元素 循环队列：s=0表示队列空，s=1且front=rear表示队列满 空间的计算：假设rear>front : rear-front Rear<=front :空间数+rear-front[2021.9], 书后习题 1．5 线性链表 数据构造中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点 结点由两局部组成：〔1〕用于存储数据元素值，称为数据域；〔2〕用于存放指针，称为指针域，用于指向前一个或后一个结点 在链式存储构造中，存储数据构造的存储空间可以不连续，各数据结点的存储依次及数据元素之间的逻辑关系可以不一样，而数据元素之间的逻辑关系是由指针域来确定的。
链式存储方式即可用于表示线性构造，也可用于表示非线性构造 线性链表，HEAD称为头指针，HEAD=NULL〔或0〕称为空表，假如是两指针：左指针〔Llink〕指向前件结点，右指针〔Rlink〕指向后件结点 线性链表的根本运算：查找 链表依次查找，数组随机查找 , 插入, 删除 1．6 树是一种简洁的非线性构造，全部元素之间具有明显的层次特性 在树构造中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根每一个结点可以有多个后件，称为该结点的子结点没有后件的结点称为叶子结点 在树构造中，一个结点所拥有的后件的个数称为该结点的度，全部结点中最大的度称为树的度树的最大层次称为树的深度 二叉树的特点：〔1〕非空二叉树只有一个根结点；〔2〕每一个结点最多有两棵子树，且分别称为该结点的左子树及右子树。
二叉树的根本性质： 〔1〕在二叉树的第k层上，最多有2k-1(k≥1)个结点； 〔2〕深度为k的二叉树最多有2k-1个结点； 〔3〕度为0的结点〔即叶子结点〕总是比度为2的结点多一个；【2007.9】 〔4〕具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数局部； 〔5〕具有n个结点的完全二叉树的深度为[log2n]+1； 〔6〕设完全二叉树共有n个结点假如从根结点开场，按层序〔每一层从左到右〕用自然数1，2，….n给结点进展编号〔k=1,2….n〕，有以下结论： ① 假设k=1，那么该结点为根结点，它没有父结点；假设k>1，那么该结点的父结点编号为INT(k/2)； ② 假设2k≤n，那么编号为k的结点的左子结点编号为2k；否那么该结点无左子结点〔也无右子结点〕； ③ 假设2k+1≤n，那么编号为k的结点的右子结点编号为2k+1；否那么该结点无右子结点。
满二叉树是指除最终一层外，每一层上的全部结点有两个子结点，那么k层上有2k-1个结点深度为m的满二叉树有2m-1个结点 完全二叉树是指除最终一层外，每一层上的结点数均到达最大值，在最终一层上只缺少右边的假设干结点 二叉树存储构造采纳链式存储构造，对于满二叉树及完全二叉树可以按层序进展依次存储 二叉树的遍历： 〔1〕〔先根〕前序遍历〔DLR〕，首先访问根结点，然后遍历左子树，最终遍历右子树； 〔2〕中序遍历〔LDR〕，首先遍历左子树，然后访问根结点，最终遍历右子树； 〔3〕后序遍历〔LRD〕首先遍历左子树，然后访问遍历右子树，最终访问根结点 1．7 查找技术 依次查找的运用状况：对于长度为n的有序线性表，最坏状况只需比拟n次 〔1〕线性表为无序表； 〔2〕表采纳链式存储构造。
二分法查找只适用于依次存储的有序表，对于长度为n的有序线性表，最坏状况只需比拟log2n次 1．8 排序技术 排序是指将一个无序序列整理成按值非递减依次排列的有序序列 交换类排序法：〔1〕冒泡排序法，须要比拟的次数为n(n-1)/2；【 2007.9】〔2〕快速排序法： 须要比拟的次数为n*log(n) 插入类排序法：〔1〕简洁插入排序法，最坏状况须要n(n-1)/2次比拟；〔2〕希尔排序法，最坏状况须要O(n )次比拟 选择类排序法：〔1〕简洁项选择择排序法, 最坏状况须要n(n-1)/。