亞信校招筆試題目

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 TreeNode(30, tNod

2、e11, 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(TreeNod

3、e 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.valu

4、e;*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.righ

5、tNode = 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;/初始化高速緩存數(shù)組*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 !=

6、ai) continue;elsebreak;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;elseflag = false;for(n = i; n k - 1; n+)an = an+1;ak - 1 = pagesj;elsecount +;for(i = 0; i max_cache_size; i

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

8、 = 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-next;half = half-next;if(half)half = half-next;if(list)prev-next = reverse(li

9、st);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;els

10、eif(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 =

11、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#includeconst int N=10000, M=100000;

12、bool edgeNN; /數(shù)組記錄兩點(diǎn)是否存在邊bool visitN; /標(biāo)記該節(jié)點(diǎn)是否訪問過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;elseif (!DFS_check(i, x) return false;return true;int main()int n,m;scanf(%d%d,&n,&m);memset(edge,false,s

13、izeof(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);elseprintf(No!n);system(pause);return 0;6.老鼠奶酪#include using

14、 namespace std;int isPath(int *grid, int m, int n);struct _TraversedNodeint x;int y;_TraversedNode *next;struct _Nodeint 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;

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

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

17、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)TraversedNode;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+;cou

18、t可以最短step步到達(dá)終點(diǎn)x=nodei.x+1)&(p_check-y=nodei.y)p_check=NULL; flag_down_success=false;elsep_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

19、;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步到達(dá)終點(diǎn)x=nodei.x-1)&(p_check-y=nodei.y)p_check=NULL;flag_up_success=false;elsep_check=p_check-next;*if(flag_up_success)TraversedNode=new _Travers

20、edNode;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步到達(dá)終點(diǎn)x=no

21、dei.x)&(p_check-y=nodei.y+1) p_check=NULL;*flag_right_success=false;elsep_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_nod

22、e.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步到達(dá)終點(diǎn)x=nodei.x)&(p_check-y=nodei.y-1)p_check=NULL; flag_left_success=false;elsep_check=p_check-next; if(flag_left_success)TraversedNode=new _TraversedNode;Trav

23、ersedNode-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不存在到達(dá)終點(diǎn)的路徑endl;return 0;break;step+;num_node=count_node; count_node=0;for(int i=0;inum

24、_node;i+)*nodei.x=node_nexti.x;nodei.y=node_nexti.y;cout(nodei.x,nodei.y) coutendl;7格雷碼import java.util.Scanner;public static int gray(byte term1,byte term2)int n=0;for(int i=0;i1); term2=(byte)(term1);if(n=1)return 1;elsereturn0;*8.虻果 nN 主成的排列箱為-5*6*7*14*15*163*9*12*131血IrapeziumPattern 類的構(gòu)造方法為帕 gz

25、iumP 自 tt 亡 rn Ki0=n using n amespace std;void myPri nt(i nt n)if(1 = n)cout 1*2 e ndl; return;int last nu mber = n*( n+1);每一行最后一個(gè)數(shù)int first=1; 每一行第一個(gè)數(shù)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 -

26、step+1;cout num ;num+;for( l=0;l(n-i);l+)/每一行的后半部分cout *num;num+;cout n)myPrint(n);return 0;9短作業(yè)優(yōu)先調(diào)度算法(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, du

27、rations);System.out.println(averageWaitingTime);* param requestTimes任務(wù)提交時(shí)間* param durations任務(wù)服務(wù)時(shí)間* 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

28、.length;int durationTimes = copyArray(durations); /復(fù)制一份服務(wù)時(shí)間int startTimes = new intn; /開始時(shí)間int endTime = new intn; /結(jié)束時(shí)間int waitingTime = new intn; /等待時(shí)間int cycleTime = new intn; /周轉(zhuǎn)時(shí)間/第一個(gè)執(zhí)行任務(wù)的開始時(shí)間、結(jié)束時(shí)間、等待時(shí)間startTimes0 = requestTimes0;endTime0 = startTimes0 + durations0;waitingTime0 = 0;/*核心代碼*/int

29、lastIndex = 0; /上一次執(zhí)行任務(wù)的索引int minIndex = 0; /最短任務(wù)的索引for(int i = 1; i n; i+) minIndex = getMinIndex(durations); /作曲最短任務(wù)索引為當(dāng)前任務(wù)startTimesminIndex = endTimelastIndex; /當(dāng)前任務(wù)的開始時(shí)間為上一個(gè)任務(wù)的結(jié)束時(shí)間endTimeminIndex = startTimesminIndex + durationTimesminIndex; /結(jié)束時(shí)間=開始時(shí)間+服務(wù)時(shí)間waitingTimeminIndex = startTimesminInd

