公共基础知识要点(修改)

《公共基础知识要点(修改)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、公基要点第一章数据结构与算法(3-4分)1.1算法算法：解题方案的准确而完整的描述。不等于程序（算法的描述），也不等于计算方法其基本特征：1、可行性（工具限制，可行不？）2、确定性（无歧义，不允许有多义性）3、有穷性（有限的时间）4、拥有足够的情报（输入的初始数据有关）。算法的基本要素：P21、算法中对数据的运算和操作2、算法的控制结构（基本控制结构：顺序、选择、循环或重复）算法设计基本方法：P31、列举法2、归纳法3、递推4、递归5、减半递推6、回溯法（试）算法执行过程中所需基本运算执行次数算法复杂度：包括1、时间复杂度2、空间复杂度P5算法时间复杂度：执

2、行算法所需要的计算工作量算法程序所占空间、初始数据所占空间、算法执行所需额外空间算法空间复杂度：执行这个算法所需要的内存空间1.2数据结构的基本概念P7数据结构，（数据组织成不同的形式，数据处理的效率不同）P10概念：相互有关联（带有结构）的数据元素的集合。数据元素相当于实体。P10数据结构的内容：数据的逻辑结构（各元素之间所固有的逻辑关系）数据的存储结构（各元素在计算机中的存储关系）各种数据结构进行的运算包含两个方面的信息：P111、数据元素的信息D2、数据元素之间的前后件关系R数据的逻辑结构：B=（D，R），数据元素的集合，数据元素的前后件关系P11数据

3、的存储结构：数据的逻辑结构在计算机存储空间中的存放形式，也称数据的物理结构P12数据元素的逻辑结构和存储结构不一定一般也不可能相同（学号与座位）常用的存储结构有：顺序、链接、索引春夏秋冬数据结构的图形表示：P13线性结构与非线性结构P141、空数据结构<——>非空2、非空的数据结构：（线性结构）（本书范围，只有树是非线性结构）a、有且只有一个根节点b、每一个节点最多有一前件，也最多有一个后件1.3线性表及其顺序存储结构线性表示最简单、最常用的数据结构非空线性表的特征：1、有且只有一个根结点，它无前件2、有且只有一个终端结点，它无后件3、其他结点有且只有一个前

4、件和后件4、结点的个数称线性表的长度线性表的顺序存储结构（顺序表）：P161、占用存储空间是连续2、各数据元素在存储空间中是按逻辑顺序依次存放的顺序表的插入运算：长度为N的线性表平均移动元素N/2次顺序表的删除运算：平均情况下，元素移动一半栈和队列P19栈和队列都是特殊的线性表，插入和删除操作只能在端口。栈是“先进后出（FILO），后进先出”，队列是“先进先出（FIFO），后进后出”栈：栈顶（top）、栈底（bottom）入栈（top+1，新元素插入到栈顶指针指向位置）P21退栈（先栈顶元素赋给一变量，top-1）栈满入栈则“上溢”，栈空退栈则“下溢”读栈顶

5、元素（栈顶元素赋给一变量，栈顶指针不变）队列：队头(出队端，排头指针front指向排头元素的前一位置)P21队尾（进队端，队尾指针rear指向队尾元素）入队、退队循环队列：判定队列中元素的个数（习题）P23Front=rear，则s=0队列空S=1队列满线性链表线性表的顺序存储结构有以下缺点：插入、删除运算效率低存储空间不便于扩充不便于对存储空间动态分配线性表的链式存储结构称为线性链表。由数据域和指针域组成比较：1、线性表的顺序存储结构和链式存储结构的区别P242、两者占用的存储空间（多？少？）P253、访问元素哪个是顺序访问？哪个是随机访问P26线性链表的

6、基本运算：查找、插入、删除树与二叉树树是非线性结构树的根结点结点的度（节点的后件的个数）树的度（最大结点的度）叶子结点（无后件，度为0）树的深度（树的最大层数）二叉树：最多有2颗子树，（左右）只有一个根结点，每一个结点最多只有两个子树（左右）性质1：K层上最多有2^(k-1)个结点性质2：深度为M的二叉树最多有2^m-1个结点性质3：叶子结点比度为2的结点多一个性质4：有N个结点的二叉树，其深度至少为[LOG2N]+1满二叉树：除最后一层外，每一层上的所有结点都有两个子结点完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结

7、点完全二叉树有性质5：有N个结点的完全二叉树，其深度为[LOG2N]+1满二叉树、完全二叉树是二叉树的特殊形式，与二叉树的联系与区别？二叉树的遍历：不重复地访问二叉树的所有结点，前序遍历、中序遍历、后序遍历前序遍历（DLR）访问根结点前序遍历左子树前序遍历右子树递归过程总结：根左右中序遍历：左根右，递归后序遍历：左右根，递归查找技术P391、无序表(不管是顺序存储还是链式存储结构)顺序查找2、链表（不管有序还是无序）二分法查找：只适用于顺序存储的有序表N个元素，最坏情况，比较LOG2N次排序技术P40交换类排序法：冒泡排序法（最坏情况比较次数N*（N-1）/

8、2）快速排序法（最坏情况比较次数N*（N-1）/2）