1990年度高级程序员级下午试题

阅读下列说明和流程图，回答问题 1～3，将解答写在答卷的对应栏内。

[说明]

有一种游戏，是用滚球击十个柱-比赛分为十局，每局可滚球一次或多次，其规则和记分方法如下；

(1)若一局的第一个球击倒全部十个柱( 称为 strike )，则这局不再滚球( 例外，对第十局来说，还可补滚两次球 )，其得分为 10 加下两次滚球所击倒的柱数。

(2)若一局的第一个球未击倒十个柱，则可对剩下的柱再滚一次球。如果这局的两次滚球击倒全部十个柱( 称为 spare )，则这局不再滚球( 例外，对第十局来说，还可补滚一次球 )，其得分为 10 加上下一次滚球所击倒的柱数，否则，这局也不再滚球，其得分为本局两次滚球所击倒的柱数之和。

试题 2

阅读下列说明和流程图，回答问题 1 和问题 2，把解答写在答卷的对应栏内。

某毛纺厂生产 500 种毛料商品，这些商品送到 300 个销售点销售。销售点应在收到商品后的规定时间内把贷款汇给毛纺厂。

流程图描述了该厂发货、收款、催款的处理过程。其中商品文件和销售点文件的记录格式如下：

发货单的格式如下：

收款单的格式如下：

处理1～3把当天的发货单合并到发货文件。处理4～6把当天的收款单合并到收款文件。每天在处理3和处理5做过之后，由处理7在发货文件中当天已收款的记录上加上已收款标记。处理8在月末执行一次，它有三个功能：(1)汇总输出本月发货清单；(2)删除发货文件中已收款的所有记录，形成一个新的发货文件，作为下月初处理时的初始文件；(3)产生催款通知单，以便对那些一个月以前已发货但至今仍未收到货款的销售点催款。处理 9 也每月末执行一次，除耩班本月收款报告外，还删除收款文件中的所有记录。现假定不会有完全相同的发货单。
[问题1]

指出流程图中应在哪几个处理框中检查发货单和收款单的错误，并分别指出它们各能指出什么错误。
[问题2]

如果把流程图中从日收款分类文件到处理 7 的连线改成从日收款文件到处理 7 的连线，则有什么缺点，理由是什么? ，
[问题3]

如果把流程图中从日收款分类文件到处理 7 的连线改成从收款文件到处理 7 的连线，则有什么缺点，理由是什么?

试题 3

阅读下列说明和流程图，回答问题 1 和 2 ，把解答写在答卷的对应栏内。

[说明]

(1)流程图描述某大型百货商店商品销售的数据处理流程。

(2)商店设有若干柜台，同一种商品可能在几个柜台上销售，各柜台每天提供一组日销售数据，其格式如下：

日期，柜台号，商品代码，销售数量，商品代码，销售数量，…

(3)数据处理系统每日产生一份反映各柜台当日销售金额和商店日销售金额的“日销售金额报告”，必要时还产生一份“商品请购报告”，给出那些低于最低库存量的商品代码、商品名称、最低库存量和实际库存量。处理过程中产生存档的“日销售文件”和临时工作文件“日销售量文件”和“日销售金额文件”。

(4)系统中所用到的数据均来自数据文件。

(5)流程图中的商品库存文件的记录已按关键宇“商品代码”排序。
[问题1]

①指出商品库存文件的记录中必须包括哪些数据项?

②分别指出在日销售文件，日销售量文件和日销售金额文件的记录中至少应包括哪些数据项，同时不产生数据冗余?

③错误清单可能指出哪些错误?
[问题2]

简要叙述处理 6 的主要内容。
[问题3]

如果删除流程图中的虚框 A 部分，日销售文件的记录中应增加什么数据项。

试题4

阅读下列说明和流程图，回答问题，把解答填入答卷的对应栏内。

[问题]

将一个 m×n 的矩阵 X 转置后存放到矩阵 Y 中，其计算复杂度为 O(m*n)。对稀疏矩阵来说，可以用紧凑的存贮方式来减少所需的存贮量，并降低计算复杂度。

已知有 t(t>0) 个非零元素的 m×n 稀疏矩阵 W（每行每列至少有一个非零元素）以紧凑方式存放在数组 X[l：t，1：3]中。X 中某行的三个值为（i，j，v）时表示在 W 的第 i 行第 j 列有一个非零元素 v。假定 X 中的元素已按行号列号递增排序。现要求将 X 转置后以紧凑表示形式存放在数组 Y[l：t，1：3] 中，并且 Y 也按行号列号递增排序。

下面描述了两种紧凑的稀疏矩阵的转置算法：

算法一见流程图a

