2013下半年程序员考试真题及答案-下午卷
试题一
【说明】
两个包含有限个元素的非空集合A、B的相似度定义为|A∩B|/|A∪B|，即它们的交集大小(元素个数)与并集大小之比。
以下的流程图计算两个非空整数集合(以数组表示)的交集和并集，并计算其相似度。已知整数组A[1:m]和B[1:n]分别存储了集合A和B的元素(每个集合中包含的元素各不相同)，其交集存放于数组C[1:s]，并集存放于数组D[1:t]，集合A和B的相似度存放于SIM。
例如，假设A={1,2,3,4},B={1,4,5,6},则C={1,4},D={1,2,3,4,5,6},A与B的相似度SIM=1/3。
阅读以上说明和流程图，填补流程图中的空缺(1)〜(5)，将解答填入答题纸的对应栏内。
答案解析：
(1)s (2)t (3)C[s] (4)D[t] (5)s/t
本题考査程序处理流程图的设计能力。
首先我们来理解两个有限集合的相似度的含义。两个包含有限个元素的非空集合A、B的相似度定义为它们的交集大小(元素个数)与并集大小之比。如果两集合完全相等，则相似度必然为1(100%);如果两集合完全不同(没有公共元素)，则相似度必然为0;如果集合A中有一半元素就是集合B的全部元素，而另一半元素不属于集合B，则这两个集合的相似度为0.5(50%)。因此，这个定义符合人们的常理性认识。
在大数据应用中，经常要将很多有限集进行分类。例如，每天都有大量的新闻稿。为了方便用户检索，需要将新闻稿分类。用什么标准来分类呢？每一篇新闻稿可以用其中所有的关键词来表征。这些关键词的集合称为这篇新闻稿的特征向量。两篇新闻稿是否属于同一类，依赖于它们的关键词集合是否具有较高的相似度(公共关键词个数除以总关键词个数)。搜索引擎可以将相似度超过一定水平的新闻稿作为同一类。从而，可以将每天的新闻稿进行分类，就可以按用户的需要将某些类的新闻稿推送给相关的用户。
本题中的集合用整数组表示，因此，需要规定同一数组中的元素各不相同(集合中的元素是各不相同的)。题中，整数组A[1:m]和B[1:n]分别存储了集合A和B的元素。流程图的目标是将A
、B中相同的元素存放入数组C[1:s](共s个元素)，并将A、B中的所有元素(相同元素只取一次)存放入数组D[1:t](共t个元素)，最后再计算集合A和B相似度s/t。
流程图中的第一步显然是将数组A中的全部元素放入数组D中。随后，只需要对数组B中的每个元素进行判断，凡与数组A中某个元素相同时，就将其存入数组C;否则就续存入数组D(注意，数组D中已有m个元素)。这需要对j(遍历数组B)与i(遍历数组A)进行两重循环。判断框B[j]=A[i]成立时，B[j]应存入数组C;否则应继续i循环，直到循环结束仍没有相等情况出现时，就应将B[j]存入数组D。存入数组C之前，需要将其下标s增1;存入数组D之前，需要将其下标t增1。因此，初始时，应当给j赋0,使数组C的存数从C[l]开始。从而，(1)处应填s，(3)处应填C[s]。而数组D是在已有m个元素后续存，所以，初始时，数组D的下标t应当是m，续存是从D[m+1]幵始的。因此，(2)处应填t，(4)处应填D[t]。
两重循环结束后，就要计算相似度s/t，将其赋予SIM，因此(5)处应填s/t。
试题二
【说明】
下面的函数sort(intn，inta[])对保存在数组a中的整数序列进行非递减排序。由于该序列中的元素在一定范围内重复取值，因此排序方法是先计算出每个元素出现的次数并记录在数组b中，再从小到大顺序地排列各元素即可得到一个非递减有序序列。例如，对于序列6,5,6,9,6,4,8,6,5,其元素在整数区间[4,9]字符串截取从某个字符到最后一位内取值，因此使数组元素b[0]〜b[5]的下标0〜5分别对应数值4〜9,顺序地扫描序列的每一个元素并累计其出现的次数，即将4的个数记入b[0]，5的个数记入b[1]，依此类推，9的个数记入b[5]。最后依次判断数组b的每个元素值，并将相应个数的数值顺序地写入结果序列即可。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。