2013下半年程序员考试真题及答案-下午卷.doc-资料库

第1页 / 共19页

第2页 / 共19页

第3页 / 共19页

第4页 / 共19页

第5页 / 共19页

第6页 / 共19页

第7页 / 共19页

第8页 / 共19页

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 的每个元素值，并将相应个数的数值顺序地写入结果序列即可。对于上例，所得数组 b 的各个元素值如下：那么在输出序列中写入 1 个 4、2 个 5、4 个 6、1 个 8、1 个 9,即得 4,5,5,6,6,6,6,8,9, 从而完成排序处理。【C 函数】

阅读以上说明和 C 函数，填充函数中的空缺，将解答填入答题纸的对应栏内。答案解析： (1)afi]maximum,或 a[i]>=maximum,或其等价形式 (3)0 (4)b[k],或 b[k]>0,或 b[k]!=0,或其等价形式 (5)k 本题考查 C 程序的基本语法和运算逻辑。首先应认真分析题目中的说明，然后确定代码结构和各变量的作用。空(1)和(2)所在 for 语句的功能是求出数组 a 中的最小元素 minimum 和最大元素 maximum。在设置了 minimum 和 maximum 的初始值后，空(1)处的判断条件是只要目前的元素

a[i]小于 minimum,就需要更新 minimum，反之，空(2)处的判断条件是只要目前的元素 a[i] 大于 maximum，就需要更新 maximum，因此空(1)处应填入 a[i]maximum 或其等价方式。minimum 和 maximum 的作用是要确定计数数组 b 的大小。根据题目中的描述，序列中的每个元素 a[i]都对应到计数数组 b[]的一个元素 b[k]，对应方式为：k=a[i]-minimum,其中 minimum 是数组 a 中的最小元素，显然在计数时，一个数值出现一次，就在对应的 b[k]中累加一次。空(3)〜(5)所在的语句组是产生排序后的序列，重新写入数组 a。首先需明确变量 i 和 k 的作用，根据它们在该语句组中的出现位置，i 用于表示数组 a 的元素下标，k 用于表示数组 b 中元素的下标，因此，空(3)处应填入 0,使得从数组 a 中下标为 0 的数组元素开始。通过循环控制“for(k=0;k0” 或其等价形式。由于 b[k]中记录的是元素 k+minimum 的出现次数，所以空(5)处应填入"k"，从而将元素值恢复后再写回去。

试题三【说明 1】 F 面的函数 countChar(char*text)统计字符串 text 中不同的英文字母数和每个英文字母出现的次数(英文字母不区分大小写)。【C 代码 1】【说明 2】将下面 C 代码 2 中的空缺补全后运行，使其产生以下输出。 f2:f2:f2:2 f3:f3:1 【C 代码 2】

阅读以上说明和 C 代码，填充代码中的空缺，将解答填入答题纸的对应栏内。答案解析： (1)text,或&text[0],或其等价形式 (2)ptr++,或++ptr,或 ptr=ptr+l,或 ptr+=l (3)c[i],或*(c+i) (4)f2 (5)f3 (6)f(n),或(*f)(n)

本题考查数据指针、运算逻辑和函数指针的应用。首先应认真分析题目中的说明，然后确定代码结构和各变量的作用。在函数 countChar(char*text)中来统计字符串 text 中不同的英文字母数和每个英文字母出现的次数。用来表示计数值的数组元素 c[i]需要与英文字母对应起来，方式为 c[0]记录字母 A 或 a 的次数，c[l]记录字母 B 或 b 的次数，依此类推，因此 i=英文字母-‘A’(英文字母为大写)或 i=英文字母-‘a’(英文字母为小写)。数据指针是指向数据的指针变量。数据指针 ptr 用来表示 text 中的每一个字符，初始时 ptr 指向第一个字符，因此空(1)处应填入“text”或其等价方式，(2)处的作用是随循环控制逐个指出 text 中的后续字符，因此空(2)处应填入“ptr++”或其等价方式。显然，若 c[i]的值不为 0 则表示字符‘A’+i 或‘a’+i 出现了，反之，则表示字符‘A’ +i 或‘a’+i 未出现，因此在计算字符种类时只要判断 c[i]是否为 0 即可，因此空(3)处应填入“c[i]”或其等价形式。函数指针是指向函数的指针变量。根据代码 2 的声明“intfl(int(*f)(int))；w 可知调用函数 fl 时，实参应该是函数名或函数指针，且函数名或函数指针指向的函数应有一个整型参数，返回值为整型，而 f2 和 fi 都是符合这种定义类型的函数。 C 代码 2 中，在 main 函数中两次调用了函数 fl，分析运行结果可知，是先以 f2 为实参调用 fl,然后以 fi 为实参调用 fl,因此空(4)和(5)分别填入“f2”或“f3”或它们的等价形式，在空(6)处应填入“f(n)”或其等价形式来实现最后对 f2 和 f3 的调用。

资料库

2013下半年程序员考试真题及答案-下午卷.doc

相关推荐

程序员考试

热门标签

最新资料