201711程序员下午真题

第 1 题

阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
【说明】
对于大于1的正整数n，(x+1)n可展开为
下面流程图的作用是计算(x+1)n展开后的各项系数（i=0,1,....,n）并依次存放在数组A[0...n]中。方法是依次计算k=2，3，..，n时(x +1)k的展开系数并存入数组A，在此过程中，对任一确定的k，利用关系式 ，按照i递减的顺序逐步计算并将结果存储在数组A中。其中，和都为1，因此可直接设置A[0]、A[k]的值为1。
例如，计算(x+1)3的过程如下：
先计算 (x+1)2 ( 即k=2) 的各项系数，然后计算(x+1)3(即k=3)的各项系数。
K=2时，需要计算，和，并存入A[0] ，A[1]和A[2]，其中A[0]和A[1]的值已有，因此将（即 A[1]）和即 (A[0])相加得到的值并存入A[1]。
k=3 时，需要计算，和和，先计算出(由)得到并存入A[2]，再计算(由得到)并存入A[1]。

【流程图】

注：循环开始框内应给出循环控制变量的初值和终值，默认递增值为1。
格式为：循环控制变量=初值，终值，递增值。

答案与解析

  • 试题难度：较难
  • 知识点：流程图>流程图
  • 试题答案：（1）2，n，1
    （2）A[k]
    （3）k-1，1，-1
    （4）A[i]+A[i-1]
    （5）A[i]
  • 试题解析：（1）（3）空为填写循环初值终值和递增值，题目中给出的格式为循环控制变量=初值，终值，递增值。按照题意，实质为求杨辉三角。如下图：
    计算方式为从第2行计算迭代到计算第3行，再根据第3行值求取第4行，直到计算到第n行。所以第一空填2，n，1。
    而对于每行的求取，第1项结果一直为1，最大项一直是1，可以直接赋值，所以第二空填A[k]。
    然后从倒数第二项开始计算，依次往前计算。
    所以第三空的填k-1，1，-1。因为：，故有A[i]=A[i]+A[i-1]。（注意A[i]+A[i-1]保留的k-1行的结果）。

第 2 题

试题二（共15分）
阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
对n个元素进行简单选择排序的基本方法是：第一趟从第1个元素开始，在n个元素中选出最小者，将其交换至第一个位置，第二趟从第2个元素开始，在剩下的n-1个元素中选出最小者，将其交换至第二个位置，依此类推，第i趟从n-i+1个元素中选出最小元素，将其交换至第i个位置，通过n-1趟选择最终得到非递减排序的有序序列。

【代码】

include   <stdio.h>

void selectSort(int data[ ],int n)
//对 data[0]~data[n-1]中的n个整数按非递减有序的方式进行排列
{
     int i,j,k;
     int  temp;
     for(i=0;i<n-1;i++){        
          for(k=i,j=i+1;（1）;（2）)         //k表示data[i]~data[n-1]中最小元素的下标
              if(data[j]<data[k])   （3）    ;      
          if(k!=i) {
             //将本趟找出的最小元素与data[i]交换
               temp=data[i]; （4） ;data[k]=temp;
           }
      }
}

int main()
{
       int arr[ ]={79,85,93,65,44,70,100,57};
       int i,m;
       m=sizeof(arr)/sizeof(int);             //计算数组元素的个数，用m表示
       （5）;                                         //调用selectSort对数组arr进行非递减排序
       for(（6）;i <m;i++)                      //按非递减顺序输出所有的数组元素             
             printf("%d\t",arr[i]);
       printf("\n");
       return 0;
}</m;i++)></data[k])></n-1;i++)></stdio.h>

