【计算机类职业资格】(Java)程序员面试-15及答案解析.doc

1、(Java)程序员面试-15 及答案解析(总分：100.00，做题时间：90 分钟)一、论述题(总题数：26，分数：100.00)1.如何找出单链表中的倒数第 k 个元素 （分数：4.00）_2.如何实现链表的反转 （分数：4.00）_3.如何从尾到头输出单链表 （分数：4.00）_4.如何寻找单链表的中间结点 （分数：4.00）_5.如何检测一个链表是否有环 （分数：4.00）_6.如何在不知道头指针的情况下删除指定结点 （分数：4.00）_7.如何判断两个链表是否相交 （分数：4.00）_8.栈与队列有哪些区别 （分数：4.00）_9.如何实现栈 （分数：4.00）_10.如何用 O(1)

2、的时间复杂度求栈中最小元素 （分数：4.00）_11.如何实现队列 （分数：4.00）_12.如何用两个栈模拟队列操作 （分数：4.00）_13.如何进行选择排序 （分数：4.00）_14.如何进行插入排序 （分数：4.00）_15.如何进行冒泡排序 （分数：4.00）_16.如何进行归并排序 （分数：4.00）_17.如何进行快速排序 （分数：4.00）_18.如何进行希尔排序 （分数：4.00）_19.如何进行堆排序 （分数：4.00）_20.各种排序算法有什么优劣 （分数：4.00）_21.如何用移位操作实现乘法运算 （分数：4.00）_22.如何判断一个数是否为 2 的 n 次方 （分

3、数：4.00）_23.如何求二进制数中 1 的个数 （分数：3.00）_24.如何寻找数组中的最小值与最大值 （分数：3.00）_25.如何找出数组中第二大的数 （分数：3.00）_26.如何求最大子数组之和 （分数：3.00）_(Java)程序员面试-15 答案解析(总分：100.00，做题时间：90 分钟)一、论述题(总题数：26，分数：100.00)1.如何找出单链表中的倒数第 k 个元素 （分数：4.00）_正确答案：()解析：为了找出单链表中的倒数第 k 个元素，最容易想到的方法是首先遍历一遍单链表，求出整个单链表的长度 n，然后将倒数第 k 个，转换为正数第 n-k 个，接下去遍历

4、一次就可以得到结果。但是该方法存在一个问题，即需要对链表进行两次遍历，第一次遍历用于求解单链表的长度，第二次遍历用于查找正数第n-k 个元素。 显然，以上这种方法还可以进行优化。于是想到了第二种方法，如果沿从头至尾的方向从链表中的某个元素开始，遍历 k 个元素后刚好达到链表尾，那么该元素就是要找的倒数第 k 个元素，根据这一性质，可以设计如下算法：从头结点开始，依次对链表的每一个结点元素进行这样的测试，遍历 k 个元素，查看是否到达链表尾，直到找到那个倒数第 k 个元素。此种方法将对同一批元素进行反复多次的遍历，对于链表中的大部分元素而言，都要遍历 k 个元素，如果链表长度为 n，该算法时间复

