数据结构简答题汇总

数据结构简答题1、简述逻辑结构与存储结构的联系和区别。答：联系：数据的逻辑结构与存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构在数据结构中，逻辑结构与计算机无关，存储结构是数据元素之间的逻辑关系在计算机中的表示。存储结构不仅将逻辑结构中所有数据元素存储到计算机内存中，而且还要在内存中存储各数据元素间的逻辑关系。通常情况下，一种逻辑结构可以有多种存储结构，例如，线性结构可以采用顺序存储结构或链式存储结构表示。2、简述顺序表和链表存储方式的特点。答：顺序表的优点是可以随机存取元素，存储密度高；缺点是不便于插入和删除元素（需要移动大量的元素）。链表的优点是便于节点的插入和删除只需要修改指针域，不需要移动节点；缺点是不能进行随机访问，只能顺序访问，另外，每个节点上增加指针域，导致存储密度较低。3、头指针和头结点的区别答：它是一个链表存在的标志，是必须存在必不可少的。头指针是指在第一个结点之前的指针，头结点是第一个结点之前的结点，它是为了方面在第一个结点之前进行元素的插入和删除操作，它不是必须的，并且数据域也可以不存放信息。它是一个链表存在的标志，是必须存在必不可少的。4、栈和队列的区别答：栈是只能在一端进行插入和删除的线性表，插入和删除都在栈顶进行，它的特点是“先进后出”。常用于括号的匹配问题，递归问题，但是递归问题要注意堆栈的溢出现象队列是在一端插入在另一端删除的线性表，插入的那端是队尾，删除的那端是队首，特点是“先进先出”，在层次遍历和BFS算法、迪杰斯特拉算法中使用到5、解释带头结点的单链表和不带头结点的单链表的区别。答：带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点。在操作上，带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点，算法步骤都相同。不带头结点的单链表，其算法步骤要分别考虑6、贪心算法、动态规划和分治算法。答：贪心算法是指从上到下，每次都求解局部最优解的算法，特点是每次求解最优解，但是最终的结果不一定是最优，经典例子是背包问题。动态规划是将一个大问题划分成若干个子问题，问题之间存在重叠，从上到下，求解整体最优解，每一次的求解会对下一次的问题造成影响，最终的最优解不一定包含每次的最优解，但是一定有部分最优解。经典例子是求最长子串。分治算法是将一个大问题划分成若干个和大问题相似的子问题，再对子问题进行递归求解，最终合并得到最后的结果。特点是大问题的划分与子问题相似，并且每个问题之间是相互独立的。经典例子是二路归并排序、快速排序插入或删除的位置是第一个结点还是其他结点。因为两种情况的算法步骤不同。7、共享栈答：利用栈底位置不变的特性，让两个顺序栈共享同一个一维数组空间，将两个栈的栈底分别设在共享空间的两端，两个栈顶向共享空间延伸。，fw/8、如何区分循环队列是队空还是队满？答：有两种区分方式：牺牲一个单元来区分队空和队满队空：队首指针==队尾指针；队满：(队尾指针+1)%maxsize==队首指针在结构体中增设表示元素数据的内存单元队空：元素的个数为0队满：元素的个数为Maxsize9、栈和队列的异同点?答：栈与队列的相同点：都是线性结构。插入操作都是限定在表尾进行。都可以通过顺序结构和链式结构实现。插入与删除的时间复杂度都是0(1)，在空间复杂度两者相同。栈与队列的不同点：删除数据元素的位置不同，栈的删除操作在表尾进行，队列的删除操作在表头进行。应用场景不同，常见栈的应用场景包括括号问题的求解，表达式的转换和求值，函数调用和递归实现，深度优先搜索遍历等；常见的队列的应用场景包括计算机系统中各种资源的管理，消息缓冲器的管理和广度优先搜索遍历等。顺序栈能够实现多栈空间共享，而顺序队列不能。10、利用两个栈s1,s2模拟一个队列时，如何用栈的运算实现队列的插入，删除以及判队空运算。请简述这些运算的算法思想。答：栈的特点是后进先出，队列的特点是先进先出。所以，当用两个栈和s2模拟一个队列时，si作为输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈1退栈并逐个压入栈s2中，si中最先入栈的元素在s2中处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。只有栈s2为空且si也为空时，才算是队列空。11、栈在括号匹配中的算法思想答：如果是左括号，则入栈如果是右括号，则判断当前栈是否为空，如果为空，则不匹配，不为空，则看是否与栈顶的左括号匹配，如果匹配，则栈顶元素出栈最终所有的元素都进栈和出栈完毕，检查栈是否为空，如果不为空，则说明还有多余的左括号没有匹配，因此括号匹配失败，如果为空，则括号匹配成功。12、栈在后缀表达式求值的算法思想：答：依次扫描表达式的每一项如果是操作数，则进栈如果是运算符，则从栈中退出两个元素进行出栈，且将得到的结果入栈表达式的所有项都扫描完后，后栈顶存放的元素就是最终的结果。13、栈在递归中是怎样运用的？答：若在一个函数、一个过程或者一个数据结构的定义中直接或者间接的调用了它自身，则这个函数、这个过程、这个数据结构称为是递定义的，简称为递归。递归问题只需要少数的代码就能够描述出解题过程中所需要的多次重复计算，大大减少了程序的代码量，递归会让代码的结构简单、清晰，但是大量的递归调用会建立函数的副本，耗费大量的时间和内存。递归所用到的是系统管理栈，但是通常情况下，每次递归都要保留现场间复杂度为O(n)，效率不高，当递归次数过深的时候，容易出现堆栈溢出的现象。14、一棵度为2的有序树与一棵二叉树有何区别答：一棵度为2的有序树与一棵二叉树的区别在于：有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序。而二叉树无论其孩子数是否为2,均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。15、名词解释：满二叉树，完全二叉树，二叉排序树，平衡二叉树，线索二叉树答：满二叉树：高度为H,结点数为2H-1的二叉树为满二叉树。完全二叉树：除最后一层外，其余各层的节点数量达到最大值，并且最后一层只能在右侧缺少节点。二叉排序树：左子树上所有的关键字均小于根结点，右子树上所有关键字均大于根结点。左子树和右子树又分别是一棵二叉排序树。平衡二叉树：树中每一个结点的左子树，右子树高度之差的绝对值小于等于1线索二叉树：将二叉链表中的空指针改成指向前驱节点或后继的线索。线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解决了二叉链表找左、右孩子困难的问题。16、树的存储结构有哪些？答：双亲表示法：采用一组连续的存储空间存储每个结点，同时在每个结点后面增设一个伪指针指向其双亲节点。孩子表示法：将每个结点的孩子结点用单链表链接起来形成一个线性结构。孩子兄弟表示法：以二叉链表作为树的存储结构，其左指针指向第一个孩子结点，右指针指向其④相邻的兄弟结点。可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等，但缺点是从当前结点查找其双亲结点比较麻烦。17、一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上各层的结点数目是多少？⑴第i层上的结点数目是mi-1。18、哈夫曼树答：权：树中的结点往往被赋予一个有意义的数值称为该结点的权。结点的带权路径长度：从树的根到任意节点的路径长度与该结点的权值之积称为该结点的带权路径长度。树的带权路径长度：树中所有叶结点的带权路径之和为该树的带权路径长度。哈夫曼树：带权路径长度最小的树为哈夫曼树19、构造哈夫曼树的算法答：将树中的每个结点都看成一个独立的二叉树构成森林F,从F中选择根结点最小的两棵树构成一棵新的二叉树，二叉树的根结点为两个结点之和，并将这两个树从中删除，将新构成的树并入F中，重复上述过程，直到F中只剩下一个树。特点：哈夫曼树中不存在度为1的结点，权值越小的结点距离根结点的路径长度越大。20、串的存储结构答：定长顺序存储表示：采用一组连续的存储空间存储串的字符序列。堆分配存储表示：依然采用一组连续的存储空间存储串的字符序列，但是存储空间是在运行过程中动态分配的。21、串的模式匹配答：串的模式匹配指子串在主串中的位置。暴力匹配算法：从主串的第一个字符开始，与子串的第一个字符比较一但出现不匹配的字符，则主串往后移动一个位置，子串移动子的第一个位置并与主串对齐。KMP算法：暴力匹配的弊端就是，没有充分利用已经匹配了的串的信息，好的解决方法应该是在模式串中找到最长的子串，并且记录到next数组中KMP算法的步骤⑴主串S和模式串T进行比较，并设起始的下标为i和j⑵如果S[i]==T[i]，则继续比较，进行i++,j++⑶当S[i]!=T[j]时，将j=next[j]；将模式串右移，直到与主串对齐；如果==-1,则主串往后移动一个单位,i++,j++,j又回到模式串的第一个位置22、如何对无环有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线以上？答：23、（1）如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？（2）如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？（3）如果G3是一个具有n个顶点的弱连通有向图，那么G3最多有多少条边？G3最少有多少条边？答：（1）G3最多n（n-1）条边，最少n-1条边（tips：弱连通有向图指把有向图看作无向图时，仍是连通的）

