数据结构基础知识面试题(数据结构面试题目及答案)

数据结构笔试面试复习

慎进华为，尤其是做技术人员的，每年都有跳楼的员工，就是因为工作压力太大

LOOK 这个连接：

进去用搜索搜一下就有

● 华为公司2008年应届毕业生校园招聘宣讲会 [2007/11/05]

○华为公司宣讲会地点—教学主楼一楼多功能报 [2007/11/01]

金蝶笔试题：金蝶和华为面试_JiuYeWang.com [2007/10/29]

面试试题早知道：华为面试题 [2007/10/23]

面试斯伦贝谢和华为 [2007/10/23]

2007年华为笔试题题型 [2007/10/23]

华为新员工转正笔试题(附答案） [2007/10/23]

华为硬件笔试题(2005年11月8日19点南京) [2007/10/23]

华为2005年11月的笔试题目 [2007/10/23]

[华为笔试大全]华为最新笔试题及其分析 [2007/10/23]

11月27日的华为3com的软件笔试题概述 [2007/10/23]

华为3COM招聘数据通信工程师试题 2005.11.21 [2007/10/23]

华为3com笔试试题目 2005.11.21 [2007/10/23]

2006年华为研发类笔试编程题(2006年10月29日晚... [2007/10/23]

2008华为校园招聘 [2007/10/08]

[华为面经大全]我在华为面试的真实经历 [2007/09/29]

上周末去华为面试的一些情况,和大家分享一二 [2007/09/29]

[华为面经大全]华为面经（暴笑） [2007/09/29]

[华为面经大全]华为3COM国际技术支持面经 [2007/09/29]

[华为面经大全]中兴和华为的面试经历 [2007/09/29]

[华为面经大全]seallow的华为面经 [2007/09/29]

[华为面经大全]真实体验：应聘华为，三进三出（1） [2007/09/29]

[华为面经大全]真实体验：应聘华为，三进三出（2） [2007/09/29]

[华为面经大全]真实体验：应聘华为，三进三出（3） [2007/09/29]

目前为止最详细的华为面试（包括详细的流程） [2007/09/29]

上周末去华为面试的一些情况,和大家分享一二 [2007/09/29]

华为2004年招收应届大学毕业生技术支持面试题 [2007/09/29]

华为新员工转正笔试题(附答案） [2007/09/29]

面试试题早知道：华为面试题 [2007/09/29]

[华为面经大全]华为3COM的面试经过 [2007/09/29]

大公司笔试面试有哪些经典算法题目？

大公司面试的算法题目多半也是仿照行业经典题库出的，还有的也是结合自己公司业务中的实际情况，用几个特别的案例形式筛选出自己想要的人才。可以去下载一下谷歌微软的经典题库多多复习，还可以到各大公司的论坛贴吧群去看一下笔试和面试经验。

下面简单列举一些经典算法题：

1.判断一个字符串中的字符是否唯一

2.字符串翻转

3.去除字符串中重复字符

4.利用已知函数判断字符串是否为另一字符串的子串

5. 从链表中移除重复结点

6.实现一个算法从一个单链表中返回倒数第n个元素

7. 给定链表中间某结点指针，删除链表中该结点

8.求由两个链表结点组成的数之和

9. 给定一个循环链表，实现一个算法返回这个环的开始结点

10 如何只用一个数组实现三个栈

11. 实现一个栈，要求实现min函数以返回栈中的最小值

12.实现数据结构SetOfStacks来模拟叠盘子

13. 编程解决汉诺塔问题

14.使用两个栈实现一个队列

15. 写程序将一个栈按升序排序

16. 用一个函数判断一棵树是否平衡

17. 设计算法判断有向图两结点间是否存在路径

18. 将递增数组构建成一颗最小高度二叉树

19.将二叉树每一层结点构建成一个链表

20. 查找二叉查找树的任意给定结点的“下一个”结点

21.找出一棵二叉树中两个结点的第一个共同祖先结点

22. 判断一棵二叉树是否为另一棵二叉树的子树

23.输出二叉树中路径上结点值之和为给定值的所有路径

24.写程序使整数N中第i位到第j位的值与整数M中的相同

25.给定一个字符串类型表示的小数，输出其二进制表示

26. 给定一个整数x,找出另外两个二进制表示中1的个数和x相同的数

27.解释以下代码的作用：((n (n-1)) == 0)

28. 交换一个整数二进制表示中的奇数位和偶数位

29. 写程序找出丢失的整数，要求时间复杂度O(n)

30. 为通用卡牌游戏设计数据结构，并设计子类

我们可以把每一类的题目都细细研究，触类旁通，只有掌握了基础的知识才能慢慢解决复杂问题。

五分钟玩转面试考点-数据结构-最大堆与最小堆（TOP N问题）

咳咳：俗话说： 脱离业务的技术，就是耍流氓 。那么我就要提出这篇文章的灵魂一问了，请听题：

这个时候，感觉就是M个数中选择N个数 ，就是TOP N问题呀，是不是脑海中不由自主的蹦出了排序算法啦~

哈哈，咱就按照这个思路走。然后， 表面不慌，假装思索中ing，其实内心再想：排序算法是啥呀？

冒泡排序 ，核心思想： 相邻比较。 每次将最大的浮出水面。

快速排序 ，核心思想： 分治法+挖坑填数。 每次选择一基数，排序完成左边比基数小，右边比基数大。一直切分（ 分治 ），直至选出 无序 的最大的N个整数。

堆排序（出场自带猪脚光环~） ，可以创建一个N大小的 最小堆 。然后balabala。

我就拿（内心PS：读书人的事情，怎么能说偷呢？）一下图吧，放在这里这里让大家容易理解~~

给定一个列表array=[16,7,3,20,17,8]，对其进行堆排序。

首先根据该数组元素构建一个完全二叉树，得到

然后需要构造初始堆，则从最后一个非叶节点开始调整，调整过程如下：

第一步：找到最后一个组（非叶节点）， 左节点8 pk 擂主3 ，左孩子8胜利！然后3和8互相调换位置。 败者3 没有子节点，结束比赛。

从右到左。组内pk， 左子树20 pk 右子树17 左子树20胜利，获得挑战擂主7的机会。 左子树20 pk 擂主7 左子树20胜利，20和7交换位置。 败者7 没有子节点，结束比赛。

从下到上， 左子树20 PK 右子树8 ，左子树20胜利。获得挑战擂主16的机会。 左子树20 pk 擂主16 左子树胜利，交换位置。

此时 败者16 含有孩子节点，将被挑战。

组内挑战开始： 左子树7 和 右子树17 组内pk，右子树17胜利。获取挑战擂主16的机会。 右子树17 和 擂主16 pk，右子树17胜利，交换位置。 败者16 无孩子节点，结束比赛。

这样就得到了 初始堆 。

哈哈，相信到这里，基本懂得同学还是懂，不懂得还是一脸XX。这是哪？我在干什么？你是谁？

1. 找到最后一个非叶节点，从右到左，从下到上 ，遍历所有 非叶节点 ；

2.若是父节点 小于 最大的子节点 ，那么交换父子节点的位置，但是要注意，交换之后 对其他节点的影响。

我们的目标是：

( 没有蛀牙.... ) 根节点一定是树中最大的值。同时，父节点大于子节点 。

切回到我们的问题。此时，你应该基本知道了堆的概念，为什么不选最大堆呢？因为咱们选最小堆就是采用 末位淘汰制 。将堆中最小元素剔除。

每次最小堆调整后，总会将整个堆中 最小的元素放在根节点上 ，然后我们分别取出 [N-1,M] 中的元素，若大于堆顶，则替换。然后（ 随着堆的蠕动，你可以动态想想这个画面~~ ） 再次 将最小元素选出放于堆顶。 直至堆里保存的都是最大的元素。

还是上面的数组，证据在上面，咱们就开始分析啦：

咱们从i=5，最后一个元素array[5]开始说起：

父节点 ：(i-1)/2=2， 他的父节点就是i=2 ，array[2]也就是3。

子节点 ： 2i+1=11，等等兄得，你越界了...你根本没有孩子节点...(名侦探小胖)

于是我就大胆推测一下， 最后一个非子节点就是array[2]。

反向推理一下 ：i=2时，左孩子：2i+1=5，右孩子：2i+2=6，但是最大下标是5，那么 只有一个孩子节点array[5] 也就是8。

那倒数第二个下标非叶节点的下标是啥？

博主内心独白：emmm我也不知道....继续套公式，看看有啥规律不。

数组倒数第二个下标数是i=4，(i-1)/2=1，那么 下标array[1]就是第2个父节点。

数组倒数第三个下标数是i=3，(i-1)/2=1，也是下标array[1]。

那倒数第一个下标非叶节点的下标是啥？

数组倒数第四个下标数是i=2，(i-1)/2=1，那么 下标array[0]就是第3个父节点。

数组倒数第三个下标数是i=1，(i-1)/2=1，也是下标array[0]。

此时还有吗？

数组倒数第五个下标数是i=0，(i-1)/2=-1，也是下标array[-1]。

也就是根节点没有父节点了....

等等，我好像发现啥规律了...

父节点是array[2]=3 array[1]=7 array[0]=16。

array=[16,7,3,20,17,8]

现在要开始 XX联盟S17 的比赛，比赛组根据玩家投票新采用了一种新的比赛规则，规则如下：

横向：每个新晋擂主可以参与更高一级的比赛，直至选出冠军。登顶大根堆顶峰；

纵向：每个下台擂主要被更低一级的选手挑战，需要证明自己实力，也可能被一撸到底；

简言之：能者上，弱者下

每一小组选出最强者，参与擂主pk， 胜利者获取下一次挑战机会；失败者要被挑战，直至完成一场胜利，或者排名倒数 。

而后，开始了激烈的小组比赛，擂主 先把收拾自己的东西 ，因为他也不知道自己是一败涂地还是保持原位！心里有些忐忑~

215. 数组中的第K个最大元素

兜兜转转，从第一篇博客到2021.08.22已经过去了2年半多了。今天又回到这个题目。带来一种最小堆更加简洁的实现。即依赖JDK API来实现最小堆，只需要使得最小堆维护top n个元素即可。