《java 数据结构经典题》由会员分享，可在线阅读，更多相关《java 数据结构经典题（29页珍藏版）》请在金锄头文库上搜索。
1、1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。10/ 6 14/ / 4 8 12 16转换成双向链表4=6=8=10=12=14=16。首先我们定义的二元查找树 节点的数据结构如下：struct BSTreeNodeint m_nValue; / value of nodeBSTreeNode *m_pLeft; / left child of nodeBSTreeNode *m_pRight; / right child of node;2.设计包含 min 函数的栈。定义栈的数据结构，要求
2、添加一个 min 函数，能够得到栈的最小元素。要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。3.求子数组的最大和题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为 O(n)。例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为 3, 10, -4, 7, 2，因此输出为该子数组的和 18。4.在二元树中找出和为某一值的所有路径题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输
3、入整数相等的所有路径。例如 输入整数 22 和如下二元树10/ 5 12/47则打印出两条路径：10, 12 和 10, 5, 7。二元树节点的数据结构定义为：struct BinaryTreeNode / a node in the binary treeint m_nValue; / value of nodeBinaryTreeNode *m_pLeft; / left child of nodeBinaryTreeNode *m_pRight; / right child of node;5.查找最小的 k 个元素题目：输入 n 个整数，输出其中最小的 k 个。例如输入 1，2，3，4
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,00 在下排出现了 6 次，1 在下排出现了 2 次，2 在下排出现了 1 次，3 在下排出现了 0 次以此类推第 7 题微软亚院之编程判断俩个链表是否相交给出俩个单向链表的头指针，比如 h1，h2，判断这俩个链表是
5、否相交。为了简化问题，我们假设俩个链表均不带环。问题扩展：1.如果链表可能有环列?2.如果需要求出俩个链表相交的第一个节点列?第 8 题此贴选一些 比较怪的题，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，这两个房间是 分割开的，从一间里不能看到另一间的情况。现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。有什么办法呢？2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一块。如果你只能将金条切割两次，你怎样分给这些工人?3.用一种算法来颠倒一个链接表的顺序。
6、现在在不用递归式的情况下做一遍。用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。用一种算法整理一个数组。你为什么选择这种方法?用一种算法使通用字符串相匹配。颠倒一个字符串。优化速度。优化空间。颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”，实现速度最快，移动最少。找到一个子字符串。优化速度。优化空间。比较两个字符串，用 O(n)时间和恒量空间。假设你有一个用 1001 个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在 1 到 1000(包括 1000)之间。此外，除一个数字出现 两次外，其他所有数字只出现一次。假设你只能对这个数组做一次处理，用
7、一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不 用这种方式的算法吗?不用乘法或加法增加 8 倍。现在用同样的方法增加 7 倍。第 9 题判断整数序列是不是二元查找树的后序遍历结果题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回 true，否则返回 false。例如输入 5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：8/ 610/ / 5 7 9 11因此返回 true。如果输入 7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回 false。第 10 题翻转句子中单词的顺序。题目：输入一个英文
8、句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如输入“I am a student.”，则输出“student. a am I”。第 11 题求二叉树中节点的最大距离.如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义“距离“为两节点之间边的个数。写一个程序，求一棵二叉树中相距最远的两个节点之间的距离。第 12 题题目：求 1+2+n，要求不能使用乘除法、for、while、if、else、switch、case 等关键字以及条件判断语句（A?B:C）。第 13 题：题目：输入一个单向链表，输出该链表
9、中倒数第 k 个结点。链表的倒数第 0 个结点为链表的尾指针。链表结点定义如下：struct ListNodeint m_nKey;ListNode* m_pNext;第 14 题：题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是 O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组 1、2、4、7、11、15 和数字 15。由于 4+11=15，因此输出 4 和 11。第 15 题：题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两
10、种方法完成树的镜像转换。例如输入：8/ 6 10/ /5 7 9 11输出：8/ 10 6/ /11 9 7 5定义二元查找树的结点为：struct BSTreeNode / a node in the binary search tree (BST)int m_nValue; / value of nodeBSTreeNode *m_pLeft; / left child of nodeBSTreeNode *m_pRight; / right child of node;第 16 题：题目（微软）：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。例如输入8/
11、6 10/ / 5 7 9 11输出 8 6 10 5 7 9 11。第 17 题：题目：在一个字符串中找到第一个只出现一次的字符。如输入 abaccdeff，则输出 b。分析：这道题是 2006 年 google 的一道笔试题。第 18 题：题目：n 个数字（0,1,n-1）形成一个圆圈，从数字 0 开始，每次从这个圆圈中删除第 m 个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。当一个数字删除后，从被删除数字的下一个继续删除第 m 个数字。求出在这个圆圈中剩下的最后一个数字。July：我想，这个题目，不少人已经 见识过了。第 19 题：题目：定义 Fibonacci 数列如下
12、：/ 0 n=0f(n)= 1 n=1 f(n-1)+f(n-2) n=2输入 n，用最快的方法求该数列的第 n 项。分析：在很多 C 语言教科书中讲到递归函数的时候，都会用 Fibonacci 作为例子。因此很多程序员对这道题的递归解法非常熟悉，但呵呵，你知道的。第 20 题：题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。例如输入字符串“345“，则输出整数 345。第 21 题2010 年中兴面试题编程求解：输入两个整数 n 和 m，从数列 1，2，3.n 中 随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来.第 22 题：有 4 张红色的牌和 4 张蓝色的牌，
13、主持人先拿任意两张，再分别在 A、B、C 三人额头上贴任意两张牌，A、B、C 三人都可以看见其余两人额头上的牌，看完后让他们猜自己额头上是什么颜色的牌，A 说不知道，B 说不知道，C 说不知道，然后 A 说知道了。请教如何推理，A 是怎么知道的。如果用程序，又怎么实现呢？第 23 题：用最简单，最快速的方法计算出下面这个圆形是否和正方形相交。“3D 坐标系 原点(0.0,0.0,0.0)圆形:半径 r = 3.0圆心 o = (*.*, 0.0, *.*)正方形:4 个角坐标;1:(*.*, 0.0, *.*)2:(*.*, 0.0, *.*)3:(*.*, 0.0, *.*)4:(*.*,
14、0.0, *.*)第 24 题：链表操作，（1）.单链表就地逆置，（2）合并链表第 25 题：写一个函数,它的原形是 int continumax(char *outputstr,char *intputstr)功能：在字符串中找出连续最长的数字串，并把这个串的长度返回，并把这个最长数字串付给其中一个函数参数 outputstr 所指内存。例如：“abcd12345ed125ss123456789“的首地址传给 intputstr 后，函数将返回 9，outputstr 所指的值为 12345678926.左旋转字符串题目：定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。如
15、把字符串 abcdef 左旋转 2 位得到字符串 cdefab。请实现字符串左旋转的函数。要求时间对长度为 n 的字符串操作的复杂度为 O(n)，辅助内存为 O(1)。27.跳台阶问题题目：一个台阶总共有 n 级，如果一次可以跳 1 级，也可以跳 2 级。求总共有多少总跳法，并分析算法的时间复杂度。这道题最近经常出现，包括 MicroStrategy 等比较重视算法的公司都曾先后选用过个这道题作为面试题或者笔试题。28.整数的二进制表示中 1 的个数题目：输入一个整数，求该整数的二进制表达中有多少个 1。例如输入 10，由于其二进制表示为 1010，有两个 1，因此输出 2。分析：这是一道很基
16、本的考查位运算的面试题。包括微软在内的很多公司都曾采用过这道题。29.栈的 push、pop 序列题目：输入两个整数序列。其中一个序列表示栈的 push 顺序，判断另一个序列有没有可能是对应的 pop 顺序。为了简单起见，我们假设 push 序列的任意两个整数都是不相等的。比如输入的 push 序列是 1、2、3、4、5，那么 4、5、3、2、1 就有可能是一个 pop 系列。因为可以有如下的 push 和 pop 序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，这样得到的 pop 序列就是 4、5、3、2、1。但序列 4、3、5、1、2 就不可能是 push 序列 1、2、3、4、5 的 pop 序列。30.在从 1 到 n 的正数中 1 出现的次数题目：输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。例如输入 12，从 1 到 12 这些整数中包含 1 的数字有 1，1