答案与解析

  • 试题难度：较难
  • 知识点：C程序设计>C程序设计
  • 试题答案：（1）j<n或者j<=n-1
    （2）j++
    （3）k=j
    （4）data[i]=data[k]
    （5）selectSort(arr,m)此处m也可以填8或者sizeof(arr)/sizeof(int), arr可以改成&arr[0]
    （6）i=0
  • 试题解析：本题考查 C 程序设计基本技能及应用。简单选择排序方法是设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录（Ri,Ri+1,…,Rn）中找出排序码最小的记录，与第i个记录交换。执行n-1趟后就完成了记录序列的排序。
    第1空应填j循环结束条件，j应该运行至序列末尾。填j<n或者j<=n-1；
    第2空填j循环控制语句，j每次递增1，往后移动一个元素与a[i]进行比较。
    第3空为自动保存最大元素的下标，k=j。
    第4空为交换两个元素，temp为临时变量，保存data[i]的值，使用data[i]=data[k]使data[i]为后面n-i+1个记录（Ri,Ri+1,…,Rn）中找出排序码最小的记录，再将temp赋给data[k]。
    第5空为调用selectSort对数组arr进行非递减排序，selectSort有两个参数，数组和排序元素个数，为selectSort(arr,m)。
    第6空进行元素遍历输出所有的数组元素，从下标为0开始，所以填i=0。

第 3 题

试题三（共15分）
阅读以下代码和问题，回答问题1至问题3，将解答填入答题纸的对应栏内。
 【代码 1】
typedef enum {A，B，C，D} EnumType;
EnumType  f(int yr)
{
       if(0 == yr%400) {
               return A;
       }
       else 

            if (!(yr%4)) {
                   if(0!=yr%100)
                       return B;
                   else
                       return C;
           }
       return D;
}

【代码2 】

include<stdio.h>

int  main()
{       int score;
        scanf("%d"，&score);
        switch (score)
        {
              case 5: printf("Excellent!\n");
              case 4: printf("Good!\n");  break;
              case 3: printf("Average!\n");
              case 2:
              case 1:
              case 0: printf("Poor!\n");
              default: printf("Oops,Error\n");
        }
        return 0;
}

【代码3】

include<stdio.h>

int  main()
{     int i,j,k;
             for(i=0; i<2; i++)
                  for(j=0; j<3;j++)
                     for( k=0; k<2;k++)  {
                            if(i!=j&&j!=k)
                                  printf("%d %d %d\n", i,j,k);
                     }
       ruturn 0;
}
 </stdio.h></stdio.h></div>

【问题1 】（4分）
对于代码1，写出下面的函数调用后x1 、x2、x3和x4的值。
x1 = f(1997);
x2 = f(2000);
x3 = f(2100);
x4 = f(2020);


【问题2】（5分）
（1）写出代码2进行时输入为3的输出结果；
（2）写出代码2进行时输入为5的输出结果。
 
【问题3】（6分）
写出代码3运行后的输出结果。</stdio.h></stdio.h>

答案与解析

  • 试题难度：较难
  • 知识点：C程序设计>C程序设计
  • 试题答案：问题1：x1=3;x2=0;x3=2;x4=1
    问题2：
    （1）Average！
             poor！
             Oops，Error
    （2）Excellent！
             Good！
    问题3：
    0 1 0
    0 2 0
    0 2 1
    1 0 1
    1 2 0
    1 2 1
  • 试题解析：对于问题1：
    第一个条件  0==yr%400， 2000满足，返回为A；其余都不满足，继续进行判断；
    第二个条件  ！yr%4， 1997不满足，返回为D；其余满足，继续进行判断；
    第三个条件  0！=yr%100，2020满足，返回为B；2100不满足，返回为C。
    枚举类型中列出的每一个枚举符都对应着一个整数值，枚举类型实际上是一个整型符号常量的集合。当定义枚举类型时，枚举符都已经被系统隐含地赋予了一个整型值，默认情况下，第一个元素为0，第二个元素为1，依此类推。所以相应的A=0，B=1，C=2，D=3，故返回为：x1=3;x2=0;x3=2;x4=1。

    对于问题2：

    控制传递给与开关的值匹配的 case 语句。switch 语句可以包括任意数目的 case 实例，但是任何两个 case 语句都不能具有相同的值。语句体从选定的语句开始执行，直到 break 将控制传递到 case 体以外。case后面的常量表达式实际上只起语句标号作用，而不起条件判断作用，即"只是开始执行处的入口标号". 因此，一旦与switch后面圆括号中表达式的值匹配，就从此标号处开始执行，而且执行完一个case后面的语句后，若没遇到break语句，就自动进入 下一个case继续执行，而不在判断是否与之匹配，直到遇到break语句才停止执行，退出break语句.因此，若想执行一个case分之后立即跳出 switch语句，就必须在此分支的最后添加一个break语句。

    对于问题三：
    此题考查多重for循环再加上一个判定条件，i的取值为（0，1），j的取值为（0，1，2），k的取值为（0，1），只要按顺序找到i！=j且j！=k的组合即可。

