阅读以下说明和流程图，填补流程图和问题中的空缺(1)～(5)，将解答填入答题纸的对应栏内。【说明】设整型数组A[1：N]每个元素的值都是1到N之间的正整数。一般来说，其中会有一些元素的值是重复的，也有些数未出现在数组中。下面流程图的功能是查缺查重，即找出A[1：N]中所有缺的或重复的整数，并计算其出现的次数（出现次数为0时表示缺）。流程图中采用的算法思想是将数组A的下标与值看作是整数集[1：N]加上的一个映射，并用数组C[1：N]记录各整数出现的次数，需输出所有缺少的或重复的数及其出现的次数。【流程图】【

阅读以下说明和流程图，填补流程图中的空缺(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。

【流程图】

阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。

【说明】对于大于1的正整数n，(x+1)n可展开为下面流程图的作用是计算(x+1)n展开后的各项系数（i=0,1,....,n）并依次存放在数组A[0...n]中。方法是依次计算k=2，3，..，n时(x+1)k的展开系数并存入数组A，在此过程中，对任一确定的k，利用关系式，按照i递减的顺序逐步计算并将结果存储在数组A中。其中，和都为1，因此可直接设置A[0]、A[k]的值为1。 例如，计算(x+1)3的过程如下：先计算(x+1)2(即k=2)的各项系数，然后计算(x+1)3(即k=3)的各项系数。K=2时，需要计算，和，并存入A[0]，A[1]和A[2]，其中A[0]和A[1]的值已有，因此将（即A[1]）和即(A[0])相加得到的值并存入A[1]。k=3时，需要计算，和和，先计算出(由)得到并存入A[2]，再计算(由得到)并存入A[1]。

阅读以下说明和流程图，回答问题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)。

试题一（共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。

●试题二

阅读下列说明、流程图和算法，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

下面的流程图(如图3所示)用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以4为基准数的划分过程如下：

【流程图】

图3流程图

【算法说明】

将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A[]，int low，int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[]，int L，int H)的功能是实现数组A中元素的递增排序。

【算法】

void sort (int A[]， int 1，int H){

if ( L<H){

k=p(A，L，R)；//p()返回基准数在数组A中的下标

sort( (4) )；//小于基准数的元素排序

sort( (5) )；//大于基准数的元素排序

}

}

试题一（共 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。

[流程图]

阅读下列说明和流程图，将应填入(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)～(5)，将解答填入对应栏内。

[说明]

下面的流程图旨在统计指定关键词在某一篇文章中出现的次数。

设这篇文章由字符A(0)，…，A(n-1)依次组成，指定关键词由字符B(0)，…，B(m-1)依次组成，其中，n＞m≥1。注意，关键词的各次出现不允许有交叉重叠。例如，在“aaaa”中只出现两次“aa”。

该流程图采用的算法是：在字符串A中，从左到右寻找与字符串B相匹配的并且没有交叉重叠的所有子串。流程图中，i为字符串A中当前正在进行比较的动态予串首字符的下标，j为字符串B的下标，k为指定关键词出现的次数。

[流程图]

阅读下列说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。 【说明】 设有二维整数数组（矩阵）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)～(5)，将解答填入答题纸的

对应栏内。

【说明】

本流程图旨在统计一本电子书中各个关键词出现的次数。假设已经对该书从头到尾

依次分离出各个关键词{A(i)li=l，…，n}(n＞1)}．其中包含了很多重复项，经下面的流程

处理后，从中挑选出所有不同的关键词共m个{K（j）[j=l，…，m}，而每个关键词K（j）出现的次数为NK（j）．j=l，…，m。

??????

●试题一

阅读下列说明和流程图，将应填入(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