数据结构考研复试、工作面试常见问题及答案

数据结构考研复试、⼯作⾯试常见问题及答案⽂章⽬录1、逻辑结构与物理结构（存储结构）的区别？答：逻辑结构是指数据元素之间的逻辑关系，⽽物理结构则是数据的逻辑结构在计算机中的存储形式。逻辑结构分类：（1）集合：各个元素之间是“平等”的，类似于数学⾥⾯的集合（2）线性结构：数据结构中的数据元素是⼀对⼀关系的（3）树形结构：数据结构中的数据元素之间存在⼀对多的层次关系（4）图形结构：数据结构中的数据元素之间存在多对多的关系物理结构分类：（1）顺序存储结构：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。优点：可以实现随机存储，每个元素占⽤最少的存储空间。缺点：只能使⽤相邻的⼀整块存储单元，因此可能产⽣较多的外部碎⽚。（2）链式存储结构：不要求逻辑上相邻的元素在物理位置上也相邻，借助指⽰元素存储地址的指针来表⽰元素之间的逻辑关系。优点：不会出现碎⽚的现象，能充⽅利⽤所有存储单元。缺点：每个元素因存储指针⽽占⽤额外的存储空间，且只能实现顺序存储。（3）索引存储结构：在存储元素信息的同时，还建⽴附加的索引表，索引表中的每项称为索引项，索引项的⼀般形式是（关键字，地址）。优点：检索速度快。缺点：附加的索引表额外占⽤存储空间，。另外，增加和删除数据也要修改修改索引表，因⽽会花费较多的时间。（4）散列存储结构：根据元素的关键字直接计算出该元素的存储地址，⼜称为哈希（Hash）存储。优点：检索、增加和删除结点的操作都很快。缺点：若散列函数不好，则可能出现元素存储单元的冲突，⽽解决冲突会增加时间和空间开销。2、算法的特点？算法的五⼤特征：（1）有穷性：有限的步骤（2）确定性：不可⼆义性（3）可⾏性：每⼀步都是通过执⾏有限次数完成的（4）输⼊：零个或多个输⼊（5）输出：⾄少有⼀个或多个输出好的算法包括：正确性、可读性、健壮性（当输⼊数据不合法时，算法也能做出相应的反应）、效率与低存储需求时间复杂度：算法的执⾏时间与原操作的执⾏次数之和成正⽐空间复杂度：如果输⼊数据所占空间只取决于问题本⾝，⽽与算法⽆关，只需要分析除了输⼊和程序之外的辅助变量所占⽤的空间即可。3、常见的数据结构？数据结构：指相互之间存在⼀种或者多种特定关系的数据元素的集合。常见的数据结构：（1）数组：⼀维数组、⼆维数组（2）链表：单链表、循环链表（3）栈：先进后出、递归、后缀表达式、函数调⽤（4）队列：先进先出、树的层次遍历、图的⼴度遍历（5）树：⼆叉树、森林、平衡⼆叉树、线索⼆叉树、遍历（6）图：有向图、⽆向图、遍历、最短路径4、链表结构和顺序存储结构的区别？顺序存储结构：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。链式存储结构：不要求逻辑上相邻的元素在物理位置上也相邻，借助指⽰元素存储地址的指针来表⽰元素之间的逻辑关系。顺序存储结构：读取⽅便O(1)插⼊删除需要移动⼤量元素（平均需要移动半个表长的元素）空间分配：⼀次性存储密度=1链式存储结构：读取不⽅便，需要遍历O(n)插⼊删除⽅便，只需要改变指针空间分配，：在需要的时候分配存储密度<1存储密度=（结点数据本⾝所占的存储量）/（结点结构所占的存储总量）5、线性链表？线性链表中⼀个节点代表⼀个存储空间，即节点。每⼀个节点包括两个部分，⼀个⽤来存储数据，⼀个存储下⼀个元素的地址。6、数组和链表的区别？数组：事先定义长度，不能适应数据动态地递减从栈中分配空间快速访问数据元素，插⼊删除不⽅便链表：动态地进⾏存储分配，可以适应数据动态地递减从堆中分配空间查找访问数据不⽅便，插⼊删除数据⽅便7、判断⼀个链表是否有环，如何找到这个环？题问：给定⼀个单链表，只给出头指针h：（1）如果判断是否存在环？对于判断⼀个单链表是否存在环，可以利⽤追赶的⽅式，设⽴两个指针slow、fast果没有环，fast遇到NULL退出。，从头指针开始，每次分别前进⼀步和两步，如果存在环，则两者相遇；如（2）如何知道环的长度？在slow和fast相遇的地⽅标记，再次相遇所⾛过的操作数就是环的长度。（3）如何找出环的连接点在哪⾥？分别从相遇点和头指针开始⾛，再次相遇的那个点就是连接点。（4）带环链表的长度是多少？连接点距离头指针的长度，加上环的长度，即为链表长度。8、单链表和双链表的区别？单链表：只能向后访问，不能逆向访问双链表：在单链表的基础上添加⼀个指向前驱节点的指针域，实现双向遍历9、头指针和头结点的区别？头指针：是链表指向第⼀个结点的指针，若链表有头节点，则是指向头节点的指针是必需的具有标识作⽤头节点：头结点是为了操作的统⼀和⽅便⽽设⽴的，放在第⼀个元素的结点之前不是必需的，为了⽅便操作对于插⼊和删除第⼀个结点，和其他结点操作统⼀10、简述KMP算法？KMP算法是在简单模式匹配的基础上对串的模式匹配进⾏优化。主要的思路是每趟⽐较过程中让字串先滑动到⼀个合适的位置。当发⽣不匹配时，不同于简单模式匹配的右移⼀位，⽽是移动到合适的位置。这⾥所移动的位置依靠与next数组，求next数组的⽅法是⽐较前后缀相同元素。11、栈和队列的区别？栈：先进后出允许在表尾进⾏插⼊和删除插⼊和删除都在表尾进⾏top==-1为空top++进栈top--出栈队列：先进先出允许在⼀端进⾏插⼊⼀端进⾏删除在队尾插⼊在队头删除front==rear为空rear=(rear+1)%maxsize进队front=(front+1)%maxsize出队12、栈和队列的相同之处和不同之处？相同点：（1）栈和队列都是线性结构（2）栈和队列在插⼊时都是在表尾进⾏（3）栈和队列都可以⽤顺序存储结构和链式存储结构（4）栈和队列插⼊和删除操作的时间复杂度和空间复杂度是⼀样的不同点：（1）删除元素位置不同，栈在表尾，队在表头（2）⽤链表存储时可以实现多栈空间共享，队列不⾏13、两个栈实现队列，两个队列实现栈？两个栈实现⼀个队列：先将数据存在到第⼀个栈⾥，在将第⼀个栈⾥的元素全部出栈到第⼆个栈，第⼆个栈出栈，即可达到先进先出。两个队列实现⼀个栈：先将数据存到第⼀个队列⾥⾯，然后数据出队⼀直出队到第⼆个队列⾥⾯，直到第⼀个队列⾥⾯剩余⼀个数据，这个时候出队，即可达到先进后出的特性。14、树和⼆叉树的相关概念？（1）⼆叉树和度为2的树的区别？⼆叉树的特点：<1>每个节点最多有两颗⼦树，节点的度最⼤为2<2>左⼦树和右⼦树是有顺序的，次序不能颠倒<3>即使某结点只有⼀个⼦树，也要区分左右⼦树<4>⼆叉树可以是空树、只有⼀个根节点、根节点只有左⼦树、根节点只有右⼦数、根节点左右⼦树都有度为2的树：树的结点的最⼤的度为2（2）⼆叉树的遍历：先序、中序、后序、层次遍历。（3）树的遍历：先根遍历（先访问根节点，从左到右先根遍历的每个⼦树）、后根遍历（先依次后根遍历每个根⼦树，然后再访问根节点）15、⼆叉平衡树？在⼆叉排序树的基础上，只要保证每个节点左⼦树和右⼦数的⾼度差⼩于等于1就可以了。适合⽤于插⼊删除⽐较少，但是查找⽐较多的情况。16、⼆叉搜索树？是⽐根节点⼤的放在右⼦数，⽐根节点⼩的放在左⼦树，对⼆叉排序树进⾏中序遍历，可以得到⼀个递增的有序序列。17、红⿊树？主要性质：（1）节点是红⾊或者⿊⾊，没有其他的颜⾊（2）根节点是⿊⾊，不能为红⾊（3）每个叶节点是⿊⾊，这⾥的叶⼦节点，节点是指空的叶⼦节点（4）不存在两个连续的红⾊节点，即⽗节点和⼦节点不能是连续的红⾊（5）从任⼀节点到其每个叶节点的所有路径都包含相同数⽬的⿊⾊节点优点：平均查找，添加输出效果都还不错红⿊树的应⽤⽐较⼴泛，主要是⽤来存储有序的数据，它的时间复杂度是O(logn)，效率⾮常之⾼。例如Java集合中的TreeSet和TreeMap，C++STL中set、map，需要使⽤动态规则的防⽕墙系统，使⽤红⿊树⽽不是散列表被实践证明具有更好的伸缩性。Linux内核在管理vm_area_struct（虚拟内存）时就是采⽤了红⿊树来维护内存块的。18、图的相关概念？图结构中节点之间的关系是任意的，图中的任意两个节点都可能有关系。图分为有向图和⽆向图有向图的基本算法：拓扑排序、最短路（Dijkstra算法和Floyd算法）⽆向图的基本算法：最⼩⽣成树（Prime算法，Kruska算法）、DFS、BFS19、邻接矩阵与邻接表的区别？图的存储结构：邻接表：（链式存储结构）由单链表的表头形成的顶点表，和单链表其余节点形成的边表两部分组成；⼀般顶点表存放顶点信息和指向第⼀个边节点的指针。适合⽤于稀疏图。邻接矩阵：（顺序存储结构）⽤⼀个⼀维数组存储图中顶点的信息，⽤⼀个⼆维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的⼆维数组称为邻接矩阵。适合⽤于稠密图。有向图的⼗字链表法⽆向图的多重链表法20、深度优先遍历与⼴度优先遍历？深度优先遍历类似于⼆叉树的先序遍历步骤：<1>访问起始点v<2>若v的第⼀个邻接点没有被访问过，则深度遍历该邻接点<3>若v的第⼀个邻接点已经被访问，则访问其第⼆个连接点，进⾏深度遍历；重复以上步骤，直到所有节点都被访问为⽌⼴度优先遍历类似于层次遍历步骤：<1>访问起始点v<2>依次遍历v的所有未访问过得邻接点<3>再次访问下⼀层中未被访问过的邻接点；重复以上步骤，直到所有节点都被访问过为⽌21、最⼩⽣成树的算法（普利姆算法，克鲁斯卡尔算法）？普利姆算法（Prime）算法执⾏过程：（1）将v0到其他顶点的所有边当作侯选边（2）重复以下过程，直到所有的顶点被并⼊树中：（2.1）从侯选边中挑选出最⼩的边输出，并将与该边的另⼀端顶点并⼊树种（2.2）考查所有剩余的顶点，选取与这棵树相邻的边的最短边时间复杂度为O(n^2)，适合⽤于稠密图克鲁斯卡尔算法（Kruska）思路：每次找出候选边中权值最⼩的边，并⼊⽣成树中算法执⾏过程：（1）将图中边按照权值从⼩⼤排序（2）然后从最⼩边开始扫描（3）并检测当前边是否为候选边，即是否该边并⼊会构成回路适⽤于稠密图22、什么时候最⼩⽣成树唯⼀？所有权值都不相同，或者有相同的边，但是在构造最⼩⽣成树的过程中权值相等的边都被并⼊到最⼩⽣成树中的图，其最⼩⽣成树是唯⼀的。23、Dijkstra算法与Floyd算法的区别？Dijkstra算法（迪杰斯特拉）⽤于计算图中某⼀结点到其余顶点的最短路径思路：（1）集合S存放图中⼀找到最短路径的顶点（2）集合U存放途中剩余顶点算法执⾏过程：（1）初始时，S只包含原点，即：S={v}，v的距离为0。U包含除v以外的其他顶点。即：U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。（2）从U中选取⼀个距离v最⼩的顶点k，把k，加⼊S中（该选定的距离就是v⼤k的最短路径长度）。（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）⽐原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。（4）重复步骤（2）和（3）直到所有顶点都包含在S中。Floyd算法（弗洛伊德）解决任意两点间的最短路径的⼀种算法，可以正确处理有向图或负权的最短路径问题，同时也被⽤于计算有向图的传递闭包。时间复杂度O(n^3)，空间复杂度O(n^2)算法描述：（1）从任意⼀条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权值为⽆穷⼤。（2）对于每⼀对顶点u和v，看看是否存在⼀个顶点w，使得从u到w再到v⽐已知的路径更短。如果是更新它。24、拓扑排序的概念以及实现？AOV⽹：⼀种以顶点表⽰活动，以边表⽰活动的先后次序且没有回路的有向图。反映出整个⼯程中各个活动之间的先后关系的有向图。拓扑算法的核⼼过程：（1）从有向图中选择⼀个没有前驱（⼊度为0）的顶点输出（2）删除1中的顶点，并且删除从该顶点发出的全部边（3）⼀直重复若图中没有环的时候，还可采⽤深度优先搜索遍历的⽅法进⾏拓扑排序。25、关键路径的相关概念？AOE⽹：在带权有向图中，若以顶点表⽰事件，有向边表⽰活动，边上的权值表⽰该活动持续的时间AOV和AOE的区别：相同点：都是⽆环图不同点：AOV活动在顶点，边⽆权值，代表活动之前的先后关系AOE或者在边，边有权值，代表活动持续的时间关键路径的核⼼算法：最⼤路径长度的路径称为关键路径关键活动：关键路径上的活动为关键活动，关键活动的最早开始时间等于最晚开始时间。由于AOE⽹中的某些活动是可以同时发⽣的，所以完成整个⼯程的时间应该是从起始点到终点的最⼤路径长度，关键路径长度即为⼯程的最短完成时间。26、各种排序的概括与总结？（1）排序算法：冒泡排序、选择排序、插⼊排序、希尔排序、归并排序、快速排序、基数排序、堆排序（2）稳定的排序：冒泡排序、插⼊排序、归并排序、基数排序（3）经过⼀趟排序，能够保证⼀个关键字到达最终位置：冒泡排序、快速排序、简单选择排序、堆排序（4）关键字⽐较次数和原始序列⽆关：简单选择排序、折半排序（5）排序趟数和原始序列⽆关：冒泡排序、快速排序（6）将顺序存储更换为链式存储，时间效率低：希尔排序、堆排序（7）排序最优和最差相同的排序算法：简单选择、归并排序、堆排序（8）排序算法中哪些最坏和平均的时间复杂度是⼀样的：直接插⼊、折半插⼊、冒泡排序、简单选择排序、堆排序、归并排序27、各种查找⽅法？查找⽅法分为静态查找表和动态查找表静态查找表：顺序查找、折半查找、⽅块查找顺序查找：结构简单，顺序结构和链式结构都可以，查找效率低折半查找：要求查找表为顺序存储结构，并且有序分块查找：先把查找表分为若⼲⼦表，要求每个⼦表的元素都要⽐他后⾯的⼦表的元素⼩，从⽽保存块间是有序的，把各⼦表中最⼤关键词构成⼀张索引表，表中还包含各⼦表的起始地址。特点：块间有序，块内⽆序，查找时，块间索引查找，块内进⾏顺序查找。动态查找表：⼆叉排序树、平衡⼆叉树⼆叉排序树：是⽐根节点⼤的放在右⼦数，⽐根节点⼩的放在左⼦树，对⼆叉排序树进⾏中序遍历，可以得到⼀个递增的有序序列。平衡⼆叉树：他的左右⼦树⾼度差不能⼤于1，且左右⼦树也都是平衡⼆叉树28、快速排序的优化？优化：（1）当整个序列有序时退出算法（2）当序列长度很⼩时（根据经验是⼤概⼩于8），应该使⽤常数更⼩的算法，⽐如插⼊排序等。（3）随机选取分割位置（4）当分割位置不理想时，考虑是否重新选取分割位置（5）分割成两个序列时，只对其中⼀个递归进去，另⼀个序列仍可以在这⼀函数内继续划分，可以显著减⼩栈的⼤⼩（尾递归）（6）将单向扫描改成双向扫描，可以减少划分过程中的交换次数优化1：当待排序序列的长度分割到⼀定⼤⼩后，使⽤插⼊排序原因：对于很⼩和部分有序的数组，快排不如插排好。当待排序序列的长度分割到⼀定⼤⼩后，继续分割的效率⽐插⼊排序要差，此时可以使⽤插排⽽不是快排。优化2：在⼀次分割结束后，可以把与Key相等的元素聚在⼀起，继续下次分割时，不⽤再对与Key相等元素分割。优化3：优化递归操作（快排函数再函数尾部有两次递归操作，我们可以对其使⽤递归优化）优点：如果待排序的序列划分极端不平衡，递归的深度将趋近于n，⽽栈的⼤⼩是很有限的，每次递归调⽤都会耗费⼀定的栈空间，函数的参数越多，每次递归耗费的空间也越多。优化后，可以缩减堆栈深度，由原来的O(n)缩减为O(logn)，将会提⾼性能。29、B树和B+树的区别，以⼀个m阶数为例？关键词的数量不同：B+树中具有n个关键字的结点只包含有n棵⼦树。每个结点关键字个数的范围是|m/2|<=n<=m树B中具有n个关键字的结点含有n+1棵⼦树。每个结点关键字个数的范围是|m/2|-1<=n<=m-1存储的位置不⽤：B+树中数据都存储再叶⼦结点上，也就是其所有⼦结点的数据组合起来就是完整的数据，但是B树的数据存储再每⼀个结点中。分⽀结点的结构不同：B+树的分⽀结点仅仅存储着关键字信息和⼉⼦的指针，也就是说内部结点仅仅包含着索引信息。查询不同：树B再找到具体的数值以后，则结束，⽽B+树则需要通过索引找到叶⼦结点中的数据才结束30、哈希表（概念、构造⽅法、冲突解决）？概念：根据给定的关键字来计算出关键字的表内地址建⽴⽅法：直接定址法：H(Key)=a*Key+b特点：计算简单，且不会产⽣冲突，若关键字发布不连续，空位较多，则会造成存储空间的浪费。数字分析法：当关键字的位数⼤于地址的位数，对关键字的各位分布进⾏分析，选出发布均匀的任意⼏位作为散列的地址，适⽤于所有关键字都已知的情况。平⽅取中法：取关键字平⽅后的中间⼏位作为Hash地址（适⽤于关键字的每位取值都不够均匀或⼩于散列地址所需的位数）除留余数法：取关键字对p取余的值作为散列地址，其中p<m，即H(Key)=Key%p(p<m)。冲突解决⽅法：开放定址法：（1）线性探查法：依次探查下⼀个地址，直到有空位置出现为⽌（任意产⽣堆积）（2）平⽅探查法：可以减少堆积问题，但是不能探查到hash上的所有单元，可探查到⼀半单元。链地址法：把所有的同义词⽤单链表连接起来公共溢出区法：为所有冲突的关键字记录⼀个公共溢出区来存放。再查找时，堆给定关键字通过散列函数计算出散列地址后，先于基本表的相应位置进⾏对⽐，如果相等，则查找成功；如果不相等，则到溢出表进⾏顺序查找。如果相对于基本表⽽⾔，再有冲