第 4 题

试题四（共15分）
阅读以下说明、C函数和问题，回答问题1和问题2将解答填入答题纸的对应栏内。
【说明】
当数组中的元素已经排列有序时，可以采用折半查找（二分查找）法查找一个元素。下面的函数biSearch(int r[]，int low，int high，int key)用非递归方式在数组r中进行二分查找，函数biSearch_rec(int r[]，int low，int high，int key)采用递归方式在数组r中进行二分查找，函数的返回值都为所找到元素的下标；若找不到，则返回-1。
 
【C 函数 1】
int biSearch(int r[]，int low，int high，int key)
//r[low..high] 中的元素按非递减顺序排列
//用二分查找法在数组r中查找与key相同的元素
//若找到则返回该元素在数组r的下标，否则返回-1
{
    int mid;
    while(（1）) {
         mid = (low+high)/2 ;
         if (key ==r[mid])
                return mid;
         else if (key<r[mid])
                 （2）;
         else
                 （3）;
    }/while/
    return -1;
}/biSearch/

【C 函数 2】
int biSearch_rec(int r[]，int low，int high，int key)
//r[low..high]中的元素按非递减顺序排列
//用二分查找法在数组r中查找与key相同的元素
//若找到则返回该元素在数组r的下标，否则返回-1
{
    int mid;
    if(（4）) {
         mid = (low+high)/2 ;
         if (key ==r[mid])
                return mid;
         else if (key<r[mid])
                     return biSearch_rec(（5）,key);
         else
                     return biSearch_rec(（6）,key);
    }/if/
    return -1;
}/biSearch_rec/

【问题1 】（12分）
请填充C函数1和C函数2中的空缺，将解答填入答题纸的对应栏内。
【问题2 】（3分）
若有序数组中有n个元素，采用二分查找法查找一个元素时，最多与（  ）个数组元素进行比较，即可确定查找结果。
（7）备选答案：
A.[log2(n+1)]        B.[n/2]        C.n-1        D.n

答案与解析

  • 试题难度：较难
  • 知识点：C程序设计>C程序设计
  • 试题答案：（1）low<=high
    （2）high=mid-1
    （3）low=mid+1
    （4）low<=high
    （5）r,low,mid-1
    （6）r,mid+1,high
    （7）A
  • 试题解析：本题考查折半查找。二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好，占用系统内存较少；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
    二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x。
    总共有n个元素，渐渐跟下去就是n,n/2,n/4,....n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。

第 5 题

试题五（共15分）
阅读以下说明和Java代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
以下Java代码实现一个超市简单销售系统中的部分功能，顾客选择图书等物件（Item）加入购物车（ShoppingCart），到收银台（Cashier）对每个购物车中的物品统计其价格进行结账。设计如图5-1所示类图。 


图5-1类图

【Java代码】
interface Item{
    public void accept(Visitor visitor);
    public double getPrice();
}

