1、软件水平考试（初级）程序员下午（应用技术）模拟试卷 41 及答案与解析 1 阅读以下说明和流程图，回答问题将解答填入对应栏。 说明 本流程图采用 “双向冒泡法 ”实现对数组 an的排序。双向冒泡法就是在逐步缩小的数组内，分别从数组的两端开始向内搜索，同时将大数往上浮，小数往下沉，每次交换一组数。flag是一个标志，发生过交换就置为 1，当这个循环过程都不再发生交换时，则数组排序完成。 注：流程中循环开始的说明按照 “循环变量：循环初值，循环终值，增量 ”格式描述； 定义 swAPa,b为将 a和 b两数交换。 问题 将流程图的 (1) (5)处补充完整。 2 阅读以下函数说明和 C语言函数，将
2、应填入 (n)处的字句写在对应栏内。 说明 1 L为一个带头结点的循环链表。函数 LinkList deletenode(LinkList L,int c)的功能是删除 L中数据域 data的值大于 C的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。 C函数 1 LinkList deletenode(LinkList L,int c) LinkList Lc,P,pre; pre=L; p=(1); Lc=(LinkList)malloc(sizeof(Listnode); Lc- next=Lc; while(P!=L) if(p- data C) (2
3、); (3); Lc- next=p; p=pre- next; else pre=p; p=pre- next; return Lc; 说明 2 递归函数 dec_to_k_2(int n,int k)的功能是将十进制正整数 n转换成 k(2k9)进制数，并打印。 C函数 2 dec to k 2(int n,int k) if(n!=O) dec to k 2( (4) ,k); printf(“%d“, (5) ); 3 阅读以下函数说明和 C语言函数，将应填入 (n)处的字句写在对应栏内。 说明 函数 int psort(int a,int n)实现将含 n个整数的数组 a的不同元素按
4、从小到大顺序存于数组 a中。实现方法是从未确定的元素列中找到最小元素并将 a的第 i最小元素交换至 ai位置。如该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面；否则，忽视该元素。 C函数 int psort(int a,int n) int i,J,k,P; for(i=0,k=0;i (1);i+) for(j=i+1, (2) ;j n; j+) if(ap aj) p=j; if(p!=i) t=ap; ap=ai; ai=t; if( (3) ) k+; else if( (4) ai) (5)=ai; return k; int a=5,7,5,6,4,3,
5、4,6,7; main() int k,n; for(k=0;k (Sizeof a)/Sizeof(int);k+) printf(“%5d“,ak); printf (“nn“); n=psort(a,(sizeof(a)/sizeof(int); for(k=0;k n;k+) printf(“%5d“,ak); printf(“nn“); 4 阅读以下函数说明和 C语言函数，将应填入 (n)处的字句写在对应栏内。 说明 这是一个求解 Josephus问题的函数。用整数序列 1， 2， 3 ， n表示顺 序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。 Josephus
6、问题描述，设 n个人围坐在一个圆桌周围，现在从第 s个人开始报数，数到第 m个人，让他出局；然后从出局的下一个人重新开始报数，数到第 m个人，再让他出局， 如此反复直到所有的人全部出局为止。 C函数 void Josephus(int A,int n,s,m) (int i,j,k,temp; if(m=O) printf(“m=0是无效的参数 !n“); return; for(i=0;i n;i+) Ai=i+1; /*初始化，执行 n次 */ i= (1) /*报名起始位置 */ for(k=n;k 1;k-) if(2) i=0; i=(3) /*寻找出局位置 */ if(i!=k-1
7、) tmp=Ai; for(j=i;J k-1;j+) (4); (5); for(k=0;k n/2;k+) tmp=Ak;Ak=An-k+1;An-k+1=tmp; 5 阅读以下说明和 C+程序，将应填入 (n)处的字句写在对应栏内 说明 以下程序的功能是计算三角形、矩形和正方形的面积并输出。 程序由 4个类组成：类 Triangle， Rectangle和 Square分别表示三角形、矩形和正方形；抽象类 Figure提供了一个纯虚拟函数 getArea()，作为计算上述三种图形面积的通用接口。 C+程序 #include iostream.h #include math.h class
8、 Figure public: virtual double getArea()=0; /纯虚拟函数 ; class Rectangle: (1) protected: double height; double width; public: Rectangle(); Rectangle(double height,double width) This- height=height; This- width=width; double getarea() return (2); ; class Square: (3) public: square(double width) (4); ; cl
9、ass triangle: (5) double la; double lb; double lc; public: triangle(double la,double lb,double lc) this- la=la;thiS- ib;this- lc; double getArea() double s=(la+lb+lc)/2.0; return sqrt(s*(s-la)*(s-lb)*(s-lc); ; viod main() figure*figures3= new triangle(2,3,3),new Rectangle(5,8),new Square(5); for(int
10、 i=0; i 3;i+) cout “figures“ i “area=“ (figures)- getarea() endl; ; 6 阅读以下说明和 Java程序，将应填入 (n)处的字句写在对应栏内。 说明 下面程序输出一个矩形面积，以及矩形区域上的假想的作物产量。 Java程序 public class MainJava public static void main(String args) Lot_size small=new Lot_size(); Lot_size medium=new Lot_size(); small.set(5,5,5， 25); medium.set(
11、10,10,10,50); System.out.println(“For a small lot of area“ +small.get_area()+“n“); System.out.println(“the actual crops are $“ +small.get_data2()+“n“); System.out.println(“and ideal crops are $“ +small.get data()+“n“); System.out.println(“For a medium lot of area“ +medium.get_area()+“n”)； System.out
12、.println(“the actual crops are $“ +medium.get_data2()+“n“); System.out.println (“and ideal crops are $“ +medium.get_data()+“n“); class Crop_assessment private int actual_crop; private int ideal_crop; public void set(int in_actual,int in ideal) actual_crop=in_actual; ideal_crop=in_ideal; public int g
13、et_actual_crop()return (1) ; public int get_ideal_crop()(return (2) ; class Lot_size private int length; private int width; private Crop_assessment crop= (3) ; public void set(int 1,int W,int a,int i) length=1; width=W; crop.set(a,i); public int get_area()return length*width; public int get_data()fr
14、eturn (4) ; public int get_data2()(return (5) ; 软件水平考试（初级）程序员下午（应用技术）模拟试卷 41 答案与解析 1 【正确答案】 (1) left right&flag=l； (2) left,right-1,1； (3) ai ai+1； (4) flag=1； (5) aRight-i aRight-i-1 【试题解析】 本题目考查的是流程图。 先题目中已经给出算法说明，是分别从数组的两端同时向内搜索，每次交换一组数，所以，可以判断， (1)中的条件应该由两部分组成，首先是 left right，因为这样才能构成一个数组，第二个条件是
15、flag=1，如果它成立，则说明还有交换，要继续排序，如果 flag=0，则说明没有交换了，排序完成，所以 (1)要填入 “leftright&fla=1”。内循环开始，从数组两端，两两比较数的大小，所以 (2)应填入“left,right-1,1”，在 left端 ，当 ai ai+1时，将两数交换，交换后将 flag置 1，即 (3)填入 “ai ai+1”， (4)填入 “flag=1”；在 right 端，当 aRight-i aRight-i-1时，将两数交换， flag 置 1，所以 (5)应填入 “aRight-i aRight-i-1”。 2 【正确答案】 (1) pre- n
16、ext或 L- next (2) pre- neXt=p- next (3) p-next=Lc- next (4) n/k (5) n%k 【试题解析】 函数 1是考察链表的删除和插入的操作。 (1)空所在语句是对指针 P赋初值，应填 “pre- next”或 “L- next”，通过下面的程序可以判断指针 pre所指的结点是指针 p 所指结点前驱结点。 (2)、 (3)空所在的语句块是处理当指针 p 所指的结点是一个大于 C的结点，则将该结点从链表 L 中删除，再将它插入到链表 Lc中。分别填 “pre- next=p- next”和 “p- next=-Lc- next” 。 函数 2是
17、一个递归函数，采用除 k取余法。最开始得到余数作为 k进制数的最低位，最后得到的余数作为 k 进制数的 最高位。用递归法求解时，先将 n/k转换成 k进制，再输出 n%k。因此 (4)填 “n/k”， (5)填 “n%k”。 3 【正确答案】 (1) n-1 (2) P=i (3) k=0 (4) ak-1 (5) ak+ 【试题解析】 本程序排序方法是从未确定的元素列中找到最小元素并将 a的第 i最小元素交换至 ai位置。如该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面；否则，忽视该元素。这是采用选择法对数组元素进行排序，因此空 (1)填 “n-1”， 空 (2)填
18、 “p=i”。若该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面；否则，忽视该元素。因此，空 (3)填 “k=0”；而当 ak-1 ai时 ”，则 ak+=ai；否则忽略元素 ai。所以空 (4)填 “ak-1”空 (5)填 “ak+”。 4 【正确答案】 (1) s-1 (2) i=k (3) (i+m-1)%k (4) Aj=Aj+1 (5) Ak-1=tmp 【试题解析】 JosephuS 问题是一个经典的顺序 表问题，所用到的数据结构就是一维数组。整个算法过程实际上就是一个从 n到 1的循环。当还剩下 k 个人的时候，首先找到出局位置，然后将出局者交换到第 k-
19、1位置。循环结束，将数组逆置，即得到出局序列。空 (1)是赋报名起始位置，应填 “s-1”： (2)填 “i=k”。空 (3)是寻找出局位置，应填 “(i+m-1)%k”。数组 A 的元素要循环向右移动一个位置，则 (4)填 “Aj=Aj+1(5)填 “Ak-1=tmp”。 5 【正确答案】 (1) public Figure (2) height*width (3) public Rectangle (4) this- height=this- width=width (5) public Figure 【试题解析】 本题考查 C+编程中的几个重要概念。 Figure类是一个抽象类，其他三个
20、类 rectangle、 square、 triangle都要直接或间接继承该类，所以 (1)(5)处应为 “public Figure”。 (2)处是要计算矩形面积，矩形面积等于长乘以宽，所以 (2)处应为 “height* width”。正方形是一个特殊 的矩形，所以可以继承矩形类，所以 (3)处应为 “publicRectangle”， (4)处应为 “this-height=this- width=width”。 6 【正确答案】 (1) return actual_crop (2) return ideal_crop (3) new Crop_assessment() (4) cro
21、p.get_ideal_crop (5) crop.get_actual_crop() 【试题解析】 本题以 Java语言为载体，考查面向对象程 序设计中的几个重要概念 类的嵌套及函数的使用。 本题的功能是通过已定义的粮食收成类定义了一个计算特定矩形域上粮食收成的类，在主函数中定义了两个对象，并调用了相应的函数，来输出理想和实际的粮食产量。 首先，由于 Crop assessment定义的成员数据缺省为私有的，所以想要获得实际和理想的粮食产量，要通过两个公有成员函数，所以 (1)处应填入 “return actual_crop”， (2)处应填入 “return ideal_crop”。 其次，在类 Lot size中，由于我们要反映矩形域上的粮食产 量，所以我们在类中嵌套定义了一个类， Java中对象需要实例化，故 (3)应填入 “new Crop_assessment()”。 最后，由于我们想通过 Lot_size类中的 get_data和 get_data2函数得到粮食产量，但由于这两个成员数据是私有函数，所以我们必须通过定义的对象调用它，所以 (4)应填入 “crop.get_ideal_crop()”， (5)应填入 “crop.get_actual_crop()”。
