下六个月下午程序员考试试题-
案例分析－答案与解析
试题一（共1５分)
【阐明】
两个包具有限个元素的非空集合A、B的相似度定义为|A∩B|/|Ａ∪B|,即它们的交集大小(元素个数)与并集大小之比。
如下的流程图计算两个非空整数集合(以数组表达）的交集和并集，并计算其相似度。已知整数组A［1:m］和B[1：n］分别存储了集合A和B的元素（每个集合中包括的元素各不相似)，其交集寄存于数组C［１:s],并集寄存于数组D［1:t］，集合A和Ｂ的相似度寄存于ＳＩM。
例如,假设A={1,2，３,4},B＝{1,4，５,６},则C＝{1，4},Ｄ=｛１,2,3,4,５,6｝,A与Ｂ的相似度SIＭ＝１/3。
阅读以上阐明和流程图，弥补流程图中的空缺(1)?(5),将解答填入答题纸的对应栏内。
【参照答案】
(1)、ｓ
(2）、ｔ
（３)、C[s］
(4)、Ｄ［t]
（５）、s/ｔ
【答案解析】
首先我们来理解两个有限集合的相似度的含义。两个包具有限个元素的非空集合A、B的相似度定义为它们的交集大小(元素个数)与并集大小之比。假如两集合完全相等,则相似度必然为１(100%);假如两集合完全不一样（没有公共元素),则相似度必然为０；假如集合Ａ中有二分之一元素就是集合Ｂ的所有元素,而另二分之一元素不属于集合B，则这两个集合的相似度为0．5(5０%）。因此，这个定义符合人们的常理性认识。
在大数据应用中,常常要将诸多有限集进行分类。例如，每天均有大量的新闻稿。为了以便顾客检索，需要将新闻稿分类。用什么原则来分类呢?每一篇新闻稿可以用其中所有的关键词来表征。这些关键词的集合称为这篇新闻稿的特性向量。两篇新闻稿与否属于同一类，依赖于它们的关键词集合与否具有较高的相似度(公共关键词个数除以总关键词个数)。搜索引擎可以将相似度超过一定水平的新闻稿作为同一类。从而,可以将每天的新闻稿进行分类，就可以按顾客的需要将某些类的新闻稿推送给有关的顾客。
本题中的集合用整数组表达，因此,需要规定同一数组中的元素各不相似(集合中的元素是各不相似的)。题中,整数组A[１:m]和B[1:ｎ]分别存储了集合A和B的元素。流程图的目的是将A、B中相似的元素寄存入数组Ｃ［1:ｓ](共s个元素)，并将A、B中的所有元素（相似元素只取一次)寄存入数组D[1:ｔ](共t个元素)，最终再计算集合A和B相似度s/t。
流程图中的第一步显然是将数组A中的所有元素放入数组Ｄ中。随即，只需要对数组B中的每个元素进行判断，凡与数组A中某个元素相似时,就将其存入数组C;否则就续存入数组D(注意,数组D中已经有m个元素)。这需要对j(遍历数组B)与ｉ（遍历数组A)进行两重循环。判断框B[j］=A[i]成立时,B[ｊ]应存入数组Ｃ;否则应继续i循环，直到循环结束仍没有相等状况出现时，就应将Ｂ[j]存入数组D。存入数组Ｃ之前,需要将其下标ｓ增１;存入数组D之前,需要将其下标t增1。因此,初始时，应当给ｊ赋0,使数组C的存数从C［l]开始。从而，（１)处应填ｓ，(3)处应填C[s]。而数组Ｄ是在已经有m个元素后续存，因此,初始时,数组Ｄ的下标ｔ应当是m，续存是从Ｄ［m＋1]幵始的。因此，（2)处应填ｔ,(4)处应填Ｄ［t]。
两重循环结束后，就要计算相似度s／t，将其赋予ＳIM，因此(5）处应填s/t。
试题二(10分）
【阐明】
下面的函数ｓort（inｔn，inｔa［］)对保留在数组a中的整数序列进行非递减排序。由于该序列中的元素在一定范围内反复取值,因此排序措施是先计算出每个元素出现的次数并记录在数组b中，再从小到大次序地排列各元素即可得到一种非递减有序序列。例如,对于序列6,5,６,9，６，４,8，６,5，其元素在整数区间[4，9]内取值,因此使数组元素b[0］?b[5］的下标0?5分别对应数值４?9,次序地扫描序列的每一种元素并合计其出现的次数,即将4的个数记入ｂ[0],5的个数记入b[1],依此类推，９的个数记入b[5]。最终依次判断数组ｂ的每个元素值,并将对应个数的数值次序地写入成果序列即可。
对于上例,所得数组b的各个元素值如下:
B[0]
B[1]
B[２］
Ｂ[3]
B[4]
B[5]
1
2
4
0
1
１
那么在输出序列中写入1个4、2个５、4个6、1个8、1个9，即得4,5,5,6,6,6,6,８,9，从而完毕排序处理。
【C函数】
阅读以上阐明和C函数,填充函数中的空缺,将解答填入答题纸的对应栏内。
【参照答案】
(1)、afi]minimｕm，或a[i]=miｎｉmum，或其等价形式
（２）、a［i]maｘimｕm，或a[i］＝mａｘimｕm，或其等价形式
(3)、0
（4)、b[k]，或b［k]0，或b[k］!＝0,或其等价形式
(5）、k
【答案解析】