亚信校招笔试题目.doc

1.BSTpublic class BSTMinLength public static void main(String args) TreeNode tNode11 = new TreeNode(10, null, null); TreeNode tNode12 = new TreeNode(50, null, null); TreeNode tNode13 = new TreeNode(5, null, null); TreeNode tNode14 = new TreeNode(30, null, null); TreeNode tNode21 = new TreeNode(30, tNode11, tNode12); TreeNode tNode22 = new TreeNode(30, tNode13, tNode14); TreeNode tNodeRoot = new TreeNode(100, tNode21, tNode22); System.out.println(minlength(tNodeRoot); private static int minlength(TreeNode tNode) if (tNode != null) return getlength(tNode,0); return -1; private static int getlength(TreeNode tNode,int curLength) int minLeft=-1; int minRight=-1; if (tNode.leftNode!=null) minLeft=getlength(tNode.leftNode, curLength+tNode.value); if (tNode.rightNode!=null) minRight=getlength(tNode.rightNode, curLength+tNode.value); if (tNode.leftNode=null & tNode.rightNode=null) return curLength+tNode.value; if (tNode.leftNode=null) return minRight; if (tNode.rightNode=null) return minLeft; return minLeftminRight? minRight:minLeft; class TreeNode int value; TreeNode leftNode; TreeNode rightNode; TreeNode(int value, TreeNode lefeNode, TreeNode rightNode) this.value = value; this.leftNode = lefeNode; this.rightNode = rightNode; 2.lru#include using namespace std; int lruCountMiss(int max_cache_size, int *pages, int len) int count = 0; int i,j,k,n; bool flag = false; int *a = new intmax_cache_size; /初始化高速缓存数组 for(i = 0; i max_cache_size; i+) ai = -1; for(j= 0; j len; j+) for(i = 0; i max_cache_size; i+) if(pagesj != ai) continue; else break; if(i != max_cache_size) for(k = i; k max_cache_size; k+) if(ak = -1) flag = true; break; if(!flag) for(n = i; n max_cache_size - 1; n+) an = an+1; amax_cache_size - 1 = pagesj; else flag = false; for(n = i; n k - 1; n+) an = an+1; ak - 1 = pagesj; else count +; for(i = 0; i max_cache_size; i+) if(ai = -1) ai = pagesj; flag = true; break; if(!flag) for(i = 0; i max_cache_size-1; i+) ai = ai+ 1; amax_cache_size - 1 = pagesj; else flag = false; return count; int main() int arr = 7, 0, 1, 2, 0, 3, 0, 4; cout lruCountMiss(3, arr, 8) next;curr-next = prev;while(next != NULL)prev = curr;curr = next;next = next-next;curr-next = prev;return curr;elsereturn head;lnode *reverseLinkedList(lnode *list) if(list) lnode *ori = list; lnode *half = list; lnode *prev = list; while(list & half & half-next) prev = list; list = list-next; half = half-next; if(half) half = half-next; if(list) prev-next = reverse(list); return ori; return list;4. SJFfloat waitingTimeSJF(int * requestTimes, int * durations,int n) int *flags = new intn; float sums = 0; for(int i = 0 ;i n; i+) flagsi = -1; int nowtime = 0; for( int i = 0; i n; i+ ) int count = 0; for(int k = 0; k n;k+) if(count = 0) if(requestTimesk =0 ) flagscount+ = k; else if(durationsk =0 & requestTimesk = nowtime ) if( durationsk durationsflags0) count = 1; flags0 = k; else if( durationsk = durationsflags0 ) flagscount+ = k; if(count = 0) count = 1; for(int j = 0; j=0 ) flags0 = j; nowtime = requestTimesj; int idx = flags0; int minreq = requestTimes flags0 ; int mindrus = durationsidx; if(count 1) for(int j = 1; j count ;j+) if(requestTimesflagsj minreq ) minreq =requestTimesflagsj; idx = flagsj; sums += nowtime - requestTimesidx; nowtime += durationsidx; requestTimesidx = -1; durationsidx = -1; return sums/n;5 无向连通判断是否为树#include#include#include const int N=10000, M=100000;bool edgeNN; / 数组记录两点是否存在边bool visitN; / 标记该节点是否访问过 bool DFS_check(int x, int y=-1) if (visitx) return false; visitx = true; int i; for (i=0;iN;i+) if (edgexi & i!=y) if (visiti) return false; else if (!DFS_check(i, x) return false; return true; int main() int n,m; scanf(%d%d,&n,&m); memset(edge,false,sizeof(edge); int i,x,y; for (i=0;im;i+) scanf(%d%d,&x,&y); edgex-1y-1 = true; edgey-1x-1 = true; memset(visit,false,sizeof(visit); bool result = DFS_check(0); if (result) for (i=0;in;i+) if (!visiti) result = false; if (result) printf(Yes!n); else printf(No!n); system(pause); return 0;6. 老鼠奶酪#include using namespace std;int isPath(int *grid, int m, int n);struct _TraversedNode int x; int y; _TraversedNode *next;struct _Node int x; int y;int main(int argc, const char * argv) int *grid= new int*8; for(int i=0;i8;i+) gridi= new int8; grid00=1; grid01=1; grid02=0; grid03=0; grid04=0; grid05=0; grid06=0; grid07=1; grid10=1; grid11=1; grid12=1; grid13=1; grid14=1; grid15=1; grid16=1; grid17=1; grid20=1; grid21=0; grid22=0; grid23=0; grid24=1; grid25=0; grid26=0; grid27=1; grid30=1; grid31=1; grid32=1; grid33=0; grid34=1; grid35=0; grid36=0; grid37=1; grid40=0; grid41=1; grid42=0; grid43=0; grid44=1; grid45=1; grid46=1; grid47=1; grid50=0; grid51=1; grid52=0; grid53=0; grid54=0; grid55=0; grid56=0; grid57=1; grid60=0; grid61=1; grid62=0; grid63=9; grid64=1; grid65=1; grid66=1; grid67=1; grid70=0; grid71=1; grid72=1; grid73=1; grid74=0; grid75=0; grid76=1; grid77=0; for(int i=0;i8;i+) for(int j=0;j8;j+) coutgridij ; coutx=0; TraversedNode-y=0; head=TraversedNode; p=TraversedNode; p-next=NULL; int count_node=0; int num_node=1; _Node *node=new _Noden+m; _Node *node_next=new _Noden+m; node0.x=0; node0.y=0; while(1) for(int i=0;inum_node;i+) if(nodei.x+1=m-1) if(gridnodei.x+1nodei.y!=0) if(gridnodei.x+1nodei.y=9) step+; cout可以最短step步到达终点x=nodei.x+1)&(p_check-y=nodei.y) p_check=NULL; flag_down_success=false; else p_check=p_check-next; if(flag_down_success) TraversedNode=new _TraversedNode; TraversedNode-x=nodei.x+1; TraversedNode-y=nodei.y; p-next=TraversedNode; p=TraversedNode; p-next=NULL; node_nextcount_node.x=nodei.x+1; node_nextcount_node.y=nodei.y; count_node+; flag_down_success=true; if(nodei.x-1=0) if(gridnodei.x-1nodei.y!=0) if(gridnodei.x-1nodei.y=9) step+; cout可以最短step步到达终点x=nodei.x-1)&(p_check-y=nodei.y) p_check=NULL; flag_up_success=false; else p_check=p_check-next; if(flag_up_success) TraversedNode=new _TraversedNode; TraversedNode-x=nodei.x-1; TraversedNode-y=nodei.y; p-next=TraversedNode; p=TraversedNode; p-next=NULL; node_nextcount_node.x=nodei.x-1; node_nextcount_node.y=nodei.y; count_node+; flag_up_success=true; if(nodei.y+1=n-1) if(gridnodei.xnodei.y+1!=0) if(gridnodei.xnodei.y+1=9) step+; cout可以最短step步到达终点x=nodei.x)&(p_check-y=nodei.y+1) p_check=NULL; flag_right_success=false; else p_check=p_check-next; if(flag_right_success) TraversedNode=new _TraversedNode; TraversedNode-x=nodei.x; TraversedNode-y=nodei.y+1; p-next=TraversedNode; p=TraversedNode; p-next=NULL; node_nextcount_node.x=nodei.x; node_nextcount_node.y=nodei.y+1; count_node+; flag_right_success=true; if(nodei.y-1=0) if(gridnodei.xnodei.y-1!=0) if(gridnodei.xnodei.y-1=9) step+; cout可以最短step步到达终点x=nodei.x)&(p_check-y=nodei.y-1) p_check=NULL; flag_left_success=false; else p_check=p_check-next; if(flag_left_success) TraversedNode=new _TraversedNode; TraversedNode-x=nodei.x; TraversedNode-y=nodei.y-1; p-next=TraversedNode; p=TraversedNode; p-next=NULL; node_nextcount_node.x=nodei.x; node_nextcount_node.y=nodei.y-1; count_node+; flag_left_success=true; if(count_node=0) cout不存在到达终点的路径endl; return 0; break; step+; num_node=count_node; count_node=0; for(int i=0;inum_node;i+) nodei.x=node_nexti.x; nodei.y=node_nexti.y; cout(nodei.x,nodei.y) ; coutendl; 7格雷码importjava.util.Scanner;publicstaticintgray(byteterm1,byteterm2)intn=0;for(inti=0;i1);term2=(byte)(term1);if(n=1)return1;elsereturn0;8. #include using namespace std;void myPrint(int n)if(1 = n)cout 1*2 endl;return;int lastnumber = n*(n+1);/每一行最后一个数int first=1;/每一行第一个数int num=1;int step=n;for(int i=1;i=n;i+)for(int j=1;ji;j+)/输出-cout-;num = first;for(int l=0;l(n-i+1);l+)/每一行的前半部分cout num *;num+;num = lastnumber - step+1;cout num ;num+;for( l=0;l(n-i);l+)/每一行的后半部分cout *num;num+;cout n)myPrint(n);return 0;9短作业优先调度算法（SJF）public class ShortJobFirst public static void main(String args) int requestTimes = 0, 2, 4, 5; int durations = 7, 4, 1, 4; float averageWaitingTime = ShortJobFirst.minWaitingTime(requestTimes, durations); System.out.println(averageWaitingTime); /* * * param requestTimes 任务提交时间 * param durations 任务服务时间 * return */ public static float minWaitingTime(int requestTimes, int durations) if(requestTimes = null | durations = null) return -1; if(requestTimes.length != durations.length) return -1; int n = requestTimes.length; int durationTimes = copyArray(durations); / 复制一份服务时间 int startTimes = new intn; / 开始时间 int endTime = new intn; / 结束时间 int waitingTime = new intn; / 等待时间 int cycleTime = new intn; / 周转时间 / 第一个执行任务的开始时间、结束时间、等待时间 startTimes0 = requestTimes0; endTime0 = startTimes0 + durations0; waitingTime0 = 0; /* 核心代码 */ int lastIndex = 0; / 上一次执行任务的索引 int minIndex = 0; / 最短任务的索引 for(int i = 1; i n; i