程序員考試下午試題

1、程序員考試下午試題（模擬）Back *aveage (Node *head ) Back *p,*q;p= (Back * ) malloc (sizeof (Back);if (head=NULL ) p- num=0;p- ave=0; else (6);p- num二q- nu m+1;(7); retue n p;mai n() Node *h; Back *p;h=create(); /* 建立以h為頭指針的鏈表*/if (h=NULL) printf( 沒有元素);else p=aveage(h);printf(鏈表元素的均值為：6f,p- ave);四、希爾排序已知待排序序列da

2、tan;希爾排序的增量序列為dm，其中 d序列降序排列，且dm-1=1 。其方法是對(duì)序列進(jìn)行 m趟排序， 在第i趟排序中，按增量di把整個(gè)序列分成di個(gè)子序列，并按直 接插入排序的方法對(duì)每個(gè)子序列進(jìn)行排序。希爾排序的程序?yàn)椋簐oid shellsort(i nt *data,i nt *d,i nt n ,i nt m) int i,j;for (i=0;i i+)for (j=0;( 1)；j+)shell( ( 2)；void shell(i nt *data,i nt d,i nt nu m,i nt n) int i,j,k,temp;for (i=1;( 3);i+) j=0;tem

3、p=data j+i*d;while (j i) ( 4)j+;for (k=j;k k+) datak+1=datak;(5)(6) 五、求樹的寬度所謂寬度是指在二叉樹的各層上，具有結(jié)點(diǎn)數(shù)最多的那一層上 的結(jié)點(diǎn)總數(shù)。本算法是按層次遍歷二叉樹，采用一個(gè)隊(duì)列 q，讓根結(jié) 點(diǎn)入隊(duì)列，最后出隊(duì)列，若有左右子樹，則左右子樹根結(jié)點(diǎn)入隊(duì)列，如此反復(fù)，直到隊(duì)列為空。int Width(Bi nTree *T) int fron t=-1,rear=-1; /*int flag=0,count=0,p;/*pflag記錄層中結(jié)點(diǎn)數(shù)的最大值。if(T!二Null)隊(duì)列初始化*/用于指向樹中層的最右邊的結(jié)點(diǎn),*

4、/ rear+; (1); flag=1; p二rear;while( (2) fron t+;T=qfr on t;if(T- lchild!=Null) rear+; (3); coun t+; /if(T- rchild!=Null)(4); rear+; qrear=T- rchild;if(front=p)/*當(dāng)前層已遍歷完畢*/ if( (5) flag二co unt; coun t=0; /p=rear; /* p指向下一層最右邊的結(jié)點(diǎn)*/return(flag);六、區(qū)間覆蓋設(shè)在實(shí)數(shù)軸上有n個(gè)點(diǎn)(x0，x1，xn-2，xn-1 )，現(xiàn)在要求用長度為1的單位閉區(qū)間去覆蓋這n個(gè)點(diǎn)，

5、則需要多少個(gè)單位 閉區(qū)間。int cover(float x , i nt num) float start nu m,e ndnu m;int i ,j ,flag, coun t=0;for (i=0;i i+) flag=1;for (j=0;j( 1);j+) if (startj xi) (en dj-xi =1)( 2);else if ( 3) en dj=xi;else if (xi startj) (xi en dj) flag=0;if (flag) break;if （ （4） endcount=xi;（5） ; count+; retur n coun t-1;star

6、tco un t=xi七、圍棋中的提子在圍棋比賽中，某一方（假設(shè)為黑方）在棋盤的某個(gè)位置（i, j）下子后，有可能提取對(duì)方（白方的一串子）。以W1919表示一 個(gè)棋盤，若 Wij=0 表示在位置（i, j）上沒有子，Wij=1 表示 該位置上的是黑子，Wij=-1 表示該位置上是白子。可以用回溯法 實(shí)現(xiàn)提子算法。下列程序是黑棋（tag=1 ）下在（i，j）位置后判斷是否可以吃 掉某些白子，這些確定可以提掉的白子以一個(gè)線性表表示。問題相應(yīng)的數(shù)據(jù)結(jié)構(gòu)有：#define length 19 /*棋盤大小 */#define max_num 361 /*棋盤中點(diǎn)的數(shù)量*/struct positi o

7、n int row; int col; /*棋子位置*/struct killed struct positi on datamax_ nu m; int num; *p; /*存儲(chǔ)可以吃掉的棋子位置*/struct stack struct positi on no demax_ nu m; int top; /* 棧 */int wlengthlength; /*棋盤中雙方的棋子分布*/in t visitedle ngthle ngth; /*給已搜索到的棋子位置作標(biāo)記,初值為0,搜索到后為1*/struct killed *kill( int wle ngthle ngth,i nt

8、r,i nt c,i nt tag) struct killed *p;struct positi on *s;struct stack S;for (i=0;i le ngth;i+)for (j=0;j le ngth;j+)(1);S.top=-1; p- num=-1;if (wr-1c=tag*(-1) s- row=r-1; s- col=c;else if (wr+1c=tag*(-1) s- row=r+1; s- col=c;else if (wrc-1=tag*(-1) s- row=r; s- col=c-1;else if (wrc+1=tag*(-1) s- row=

9、r; s- col=c+1;else p- len=0; retur n p;push(S,s); visiteds- rows- col=1;flag=search(s,tag);while ( 2) push(S,s); visiteds- rows- col=1;while (S- top =0) Pop(S);(4)；flag二search(s,tag);while (flag) push(S,s);visit(s);flag二search(s);void push( struct stack *S, struct positi on *s) S- top+;S- no deS- to

10、p.row=s-S- no deS- top.col=s-p- nu m+;p- datap- nu m.row二s-p- datap- nu m.col二s- void pop(struct stack *S) S- top-;struct positi on *gettop(struct stack *S) struct positi on *s;s- row二S- dataS- top.row;s- row=S- dataS- top.row;return s;int search(struct positi on *s,i nt tag) int row,col;row=s- col=

11、s-if (Wrow+1col=(-1)*tag) (!visitedrow+1col) s- row=row+1;s- col=col; return 1;if (Wrow-1col=(-1)*tag) (!visitedrow-1col) s- row=row-1;s- col=col; return 1;if (Wrowcol+1=(-1)*tag) (!visitedrowcol+1) s- row=row;s- col=col+1; return 1;if (Wrowcol-1=(-1)*tag) (!visitedrowcol-1) s- row=row;s- col=col-1;

12、 return 1答案：(1 ) strlen(s)+strlen(t)( 2 ) position+strlen(t)( 3 )targeti=si-strle n( t)(4) return a (5) return f(a,b-a)(6) q=aveage(head- n ext) (7 ) p- ave=(head- data+q- ave*q- num )/p- num(1) j di (2) data,di,j,n (3 ) num+i*d n (4) data j+i*d temp (5 ) data j=temp(1) qrear=T (2) front p (3) qrear=T- lchi