logo资料库

数据结构经典面试题80题.docx

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.04M 资料格式：docx 举报 版权申诉
第1页 / 共45页
第2页 / 共45页
第3页 / 共45页
第4页 / 共45页
第5页 / 共45页
第6页 / 共45页
第7页 / 共45页
第8页 / 共45页
资料共45页，剩余部分请下载后查看
    1.把二元查找树转变成排序的双向链表 题目： 输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点，只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16。 首先我们定义的二元查找树 节点的数据结构如下： struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; 2.设计包含 min 函数的栈。 定义栈的数据结构，要求添加一个 min 函数，能够得到栈的最小元素。
    要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。 3.求子数组的最大和 题目： 输入一个整形数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为 O(n)。 例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为 3, 10, -4, 7, 2， 因此输出为该子数组的和 18。 4.在二元树中找出和为某一值的所有路径 题目：输入一个整数和一棵二元树。 从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。 打印出和与输入整数相等的所有路径。 例如 输入整数 22 和如下二元树 10 / \ 5 12 / \ 4 7
    则打印出两条路径：10, 12 和 10, 5, 7。 二元树节点的数据结构定义为： struct BinaryTreeNode // a node in the binary tree { int m_nValue; // value of node BinaryTreeNode *m_pLeft; // left child of node BinaryTreeNode *m_pRight; // right child of node }; 5.查找最小的 k 个元素 题目：输入 n 个整数，输出其中最小的 k 个。 例如输入 1，2，3，4，5，6，7 和 8 这 8 个数字，则最小的 4 个数字为 1，2，3 和 4。 第 6 题 腾讯面试题： 给你 10 分钟时间，根据上排给出十个数，在其下排填出对应的十个数 要求下排每个数都是先前上排那十个数在下排出现的次数。 上排的十个数如下：
    【0，1，2，3，4，5，6，7，8，9】 举一个例子， 数值: 0,1,2,3,4,5,6,7,8,9 分配: 6,2,1,0,0,0,1,0,0,0 0 在下排出现了 6 次，1 在下排出现了 2 次， 2 在下排出现了 1 次，3 在下排出现了 0 次.... 以此类推.. 第 7 题 微软亚院之编程判断俩个链表是否相交 给出俩个单向链表的头指针，比如 h1，h2，判断这俩个链表是否相交。 为了简化问题，我们假设俩个链表均不带环。 问题扩展： 1.如果链表可能有环列? 2.如果需要求出俩个链表相交的第一个节点列? 第 8 题 此贴选一些 比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特 此并作一题。
    1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关， 这两个房间是 分割开的，从一间里不能看到另一间的情况。 现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控 制的。 有什么办法呢？ 2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块， 每天给出一块。 如果你只能将金条切割两次，你怎样分给这些工人? 3. 用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。 用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。 用一种算法整理一个数组。你为什么选择这种方法? 用一种算法使通用字符串相匹配。 颠倒一个字符串。优化速度。优化空间。 颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”， 实现速度最快，移动最少。 找到一个子字符串。优化速度。优化空间。 比较两个字符串，用 O(n)时间和恒量空间。 假设你有一个用 1001 个整数组成的数组，这些整数是任意排列的，但是你 知道所有的整数都在 1 到 1000(包括 1000)之间。此外，除一个数字出现 两次外， 其他所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法找出
    重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不 用 这种方式的算法吗? 不用乘法或加法增加 8 倍。现在用同样的方法增加 7 倍。 第 9 题 判断整数序列是不是二元查找树的后序遍历结果 题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。 如果是返回 true，否则返回 false。 例如输入 5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果： 8 / \ 6 10 / \ / \ 5 7 9 11 因此返回 true。 如果输入 7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回 false。 第 10 题 翻转句子中单词的顺序。
    题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。 句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。 例如输入“I am a student.”，则输出“student. a am I”。 第 11 题 求二叉树中节点的最大距离... 如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的， 我们姑且定义"距离"为两节点之间边的个数。 写一个程序， 求一棵二叉树中相距最远的两个节点之间的距离。 第 12 题 题目：求 1+2+…+n， 要求不能使用乘除法、for、while、if、else、switch、case 等关键字以及条 件判断语句（A?B:C）。
    第 13 题： 题目：输入一个单向链表，输出该链表中倒数第 k 个结点。链表的倒数第 0 个结 点为链表的尾指针。 链表结点定义如下： struct ListNode { int m_nKey; ListNode* m_pNext; }; 第 14 题： 题目：输入一个已经按升序排序过的数组和一个数字， 在数组中查找两个数，使得它们的和正好是输入的那个数字。 要求时间复杂度是 O(n)。如果有多对数字的和等于输入的数字，输出任意一对 即可。 例如输入数组 1、2、4、7、11、15 和数字 15。由于 4+11=15，因此输出 4 和 11。 第 15 题： 题目：输入一颗二元查找树，将该树转换为它的镜像，
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料