class Book  （1）{
    private double price;
    public Book(double price){（2）;}
    public void accept(Visitor visitor){    //访问本元素
          （3）;
    }
    public double getPrice() {
         return price;
    }
}
//其它物品类略

 interface Visitor {
        public void visit(Book book);
        //其它物品的visit方法
}

 class Cashier（4）{
        private  double totalForCart;
        //访问Book类型对象的价格并累加
     （5）{
           //假设Book类型的物品价格超过10元打8折
             if(book.getPrice()<10.0）{
                  totalForCart+=book.getPrice();
             } else
                   totalForCart+=book.getPrice()*0.8;
        }
    //其它visit方法和折扣策略类似，此处略

    public double getTotal() {
        return totalForCart;
    }
}
 
class ShoppingCart {
     //normal shopping cart stuff
     private java.util.ArrayList<Item>items=new java.util.ArrayList<>();
     public double calculatePrice() {
          Cashier visitor=new Cashier();

          for(Item item:items) {
                  （6）;
          }
          double total=visitor.getTotal();
          return total;
     }
     public void add(Item e) {
         this.items.add(e);
     }
}

答案与解析

  • 试题难度：较难
  • 知识点：Java程序设计>Java程序设计案例
  • 试题答案：（1）implements Item
    （2）this.price=price
    （3）visitor.visit(this)
    （4）implements Visitor
    （5）public void visit(Book book)
    （6）item.accept(visitor)
  • 试题解析：这里考查的是访问者模式。其定义如下：封装某些作用于某种数据结构中各元素的操作，它可以在不改变数据结构的前提下定义作用于这些元素的新的操作。<br /> 第一、四空为接口与实现，接口使用Interface，实现使用implements。第二空this表示类实例本身。第三空为访问本元素。第五空实现接口里面的方法。第六空调用accept方法。


第 6 题

试题六（共15分）
阅读下列说明和C++代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明 】
以下C++代码实现一个超市简单销售系统中的部分功能，顾客选择图书等物品（Item）加入购物车（ShoppingCart），到收银台（Cashier）对每个购物车中的物品统计其价格进行结账，设计如图6-1所示类图。


图6-1  类图

【C++代码】
using namespace std;
class Book;
class Visitor {
public:
        virtual void visit(Book book)=0;
        //其它物品的visit方法
};
 
class Item {
public:virtual void accept(Visitor visitor)=0;
          virtual double getPrice()=0;
};

class Book （1）{
private:    double price;
public:
        Book (double price){ //访问本元素
                       （2）;
        }
        void accept(Visitor visitor) {
                       （3）;
        }
        double getPrice() {         return price;        }
};
class Cashier（4）{
private;
        double totalForCart;
public:
        //访问Book类型对象的价格并累加
        （5）{
            //假设Book类型的物品价格超过10元打8折
            if(book->getPrice()<10.0) {
                  totalForCart+=book->getPrice();
            } else
                  totalForCart+=book->getPrice()0.8;
        }
        //其它visit方法和折扣策略类似，此处略
        double getTotal() {
                return totalForCart;
        }
};

class ShoppingCart {
private:
        vector<Item>items;
public:
        double calculatePrice() {
                Cashier visitor=new Cashier();

                for(int i=0;i <items.size();i++)</item>
                          （6）;
                }
                double total=visitor->getTotal();
                return total;
        }

        void add(Iteme) {
                items.push_back（e）;
         }
};</items.size();i++)></item*>

答案与解析

  • 试题难度：较难
  • 知识点：C++程序设计>C++程序设计
  • 试题答案：（1）:public Item
    （2）this->price=price
    （3）visitor->visit(this)
    （4）:public Visitor
    （5）void visit(Book*book)
    （6）items[i]->accept(visitor)
  • 试题解析：这里考查的是访问者模式。其定义如下：封装某些作用于某种数据结构中各元素的操作，它可以在不改变数据结构的前提下定义作用于这些元素的新的操作。


results matching ""

    No results matching ""