⑵G2最多n（n-1）条边，最少n条边（3）G1最多n（n-1）/2条边，最少n-1条边阵？(2)答：(1)2阵？(2)答：(1)表示有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩对于一个有向图，不用拓扑排序，如何判断图中是否存在环？106,不一定是稀疏矩阵（稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律）（2）使用深度优先遍历，按退出dfs过程的先后顺序记录下的顶点是逆向拓扑有序序列。若在执行dfs（v）未退出前，出现顶点u到v的回边，则说明存在包含顶点v和顶点u的环。25、试评述这三种表示法的优、缺点：（1）邻接矩阵表示法；（2）邻接表表示法；（3）其它表示法。答：（1）邻接矩阵表示法，有n个顶点的图占用n2个元素的存储单元，与边的个数无关，当边数较少时，存储效率较低。这种结构下，对查找结点的度、第一邻接点和下一邻接点、两结点间是否有边的操作有利，对插入和删除顶点的操作不利。A.（2）邻接表表示法是顶点的向量结构与顶点的邻接点的链式存储结构相结合的结构，顶点的向量结构含有n（nN0）个顶点和指向各顶点第一邻接点的指针，其顶点的邻接点的链式存储结构是根据顶点的邻接点的实际设计的。这种结构适合查找顶点及邻接点的信息，查顶点的度，增加或删除顶点和边（弧）也很方便，但因指针多占用了存储空间，另外，某两顶点间是否有边（弧）也不如邻接矩阵那么清楚。对有向图的邻接表，查顶点出度容易，而查顶点入度却困难，要遍历整个邻接表。要想查入度象查出度那样容易，就要建立逆邻接表。无向图邻接表中边结点是边数的二倍也增加了存储量。（3）十字链表是有向图的另一种存储结构，将邻接表和逆邻接表结合到一起，弧结点也增加了信息（至少弧尾，弧头顶点在向量中的下标及从弧尾顶点发出及再入到弧头顶点的下一条弧的四个信息）。查询顶点的出度、入度、邻接点等信息非常方便。邻接多重表是无向图的另一种存储结构，边结点至少包括5个域：连接边的两个顶点在顶点向量中的下标，指向与该边相连接的两顶点的下一条边的指针，以及该边的标记信息（如该边是否被访问）。边结点的个数与边的个数相同，这是邻接多重表比邻接表优越之处。26、请简述深度优先遍历、广度优先遍历的基本思想。答：深度优先遍历：首先访问图中起始顶点V，然后由v出发，访问与v邻接且未被访问的顶点再访问与v相邻且未被访问的顶点W1...重复上述过程。当不能再继续向下访问时，依次退回到最近被的问的顶点，若它仍有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被切问过为止。所以深度优先遍历的策略就是尽可能“深”的搜索一个图。广度优先遍历：广度优先遍历类似于二叉树的层次遍历。首先访问起始顶点V,然后从v出发，依次访问v的各个未访问过的邻接顶点w1,w2,...然后依次访问w1,w2...的所有未被防问过的邻接顶点，再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止，此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。27、Dijkstra算法和BFS求的最短路径有什么区别吗？答：Dijkstra算法求的是单源最短路径，当图为带权图（权值非负）时，把从一个顶点a到一个顶点b的一条路径（可能不止一条）所经过边的权值之和，定义为该路径的带权路径长度，而最短路径就是带权路径长度最短的那条路径。BFS求最短路径的图的边是不带权值或权值相等的，与其说它求的是路径，不如说它求的是次数。28、请比较AOE网与AOV网。答：AOV网：其顶点用来表示活动。AOV网的边无权值，仅表示顶点的前后关系。AOV网是用来分析工程至少需要花多少时间完成，或是为了缩短时间需要加快哪些活动等问题。AOE网：顶点表示事件，边表示活动，边上的权值用来表示活动持续的时间OE网是用来表示活动之间的制约关系。29、归并排序是否稳定？为什么？答：归并排序是稳定的排序算法。归并排序的稳定性分析：归并排序是把序列递归bai地分成短序列，递归出口是短序列只有1个元素或者2个序列，然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等，没有外部干扰，将不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定性是没有受到破坏的，合并过程中如果两个当前元素相等时，把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。胴并排序也是稳定的排序算法。30、在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？答：这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。对4,3,2,1进行冒泡排序就可否定本题结论。