30、ex - requestTimesminIndex; /等待時(shí)間=開始時(shí)間-提交時(shí)間*cycleTimeminIndex = endTimeminIndex - requestTimesminIndex; /周轉(zhuǎn)時(shí)間結(jié)束時(shí)間-提交時(shí)間lastIndex = minIndex; /更新當(dāng)前任務(wù)索引為下一次循環(huán)中的 “上一次任務(wù)索 引”/計(jì)算平均等待時(shí)間int s = 0;for(int i : waitingTime)s += i;float averageTime = (float) s / (float) n; return averageTime;/獲取最短任務(wù)索引，獲取完成之后，該任務(wù)的

31、服務(wù)時(shí)間置為最大值，從下一次尋 找最短任務(wù)的過程中排除。public static int getMinIndex(int arr) if(arr = null)return -1;int minValue = Integer.MAX_VALUE; /最短任務(wù)值int minIndex = 0;for(int i = 1; i arr.length; i+) if(arri minValue) minValue = arri;minIndex = i;*arrminIndex = Integer.MAX_VALUE; /一次尋找最短任務(wù)的過程中排除。return minIndex; /返回索引

32、/復(fù)制一份數(shù)組public static int copyArray(int arr) if(arr = null)return null;int size = arr.length; int copyArr = new intsize;for(int i = 0; i size; i+) copyArri = arri;return copyArr;10.有序循環(huán)鏈表插入整數(shù)#include#include#define N 5 typedef struct node int data;struct node * next; SN;SN * creatlink ( int a )/tail即

33、所設(shè)置的尾指針，p即程序中遍歷整個(gè)鏈表的指針SN * tail = NULL, * p;int i;for ( i = 0; i data = ai;if ( !tail ) /當(dāng)tail為NULL是=時(shí)，表示當(dāng)前節(jié)點(diǎn)時(shí)所創(chuàng)建的第一個(gè)結(jié)點(diǎn)tail-next = tail = p;該任務(wù)的服務(wù)時(shí)間置為最大值，從下*else /直接將p結(jié)點(diǎn)插入在尾結(jié)點(diǎn)后成為新的尾結(jié)點(diǎn)即可。p-next = tail-next;tail = tail-next = p;return tail;void printlink ( SN * tail )SN * p = tail;printf();do printf (

34、 %d-, p-next-data ); p = p-next; while ( p != tail );printf ( An);SN * insertnode ( SN * tail, int n )/形參tail即尾指針，s即待插結(jié)點(diǎn)/設(shè)單向循環(huán)鏈表非空且數(shù)據(jù)域值升序有序，要求使得插入新結(jié)點(diǎn)之后，新鏈表依然 升序有序SN * p = tail;SN * s;s=(SN *)malloc(sizeof(SN);s-data=n;*do if ( p-next-data = s-data )break;elsep = p-next; while ( p != tail );if ( p =

35、tail & tail-next-data data ) /此時(shí)表明待插結(jié)點(diǎn)數(shù)據(jù)大于或等于當(dāng)前尾結(jié)點(diǎn)的值，所以插入后成為新的尾結(jié)點(diǎn)， 即需要挪尾指針tail = s;/接下來只需要進(jìn)行插入算法即可s-next = p-next;p-next = s;return tail;*int main ( void )SN * tail;int tmp;int aN = 3, 4, 6, 1, 2 ;/創(chuàng)建單向循環(huán)鏈表tail = creatlink ( a );/輸出單向循環(huán)鏈表printlink ( tail );scanf(%d,&tmp);insertnode ( tail, t

36、mp );printlink ( tail );return 0;4.3字符串格式化，去掉首尾的空格，以及字符串中間連續(xù)的空格，但 中間的只保留最后一個(gè)空格。比如：i love meitua n ,格式化后：ilove meitua n.我說一下我的思路：1.用string的substring方法很輕松去掉首尾的 空格。2，將去掉首尾空格的字符串轉(zhuǎn)化為一個(gè)字符數(shù)組，方便對(duì)空格的查找。3，將找到的空格的下標(biāo)記錄在一個(gè)arrayList（長度可變的優(yōu)點(diǎn)等）中去。4，將第1步驟得到的字符串進(jìn)行切割，最后一個(gè)空格前的字符串作為 前綴字符串將（包括最后一個(gè)空格的下標(biāo)）從最后一個(gè)下標(biāo)開始到字符串結(jié) 尾作為后綴字符串。5將前綴字符串中的所有的空格使用replaceAll方法替換為沒有6將5步驟得到的字符串與后綴字符串進(jìn)行拼接。那么就得到了想要 的字符串。代碼實(shí)現(xiàn)如下；java view plai n copy1.package test;2.4.3. import java.util.ArrayList;*public class Solution pub