2013年下半年下午程序员考试试题-

案例分析-答案与解析

试题一（共15分）

【说明】

两个包含有限个元素的非空集合A、B的相似度定义为|A n B|/|A U 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}, 贝U C={1,4},D={1,2,3,4,5,6},A 与 B 的相似度SIM=1/3。

阅读以上说明和流程图，填补流程图中的空缺（1） ? （5），将解答填入答题纸的对应栏内。【参考答案】

⑵、t

⑶、C[s]

（4）、D[t]

（5）、s/t

【答案解析】

Ani-Din. AIII»I <

学习-----好资料

首先我们来理解两个有限集合的相似度的含义。两个包含有限个元素的非空集合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。

试题二（10分）

【说明】

下面的函数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的每个元素值，并将相应个数的数值顺序地写入结果序列即可。

对于上例，所得数组b的各个元素值如下：

B[0]B[1]B[2]B[3]B[4]B[5]