《计算机科学技术专业技能模拟考核》由会员分享，可在线阅读，更多相关《计算机科学技术专业技能模拟考核（16页珍藏版）》请在金锄头文库上搜索。
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 name20; /* the name of student*/int maths;int english;int computer;struct Grade_table gradeSIZE;void ini( )int i, j =
