2021年下半年程序员下午试卷_4
2021年下半年程序员下午试卷1、【简答题】试题一（共15分）阅读以下说明和算法，完善算法并回答问题，将解答写在答题纸的对应栏内。说明假设以二维数组G1.m,1.n表示一幅图像各像素的颜色，则Gi,j表示区域中点(i,j)处的颜色，颜色值为0到k的整数。下面的算法将指定点(i0,j0)所在的同色邻接区域的颜色置换为给定的颜色值。约定所有与点(i0,j0)同色的上、下、左、右可连通的点组成同色邻接区域。例如，一幅89像素的图像如图1-1所示。设用户指定点(3,5)，其颜色值为0，此时其上方(2,5)、下方(4,5)、右方(3,6)邻接点的颜色值都为0，因此这些点属于点(3,5)所在的同色邻接区域，再从上、下、左、右四个方向进行扩展，可得出该同色邻接区域的其他点（见图1-1中的阴影部分）。将上述同色区域的颜色替换为颜色值7所得的新图像如图1-2所示。算法输入：矩阵G，点的坐标(i0,j0)，新颜色值newcolor。输出：点(i0,j0)所在同色邻接区域的颜色置换为newcolor之后的矩阵G。算法步骤(为规范算法，规定该算法只在第七步后结束)：第一步：若点(i0,j0)的颜色值与新颜色值newcolor相同,则(1)；第二步：点(i0,j0)的颜色值oldcolor；创建栈S，并将点坐标(i0,j0)入栈；第三步：若(2)，则转第七步；第四步：栈顶元素出栈(x,y)，并(3)；第五步：1)若点(x,y-1)在图像中且Gx,y-1等于oldcolor，则(x,y-1)入栈S；2)若点(x,y+1)在图像中且Gx,y+1等于oldcolor，则(x,y+1)入栈S；3)若点(x-1,y)在图像中且Gx-1,y等于oldcolor，则(x-1,y)入栈S；4)若点(x+1,y)在图像中且Gx+1,y等于oldcolor，则(x+1,y)入栈S；第六步：转(4)；第七步：算法结束。问题是否可以将算法中的栈换成队列？回答：(5)。15分解析：（1）转第七步（2）栈空（3）Gx,ynewcolor（4）第三步（5）可以2、【简答题】试题二（共15分）阅读以下说明和C函数，将应填入（n）处的字句写在答题纸的对应栏内。说明某单位准备进行一次选举，对指定的n名(n80)候选人进行投票。为了简化选举工作，事先印制了写有这n名候选人姓名的选票，投票者只需将选中者名下的圆圈涂黑即可。规定每张选票上被涂黑的圆圈数不得超过3个，也不得少于1个，否则视为无效选票。投票结束后，所有选票经计算机扫描处理，形成了描述选票状态的文本文件。例如，n=8时所形成的文件如下：010110001001010010011000111111110000000000111000其中，每行表示一张选票的数据，每列代表一位候选者的得票情况。第i行第j列为1，表示第i张选票上投了第j名候选人1票。函数statistic()的功能是读入选票数据，并统计每位候选者的得票数,函数返回有效选票数。C函数intstatistic(FILE*fp,intcandidate,intn)/*从文件中读入选票数据，n为候选人数量(n80)，从有效选票中统计每位候选者的得票数并存入candidate,函数返回有效选票数*/charstr80;/*str保存读入的一张选票数据*/inti,tag=0;/*tag用于判断每张选票是否有效*/intq=0;/*q用于计算有效选票数*/for(i=0;in;i+)candidatei=0;while(1)fgets(str,80,fp);/*读入一张选票数据*/for(tag=0,i=0;(2);i+)if(stri=1)tag+;if(3)/*若是有效选票，则进行统计*/(4);for(i=0;in;i+)if(stri=1)(5);returnq;/*statistic*/15分解析：（1）!feof(fp)（2）instri!=0（3）tag=1tag=3（4）q+（5）candidatei+3、【简答题】试题三（共15分）阅读以下说明和C函数，将应填入（n）处的字句写在答题纸的对应栏内。说明若一个矩阵中的非零元素数目很少且分布没有规律，则称之为稀疏矩阵。对于m行n列的稀疏矩阵M，进行转置运算后得到n行m列的矩阵MT，如图3-1所示。为了压缩稀疏矩阵的存储空间，用三元组（即元素所在的行号、列号和元素值）表示稀疏矩阵中的一个非零元，再用一维数组逐行存储稀疏矩阵中的所有非零元素（也称为三元组顺序表）。例如，图3-1所示的矩阵M相应的三元组顺序表如表3-1所示，其转置矩阵MT的三元组顺序表如表3-2所示。函数TransposeMatrix(MatrixM)的功能是对用三元组顺序表表示的稀疏矩阵M进行转置运算。对M实施转置运算时，为了将M中的每个非零元素直接存入其转置矩阵MT三元组顺序表的相应位置，需先计算M中每一列非零元素的数目（即MT中每一行非零元素的数目），并记录在向量num中；然后根据以下关系，计算出矩阵M中每列的第一个非零元素在转置矩阵MT三元组顺序表中的位置：cpot0=0cpotj=cpotj-1+numj-1/*j为列号*/类型ElemType、Triple和Matrix定义如下：typedefintElemType;typedefstruct/*三元组类型*/intr,c;/*矩阵元素的行号、列号*/ElemTypee;/*矩阵元素的值*/Triple;typedefstruct/*矩阵的三元组顺序表存储结构*/introws,cols,elements;/*矩阵的行数、列数和非零元素数目*/TripledataMAXSIZE;Matrix;C函数intTransposeMatrix(MatrixM)intj,q,t;int*num,*cpot;MatrixMT;/*MT是M的转置矩阵*/num=(int*)malloc(M.cols*sizeof(int);cpot=(int*)malloc(M.cols*sizeof(int);if(!num|!cpot)returnERROR;MT.rows=(1);/*设置转置矩阵MT行数、列数和非零元数目*/MT.cols=(2);MT.elements=M.elements;if(M.elements0)for(q=0;qM.cols;q+)numq=0;for(t=0;tM.elements;+t)/*计算矩阵M中每一列非零元素数目*/numM.datat.c+;/*计算矩阵M中每列第一个非零元素在其转置矩阵三元组顺序表中的位置*/(3);for(j=1;jM.cols;j+)cpotj=(4);/*以下代码完成转置矩阵MT三元组顺序表元素的设置*/for(t=0;tM.elements;t+)j=(5);/*取矩阵M的一个非零元素的列号存入j*/*q为该非零元素在转置矩阵MT三元组顺序表中的位置（下标）*/q=cpotj;MT.dataq.r=M.datat.c;MT.dataq.c=M.datat.r;MT.dataq.e=M.datat.e;+cpotj;/*计算M中第j列的下一个非零元素的目的位置*/*for*/*if*/free(num);free(cpot);/*此处输出矩阵元素，代码省略*/returnOK;/*TransposeMatrix*/15分解析：（1）M.cols（2）M.rows（3）Cpot0=0（4）Cpotj-1+numj-1（5）M.datat.c4、【简答题】试题四（共15分）阅读以下应用说明以及用VisualBasic编写的程序代码，将应填入（n）处的字句写在答题纸的对应栏内。应用4.1设应用程序的运行窗口内有一个文字标签（Label）以及一个框架，其中有三个复选框（chk1，chk2，chk3），各个复选框单击事件过程的程序代码如下：PrivateSubchk1_Click()Label.fontBold=chk1.ValueEndSubPrivateSubchk2_Click()Label.fontItalic=chk2.ValueEndSubPrivateSubchk3_Click()Label.fontUnderLine=chk3.ValueEndSub三个复选框chk1、chk2、chk3的功能分别是：(1)。应用4.2设应用程序的运行窗口内有两个文本框Txt1和Txt2，其初始内容为空。在Txt1文本框中输入一个数值，当光标离开此文本框（例如进入文本框Txt2）时，执行的程序代码如下：PrivateSubTxt1_LostFocus()dimxasdoublex=Val(Txt1.Text)Ifx0Orx100ThenTxt1.Text=""MsgBox$("请重新输入！")Txt1.SetFocusElseTxt2.Text=Txt1.TextEndIfEndSub该程序代码的功能是：若在文本框Txt1中输入的数值小于0或大于100，当光标离开此文本框时，(2)；否则，将其值复制到文本框Txt2中。应用4.3在下面的应用中，当窗口内发生Click事件时，窗口内将显示如图4-1所示的杨辉三角形（每一行都是二项式展开的系数）。请完善程序代码PrivateSubForm_Click()Dimi,j,cAsInteger,StrTempAsStringDima(9)AsIntegera(0)=0:a(1)=1StrTemp=Str(a(1)+Space(3)CurrentX=(ScaleWidth-TextWidth(StrTemp)/2PrintStrTempForj=2To9a(j)=1Forc=j-1To2Step-1a(c)=(3)Next(4)=""
