2011年(上半年)试题及答案(下午)

2011年上半年  软件设计师  下午试卷

（考试时间  14:00～16:30  共150分钟）

2. 在答题纸的指定位置填写准考证号、身份证号和姓名。

3. 答题纸上除填写上述内容外只能写解答。

4. 本试卷共6道题，试题一至试题四是必答题，试题五和试题六选答1道。每题15分，满分75分。

5. 解答时字迹务必清楚，字迹不清时，将不评分。

6. 仿照下面例题，将解答写在答题纸的对应栏内。

例题

2011年上半年全国计算机技术与软件专业技术资格（水平）考试日期是（1）月（2）日。

因为正确的解答是“5月21日”，故在答题纸的对应栏内写上“5”和“21”（参看下表）。

试题一（共15分）

阅读下列说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。

【说明】

某医院欲开发病人监控系统。该系统通过各种设备监控病人的生命体征，并在生命体征异常时向医生和护理人员报警。该系统的主要功能如下：

（1）本地监控：定期获取病人的生命体征，如体温、血压、心率等数据。

（2）格式化生命体征：对病人的各项重要生命体征数据进行格式化，然后存入日志文件并检查生命体征。

（3）检查生命体征：将格式化后的生命体征与生命体征范围文件中预设的正常范围进行比较。如果超出了预设范围，系统就发送一条警告信息给医生和护理人员。

（4）维护生命体征范围：医生在必要时（如，新的研究结果出现时）添加或更新生命体征值的正常范围。

（5）提取报告：在医生或护理人员请求病人生命体征报告时，从日志文件中获取病人生命体征生成体征报告，并返回给请求者。

（6）生成病历：根据日志文件中的生命体征，医生对病人的病情进行描述，形成病历存入病历文件。

（7）查询病历：根据医生的病历查询请求，查询病历文件，给医生返回病历报告。

（8）生成治疗意见：根据日志文件中的生命体征和病历，医生给出治疗意见，如处方等，并存入治疗意见文件。

（9）查询治疗意见：医生和护理人员查询治疗意见，据此对病人进行治疗。

现采用结构化方法对病人监控系统进行分析与设计，获得如图1-1所示的顶层数据流图和图1-2所示的0层数据流图。

图1-1 顶层数据流图

图1-2 0层数据流图

【问题1】（3分）

使用说明中的词语，给出图1-1中的实体E1～E3的名称。

答：

E1: 病人  E2：护理人员  E3:医生

【问题2】（4分）

使用说明中的词语，给出图1-2中的数据存储D1～D4的名称。

答：

D1: 生命体征范围文件    D2: 日志文件

D3: 病历文件            D4: 治疗意见文件

【问题3】（6分）

图1-2中缺失了4条数据流，使用说明、图1-1和图1-2中的术语，给出数据流的名称及其起点和终点。

答：

说明实体E1和E3之间可否有数据流，并解释其原因。

答：不可有数据流，因为E1和E3之间没有加工。

试题二（共15分）

阅读下列说明，回答问题1至问题3，将解答填入答题纸的对应栏内。

【说明】

某服装销售公司拟开发一套服装采购管理系统，以便对服装采购和库存进行管理。

【需求分析】

（1）采购系统需要维护服装信息及服装在仓库中的存放情况。服装信息主要包括：服装编码、服装描述、服装类型、销售价格、尺码和面料，其中，服装类型为销售分类，服装按销售分类编码。仓库信息包括：仓库编码、仓库位置、仓库容量和库管员。系统记录库管员的库管员编码、姓名和级别。一个库管员可以管理多个仓库，每个仓库有一名库管员。一个仓库中可以存放多类服装，一类服装可能存放在多个仓库中。

（2）当库管员发现有一类或者多类服装缺货时，需要生成采购订单。一个采购订单可以包含多类服装。每类服装可由多个不同的供应商供应，但具有相同的服装编码。采购订单主要记录订单编码、订货日期和应到货日期，并详细记录所采购的每类服装的数量、采购价格和对应的多个供应商。

