防伪码查询网站怎么做的,濮阳做网站建设的公司,电商网站开发外包,淮安市哪里有做网站数据结构 1.数据结构三要素是什么#xff1f;逻辑结构包括什么#xff1f;存储结构包括什么#xff1f; 逻辑结构、存储结构、数据运算 逻辑结构包括线性结构和非线性结构 线性结构包括线性表、栈、队列#xff0c;非线性结构包括树、图集合 存储结构包括顺序存储、链式存储…数据结构 1.数据结构三要素是什么逻辑结构包括什么存储结构包括什么 逻辑结构、存储结构、数据运算 逻辑结构包括线性结构和非线性结构 线性结构包括线性表、栈、队列非线性结构包括树、图集合 存储结构包括顺序存储、链式存储、索引存储和散列存储
2.O(n)的大O是什么意思什么是时间复杂度? ★★★ 算法效率的度量通过时间复杂度和空间复杂度。 大O表示的是最坏情况下的时间复杂度也就是最坏情况下算法中所有语句的频度之和的数量级一般用大O表示算法复杂度只需要取次数最高的项而且去掉系数就OK 频度语句重复执行的次数 时间复杂度就是用来衡量程序运行时间的一个描述可以用来方便开发者估算出程序的运行时间。 如果某一算法的时间复杂度为On2表明该算法的运行时间与n2这个数量级成正比。n表示问题规模。比如要遍历一个n×n的矩阵的所有元素时间复杂度就是On2 空间复杂度算法所消耗的存储空间用来存放指令、常数、变量等 算法原地工作指算法所需的辅助空间为常量空间复杂度为O1
3.什么是线性表什么是顺序表什么是链表 线性表是具有相同数据类型的n个数据元素的有限序列 顺序表是线性表的顺序存储特点表中元素的逻辑顺序与物理顺序相同 插入最好情况在表尾插入O1On 删除最好情况在表尾插入O1On 按值查找on 按位查找O1 单链表是线性表的链式存储 建立链表 头插法用于链表逆置、尾插法On 每插入一个O1 按位查找、按值查找O(n) 插入节点遍历链表查找第i-1个元素On插入O1 删除遍历查找第i-1个元素On插入O1
4.链表的种类 1单链表对每个链表节点除了存放元素自身的信息外还需要存放一个指向其后继的指针。 2双链表想要访问单链表的前驱结点时只能从头开始遍历时间复杂度高为此引入双链表。双链表结点中除了数据域有两个指针prior和next分别指向前驱结点和后继结点找某结点的前驱只需通过prior指针时间复杂度降为O1 3循环单链表最后一个结点的指针指向头结点使整个链表形成一个环。 循环双链表表尾结点的next指针指向头结点头结点的prior指针指向表尾结点。 好处单链表只能从表头结点开始遍历所有结点而循环单链表可以从表中的任一结点开始遍历整个链表。对单链表我们常常设立头指针这样在表头表尾操作的时间复杂度分别为O(1)和O(n)而对于循环列表常常设立尾指针不管是在表头操作还是表尾操作时间复杂度都为O1 4静态链表借助数组描述线性表的链式存储结构结点包括数据域和指针域指针域存放的是结点的相对地址数组下标又称游标。需要预先分配一块连续的内存空间。 优点增删改查不用移动大量元素。缺点不能随机存取容量固定不可变。应用场景不支持指针的高级语言Basic) 或 数据元素固定不变的场景如操作系统中的文件分配表FAT。
5.顺序存储结构和链式存储结构的优点★★★ 顺序存储结构的优点 1.最主要的特点是可以随机存取即通过首地址和元素序号可在时间O1内找到指定的元素链表只能从表头开始遍历顺序存取元素。 2.存储密度高每个节点只存储数据元素链式存储还要存指针存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比 3.各种语言都有数组方便顺序存储的实现好理解。
链式存储结构的优点 1.进行插入、删除操作时很方便不需要移动数据元素。 顺序存储在进行插入操作时需要将插入位置之后的元素全部后移一位时间复杂度为On而链式存储只需要修改插入位置前驱后继节点指针的指向时间复杂度为n1 2.不用预先估计存储空间的规模在需要时向内存申请空间即可操作灵活。 而顺序存储包含两种方式静态分配和动态分配若采用静态分配一旦存储空间满了就不能再扩充因此为了规避内存溢出的风险只能尽量分配足够大的存储空间但这样又会导致空间的浪费。而动态分配虽然可以扩充存储空间但是需要移动大量元素操作效率低。
索引存储 优点检索速度快 缺点附加的索引表额外占用存储空间增加和删除元素时也要修改索引表。
6.解释一下顺序存储与链式存储★★★ 顺序存储是指在内存中开辟连续的存储空间来存放数据把逻辑上相邻的元素存储在物理位置也相邻的存储单元中。 链式存储的存储空间不是连续的借助指示元素存储地址的指针来表示元素间的逻辑关系。对每个链表节点除了存放元素自身的信息外还需要存放一个指向其后继的指针通过指针指向下一元素将所有的元素串起来从而形成了一个链表。 索引存储存储元素信息的同时还简历附加的索引表。 散列存储根据元素的关键字直接计算出该元素的存储地址。
7.头指针和头结点的区别★★ 不管带不带头结点头指针始终指向链表的第一个结点而头结点是带头结点链表中的第一个结点结点内通常不存储信息它是为了方便做的一种处理。 引入头结点的优点 1.由于第一个数据节点的位置被存放在头结点的指针域中因此在链表的第一个位置上的操作和在链表其他位置上的操作一致无需进行特殊处理。 2.无论链表是否为空其头指针都是指向头结点的非空指针因此空表和非空表的处理也得到了统一。
8.判断链表是否有环非常重要★★★★★★★ “快慢指针”创建两个指针fast和slow开始时两个指针都指向链表头head在每一步操作中slow向前走一步fast向前走两步由于fast比slow移动的快如果有环两个指针就会相遇。
9.栈和队列的区别和内存结构★★★ 栈Stack是只允许在一端进行插入和删除操作的线性表先进后出FILO) 队列Queue是只允许在表的一端进行插入而在表的另一端进行删除的线性表先进先出FIFO 栈栈有两种存储方式采用顺序存储的栈称为顺序栈采用链式存储的栈称为链栈。顺序栈利用一组地址连续的存储单元存放数据元素同时附设一个指针指示当前栈顶元素位置。链栈是利用一个单链表存储数据元素并将表头作为栈顶进行插入和删除操作。 队列队列也是分为顺序存储和链式存储两种方式顺序存储是利用一组地址连续的存储单元存放数据元素并附设两个指针通常front指针指向队头元素rear指针指向队尾元素的下一个位置。链式存储是利用一个带有头指针和尾指针的链表存储数据元素。
10.有一个循环队列Q里面的编号是0到n-1头尾指针分别是frontrear现在求Q中元素的个数★★ 因为出队操作会导致队头的存储空间空闲当rear指针指到maxsize的时候其实是一种“假溢出”这时候队列并没有满。为了解决这个问题我们把存储队列元素的表从逻辑上视为一个环称为循环队列。 初始frontrear0 出队front (front1)%maxsize 队头指针加一取模 入队rear (raer1)%maxsize 队尾指针加1取模 队列长度(rear-frontmaxsize)%maxsize
11.如何区分循环队列是队空还是队满★★★ 队满条件和队空条件都是rear front 因此为了区分这两个条件可以采用的处理方式为 1.入队时少用一个存储单元将差一个不满的条件视为队满判断队空条件不变队头和队尾指针在同一位置时队空 rear front判断队满条件变为队头指针在队尾指针的下一位置时队满也就是rear1%maxsize front 2.增设一个数据成员记录元素个数队空条件为size 0队满条件为sizemaxsize。
12.栈的应用 1括号匹配匹配过程为从左至右扫描表达式每当遇到一个右括号时就判断他和最后出现的那个左括号是否匹配因此用栈存储被扫描到的左括号。每当扫描到右括号时就让栈顶的左括号出栈。 2后缀表达式的运算运算过程是从左到右扫描表达式每遇到一个运算符就让运算符前面最近的两个操作数执行对应运算合体成一个新的操作数。最后出现的操作数最先被运算所以用栈来存储操作数。 3中缀表达式转后缀表达式栈中存储还未确定运算顺序的运算符。 4递归最后被调用的函数最先执行结束。 5进制转换以二进制转十进制为例读入顺序为从低位到高位而为了简化权值的计算应该从低位到高位加权先读入的数后加权因此用栈存储。 6迷宫求解 7深度优先搜索图 8前序遍历二叉树
13.队列的应用 1层次遍历先被遍历的结点他的孩子也会先被遍历到将遍历视为入队将遍历其孩子结点视为出队的话就是先进先出因此用队列存储。 2图的广度优先遍历先被遍历的结点与他邻接的顶点也会先被遍历到如果将遍历视为入队将遍历其邻接顶点视为出队的话就是先进先出因此用队列存储。 3打印机缓冲区主机和外部设备速度不匹配先进入缓冲区排队的先打印 4CPU资源竞争中的先来先服务策略
14.介绍一下字符串匹配算法朴素的匹配算法和KMP算法。如何实现要会用语言描述★★★ (1)子串的定位操作称为串的模式匹配求的是子串模式串在主串中的位置。 (2)朴素模式匹配算法这个方法也称为暴力匹配。就是从源字符串开始搜索若出现不能匹配则从原搜索位置1进行搜索。将主串中所有与给定子串长度相同的子串依次与模式串进行对比直到找到一个完全匹配的子串或所有子串都不匹配为止。主串长度n模式串长度m最坏情况下共需对比n-m1个子串每个子串对比m个字符时间复杂度为O(n*m)很高。 (3)KMP算法 KMP算法的思想是利用匹配失败后的信息尽量减少子串与主串的匹配次数以达到快速匹配的目的。 算法实现的关键是求出next数组next[j]表示在子串的第j个字符与主串发生失配时则跳到子串指针应该移动到的位置。 求next数组的方法在不匹配的位置前画一个分界线模式串一步步右移直到分界线之前能匹配或者模式串完全跨过分界线为止。此时子串指针j指向哪儿next数组的值就是多少。 匹配方法匹配过程产生失配时主串指针i不变子串指针j退回到next[j]的位置并重新进行比较。 时间复杂度求next数组Om模式匹配On),O(mn)主要优点是主串不回溯。
15.树的特点与基本术语 (1)树的根结点没有前驱其他结点都只有一个前驱 (2)树中的所有结点都只有0个或多个后继
(1)祖先根到结点K的路径上的任意结点都是结点K的祖先 (2)结点的度一个结点的孩子个数 (3)树的度数中所有结点的最大度数
16.平衡二叉树、二叉排序树、完全二叉树、二叉搜索树的区别及如何构造★★★ 每个结点至多有两棵子树并且子树有左右之分不能任意颠倒。 (1)满二叉树除了叶子结点外其余节点度全为2 (2)完全二叉树完全二叉树中除了最后一层外其余每层都含有最多结点数叶子结点只可能在层次最大的两层上出现。 (3)二叉树排序左子树上所有结点的关键字均小于根结点的关键字右子树上所有结点的关键字均大于右子树的关键字左子树、右子树又各是一棵二叉排序树。 (4)平衡二叉树树上任一结点左子树和右子树深度之差不超过1.
(1)二叉树的顺序存储用一组地址连续的存储单元依次从上到下、从左到右存储完全二叉树上的结点元素即将完全二叉树上的标号为i的结点存储在数组下标为i-1的存储单元中。对于一般二叉树为了让数组下标反映二叉树中结点的逻辑关系只能添加一些空结点让每个结点与完全二叉树上的结点相对照但会造成存储空间的浪费。 (2)二叉树的链式存储用链表结点存储二叉树的每个结点二叉链表包括数据域、左指针域、右指针域分别指向其左子树和右子树的根节点。
17.如何由遍历序列构造一颗二叉树/已知先序序列和后序序列能否重现二叉树笔试经常考★★★ 不能没有中序遍历序列的情况下是无法确定一颗二叉树的 18.二叉树的遍历 先序遍历访问根节点----先序遍历左子树----先序遍历右子树 中序遍历中序遍历左子树----访问根节点----中序遍历右子树 后序遍历后序遍历左子树----后序遍历右子树----访问根节点 层次遍历借助队列先将二叉树的根节点入队然后出队访问出队结点若他有左子树则将左子树的根节点入队若他有右子树则将右子树的根节点入队。然后再出队访问出队结点。。。。直至队列为空
19.线索二叉树 在含有n个结点的二叉树中会有n1个空指针可以利用这些指针存放当前结点的前驱和后继指针引入线索二叉树可以加快查找结点前驱和后继的速度。 要增加两个标志域标识指针域是指向左右孩子的还是指向前驱后继的。
20.树的存储结构 (1)双亲表示法采用一组连续的存储空间来存储每个结点同时在每个结点中增设一个伪指针指示其双亲结点在数组中的位置。优点可以很快找到每个结点的双亲结点。缺点求结点的孩子时要遍历整个结构。 2孩子表示法将每个结点的孩子结点都用单链表链接起来形成一个线性结构。优点寻找子女方便寻找双亲则需要遍历n个结点的孩子链表。 3孩子兄弟表示法以二叉链表作为存储结构。每个结点包括三部分内容结点值、指向第一个孩子结点的指针、指向下一个兄弟结点的指针。“左孩子右兄弟”优点方便实现树转换为二叉树的操作易于查找孩子。缺点找双亲结点比较麻烦。
21.树、森林、二叉树的转换 1树–二叉树每个结点左指针指向它的第一个孩子右指针指向它在树中相邻的右兄弟。 2森林–二叉树将森林中的每棵树都转换为二叉树将第二棵二叉树作为第一棵的右子树将第三棵二叉树作为第二棵二叉树的右兄弟以此类推直至只剩下唯一一棵二叉树。 3二叉树–森林将根节点右链断开形成两棵二叉树以此类推直至所有二叉树根节点都不存在右子树最后将每棵二叉树都转换为树得到森林。
22.树与二叉树的应用哈夫曼树、并查集 1哈夫曼树是带权路径长度最小的二叉树 2构造方法首先将这n个结点构成森林每次在森林中找到两棵权值最小的树作为新结点的左右子树并将新结点的权值设为左右子树权值之和。在森林中删除选出的两棵树并将新得到的树加入森林。重复上述步骤直至森林中仅剩一棵树就是哈夫曼树。 3哈夫曼树的用途哈夫曼编码。将每个字符当作一个独立的结点其权值为他出现的频度构造出哈夫曼树。将转向左孩子的边标记为0转向右孩子的边标记为1依次读出每个结点路径的标记即可得到字符的哈夫曼编码。 好处出现频率高的字符被赋予了更高的权值而在哈夫曼树中处于上层得到更短的编码这样可以缩短总体的编码长度降低传输难度。在构造哈夫曼树的过程中所有字符结点均作为哈夫曼树的叶子节点一个叶子节点不会成为另一个叶子结点的祖先因此不会存在一个编码是另一个编码的前缀的现象不会造成解码上的错误。 4并查集每一个集合以森林中的一棵树表示集合的并操作就转化成了合并两棵树只需要改变第二棵树根节点的指向集合的查操作就转化成了判断两个结点是否在同一棵树中。
23.图的基本概念 (1)图是由顶点集和边集构成边集可为空顶点集不可为空 (2)完全图在全图的任意两个顶点间都存在边 (3)子图设有两个图其中一个图的顶点集和边集分别是另一个图顶点集和边集的子集 (4)连通在无向图中若两个顶点间有路径则称两个顶点连通。 连通图图中任意两个顶点连通 连通分量无向图中的极大连通子图 (5)强连通在有向图中如果有一对顶点v和w从v到w和从w到v都有路径则称这两个顶点是强连通的 强连通图每对顶点都是强联通的 强连通分量极大强连通子图 (6)生成树包含图中全部顶点的极小连通子图。
24.邻接表和邻接矩阵如何存储大数据★ (1)邻接矩阵法适用于存储稠密图用一个一维数组存储图中顶点信息用一个二维数组存储图中边的信息即各顶点间的邻接关系存储顶点之间邻接关系的二维数组称为邻接矩阵。空间复杂度O(n2),n为图中顶点个数。 (2)邻接表法适用于存储稀疏图图中顶点用一个一维数组存储存储顶点数据和边表头指针。为每个顶点建立一个单链表存储依附于此顶点的边这个单链表就成为边表对于有向图来说叫出边表空间复杂度无向图每条边存储了两次OV2E 有向图OVE
25.介绍一下深度优先搜索和广度优先搜索是如何实现的★★★ (1)广度优先搜索非递归类似于二叉树的层序遍历算法是一种分层的查找过程每向前走一步可能访问一批顶点不像深度优先遍历那样有往回退的情况。基本思想先访问起始顶点v再由v出发依次访问v未被访问过的邻接顶点w1、w2…然后依次访问w1、w2…的未被访问过的顶点重复这个过程直至图中所有顶点都被访问过为止。 实现借助一个辅助队列先把初始顶点入队然后每访问一个顶点就要把此顶点出队然后把顶点未访问过的邻接顶点依次入队直至队空。 时间复杂度访问顶点的时间找邻接顶点的时间即访问边的时间采用邻接表存储方式O(VE)采用邻接矩阵存储方式OV2
(2)深度优先搜索递归深度优先搜索类似于树的先序遍历他的策略是尽可能深的搜索一个图。 基本思想是首先访问图中某一起始顶点v然后由v出发访问与v邻接但未被访问的顶点w1再访问与W1邻接但未被访问的顶点w2…重复上述过程当不能再向下访问时依次退回到最近被访问的结点若他还有顶点未被访问过则从该点开始继续上述的搜索过程直至图中所有顶点都被访问过为止。 实现递归实现 时间复杂度访问顶点的时间找邻接顶点的时间即访问边的时间采用邻接表存储方式O(VE)采用邻接矩阵存储方式OV2
26.最小生成树和最短路径用什么算法来实现迪杰斯特拉、弗洛依德、普利姆、克鲁斯卡尔算法的基本思想是什么算法的时间复杂度如何进行优化必考★★★★★★★ 一最小生成树 生成树包含图中全部顶点的极小连通子图 1Prim(普里姆)归并顶点 思路从某一顶点开始构建生成树每次将代价最小的新顶点纳入生成树直到所有顶点都纳入为止。 实现方法两个数组一个用来存储各顶点加入生成树的最小代价一个用来存储各顶点是否已经加入了最小生成树。每次归并一个新顶点前要遍历这两个数组找到还未加入树且权值最小的顶点归并一个新顶点后要更新这两个数组。 时间复杂度此算法是双层循环外层循环控制次数一共要归并n个顶点因此要循环n-1次内层并列两个循环每个循环负责遍历一个数组其时间复杂度为on因此此算法的时间复杂度为On2时间复杂度只与顶点有关与边无关适用于稠密图。
2Kruskal克鲁斯卡尔归并边 思路每次选择一条权值最小的边且这条边所连的2个顶点间还未存在路径我们使这条边两头连通重复上述操作直至所有结点都连通。 实现方法将图中边按照权值从小到大排列然后从最小的边开始扫描设置一个边的集合来记录如果该边并入不构成回路的话则将该边并入当前生成树。直到所有的边都检测完为止。 时间复杂度用堆来存放边的集合OlogE用并查集来判断2顶点是否连通是否属于同一个集合O(E logE) 时间复杂度只与边有关适合边稀疏顶点多的图
二、最短路径 1广度优先遍历解决无权图的单源最短路径问题 实现方法需要借助一个数组和一个辅助队列。先把初始顶点入队然后每访问一个顶点v就要把v出队然后把v未访问过的邻接顶点w1、w2…依次入队并把他们的最短路径长度改为v的最短路径长度1重复上述操作直至队空。 时间复杂度访问顶点的时间找邻接顶点的时间即访问边的时间采用邻接表存储方式O(VE)采用邻接矩阵存储方式OV2 (2)Dijkstra(迪杰斯特拉)(带权图/无权图的最短路径) 思路设置一个集合s记录已经求得最短路径的顶点初始时把源点加入此集合集合每并入一个新顶点都要修改源点到未求得最短路径的顶点的最短路径长度重复上述过程使得所有顶点都加入集合。与prim相似贪心算法 时间复杂度算法的核心部分在于一个双重循环外层循环控制算法进行的轮数每次循环归并一个顶点且共有n个顶点所以算法需要进行n轮。双重循环的内循环又是两个并列的单重for循环组成(找距离最小顶点和更新距离),时间复杂度为O(n2) 其中n为图中的顶点数。
3Floyd(弗洛伊德) 思路首先初始化一个方阵如果两个顶点间有边就用边的权值作为最短路径存入方阵。然后逐步尝试在原路径中加入顶点k作为中间顶点。若路径变短则替代源路径并形成新的方阵。 时间复杂度算法的核心为一个三重循环外层循环用来控制迭代次数每考虑将一个顶点作为中转点就会迭代一次因此外层循环要循环n-1次。内层的两层循环用来遍历矩阵更新最短路径长度所以时间复杂度为O(n3) 其中n是图中的顶点数。
27.拓扑排序 AOV网是顶点表示活动的网络边ViVj表示活动i必须先于活动j进行。 对AOV网进行拓扑排序的步骤从AOV网中选择一个没有前驱的顶点并输出然后从网中删除该顶点和所有以它为起点的有向边重复上述步骤直到AOV网为空或者不存在无前驱的顶点为止。 时间复杂度由于删除每个顶点的同时还要删除以他为起点的边因此每个顶点和每条边都会被遍历一次。采用邻接表存储方式O(VE)采用邻接矩阵存储方式OV2
28.关键路径 AOE网顶点表示事件边表示活动边上的权值表示活动开销 在AOE网中有些活动是可以并行的从源点到汇点的路径可能有很多条具有最大路径长度的路径称为关键路径而把关键路径上的活动称为关键活动。。完成整个工程的最短时间就是关键路径的长度。 29.查找算法的评价指标平均查找长度ASL 所有查找过程中进行关键字的比较次数的平均值
30.顺序查找线性查找 基本思想从线性表的一端或者链表的表头开始逐个检查关键字是否满足给定条件。若找到则查找成功。若已经查找到线性表的另一端或者链表的表尾还没有找到则查找失败。 优化思路1若表是关键字有序的则查找失败时可以不用再比较到表的另一端就能返回失败信息降低查找失败的平均查找长度。 优化思路2若每个元素被查的概率不等则将被查概率大的放在靠前的位置。
31.折半查找二分查找仅适用于有序的顺序表 每次确定中间元素后都需要通过数组下标拿到它的值因此需要随机存取的特性只能使用线性表。 基本思想在有序表中取中间元素作为比较对象如果要查找的值和中间元素的关键字相等则查找成功若小于中间元素的关键字则在中间元素的左半区继续查找若大于中间元素的关键字则在中间元素的右半区继续查找。重复上述过程直到查找成功。 实现方法初始化一个数组A存放有序表中元素初始化三个伪指针lowhighmid分别表示查找区域的最左元素下标查找区域的最右元素下标以及当前比较元素下标。如果A[mid]查找值key则让highmid-1查找左半区如果A[mid]key则让lowmid1查找右半区。直至A[mid]key或者lowhigh为止。 时间复杂度折半查找的查找过程可以用一棵平衡二叉树表示根据元素个数可以计算出树的高度为log2(n1)每次查找的最多查找次数等于树的高度因此时间复杂度为Olog2 n(以二为底n的对数)
32.分块查找 基本思想将查找表分为若干子块块内元素无序块间有序即第一个块中的最大关键字小于第二个块中所有记录的关键字以此类推。再建立一个索引表索引表中的每个元素含有各块的最大关键字和各块第一个元素的地址索引表按关键字有序排列。 查找过程分为两步第一步是在索引表中确定待查记录所在的块可以顺序或折半查找索引表第二步是在块内顺序查找。
33.二叉排序树BST 定义左子树上所有结点的关键字均小于根结点的关键字右子树上所有结点的关键字均大于右子树的关键字左子树、右子树又各是一棵二叉排序树。 查找先将给定值与根节点的关键字比较如果相等则查找成功如果小于根节点关键字则在左子树上查找如果大于根节点关键字则在右子树上查找这是一个递归的过程。 构造从一棵空树出发依次输入元素将他们插入二叉排序树中的合适位置使其符合二叉排序树定义。 删除如果删除节点是叶节点则直接删除如果是非叶节点且只有一棵子树则让这棵子树成为被删除结点父节点的子树若是非叶节点且有左右两棵子树则用被删除节点的直接前驱或者直接后继中序遍历替代。 平均查找长度二叉排序树的平均查找长度主要取决于树的高度。最好情况二叉排序树的平衡的左右子树高度之差不超过1Olog2 n最坏情况二叉排序树是一个只有左右孩子的单支树On
34.平衡二叉树AVL 引入目的为避免树的高度增长过快降低二叉排序树的性能。 定义任意节点左右子树高度之差的绝对值不超过1的树。 结点的平衡因子结点左子树和右子树的高度差 插入每当在二叉排序树中插入删除一个结点时首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。如果导致了不平衡则先找到插入路径上离插入节点最近的平衡因子的绝对值大于1的结点A再对以A为根的子树最小平衡子树在保持二叉排序树特性的前提下调整各节点的位置关系使之重新达到平衡。 设最小平衡子树的根节点为A 如果由于在结点A的左孩子的左子树上插入新节点而导致失去平衡则通过一次右单旋转调整。 如果由于在结点A的右孩子的右子树上插入新节点而导致失去平衡则通过一次左单旋转调整。 如果由于在结点A的左孩子的右子树上插入新结点而导致失去平衡则先通过一次左旋再通过一次右旋调整。 如果由于在结点A的右孩子的左子树上插入新结点而导致失去平衡则先通过一次右旋再通过一次左旋调整。 平均查找长度含有n个节点的平衡二叉树的最大深度为Olog2 n因此平衡二叉树的平均查找长度为Olog2 n
35.红黑树RBT原理是什么建立过程★★★ 引入目的为了保持AVL树的平衡性在进行插入和删除操作后需要频繁地调整全数的整体拓扑结构代价较大。因此在AVL树的平衡标准上进一步放宽条件形成红黑树。对于红黑树来说插入删除操作很多时候不会破坏其红黑特性无需频繁调整树的形态即使要调整也可以在常数级时间内完成。 定义红黑树是满足如下红黑性质的二叉排序树 1每个结点是红色或者黑色的 2根、叶节点是黑色的 3不存在两个相邻的红结点 4对于每个结点从该结点到任一叶结点的简单路径上所含黑结点数量相同。 插入先进行查找操作确定插入位置并插入。如果新结点是根则染为黑色若新节点非根则染为红色。如果插入后不满足红黑树定义则需要调整使其重新满足红黑树定义。
36.B树多路平衡查找树 B树的阶B树中所有结点的孩子个数最大值 定义B树是满足如下特性的m叉树 1树中每个结点至多有m棵子树即至多有m-1个关键字 2若根节点不是终端结点则至少有两棵子树。 3除根节点外的所有非叶结点至少有m/2棵子树 4所有叶结点都出现在同一层次上并且不携带信息 查找1在B树里找结点2在结点里找关键字 插入1首先进行查找操作找出插入该关键字的最低层中的某个非叶节点。 2进行插入操作如果插入后被插入节点的关键字个数超过m-1则需要对节点进行分裂。分裂方法是从中间位置将关键字一分为二左部分放在原结点中右部分放在新结点中中间位置的关键字插入原节点的父结点中。若此时导致父节点关键字个数也超过上限则继续分裂。 删除如果被删除的关键字k不在终端结点中时可以用k的前驱或者后继来替代k。如果被删除的关键字在终端结点则有2种情况如果被删除关键字所在节点删除前的关键字个数m/2则直接删除。反之需要重新调整结点向兄弟结点借一个关键字或者与兄弟节点和双亲结点中的关键字进行合并。 用作数据库索引
37.B数和B树的区别★★★ 1在B树中具有n个关键字的结点只含有n棵子树即每个关键字对应一棵子树。而在B树中具有n个关键字的结点含有n1棵子树。 2在B树中叶结点包含了全部关键字即在非叶结点中出现的关键字也会出现在叶结点中。而在B树中叶结点包含的关键字与其他结点包含的关键字是不重复的。 3在B树中非叶节点仅起索引作用叶结点包含关键字对应记录的存储地址.而B树的结点中都包含关键字对应记录的存储地址。
38.哈希表的概念、构造方法、哈希有几种类型哈希冲突的解决办法★★★★ 定义根据关键字而直接进行访问的数据结构 构造方法 1直接定址法直接取某个线性函数值作为散列地址不会产生冲突适合关键字分布基本连续的情况若不连续则空位较多会造成存储空间浪费 2除留取余法取一个最接近散列表表长的质数p散列函数为key%p 3数字分析法选取数码分布较为均匀的若干位作为散列地址 4平方取中法取平方值的中间几位作为散列地址。 处理冲突的方法 1开放定址法可存放新表项的空闲地址既向他的同义词表项开放又向他的非同义词表项开放。 A、线性探测法冲突发生时顺序查看表中下一个单元直到找出一个 空闲单元缺点大量元素在相邻的散列地址上堆积起来降低了查找效率。 B、平方探测法增量序列为0212-1222…以此类推。优点避免出现堆积问题缺点不能探测到散列表上的所有单元。 C、双散列法需要使用两个散列函数当通过第一个散列函数得到的地址发生冲突时则利用第二个散列函数计算该关键字的地址增量。 D、伪随机序列法增量为随机数。 2拉链法把所有同义词存储在一个链表中将散列地址为i的同义词链表的头指针存放在散列表的第i个单元中。 查找效率取决于散列函数、处理冲突的方法和装填因子。装填因子定义为一个表的装满程度表中记录数/散列表长度。
39.查找算法时间复杂度比较 查找算法 时间复杂度 顺序查找线性查找 On 折半查找二分查找 Olog2 n 分块查找 二叉排序树BST Olog2 n----O(n) 平衡二叉树AVL Olog2 n
线性结构 顺序查找 折半查找 分块查找 树形结构 二叉排序树 二叉平衡树 红黑树 B树、B树 散列结构 散列表
40.排序的定义 算法的稳定性两个关键字相同的元素排序前后相对顺序不变 排序算法分类 1内部排序排序期间元素全部存放在内存中关注如何降低时间复杂度 2外部排序在排序期间元素无法全部同时存放在内存中必须在排序过程中不断在内外存之间移动元素。关注如何使读写磁盘次数减少
41.直接插入排序 思路每次将一个待排序的记录按其关键字大小插入前面已经排好序的子序列直到全部记录插入完成。 空间复杂度使用常数个辅助单元空间复杂度为O1 时间复杂度最好表中元素有序每插入一个元素只需要比较一次而不需要移动 On最坏表中元素逆序On2
42.折半插入排序 思路每次将一个待排序的记录通过折半查找找出其在前面已经排好序的子序列中的待插入位置然后统一的移动待插入位置之后的所有元素将其插入。 实现初始化一个数组A存放已经排好序的子序列初始化三个伪指针lowhighmid分别表示查找区域的最左元素下标查找区域的最右元素下标以及当前比较元素下标。如果A[mid]查找值key则让highmid-1查找左半区如果A[mid]key则让lowmid1查找右半区。直至lowhigh时停止查找将low指针及之后的元素全部右移一位并将元素插入到low指针所指位置。 时间复杂度仅减少了比较元素的次数约为Onlog2 n元素移动次数未改变O(n2)因此时间复杂度还是On2
43.希尔排序缩小增量排序 只能用于顺序存储按照给定增量找子表时需要随机存取特性 直接插入排序的时间复杂度为On2如果待排序序列是正序其时间复杂度可提高至On由此可见直接插入排序适用于基本有序和数据量不大的排序表希尔排序通过以上两点对直接插入排序进行了改进。 思路把相隔某个增量d的记录组成一个子表对各子表分别进行直接插入排序缩小增量d重复上述过程直至d为1为止。 空间复杂度仅使用了常数个辅助单元空间复杂度为O1 时间复杂度约为On1.3最坏情况下为On 稳定性不稳定相同关键字的记录被划分到不同的子表时可能会改变它们之间的相对次序。
44.冒泡排序 思路从后往前两两比较相邻元素的值若为逆序则交换他们直至将最小的元素交换到待排序序列的第一个位置即为一趟冒泡。下一趟冒泡时前一趟确定的最小元素不再参与比较。重复进行冒泡直至元素不再发生交换为止。 时间复杂度最好情况当初始序列有序时进行一趟冒泡即可跳出循环时间复杂度为On。最坏情况放初始序列为逆序时要进行n-1趟冒泡第i趟冒泡要进行n-i次关键词比较因此时间复杂度为On2 稳定性稳定关键字相同时元素不发生交换 空间复杂度O1
45.快速排序是所有内部排序算法中平均性能最优的排序算法 思路在待排序表中取一个元素作为枢轴通过一趟排序将待排序表分为两部分左子序列中所有元素均小于枢轴右子序列中所有元素均大于枢轴然后在左右子序列重复该过程直到所有元素都排列在相应位置上为止。 每次由一个枢轴将待排序序列分成左右两部分这个过程类似于构造一棵二叉树最小高度为log2 n,最大高度为n 空间复杂度快速排序是递归的需要一个递归工作栈实现其容量与递归调用的最大深度一致。最好情况下Olog2 n最坏情况下On平均Olog2 n 时间复杂度最好每次选择的枢轴元素都能将序列化分成均匀的两部分Onlog2 n最坏初始排序表基本有序或者逆序时On2。 稳定性不稳定
46.简单选择排序 思路每一趟比如第i趟在后面n-i1个待排序元素中选取关键字最小的元素与第i个元素进行交换每一趟排序可以确定一个元素的最终位置经过i-1趟排序就可以让整个排序表有序。 空间复杂度O1 时间复杂度On2 稳定性不稳定
47.堆、大顶堆、小顶堆实现及应用 ★★ 堆是一种特殊的完全二叉树 大顶堆每个父节点的值都大于孩子节点 小顶堆每个父节点的值都小于小子节点 堆排序思路以从大到小排序为例首先将元素构成初始大根堆输出堆顶元素并把堆底元素送入堆顶。此时根节点已经不满足大根堆的性质堆被破坏将堆顶元素向下调整使其继续满足大根堆的性质再输出栈顶元素。重复上述步骤直至堆中仅剩一个元素为止。 插入先将新结点放在堆的末端再对新结点向上调整。 删除被删除元素用堆底元素替代然后将该元素不断向下调整。 空间复杂度O1 时间复杂度建堆时间为On)之后进行n-1次向下调整每次调整时间复杂度为Oh,时间复杂度为Onlog2n 稳定性不稳定
48.归并排序 归并的含义是将两个或两个以上的有序表组合成了一个新的有序表。 二路归并排序将待排序表中的n个记录视为n个有序子表每个子表长度为1。然后两两归并得到n/2个长度为2的有序表继续两两归并直至归并成一个长度为n的有序表为止。 实现初始化两个数组A和B将两个要进行归并操作的有序表复制到数组B的相邻位置每次从B中的两个有序表分别取出一个关键字进行比较将大的存入A重复上述操作直至B空。 空间复杂度On 时间复杂度Onlog2 n 稳定性稳定
49.基数排序 不基于比较和移动而是基于关键字各位的大小进行排序。 思路设置r个空队列按照各个关键字位权重递增的次序对d个关键字位分别进行分配和收集操作。分配顺序扫描各个元素根据当前处理的关键字位将元素插入相应队列。收集把各个队列中的结点依次出队并连接。 空间复杂度Orr是队列数 时间复杂度基数排序需要进行d趟分配和收集d是关键字位数一趟分配要On一趟收集要Or时间复杂度为Od(nr) 稳定性稳定
50.插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序必考、堆排序、基数排序等排序算法的基本思想是什么时间复杂度是否稳定给一个例子问冒泡和快速排序在最坏的情况下比较几次排序必考★★★★★★
排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性插入排序 直接插入排序 On2 O(n) O(n2) O1 稳定 折半插入排序 On2 稳定 希尔排序 Onlog2 n—O(n2) On1.3 On2 O1 不稳定 交换排序 冒泡排序 On2 O(n) O(n2) 0(1) 稳定 快速排序 Onlog2 n O(nlog2 n) O(n2) O(log2 n)–O(n) 不稳定 选择排序 简单选择排序 On2 O(n2) O(n2) O(1) 稳定 堆排序 Onlog2 n O(nlog2 n) O(nlog2 n) 0(1) 不稳定 归并排序 O(nlog2 n) O(nlog2 n) O(nlog2 n) On 稳定 基数排序 Od(nr) O® 稳定
