計(jì)算機(jī)科學(xué)技術(shù)專業(yè)技能模擬考核

1、1. 最短距離（本題100分）(dist.cpp/c)【問題描述】開車從起始點(diǎn)到目的地的路線有多條。給你一張描述待選路線的表（n*n的矩陣A），讓你找出行車距離最短的路線。表中表示了任意兩個(gè)路口的連通情況，以及距離。矩陣元素a(i,j)=0表示路口i,j不連通，a(i,j)!=0表示路口i,j的行車距離。其中起始點(diǎn)在路口1，目的地在路口n 。完成源程序DIST.CPP中Dijkstra函數(shù)的編寫。#include "stdio.h"#define maxint 10000int n,used31,map3131;void ini( )int i,j;scanf("

2、%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 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 <=

3、n; j+)if (!usedj && distj < mind)mind = distj;k = j;if (k < 0)break;usedk = 1;/路徑擴(kuò)展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&q

4、uot;, stdin);freopen("dist.out", "w", stdout);ini();Dijkstra();return 0;【輸入】輸入文件dist.in的第一行為一個(gè)自然數(shù)n(1<n<=30);接著n行，每行n個(gè)整數(shù)，描述待選路線的表（元素的值小于1000）；【輸出】輸出文件dist.out包括一行，為一個(gè)整數(shù)，表示起始點(diǎn)到目的地的最短行車的距離。 【輸入輸出樣例1】dist.indist.out40 2 3 42 0 1 13 1 0 04 1 0 03【輸入輸出樣例2】dist.indist.out60 1 3 4

5、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)【問題描述】已知從起始點(diǎn)到達(dá)各目站點(diǎn)（、C、D.）的各最短路徑上所有站點(diǎn)的前驅(qū)站點(diǎn)，以及至前驅(qū)站點(diǎn)的距離。以一個(gè)二維數(shù)組pre描述已知信息，第1列是前驅(qū)站點(diǎn)的序號(hào)（以0、1、2.分別表示站點(diǎn)A、B、C.），第2列是至前驅(qū)站點(diǎn)的距離。試推算和輸出從起始點(diǎn)出發(fā)到達(dá)各其余站點(diǎn)的最短路徑和距離。完成源程序DictS.CPP中Pathway函數(shù)的編寫。#include "stdio.h"int n, pre262;

6、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