（3）系统需记录每类服装的各个供应商信息和供应情况。供应商信息包括：供应商编码、供应商名称、地址、企业法人和联系电话。供应情况记录供应商所供应服装的服装类型和服装质量等级。一个供应商可以供应多类服装，一类服装可由多个供应商供应。库管员根据入库时的服装质量情况，设定或修改每个供应商所供应的每类服装的服装质量等级，作为后续采购服装时，选择供应商的参考标准。

【概念模型设计】

根据需求阶段收集的信息，设计的实体联系图（不完整）如图2-1所示。

【逻辑结构设计】

     根据概念模型设计阶段完成的实体联系图，得出如下关系模式（不完整）：

库管员 （库管员编码，姓名，级别）

仓库信息（       （1）     ，仓库位置，仓库容量）

服装（服装编码，服装描述，服装类型，尺码，面料，销售价格）

供应商（供应商编码，供应商名称，地址，联系电话，企业法人）

供应情况（       （2）       ，服装质量等级）

采购订单（       （3）       ）

采购订单明细（      （4）      ）

【问题1】（6分）

根据需求分析的描述，补充图2-1中的联系和联系的类型。

答：

    *    1

*                   *

    *    *    *

    *    *

【问题2】（6分）

根据补充完整的图2-1，将逻辑结构设计阶段生成的关系模式中的空（1）～（4）补充完整，并给出其主键（用下划线指出）。

答：（1）仓库编码,库管员

（2）供应商编码、服装编码,服装类型

（3）订单编码,订货日期,应到货日期

（4）供应商编码、服装编码、订单编码,数量、采购价格

【问题3】（3分）

如果库管员定期需要轮流对所有仓库中的服装质量进行抽查，对每个仓库中的每一类被抽查服装需要记录一条抽查结果，并且需要记录抽查的时间和负责抽查的库管员。请根据该要求，对图2-1进行修改，画出修改后的实体间联系和联系的类型。

答：

    *    *         *

    *       *

    *

    *    *

试题三（共15分）

阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。

【说明】

一个简单的图形编辑器提供给用户的基本操作包括：创建图形、创建元素、选择元素以及删除图形。图形编辑器的组成及其基本功能描述如下：

（1）图形由文本元素和图元元素构成，图元元素包括线条、矩形和椭圆。

（2）图形显示在工作空间中，一次只能显示一张图形（即当前图形，current）。

（3）编辑器提供了两种操作图形的工具：选择工具和创建工具。对图形进行操作时，一次只能使用一种工具（即当前活动工具，active）。

① 创建工具用于创建文本元素和图元元素。

② 对于显示在工作空间中的图形，使用选择工具能够选定其中所包含的元素，可以选择一个元素，也可以同时选择多个元素。被选择的元素称为当前选中元素（selected）。

③ 每种元素都具有对应的控制点。拖拽选定元素的控制点，可以移动元素或者调整元素的大小。

现采用面向对象方法开发该图形编辑器，使用UML进行建模。构建出的用例图和类图分别如图3-1和3-2所示。

图3-1 用例图

图3-2 类图

【问题1】（4分）

根据说明中的描述，给出图3-1中U1和U2所对应的用例，以及（1）和（2）处所对应的关系。

答：

U1: 移动元素     U2：调整元素的大小

（1）<>  (2)<>

【问题2】（8分）

根据说明中的描述，给出图3-2中缺少的C1～C8所对应的类名以及（3） ～ （6）处所对应的多重度。

答：

    C1:创建工具         C2:选择工具

C3:线条工具         C4:矩形工具

C5:椭圆工具         C6:线条 

C7: 矩形        C8: 椭圆

(3)0..1          (4)1

(5)1          (6)1..*或*

【问题3】（3分）

图3-2中的类图设计采用了桥接（Bridge）设计模式，请说明该模式的内涵。

答：Bridge模式将对象的抽象和其实现分离，从而可以地改变它们。

试题四（共15分）

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。

【说明】

某应用中需要对100000个整数元素进行排序，每个元素的取值在0～5之间。排序算法的基本思想是：对每一个元素x，确定小于等于x的元素个数（记为m），将x放在输出元素序列的第m个位置。对于元素值重复的情况，依次放入第m-1、m-2、…个位置。例如，如果元素值小于等于4的元素个数有10个，其中元素值等于4的元素个数有3个，则4应该在输出元素序列的第10个位置、第9个位置和第8个位置上。

