12届计算机科学技术专业技能模拟考核.doc

2011年计算机科学技术专业技能模拟考核题目一、要求：1、 考生在VC6.0编程环境下，完成各题函数的编写，并调试、编译、运行程序。2、 考生不能修改源程序文件名，也不能修改其扩展名，否则不得分。3、 考生只能在/*与/=之间编写程序。若修改源程序的其它部分，会得0分。4、 考核过程中，考生不能自行启动电脑，如果遇到死机需要重新启动，举手由老师帮助解决。5、 输出数据中的空格个数必须完全精确。6、 考核前考生必须认真阅读数据结构专业技能考核“须知”。二、专业技能考核题目（8题，共700.3分）0.测试环境(本题0.3分)(sum.cpp)完成源程序SUM.CPP中sum函数的编写： int sum( int a, int b) /* / 写入 return a+b; /=如果得0.3分表示环境正常，可以开始考核。int main()int a, b;freopen(sum.in, r, stdin);freopen(sum.out , w, stdout);scanf(%d%d, &a, &b);printf(%dn, sum(a,b);return 0;1. 最短距离（本题100分）(dist.cpp/c)【问题描述】开车从起始点到目的地的路线有多条。给你一张描述待选路线的表（n*n的矩阵A），让你找出行车距离最短的路线。表中表示了任意两个路口的连通情况，以及距离。矩阵元素a(i,j)=0表示路口i,j不连通，a(i,j)!=0表示路口i,j的行车距离。其中起始点在路口1，目的地在路口n 。完成源程序DIST.CPP中Dijkstra函数的编写。【输入】输入文件dist.in的第一行为一个自然数n(1n=30);接着n行，每行n个整数，描述待选路线的表（元素的值小于1000）；【输出】输出文件dist.out包括一行，为一个整数，表示起始点到目的地的最短行车的距离。 【输入输出样例1】dist.indist.out40 2 3 42 0 1 13 1 0 04 1 0 03【输入输出样例2】dist.indist.out60 1 3 4 9 01 0 2 1 3 03 2 0 0 4 8 4 1 0 0 3 79 3 4 3 0 40 0 8 7 4 08【数据规模】对于30%的数据， n=10;对于70%的数据， n=20;对于100%的数据，n=30。 #include stdio.h#define maxint 10000int n,used31,map3131;void ini( )int i,j;scanf(%d, &n);for( i=1; i=n; i+)for( j=1; j=n; j+) scanf(%d, &mapij);if( mapij =0 ) mapij=maxint;void Dijkstra() int dis31; int i,j,k, tmin;for( i=1;i=n;i+) disi = map1i; for( i=1;in;i+) tmin = maxint; for(j=1;j disj ) tmin = disj; k = j; usedk = 1; for( j=1;j=n;j+) if( disk + mapkj disj ) disj = disk + mapkj; printf(%dn,disn);int main()freopen(dist.in, r, stdin); freopen(dist.out, w, stdout);ini();Dijkstra();return 0;2. 路径回溯（本题100分）(DictS.cpp)【问题描述】已知从起始点到达各目站点（、C、D.）的各最短路径上所有站点的前驱站点，以及至前驱站点的距离。以一个二维数组pre描述已知信息，第1列是前驱站点的序号（以0、1、2.分别表示站点A、B、C.），第2列是至前驱站点的距离。试推算和输出从起始点出发到达各其余站点的最短路径和距离。完成源程序DictS.CPP中Pathway函数的编写。【输入】输入文件DictS.in的第1行为1个自然数n(1n=26，表示包括起始点在内的站点总数)；后续n行，每行2个整数，分别描述站点A、B、C.的前驱站点和至前驱站点的距离。【输出】输出文件DictS.out包含n-1行，每行2个部分，前部为最短路径，后部为距离。格式见输出样例。 【输入输出样例1】DictS.inDictS.out90 00 400 204 100 302 253 102 406 20A-B 40A-C 20A-E-D 40A-E 30A-C-F 45A-E-D-G 50A-C-H 60A-E-D-G-I 70【输入输出样例2】DictS.inDictS.out50 02 750 1350 330 123A-C-B 210A-C 135A-D 33A-E 123#include stdio.hint n, pre262;char station26=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z;void ini() int i; scanf(%d, &n); for(i=0; in; i+) scanf(%d%d, &prei0, &prei1);void Pathway() char stack26; int dist; int i, j, top=-1; for(i=1; i=0) printf(%c, stacktop-); if(top=0) printf(-); printf( %dn, dist); int main() freopen(DictS.in, r, stdin); freopen(DictS.out, w, stdout); ini(); Pathway(); fclose(stdin); fclose(stdout); return 0;3. 有限自动机（本题100分）(dfa.cpp/c)【问题描述】设有如下确定的状态转换图，0为起始状态，3，4为终结状态。编写程序，判断用户输入的符号串，是否被该有限自动机接受。【输入】输入文件dfa.in为一行字符串（字符个数小于1000）；【输出】输出文件dfa.out包括一行，为一个整数，表示输入的符号串是否被该有限自动机接受，若接受，则输出0，否则输出首次出错字符所在的位置（注：输入串首字符的位置为1）。 学生只要编写函数int dfachk(char str)，该函数的参数str为输入串，若输入串str被该有限自动机接受，则函数返回值为0。若输入串str在第n个字符处首次出错，则函数返回值为n。【输入输出样例1】dfa.indfa.outaa3【输入输出样例2】dfa.indfa.outabbaaa0【输入输出样例3】dfa.indfa.outababaaab4【输入输出样例4】dfa.indfa.outabaacaab5【数据规模】输入的字符串长度L=0) switch (stri) case a: k=0; break; case b: k=1; break; default : s=-1; if (s=0) s=ask; i+; if (s0) return i; if (s3) return i+1; return 0;main() char insmax=0; freopen(dfa.in, r, stdin); freopen(dfa.out, w, stdout); gets(ins); printf(%d,dfachk(ins);4.数据库查询（本题100分）(DB.c)【问题描述】Student数据库里面有个Grade表，该表里面存储了每个学生的学号，姓名，maths成绩，english成绩和computer成绩。现要查询Grade表，显示三门课都及格的学生学号、姓名、maths、english、computer字段，并按照学号升序排列。完成源程序DB.C中select2函数的编写。【输入】输入文件DB.in的第一行为一个自然数n(1n=100);接着n行，每行代表一个学生的记录（学号 姓名 maths成绩 english成绩 computer成绩），其中0=成绩=100，每个字段之间用空格间隔开。【输出】输出文件DB.out包括x行，每行代表一个学生的记录，显示字段为：学号、姓名、maths成绩、english成绩、computer成绩。每个字段之间用逗号间隔开【输入输出样例1】DB.inDB.out4101 Zhangsan 56 47 89102 Kate 89 60 78104 Jay 52 89 90107 Wangwu 68 78 67102,Kate,89,60,78107,Wangwu,68,78,67【输入输出样例2】DB.inDB.out10145 Anm 44 86 76123 Bob 98 66 86246 Bay 96 95 93286 Bekt 56 86 23281 Eho 86 84 75301 Dawy 65 63 64324 Deuwu 78 65 56 320 Dyosn 23 14 65 411 Eio 76 31 81450 Erobt 13 23 47123,Bob,98,66,86246,Bay,96,95,93281,Eho,86,84,75301,Dawy,65,63,64#include #include #define SIZE 100int n;struct Grade_table int no_stu; /* the number of student*/ char name20; /* the name of student*/ int maths; int english; int computer;struct Grade_table gradeSIZE;void ini( ) int i; scanf(%d,&n); for(i=0;in;i+) scanf(%d %s %d %d %d,&(gradei.no_stu),,&(gradei.maths),&(gradei.english),&(puter); void select2() int i,j,t; int aSIZE; int k=0; for(i=0;i=60&gradei.english=60&puter=60) ak=i;k=k+1; for(i=0;ik;i+) for(j=i+1;jgradeaj.no_stu) t=ai;ai=aj;aj=t; for(i=0;ik;i+) printf(%d,%s,%d,%d,%dn,gradeai.no_stu,,gradeai.maths,gradeai.english,puter); int main() freopen(DB.in, r, stdin); freopen(DB.out, w, stdout); ini(); select2(); return 0;5.图像平滑线性滤波器（本题100分）(image.cpp)【问题描述】利用加权平均掩模实现数字图像的平滑（图像边缘不予处理）；加权平均掩模如下图。完成源程序image.cpp中Smooth_Filter函数的编写。【输入】输入文件image.in的第一行为一个自然数n(1=n=300);接着n行，每行n个整数，描述nn像素图像（元素的值介于0255之间）；【输出】输出文件 image.out为n-2行，每行n-2个整数，表示滤波后n-2n-2像素图像。 【输入输出样例1】image.inimage.out40 2 3 42 0 1 13 1 0 04 1 0 01 11 0【输入输出样例2】image.inimage.out61 1 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 11 1 1 11 1 1 11 1 1 1【数据规模】对于30%的数据， n=100;对于70%的数据， n=200;对于100%的数据，n=300。#include stdio.h#define MAX_INT 300int n,mapMAX_INTMAX_INT,outMAX_INTMAX_INT;void ini( )int i,j;for( i=0; iMAX_INT; i+)for( j=0; jMAX_INT; j+) mapij=0;outij=0;scanf(%d, &n);for( i=0; in; i+)for( j=0; jn; j+) scanf(%d, &mapij);void Smooth_Filter()int i,j;for( i=1;in-1;i+)for(j=1;jn-1;j+)outij=(mapi-1j-1+2*mapi-1j+mapi-1j+1+2*mapij-1+4*mapij+2*mapij+1+mapi+1j-1+2*mapi+1j+mapi+1j+1)/16;if(j!=n-2)printf(%d ,outij);elseprintf(%dn,outij);int main()freopen(image.in, r, stdin); freopen(image.out, w, stdout);ini();Smooth_Filter();return 0;6.模拟进程调度算法（本题100分）(os.cpp)【问题描述】进程调度算法FCFS+SJF模拟。编写FCFS+SJF算法，输入一组若干个进程的调度信息，输出根据先来先服务和短进程优先算法的调度结果。（提示：短进程优先算法仅在进程的到达时间一样时，才启用）。完成源程序os.cpp中fcfs_sjf函数的编写。提醒：每个输出数据之前输出1个t。【输入】输入文件os.in中，第一行数字表示作业或进程总数，如4个作业输入4。第二行开始每行输入1个进程的调度信息，包括进程作业号、进程到达时间和进程估计运行时间。【输出】输出文件os.out将得到所输入的进程信息和调度结果的输出。 【输入输出样例1】os.inos.out41 0 702 0 203 0 404 0 5输入作业顺序:107020203040405FCFSsjf调度结果: 开始时间 作业号 到达时间 运行时间 完成时间 等待时间 周转时间0405505520202552525304065256565107013565135【输入输出样例2】os.inos.out51 0 702 0 203 10 404 20 55 0 10输入作业顺序:107020203104042055010FCFSsjf调度结果: 开始时间 作业号 到达时间 运行时间 完成时间 等待时间 周转时间05010100101020203010303010701003010010031040140901301404205145120125【数据规模】对于30%的数据， n=10;对于70%的数据， n=20;对于100%的数据，n=30。#include #include struct Job_type int no; /作业号 int tb; /作业开始时间（分） int tr; /运行时间（分） x;Job_type job36;int n;void load() int i,j; scanf(%d, &n); for( i=0; in; i+)scanf(%d, &jobi.no); scanf(%d, &jobi.tb); scanf(%d, &jobi.tr); printf(输入作业顺序:n); for(i=0;in;i+) printf(t%dt%dt%dn,jobi.no,jobi.tb,jobi.tr);void fcfs_sjf() int i,j,t=0,tw=0,tt=0; for(i=0;in-1;i+) for(j=i+1;jjobj.tb) x=jobi; jobi=jobj; jobj=x; else if (jobi.tb = jobj.tb & jobi.tr jobj.tr)x = jobi;jobi = jobj;jobj = x; printf(FCFSsjf调度结果:n); printf( 开始时间 作业号 到达时间 运行时间 完成时间 等待时间 周转时间n);for(i=0;in;i+) printf(t%d,t); t=t+jobi.tr; tw=t-jobi.tb-jobi.tr; /作业等待时间 tt=t-jobi.tb; /周转时间printf(t%dt%dt%dt%dt%dt%dn,jobi.no,jobi.tb,jobi.tr,t,tw,tt)