今天上午逃掉了选修课，意外的找到了几道北航复试的上机题，特地拿来做一做。
感觉还是有些棘手，发现自己对C/C++十分不熟，尤其是文件的操作，在Google了一阵子之后才搞定之。要知道，考试的时候是没有Google可以用的。。
下面把题和我的解答贴上来。
2009年的复试上机题目：
1 给出立方根的逼近迭代方程 y(n+1) = y(n)*2/3 + x/(3*y(n)*y(n)),其中y0=x.求给定的x经过n次迭代后立方根的值
要求:double精度,保留小数点后面六位。(送分题)
输入:x n
输出:迭代n次后的立方根
sample
input: 3000000 28
output:144.224957
#include <stdio.h> void main() { int n; double x; scanf("%lf",&x); scanf("%d",&n); double y0=x; int i; double y; for(i=0;i<n;i++) { y=y0*2/3+x/(3*y0*y0); y0=y; } printf("%lf",y); } |
2 数组排序
输入一个数组的值,求出各个值从小到大排序后的次序。
输入:输入的第一个数为数组的长度,后面的数为数组中的值,以空格分割
输出:各输入的值按从小到大排列的次序。
sample
input:
4
-3 75 12 -3
output:
1 3 2 1
#include <iostream> using namespace std; struct Node { int data; int seq; Node *next; }; void printLinkList(Node *p) { while(p) { cout<<p->data<<" "; p=p->next; } } int main() { int n; int i,j; Node *head,*p,*t; cin>>n; Node **list=new Node* [n]; head=new Node();//头结点 head->next=NULL; t=head; for(i=0;i<n;i++)//读入数据 { p=new Node(); cin>>p->data; p->next=NULL; t->next=p; t=p; list[i]=t; } for(i=0;i<n-1;i++)//排序 { for(j=1;j<n-i;j++) { if(list[j-1]->data>list[j]->data) { Node *temp=list[j-1]; list[j-1]=list[j]; list[j]=temp; } } } int record; for(i=0;i<n;i++)//计算次序 { if(i==0) { list[i]->seq=1; } else if(list[i]->data==list[i-1]->data) { list[i]->seq=list[i-1]->seq; } else if(list[i]->data>list[i-1]->data) { list[i]->seq=list[i-1]->seq+1; } if(list[i]==head->next) { record=i; } } p=list[record]; while(p)//输出 { cout<<p->seq<<" "; p=p->next; } return 0; } |
3 字符串的查找删除
给定文件filein.txt 按要求输出fileout.txt。
输入: 无空格的字符串
输出: 将filein.txt删除输入的字符串(不区分大小写),输出至fileout.txt
sample
输入:in
输出:将filein.txt 中的In、IN、iN、in删除,每行中的空格全部提前至行首,输出至fileout.txt
filein.txt中的值为:
#include
int main()
{
printf(" Hi ");
}
输出的fileout.txt为
#clude
tma()
{
prtf("Hi");
}
#include <stdio.h> #include <string.h> #include <ctype.h> void del(char str[],int delPos,int len) { int n=strlen(str); int i; for(i=delPos;i<n-len;i++) { str[i]=str[i+len]; } str[i]='\0'; } bool find(char *s,char *t,int start) { int n=strlen(t)+start; for(int i=start;i<n;i++) { if(tolower(s[i])==tolower(t[i-start])) continue; else break; } if(i==n) return true; else return false; } void main() { char toDel[20]; scanf("%s",&toDel); unsigned nDel=strlen(toDel); FILE *fp1,*fp2; if ((fp1=fopen("filein.txt","r"))==NULL) { printf("cannot open file\n"); return; } fp2=fopen("fileout.txt","w"); char buff[50]; while(fgets(buff,50,fp1)>0) { int *pos=new int [strlen(buff)]; int *posType=new int [strlen(buff)]; unsigned int p=0; unsigned int i,k; unsigned int nSpace=0; for(i=0;i<strlen(buff);i++) { if(buff[i]==' ') { nSpace++; pos[p]=i; posType[p]=0; p++; } else if(find(buff,toDel,i)) { pos[p]=i; posType[p]=1; p++; } } unsigned hasdel=0; for(k=0;k<p;k++) { if(posType[k]==0) { del(buff,pos[k]-hasdel,1); hasdel++; } else { del(buff,pos[k]-hasdel,nDel); hasdel=hasdel+nDel; } } if(nSpace>0) { for(k=0;k<nSpace;k++) { fprintf(fp2,"%s"," "); } } fprintf(fp2,"%s",buff); } fclose(fp1); fclose(fp2); } |
关于第二题我得说明一下。个人感觉这个题需要一定的技巧。虽然思路很简单，但是用最笨的方法无疑很低效。因此我是这样处理的：
首先将原数据存在一个链表中，然后把链表各个节点的地址存在一个数组中，这样就把链式结构“转化”为顺序结构。然后根据节点的数值域(data)对这个一位数组进行从小到大的排序,根据递增的顺序很容易填充每个节点的次序域(seq)。这个数组标志着链表中各个节点的地址，注意这些节点的内容并没有变化，变化的只是他们在数组中的顺序。在数组中找到链表的第一个节点，根据其指针域就可依次找到后继节点，这样访问就比单纯的查询要高效。
大家应该还有比我这好的多的方法，欢迎指教。