算法具体的步骤为：

步骤1：统计每个元素值的个数。

步骤2：统计小于等于每个元素值的个数。

步骤3：将输入元素序列中的每个元素放入有序的输出元素序列。

【C代码】

下面是该排序算法的C语言实现。

（1）常量和变量说明

R：常量，定义元素取值范围中的取值个数，如上述应用中R值应取6

i：循环变量

n：待排序元素个数

a：输入数组，长度为n

b：输出数组，长度为n

c：辅助数组，长度为R，其中每个元素表示小于等于下标所对应的元素值的个数。

（2）函数sort

1     void sort(int n, int a[], int b[]) {

2            int c[R], i;

3            for(i = 0; i <    （1）R  ; i++) {

4                    c[i] = 0;

5             }

6             for(i = 0; i < n; i++) {

7                 c[a[i]] =    （2）c[a[i]]+1  ;

8             }

9             for(i = 1; i < R; i++) {

10             c[i] =    （3）c[i-1]+c[i]  ;

11        }

12         for(i = 0; i < n; i++) {

13             b[c[a[i]] - 1] =    （4）a[i]  ;

14            c[a[i]] = c[a[i]] - 1;

15         }

16    }

【问题1】（8分）

根据说明和C代码，填充C代码中的空缺（1）～（4）。

【问题2】（4分）

根据C代码，函数的时间复杂度和空间复杂度分别为 （5） 和 （6） （用O符号表示）。

（5）或者或n或线性

（6）或者或n或线性

【问题3】（3分）

根据以上C代码，分析该排序算法是否稳定。若稳定，请简要说明（不超过100字）；若不稳定，请修改其中代码使其稳定（给出要修改的行号和修改后的代码）。

