试题三（共15分）阅读以下说明和C 函数，将应填入（n） 处的字句写在答题纸的对应栏内。[说明]若一个矩

试题一（共 15分）

阅读以下说明和算法，完善算法并回答问题，将解答写在答题纸的对应栏内。

[说明]

假设以二维数组G[1..m,1..n]表示一幅图像各像素的颜色，则G[i,j]表示区域中点(i,j)处的颜色，颜色值为0到k 的整数。下面的算法将指定点(i0,j0)所在的同色邻接区域的颜色置换为给定的颜色值。约定所有与点(i0,j0)同的上、下、左、右可连通的点组成同色邻接区域。

例如，一幅8×9 像素的图像如图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)在图像中且G[x,y-1]等于oldcolor，则(x,y-1)入栈S；

2) 若点(x,y+1)在图像中且G[x,y+1]等于oldcolor，则(x,y+1)入栈S；

3) 若点(x-1,y)在图像中且G[x-1,y]等于oldcolor，则(x-1,y)入栈S；

4) 若点(x+1,y)在图像中且G[x+1,y]等于oldcolor，则(x+1,y)入栈S；

第六步：转 (4) ；

第七步：算法结束。

[问题]

是否可以将算法中的栈换成队列？回答： (5) 。

试题四（共 15 分）

阅读以下说明和 C 语言函数，将应填入 （n） 处的字句写在答题纸的对应栏内。

[说明]

已知包含头结点（不存储元素）的单链表的元素已经按照非递减方式排序，函数compress(NODE *head)的功能是去掉其中重复的元素，使得链表中的元素互不相同。

处理过程中，当元素重复出现时，保留元素第一次出现所在的结点。

图4-1(a)、(b)是经函数 compress()处理前后的链表结构示例图。

链表的结点类型定义如下：

typedef struct Node {

int data;

struct Node *next;

}NODE;

[C 语言函数]

void compress(NODE *head)

{ NODE *ptr,*q;

ptr = （1） ; /* 取得第一个元素结点的指针 */

while ( （2） && ptr -> next) {

q = ptr -> next;

while(q && （3） ) { /* 处理重复元素 */

（4） = q -> next;

free(q);

q = ptr -> next;

}

（5） = ptr -> next;

}/* end of while */

}/* end of compress */

试题七（共15分）

阅读以下应用说明以及用Visual Basic 编写的程序代码，将应填入（n） 处的字句写在答题纸的对应栏内。

[应用说明]

某应用程序用于监测某种设备的工作温度（20～200度），其运行窗口中，包括一个温度计（矩形形状shpMeter）以及其中指示当前设备温度的水银柱（矩形形状shpT）,文字标签标记了温度刻度；另有一个图片框picCurve，用于动态描述检测到的温度曲线（用户见到的曲线与水银柱等高变化）；命令按钮“开始测”（cmdStart）用于启动温度检测，命令按钮“暂停检测”（cmdStop）用于暂停检测。矩形形状 shpT(水银柱)属性visible 初始设置为不可见，属性Filltype 设置为solid（实心），FillColor设置为红色；图片框picCurve的属性AutoRedraw设置为True；再创建一个定时器TimT，属性Enabled初始设置为False（不起作用），属性Interval(定时间隔)设置为500 毫秒。为模拟设备温度的检测，程序中利用了（0，1）之间均匀分布的伪随机数获得[20,200]之间的随机温度T。为了便于在图片框picCurve 中绘制曲线，程序中对该图片框立了坐标系统，左上角为原点（0，0），水平向右方向为X 轴，垂直向下方向为Y 轴，右下角坐标为（50，180）。为了便于观察记录的温度值，图片框中从上到下创建了5 条水平线Ls(i),i=0,1,…4，并在程序中按等间隔排列进行位置设置。程序中每隔半秒算出曲线点（x,y），其中x=0,1,2,…，再用直线段连接各相邻曲线点形成温度曲线。

[Visual Basic程序代码]

Dim (1) As Integer '声明全局变量

Private Sub CmdStart_Click( )

TimT.Enabled = True

ShpT.Visible = True

End Sub

Private Sub CmdStop_Click( )

TimT.Enabled = False

End Sub

Private Sub Form_Load( )

Dim i, H As Integer

PicCurve.Scale (0, 0)-(50, 180) '设置图片框坐标系：左上角-右下角