5、杂度为 O(kn)级，效率太低。 存在另外一种更高效的方式，只需要一次遍历即可查找到倒数第 k 个元素。由于单链表只能从头到尾依次访问链表的各个结点，因此，如果要找出链表的倒数第 k 个元素的话，也只能从头到尾进行遍历查找，在查找过程中，设置两个指针，让其中一个指针比另一个指针(虽然 Java 语言没有指针的概念，但是引用与指针有着非常相似的性质。为了便于理解，在后续的介绍中都采用指针的概念来介绍)先前移 k-1 步，然后两个指针同时往前移动。循环直到先行的指针值为 NULL 时，另一个指针所指的位置就是所要找的位置。程序代码如下： public Node findElem(Node head

6、, int k) if(k1 | kthis.length() return null; Node p1=head; Node p2=head; for(int i=0; ik-1; i+)/前移 k-1 步 p1=p1.next; while(p1!=null) p1=p1.next; p2=p2.next; return p2; 2.如何实现链表的反转 （分数：4.00）_正确答案：()解析：为了正确地反转一个链表，需要调整指针的指向，而与指针操作相关代码总是非常容易出错的。先举个例子看一下具体的反转过程，例如，i，m，n 是 3 个相邻的结点，假设经过若干步操作，已经把结点i 之前的指针

7、调整完毕，这些结点的 next 指针都指向前面一个结点。现在遍历到结点 m，当然，需要调整结点的 next 指针，让它指向结点 i，但需要注意的是，一旦调整了指针的指向，链表就断开了，因为已经没有指针指向结点 n，没有办法再遍历到结点 n 了，所以为了避免链表断开，需要在调整 m 的 next 之前要把 n 保存下来。接下来试着找到反转后链表的头结点，不难分析出反转后链表的头结点是原始链表的尾结点，即 next 为空指针的结点。下面给出非递归方法实现链表的反转的实现代码。 public void ReverseIteratively(Node head) Node pReversedHead=

8、head; Node pNode=head; Node pPrev=null; while(pNode!=null) Node pNext=pNode.next; if(pNext=null) pReversedHead=pNode; pNode.next=pPrev; pPrev=pNode; pNode=pNext; this.head=pReversedHead;3.如何从尾到头输出单链表 （分数：4.00）_正确答案：()解析：从头到尾输出单链表比较简单，通过借鉴的想法，要想解决本问题，很自然地想把链表中链接结点的指针反转过来，改变链表的方向，然后就可以从尾到头输出了，但该方法需要额外

9、的操作，是否还有更好的方法呢?答案是有。 接下来的想法是从头到尾遍历链表，每经过一个结点，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始输出结点的值，此时输出的结点的顺序已经反转过来了。该方法虽然没有只需要遍历一遍链表，但是需要维护一个额外的栈空间，实现起来会比较麻烦。 是否还能有更高效的方法?既然想到了栈来实现这个函数，而递归本质上就是一个栈结构，于是很自然地又想到了递归来实现。要实现反过来输出链表，每访问到一个结点，先递归输出它后面的结点，再输出该结点自身，这样链表的输出结果就反过来了。 具体实现代码如下： public void printListReversely(Node p

10、ListHead) if(pListHead!=null) printListReversely(pListHead.next); System.out.println(pListHead.data); 4.如何寻找单链表的中间结点 （分数：4.00）_正确答案：()解析：如何寻找单链表的中间结点?最容易想到的思路是先求解单链表的长度 length，然后遍历 length/2的距离即可查找到单链表的中间结点，但是此种方法需要遍历两次链表，即第一次遍历求解单链表的长度，第二次遍历根据索引获取中间结点。 如果是双向链表，可以首尾并行，利用两个指针一个从头到尾遍历，一个从尾到头遍历，当两个指针相遇时

11、，就找到了中间元素。以此思想为基础，如果是单链表，也可以采用双指针的方式来实现中间结点的快速查找。 具体而言，第一步，有两个指针同时从头开始遍历；第二步，一个快指针一次走两步，一个慢指针一次走一步；第三步，快指针先到链表尾部，而慢指针则恰好到达链表中部(快指针到链表尾部时，当链表长度为奇数时，慢指针指向的即是链表中间指针，当链表长度为偶数时，慢指针指向的结点和慢指针指向结点的下一个结点都是链表的中间结点)。 具体实现代码如下： public Node SearchMid(Node head) Node p=this.head; Node q=this.head; while(p!=null q

12、=q.next; return q;5.如何检测一个链表是否有环 （分数：4.00）_正确答案：()解析：定义两个指针 fast 与 slow，其中，fast 是快指针，slow 是慢指针，二者的初始值都指向链表头，slow 每次前进一步，fast 每次前进两步，两个指针同时向前移动，快指针每移动一次都要跟慢指针比较，直到当快指针等于慢指针为止，就证明这个链表是带环的单向链表，否则，证明这个链表是不带环的循环链表(fast 先行到达尾部为 NULL，则为无环链表)。具体实现代码如下： public boolean IsLoop(Node head) Node fast=head; Node s

13、low=head; if(fast=null) return false; while(fast!=null slow=slow.next; if(fast=slow) return true; return!(fast=null | fast.next=null); 上述方法只能用来判断链表是否有环，那么如何找到环的入口点呢?如果单链表有环，按照上述思路，当走得快的指针 fast 与走得慢的指针 slow 相遇时，slow 指针肯定没有遍历完链表，而 fast 指针已经在环内循环了 n 圈(n=1)。假设 slow 指针走了 s 步，则 fast 指针走了 2s 步(fast 步数还等于 s

14、 加上在环上多转的 n 圈)，设环长为 r，则满足如下关系表达式： 2s=a+nr s=nr 设整个链表长 L，入口环与相遇点距离为 x，起点到环入口点的距离为 a，则满足如下关系表达式： a+x=Fir a+x=(n-1)r+r=(n-1)r+L-a a=(n-1)r+(L-a-x) (L-a-x)为相遇点到环入口点的距离，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是在链表头与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。 具体实现代码如下： publieNode FindLoopPort(Node head) Node slow=head

15、, fast=head; while(fast!=null fast=fast.next.next; if(slow=fast)break; if(fast=null | fast.next=null) return null; slow=head; while(slow !=fast) slow=slow.next; fast=fast.next; return slow; 6.如何在不知道头指针的情况下删除指定结点 （分数：4.00）_正确答案：()解析：可以分为两种情况来讨论： 若待删除的结点为链表尾结点，则无法删除，因为删除后无法使其前驱结点的 next 指针置为空； 若待删除的结点不

16、是尾结点，则可以通过交换这个结点与其后继结点的值，然后删除后继结点。 具体实现代码如下： public boolean deleteNode(Node n) if(n=null | n.next=null) return false; int tmp=n.data; n.data=n.next.data; n.next.data=tmp; n.next=n.next.next; return true; 7.如何判断两个链表是否相交 （分数：4.00）_正确答案：()解析：如果两个链表相交，那么它们一定有着相同的尾结点，因此实现思路为：分别遍历两个链表，记录它们的尾结点，如果它们的尾结点相同，

17、那么这两个链表相交，否则不相交。具体实现代码如下： publie boolean isIntersect(Node h1, Node h2) if(h1=null | h2=null) retum false; Node tail1=h1; /找到链表 h1 的最后一个结点 while(tail1.next!=null) tail1=tail1.next; Node tail2=h2; /找到链表 h2 的最后一个结点 while(tail2.next!=null) tail2=tail2.next; return tail1=tail2; 由于这个算法只需要分别遍历一次两个链表，因此算法的时

18、间复杂度为 O(len1+len2)，其中 len1 和 len2分别代表两个链表的长度。 引申：如果两个链表相交，如何找到它们相交的第一个结点? 首先分别计算两个链表 head1、head2 的长度 len1 和 len2(假设 len1len2)，接着先对链表 head1 遍历(len1-len2)个结点到结点 P，此时结点 P 与 head2 到它们相交的结点的距离相同，此时同时遍历两个链表，直到遇到相同的结点为止，这个结点就是它们相交的结点。需要注意的是，在查找相交的第一个结点前，需要先判断两个链表是否相交，只有在相交的情况下才有必要去找它们的交点，否则根本就没有必要了。 程序代码如下

19、： public static Node getFirstMeetNode(Node h1, Node h2) if(h1=null | h2=null) return null; Node tail1=h1; int len1=1; /找到链表 h1 的最后一个结点 while(tail1.next!=null) tail1=tail1.next; len1+; Node tail2=h2; int len2=1; /找到链表 h2 的最后一个结点 while(tail2.next!=null) tail2=tail2.next; len2+; /两链表不相交 if(tail1!=tail2

20、) return null; Node t1=h1; Node t2=h2; /找出较长的链表，先遍历 if(len1len2) int d=len1-len2; while(d!=0) t1=t1.next; d-; else int d=len2-len1; while(d!=0) t2=t2.next; d-; while(t1!=t2) t1=t1.next; f2=t2.next; return t1; 同理，由于这个算法也只需要分别遍历一次两个链表，因此算法的时间复杂度为 O(len1+len2)，其中len1 和 len2 分别代表两个链表的长度。当然，在具体实现时可以使用前面已

21、经实现的方法来判断两个链表是否相交，也可以利用前面已经实现的方法来分别计算两个链表的长度。但这种方法也存在着一个缺点：需要对每个链表遍历两遍。第一遍用来判断链表是否相交，第二遍计算链表的长度，因此效率会比上例中的实现方式低。其优点是代码简洁，可用性强。8.栈与队列有哪些区别 （分数：4.00）_正确答案：()解析：栈与队列是在程序设计中被广泛使用的两种重要的线性数据结构，都是在一个特定范围的存储单元中存储的数据。这些数据都可以重新被取出使用，与线性表相比，它们的插入和删除操作受到更多的约束和限定，故又称为限定性的线性表结构。不同的是，栈就像一个很窄的桶，先存进去的数据只能最后被取出来，是 LI

22、FO(Last In First Out，后进先出)，它将进出顺序逆序，即先进后出，后进先出，栈结构示意图如图 1 所示。队列则像人们日常排队买东西的“队列”，先排队的人先买，后排队的人后买，是FIFO(First In First Out，先进先出)的，它保持进出顺序一致，即先进先出，后进后出，队列结构示意图如图 2 所示。 图 1 栈结构示意图9.如何实现栈 （分数：4.00）_正确答案：()解析：可以采用数组与链表这两种方法来实现栈。 下面给出用数组实现栈的代码： impoa java.util.Arrays; public class MyStackE private Objectst

23、ack; private int size;/数组中存储元素的个数 public MyStack() stack=new Object10; /初始长度为 10 /判断堆栈是否为空 public boolean isEmpty() return size=0; public E peek() if(isEmpty() return null; return(E)stacksize-1; public E pop() E e=peek(); stacksize-1=null; size-; return e; public E push(E item) ensureCapacity(size+1

24、); /检查容量 stacksize+=item; return item; /判断数组器是否已满，若已满，则扩充数组空间 private void ensureCapacity(int size) int len=stack.length; if(sizelen)/数组已满 int newLen=10; /每次数组扩充的容量 stack=Arrays.eopyOf(stack, newLen); public static void main(Stringargs) MyStackIntegers=new MyStackInteger(); s.push(1); s.push(2); Sys

25、tem.out.println(“栈中元素个数:“+s.size); System.out.println(“栈顶元素为:“+s.pop(); System.out.println(“栈顶元素为:“+s.pop(); 下面给出采用链表的方式实现栈的代码。 class NodeE NodeEnext=null; E clata; public Node(E data)this.data=data; public class StackE NodeEtop=null; public boolean isEmpty() return top=null; public void push(E data

26、) NodeEnewNode=new NodeE(data); newNode.next=top; top=newNode; public E pop() if(this.isEmpty() return null; E data=top.data; top=top.next; return data; public E peek() if(isEmpty() return null; return top.data; 需要注意的是，上述的实现不是线程安全的。若要实现线程安全的栈，则需要对入栈和出栈等操作进行同步，在此就不详细介绍了。10.如何用 O(1)的时间复杂度求栈中最小元素 （分数：4

27、.00）_正确答案：()解析：由于栈具有后进先出的特点，因此 frash 和 pop 只需要对栈顶元素进行操作。如果使用上述的实现方式，只能访问到栈顶的元素，而无法得到栈中最小的元素。当然，可以用另外一个变量来记录栈底的位置，通过遍历栈中的所有元素找出最小值，但是这种方法的时间复杂度为 O(n)，那么如何才能用 O(1)的时间复杂度求出栈中最小的元素呢?在算法设计中，经常会采用空间来换取时间的方式来提高时间复杂度，也就是说，采用额外的存储空间来降低操作的时间复杂度。具体来讲就是在实现时使用两个栈结构，一个栈用来存储数据，另一个栈用来存储栈的最小元素。其实现思路如下：如果当前入栈的元素比原来栈中

28、的最小值还小，则把这个值压入保存最小元素的栈中；在出栈时，如果当前出栈的元素恰好为当前栈中的最小值，保存最小值的栈顶元素也出栈，使得当前最小值变为其入栈之前的那个最小值。为了简单起见，可以在栈中保存 Interger 类型，采用前面用链表方式实现的栈，实现代码如下： public class MyStack1 MyStackIntegerelem; MyStackIntegermin; public MyStack1() elem=new MyStackInteger(); min=new MyStackInteger(); public void push(int data) elem.pu

29、sh(data); if(min.isEmpty() min.push(data); else if(datamin.peek() min.push(data); public int pop() int topData=elem.peek(); elem.pop(); if(topData=this.min() min.pop(); return topData; public int min() if(min.isEmpty() return Integer.MAX_VALUE; else return min.peek(); 11.如何实现队列 （分数：4.00）_正确答案：()解析：与

30、栈类似，队列也可以采用数组和链表两种方式来实现。下面给出采用链表方式实现队列的代码： class NodeE NodeEnext=null; E data; public Node(E data)this.data=data; public class MyQueueE private NodeEhead=null; private NodeEtail=null; public boolean isEmpty() return head=tail; public void put(E data) NodeEnewNode=new NodeE(data); if(head=null else t

31、ail.next=newNode; tail=newNode; public E pop() if(this.isEmpty() return null; E data=head.data; head=head.next; return data; public int size() NodeEtmp=head; int n=0; while(tmp!=null) n+; tmp=tmp.next; return n; public static void main(Stringargs) MyQueueIntegerq=new MyQueueInteger(); q.put(1); q.pu

32、t(2); q.put(3); System.out.println(“队列长度为:“+q.size(); System.out.println(“队列首元素:“q.pop(); System.out.println(“队列首元素:“+q.pop(); 运行结果为： 队列长度为：3 队列首元素：1 队列首元素：2 下面介绍数组实现队列的方式，为了实现多线程安全，增加了对队列操作的同步，实现代码如下： public class MyQueueE private LinkedListElist=new LinkedListE(); private int size=0; public synchr

33、onized void put(E e) ist.addLast(e); size+; public synchronized E pop() size-; return list.removeFirst(); public synchronized boolean empty() return size=0; public synchronized int size() return size; 12.如何用两个栈模拟队列操作 （分数：4.00）_正确答案：()解析：假设使用栈 A 与栈 B 模拟队列 Q，A 为插入栈，B 为弹出栈，以实现队列 Q。 再假设 A 和 B 都为空，可以认为栈

34、A 提供入队列的功能，栈 B 提供出队列的功能。 要入队列，入栈 A 即可，而出队列则需要分两种情况考虑： 1)若栈 B 不为空，则直接弹出栈 B 的数据。 2)若栈 B 为空，则依次弹出栈 A 的数据，放入栈 B 中，再弹出栈 B 的数据。 以上情况可以利用前面介绍的栈来实现，也可以采用 Java 类库提供的 Stack 来实现，下面代码是采用Java 内置的 Stack 来实现的： public class MyQueueE private StackEs1=new StackE(); private StackEs2=new StackE(); public synchronized v

35、oid put(E e) s1.push(e); public synchronized E pop() if(s2.isEmpty() while(!s1.isEmpty() s2.push(s1.pop(); return s2.pop(); public synchronized boolean empty() return s1.isEmpty() public static void main(Stringargs) MyQueueIntegerq=new MyQueueInteger(); q.put(1); q.put(2); System.out.println(“队列首元素:

36、“+q.pop(); System.out.println(“队列首元素:“+q.pop(); 程序运行结果为： 队列首元素：1 队列首元素：2 引申：如何使用两个队列实现栈? 假设使用队列 q1 与队列 q2 模拟栈 S，q1 为入队列，q2 为出队列。 实现思路：可以认为队列 q1 提供压栈的功能，队列 q2 提供弹栈的功能。 要压栈，入队列 q1 即可，而当弹栈时，出队列则需要分两种情况考虑： 1)若队列 q1 中只有一个元素，则让 q1 中的元素出队列并输出即可。 2)若队列 q1 中不只一个元素，则队列 q1 中的所有元素出队列，入队列 q2，最后一个元素不入队列 B，输出该元素，然

37、后将队列 q2 所有元素入队列 q1。13.如何进行选择排序 （分数：4.00）_正确答案：()解析：选择排序是一种简单直观的排序算法，其基本原理如下：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录与第一个记录的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二轮比较，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个时为止。以数组38，65，97，76，13，27，49为例，选择排序的具体步骤如下： 第一趟排序后：1365 97 76 38 27 49 第二趟排序后：13 2797 76 38 65 49 第三趟排序后：13 27 3876 97 65 49 第四趟排序后：13 27 38 4997 65 76 第五趟排序后：13 27 38 49 6