不稳定。修改第12行的for循环为：for(i = n - 1; i >= 0; i--){ 即可。

1、(1)R    (2)c[a[i]]+1    (3)c[i]+c[i-1]     (4)a[i] 

本题考查算法设计与分析技术以及算法的C语言实现，是比较传统的题目，要求考生细心分析题目中所描述的内容。 根据题中说明，第3到第5行代码进行c数组的初始化，c数组的长度为R，在C语言中，下标从0开始，因此空格(1)中填写R。第6到第8行检查a数组的每一个元素。如果元素的值为i，则增加c[i]的值。因此c[a[i]]=c[a[i]]+1，空格(2)填写c[a[i]]+1。完成第6行到第8行的代码后，c[i]中就存放了等于i的元素的个数。第9到第11行，通过在数组c中记录计数和，c[i]=c[i-1]+c[i]，可以确定对每一个i=0，1，…，R-1，有多少个元素是小于或等于i的。因此空格(3)填写c[i-1]+c[i]。第12行到第15行把数组a中每个元素a[i]放在输出数组b中与其相应的最终位置上，b[c[a[i]]-1]=a[i]，因此空格(4)填写a[i]。由于可能存在相同元素，因此每次将一个值a[i]放入数组b中时，都要减小c[i]的值。下面以一个例子来说明排序过程。 设a={4，1，3，4，3，4}，R=5，即待排序的元素值在{0，1，2，3，4}中，其排序过程如下图所示。 图中(a)为输入数组a，(b)为初始化后的c数组，(c)为统计数组a中每个元素后的c数组，(d)为计数和，即统计小于等于i的元素个数后的c数组。(e)到(j)是将a数组中的元素依次放到b数组的过程，(k)是数组a和数组b的元素对应关系。

从下列的2道试题（试题五和试题六）中任选1道解答。如果解答的试题数超过1道，则题号小的1道解答有效。

试题五（共15分）

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

【说明】

某饭店在不同的时段提供多种不同的餐饮，其菜单的结构图如图5-1所示。

图5-1 菜单结构图

现在采用组合（Composition）模式来构造该饭店的菜单，使得饭店可以方便地在其中增加新的餐饮形式，得到如图5-2所示的类图。其中MenuComponent为抽象类，定义了添加（add）新菜单和打印饭店所有菜单信息（print）的方法接口。类Menu表示饭店提供的每种餐饮形式的菜单，如煎饼屋菜单、咖啡屋菜单等。每种菜单中都可以添加子菜单，例如图5-1中的甜点菜单。类MenuItem表示菜单中的菜式。

图5-2  类图

【C++代码】

#include

#include

#include

using namespace std;

class MenuComponent {

protected:   string name;

public:

MenuComponent(string name) { this->name = name; }

   string getName() { return name; }

    （1）virtual void add(MenuComponent* menuComponent)=0 ;          // 添加新菜单

   virtual void print() = 0;          // 打印菜单信息

};

class MenuItem : public MenuComponent {

private:   double price;

public:

MenuItem(string name,double price): MenuComponent(name) { this->price = price; }

   double getPrice() { return price; }

   void add(MenuComponent* menuComponent) { return ; } // 添加新菜单

   void print() { cout << "    " << getName() << ", " << getPrice() << endl; }

};

class Menu : public MenuComponent {

private:   list< （2）MenuComponent*

 >  menuComponents;

public:

   Menu(string name): MenuComponent(name){}

   void add(MenuComponent* menuComponent)  // 添加新菜单

   {     （3）menuComponents.push_back(menuComponent)  ;   }

   void print() {

cout << "\\n" << getName() << "\\n-------------------------------" << endl;

std::list::iterator iter;

     for(iter = menuComponents.begin(); iter != menuComponents.end(); iter++) 

           （4）(*iter) ->print();

   }

};

void main() {

  MenuComponent* allMenus = new Menu("ALL MENUS");

  MenuComponent* dinerMenu = new Menu("DINER MENU");

  …… // 创建更多的Menu对象，此处代码省略

  allMenus->add(dinerMenu);    // 将dinerMenu添加到餐厅菜单中

  …… // 为餐厅增加更多的菜单，此处代码省略

   （5）allMenus ->print();    // 打印饭店所有菜单的信息

}

试题六（共15分）

阅读下列说明和Java代码，将应填入 （n） 处的字句写在答题纸的对应栏内。

【说明】

某饭店在不同的时段提供多种不同的餐饮，其菜单的结构图如图6-1所示。

图6-1 菜单结构图

现在采用组合（Composition）模式来构造该饭店的菜单，使得饭店可以方便地在其中增加新的餐饮形式，得到如图6-2所示的类图。其中MenuComponent为抽象类，定义了添加（add）新菜单和打印饭店所有菜单信息（print）的方法接口。类Menu表示饭店提供的每种餐饮形式的菜单，如煎饼屋菜单、咖啡屋菜单等。每种菜单中都可以添加子菜单，例如图6-1中的甜点菜单。类MenuItem表示菜单中的菜式。

图6-2  类图

【Java代码】

import java.util.*;

 （1）Abstrct class  MenuComponent {

   protected String name;

    （2）public abstract void add(MenuComponent menuComponent) ;  //添加新菜单

   public abstract void print();        //打印菜单信息

   public String getName() { return name; }

}

class MenuItem extends MenuComponent {

   private double price;

   public MenuItem(String name, double price) {

        this.name = name;   this.price = price;

   }

   public double getPrice()  { return price; }

   public void add(MenuComponent menuComponent){ return ; } // 添加新菜单

   public void print() { 

     System.out.print(" " + getName());

     System.out.println(

   }

}

class Menu extends MenuComponent {

private List menuComponents = new ArrayList();

   public Menu(String name) { this.name = name; }

   public void add(MenuComponent menuComponent) { // 添加新菜单

     menuComponents. （3）add(menuComponent);    

   }

   public void print() {

     System.out.print("\\n" + getName());

     System.out.println(

     Iterator iterator = menuComponents.iterator();

     while(iterator.hasNext()) {

        MenuComponent menuComponent = (MenuComponent)iterator.next();

         （4）menuComponent. print() ;

     }

   }

}

class MenuTestDrive {

   public static void main(String args[]) {

       MenuComponent  allMenus = new Menu("ALL MENUS");

MenuComponent  dinerMenu = new Menu("DINER MENU");

       …… // 创建更多的Menu对象，此处代码省略

       allMenus.add(dinerMenu);    // 将dinerMenu添加到餐厅菜单中

       …… // 为餐厅增加更多的菜单，此处代码省略

        （5）allMenus. print() ;    // 打印饭店所有菜单的信息

   }

}