1、软件水平考试（初级）程序员下午（应用技术）模拟试卷 48及答案与解析 1 阅读以下说明和算法，完善算法并回答问题，将解答写在对应栏内。 说明 假设以二维数组 G1m,1n表示一幅图像各像素的颜色，则 Gi,j表示区域中点 (i,j处的颜色，颜色值为 0到 k的整数。 下面的算法将指定点 (i0,j0)所在的同色邻接区域的颜色置换为给定的颜色值。约定所有与点 (i0,j0)同色的上、下、左、右可连通的点组成同色邻接区域。 例如，一幅 89像素的图像如图 1-1所示。设用户指定点(3,5)，其颜色值为 0， 此时其上方 (2,5)、下方 (4,5)、右方 (3,6)邻接点的颜色值都为0，因此这些点
2、属于点 (3,5)所在的同色邻接区域，再从上、下、左、右四个方向进行扩展，可得出该同色邻接区域的其他点 (见图 1-1中的阴影部分 )。将上述同色区域的颜色替换为颜色值 7所得的新图像如图 1-2所示。 算法 输入：矩阵 G，点的坐标 (i0,j0)，新颜色值 newcolor。 输出：点 (i0,j0)所在同色邻接区域的颜色置换为 newcolor之后的矩阵 G。 算法步骤 (为规范算法，规定该算法只在第七步后结束 )： 第一步：若点 (i0,j0)的颜色值与新颜色值 newcolor相同，则 (1)； 第二步：点(i0,j0)的颜色值 oldcolor ；创建栈 S，并将点坐标 (i0,j
3、0)入栈； 第三步：若 (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)； 第七步：算法结束。 问题 是否可以将算法中的栈换成队列
4、 ?回答： (5)。 2 阅读下列函数说明和 C函数，将应填入 (n)处的字句写对应栏内。 说明 二叉树的二叉链表存储结构描述如下： typedef struct BiTNode datatype data; struct BiTNode *lchild, * rchild; /*左右孩子指针 */ BiTNode,* BiTree; 对二叉树进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队首取出一个元素，执行下面两个操作： (1) 访问该元素所指结点； (2) 若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入
5、队。 此过程不断进行，当队列为空时，二叉树的层次遍历结束。 下面的函数实现了这一遍历算法，其中 Visit(datatype a)函数实现了对结点数据域的访问，数组 queueMAXNODE用以实现队列的功能，变量 front和 rear分别表示当前队首元素和队尾元素在数组中的位置。 函数 void LevelOrder(BiTree bt) /*层次遍历二叉树 bt*/ BiTree QueueMAXNODE; int front,rear; if(bt= =NULL)return; front=-1; rear=0; queuerear=(1); while(front (2) ) (3)
6、; Visit(queuefront- data); /*访问队首结点的数据域 */ if(queuefront lchild!： NULL) rear+; queuerear=(4); if(queuefront- rchild! =NULL) rear+; queuerear=(5); 3 阅读以下函数说明和 C语言函数，将应填入 (n)处的字句写在对应栏内。 说明 某银行共发出 M张储蓄卡，每张储蓄卡拥有唯一的卡号，每天每张储蓄卡至多支持储蓄卡持有者的 N笔 “存款 ”或 “取款 ”业务。程序中用数组 cardMN+3中的每一行存放一张储蓄卡的有关信息，其中： cardi0存放第 i张卡
7、的卡号； cardi1存放第 i张卡的余额； cardi2存放第 i张卡的当日业务实际发生笔数； cardi3 cardiN+2存放第 i张卡的当日存取款金额，正值代表存款，负值代表取款。 当持卡者输入正确的卡号、存款或取款金额后，程序进行相应的处理；若输入不正确的数据，程序会提示持卡者重新输入；若输入的卡号为负数时，银行终止该卡的当日业务。 C程序 #include stdio.H #define M 6 #define N 5 long cardMN+3=9801,2000,0,9812,2000,2,9753,3000,1, 8750,500,0,9604,2800,3,),(8901,
8、5000,5,; int locate(long cardN+3,int m,long no) int i; for(i=0;i m;i+) if(1)=no) return i; (2); main() long cardNo,money; int k; while(1) printf(“请输入卡号 :n“); scanf(“%1d“, if(cardNo 0) break; k=locate(card,M,cardNo); if(k=-1) printf(“不存在 %id号的储蓄卡 n“,cardNo); continue; printf(“请输入金额 (正值代表存款，负值代表取款 ):n
9、“); scanf(“%id“, if(cardk1+money 0) printf(“存款余额不足 ，不能完成本次的取款业务 n“); continue; if(cardk2=N) printf(“已完成本卡的当日业务 n“); continue; /*处理一笔业务的数据 */ cardk (3)=money; (4); (5); 4 已知一棵二叉树用二叉链表存储， t指向根节点， P指向树中任一节点。下列算法为输出从 t到 P之问路径上的节点。 C程序 #define MaxSize 1000 typedef struct node TelemType data ; struct node
10、 *ichiid， *rchiid； BiNode， *BiTree； void Path(BiTree t， BiNode *P) BiTree *stackMaxsize， *stacklMaxsize,*q； int tagMaxsize， top=0， topl； q=t； /*通过先序遍历发现 P*/ dowhile(q!=NULL q!=p) /*扫描左孩子， _日相应的节点不为 P*/ (1) ； stacktop=q； tagtop=0； (2) ； if(top 0) if(stacktop=P) break； /*找到 P，栈底到栈顶为 t到 P*/ if(tagtop=1
11、)top-; else q=stacktop； q=q- rchiid; tagtop=1; (3) ； top-； topl=0； while(top 0) q=stacktop； /*反向打印准备 */ topl+； (4) ； top-; while( (5) ) /*打印栈的内容 */ q=stackltoplj printf(q- data)； topl-； 5 阅读以下应用说明及 Visual Basic程序代码，根据要求回答问题 1至问题 4。 【说明】 某学期成绩管理系统的 “增、删、改数据表中的记录 ”对话框如图 1-19所示。 图 1-19对话框中共定义了 6个标签、 6个
12、文本框、 4个命令按钮和 1个 Data数据控件。其中 Data数据控件是 Visual Basic的标准控件。利用它能方便地创建应用程序与数据库之间的连接，并实现对数据资源的访问。【添加】 (cmdAdd)按钮用于向学生成绩数据表添加一条空记录：【修改】 (cmdEdit)按钮用于修改当前所显示的一条数据记录：命令按钮【删除】 (cmdDelete)用于删除当前显示的一条数据记录；单击【退出】 (cmdExit)按钮，系统将退出图 1-19所示的对话框。 表 1-13是学生成绩表结构的示例；表 1-14是学生成绩表的示例。 图 1-19将表 1-14数据 库中的记录信息显示到相应的文本框中。
13、要在各文本框 (txtStu(i)， i=0,1,2,3,4,5)中显示 Data数据控件所连接的数据表中的数据，必须将文本框与 Data数据控件进行绑定。【 Visual Basic程序】 Private Sub Form_Load() For i = 0 To 5 txtStu(i).Locked = True Next iEnd Sub Private Sub cmdAdd Click() cmdEdit.Enabled = Not cmdEdit.Enabled (1) For i = 0 To 5 txtStu(i) .Locked = Not txtStu(i).Locked Ne
14、xt i If cmdAdd. Caption = “添加 “ Then (2) Datal.Caption = “新记录 “ cmdAdd.Caption = “保存 “ cmdExit.Caption = “取消 “ txtStu(0).SetFocus Else Datal.Recordset.Update (3) cmdAdd.Caption = “添加 “ End IfEnd SubPrivate Sub cmdEdit_Click() cmdAdd. Enabled = Not cmdAdd. Enabled cmdDelete. Enabled = Not cmdDelete.
15、Enabled For i = 0 To 5 txtStu(i).Locked = Not txtStu(i).Locked Next i If cmdEdit.Caption = “修改 “ Then Datal.Recordset.Edit cmdEdit.Caption = “保存 “ cmdExit.Caption = “取消 “Else (4) cmdEdit.Caption = “修改 “ End IfEnd SubPrivate Sub cmdDelete_Click() answer = MsgBox(“确实删除该记录吗 ?“, vbYesNo + vbQuestion, “警
16、告 “) If answer = vbYes Then Datal.Recordset.Delete (5) If Datal.Recordset.EOF Then (6) End If End IfEnd Sub Private Sub cmdExit_Click() If cmdExit.Caption = “退出 “ Then End Else (7) cmdAdd. Enabled= True cmdEdit.Enabled = True cmdDelete. Enabled= True For i = 0 To 5 txtStu(i).Locked = Not txtStu(i).L
17、ocked Next i cmdExit.Caption = “退出 “ cmdAdd.Caption = “添加 “ cmdEdit.Caption = “修改 “ (8) End IfEnd SubPrivate Sub Datal_Reposition() Datal.Caption = “第 “ /初始化构造函数 int seek(T c); void disp( ) for(int i=0;i n;i +) cout Ai “ “; cout endl: template class T Sample T : :Sample(T a ,int i) n=i: for( intj =0
18、;j i;j + ) (1); template class T int Sample T : seek( T c) int low =0,high = n-1 ,mid; while(2) mid = (low + high)/2; if(3) return mid; else if( (4) ) low=mid+|; else (5); return-1; void main( ) char a =“acegkmpwxz“; Sample char s(a, 1); cout “元素序列 :“ ;s. disp( ); cout “元素 g的下标 :“ s. seek(g) endl; 1
19、0 阅读以下说明， Java代码将应填入 (n)处的字句写在对应栏内。 【说明】 链表和栈对象的共同特征是：在数据上执行的操作与在每个对象中实体存储的基本类型无关。例如，一个栈存储实体后，只要保证最后存储的项最先用，最先存储的项最后用，则栈的操作可以从链表的操作中派生得到。程序 6-1实现了链表的操作，程序 6-2实现了栈操作。 import java.io.*; class Node /定义结点 private String m_content; private Node m_next; Node(String str) m_content=str; m_next=null; Node(St
20、ring str,Node next) m_content=str; m_next=next; String getData() /获取结点数据域 return m_content; void setNext(Node next /设置下一个结点值 m_next=next; Node getNext() /返回下一个结点 return m_next; ) 【程序 6-1】 class List Node Head; List() Head=null; void insert(String str) /将数据 str的结点插入在整个链表前面 if(Head=null) Head=new Node
21、(str); else (1) void append(String str) /将数据 str的结点插入在整个链表尾部 Node tempnode=Head; it(tempnode=null) Heed=new Node(str); else white(tempnode.getNext()!=null) (2) (3) String get() /移出链表第一个结点，并返回该结点的数据域 Srting temp=new String(); if(Head=null) System.out.println(“Errow! from empty list!“) System.exit(0);
22、 else temp=Head.getData(); (4) return temp; 【程序 6-2】 class Stack extends List void push(String str) /进栈 (5) String pop() /出栈 return get(); 软件水平考试（初级）程序员下午（应用技术）模拟试卷 48答案与解析 1 【正确答案】 (1)转第七步 ;(2)栈为空 ;(3)newcolorGx,y;(4) 转第三步 ;(5)可以 2 【正确答案】 (1) bt (2) ! =rear (3) front+ + (4) queue front- lchild (5)
23、queuefront- rchild 【试题解析】 (1)遍历开始时队列长度为 1，其中只存放了根结点 bt； (2)遍历过程是一个循环访问队列的过程，其终止条件是队列为空，即 front等于rear； (3)遍历到某结点时，该结点应退出队列，因此队首元素的位置应该增 1； (4)此处应将队首结点的左孩子结点放入队列，即插在队尾； (5)此处应将队首结点的右孩子结点放入队列，即插在队尾。 3 【正确答案】 (1) cardi0 (2) return-1 (3) cardk2+3 (4) cardk1+=money (5) cardk2 【试题解析】 按照程序的说明，函数 Locate是对用户输
24、入的卡号进行比较，当找到对应的卡号，则返回持卡者对应的记录号，否则返回 -1。 cardi0中存放着第 i张卡的卡号，所以 (1)填 “cardi0”， (2)填 “return-1”。当找到持卡者的卡号为k时，由于 cardk2存放实际的交易次数，因此这次发生的交易数应该存放的位置为 cardkcardk2+3，即 (3)填 “cardk2+3”。在交易发生后，存款额要发生改变，即 (4)填 “cardk1+=money”，同时其交易次数增 1， (5)填 “cardk2”。 4 【正确答案】 (1)top+ (2) q=q- lchild (3) while(top 0) (4) stac
25、kltopl=q (5) topl 0 【试题解析】 本题本质上是对二叉树的先序遍历进行考核，但不是简单地进行先序遍历，而是仅遍历从根节点到给定的节点 p为止。本题采用非递归算法 来实现，其主要思想是： 初始化栈； 根节点进栈，栈不空则循环执行以下步骤直到发现节点 p； 当前节点不为空且不为 P进栈； 栈顶为 p，则结束，否则转 ； 若右子树访问过，则栈顶的右孩子为当前节点，转 。 扫描左孩子，当相应的节点不为 P时进栈，所以 (1)填 “top+”， (2)填 “q=q-lchild”。在栈不为空时则一直在 do while循环中查找，因此 (3)填 “while(top0)”。在进行反向打
26、印准备时，读取 stacktop的信息放到 stackltopl中，即 (4)填“stackltop1=q”。打印栈中所有内容，所以 (5)填 “topl 0”。 5 【正确答案】 (1)H或 cmdDelele.Enabled = Not cmdDelete.Enabled (2)E或 Datal.Recordset.AddNew (3)G或 Datal.Recordset.MoveLast (4)B或 Datal.Recordset.Update (5)F中 Datal.Recordset.MoveNext (6)G或 Datal.Recordset.MoveLast (7)D或 Data
27、l.Recordset.CancelUpdate (8)A或 Datal.Refresh (9)C或 DataI.Recordset 【试题解析】 这是一道要求读者掌握用 Data数据控件访问数据库的综合应用题。本题的解答思路如下。 Data数据控件是 Visual Basic的标准控件。利用它能方便地创建应用程序与数据库之间的连接，并实现对数据资源的访问。为了在程序运行时，使 Data数据控件能够访问指定表中的记录信息，应设置该控件的DatabaseName属性和 RecordSource属性。要在图 1-19各文本框中显示 Data控件 所连接的数据表中的数据，必须将文本框与 Data数据
28、控件进行绑定。 本程序开始部分，通过以下语句设置文本框不可编辑，使某条记录成为当前记录后，触发此事件。 For i = 0 TO 5 txtStu(i).Locked = True Next i 在程序运行中，应注意各命令按钮之间的互相制约关系。例如，单击【添加】按钮后，不允许再单击【修改】、【删除】等按钮。因此本案例在【添加】按钮的 Click事件中，用“cmdEdit.Enabled = Not cmdEdit.Enabled”、“cmdDelete.Enabled=NotcmdDelete.Enabled”等语句分别实现【修改】、【删除】按钮不可用状态的设置。因此 (1)空缺处所选择的语
29、句是选项 H的“cmdDelete.Enabled=Not cmdDelete.Enabled”。 对于添加记录的操作，需单击两次【添加】按钮才能完成。第 1次单击该按钮时，执行 (1)空缺处的语句。而该语句所要完成的功能是将一条空记录添加到记录集的末尾，因此 (2)空缺处所选择的语句是选项 E的 “Datal.Recordset.AddNew”。由语句 “txtStu(i).Locked=Not txtStu(i).Locked”可知，第 1次单击【添加】按钮后，就可以在文本框(txtStu(i),i=0,1,2,3,4,5)中输入各字段的数值。 第 2次单击【添加】按钮时，执行语句 “Da
30、tal.Recordset.Update”，其作用是确认添加操作后，再将新记录添加到数据库中。通常，新添加的记录是数据表中的最后一条记录，因此 (3)空缺处语句所要完成的功能是，将记录指针移到最后一条记录上，即该空缺处所选择的语句是选项 G的 “Datal.Recordset.MoveLast”。 对于修改记录中的 语句“Datal.Recordset.Edit”，其作用是调用 Recordset的 Edit方法，使当前记录成为可编辑的状态。在完成修改操作后，还需执行语句 “Datal.Recordset.Update”，以确认所要做的修改操作，即 (4)空缺处所选择的语句是选项 B的“Dat
31、al.Recordset.Update”。 对于删除记录的操作，删除当前记录的语句是“Datal.Recordset.Delete”。删除当前记录后应使下一条记录成为当前记录，因此 (5)空缺处所选择的语句是选项 F的 “Datal.Recordset.MoveNext”。 删除当前记录后，如果记录指针指向最后一条记录的后面，则需要重新将记录指针移动到最后一条记录上，使之成为当前记录。语句 “If Datal.Recordset.EOF Then”用于判断记录指针是否指向最后一条记录的后面。其中， EOF是 Recordset的一个属性，当值为True时，表明记录指针已移到最后一条记录的后面。
32、 (6)空缺处语句所要完成的功能是，使最后一条记录成为当前记录，即该空缺处所选择的语句是选项 G的“Datal.Recordset.MoveLast”。 (7)空缺处语 句所要完成的功能是放弃添加的新记录(或对数据的修改 )，选择的语句是选项 D的 “Datal.Recordset.CancelUpdate”。取消所添加的新记录 (或对数据修改 )的操作后，还需要刷新与 Datal相连接的记录集，同时把记录集中的第一条记录设置为当前记录。因此， (8)空缺处所选择的语句是选项 A的 “Datal.Refresh”。 最后 (9)空缺处所选择的语句用于设置当前记录数，即选项 C的 “Datal.
33、Recordset”。在 Datal的 Reposition事件中， Recordset是Datal控件所控 制的记录集对象，通过此对象对数据表中的记录进行浏览和操作。访问数据库的记录集可用 Datal.Recordset实现。 另外补充说明一点，对于本试题中，学生成绩表的建立步骤如下。 1)启动数据管理器，选择【外接程序】 【可视化数据管理器】命令。 2)建立数据库，即单击工具栏中的【数据库窗口】按钮。 3)建立数据表结构。在数据库窗口中单击鼠标右键，从弹出的快捷菜单中选择【新建表】命令，打开如图 1-21所示的 “表结构 ”对话框。 “表名称 ”栏输入：学生成绩表。按表 1-13给出的学生
34、成绩表结构定义表中的各个字段。 4)编辑数据表中的数据。在数据库窗口的数据表名处单击鼠标右键，从弹出的快捷菜单中选择【打开】命令。在打开的记录操作对话框按表 1-14所给出的信息添加各个学生的成绩。 6 【正确答案】 (10)D或 bas 【试题解析】 Visual Basic应用程序有 4种类型的文件，包括单独的窗体文件、标准模块文件、类模块文件和工程文件。单独的窗体文件的扩展名为 frm；公用标准模块文件的扩展名为 bas；类模块文件的扩展名为 cls；工程文件的扩展名为vbp。工程文件由若干个窗体和模块组成。 7 【正确答案】 将【 退出】按钮的 Caption属性设置为 “退出 ( (
35、2)tempnode=tempnode.getNext(); (3)tempnode.setNext(new Node(str,tempnode.getNext(); (4)Head=Head.getNext()； (5)insert(str); 【试题解析】 本题考查链表和栈的基本特征在 Java中的实现。 在对链表进行表头插入时，首先要判断该链表是否为空，如果为空，直接插入结点；如果非空，在插入结点时把该结点的指针域改成能指向下一个结点的地址。在队尾插入时，同样要判断该链表是否为空，如果为空，直接插入结点；如果非空，在 插入结点时把上一个结点的指针域改成能指向该结点的地址。 下面来具体分析
36、代码，首先定义了一个结点类，类中有两个不同的构造函数和三个函数，分别用于获取结点数据域，设置下一个结点值和返回下一个结点值。第 (1)空是函数 insert()里面的代码，函数要实现的功能是将数据 str的结点插入在整个链表前面。结合整个函数看，此空处要实现的功能是在非空链表的前面插入结点，需要指针域来存放下一个结点的地址，而下一个结点的地址就是 Head，因此，此处应该填 Head=new Node(str,Head)。 第 (2)空 和第 (3)空一起考虑，它们都是函数 append()里面的内容。函数要实现的功能是将数据 str的结点插入在整个链表尾部。这两空要实现的功能是在非空链表的尾
37、部插入结点。这需要调用返回下一个结点值函数和设置下一个结点值函数，因此，第 (2)空和第 (3)空的答案分别为 tempnode=tempnode.getNext()和tempnode.setNext(new Node(str,tempnode.getNext()。 第 (4)空是函数 get()里面的内容，此函数的功能是移出链表第一个结点，并返回该结点的 数据域，从整个函数来看，此空处的功能是让链表的地址 Head指向下一个结点。因此，答案为 Head=Head.getNext()。 第 (5)空就比较简单了，要实现的功能就是让数据进栈，而进栈操作是在栈顶进行插入的，因此，只要调用函数 insert()即可，其参数是 str，此空答案为insert(str)。
