算法笔试题总结

一、递归和分制策略汉诺塔递归实现：Voidhannoi(intn,charx,chary,charz){if(n==1)move(x,1,z);//printf(“%iMovedisk%ifrom%cto%c\n”,++c,n,x,z)//将编号1从x移到zelse{hanoi(n-1,x,z,y);//将x上编号1至n-1的移到y，z做辅助move(x,n,z);//将编号n从x移到zhanoi(n-1,y,x,z);//将y上编号1至n-1的移到z，x做辅助}}递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。解决方法：在递归算法中消除递归调用，使其转化为非递归算法。1.采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。2.用递推来实现递归函数。3.通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。排序总结排序方法平均时间最坏情况辅助存储稳定性插入排序直接插入O(n^2)O(n^2)O()稳定希尔排序O(n^1.3)O(n^2)O()不稳定交换排序冒泡排序O(n^2)O(n^2)O()稳定快速排序O(nlogn)O(n^2)O(logn)不稳定选择排序简单选择O(n^2)O(n^2)O(1)稳定堆排序O(nlogn)O(nlogn)O(1)不稳定基数排序O(d(n+rd))O(d(n+rd))O(rd)稳定归并排序O(nlogn)O(nlogn)O(n)稳定直接插入排序：voidinsertSort(listtp&r){for(i=2;i=n;i++){r[0]=r[i];/*设置监视哨*/j=i-1;k=r[i].key;while(j0&&r[j].keyk)/*大值的记录后移*/{r[j+1]=r[j];j--;}r[j+1]=r[0];/*插入位置*/}}/*straisort*/希尔排序：将整个序列划分成若干子序列，分别进行直接插入排序。voidShellSort(SeqListR,intdlta[],intt){For(k=0;kt;k++)ShellInsert(R，dlta[k])；//一趟增量为dlta[k]的Shell插入排序}//ShellSortvoidshellSort(listtp&r,intdk){for(i=dk+1;i=n;i++){r[0]=r[i];/*设置监视哨*/j=i-dk;k=r[i].key;while(r[j].keyk)/*大值的记录后移*/{r[j+dk]=r[j];j-=dk;}r[j+dk]=r[0];/*插入位置*/}}/*straisort*/冒泡排序：voidbuble_sort(listtpr){for(i=1;i=n-1;i++)/*共计n-1趟*/for(j=1;j=n-i;j++)if(r[j].keyr[j+1].key){x=r[j];r[j]=r[j+1]r[j+1]=x;}}/*bubble_sort*/快速排序：在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。privatestaticvoidqSort(sqlist&L,intlow,inthigh){if(lowhigh){//intpivotloc=partition(L,low,high);//以a[pivotloc]为基准元素将a[low:high]划分成3段a[low:pivotloc-1],a[pivotloc]和a[pivotloc+1:high]，使得a[low:pivotloc-1]中任何元素小于等于a[pivotloc]，a[pivotloc+1:high]中任何元素大于等于a[pivotloc]。下标pivotloc在划分过程中确定。qSort(L,low,pivotloc-1);//对左半段排序qSort(L,pivotloc+1,high);//对右半段排序}}IntPartition(sqlist&L,intlow,inthigh){L.r[0]=L.r[low];//用子表第一个元素作为轴Pivotkey=L.r[low].key;While(lowhigh){While(lowhigh&&L.r[high].key=privotkey)High--;If(L.r[high].keyprivotkey)R[low]=r[high];While(lowhigh&&L.r[low].key=privotkey)Low++;If(L.r[low].keyprivotkey)R[high]=r[low];}L.r[low]=L.r[0];Returnlow;}归并排序：publicstaticvoidmergeSort(Comparablea[],intleft,intright){intm=(left+right)/2;//取中点if(left=right)return;if(left+1==right){if(a[left]a[right])std::swap(a[left],a[right]);return;}mergeSort(a,left,m);mergeSort(a,m+1,right);merge(a,left,m,right);//合并到数组a}}voidMerge(A[],intl,intm,inth){inti=l;intj=m+1;intk=0;while(i=m&&j=h){if(A[i]A[j]){B[k++]=A[i];i++;}else{B[k++]=A[j];j++;}}while(i=m)B[k++]=A[i++];while(j=h)B[k++]=A[j++];for(i=l;i=h;i++)A[i]=B[i-l];}二分法：#includeiostream#defineN10usingnamespacestd;intmain(){inta[N],front,end,mid,x,i;cout请输入已排好序的a数组元素:endl;for(i=0;iN;i++)cina[i];cout请输入待查找的数x:endl;cinx;front=0;end=N-1;mid=(front+end)/2;while(front=end&&a[mid]!=x){if(a[mid]x)front=mid+1;if(a[mid]x)end=mid-1;mid=(front+end)/2;}if(a[mid]!=x)cout没找到！endl;elsecout找到了！在第mid+1项里。endl;return0;}二叉树递归、非递归遍历packageedu.cumt.jnotnull;importjava.util.Stack;publicclassBinaryTree{protectedNoderoot;publicBinaryTree(Noderoot){this.root=root;}publicNodegetRoot(){returnroot;}/**构造树*/publicstaticNodeinit(){Nodea=newNode('A');Nodeb=newNode('B',null,a);Nodec=newNode('C');Noded=newNode('D',b,c);Nodee=newNode('E');Nodef=newNode('F',e,null);Nodeg=newNode('G',null,f);Nodeh=newNode('H',d,g);returnh;//root}/**访问节点*/publicstaticvoidvisit(Nodep){System.out.print(p.getKey()+);}/**递归实现前序遍历*/protectedstaticvoidpreorder(Nodep){if(p!=null){visit(p);preorder(p.getLeft());preorder(p.getRight());}}/**递归实现中序遍历*/protectedstaticvoidinorder(Nodep){if(p!=null){inorder(p.getLeft());visit(p);inorder(p.getRight());}}/**递归实现后序遍历*/protectedstaticvoidpostorder(Nodep){if(p!=null){postorder(p.getLeft());postorder(p.getRight());visit(p);}}/**非递归实现前序遍历*/protectedstaticvoiditerativePreorder2(Nodep){StackNodestack=newStackNode();Nodenode=p;while(node!=null||stack.size()0){while(node!=null){//压入所有的左节点，压入前访问它visit(node);stack.push(node);node=node.getLeft();}if(stack.size()0){//node=stack.pop();node=node.getRight();}}}/**非递归实现后序遍历*/protectedstaticvoiditerativePostorder(Nodep){Nodeq=p;StackNodestack=newStackNode();while(p!=null){//左子树入栈for(;p.getLeft()!=null;p=p.getLeft())stack.push(p);//当前节点无右子或右子已经输出while(p!=null&&(p.getRight()==null||p.getRight()==q)){visit(p);q=p;//记录上一个已输出节点if(stack.empty())return;p=stack.pop();}//处理右子stack.push(p);p=p.getRight();}}/**非递归实现后序遍历双栈法*/protectedstaticvoiditerativePostorder2(Nodep){StackNodelstack=newStackNode();StackNoderstack=newStackNode();Nodenode=p,right;do{while(node!=null){right=node.getRight();lstack.push(node);rstack.push(right);node=node.getLeft();}node=lstack.pop();right=rstack.pop();if(right==null){visit(node);}else{lstack.push(node);rstack.push(null);}node=right;}while(lstack.size()0||rstack.size()0);}/**非递归实现后序遍历单栈法*/protectedstaticvoiditerativePostorder3(Nodep){StackNodestack=newStackNode();Nodenode=p,prev=p;while(node!=null||stack.size()0){while(node!=null){sta