1、中级软件设计师下午试题-61 及答案解析(总分：222.00，做题时间：90 分钟)一、试题一(总题数：1，分数：45.00)阅读下列说明和数据流图，回答问题 1 至问题 3，将解答填入对应栏内。 说明某供销系统接受顾客的订货单，当库存中某配件的数量小于订购量或库存量低于一定数量时，向供应商发出采货单；当某配件的库存量大于或等于订购量时，或者收到供应商的送货单时并更新了库存后，向顾客发出提货单。该系统还可随时向总经理提供销售和库存情况表。 以下是经分析得到的数据流图及部分数据字典，有些地方有待填充，假定顶层数据流图是正确的。图 1-1是顶层数据流图，图 1-2 是第 0 层数据流图，图 1-3
2、 是第 1 层数据流图，其中(A)是加工 1 的子图，(B)是加工 2 的子图。 图 1-1 图 1-2 图 1-3 （分数：45.00）(1).根据题意，图 1-2 中哪个文件可不必画出。（分数：15.00）_(2).根据题意，指出图 1-3(A)中缺失的数据流的名称，并指出该数据流的起点和终点。（分数：15.00）_(3).根据题意，指出图 1-3(B)中缺失的数据流的名称，并指出该数据流的起点和终点。（分数：15.00）_二、试题二(总题数：3，分数：57.00)设基本表：Student(SNo，SName，Sex，Age，Year，Major)，Course(CNo，Cname，Per
3、iod，Credit)，Grade(SNo，CNo，Grade)通过如下 SQL 语句建立，请在 SQL 语句空缺处填入正确的内容。 CREATE TABLE Student(SNO CHAR(6)NOT NULL, SName CHAR(20), Sex CHAR(1), Age INTEGER, Year CHAR(4), Major CHAR(20), (1) ); CREATE TABLE Course(CNo CHAR(6)NOT NULL, CName CHAR(20),Period INTEGER, Credit INTEGER, (2) ); CREATE TABLE Grad
4、e(SNo CHAR(6)NOT NULL, CNo CHAR(6)NOT NULL, Grade REAL, (3) , (4) , (5) );（分数：25.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_若另有表 Teach(CName，TName)存储教师任课情况，Tname 表示教师名。用 SQL 创建一个含有学号、姓名、课程名、成绩、任课教师名的“主修专业为计算机 CS”的学生成绩视图，并要求进行修改、插入操作时保证该视图只有计算机系的学生。请在 SQL 语句空缺处填入正确的内容。 CREATE VIEW SG (1) SELECT Student.SN
5、o,SName,Grade,Course.CName,TName FROM Student,Grade,Teach, WHERE (2) AND (3) AND Major=cs, (4) ;（分数：24.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_如下的 SQL 语句是用于查询“每个学生的选修课程数、总成绩、平均成绩”的不完整语句，请在空缺处填入正确的内容。 SELECT Student.SNo， (1) ，SUM(Grade),AVG(Grade) FROM Student,Grade WHERE Student.SNo=Grade.SNo, GROUP BY (2) ;
6、（分数：8.00）填空项 1:_填空项 1:_三、试题三(总题数：1，分数：30.00)阅读下列说明和图，回答问题 1 至问题 2，将解答填入对应栏内。 说明银行的自动柜员机(ATM)的功能描述如下： (1)金融卡与信用卡识别：包含伪卡识别以及密码验证； (2)主菜单项：这是一台 ATM 最主要的人机界面，提供各项功能给客户，具体有：提款、转帐、更改密码以及存款； (3)结束操作：客户执行完“菜单项”的功能后，可以选择“打印单据”或“不打印单据”，选好后就结束此次交易。 注意，ATM 除了能处理本行的银行卡外，其他银行的银行卡也应该能处理，通过“金融中心”与其他银行主机进行数据交换。另外，为了
7、方便，ATM 还提供快捷提款，并提供代交费功能(代交费是以转帐的方式处理的)。 该系统采用面向对象方法开发，系统中的类以及类之间的关系用 UML 类图表示。（分数：30.00）(1).图 3-1 是该系统的用例图，根据题意，用题中所述术语指出图 3-1 中参与者 A、B 分别是什么，用例C、D 分别是什么。 图 3-1（分数：15.00）_(2).ATM 机有如下状态：空闲、银行卡验证、业务选择等待、取款金额输入、密码修改、出钞、单据打印。ATM 机一般处于空闲状态，当有客户插入银行卡，则进行银行卡验证，若银行卡无效则结束服务，否则进入业务选择等待。业务有取款、修改密码等，也可以选择退出结束服
8、务，ATM 返回空闲状态。选择取款业务后，等待取款金额输入，确认后判断余额是否足够，若余额不足，则给出提示信息，并进入业务选择等待；若余额充足，则出钞，若客户需要打印单据则进入单据打印状态，否则返回业务选择等待。选择任意一个业务后，可以取消返回业务选择等待。图 3-2 描述了 ATM 状态的转变情况。 图 3-2 （分数：15.00）_四、试题四(总题数：1，分数：45.00)阅读下列说明和图，回答问题 1 到问题 3，将解答填入对应栏内。 说明操作系统中，死锁(Deadlock)是指多个进程在运行的过程中因争夺资源而造成的一种僵局。当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推
9、进。 面对死锁问题有两个解决方案：预防死锁和避免死锁。 预防死锁是一种较简单和直观的事先预防方法。该方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或多个，以此来预防死锁的发生。预防死锁由于较易实现，已被广泛应用，但由于所施加的限制条件往往太严格，可能会导致系统资源利用率和系统吞吐量的降低。 避免死锁同样是属于事先预防的策略，但它无须事先采取各种限制措施去破坏产生死锁的四个必要条件，而是在资源分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。 银行家算法(Bankers algorithm)是 Dijkstra 于 1965 年提出的一个经典的避免死锁的算法。形
10、象地描述银行发放贷款不能使有限可用资金匮乏而导致整个银行无法运转的思路，也就是说每次请求贷款，银行要考虑他能否凭着贷款完成项目，并还清贷款使银行运转正常。令 Request(i)是进程 P(i)请求向量，如果Request(i)j=k 则进程 P(i)希望请韵类资源 k 个。具体算法步骤如下： (1)如果 Request(i)Need(i)则出错(请求量超过申报的最大量)，否则转到(2)； (2)如果 Request(i)Available 则 P(i)等待，否则转(3)； (3)系统对 P(i)所请求的资源实施试探分配，并更改数据结构中的数值； (4)Available=Available-
11、Request(i); A1location(i) =Allocation(i) +Request(i); Need(i)=Need(i)-Request(i); (5)执行安全性算法，如果是安全的，则承认试分配，否则废除试分配，让进程 P(i)继续等待。 所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次运行完成，这种进程序列 P1，P2，Pn)就是安全序列。如果存在这样一个安全序列，则系统是安全的；如果系统不存在这样一个安全序列，则系统是不安全的。（分数：45.00）(1).简述产生死锁的四个必要条件。（分数：15.00）_五、试题五(总题数：1，分数：15.00)
12、阅读下列函数说明和 C 代码，将应填入 (n) 外的字句写在对应栏内。说明为网球比赛的选手安排比赛日程。设有 n(n=2m)位选手参加网球循环赛，循环赛共进行 n-1 天，每位选手要与其他 n-1 位选手赛一场，且每位选手每天赛一场，不轮空。 设 n 位选手被顺序编号为 1，2，n，比赛的日程表是一个 n 行 n-1 列的表，第 i 行 j 列的内容是第 i号选手第 j 天的比赛对手。用分治法设计日程表，就是从其中一半选手(2 m-1位)的比赛日程导出全体 2m选手的比赛日程。从众所周知的只有两位选手的比赛日程出发，反复这个过程，直至为 n 位选手安排好比赛日程为止。 如两位选手比赛日程表如下
13、所示： 11 22 1如四位选手比赛日程表如下所示： 1 2 31 2 3 42 1 4 33 4 1 24 3 2 1函数中使用的预定义符号如下： #define M 64 int aM+1M; 函数 voidd main() int twoml,twom,i,j,m,k; printf(“指定 n(=2 的 k 次幂)位选手，请输入 k：/n“); scanf(“%d“,k); /*8 预设两位选手的比赛日程*/ a11 =2; a21 =1; m=1; twoml=1;while ( (1) ) m+; twoml+=twoml; twom=twoml*2;/*为 2m 位选手安排比赛日
14、程*/ /*填日程表的左下角*/ for(i=twoml+1; (2) ;i+) for(j=1; j=twoml-1; j+) aij=ai-twomlj+twoml; /*填日程表的右上角*/ a1twoml= (3) ;/+填日程表右上角的第 1 列*/ for(i=2; i=twoml; i+) aitwoml=ai-1twoml+1; /*填日程表右上角的其他列，参照前一列填当前列*/ for(j=twoml+1; j(twom;j+) for(i=1; itwoml;I+)aij= (4) ; atwomlj=a1j-1; /*填日程表的右下角*/ for(j=twoml; jtw
15、om;J+)for(i=1;i=twoml; i+) a (5) j=i; /*输出日程表*/ for(i=1; i=twom; i+) for(j=1;jtwom;J+)printf(“%4d“,aij); printf(“/n“); printf(“/n“); （分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_六、试题六(总题数：1，分数：15.00)阅读以下说明和 c+代码，将应填入 (n) 处的字句写在答题纸对应栏内。 说明 很多时候，希望某些类只有一个或有限的几个实例，典型解决方案是所谓单身(Singleton)模式。但在多线程情况下，Sing
16、leton 模式有可能出现问题，需要进行同步检查。如果对“检查 Singleton 对象是否已经创建”进行同步，则存在严重的瓶颈，所有的线程都必须等待检查对象是否存在。解决方式是一种称为Double-Checked-Locking 模式，其意图是将非必须的锁定优化掉，同步检查最多只发生一次，因此不会成为瓶颈。以下是 c+语言实现，能够正确编译通过。 C+代码 class USTax (1) : USTax();/构造函数 public:static USTax* getInstance(); private: static USTax*instance; ; (2) =NULL; USTax*
17、USTax:get Instance() if(instance=NULL) /进行某种同步 cout“实例暂时不存在“endl;if( (3) ) cout“实例不存在，创建实例.“endl;instance= (4) ; cout“实例创建成功“endl;else cout“实例已被创建了“endl;else cout“实例已经存在“endl;return (5) ; （分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_七、试题七(总题数：1，分数：15.00)阅读以下函数说明和 Java 代码，将应填入 (n) 处的字句写在对应栏内。 说明 很多时候
18、，希望某些类只有一个或有限的几个实例，典型解决方案是所谓单身(Singleton)模式。但在多线程情况下，Singleton 模式有可能出现问题，需要进行同步检查。如果对“检查 singleton 对象是否已经创建”进行同步，则存在严重的瓶颈，所有的线程都必须等待检查对象是否存在。解决方式是一种称为Double-Checked-Locking 模式，其意图是将非必须的锁定优化掉，同步检查最多只发生一次，因此不会成为瓶颈。以下是 Java 语言实现，能够正确编译通过。 Java 代码 public class USTax private static USTax instance=null; (
19、1) USTax() private (2) static void doSync() if(instance=null) System.out.println(“实例不存在，创建实例“); instance= (3) ; System.out.println(“实例创建成功“); else System.out.println(“实例已被创建了“); public static USTax getInstance() if(instance=null) System.out.println(“实例暂时不存在“); (4) ;/同步控制 else System.out.println(“实例已
20、经存在“); return (5) ; （分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_中级软件设计师下午试题-61 答案解析(总分：222.00，做题时间：90 分钟)一、试题一(总题数：1，分数：45.00)阅读下列说明和数据流图，回答问题 1 至问题 3，将解答填入对应栏内。 说明某供销系统接受顾客的订货单，当库存中某配件的数量小于订购量或库存量低于一定数量时，向供应商发出采货单；当某配件的库存量大于或等于订购量时，或者收到供应商的送货单时并更新了库存后，向顾客发出提货单。该系统还可随时向总经理提供销售和库存情况表。 以下是经分析得到的数据流图及
21、部分数据字典，有些地方有待填充，假定顶层数据流图是正确的。图 1-1是顶层数据流图，图 1-2 是第 0 层数据流图，图 1-3 是第 1 层数据流图，其中(A)是加工 1 的子图，(B)是加工 2 的子图。 图 1-1 图 1-2 图 1-3 （分数：45.00）(1).根据题意，图 1-2 中哪个文件可不必画出。（分数：15.00）_正确答案：(采购订单)解析：分析 分层数据流图中，只涉及单个加工的文件不必画出，可在子图中再画。依此标准，图 1-2中文件“采购订单”只与加工采购有关，故不必画出。(2).根据题意，指出图 1-3(A)中缺失的数据流的名称，并指出该数据流的起点和终点。（分数：
22、15.00）_正确答案：(起点：库存配件，终点：确定顾客订单 起点：库存配件，终点：制作的销售及库存情况表 提货单，起点：更新库存，终点：顾客 到货通知，起点：采购，终点：缺到货对照)解析：分析 分层数据流图时刻牢记父图与子图平衡原则。对这种数据流缺失题目，认真对照父图与予图就可得出答案。另外，还要注意与文件的交互，包括错误数据流大多也是出在此。 根据题述，图 1-3A 是加工 1 的细化图，加工 1 在图 1-2 中，认真对照其输入输出数据流。发现缺失数据流“提货单”和“到货通知”，进一步确定数据流的起点和终点。“提货单”是输出数据流，起点应为加工“更新库存”，其终点自然是“客户”；“到货通
23、知”是输入数据流，终点应为加工“缺到货对照”，起点应为加工“采购”。 另外，确定顾客订单时，需要检查库存配件，因此应有文件“配件库存”到加工 1.2 的数据流。同理，也应有文件“配件库存”到加工 1-4 的数据流。(3).根据题意，指出图 1-3(B)中缺失的数据流的名称，并指出该数据流的起点和终点。（分数：15.00）_正确答案：(采购单，起点：按供应商汇总，终点：供应商 采购请求，起点：销售，终点：计算配件增量)解析：分析 同问题 2 的分析，仔细对照父图与子图的输入输出数据流，并确认与文件相关的数据流。二、试题二(总题数：3，分数：57.00)设基本表：Student(SNo，SName
24、，Sex，Age，Year，Major)，Course(CNo，Cname，Period，Credit)，Grade(SNo，CNo，Grade)通过如下 SQL 语句建立，请在 SQL 语句空缺处填入正确的内容。 CREATE TABLE Student(SNO CHAR(6)NOT NULL, SName CHAR(20), Sex CHAR(1), Age INTEGER, Year CHAR(4), Major CHAR(20), (1) ); CREATE TABLE Course(CNo CHAR(6)NOT NULL, CName CHAR(20),Period INTEGER,
25、 Credit INTEGER, (2) ); CREATE TABLE Grade(SNo CHAR(6)NOT NULL, CNo CHAR(6)NOT NULL, Grade REAL, (3) , (4) , (5) );（分数：25.00）填空项 1:_ （正确答案：PRIMARYKEY(SNo)）解析：填空项 1:_ （正确答案：PRIMARY KEY(Cno)）解析：填空项 1:_ （正确答案：PRIMARY KEY(SNo，CNo)）解析：填空项 1:_ （正确答案：FOREIGN KEY(SNo)REFERENCES Student(SNo)）解析：填空项 1:_ （正确答案
26、：FOREIGN KEY(CNo)REFERENCES Course(CNo)）解析：分析 空(1)处应该是完整性约束条件。在此为声明主键，据题述 Student 表的主键应该是 SNo，故空(1)应填 PRIMARY KEY(SNo)。同理，Course 表的主键为 CNo，故空(2)应填 PRIMARY KEY(CNo)，Grade 表的主键为(Sno，CNo)，故空(3)应填 PRIMARY KEY(Sno,CNo)。Grade 表的主键(Sno，CNo)中，SNo 是 Student 表的主键，CNo 是 Course 表的主键，这样，两者就是Grade 表的外健，空(4)、(5)是用
27、来声明外健的，分别填(4)FOREIGN KEY(SNo)REFERENCES Student(SNo)，(5)FOREIGN KEY(CNo)REFERENCES Course(CNo)，顺序可以颠倒。若另有表 Teach(CName，TName)存储教师任课情况，Tname 表示教师名。用 SQL 创建一个含有学号、姓名、课程名、成绩、任课教师名的“主修专业为计算机 CS”的学生成绩视图，并要求进行修改、插入操作时保证该视图只有计算机系的学生。请在 SQL 语句空缺处填入正确的内容。 CREATE VIEW SG (1) SELECT Student.SNo,SName,Grade,Cou
28、rse.CName,TName FROM Student,Grade,Teach, WHERE (2) AND (3) AND Major=cs, (4) ;（分数：24.00）填空项 1:_ （正确答案：AS）解析：填空项 1:_ （正确答案：Student.SNo=Grade.SNo）解析：填空项 1:_ （正确答案：Course.CName=Teach.CName）解析：填空项 1:_ （正确答案：WITH CHECK OPTION）解析：分析 创建视图：CREATE VIEW 视图名(列表名)AS SELECT 查询子句WITH CHECK OPTION易得空(1)为 AS。空(2)、
29、空(3)处的条件应为学生和成绩中的学号相同，教师和课程中的教师名相同。为了保证“进行修改、插入操作时保证该视图只有计算机系的学生”，需要声明为 WITH CHECKOPTION，此即空(4)内容。如下的 SQL 语句是用于查询“每个学生的选修课程数、总成绩、平均成绩”的不完整语句，请在空缺处填入正确的内容。 SELECT Student.SNo， (1) ，SUM(Grade),AVG(Grade) FROM Student,Grade WHERE Student.SNo=Grade.SNo, GROUP BY (2) ;（分数：8.00）填空项 1:_ （正确答案：COUNT(Grade.C
30、No)）解析：填空项 1:_ （正确答案：Student.SNo）解析：分析 该 SQL 语句是用于查询“每个学生的选修课程数、总成绩、平均成绩”，显然空(1)应为课程数，对应函数应为 COUNT(Grade.CNo)，应该按照学号分组，故空(2)应填 Student.Sno。三、试题三(总题数：1，分数：30.00)阅读下列说明和图，回答问题 1 至问题 2，将解答填入对应栏内。 说明银行的自动柜员机(ATM)的功能描述如下： (1)金融卡与信用卡识别：包含伪卡识别以及密码验证； (2)主菜单项：这是一台 ATM 最主要的人机界面，提供各项功能给客户，具体有：提款、转帐、更改密码以及存款；
31、(3)结束操作：客户执行完“菜单项”的功能后，可以选择“打印单据”或“不打印单据”，选好后就结束此次交易。 注意，ATM 除了能处理本行的银行卡外，其他银行的银行卡也应该能处理，通过“金融中心”与其他银行主机进行数据交换。另外，为了方便，ATM 还提供快捷提款，并提供代交费功能(代交费是以转帐的方式处理的)。 该系统采用面向对象方法开发，系统中的类以及类之间的关系用 UML 类图表示。（分数：30.00）(1).图 3-1 是该系统的用例图，根据题意，用题中所述术语指出图 3-1 中参与者 A、B 分别是什么，用例C、D 分别是什么。 图 3-1（分数：15.00）_正确答案：(A：“客户”
32、B：“金融中心” C：“提款” D：“转账”)解析：分析 图 3-1 给出了系统用例图，用例图(use case diagram)展现了一组用例、参与者(actor)以及它们之间的关系。 易知参与者 A 是“客户”，参与者 B 为“金融中心”。 用例“快捷提款”是“提款”的扩展，因此用例 C 是“提款”；用例“代交费”是“转账”的扩展，因此用例 D 是“转账”。(2).ATM 机有如下状态：空闲、银行卡验证、业务选择等待、取款金额输入、密码修改、出钞、单据打印。ATM 机一般处于空闲状态，当有客户插入银行卡，则进行银行卡验证，若银行卡无效则结束服务，否则进入业务选择等待。业务有取款、修改密码等
33、，也可以选择退出结束服务，ATM 返回空闲状态。选择取款业务后，等待取款金额输入，确认后判断余额是否足够，若余额不足，则给出提示信息，并进入业务选择等待；若余额充足，则出钞，若客户需要打印单据则进入单据打印状态，否则返回业务选择等待。选择任意一个业务后，可以取消返回业务选择等待。图 3-2 描述了 ATM 状态的转变情况。 图 3-2 （分数：15.00）_正确答案：(A：“金额是否足够” B：“银行卡无效” C：“打印单据”)解析：分析 取款时，若金额不足，自然取款失败，因此判定 A 是判断“金额是否足够”。 当银行卡验证失败，服务结束，ATM 机转入“空闲”，故 B 是“银行卡无效”。 状
34、态 C 为“打印单据”。四、试题四(总题数：1，分数：45.00)阅读下列说明和图，回答问题 1 到问题 3，将解答填入对应栏内。 说明操作系统中，死锁(Deadlock)是指多个进程在运行的过程中因争夺资源而造成的一种僵局。当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。 面对死锁问题有两个解决方案：预防死锁和避免死锁。 预防死锁是一种较简单和直观的事先预防方法。该方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或多个，以此来预防死锁的发生。预防死锁由于较易实现，已被广泛应用，但由于所施加的限制条件往往太严格，可能会导致系统资源利用率和系统吞吐量的降低。 避免
35、死锁同样是属于事先预防的策略，但它无须事先采取各种限制措施去破坏产生死锁的四个必要条件，而是在资源分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。 银行家算法(Bankers algorithm)是 Dijkstra 于 1965 年提出的一个经典的避免死锁的算法。形象地描述银行发放贷款不能使有限可用资金匮乏而导致整个银行无法运转的思路，也就是说每次请求贷款，银行要考虑他能否凭着贷款完成项目，并还清贷款使银行运转正常。令 Request(i)是进程 P(i)请求向量，如果Request(i)j=k 则进程 P(i)希望请韵类资源 k 个。具体算法步骤如下： (1)如果 Req
36、uest(i)Need(i)则出错(请求量超过申报的最大量)，否则转到(2)； (2)如果 Request(i)Available 则 P(i)等待，否则转(3)； (3)系统对 P(i)所请求的资源实施试探分配，并更改数据结构中的数值； (4)Available=Available-Request(i); A1location(i) =Allocation(i) +Request(i); Need(i)=Need(i)-Request(i); (5)执行安全性算法，如果是安全的，则承认试分配，否则废除试分配，让进程 P(i)继续等待。 所谓系统是安全的，是指系统中的所有进程能够按照某一种次序
37、分配资源，并且依次运行完成，这种进程序列 P1，P2，Pn)就是安全序列。如果存在这样一个安全序列，则系统是安全的；如果系统不存在这样一个安全序列，则系统是不安全的。（分数：45.00）(1).简述产生死锁的四个必要条件。（分数：15.00）_正确答案：(死锁的发生必须具备四个必要条件： 互斥条件：进程对所分配到的资源进行排他性使用，即在一段时间内某资源只有一个进程占用； 请求和保持条件：进程已经保持了至少一个资源但又提出了新的资源请求，若得不到满足则阻塞该进程，但其保持已获得的资源不释放； 不剥夺条件：进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放； 环路等待条件：在
38、发生死锁时，必然存在一个进程一资源的环形链，即进程集合P1，P2，Pn) 中的 P1 等待 P2 占用的资源，P2 等待 P3 占用的资源，Pn 等待 P0 占用的资源。)解析：_解析：_解析：五、试题五(总题数：1，分数：15.00)阅读下列函数说明和 C 代码，将应填入 (n) 外的字句写在对应栏内。说明为网球比赛的选手安排比赛日程。设有 n(n=2m)位选手参加网球循环赛，循环赛共进行 n-1 天，每位选手要与其他 n-1 位选手赛一场，且每位选手每天赛一场，不轮空。 设 n 位选手被顺序编号为 1，2，n，比赛的日程表是一个 n 行 n-1 列的表，第 i 行 j 列的内容是第 i号选
39、手第 j 天的比赛对手。用分治法设计日程表，就是从其中一半选手(2 m-1位)的比赛日程导出全体 2m选手的比赛日程。从众所周知的只有两位选手的比赛日程出发，反复这个过程，直至为 n 位选手安排好比赛日程为止。 如两位选手比赛日程表如下所示： 11 22 1如四位选手比赛日程表如下所示： 1 2 31 2 3 42 1 4 33 4 1 24 3 2 1函数中使用的预定义符号如下： #define M 64 int aM+1M; 函数 voidd main() int twoml,twom,i,j,m,k; printf(“指定 n(=2 的 k 次幂)位选手，请输入 k：/n“); scan
40、f(“%d“,k); /*8 预设两位选手的比赛日程*/ a11 =2; a21 =1; m=1; twoml=1;while ( (1) ) m+; twoml+=twoml; twom=twoml*2;/*为 2m 位选手安排比赛日程*/ /*填日程表的左下角*/ for(i=twoml+1; (2) ;i+) for(j=1; j=twoml-1; j+) aij=ai-twomlj+twoml; /*填日程表的右上角*/ a1twoml= (3) ;/+填日程表右上角的第 1 列*/ for(i=2; i=twoml; i+) aitwoml=ai-1twoml+1; /*填日程表右上
41、角的其他列，参照前一列填当前列*/ for(j=twoml+1; j(twom;j+) for(i=1; itwoml;I+)aij= (4) ; atwomlj=a1j-1; /*填日程表的右下角*/ for(j=twoml; jtwom;J+)for(i=1;i=twoml; i+) a (5) j=i; /*输出日程表*/ for(i=1; i=twom; i+) for(j=1;jtwom;J+)printf(“%4d“,aij); printf(“/n“); printf(“/n“); （分数：15.00）填空项 1:_ （正确答案：mk）解析：分析 题中已经说明该算法采用的是分治法
42、，“就是从其中一半选手(2m-1 位)的比赛日程导出全体 2m 选手的比赛日程”，再根据注释，不难确定空(1)应填 mk。填空项 1:_ （正确答案：i=twom）解析：分析 以下各空的判断略有难度，可通过举例法，亦即模拟执行，来生成四位选手(k 为 2)的比赛日程。空(2)应填当前问题规模中行下标的最大值，分析得当前规模行下标最大为 twom，对应四位选手为 4，故空(2)应填 i=twom。填空项 1:_ （正确答案：twoml+1）解析：分析 空(3)填的右上角第一行第一列元素，对应四位选手为 a12，此值为 3，即 twoml+1，故空(3)应填 twoml+1。填空项 1:_ （正确答案：ai+1j-1）解析：分析 比赛
