阅读以下说明和流程图,填补流程图和问题中的空缺(1)~(5),将解答填入答题纸的对应栏内。【说明】设整型数组A[1:N]每个元素的值都是l到N之间的正整数。一般来说,其中会有一些元素的值是重复的,也有些数未出现在数组中。下面流程图的功能是查缺查重,即找出A[1:N]中所有缺失的或重复的整数,并计算其出现的次数(出现次数为0时表示缺)。流程图中采用的算法思想是将数组A的下标与值看作是整数集[1:N]上的一个映射,用数组C[1:N]依次记录各整数k出现的次数c[k],并输出所有缺失的或重复的数及其出现的次数。【流程图】
【正确答案】正确答案:(1)A[i] (2)C[k]+1 (3)1 (4)k,C[k] (5)4,0 5, 2
【答案解析】解析:本题考查程序设计算法即流程图的设计。 先以问题中的简例来理解算法过程。 已知A[1:5]={3,2,5,5,1}。初始时计数数组c[1:5]={0,0,0,0,0}。 再逐个处理数组A的各个元素(根据A[i]的值在c[A[i/]/]中计数加1): A[1]=3,计数c[3]=1;A[2]:2,计数c[2]=1;A[3]=5,计数c[5]=1;A[4]=5,计数c[5]=2;A[5]=1,计数c[1]=1。最后,计算得到c[1:5]={1,1,1,0,2),即表明A[1:5]中数4缺失,数5有2,其他数都只有1个。 再看流程图。左面先对数组C初始化(赋值都是0)。再对A[i]各个元素逐个进行处理。将A[i]送k,再对c[k]计数加1。因此,(1)处应填A[i],(2)处应填c[k]+1→c[k]。 流程图右面需要输出计算结果。对于k的循环,当c[k]=1时(非缺非重)不需要输出;否则,应按要求的格式输出:缺或重的数,以及出现的次数。为此,(3)处应填1(与1比较),(4)处应填k,c[k]。 再看简例的输出,先输出4,0(数4缺失);再输出5,2(数5有2个)。