H = 30 'H 等于图片框高度的六分之一

For i = 0 To 4 '设置5条水平线Ls(i)的位置

Ls(i).X1 = 0 'Ls(i)起点横坐标

Ls(i).Y1 = H * (2) 'Ls(i)起点纵坐标

Ls(i).X2 = 50 'Ls(i)终点横坐标

Ls(i).Y2 = Ls(i).Y1 'Ls(i)终点纵坐标

Ls(i).BorderColor = &HC0C0C0 '设置水平线颜色

Next i

x = 0 '设置曲线坐标初值

End Sub

Private Sub timT_Timer()

Dim T, H As Integer 'T为即时温度，H 为图片框中温度点显示高度

T = Int(Rnd * 181) + 20 '模拟随机产生设备温度（20～200 度）

'按当前温度显示水银柱

H = ShpMeter.Height * (3) '算出水银柱的高度

ShpT.Top = (4) - H '设置水银柱顶部位置

ShpT.Height = H '设置水银柱的高度

'绘制温度曲线

y = (5) '算出曲线上当前点的纵坐标

If x = 51 Then '当超出图片框时

PicCurve.Cls '清除图片框内以前画的曲线

x = 0 '设置重画曲线的初值

ElseIf x > 0 Then '除左边点外

PicCurve.Line (x-1,Lasty)-(x,y),vbRed '由前1 点到当前点画红色线段

End If

x = x + 1 '准备下一点坐标

Lasty =y '保存当前坐标供下次使用

End Sub

试题五（共15分）

阅读以下说明和C 函数，将应填入（n） 处的字句写在答题纸的对应栏内。

[说明]

某班级有N 名学生，他们可根据自己的情况选修名称和数量不尽相同的课程。设N，如图5-1 所示。

程序中相应的类型定义如下：

define N 6

struct node{

char cname[5]; /*课程名*/

int grade; /*成绩*/

struct node *next; /*指针，指示某学生选修的下一门课程及成绩*/

};

struct student{

char xh[5]; /*学号*/

char name[20]; /*姓名*/

struct node *link; /*指针，指示出选修的课程及成绩链表*/

}stud_info[N];

stud_info[]为一个全局数组。

函数func (char kc[],int *num)的功能是统计选修了课程名为kc 的学生的人数，

并返回该课程的平均成绩（若无人选修该课程，则平均成绩为0），参数num 带回选修课程kc 的学生人数。

[C函数]

double func (char kc[],int *num)

{

int i,count = 0,sum = 0; /*count用于记录选修课程名为kc 的学生的人数*/

double avg = 0.0;

struct node *p;

for(i = 0; i < N; i++){

p = (1) ; /*取第i 个学生所修课程链表的头指针*/

while (p) {

if ( (2) ) {

sum = (3) ;

count++;

break;;

}/*if*/

p = p->next;

}/*while*/

}

(4) ;

if ( (5) )

avg = (double)sum / count; /* 计算平均成绩 */

return avg;

}/*func*/

●试题一

阅读下列说明和流程图，将应填入(n)处的语句写在答题纸的对应栏内。

【说明】

下列流程图用于从数组K中找出一切满足：K(I)+K(J)=M的元素对(K(I)，K(J))(1≤I≤J≤N)。假定数组K中的N个不同的整数已按从小到大的顺序排列，M是给定的常数。

【流程图】

此流程图1中，比较"K(I)+K(J)∶M"最少执行次数约为 (5) 。

图1

●试题一

阅读下列说明和流程图，将应填入(n)的语句写在答题纸的对应栏内。

【流程图】

图1

下面的流程图描述了对16位二进制整数求补的算法。计算过程是：从二进制数的低位(最右位)开始，依次向高位逐位查看，直到首次遇到"1"时，停止查看。然后，对该"1"位左面的更高位(如果有的话)，逐位求反，所得的结果就是对原二进制数求补的结果。

例如：对二进制整数10111001 10101000求补的结果是01000110 01011000。

设16位二进制整数中的各位，从低位到高位，依次存放在整型数组BIT的BIT［1］～BIT［16］中。例如，二进制整数10111001 10101000存放在数组BIT后，就有BIT1［1］=0，BIT［2］=0，……，BIT［15］=0，BIT［16］=1。

流程图(如图1所示)中 (1) 处按"循环变量名：循环初值，增量，循环终值"格式描述。若流程图中存在空操作，则用NOP表示。

