itgle.com
试题一（共 15 分）阅读以下说明和流程图，填补流程图中的空缺（1）～（9） ，将解答填入答题纸的对应栏内。[说明]假设数组 A 中的各元素 A(1)，A(2) ，…，A(M)已经按从小到大排序（M≥1） ；数组 B 中的各元素 B(1)，B(2)，…，B(N)也已经按从小到大排序（N≥1） 。执行下面的流程图后， 可以将数组 A 与数组 B 中所有的元素全都存入数组 C 中， 且按从小到大排序 （注意：序列中相同的数全部保留并不计排列顺序） 。例如，设数组 A 中有元素：2，5，6，7，9；数组B 中有
题目
试题一（共 15 分）
阅读以下说明和流程图，填补流程图中的空缺（1）～（9） ，将解答填入答题纸的对应栏内。
[说明]
假设数组 A 中的各元素 A(1)，A(2) ，…，A(M)已经按从小到大排序（M≥1） ；数组 B 中的各元素 B(1)，B(2)，…，B(N)也已经按从小到大排序（N≥1） 。执行下面的流程图后， 可以将数组 A 与数组 B 中所有的元素全都存入数组 C 中， 且按从小到大排序 （注意：序列中相同的数全部保留并不计排列顺序） 。例如，设数组 A 中有元素：2，5，6，7，9；数组B 中有元素：2，3，4，7；则数组 C 中将有元素：2，2，3，4，5，6，7，7，9。
[流程图]
相似考题
更多“ 试题一（共 15 分）阅读以下说明和流程图，填补流程图中的空缺（1）～（9） ，将解答填入答题纸的对应栏内。[说明]假设数组 A 中的各元素 A(1)，A(2) ，…，A(M)已经按从小到大排序（M≥1） ；数组”相关问题
-
第1题：
阅读下列说明和流程图，将应填入(n)处的语句写在对应栏内。
【说明】
有数组A(4,4)，把1到16个整数分别按顺序放入A(1,1)，…，A(1,4)，A(2,1)，…，A(2,4)，A(3,1)，…，A(3,4)，A(4,1)，…，A(4,4)中，下面的流程图用来获取数据并求出两条对角线元素之积。
【流程图】
正确答案：(1)141 (2)141 (3)1 (4)s×A[ii] (5)s×A[5-ii]
(1)1，4，1 (2)1，4，1 (3)1 (4)s×A[i,i] (5)s×A[5-i,i] 解析：本题考查用程序流程图描述数组及求对角线的和。
题目要求把1到16个整数分别按顺序放入A(1,1)，…，A(1,4)，A(2,1)，…，A(2,4)， A(3,1)，…，A(3,4)，A(4,1)，…，A(4,4)中，那么数组中的元素刚好构成一个方阵，用流程图求出这个方阵的对角线之积。下面来具体分析流程图。
第(1)空与第(2)空应该结合起来完成，它们都是一个循环判断语句的条件，从图中可以看出，如果这两个条件都成立，则读出当前数组中的元素值，根据题目要求，数组中的元素个数是每行4个每列4个，那么循环的上界应该是4，而下标是从1开始的，因此这两个空答案为1，4，1。
第(3)空是一个赋值语句，给变量s赋一个初值，从图中后面的语句不难看出s中存放的是求积的结果，那么在求积以前，s的值应该为1，因此此空答案为1。
第(4)空也是一个赋值语句，是在循环条件判断语句下，我们已经知道变量s中存放的是每次求积的结果，那么此空很明显是用来求积的，用当前取到的对角线元素乘以变量s中存放的值，因此此空答案为s×A[i,i]。
第(5)空和上一空非常相似，但它是用来求另外一条对角线的积的，它也是在一个循环下来实现的，这条对角线的元素位置与上面那条具有对称的特点，因此此空答案为s×A[5-i,i]。 -
第2题：
阅读以下说明和流程图，回答问题1-2，将解答填入对应的解答栏内。
[说明]
下面的流程图采用欧几里得算法，实现了计算两正整数最大公约数的功能。给定正整数m和 n，假定m大于等于n，算法的主要步骤为：
(1)以n除m并令r为所得的余数；
(2)若r等于0，算法结束；n即为所求；
(3)将n和r分别赋给m和n，返回步骤(1)。
[流程图]
[问题1] 将流程图中的(1)～(4)处补充完整。
[问题2] 若输入的m和n分别为27和21，则A中循环体被执行的次数是(5)。
正确答案：[问题1] (1) n＞m或nm或其它等效形式 (2) m←t (3) n←r (4) m%n [问题2] (5) 1
[问题1] (1) n＞m或nm或其它等效形式 (2) m←t (3) n←r (4) m%n [问题2] (5) 1 解析：(1)～(2)当n的值大于(等于)m时，应交换两者的值，再使用欧几里得算法；
(3)～(4)略；
(5)m，n和r在执行循环A前后的值分别为：
-
第3题：
阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。 【说明】 下面流程图的功能是:在给定的一个整数序列中查找最长的连续递增子序列。设序列存放在数组 A[1:n](n≥2)中，要求寻找最长递增子序列 A[K: K+L-1] (即A[K]<A[K+1]<…<A[K+L-1])。流程图中，用 Kj 和Lj 分别表示动态子序列的起始下标和长度，最后输出最长递增子序列的起始下标 K 和长度 L。 例如，对于序列 A={1 ，2，4，4 ，5，6，8，9，4，5，8}，将输出K=4， L=5。
【流程图】
注:循环开始框内应给出循环控制变量的初值和终值，默认递增值为1，格式为: 循环控制变量=初值，终值正确答案：（1）n-1
（2）Lj+1→Lj
（3）Lj > L
（4）Kj
（5）i+1
-
第4题：
阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。 【说明】 设有整数数组A[1：N]（N>1），其元素有正有负。下面的流程图在该数组中寻找连续排列的若干个元素，使其和达到最大值，并输出其起始下标K、元素个数L以及最大的和值M。 例如，若数组元素依次为3，-6，2，4，-2，3，-1，则输出K=3，L=4,M=7。该流程图中考察了A[1：N]中所有从下标i到下标j（j≥i）的各元素之和S，并动态地记录其最大值M。
【流程图】
注：循环开始框内应给出循环控制变量的初值和终值，默认递增值为1，格式为：循环控制变量=初值，终值正确答案：（1）i，N
（2）S+A[j]
（3）S
（4）j-i+1
（5）S
-
第5题：
?????? 阅读以下说明和流程图，填补流程图中的空缺(1)～(5)，将解答填入答题纸的
对应栏内。
【说明】
本流程图旨在统计一本电子书中各个关键词出现的次数。假设已经对该书从头到尾
依次分离出各个关键词{A(i)li=l，…，n}(n＞1)}．其中包含了很多重复项，经下面的流程
处理后，从中挑选出所有不同的关键词共m个{K（j）[j=l，…，m}，而每个关键词K（j）出现的次数为NK（j）．j=l，…，m。
??????
正确答案：
??流程图中的第1框显然是初始化。A(1)→K(1)意味着将本书的第1个关键词作为选出的第1个关键词。1→NK(1)意味着此时该关键词的个数置为1。m是动态选出的关键词数目，此时应该为1，因此(1)处应填1。?本题的算法是对每个关键词与已选出的关键词进行逐个比较。凡是遇到相同的，相??应的计数就增加1；如果始终没有遇到相同关键词的，则作为新选出的关键词。流程图第2框开始对i=2,n循环，就是对书中其他关键词逐个进行处理。流程图第3框开始j=l，m循环，就是按已进出的关键词依次进行处理。接着就是将关键词A(i)与选出的关键词K(j)进行比较。因此(2)处应填K(j)。如果A(i)=K(j)，则需要对计数器NK(j)增1．即执行NK(j)+1→NK(j)。因此(3)处应填NK(j)+I→NK(j)。执行后，需要跳出j循环，继续进行i循环，即根据书中的下一个关键词进行处理。如果A(i)不等于NK(j)，则需要继续与下个NK(j)进行比较，即继续执行j循环。如果直到j循环结束仍没有找到匹配的关键词，则要将该A(i)作为新的已选出的关键词。因此，应执行A(i)→K(m+1)以及m+l→m。更优的做法是先将计数器m增1，再执行A（j)→K(m)。因此(4)处应填m+l→m，(5)处应填A(i)。试题一参考答案(1)1(2)K(j)(3)Nk(j)+I→NK(j)或NK(j)十十或等价表示(4)m+l→m或m++或等价表示(5)A(i)?? -
第6题：
试题三（共15分）
阅读以下说明和C函数，回答问题 l和问题 2，将解答填入答题纸的对应栏内。
【说明】
对于具有n个元素的整型数组a，需要进行的处理是删除a中所有的值为 0的数组元素，并将a中所有的非 O元素按照原顺序连续地存储在数组空间的前端。下面分别用函数CompactArr_v1 和CompactArr v2来实现上述处理要求，函数的返回值为非零元素的个数。 函数CompactArr_vl(int a[]，int n)的处理思路是：先申请一个与数组a的大小相同的动态数组空间，然后顺序扫描数组a的每一个元素，将遇到的非O元素依次复制到动态数组空间中，最后再将动态数组中的元素传回数组a中。
函数CompactArr_v2(int a[]，int n)的处理思路是：利用下标i（初值为 0）顺序扫描数组a的每一个元素，下标k（初值为0）表示数组 a中连续存储的非0元素的下标。扫描时，每遇到一个数组元素，i就增 1，而遇到非 0元素并将其前移后k才增 1。
【问题1】 (12分)
请根据说明中函数CompactArr_v1的处理思路填补空缺(1)～(3)，根据CompactArr_v2的处理
思路填补空缺(4)。
【问题2】（3分）
请说明函数CompactArr vl存在的缺点。
正确答案：
试题三参考答案（共 15分）
【问题 1】 (12分)
(1) sizeof(int) （3分）
若考生解答为一个正整数，则给 2分
(2)temp[k++] 或*(temp+k++)或等价表示 （3分）
(3) ik 或等价表示 （3分）
(4)a[k++] 或*（a+k++）或等价表示 （3分）
【问题 2】（3分）
可能由于动态内存申请操作失败而导致函数功能无法实现，时间和空间效率低。
注：考生仅回答出运行速度慢则给 2分，其他含义相同的描述可给满分或酌情给分。 -
第7题：
阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
[说明]
两个包含有限个元素的非空集合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。
[流程图]
答案：解析：s
t
C[s]
D[t]
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[i]存入数组D。存入数组C之前，需要将其下标s增1；存入数组D之前，需要将其下标t增1。因此，初始时，应当给i赋0，使数组C的存数从C[1]开始。从而，(1)处应填s，(3)处应填C[s]。而数组D是在已有m个元素后续存，所以，初始时，数组D的下标t应当是m，续存是从D[m+1]开始的。因此，(2)处应填t，(4)处应填D[t]。
两重循环结束后，就要计算相似度s/t，将其赋予SIM，因此(5)处应填s/t。 -
第8题：
阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
[说明]
本流程图旨在统计一本电子书中各个关键词出现的次数。假设已经对该书从头到尾依次分离出各个关键词{A(i)|i=1,…,n}(n＞1)}，其中包含了很多重复项，经下面的流程处理后，从中挑选出所有不同的关键词共m个{K(j)|j=1,…,m}，而每个关键词K(j)出现的次数为NK(j),j=1,…,m。
[流程图]
答案：解析：1
K(j)
NK(j)+1→NK(i) 或NK(j)++ 或等价表示
m+1→m或m++ 或等价表示
A(i)
【解析】
流程图中的第1框显然是初始化。A(1)→K(1)意味着将本书的第1个关键词作为选出的第1个关键词。1→NK(1)意味着此时该关键词的个数置为1。m是动态选出的关键词数目，此时应该为1，因此(1)处应填1。
本题的算法是对每个关键词与已选出的关键词进行逐个比较。凡是遇到相同的，相应的计数就增加1；如果始终没有遇到相同关键词的，则作为新选出的关键词。
流程图第2框开始对i=2,n循环，就是对书中其他关键词逐个进行处理。流程图第3框开始j=1，m循环，就是按己选出的关键词依次进行处理。
接着就是将关键词A(i)与选出的关键词K(j)进行比较。因此(2)处应填K(j)。
如果A(i)=K(i)，则需要对计数器NK(j)增1，即执行NK(j)+1→NK(j)。因此(3)处应填NK(j)+1→NK(j)。执行后，需要跳出j循环，继续进行i循环，即根据书中的下一个关键词进行处理。
如果A(i)不等于NK(j)，则需要继续与下个NK(j)进行比较，即继续执行j循环。如果直到j循环结束仍没有找到匹配的关键词，则要将该A(i)作为新的已选出的关键词。因此，应执行A(i)→K(m+1)以及m+1→m。更优的做法是先将计数器m增1，再执行A(i)→K(m)。因此(4)处应填m+1→m，(5)处应填A(i)。 -
第9题：
阅读以下说明和流程图，填补流程图中的空缺(1)～(9)，将解答填入对应栏内。1、【说明】 假设数组A中的各元素A(1)，A(2)，…，A(M)已经按从小到大排序(M≥1)；数组B中的各元素B(1)，B(2)，…，B(N)也已经按从小到大排序(N≥1)。执行下面的流程图后，可以将数组A与数组B中所有的元素全都存入数组C中，且按从小到大排序 (注意：序列中相同的数全部保留并不计排列顺序)。例如，设数组A中有元素：2，5， 6，7，9；数组B中有元素2，3，4，7：则数组C中将有元素：2，2，3，4，5，6，7， 7， 9。【流程图】
答案：解析：（1）1(2)A(i)(3)B(j)(4)i(5)j(6)B(j)(7)A(i)(8)j(9)i
【解析】
这是最常见的一种合并排序方法。为对较大的序列进行排序，先将其分割成容量相当的几个部分，分别进行排序，最后再合并在一起。当然，这些排序要么都是升序，要么都是降序。本题全部是按升序排序的。 例如，为了将整副扑克牌按升序进行排序，先将其分割成两个部分(数量大致相当)，对每个部分完成升序排序后，就形成了两叠已排序的牌。如何将其合并呢?办法如下。 每次都比较各叠最上面的两张牌，取出比较小的，放入新堆，再继续比较。直到其中一堆空了，就将另一堆剩余的牌逐张放入新堆。新堆就是合并后的已完成排序的序列。 在数据排序时，遇到相同的数比较时，任取一个就可以了。 对本题来说，i、j、k是数组A、B、C的下标，初始时，都应该是1。因此，空(1)处应填写1。 将A(i)与B(j)进行比较后，如果A(i)≤B(j)，那么应该将A(i)→C(k)。这是升序的要求。因此，空(2)处应填A(i)。如果A(i)＞B(j)，则应将B(j)→C (k)。因此，空(3)处应填B(j)。 在A(i)→C(k)后，i应增加1，为下次取A(i)再比较做准备(k也需要增加1，为下次存入C(k)做准备)。这时，需要比较数组A是否已经取完，即判断i＞M是否成立。如果i＞M，则表示数组A中的元素已经全部取出，需要将数组B中剩余的元素逐个移入C(k)。因此，空(4)处应填i，空(6)处应填B(j)。数组B处的元素何时移完呢?这就需要判断i＞N是否成立。因此，空(8)处应填j。 同样，空(3)处将B(j)存入C(k)，直到，j＞N时数组B中的元素取完。此时，需要将数组A中剩余的元素逐个移入C(k)，直到i＞M时全部完成。因此，空(5)处应填j，空(7)处应填A(i)，空(9)处应填i。 -
第10题：
试题（15 分）阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏 内。【说明】设有整数数组 A[1：N]（N>1），其元素有正有负。下面的流程图在该数组 中寻找连续排列的若干个元素，使其和达到最大值，并输出其起始下标 K、元素 个数 L 以及最大的和值 M。例如，若数组元素依次为 3，-6，2，4，-2，3，-1，则输出 K=3，L=4,M=7。 该流程图中考察了 A[1：N]中所有从下标 i 到下标 j（j≥i）的各元素之和 S，并动态地记录其最大值 M。【流程图】
注：循环开始框内应给出循环控制变量的初值和终值，默认递增值为 1，格式为：循环控制变量=初值，终值答案：解析：1、j=i+1
2、S+A[j]
3、S
4、j-i+1
5、S -
第11题：
阅读下列说明，补充（1）-（9），将解答填入答题纸的对应栏内。
答案：解析：
-
第12题：
试题一（共 20 分）阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。【说明】设有二维整数数组（矩阵）A[1:m,1:n],其每行元素从左至右是递增的，每列元素从上到下是递增的。以下流程图旨在该矩阵中需找与给定整数 X 相等的数。如果找不到则输出“false”;只要找到一个（可能有多个）就输出“True”以及该元素的下标 i 和 j（注意数组元素的下标从 1 开始）。例如，在如下矩阵中查找整数 8，则输出伟：True,4,12 4 6 94 5 9 106 7 10 128 9 11 13流程图中采用的算法如下：从矩阵的右上角元素开始，按照一定的路线逐个取元素与给定整数 X 进行比较（必要时向左走一步或向下走一步取下一个元素），直到找到相等的数或超出矩阵范围（找不到）。【流程图】
【问题】该算法的时间复杂数是（）
供选择答案：A.O（1） B.O（m+n） C.（m*n） D,O（m2+n2）答案：解析：（1）n（2）j-1→j（3）i+1→I（4）j（5）C
【解析】
读题，可以看出元素查找的过程为从右上角开始，往右或者往下进行查找。因此，初始值i=1，j=n。如果查找值小于右上角值，则往右移动一位再进行比较。所以，第二空填j-1→j 。接下来是判断什么时候跳出循环。此时，终止循环的条件是：j=0，也就是其从最右端移到了最左端。再看X第13题：
试题一（共15分）
阅读以下说明，回答问题1至问题5，将解答填入答题纸对应的解答栏内。
【说明】
某网吧拓扑结构如图 1-1 所示，可提供影视、游戏竞技、视频聊天等多种服务，采用VLAN 划分来区分不同的服务。
问题 1】（2分）
网吧要求实现千兆接入，可采用的方式为 （1） 。
（1）备选答案：
A. FTTx
B. ADSL
C. PSTN拨号
正确答案：A
第14题：
阅读下列说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。 【说明】 设有二维整数数组（矩阵）A[1:m,1:n],其每行元素从左到右是递增的，每列元素从上到下是递增的。以下流程图旨在该矩阵中需找与给定整数X相等的数。如果找不到则输出“false”;只要找到一个（可能有多个）就输出“True”以及该元素的下标i和j（注意数组元素的下标从1开始）。 例如，在如下矩阵中查找整数8，则输出伟：True,4,1 2 4 6 9 4 5 9 10 6 7 10 12 8 9 11 13 流程图中采用的算法如下：从矩阵的右上角元素开始，按照一定的路线逐个取元素与给定整数X进行比较（必要时向左走一步或向下走一步取下一个元素），直到找到相等的数或超出矩阵范围（找不到）。
【流程图】
【问题】该算法的时间复杂数是（） 供选择答案：A.O（1） B.O（m+n） C.O（m*n） D,O（m²+n²）正确答案：（1）n
（2）j-1→j
（3）i+1→I
（4）j
（5）C
第15题：
阅读以下说明和流程图，填补流程图和问题中的空缺(1)～(5)，将解答填入答题纸的对应栏内。 【说明】 设整型数组A[1：N]每个元素的值都是1到N之间的正整数。一般来说，其中会有一些元素的值是重复的，也有些数未出现在数组中。下面流程图的功能是查缺查重，即找出A[1：N]中所有缺的或重复的整数，并计算其出现的次数（出现次数为0时表示缺）。流程图中采用的算法思想是将数组A的下标与值看作是整数集[1：N]加上的一个映射，并用数组C[1：N]记录各整数出现的次数，需输出所有缺少的或重复的数及其出现的次数。
【流程图】
【问题】 如果数组A[1：5]的元素分别为{3，2，5，5，1}，则算法流程结束后输出结果为： (5) 。 输出格式为：缺少或重复的元素，次数（0表示缺少）正确答案：(1)A[i]
(2)C[k]+1
(3)0
(4)k 和C[k]
(5)4,{1,1,1,0,2}
第16题：
试题一（共15分）
阅读以下说明和流程图，填补流程图中的空缺(1)～(5)，将解答填入答题纸的
对应栏内。
【说明】
两个包含有限个元素的非空集合A、B的相似度定义为IAUBI/IA U Bl，即它们的交
集大小(元素个数)与并集大小之比。
以下的流程图计算两个非空整数集合（以数组表示）的交集和并集，并计算其相似
度。己知整数组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。
正确答案：
本题考查程序处理流程图的设计能力。
首先我们来理解两个有限集合的相似度的含义。两个包含有限个元素的非空集合A、
B的相似度定义为它们的交集大小（元素个数）与并集大小之比。如果两集合完全相等，
则相似度必然为1(100%)；如果两集合完全不同（没有公共元素），则相似度必然为0；
如果集合A中有一半元素就是集合B的全部元素，而另一半元素不属于集合B，则这两
个集合的相似度为0.5(50%)。因此，这个定义符合人们的常理性认识。
在大数据应用中，经常要将很多有限集进行分类。例如，每天都有大量的新闻稿。
为了方便用户检索，需要将新闻稿分类。用什么标准来分类呢？每一篇新闻稿可以用其
中所有的关键词来表征。这些关键词的集合称为这篇新闻稿的特征向量。两篇新闻稿是
否属于同一类，依赖于它们的关键词集合是否具有较高的相似度（公共关键词个数除以
总关键词个数）。搜索引擎可以将相似度超过一定水平的新闻稿作为同一类。从而，可以
将每天的新闻稿进行分类，就可以按用户的需要将某些类的新闻稿推送给相关的用户。
本题中的集合用整数组表示，因此，需要规定同一数组中的元素各不相同（集合中
的元素是各不相同的）。题中，整数组A[1：m]，和B[l：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[1]开始。从而，()处应填s，(3)处应填C[s]。而数组D
是在已有m个元素后续存，所以，初始时，数组D的下标t应当是m，续存是从D【m+1】
开始的。因此，(2)处应填t，(4)处应填D[t]。
两重循环结束后，就要计算相似度s／t，将其赋予SIM，因此(5)处应填s／t。
参考答案
(l)s(2)t(3)C[s](4)D[t](5)s／t
第17题：
●试题一
阅读下列说明和流程图，将应填入(n)处的语句写在答题纸的对应栏内。
【说明】
下列流程图用于从数组K中找出一切满足：K(I)+K(J)=M的元素对(K(I)，K(J))(1≤I≤J≤N)。假定数组K中的N个不同的整数已按从小到大的顺序排列，M是给定的常数。
【流程图】
此流程图1中，比较"K(I)+K(J)∶M"最少执行次数约为 (5) 。
图1
正确答案：
●试题一【答案】(1)(2)<(3)I+l->I(4)J-1->J(5)「N／2」【解析】该算法的思路是：设置了两个变量I和J，初始时分别指向数组K的第一个元素和最后一个元素。如果这两个元素之和等于M时，输出结果，并这两个指针都向中间移动；如果小于M，则将指针I向中间移动(因为数组K已按从小到大的顺序排列)；如果大于M，则将指针J向中间移动(因为数组K已按从小到大的顺序排列)。当IJ时，说明所有的元素都搜索完毕，退出循环。根据上面的分析，(1)、(2)空要求填写循环结束条件，显然，(1)空处应填写""，(2)空处应填写"<"。这里主要要注意I=J的情况，当I=J时，说明指两个指针指向同一元素，应当退出循环。(3)空在流程图有两处，一处是当K(I)+K(J)=M时，另一处是当K(I)+K(J)<M时，根据上面分析这两种情况都要将指针I向中间移动，即"I+1->I"。同样的道理，(4)空处应填写"J-1->J"。比较"K(I)+K(J)：M"最少执行次数发生在第1元素与第N个元素之和等于M、第2元素与第N-1个元素之和等于M、……，这样每次比较，两种指针都向中间移动，因此最小执行次数约为"N-2"。第18题：
试题三（共 15 分）
阅读以下说明和 C 程序，将应填入 （n） 处的字句写在答题纸的对应栏内。
正确答案：
第19题：
阅读下列说明和流程图，填补流程图中的空缺（1）~（9），将解答填入答题纸的对应栏内。【说明】假设数组A中的各元素A⑴，A (2)，…，A (M)已经按从小到大排序(M>1):数组B中的各元素B(1) , B (2) . B (N)也已经按从小到大排序(N≥1)。执行下面的流程图后，可以将数组A与数组B中所有的元素全都存入数组C中，且按从小到大排序(注意：序列中相同的数全部保留并不计排列顺序)。例如，设数组A中有元素： 2,5,6,7,9;数组B中有元素： 2,3,4,7;则数组C中将有元素： 2,2,3,4,5,6,7，7,9.
答案：解析：(1)1 (2)A (i) (3) B (j)⑷ i (5)J(6) B (j)(7) A (i)(8) j(9) i第20题：
阅读以下C代码，回答问题（1）~（6），将解答填入答题纸的对应栏内。【说明】函数insertElem的功能是在元素升序排列的数组中加入一个新元素并保持数组元素升序排列的特点。在main函数中输入若干表示价格的实数，输入为0或负数或实数个数超出限定数量时终止，调用insertElem将价格按升序保存在数组pdata中，最后输出所输入的实数
答案：解析：（1）arr[n]（2）arr[i+1]=arr[i]（3）arr[i+1]（4）break（5）pdata,n,price（6）idx【解析】
1空如果所有元素都比带插入元素小，那么带插入元素排在最后。23空插入元素并将其他元素后移4空如果price小于等于0，则break终止循环5空调用inserElem函数时填写的参数6遍历所有元素并输出结果。第21题：
阅读说明和流程图，填补流程图中的空缺（1）?（5），将答案填入答题纸对应栏内。【说明】本流程图用于计算菲波那契数列{a1=1，a2=1，…,an=an-1+an-2!n=3,4,…}的前n项（n>=2) 之和S。例如，菲波那契数列前6项之和为20。计算过程中，当前项之前的两项分别动态地保存在变量A和B中。【流程图】
答案：解析：（1）2或A+B（2）n（3）A+B（4）B-A（5）S+B
【解析】
菲波那契数列的特点是首2项都是1，从第3项开始，每一项都是前两项之和。该数列的前几项为1，1，2, 3，5，8，…。在流程图中，送初始值1—A，2—B后，显然前2项的和S应等于2,所以（1）处应填2 (或A+B)。此时2→i (i表示动态的项编号），说明已经计算出前2项之和。接着判断循环的结束条件。显然当i=n时表示已经计算出前n项之和，循环可以结束了。因此（2）处填n。判断框中用“>”或“≥”的效果是一样的，因为随着i的逐步增1，只要有i=n结束条件就不会遇到i>n的情况。不过编程的习惯使循环结束条件扩大些，以防止逻辑出错时继续循环。接下来i+1→i表示数列当前项的编号增1，继续往下计算。原来的前两项值（分别在变量A和B中）将变更成新的前两项再放到变量A和B中。
首先可以用A+B—B实现（原A) + (原B)—(新B)，因此（3）处填A+B。为了填新A值（原来的B值)，不能用B—A，因为变量B的内容已经改变为（原A) + (原B)，而B-A正是（（原A) + (原B))-(原A)=(原B)，因此可以用B-A—A来实现新A的赋值。这样，（4）处填B-A。最后应是前n项和值的累加（比原来的S值增加了新B值)，所以（5）处应填S+B。填完各个空后，最好再用具体的数值来模拟流程图走几个循环检查所填的结果（这是防止逻辑上出错的好办法）。第22题：
第一题 阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
【说明】
对于大于1的正整数n，(x+1)n可展开为
问题：1.1 【流程图】
注：循环开始框内应给出循环控制变量的初值和终值，默认递增值为1。
格式为：循环控制变量=初值，终值，递增值。答案：解析：（1）2，n，1
（2）A[k]
（3）k-1，1，-1
（4）A[i]+A[i-1]
（5）A[i]
【解析】
（1）（3）空为填写循环初值终值和递增值，题目中给出的格式为循环控制变量=初值，终值，递增值。按照题意，实质为求杨辉三角。如下图：
第23题：
阅读以下说明和流程图，填写流程图中的空缺，将解答填入答题纸的对应栏内。【说明】设[a1b1],[a2b2],...[anbn]是数轴上从左到右排列的n个互不重叠的区间（a1
答案：解析：1.A2.ai3.bi4.A 、B5.B
【解析】
若A≤ai则输出A，反之输出ai。若A≤bi不满足则输出bi，依次类推。