Google微软-华为腾讯-面试笔试数据结构和算法编程题目和部分答案 - CSDN文库

4星 · 超过85%的资源需积分: 10 7 浏览量更新于2023-03-03 评论 1 收藏 110KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

数据结构+算法面试常见试题

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.在二元树中找出和为某一值的所有路径

为了简化问题，我们假设俩个链表均不带环。

问题扩展：

1.如果链表可能有环列?

2.如果需要求出俩个链表相交的第一个节点列?

第 8 题

此贴选一些比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一

题。

1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，

这两个房间是分割开的，从一间里不能看到另一间的情况。

现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。

有什么办法呢？

2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出

一块。

如果你只能将金条切割两次，你怎样分给这些工人?

3.　★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。

　　★用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。

　　★用一种算法整理一个数组。你为什么选择这种方法?

　　★用一种算法使通用字符串相匹配。

　　★颠倒一个字符串。优化速度。优化空间。

　　★颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”，

实现速度最快，移动最少。

　　★找到一个子字符串。优化速度。优化空间。

　　★比较两个字符串，用 O(n)时间和恒量空间。

　　★假设你有一个用 1001 个整数组成的数组，这些整数是任意排列的，但是你知道所有

的整数都在 1 到 1000(包括 1000)之间。此外，除一个数字出现两次外，其他所有数字只出

现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在

运算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗?

　　★不用乘法或加法增加 8 倍。现在用同样的方法增加 7 倍。

第 9 题

判断整数序列是不是二元查找树的后序遍历结果

题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。

如果是返回 true，否则返回 false。

剩余28页未读，继续阅读

评论4

unistu

2013-01-06

没啥看的，都已经过时了

「已注销」

粉丝: 0
资源: 17

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