●试题一

阅读下列说明和流程图，将应填入(n)的字句写在答题纸的对应栏内。

【说明】

下列流程图(如图4所示)用泰勒(Taylor)展开式

sinx=x-x3／3!+x5／5!-x7／7!+…+(-1)n×x 2n+1／(2n+1)!+…

【流程图】

图4

计算并打印sinx的近似值。其中用ε(>0)表示误差要求。

试题二 （ 共15 分）

阅读以下问题说明、C 程序和函数，将解答填入答题纸的对应栏内。

【 问题1 】

分析下面的C 程序，指出错误代码（或运行异常代码）所在的行号。

【C程序】

【 问题2】

函数inputArr(int a[], int n)的功能是输入一组整数（输入0或输入的整数个数达到n时结束）存入数组 a，并返回实际输入的整数个数。函数 inputArr 可以成功编译。但测试函数调用inputArr后，发现运行结果不正确。

请指出错误所在的代码行号，并在不增加和删除代码行的情况下进行修改，写出修改正确后的完整代码行，使之符合上述设计意图。

【C 函数】

●试题二

阅读下列程序说明和C程序，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

程序8用于计算某公司每个职工应缴纳的个人所得税额和全体职工缴纳的个人所得税总额，职工的当月收入(工资或薪金)通过键盘输入，每次输入一个职工的工号和工资(或薪金)。由于该公司的工资或薪金是不定时发放的，所以输入过程中每个职工的收入会出现多次输入，整个输入以工号小于等于0结束。

假设个人所得税法规定：个人收入所得，按月计税，以每月收入总额减除免税金额800元后的余额作为该月的月应纳税所得额。适用税率如表2所示。

上表表明，个人收入所得税是按照超额累进的税率来征收的。

设一个人的月应纳税所得额为K(元)，用下面的公式计算其应缴纳的个人所得税额S(元)；

若0＜K≤500，则S=K×5%；

若500＜K≤2000，则S=500×5%+(K-500)×10%；

若2000＜K≤5000，则S=500×5%+1500×10%+(K-2000)×15%；

若5000＜K≤20 000，则S=500×5%+1500×10%+3000×15%+(K-5000)×20%；

…

例如，某人某月收入总额为4100元，减去800元后，应纳税所得额为3300元，其应缴纳的个人所得税额为500*5%+1500*10%+1300*15%=370元。

【程序】

include <stdio．h>

define MaxNum50

define BASE 800/*免税金额基数*/

int paylevel［］={0，500，2000，5000，20000，40000，60000，80000，100000，1000001}；

int taxPrate［］={5，10，15，20，25，30，35，40，45}；/*税率表*/

typedef struct{

int Id；/*职工的工号*/

long Salary；/*职工的工资*/

}Info；

/*查找工号为Id的职工在数组employee中的下标，返回值为0表示没有*/

int find (int Id ，Info employee［］，int m){

int j；

employee［0］.Id=Id；

for(j=m； (1) ；j--)；

return j；

}

void main(void)

{Info employee［MaxNum+1］；

long Wage；

double sum=0，K，S；

int i，j，N=0，Code；

scanf(″%d %ld″，&Code，&Wage)；/*读入职工号、工资或薪金*/

while(Code＞0){

i=find(Code，empolyee，N)；

if(i＞0)employee［i］.Salary+=Wage；

else{ (2) ；

employee［N］．Id=Code；employee［N］.Salary=Wage；

}

scanf(″%d %ld″，&Code，&Wage)；

}

for(i=1；i＜=N；i++){

K= (3) ；/*计算月应纳税所得额*/

S=0；/*月应纳税额赋初值*/

if(K＞0){

for(j=1；j＜=9；j++)

if (4) /*月应纳税所得额超过第j级*/

S=S+(paylevel［j］-paylevel［j-1］)*taxPrate［j-1］/100；

else{S=S+ (5) *taxPrate［j-1］/100；break；}

}

printf(″职工%d应缴纳的个人所得税额:%10．21f＼n″，employee［i］．Id，S)；

sum+=S；

}

printf(″全体职工个人所得税总额:%10．21f＼n″，sum)；

}

●试题七

阅读以下说明及Visual Basic程序代码，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

