数据结构java面试题及答案

　　数组是最常用的基础数据结构，它将元素保存在连续的内存中。它也是面试最喜欢的问题之一，在代码面试中你会经常听到很多关于数组的问题，例如，数组的反转、数组的排序或者查找数组中的一个元素。

　　数组结构的一个关键优点是在知道索引的情况能够以O(1)的复杂度找到一个元素。但是增加或者删除一个元素是很慢的，因为一旦创建了一个数组，你就不能改变它的大小了。

　　为了创建一个更长或者更短的数组，你需要创建一个新的数组，然后将所有元素从旧数组中复制到新数组中。

　　解决数组问题的关键是，你要对数组这种数据结构有一个深刻的认识，同时还要了解基本的程序流程如循环、递归以及基本的操作符。

　　下面是一些经常问到和数组相关的面试题，你可以拿来练习：

　　1、在一个给定的从1到100的整型数组中，如何快速找到缺失的数字？

　　2、如何找到一个给定的整型数组中的重复数字？

　　3、在一个未排序的整型数组中，如何找到最大和最小的数字？

　　4、在一个整型数组中，如何找到一个所有成对的数字，满足它们的和等于一个给定的数字？

　　5、如果一个数组包含多个重复元素，如何找到这些重复的数字？

　　6、用Java实现从一个给定数组中删除重复元素？

　　7、如何利用快速排序对一个整型数组进行排序？

　　8、如何从一个数组中删除重复元素？

　　9、用Java实现数组反转？

　　10、如何不借助库实现从数组中删除重复元素？

　　链表问题

　　链表是另外一个常见的数据结构，对数组结构是一个补充。和数组类似，它也是一个线性的数据结构，以线性方式存储元素。

　　不过和数组不同的是，链表的元素不是存储在连续位置中，而是分散在各个内存中的各个位置，通过节点链接起来。一个链表就是一个包含了下个节点内存地址的节点列表。

　　基于这种结构，可以很容易实现链表中元素的添加和删除，因为只需要改变节点的指向而无需创建一个新的数组。不过链表中的查找是相对困难的，在一个单向链表中需要花费O(n)的时间代价来查找一个元素。

　　链表有几种不同的形式。首先是单向链表，在这个结构你只能向一个方向遍历（向前或者反转）；其次是双向链表，你可以双向遍历（向前或者向后）；最后是环形链表，组成一个环的形式。

　　要解决链表问题，你就必须了解递归的相关知识，因为链表是一种递归的数据结构。如果你从链表中去掉一个节点,剩下的数据结构仍然是链表，因此,许多链表问题有比遍历更简单的递归解决方案.

　　下面是一些最常见和流行的链表面试问题

　　1、在一次遍历中，怎样发现单个链表的中间元素?

　　2、怎样验证给定的链表是环形的?怎样发现这个环的起始节点?

　　3、怎样翻转链表?

　　4、不使用递归，怎样反转单个链表?

　　5、在未排序链表中，怎样移除重复的节点?

　　6、怎样找出单个链表的长度?

　　7、从单个链表的结尾处，怎样找出链表的第三个节点?

　　8、怎样使用栈计算两个链表的和?

　　字符串相关问题

　　与数组和链表数据结构一起，字符串是编程工作面试中的另一个热门话题。我从未参加过没有问过基于字符串相关问题的编码面试。

　　字符串的一个优势在于，如果你了解数组，你可以很容易地解决基于字符串的问题，因为字符串仅仅是一个字符数组。

　　因此，在解决基于数组的编程问题中所学到的所有技术也可用于解决字符串编程问题。

　　以下是编程求职面试中常见的字符串编程问题：

　　1、如何输出字符串中的重复字符？

　　2、如何判断两个字符串是否互为回文？

　　3、如何从字符串中输出第一个不重复字符？

　　4、如何使用递归实现字符串反转?

　　5、如何检查字符仅包含数字字符？

　　6、如何在字符串中找到重复字符？

　　7、如何对给定字符串中的元音及辅音进行计数？

　　8、如何计算给定字符传中特定字符出现的次数？

　　9、如何找到一个字符串的全排列？

　　10、在不使用任何库方法的情况下如何反转给定语句中的单词？

　　11、如何判断两个字符串是否互为旋转？

　　12、如何判断给定字符串是否是回文？

      以上就是动力节点Java培训机构小编介绍的“数据结构java面试题及答案”的内容，希望对大家有帮助，如有疑问，请在线咨询，有专业老师随时为你服务。