算法二见流程图b。争扣外图中：数组元素 S[i] 用来存放X中列号为 i 的元素个数，数组元素 U[j] 用来计算X中第 j 列元素在Y中的行号。

[问题1]

填充流程图 a 和流程图 b 中的 ①～⑤，使之实现相应的算法。
[问题2]

分别写出算法一和算法二的计算复杂度。 · ·

试题5

阅读下列说明和流程图。回答问题 1 和 2，把解答填入答卷的对应栏内。

有一个集合，集合中有 n 个元素，每个集合元素都是正整数，它们存放在一维数组A中，每个数组元素存放一个集合元素。对给定的整数 total（假定集合中每个元素的值均小于 total），流程图求出所有满足下列条件的子集：子集中各元素之和等于 total。

本题在使用试探法找出全部解答的过程中，依次选取当前的候选元素，尝试组成一个小于 total 的部分和，如果合适，则选取下一元素试探；若不合适，则回溯取另一个候选元素尝试，题中利用 s 栈存放候单元素的下标，用它实现回溯。如果候选元素加上部分和等于 total ，则表示找到一个解答，然后通过回溯，再试探寻找其它的解答。
[问题1]

问流程图中的 ④ 应与 A～D 中的那一点相连，并填充图中的①～③，使之成为完整的流程图。
[问题2]

设 total＝10，n＝6，数组 A 中各元素的值为(8，4，1，2，5，3)。

若图中的(1)框改为 sp：0，则执行该流程图后输出什么结果。

[流程图]

试题6

在 COMET 型计算机上可以使用试卷上所附的 CASL 汇编语言。阅读下列程序说明和 CASL 程序，把应填入其中__n__处的字句，写在答卷的对应栏内。

[程序说明]

本程序完成两个 4 位十进制数相加，并输出两数之和。

例： 输入 '5794+6438'

     输出 '12232'

(1)必须按上述要求输入，否则输出 'INPUTERROR' 信息，并重新输入。

(2)从低位开始，逐位进行十进制相加。

(3)若输入长度为 0 时，本程序结束。
[问题]

在程序中的 ①～⑦ 处各填入一条正确指令，以完成此程序。除非必要，标号栏不要填写。
[程序]

试题7

阅读下列程序说明和 C 程序，把应填入其中__n__ 处的字句，写在答卷的对应栏内。

[程序说明]

设对于一个 n×n 的上三角矩阵 a，为节约存贮，只将它的上三角元素按行主序连续存放在数组 b 中。下面的函数 trans 在不引入工作数组的情况下，实现将 a 改为按列主序连续存放在数组 b 中。

设 n＝5，

b＝(1，2，3，4，5，6，7，8，9，10，11，12，13，14，15)

经调用 trans 函数后，b 变为

b＝(1，2，6，3，7，10，4，8，11，13，5，9，12，14，15)

函数 tans 对数组元素的存贮位置作调整。调整过程中存在若干个循环传送链：

b(i₁)→b(i₂)→…→b(i_j)→b(i₁)   1≤j<n

例如，考察调整后的数组元素 b(2)( 值为 6 )，与该元素相关的位置调整将形成下面的循环传送链：

b(2)→b(3)→b(6)→…→b(12)→b(9)→b(5)→b(2)

关键是确定循环传送链的下标 i₁，i₂，…，i_j ,以及在考察调整后的元素 b(k)( k；3，4，… ) 时能判定 b(k) 是已被传送过的某传送链上的元素。

函数 ctr(k，n) 计算调整后的数组 b 的第 k 个元素 b(k) 在原数组 b 中的位置，该位置作为函数 ctr(k，n) 的返回值。函数 ctr 根据 k 确定它在矩阵中的行号 i 和列号 j ( 注意行号和列号均从 0 算起 )，然后按矩阵存放原则计算出它在 b 中的位置。
[程序]

trans( b，n )

int n，b[]

{ int m，k，r，cc，rr；int w；

m＝(n+1)*n/2-4；

k=2

while (m>0)

{ r＝ctr(k，n)；

if ( r == k )

m--；

else

{ cc=k；rr＝r；

while(__①__)

{ CC=rr，rr=ctr(cc，n)；

}

if (__②__

{ cc＝k；rr＝r；w＝b[k]；

while(__③__)

{ b[cc]=b[rr]；m--；

cc=rr，rr=ctr(cc，n)；

}

b[cc]-w；__④__；

}

}

k++；

}

}

ctr( k，n )

int k，n；

{ int i，j；

i＝k；j=0 ；

while (__⑤__)

i -= ++j ；

return( i*n+j-i*(i+1)／2 )； ·

}　　

试题8～10 略（COBOL、FORTRAN、PASCAL）

                                              回目录     老顽童校对整理  2003年5月