公共基础_1.ppt

公共基础知识 第一章基本数据结构与算法 新航线培训中心 考点1 算法 一 算法基本概念算法是指为解决某个特定问题而采取的确定且有限的步骤的一种描述 它是指令的有限序列 使得给定类型的问题通过有限的指令序列 在有限的时间内被求解 1 算法的基本特性有穷性即在一定的时间是能够完成的 即算法应该在计算有限个步骤后能够正常结束 新航线培训中心 考点1 算法 确定性算法的设计必须是每一个步骤都有明确的定义 不允许有模糊的解释 也不能有多义性 可行性由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的 因此 它总是受到计算工具的限制 使执行产生偏差 新航线培训中心 考点1 算法 输入和输出 拥有足够的情报 算法的执行与输入的数据和提供的初始条件相关 不同的输入或初始条件会有不同的输出结果 提供准确的初始条件和数据 才能使算法正确执行 新航线培训中心 考点1 算法 二 算法复杂度算法的时间复杂度算法的空间复杂度 新航线培训中心 练习 算法的时间复杂度是指A 执行算法程序所需要的时间B 算法程序的长度C 算法执行过程中所需要的基本运算次数D 算法程序中的指令条数 参考答案 C 解析 算法的复杂度主要包括算法的时间复杂度和空间复杂度 所谓算法的时间复杂度是指执行算法所需要的计算工作量 即算法执行过程中所需要的基本运算的次数 算法的空间复杂度一般是指执行这个算法所需要的内存空间 新航线培训中心 练习 算法的空间复杂度是指A 算法程序的长度B 算法程序中的指令条数C 算法程序所占的存储空间D 执行算法需要的内存空间 参考答案 D 解析 算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度 所谓算法的时间复杂度是指执行算法所需要的计算工作量 算法的空间复杂度是指执行这个算法所需要的内存空间 新航线培训中心 考点2数据结构的基本概念 一 什么是数据结构1数据结构的定义数据结构是指互相之间存在着一种或多种关系的数据元素的集合 数据元素是数据的基本单位 即数据集合中的个体 数据元素亦称节点或记录 有时一个数据元数可由若干数据项组成 数据项是数据的最小单位 数据元素 新航线培训中心 2数据的逻辑结构是指反映数据元素之间的逻辑关系的数据结构 数据的逻辑结构有两个要素 数据元素的集合 记作D数据之间的前后关系 记作R则数据结构B D R 考点2数据结构的基本概念 新航线培训中心 考点2数据结构的基本概念 3数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构 或数据的物理结构 即数据存储时 不仅要存放数据元素的信息 而且要存储数据元素之间的前后件关系的信息 新航线培训中心 考点2数据结构的基本概念 二 线性结构与非线性结构 A B C X Y Z 学生成绩表 线性表 结点间是以线性关系联结 线性结构 新航线培训中心 考点2数据结构的基本概念 非线性结构 图形结构 新航线培训中心 考点2数据结构的基本概念 1 数据的逻辑结构 2 数据的存储结构 3 数据的运算 检索 排序 插入 删除 修改等 A 线性结构 B 非线性结构 A顺序存储 B链式存储 线性表 栈 队 树形结构 图形结构 数据结构的三个方面 亦称物理结构 新航线培训中心 练习 数据结构作为计算机的一门学科 主要研究数据的逻辑结构 对各种数据结构进行的运算 以及 A 数据的存储结构B 计算方法C 数据映象D 逻辑存储 参考答案 A 解析 数据结构作为计算机的一门学科 主要研究和讨论以下三个方面的问题 数据集合中各数据元素之间所固有的逻辑关系 即数据的逻辑结构 在对数据进行处理时 各数据元素在计算机中的存储关系 即数据的存储结构 对各种数据结构进行的运算 新航线培训中心 考点3线性表及其顺序存储结构 顺序存储结构 顺序存储结构常用于线性数据结构 将逻辑上相邻的数据元素存储在物理上相邻的存储单元里 顺序存储结构的三个弱点 1 作插入或删除操作时 需移动大量元数 2 长度变化较大时 需按最大空间分配 3 表的容量难以扩充 新航线培训中心 考点4栈和队列 一 栈 进栈出栈 先进后出 栈顶 栈底 新航线培训中心 练习 栈底至栈顶依次存放元素A B C D 在第五个元素E入栈前 栈中元素可以出栈 则出栈序列可能是A ABCEDB DCBEAC DBCEAD CDABE 参考答案 B 解析 栈操作原则上 后进先出 栈底至栈顶依次存放元素A B C D 则表明这4个元素中D是最后进栈 B C处于中间 A最早进栈 所以出栈时一定是先出D 再出C 最后出A 新航线培训中心 考点4栈和队列 队列定义 一种特殊的线性结构 限定只能在表的一端进行插入 在表的另一端进行删除的线性表 特点 先进先出 a1 a2 a3 a4 an 1 an 队列示意图 队头 队尾 新航线培训中心 考点4栈和队列 循环队列 就是将队列存储空间最后一个位置绕到第一个位置 形成逻辑上的环状空间 供队列循环使用 循环队列中实际元素个数 Rear Front N modN 其中Rear为队尾 Front为队头N为循环队列最多可以存放元素个数 mod为取余运算 设某循环列队的容量为50 如果头指针front 45 指向队头元素的前一位置 尾指针rear 10 指向队尾元素 则该循环队列中共有 个元素 10 45 50 50 15 新航线培训中心 考点5线性链表 线性表的链式存储结构称为线性链表 链式存储结构 线性链表表示法 新航线培训中心 考点6树与二叉树 一 树的基本概念由一个或多个结点组成的有限集合 仅有一个根结点 结点间有明显的层次结构关系 新航线培训中心 考点6树与二叉树 结点 树中的元素 包含数据项及若干指向其子树的分支 结点的度 结点拥有的子树数 叶子 度为零的结点 也称终端结点 结点的层次 从根结点开始算起 根为第一层 深度 树中结点的最大层次数 4 新航线培训中心 考点6树与二叉树 二 二叉树及其基本性质二叉树是另一种树型结构 它的特点是每个结点最多只有二棵子树 即二叉树中不存在度大于2的结点 并且 二叉树的子树有左右之分 其次序不能任意颠倒 特别要注意 二叉树不是树的特殊情况 a a b b 两棵不同的二叉树 新航线培训中心 满二叉树 特点 每一层上都含有最大结点数 考点6树与二叉树 新航线培训中心 完全二叉树 特点 除最后一层外 每一层都取最大结点数 最后一层结点都集中在该层最左边的若干位置 考点6树与二叉树 新航线培训中心 A 二叉树的第i层上至多有2i 1 i 1 个结点 二叉树的基本性质 第三层上 i 3 有23 1 4个节点 第四层上 i 4 有24 1 8个节点 考点6树与二叉树 新航线培训中心 A 二叉树的第i层上至多有2i 1 i 1 个结点 B 深度为k的二叉树中至多含有2k 1个结点 二叉树的基本性质 此树的深度k 4 共有24 1 15个节点 考点6树与二叉树 新航线培训中心 A 二叉树的第i层上至多有2i 1 i 1 个结点 B 深度为k的二叉树中至多含有2k 1个结点 C 若在任意一棵二叉树中 有n0个叶子结点 有n2个度为2的结点 则 n0 n2 1 二叉树的基本性质 n0 8n2 7 考点6树与二叉树 新航线培训中心 A 二叉树的第i层上至多有2i 1 i 1 个结点 B 深度为k的二叉树中至多含有2k 1个结点 C 若在任意一棵二叉树中 有n0个叶子结点 有n2个度为2的结点 则 n0 n2 1D 具有n个结点的二叉树 其深度至少为 log2n 1 其中 log2n 表示取log2n的整数部分 二叉树的基本性质 考点6树与二叉树 新航线培训中心 二叉树遍历定义及遍历算法遍历是指按某条搜索路线寻访树中每个结点 且每个结点只被访问一次 考点6树与二叉树 遍历算法 1 前 先 序遍历 首选访问根结点 然后遍历左子树 最后遍历右子树 2 中序遍历 首先遍历左子树 然后访问根结点 最后遍历右子树 3 后序遍历 首选遍历左子树 然后遍历右子树 最后访问根结点 新航线培训中心 遍历算法 先序遍历 DLR中序遍历 LDR后序遍历 LRD A D B C T1 T2 T3 DLR 以先序遍历DLR为例演示遍历过程 ABDC BDAC DBCA 考点6树与二叉树 新航线培训中心 练习 若某二叉树的前序遍历访问顺序是abdgcefh 中序遍历访问顺序是dgbaechf 则其后序遍历的结点访问顺序是A bdgcefhaB gdbecfhaC bdgaechfD gdbehfca 参考答案 D 解析 前序遍历的第一个结点a为树的根节点 中序遍历中a的左边的结点为a的左子树 a的右边的结点为a的右子树 再分别对a的左右子树进行上述两步处理 直到每个结点都找到正确的位置 新航线培训中心 练习 已知二叉树后序遍历序列是dabec 中序遍历序列是debac 它的前序遍历序列是A acbedB decabC deabcD cedba 参考答案 D 解析 依据后序遍历序列可确定根结点为c 再依据中序遍历序列可知其左子树由deba构成 右子树为空 又由左子树的后序遍历序列可知其根结点为e 由中序遍历序列可知其左子树为d 右子树由ba构成 新航线培训中心 考点7查找技术 顺序查找 k 9 s 新航线培训中心 考点7查找技术 二分法查找 查找23的过程如下图 mid low high 2取整 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 新航线培训中心 考点8排序技术 插入排序 基本思想 从数组的第2号元素开始 顺序从数组中取出元素 并将该元素插入到其左端已排好序的数组的适当位置上 需要n n 1 2次比较 新航线培训中心 考点8排序技术 待排元素序列 53 2736156942第一次排序 2753 36156942第二次排序 273653 156942第三次排序 15273653 6942第四次排序 1527365369 42第五次排序 152736425369 插入排序示例 新航线培训中心 选择类排序法最坏情况下需要比较n n 1 2次 考点8排序技术 2810754 2810754 2410758 2457108 2457108 2457810 待排元素序列 第一次排序 第二次排序 第三次排序 第四次排序 第五次排序 新航线培训中心 练习 冒泡排序在最坏情况下的比较次数是A n n 1 2B nlog2nC n n 1 2D n 2 参考答案 C 解析 冒泡排序的基本思想是对当前未排序的全部结点自上而下依次进行比较和调整 让键值较大的结点下沉 键值较小的结点往上冒 也就是说 每当两相邻结点比较后发现它们的排列与排序要求相反时 就将它们互换 对n个结点的线性表采用冒泡