2022年数据结构面试题精选 .pdf
《2022年数据结构面试题精选 .pdf》由会员分享,可在线阅读,更多相关《2022年数据结构面试题精选 .pdf(15页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、特别说明 : 本文中二叉树结构定义为:struct Node Node* left; Node* right; int data; ; 定义:空二叉树的高度为-1,只有根节点的二叉树高度为0,根节点在0 层,深度为0。求二叉树中相距最远的两个节点之间的距离两个节点的距离为两个节点间最短路径的长度。求两节点的最远距离,实际就是求二叉树的直径。假设相距最远的两个节点分别为A、B,它们的最近共同父节点(允许一个节点是其自身的父节点)为C,则A到 B 的距离 = A 到 C的距离 + B到 C的距离。节点 A、B 分别在 C 的左右子树下(假设节点 C的左右两子树均包括节点C),不妨假设A在 C的左子
2、树上,由假设“A到 B的距离最大”,先固定B 点不动(即 B到 C的距离不变),根据上面的公式,可得 A 到 C 的距离最大,即点A是 C左子树下距离C最远的点,即:A到 C的距离 = C 的左子树的高度。同理,B到 C的距离 = C 的右子树的高度。因此,本问题可以转化为:“二叉树每个节点的左右子树高度和的最大值”。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 15 页 - - - - - - - - - 判断二叉树是否平衡二叉树根据平衡二叉树的定义:每个结点的左右子
3、树的高度差小等于1,只须在计算二叉树高度时,同时判断左右子树的高度差即可。二叉树的广度遍历(某层)若需要对同一层的节点数据进行一些特殊操作(比如:打印完一层后换行、只打印某一层),可以记录某一层的最后一个节点,当遍历完该节点时(此时,队列的中的最后一个元素恰好就是下一层的最后一个节点),再进行这些特殊操作。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 15 页 - - - - - - - - - 指定二叉树,给定两节点求其最近共同父节点遍历二叉树时,只有先访问给定两节点
4、A、B 后,才可能确定其最近共同父节点C,因而采用后序遍历。可以统计任一节点的左右子树“是否包含A、B中的某一个”(也可以直接统计“包含了几个A、B”)。当后序遍历访问到某个节点D时,可得到三条信息:节点D是否是 A、B两节点之一、其左子树是否包含A、B两节点之一、其右子树是否包含A、B 两节点之一。当三条信息中有两个为真时,就可以确定节点D的父节点(或节点D,如果允许一个节点是自身的父节点的话)就是节点 A、B的最近共同父节点。另外,找到最近共同父节点C后应停止遍历其它节点。上面的代码中需要特别注意的是:判断所访问时节点是否是两节点A、B时要写成const intmid = (root= v
5、a) +(root= vb);而不是:constint mid = (root = va) | (root = vb);这样当 va 等于 vb 时,可以得到正确结果。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 15 页 - - - - - - - - - 二叉树的高度求二叉树中叶子节点的个数交换二叉树的左右儿子名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第
6、 4 页,共 15 页 - - - - - - - - - 从根节点开始找到所有路径,使得路径上的节点值和为某一数值(路径不一定以叶子节点结束)这道题要找到所有的路径,显然是用深度优先搜索(DFS )啦。但是我们发现DFS 所用的栈和输出路径所用的栈应该不是一个栈,栈中的数据是相反的。看看代码: 注意使用的两个栈。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 15 页 - - - - - - - - - 二叉树“弓”字形遍历题目描述:对二叉树进行“ 弓” 字形遍历,即第
7、一层从左往右遍历,第二层从右往左遍历,第三层从左往右遍历 . 思路:传统的广度优先遍历, 只需一个队列即可, 但只能实现每层从左往右遍历。这里可以设两个栈,分别存放相邻两层的节点,先将某层节点存入一个栈,对这个栈的每个节点进行访问和出栈操作,在出栈的同时把它的孩子节点存入另一个栈,当这层的每个节点都操作完毕后,同时也实现了下一层节点在另一个栈的入栈操作。要注意的是,相邻两层的节点入栈的顺序是相反的,这样才能实现“ 弓” 字形遍历。在这边可以控制一个flag 状态量,当栈中为空时,判断flag 是否等于0,如果等于0 则从左到右,否则就是从右到左平衡二叉树( AVL 树)1)是一棵二叉查找树(B
8、ST),任意一棵子树,其左右子树的高度差不大于1 2) 四种变形LL 型RR 型名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页,共 15 页 - - - - - - - - - LR 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 15 页 - - - - - - - - - RL 判断二叉树是不是完全二叉树名师资料总结 - - -精品资料欢迎下载 -
9、- - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页,共 15 页 - - - - - - - - - 红黑树一般的,红黑树,满足以下性质,即只有满足以下全部性质的树,我们才称之为红黑树:1)每个结点要么是红的,要么是黑的。2)根结点是黑的。3)每个叶结点,即空结点(NIL )是黑的。4)如果一个结点是红的,那么它的俩个儿子都是黑的。5)对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。这些约束强制了红黑树的关键性质:最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点。 因为根据属性5 所有最长的
10、路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。因为每一个红黑树也是一个特化的二叉查找树,因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而,在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的属性需要少量 (O(log n)的颜色变更 (实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂,但操作时间仍可以保持为O(log n) 次。首先用与二叉搜索树一样的方法将一个结点插入到红黑树中,并且颜色为红色。(这个新结点的子结点将是叶结点, 根据定义, 这些叶结点是黑色的。 )此时,我们将或者破坏了性质2(根结点为
11、黑色)或者破坏了性质4(不能有两个相邻的红色结点)。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页,共 15 页 - - - - - - - - - 求链表倒数第k 个结点设置两个指针 p1,p2 ,首先 p1 和 p2 都指向 head ,然后 p2 向前走 k 步,这样 p1 和 p2 之间就间隔 k个节点,最后 p1 和 p2 同时向前移动,直至p2 走到链表末尾。判断两个链表是否相交题目描述 :给出两个单向链表的头指针(如下图所示),比如 h1、h2,判断这两个链表是
12、否相交。这里为了简化问题,我们假设两个链表均不带环。分析:这是来自编程之美上的微软亚院的一道面试题目。请跟着我的思路步步深入(部分文字引自编程之美):1. 直接循环判断第一个链表的每个节点是否在第二个链表中。但,这种方法的时间复杂度为O(Length(h1) * Length(h2)。显然,我们得找到一种更为有效的方法,至少不能是 O(N2)的复杂度。2. 针对第一个链表直接构造hash 表,然后查询hash 表,判断第二个链表的每个结点是否在hash 表出现,如果所有的第二个链表的结点都能在hash 表中找到,即说明第二个链表与第一个链表有相同的结点。时间复杂度为为线性:O(Length(h
13、1) + Length(h2),同时为了存储第一个链表的所有节点,空间复杂度为O(Length(h1) 。是否还有更好的方法呢,既能够以线性时间复杂度解决问题,又能减少存储空间?3. 进一步考虑 “ 如果两个没有环的链表相交于某一节点,那么在这个节点之后的所有节点都是两个链表共有的 ” 这个特点,我们可以知道,如果它们相交,则最后一个节点一定是共有的。而我们很容易能得到链表的最后一个节点,所以这成了我们简化解法的一个主要突破口。那么,我们只要判断俩个链表的尾指针是否相等。相等,则链表相交;否则,链表不相交。所以,先遍历第一个链表,记住最后一个节点。然后遍历第二个链表,到最后一个节点时和第一个链
14、表的最后一个节点做比较,如果相同,则相交,否则,不相交。这样我们就得到了一个时间复杂度,它为O(Length(h1) + Length(h2),而且只用了一个额外的指针来存储最后一个节点。这个方法时间复杂度为线性O(N),空间复杂度为O(1),显然比解法三更胜一筹。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页,共 15 页 - - - - - - - - - 4. 上面的问题都是针对链表无环的,那么如果现在,链表是有环的呢?还能找到最后一个结点进行判断么 ?上面的方法还同
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年数据结构面试题精选 2022 数据结构 试题 精选
限制150内