31、简述直接插入排序，简单选择排序的基本思想以及在时间复杂度和排序稳定性上的差别。答：直接插入排序的基本思想是基于插入，开始假定第一个元素有序，然后从第二个元素开始，依次插入到前面有序的元素中。即将元素[i](2<=i<=n)插入到有序元素R[1..i-1]中，使元素的有序序列从R[1..i-1]变为R[1..i]，最终使整体有序。共进行n-1趟插入。最坏时间复杂度是)(n2),平均时间复杂度是O(n2)，空间复杂度是0(1)，是稳定排序。简单选择排序的基本思想是基于选择，开始有序元素长度为零，第(1<=i〈n)趟简单选择排序是，从无序元素R[i..n]的n-i+1记录中选出关键字最小的元素，和第个元素交换，使有序元素序列逐步扩大，最后使整体有序。共进行n-1趟选择。最坏时间复杂度是0(n2)，平均时间复杂度是0(n2)，空间复杂度是0(1)，是不稳定排序。32、关于堆排序的知识点答：堆：是一种特殊的完全二叉树，叶子结点的值大于或者小于根结点的值(tips:完全二叉树是指第n-1层，每一层的结点数是2(n-1)，最后一层的结点可以不放满，但是必须是从左至右放的)堆排序：最好、最坏、平均时间复杂度是0(nlogn)思想：(以大根堆为例)将待排序的构造成一个大根堆，此时最大的元素就是根结点的元素，这时候，将这个元素与末尾的元素进行交换，然后再将剩下>的个元素构造成一个大根堆，就会形成一个有序区。堆排序步骤：构造初始堆建立一个完全二叉树■从最后一个非叶子结点开始调整，一旦比根结点大，则与根结点进行交换，最终最大的元素位于根结点的位置上将堆顶元素与末尾元素进行交换，末尾的元素值最大重新调整结构，使其满足堆定义，然后继续交换堆顶元素当前末尾元素，反复执行+调整步骤，直到整个序列有序。33、若对有n个元素的有序顺序表和无序顺序表进行顺序查找，试就下列三种情况分别讨论(1)(2)(1)(2)(3)答：(1)查找，查找失败查找成功，且表中只有一个关键字等于给定值k的元素查找成功，且表中有若干关键字等于给定值k的元素，要求--次查找能找出所有元素平均查找长度不同。因为有序顺序表查找到其关键字值比要查找值大的元素时就停止并报告失败信息，不必查找到表尾;而无序顺序表必须查找到表尾才能确定查找失败。平均查找长度相同。两者查找到表中元素的关键字值等于给定值时就停止查找。

（3）平均查找长度不同。有序顺序表中关键字相等的元素相继排列在一起，只要查找到第一个就可以连续查找到其他关键字相同的元素。而无序顺序表必须查找全部表中的元素才能找出相同关键字的元素，因此所需的时间不同。34、试比较B树与B+树答：相同点：（1）根结点所含关键字范围：1<=k<=m-1（2