计算机科学技术专业技能模拟考核

1、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函数的编写。#include stdio.h#define maxint 10000int n,used31,map3131;void ini( )int i,j;scanf(%d, &n);for( i=1;

2、i=n; i+)for( j=1; j=n; j+) scanf(%d, &mapij);if( mapij =0 ) mapij=maxint;void Dijkstra()int dist100;int i, j;/初始for (i = 1; i = n; i+)disti = map1i;usedi = 0;used1 = 1;for (i = 1; i n; i+)/选择最短int mind = maxint, k = -1;for (j = 1; j = n; j+)if (!usedj & distj mind)mind = distj;k = j;if (k 0)break;us

3、edk = 1;/路径扩展for (j = 1; j = n; j+)if (!usedj & mapkj maxint & distk + mapkj distj)distj = distk + mapkj;printf(%dn, distn);int main()freopen(dist.in, r, stdin);freopen(dist.out, w, stdout);ini();Dijkstra();return 0;【输入】输入文件dist.in的第一行为一个自然数n(1n=30);接着n行，每行n个整数，描述待选路线的表（元素的值小于1000）；【输出】输出文件dist.out包

4、括一行，为一个整数，表示起始点到目的地的最短行车的距离。 【输入输出样例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 082. 路径回溯（本题100分）(DictS.cpp)【问题描述】已知从起始点到达各目站点（、C、D.）的各最短路径上所有站点的前驱站点，以及至前驱站点的距离。以一个二维数组pre描述已知信息，第1列是前驱站点的序号（以0、1、2.分别表示站点A、B

5、、C.），第2列是至前驱站点的距离。试推算和输出从起始点出发到达各其余站点的最短路径和距离。完成源程序DictS.CPP中Pathway函数的编写。#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()/*int i, j, sum = 0;int st100, top;for (

6、i = 1; i = 0; j-)printf(%c-, stationstj);printf(%c, stationi);printf( %dn, sum);/=int main() freopen(DictS.in, r, stdin);freopen(DictS.out, w, stdout);ini();Pathway();fclose(stdin);fclose(stdout);return 0;【输入】输入文件DictS.in的第1行为1个自然数n(1n=26，表示包括起始点在内的站点总数)；后续n行，每行2个整数，分别描述站点A、B、C.的前驱站点和至前驱站点的距离。【输出】输出

7、文件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 1233. 有限自动机（本题100分）(dfa.cpp/c)【问题描述】设有如下确定的状态转换图，0为起始

8、状态，3，4为终结状态。编写程序，判断用户输入的符号串，是否被该有限自动机接受。#include stdio.h#define max 1000int dfachk(char str) /*int i, j, f105;int s = 0;for (i = 0; i 10; i+)for (j = 0; j 5; j+)fij = -1;/根据表转换: fij = k, 代表 从状态i, 输入字符j, (j : 0代表a, 1 :代表b)，转移到状态kf00 = 0;f01 = 1;f10 = 2;f20 = 1;f11 = 3;f31 = 3;f30 = 4;f40 = 3;/一遍循环字符串

