2010年下半年初级软考辅导:程序员数据结构笔记（六） _计算机_软件水平考试_复习指导

第六天
　　快考试了，老师没有多说什么，他只是给我们讲了讲近三年试题情况，并详细讲述了两道题目：一道递归，另一道回溯。不过今天不知怎么回事，我感觉特别累，也特别想睡觉。所以没什么感觉。这里就不说了，两道题目都有的，递归那题是2001年最后一题，回溯是在《程序员教程》P416，老师说高程曾经考过，有兴趣自己看看也能看懂的。老师特意为我们出了一份下午试题，我现在把他拿出来让大家参考参考。到这里，就到这里！
　　程序员考试下午试题（模拟）
　　一、把一个字符串插入到另一个字符串的某个位置（指元素个数）之后
　　charinsert
　　}
　　}
　　returngarget;
　　}
　　二、辗转相除法求两个正整数的最大公约数
　　intf
　　}
　　三、求一个链表的所有元素的平均值
　　typedefstructBack;
　　typedefstructnodeNode;
　　Backaveage（Nodehead）
　　else
　　retuenp;
　　}
　　main
　　}
　　四、希尔排序
　　已知待排序序列data[n]；希尔排序的增量序列为d[m]，其中d序列降序排列，且d[m-1]=1。其方法是对序列进行m趟排序，在第i趟排序中，按增量d[i]把整个序列分成d[i]个子序列，并按直接插入排序的方法对每个子序列进行排序。
　　希尔排序的程序为：
　　voidshellsort
　　voidshell
　　}
　　五、求树的宽度
　　所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。本算法是按层次遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。
　　intWidth
　　while
　　//
　　if
　　if/当前层已遍历完毕/
　　}
　　return;
　　}
　　六、区间覆盖
　　设在实数轴上有n个点（x0，x1，……，xn-2，xn-1），现在要求用长度为1的单位闭区间去覆盖这n个点，则需要多少个单位闭区间。
　　intcover
　　if
　　}
　　returncount-1;
　　}
　　start[count]=x[i]
　　七、围棋中的提子
　　在围棋比赛中，某一方（假设为黑方）在棋盘的某个位置（i，j）下子后，有可能提取对方（白方的一串子）。以W[19][19]表示一个棋盘，若W[i][j]=0表示在位置（i，j）上没有子，W[i][j]=1表示该位置上的是黑子，W[i][j]=-1表示该位置上是白子。可以用回溯法实现提子算法。
　　下列程序是黑棋（tag=1）下在（i，j）位置后判断是否可以吃掉某些白子，这些确定可以提掉的白子以一个线性表表示。
　　问题相应的数据结构有：
　　#definelength19/棋盘大小/
　　#definemax_num361/棋盘中点的数量/
　　structposition;/棋子位置/
　　structkilledp;/存储可以吃掉的棋子位置/
　　structstack;/栈/
　　intw[length][length];/棋盘中双方的棋子分布/
　　intvisited[length][length];/给已搜索到的棋子位置作标记，初值为0，搜索到后为1/
　　structkilledkill
　　while
　　}
　　}
　　voidpush
　　voidpop
　　structpositiongettop
　　intsearch
　　iftag)&&
　　iftag)&&
　　iftag)&&
　　（5）;
　　}
　　答案：
　　（1）strlen+strlen（2）position+strlen（3）target[i]=s[i-strlen]
　　（4）returna（5）returnf
　　（6）q=aveage（7）p->ave=/p->num
　　（1）j<d[i]（2）data，d[i]，j，n（3）num+id<n（4）data[j+id]<temp（5）data[j]=temp
　　（1）q[rear]=T（2）front<p（3）q[rear]=T->lchild（4）count++（5）flag<count
　　（1）count（2）&&（3）start[j]=x[i]（4）!flag（5）
　　（1）visited[i][j]=0（2）flag（3）flag=search（4）s=gettop（5）return0