7、9;,'Y','Z'void ini() int i;scanf("%d", &n);for(i=0; i<n; i+)scanf("%d%d", &prei0, &prei1);void Pathway()/*int i, j, sum = 0;int st100, top;for (i = 1; i < n; i+)/從'B'開始for (j = i, top = sum = 0; ;)/從尾到頭('A')進(jìn)棧sttop+ = prej0;sum +=

8、 prej1;j = prej0;if (j = 0)/到達(dá)'A'break;for (j = top - 1; j >= 0; j-)printf("%c-", stationstj);printf("%c", stationi);printf(" %dn", sum);/=int main() freopen("DictS.in", "r", stdin);freopen("DictS.out", "w", stdout);ini

9、();Pathway();fclose(stdin);fclose(stdout);return 0;【輸入】輸入文件DictS.in的第1行為1個(gè)自然數(shù)n(1<n<=26，表示包括起始點(diǎn)在內(nèi)的站點(diǎn)總數(shù))；后續(xù)n行，每行2個(gè)整數(shù)，分別描述站點(diǎn)A、B、C.的前驅(qū)站點(diǎn)和至前驅(qū)站點(diǎn)的距離?！据敵觥枯敵鑫募﨑ictS.out包含n-1行，每行2個(gè)部分，前部為最短路徑，后部為距離。格式見輸出樣例。【輸入輸出樣例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

10、-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. 有限自動(dòng)機(jī)（本題100分）(dfa.cpp/c)【問題描述】設(shè)有如下確定的狀態(tài)轉(zhuǎn)換圖，0為起始狀態(tài)，3，4為終結(jié)狀態(tài)。編寫程序，判斷用戶輸入的符號(hào)串，是否被該有限自動(dòng)機(jī)接受。#include "stdio.h"#define max 1000int dfachk(char str) /*int i, j, f105;int s = 0;for (i = 0; i

11、< 10; i+)for (j = 0; j < 5; j+)fij = -1;/根據(jù)表轉(zhuǎn)換: fij = k, 代表 從狀態(tài)i, 輸入字符j, (j : 0代表'a', 1 :代表'b')，轉(zhuǎn)移到狀態(tài)kf00 = 0;f01 = 1;f10 = 2;f20 = 1;f11 = 3;f31 = 3;f30 = 4;f40 = 3;/一遍循環(huán)字符串,頭到尾for (i = 0; stri; i+)if (stri != 'a' && stri != 'b')return i + 1;/非'a

12、9;非'b's = fsstri - 'a'if (s < 0)return i + 1;/無(wú)路可走if (s != 3 && s != 4)return i + 1;/非法結(jié)束return 0;/=void main() char insmax=0;freopen("dfa.in", "r", stdin);freopen("dfa.out", "w", stdout); gets(ins);printf("%d",dfachk(ins);

13、【輸入】輸入文件dfa.in為一行字符串（字符個(gè)數(shù)小于1000）；【輸出】輸出文件dfa.out包括一行，為一個(gè)整數(shù)，表示輸入的符號(hào)串是否被該有限自動(dòng)機(jī)接受，若接受，則輸出0，否則輸出首次出錯(cuò)字符所在的位置（注：輸入串首字符的位置為1）。 學(xué)生只要編寫函數(shù)int dfachk(char str)，該函數(shù)的參數(shù)str為輸入串，若輸入串str被該有限自動(dòng)機(jī)接受，則函數(shù)返回值為0。若輸入串str在第n個(gè)字符處首次出錯(cuò)，則函數(shù)返回值為n?！据斎胼敵鰳永?】dfa.indfa.outaa3【輸入輸出樣例2】dfa.indfa.outabbaaa0【輸入輸出樣例3】dfa.indfa.outababaaa

14、b4【輸入輸出樣例4】dfa.indfa.outabaacaab5【數(shù)據(jù)規(guī)?！枯斎氲淖址L(zhǎng)度L<10004.數(shù)據(jù)庫(kù)查詢（本題100分）(DB.c)【問題描述】Student數(shù)據(jù)庫(kù)里面有個(gè)Grade表，該表里面存儲(chǔ)了每個(gè)學(xué)生的學(xué)號(hào)，姓名，maths成績(jī)，english成績(jī)和computer成績(jī)?，F(xiàn)要查詢Grade表，顯示三門課都及格的學(xué)生學(xué)號(hào)、姓名、maths、english、computer字段，并按照學(xué)號(hào)升序排列。完成源程序DB.C中select2函數(shù)的編寫。#include <stdio.h>#define SIZE 100int n;struct Grade_tabl

15、eint 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 = 0;scanf("%d",&n);for(i=0;i<n;i+) scanf("%d %s %d %d %d",&(gradei.no_stu),,&(gradei.maths),&a

16、mp;(gradei.english),&(puter);void select2()/*int rankSIZE, tot = 0;int i, j, k;for (i = 0; i < n; i+)if (gradei.maths >= 60 && gradei.english >= 60 && puter >= 60)/存下標(biāo)ranktot+ = i;/選擇排序，只對(duì)下標(biāo)排序，比較簡(jiǎn)單for (i = 0; i < tot; i+) k = i;for (j = i + 1; j

17、 < tot; j+)if (graderankj.no_stu < graderankk.no_stu)/記錄最小k = j;if (k != i)/最小學(xué)號(hào)的下標(biāo)k與i交換Grade_table tmp = graderankk;graderankk = graderanki;graderanki = tmp;for (i = 0; i < j; i+)printf("%d,%s,%d,%d,%dn", graderanki.no_stu, , graderanki.maths, graderanki.english, g

18、puter);/= int main()freopen("DB.in", "r", stdin);freopen("DB.out", "w", stdout);ini();select2();return 0;【輸入】輸入文件DB.in的第一行為一個(gè)自然數(shù)n(1<n<=100);接著n行，每行代表一個(gè)學(xué)生的記錄（學(xué)號(hào) 姓名 maths成績(jī) english成績(jī) computer成績(jī)），其中0<=成績(jī)<=100，每個(gè)字段之間用空格間隔開?！据敵觥枯敵鑫募﨑B.out包括

19、x行，每行代表一個(gè)學(xué)生的記錄，顯示字段為：學(xué)號(hào)、姓名、maths成績(jī)、english成績(jī)、computer成績(jī)。每個(gè)字段之間用逗號(hào)間隔開【輸入輸出樣例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 7

20、5301 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)【問題描述】利用加權(quán)平均掩模實(shí)現(xiàn)數(shù)字圖像的平滑（圖像邊緣不予處理）；加權(quán)平均掩模如下圖。完成源程序 image.cpp中Smooth_Filter函數(shù)的編寫。#include "stdio.h"#de

21、fine MAX_INT 300int n,mapMAX_INTMAX_INT,outMAX_INTMAX_INT;void ini( )int i,j;for( i=0; i<MAX_INT; i+)for( j=0; j<MAX_INT; j+) mapij=0;outij=0;scanf("%d", &n);for( i=0; i<n; i+)for( j=0; j<n; j+) scanf("%d", &mapij);void Smooth_Filter()/*int i, j, p, q, sum;/加權(quán)

22、平均掩模int src33 = 1, 2, 1, 2, 4, 2, 1, 2, 1;/加權(quán)平均 例如第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;/outi

23、j = sum;printf("%d", sum);/我直接輸出sum,也可保存在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的第一行為一個(gè)自

24、然數(shù)n(1=<n<=300);接著n行，每行n個(gè)整數(shù)，描述n×n像素圖像（元素的值介于0255之間）；【輸出】輸出文件 image.out為n-2行，每行n-2個(gè)整數(shù)，表示濾波后n-2×n-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

25、6.模擬進(jìn)程調(diào)度算法（本題100分）(os.cpp)【問題描述】進(jìn)程調(diào)度算法FCFS+SJF模擬。編寫FCFS+SJF算法，輸入一組若干個(gè)進(jìn)程的調(diào)度信息，輸出根據(jù)先來(lái)先服務(wù)和短進(jìn)程優(yōu)先算法的調(diào)度結(jié)果。（提示：短進(jìn)程優(yōu)先算法僅在進(jìn)程的到達(dá)時(shí)間一樣時(shí)，才啟用）。完成源程序 os.cpp中fcfs_sjf函數(shù)的編寫。提醒：每個(gè)輸出數(shù)據(jù)之前輸出1個(gè)t。#include <stdio.h>#include <stdlib.h>struct Job_type int no; /作業(yè)號(hào) int tb; /作業(yè)開始時(shí)間（分） int tr; /運(yùn)行時(shí)間（分） x;Job_ty

26、pe job36;int n;void load() int i,j; scanf("%d", &n); for( i=0; i<n; i+)scanf("%d", &jobi.no); scanf("%d", &jobi.tb); scanf("%d", &jobi.tr); printf("輸入作業(yè)順序:n"); for(i=0;i<n;i+) printf("t%dt%dt%dn",jobi.no,jobi.tb,jobi.t

27、r);void fcfs_sjf()/*int i, j, timeNow;struct Job_type t;/冒泡排序，二級(jí)排序。關(guān)鍵字：作業(yè)開始時(shí)間，作業(yè)運(yùn)行時(shí)間。for(i = 0; i < n - 1; i+) /進(jìn)行n-1趟比較for(j = 0; j < n - 1 - i; j+) /大的沉底if(jobj.tb != jobj + 1.tb) /作業(yè)開始時(shí)間不相等if(jobj.tb > jobj + 1.tb)t = jobj;jobj = jobj + 1;jobj + 1 = t;elseif(jobj.tr > jobj + 1.tr)t =

28、jobj;jobj = jobj + 1;jobj + 1 = t;/= printf("FCFSsjf調(diào)度結(jié)果:n");printf(" 開始時(shí)間 作業(yè)號(hào) 到達(dá)時(shí)間 運(yùn)行時(shí)間 完成時(shí)間 等待時(shí)間 周轉(zhuǎn)時(shí)間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.

29、tb);timeNow += jobi.tr;/= int main() freopen("os.in", "r", stdin); freopen("os.out", "w", stdout); load(); fcfs_sjf(); return 0; 【輸入】輸入文件os.in中，第一行數(shù)字表示作業(yè)或進(jìn)程總數(shù)，如4個(gè)作業(yè)輸入4。第二行開始每行輸入1個(gè)進(jìn)程的調(diào)度信息，包括進(jìn)程作業(yè)號(hào)、進(jìn)程到達(dá)時(shí)間和進(jìn)程估計(jì)運(yùn)行時(shí)間?！据敵觥枯敵鑫募s.out將得到所輸入的進(jìn)程信息和調(diào)度結(jié)果的輸出。 【輸入輸出樣例1】os.inos.out41 0 702 0 203 0 404 0 5輸入作業(yè)順序:107020203040405FCFSsjf調(diào)度結(jié)果: 開始時(shí)間 作業(yè)號(hào) 到達(dá)時(shí)間 運(yùn)行時(shí)