9、,头到尾for (i = 0; stri; i+)if (stri != a & stri != b)return i + 1;/非a非bs = fsstri - a;if (s 0)return i + 1;/无路可走if (s != 3 & s != 4)return i + 1;/非法结束return 0;/=void main() char insmax=0;freopen(dfa.in, r, stdin);freopen(dfa.out, w, stdout); gets(ins);printf(%d,dfachk(ins);【输入】输入文件dfa.in为一行字符串（字符个数小于1

10、000）；【输出】输出文件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.outabaa

11、caab5【数据规模】输入的字符串长度L10004.数据库查询（本题100分）(DB.c)【问题描述】Student数据库里面有个Grade表，该表里面存储了每个学生的学号，姓名，maths成绩，english成绩和computer成绩。现要查询Grade表，显示三门课都及格的学生学号、姓名、maths、english、computer字段，并按照学号升序排列。完成源程序DB.C中select2函数的编写。#include #define SIZE 100int n;struct Grade_tableint no_stu; /* the number of student*/char nam

12、e20; /* the name of student*/int maths;int english;int computer;struct Grade_table gradeSIZE;void ini( )int i, j = 0;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 rankSIZE, tot = 0;int i, j, k;fo

13、r (i = 0; i = 60 & gradei.english = 60 & puter = 60)/存下标ranktot+ = i;/选择排序，只对下标排序，比较简单for (i = 0; i tot; i+) k = i;for (j = i + 1; j tot; j+)if (graderankj.no_stu graderankk.no_stu)/记录最小k = j;if (k != i)/最小学号的下标k与i交换Grade_table tmp = graderankk;graderankk = graderanki;graderanki = tmp;for

14、(i = 0; i j; i+)printf(%d,%s,%d,%d,%dn, graderanki.no_stu, , graderanki.maths, graderanki.english, puter);/= int main()freopen(DB.in, r, stdin);freopen(DB.out, w, stdout);ini();select2();return 0;【输入】输入文件DB.in的第一行为一个自然数n(1n=100);接着n行，每行代表一个学生的记录（学号 姓名 maths成绩 english成绩 c

15、omputer成绩），其中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

16、 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,645.图像平滑线性滤波器（本题100分）(image.cpp)【问题描述】利用加权平均掩模实现数字图像的平滑（图像边缘不予处理）；加权平均掩模如下图。完成源程序image.cpp中Smoot

17、h_Filter函数的编写。#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, p, q, sum;/加权平均掩模int src33 =

18、 1, 2, 1, 2, 4, 2, 1, 2, 1;/加权平均 例如第1行第1列=(1 * 0 + 2 * 2 + 1 * 3 + 2 * 2 + 4 * 0 + 2 * 1 + 1 * 3 + 2 * 1 + 1 * 0)/16 for (i = 0; i n - 2; i+)for (j = 0; j n - 2; j+)sum = 0;for (p = i; p i + 3; p+)for (q = j; q j + 3; q+)sum += mappq * srcp - iq - j;sum /= 16;/outij = sum;printf(%d, sum);/我直接输出sum,也

19、可保存在outij中最后输出j = n - 3 ? printf(n) : printf( );/= int main()freopen(image.in, r, stdin); freopen(image.out, w, stdout);ini();Smooth_Filter();return 0;【输入】输入文件image.in的第一行为一个自然数n(1=n=300);接着n行，每行n个整数，描述nn像素图像（元素的值介于0255之间）；【输出】输出文件 image.out为n-2行，每行n-2个整数，表示滤波后n-2n-2像素图像。 【输入输出样例1】image.inimage.out4

20、0 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 16.模拟进程调度算法（本题100分）(os.cpp)【问题描述】进程调度算法FCFS+SJF模拟。编写FCFS+SJF算法，输入一组若干个进程的调度信息，输出根据先来先服务和短进程优先算法的调度结果。（提示：短进程优先算法仅在进程的到达时间一样时，才启用）。完成源程序os.cpp中fcfs

21、_sjf函数的编写。提醒：每个输出数据之前输出1个t。#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,

22、jobi.no,jobi.tb,jobi.tr);void fcfs_sjf()/*int i, j, timeNow;struct Job_type t;/冒泡排序，二级排序。关键字：作业开始时间，作业运行时间。for(i = 0; i n - 1; i+) /进行n-1趟比较for(j = 0; j jobj + 1.tb)t = jobj;jobj = jobj + 1;jobj + 1 = t;elseif(jobj.tr jobj + 1.tr)t = jobj;jobj = jobj + 1;jobj + 1 = t;/= printf(FCFSsjf调度结果:n);printf(

23、 开始时间 作业号 到达时间 运行时间 完成时间 等待时间 周转时间n);/*timeNow = 0;for(i = 0; i n; i+)printf(t%dt%dt%dt%dt%dt%dt%dn,timeNow,jobi.no,jobi.tb,jobi.tr,timeNow + jobi.tr,timeNow - jobi.tb,timeNow + jobi.tr - jobi.tb);timeNow += jobi.tr;/= int main() freopen(os.in, r, stdin); freopen(os.out, w, stdout); load(); fcfs_sjf(); return 0; 【输入】输入文件os.in中，第一行数字表示作业或进程总数，如4个作业输入4。第二行开始每行输入1个进程的调度信息，包括进程作业号、进程到达时间和进程估计运行时间。【输出】输出文件os.out将得到所输入的进程信息和调度结果的输出。 【输入输出样例1】os.inos.out41 0 702 0 203 0 404 0 5输入作业顺序:107020203040405FCFSsjf调度结果: 开始时间 作业号 到达时间 运行时间 完成时间 等待时间 周转时间040550552020255252530406525656