初级程序员 2019年 下半年 下午

第1题

阅读以下说明和流程图，填写流程图中的空缺，将解答填入答题纸的对应栏内。

【说明】

某系统中有N个等长的数据记录，其主键值为随机排序且互不相等的正整数编号，表示为K(0)，K(1)，...，K(N-1)。

现采用杂凑法将各数据记录存入区域S(0)，S(1)，S(M-1)中（M≥N），以加快按主键值检索的效率（初始时各区域都是空的）。

下面流程图中，选用适当的质数P（N≤P≤M），对每个主键值先计算出它除以P的余数j。

如果区域S(j)已占用，则考查下一个区域S(j+1)，……，直到发现某个区域为空时，则将该主键值相应的数据记录存入该区域（注意，S(M-1)的下一个区域是S(0)）。

为了标记每个区域是否已占用，采用了M个标记位F(0)，F(1)，……，F(M-1)。

初始时所有的标记位都为0，每当一个区域被占用时，将相应的标记位置1。

例如，设6个记录的主键值分别为31、15、20、35、18、10，取质数P=7，用上述杂凑法将这些记录存入区域S(0)~S(7)后，各区域中记录的主键值依次为35、15、空、31、18、10、20、空。

【流程图】