考试心得:09考研数据结构试题解法Java认证考试

文章作者 100test 发表时间 2009:04:10 01:03:16
来源 100Test.Com百考试题网

　　今天去网上看了一下09年的考研试题，看见该题目（图片）：

　　先来定义结点（为了简便，省略set/get）：
　　public class Node
　　{
　　public int data.
　　public Node link.
　　}
　　我能想到的两种解法，一个基于递归：
　　递归版的思路就是，基于当前结点，如果后一个是倒数第K-1，那么当前结点是所求，若不然，返回当前是倒数第几个。
　　public int printRKWithRecur(Node head,int k)
　　{
　　if(k==0||head==null||head.link==null)return 0.
　　if(_recurFind(head.link,k)>.=k)return 1.
　　return 0.
　　}
　　private final int _recurFind(Node node, int k) {
　　if(node.link==null)
　　{
　　return 1.
　　}
　　int sRet=_recurFind(node.link,k).
　　if(sRet==k-1)
　　{
　　System.out.println("Got:" node.data).
　　return k.
　　}
　　return sRet 1.
　　}
　　对每个结点，该算法都只访问一次，因此复杂度O（N）。
　　第二解法，相对递归来说，这种方法可以算是消除递归版，而且从某种意义上来说比递归更高效，跟省空间，递归版实际上是把回溯的数据存在栈上，而版方法是自己存储，且利用数组实现一个循环队列，只存储K个元素。
　　public static class CycleIntQueue
　　{
　　int[] datas.
　　int top=0.
　　int num=0.
　　public CycleIntQueue(int n)
　　{
　　datas=new int[n].
　　}
　　public void push(int i)
　　{
　　datas[(top )趖as.length]=i.
　　num .
　　}
　　public int numPushed()
　　{
　　return num.
　　}
　　public int getButtom()
　　{
　　return datas[top趖as.length].
　　}
　　}
　　public int printRKWithCycleQueue(Node head,int k)
　　{
　　if(k==0||head==null)return 0.
　　CycleIntQueue queue=new CycleIntQueue(k).
　　Node cur=head.link.
　　while(cur!=null)
　　{
　　queue.push(cur.data).
　　cur=cur.link.
　　}
　　if(queue.numPushed()<.k)return 0.
　　System.out.println("Got:" queue.getButtom()).
　　return 1.
　　}
　　本算法，都每个结点也只放一次，另外进行一次入队操作，该操作复杂度O(1),从而，整个算法复杂度仍是O(N).