亚信校招笔试题目.docx

1、亚信校招笔试题目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 TreeNo

2、de(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

3、 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

4、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.le

5、ftNode = 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 =

6、 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 -

7、 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) n

8、ext; curr-next = prev; while(next != NULL) prev = curr; curr = next; next = next-next; curr-next = prev; return curr; else return 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-n

9、ext; 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+ ) i

10、nt 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 ) fl

11、ags0 = 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; requestTime

12、sidx = -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

13、; 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+)

14、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 *gri

15、d= 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;

16、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;

17、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

18、_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=n

19、ew _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+

20、; 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=node

21、i.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) Travers

22、edNode=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;