某学校举办了一场奥运知识竞赛，参加竞赛的选手为200名，1~200为选手编号。竞赛时间为9：00～11：00。8道竞赛题目依次从"A"～"H"编号，选手可按任意次序答题，每完成一道题目，可立即提交答案。若答案正确(Y)，则选择其他题目进行解答，否则，可继续做该题目或选择其他题目进行解答，直至竞赛结束。

选手提交答案的情况及判定结果由专人即时录入，录入数据包括提交答案的时间、选手编号、题目编号(A～H)、是否正确(Y／N)等。

对竞赛情况进行统计和排名的规则如下：

1．若选手X在竞赛时提交的题目P解答正确，则解答该题目所用时间计算如下：

解答题目P的用时=提交题目P正确的时间-竞赛的开始时间+罚时罚时=提交题目P错误解答的次数×20例如：表1中14号选手在10：27提交了题目A的正确解答，因此该选手正确解答该题目所用时间P为87分钟，由于他在09：37和09：52两次提交了题目A的错误解答，因此罚时为(2×20)分钟=40分钟，所以14号选手解答题目A的用时=(87+40)分钟=127分钟。

2．已经提交正确答案的题目再次提交时不再计算。

3．竞赛结束时，选手的总用时为所有解答正确的题目用时累加所得，解答不正确的题目不计时。

4．排名时，完成题目数量多者排名靠前；若完成的题目数相同，则用时少者排名靠前；若完成的题目数和所用时间均相等，则名次相同；完成题目数为0的选手不参加排名。

本应用程序的运行窗口如图3所示。

图3

窗口中的两个文本框为Txt_time和Txt_player，分别用于录入提交答案的时间和选手编号。组合列表框Combol提供题目编号(A～H)，录入时从中选择。检查框Chk_yn用于输入解答是否正确信息。当单击"确定"按钮(Cmd_comfirm)时，录入的提交信息加入列表框Listl中，排名情况在列表框List2输出。单击"关闭"按钮时退出应用程序。

在开发过程中，需要编写的部分程序代码如下：

【程序】

Private Type Info

No As Integer′选手编号

Num As Integer′完成题目数量

Time As Integer′完成题目的总用时

d (8) As Integer′d用于记录提交第i个题目错误答案的次数

a (8) As Boolean′a用于记录第i个题目是否已经提交正确答案

End Type

Dim R(201)As info′R［j］用于统计编号为j的选手提交答案的情况

Dim MaxIndex As Integer′MaxIndex记录提交答案的选手中编号最大者

Private Sub Form_Load()

For i=1 to 8

Combo1．AddItem chr( (1) )

Next

Combo1．Text=Combo1．List(0)：txt_time．Text=""：txt_player．Text=""

For i=1 To 200

R(i)．num=0：R(i)．time=0：R(i)．no=i

Forj=1 To 8

R(i)．d(j)=0：R(i)．a(j)=False

Next j，i

End Sub

Private Sub cmd_confirm_Click()

Dim h，m，k，time As Integer，ch，pass，s1 As String

K=Instr(txt_time．text，"∶")：If k<2 Then Goto error1

H=Val(Left(txt_time．Text，k-1))：m=Val(Mid(txt_time．Text，k+1))

If h>11 Or h=11 And m>0 Or m>=60 Then goto errorl

Time= (2) ′计算答题时间，以分钟为单位

If txt_plater．text<1 or txt_player．text>200 Then Goto error1

ch= (3)

pass=IIf(chk_yn． (4) =0，"N"，"Y")

s1=txt_time．Text+Space (4) +txt_player．Text

s1=s1+Space(10-Len(txt_player．Text))+ch+Space (8) +pass

List1．Additem s1

K=Val(txt_player．Text)′k为选手编号

R(k)．no=k′编号为k的选手的提交信息记录在下标为k的数组元素中

If k>maxindex Then maxindex=k

M=Asc(ch)-Asc("a")

If pass<>"Y"Then′编号为k的选手提交第m个题目的解答不正确

R(k)．d(m)=R(k)．d(m)+1

Else If R(k)．a(m)<>True Then′已经提交正确的题目的解答不再计算

R(k)．a(m)=true：R(k)．num=R(k)．num+1

R(k)．time=R(k)．time+ (5)

Call statistic′调用过程statistic进行实时排名和输出

End If

Exit Sub

error1：MsgBox"录入信息有错误!"，vbOKOnly

End Sub