Java面试题集136150.docx
《Java面试题集136150.docx》由会员分享，可在线阅读，更多相关《Java面试题集136150.docx（32页珍藏版）》请在冰点文库上搜索。
Java面试题集136150
摘要：
这一部分主要是数据结构和算法相关的面试题目，虽然只有15道题目，但是包含的信息量还是很大的，很多题目背后的解题思路和算法是非常值得玩味的。
136、给出下面的二叉树先序、中序、后序遍历的序列？
答：
先序序列：
ABDEGHCF；中序序列：
DBGEHACF；后序序列：
DGHEBFCA。
补充：
二叉树也称为二分树，它是树形结构的一种，其特点是每个结点至多有二棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。
二叉树的遍历序列按照访问根节点的顺序分为先序（先访问根节点，接下来先序访问左子树，再先序访问右子树）、中序（先中序访问左子树，然后访问根节点，最后中序访问右子树）和后序（先后序访问左子树，再后序访问右子树，最后访问根节点）。
如果知道一棵二叉树的先序和中序序列或者中序和后序序列，那么也可以还原出该二叉树。
例如，已知二叉树的先序序列为：
xefdzmhqsk，中序序列为：
fezdmxqhks，那么还原出该二叉树应该如下图所示：
137、你知道的排序算法都哪些？
用Java写一个排序系统。
答：
稳定的排序算法有：
插入排序、选择排序、冒泡排序、鸡尾酒排序、归并排序、二叉树排序、基数排序等；不稳定排序算法包括：
希尔排序、堆排序、快速排序等。
下面是关于排序算法的一个列表：
下面按照策略模式给出一个排序系统，实现了冒泡、归并和快速排序。
Sorter.java
[java] viewplain copy
1.package com.jackfrued.util;
2.
3.import java.util.Comparator;
4.
5./**
6. * 排序器接口（策略模式:
将算法封装到具有共同接口的独立的类中使得它们可以相互替换）
7. * @author骆昊
8. *
9. */
10.public interface Sorter {
11.
12. /**
13. * 排序
14. * @param list 待排序的数组
15. */
16. public > void sort（T[] list）;
17.
18. /**
19. * 排序
20. * @param list 待排序的数组
21. * @param comp 比较两个对象的比较器
22. */
23. public void sort（T[] list, Comparator comp）;
24.}
BubbleSorter.java
[java] viewplain copy
1.package com.jackfrued.util;
2.
3.import java.util.Comparator;
4.
5./**
6. * 冒泡排序
7. * @author骆昊
8. *
9. */
10.public class BubbleSorter implements Sorter {
11.
12. @Override
13. public > void sort（T[] list） {
14. boolean swapped = true;
15. for（int i = 1; i < list.length && swapped;i++） {
16. swapped= false;
17. for（int j = 0; j < list.length - i; j++） {
18. if（list[j].compareTo（list[j+ 1]） > 0 ） {
19. T temp = list[j];
20. list[j]= list[j + 1];
21. list[j+ 1] = temp;
22. swapped= true;
23. }
24. }
25. }
26. }
27.
28. @Override
29. public void sort（T[] list,Comparator comp） {
30. boolean swapped = true;
31. for（int i = 1; i < list.length && swapped; i++） {
32. swapped = false;
33. for（int j = 0; j < list.length - i; j++） {
34. if（pare（list[j], list[j + 1]） > 0 ） {
35. T temp = list[j];
36. list[j]= list[j + 1];
37. list[j+ 1] = temp;
38. swapped= true;
39. }
40. }
41. }
42. }
43.}
MergeSorter.java
[java] viewplain copy
1.package com.jackfrued.util;
2.
3.import java.util.Comparator;
4.
5./**
6. * 归并排序
7. * 归并排序是建立在归并操作上的一种有效的排序算法。
8. * 该算法是采用分治法（divide-and-conquer）的一个非常典型的应用，
9. * 先将待排序的序列划分成一个一个的元素，再进行两两归并，
10. * 在归并的过程中保持归并之后的序列仍然有序。
11. * @author骆昊
12. *
13. */
14.public class MergeSorter implements Sorter {
15.
16. @Override
17. public > void sort（T[] list） {
18. T[] temp = （T[]） new Comparable[list.length];
19. mSort（list,temp, 0, list.length- 1）;
20. }
21.
22. private > void mSort（T[] list, T[] temp, int low, int high） {
23. if（low == high） {
24. return ;
25. }
26. else {
27. int mid = low + （（high -low） >> 1）;
28. mSort（list,temp, low, mid）;
29. mSort（list,temp, mid + 1, high）;
30. merge（list,temp, low, mid + 1, high）;
31. }
32. }
33.
34. private > void merge（T[] list, T[] temp, int left, int right, int last） {
35. int j = 0;
36. int lowIndex = left;
37. int mid = right - 1;
38. int n = last - lowIndex + 1;
39. while （left <= mid && right <= last）{
40. if （list[left].compareTo（list[right]） < 0）{
41. temp[j++] = list[left++];
42. } else {
43. temp[j++] = list[right++];
44. }
45. }
46. while （left <= mid） {
47. temp[j++] = list[left++];
48. }
49. while （right <= last） {
50. temp[j++] = list[right++];
51. }
52. for （j = 0; j < n; j++） {
53. list[lowIndex + j] = temp[j];
54. }
55. }
56.
57. @Override
58. public void sort（T[] list, Comparator comp） {
59. T[]temp = （T[]）new Comparable[list.length];
60. mSort（list,temp, 0, list.length- 1, comp）;
61. }
62.
63. private void mSort（T[] list, T[] temp, int low, int high, Comparator comp） {
64. if（low == high） {
65. return ;
66. }
67. else {
68. int mid = low + （（high -low） >> 1）;
69. mSort（list,temp, low, mid, comp）;
70. mSort（list,temp, mid + 1, high, comp）;
71. merge（list,temp, low, mid + 1, high, comp）;
72. }
73. }
74.
75. private void merge（T[] list, T[]temp, int left, int right, int last, Comparator comp） {
76. int j = 0;
77. int lowIndex = left;
78. int mid = right - 1;
79. int n = last - lowIndex + 1;
80. while （left <= mid && right <= last）{
81. if （pare（list[left], list[right]） <0） {
82. temp[j++] = list[left++];
83. } else {
84. temp[j++] = list[right++];
85. }
86. }
87. while （left <= mid） {
88. temp[j++] = list[left++];
89. }
90. while （right <= last） {
91. temp[j++] = list[right++];
92. }
93. for （j = 0; j < n; j++） {
94. list[lowIndex + j] = temp[j];
95. }
96. }
97.
98.}
QuickSorter.java
[java] viewplain copy
1.package com.jackfrued.util;
2.
3.import java.util.Comparator;
4.
5./**
6. * 快速排序
7. * 快速排序是使用分治法（divide-and-conquer）依选定的枢轴
8. * 将待排序序列划分成两个子序列，其中一个子序列的元素都小于枢轴，
9. * 另一个子序列的元素都大于或等于枢轴，然后对子序列重复上面的方法，
10. * 直到子序列中只有一个元素为止
11. * @author Hao
12. *
13. */
14.public class QuickSorter implements Sorter {
15.
16. @Override
17. public > void sort（T[] list） {
18. quickSort（list, 0, list.length- 1）;
19. }
20.
21. @Override
22. public void sort（T[] list, Comparator comp） {
23. quickSort（list, 0, list.length- 1, comp）;
24. }
25.
26. private > void quickSort（T[] list, int first, int last） {
27. if （last > first） {
28. int pivotIndex = partition（list, first, last）;
29. quickSort（list, first, pivotIndex - 1）;
30. quickSort（list, pivotIndex, last）;
31. }
32. }
33.
34. private void quickSort（T[] list, int first, int last,Comparator comp） {
35. if （last > first） {
36. int pivotIndex = partition（list, first, last, comp）;
37. quickSort（list, first, pivotIndex - 1, comp）;
38. quickSort（list, pivotIndex, last, comp）;
39. }
40. }
41.
42. private > int partition（T[] list, int first, int last） {
43. T pivot = list[first];
44. int low = first + 1;
45. int high = last;
46.
47. while （high > low） {
48. while （low <= high && list[low].compareTo（pivot） <= 0） {
49. low++;
50. }
51. while （low <= high && list[high].compareTo（pivot） >= 0） {
52. high--;
53. }
54. if （high > low） {
55. T temp = list[high];
56. list[high]= list[low];
57. list[low]= temp;
58. }
59. }
60.
61. while （high > first&& list[high].compareTo（pivot） >= 0） {
62. high--;
63. }
64. if （pareTo（list[high]）> 0） {
65. list[first]= list[high];
66. list[high]= pivot;
67. return high;
68. }
69. else {
70. return low;
71. }
72. }
73.
74. private int partition（T[] list, int first, int last, Comparator comp） {
75. T pivot = list[first];
76. int low = first + 1;
77. int high = last;
78.
79. while （high > low） {
80. while （low <= high&& pare（list[low], pivot） <= 0） {
81. low++;
82. }
83. while （low <= high&& pare（list[high], pivot） >= 0） {
84. high--;
85. }
86. if （high > low） {
87. T temp = list[high];
88. list[high] = list[low];
89. list[low]= temp;
90. }
91. }
92.
93. while （high > first&& pare（list[high], pivot） >= 0） {
94. high--;
95. }
96. if （pare（pivot,list[high]） > 0） {
97. list[first]= list[high];
98. list[high]= pivot;
99. return high;
100. }
101. else {
102. return low;
103. }
104. }
105.
106.}
138、写一个二分查找（折半搜索）的算法。
答：
折半搜索，也称二分查找算法、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。
搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空，则代表找不到。
这种搜索算法每一次比较都使搜索范围缩小一半。
[java] viewplain copy
1.package com.jackfrued.util;
2.
3.import java.util.Comparator;
4.
5.public class MyUtil {
6.
7. public static > int binarySearch（T[] x, T key） {
8. return binarySearch（x, 0, x.length- 1, key）;
升级会员 