阅读以下说明和算法，完善算法并回答问题，将解答写在对应栏内。[说明]假设以二维数组G[1..m,1..n]表示一幅图像各像素的颜色，则G[i,j]表示区域中点(i,j]处的颜色，颜色值为0到k的整数。下面的算法将指定点(i0,j0)所在的同色邻接区域的颜色置换为给定的颜色值。约定所有与点(i0,j0)同色的上、下、左、右可连通的点组成同色邻接区域。例如，一幅8×9像素的图像如图1-1所示。设用户指定点(3,5)，其颜色值为0，此时其上方(2,5)、下方(4,5)、右方(3,6)邻接点的颜色值都为0，因此这
题目
阅读以下说明和算法，完善算法并回答问题，将解答写在对应栏内。
[说明]
假设以二维数组G[1..m,1..n]表示一幅图像各像素的颜色，则G[i,j]表示区域中点(i,j]处的颜色，颜色值为0到k的整数。
下面的算法将指定点(i0,j0)所在的同色邻接区域的颜色置换为给定的颜色值。约定所有与点(i0,j0)同色的上、下、左、右可连通的点组成同色邻接区域。
例如，一幅8×9像素的图像如图1-1所示。设用户指定点(3,5)，其颜色值为0，此时其上方(2,5)、下方(4,5)、右方(3,6)邻接点的颜色值都为0，因此这些点属于点(3,5)所在的同色邻接区域，再从上、下、左、右四个方向进行扩展，可得出该同色邻接区域的其他点(见图1-1中的阴影部分)。将上述同色区域的颜色替换为颜色值7所得的新图像如图1-2所示。
[算法]
输入：矩阵G，点的坐标(i0,j0)，新颜色值newcolor。
输出：点(i0,j0)所在同色邻接区域的颜色置换为newcolor之后的矩阵G。
算法步骤(为规范算法，规定该算法只在第七步后结束)：
第一步：若点(i0,j0)的颜色值与新颜色值newcolor相同，则(1)；
第二步：点(i0,j0)的颜色值→oldcolor；创建栈S，并将点坐标(i0,j0)入栈；
第三步：若(2)，则转第七步；
第四步：栈顶元素出栈→(x,y)，并(3)；
第五步：
1) 若点(x,y-1)在图像中且G[x,y-1]等于oldcolor,则(x,y-1)入栈S；
2) 若点(x,y+1)在图像中且G[x,y+1]等于oldcolor,则(x,y+1)入栈S；
3) 若点(x-1,y)在图像中且G[x-1,y]等于oldcolor,则(x-1,y)入栈S；
4) 若点(x+1,y)在图像中且G[x+1,y)等于oldcolor,则(x+1,y)入栈S：
第六步：转(4)；
第七步：算法结束。
[问题]
是否可以将算法中的栈换成队列?回答：(5)。
相似考题
更多“ 阅读以下说明和算法，完善算法并回答问题，将解答写在对应栏内。[说明]假设以二维数组G[1..m,1..n]表示一幅图像各像素的颜色，则G[i,j]表示区域中点(i,j]处的颜色，颜色值为0到k的整数。下面的算法将”相关问题
-
第1题：
阅读下列函数说明和C代码，将应填入(n)处的字句写在对应栏内。
【说明】
函数QuickSort是在一维数组A[n]上进行快速排序的递归算法。
【函数】
void QuickSort( int A[ ],int s,int t)
{ int i=s,j=t+1,temp;
int x=A[s];
do{
do i ++ ;while (1);
do j -- ;while(A[j]＞x);
if(i＜j){temp=A[i];(2);(3);}
}while(i＜j);
A[a] =A[j];A[j] =x;
if(s＜i-1) (4);
if(j+1＜t) (5);
}
正确答案：(1)A[i]x (2)A[i]=A[j] 3)A[j]=temp (4)QuickSort(Asj-1) (5)QuickSort(Aj+1t)；
(1)A[i]x (2)A[i]=A[j] 3)A[j]=temp (4)QuickSort(A，s，j-1) (5)QuickSort(A，j+1，t)； 解析：快速排序的思想是：任取待排序序列中的某个元素作为基准(一般取第一个元素)，通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面单元，排序码较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。 -
第2题：
阅读下列说明和C代码，回答问题l至问题3．将解答写在答题纸的对应栏内。
【说明】
计算一个整数数组a的最长递增子序列长度的方法描述如下：
假设数组a的长度为n，用数组b的元素b[i]记录以a[i](0≤i<n)为结尾元素的最长
递增子序列的长度，则数组a的最长递增子序列的长度为器
；其中b[i]满足最优子结构，可递归定义为：
【c代码】
下面是算法的c语言实现。
(1)常量和变量说明
a：长度为n的整数数组，待求其最长递增子序列
b：长度为n的数组，b[i]记录以a[i](0≤i<n)为结尾元素的最长递增子序列的长度，
其中0≤i<n
len:最长递增子序列的长度
i.j:循环变量
temp,临时变量
(2)C程序
include <stdio . h>
int maxL （int *b. int n） {
int i. temp =0;
For（i = 0; i < n; i++）{
if （b[i] > temp ）
Temp= b[i];
}
Return temp;
【问题l】（8分）
根据说明和C代码,填充C代码中的空(1)～(4)。
【问题2】（4分）
根据说明和C代码，算法采用了(5)设计策略，时间复杂度为(6)（用O符号表示）。
【问题3】（3分）
已知数组a={3，10，5，15，6，8}，根据说明和C代码，给出数组b的元素值。
正确答案：
本题考查算法设计与分析以及用C程序设计语言来实现算法的能力。此类题目要求考生认真阅读题目对问题的描述，理解算法思想，并会用C程序设计语言来实现。【问题1】根据题干描述，用一个数组b来记录数组a每个子数组的最长递增子序列的长度，即b[i]记录a[0．．i]的最长递增子序列的长度。首先，只有一个元素的数组的最长递增子序列的长度为1，即给b[0]直接赋值1。因此，空(1)处填写“b[0]=1”。两重for循环中，第一重是从a数组的第二个元素开始，考虑每个子数组a[0....II]的最长递增子序列的长度，第二重是具体的计算过程。考虑子数组a[0..I]，其最长递增于序列的长度应该等于子数组a[O.i-l]中的比元素a[i]小的元素的最长递增子序列的长度加1，当然，可能存在多个元素比元素a[i]小，那么存在多个最长递增子序列的长度，此时，取最大者。因此，空处填写j<i”，即考虑子数组a[O...i-l]。空(3)处填写“a[j]<=a[i]”，要求元素值小于等于a[i]而且目前的长度应该小于当前考虑的子数组的最长子序列长度。空(4)处填写“b[i]=len+1”。简单的说，程序是根据题干给出的公式来实现的。另外，计算的过程不是采用递归的方式，而是以一种自底向上的方式进行的【问题2】从题干说明和C程序来看，这是一个最优化问题，而且问题具有最优子结构，一个序列的最长递增子序列由其子序列的最长递增子序列构成。在计算过程中采用了自底向上的方式来进行，这具有典型的动态规划特征。因此采用的是动态规划设计策略。C程序中，有两重for循环，因此时间复杂度为。【问题3】输入数组为数组a={3.10，5，15，6，8}，很容易得到，子数组a[0...0]，a[0．．1]．…，a[0....5]的最长递增子序列的长度分别为l，2，2，3,3，4，因此答案为b={I，2，2，3，4}。该题可以根据题干说明、C代码来计算。由于输入很简单，答案也可以从输入直接许算出来。试题四参考答案【问题1】(1)b[0]=I(2)j<i(3)a[j]<=a[i](4)b[i]=len+1【问题2】(5)动态规划(6)【问题3】b={1，2，2，3，3，4} -
第3题：
阅读下列说明和C代码，回答问题，将解答填入答题纸的对应栏内。
【说明】
计算一个整数数组a的最长递增子序列长度的方法描述如下：
假设数组a的长度为n，用数组b的元素b[i]记录以a[i](0≤i＜n)为结尾元素的最长递增子序列的长度为 ；其中b[i]满足最优子结构，可递归定义为：
【C代码】
下面是算法的C语言实现。
（1）常量和变量说明
a：长度为n的整数数组，待求其最长递增子序列
b：长度为n的数组，b[i]记录以a[i](0≤i
i, j：循环变量
temp：临时变量
（2）C程序
#includeint maxL(int*b, int n) {int i, temp=0;for(i=0; i
【问题1】（8分）
根据说明和C代码，填充C代码中的空（1）～（4）。
【问题2】（4分）
根据说明和C代码，算法采用了 （5） 设计策略，时间复杂度为 （6） （用O符号表示）。
【问题3】（5分）
已知数组a={3，10，5，15，6，8}，据说明和C代码，给出数组b的元素值。答案：解析：【问题1】
（1）b[0]=1
（2）j（3）a[j]<=a[i]
（4）b[i]=len+1
【问题2】（4分）
（5）动态规划法
（6）O(n2)
【问题3】（5分）
B={1，2，2，3，3，4} -
第4题：
阅读以下说明和算法，完善算法并回答问题。
【说明】
假设以二维数组G[1..m，1..n)表示一幅图像各像素的颜色，则G[i，j]表示区域中点(i，j)处的颜色，颜色值为0～k的整数。
下面的算法将指定点(i0，j0)所在的同色邻接区域的颜色置换为给定的颜色值。约定所有与点(i0，j0)同色的上、下、左、右可连通的点组成同色邻接区域。
例如，一幅8×9像素的图像如图2-1所示。设用户指定点(3，5)，其颜色值为0，此时其上方(2，5)、下方(4，5)、右方(3，6)邻接点的颜色值都为0，因此这些点属于点(3，5)所在的同色邻接区域，再从上、下、左、右四个方向进行扩展，可得出该同色邻接区域的其他点(见图2-1中的阴影部分)。将上述同色区域的颜色替换为颜色值7所得的新图像如图2-2所示。
【算法】
输入：矩阵G，点的坐标(i0，j0)，新颜色值newcolor。
输出：点(i0，j0)所在同色邻接区域的颜色置换为newcolor之后的矩阵G。
算法步骤(为规范算法，规定该算法只在第七步后结束)如下。
第一步：若点(i0，j0)的颜色值与新颜色值newcolor相同，则(1)；
第二步：点(i0，j0)的颜色值→oldcolon创建栈S，并将点坐标(i0，j0)入栈；
第三步；若(2)，则转第七步；
第四步；栈顶元素出栈→(x,y)，并(3)；
第五步；1)若点(x，y-1)在图像中且G[x，y-1]等于oldcolor，则(x,y-1)入栈S；
2)若点(x，y+1)在图像中且GIx，y+1]等于oldeolor，则(x，y+1)入栈S；
3)若点(x-1，y)在图像中且G[x-1，y)等于oldcolor，则(x-1，y)入栈S；
4)若点(x+1，y)在图像中且G[x+1，y)等于oldcolor，则(x+1，y)入栈S；
第六步：转(4)；
第七步：算法结束。
【问题】
是否可以将算法中的栈换成队列?回答；(5) 。
正确答案：(1)转第七步 (2)栈S空或等价的文字描述 (3)G[xy]←newcolor或G[xy]=newcolor或等价的文字描述 (4)第三步 (5)可以
(1)转第七步 (2)栈S空，或等价的文字描述 (3)G[x,y]←newcolor，或G[x,y]=newcolor，或等价的文字描述 (4)第三步 (5)可以 解析：本题考查栈结构在算法中的应用。
栈或(和)队列常在某些应用中用来临时存储需要处理的元素，因此，其基本应用方式为：首先令一个(或多个)元素入栈(队列)，然后在栈(队列)非空的情况下，栈顶(队头)元素出栈(队列)并进行处理，然后令与该栈顶(队头)元素相关的其他元素入栈(队列)，再从判栈(队列)空开始重复以上过程。
根据题目说明部分的描述，所有与点(i0，j0)同色的上、下、左、右可连通的点组成同色邻接区域。要置换一个同色邻接区域中所有点的颜色，可先将所有需要改变颜色的点的坐标记录下来，然后逐个地改变其颜色值；也可采取找出一个点、处理一个点的方式进行颜色置换。题中给出的算法属于后一种情况。
显然，算法中需要一个存储空间，用于临时存储需要置换颜色的点的坐标，使每个需要处理的元素都进、出该存储区域一次，算法中的栈起的就是这个作用。实际上，对区域中各点的颜色置换的顺序是无关紧要的，因此，将算法中的栈换成队列不会影响算法的输出。
在本题中，若新的颜色值与同色区域中的原颜色相同，则无需置换。因此空 (1)处应填入“转第七步”。算法第二步先记下点(i0，j0)所在区域的原颜色，并令点(i0，j0)入栈，之后就是基于栈非空的操作了，因此空(2)处应填入“栈S为空”。第三步令栈顶元素出栈并修改对应点的颜色值，空(3)处应填入“修改(x，y)处的颜色值为newcolor"。算法中必然有一步能使算法步骤循环处理，因此第六步中的空(4)处应填入“第三步”。 -
第5题：
试题一（共 15分）
阅读以下说明和算法，完善算法并回答问题，将解答写在答题纸的对应栏内。
[说明]
假设以二维数组G[1..m,1..n]表示一幅图像各像素的颜色，则G[i,j]表示区域中点(i,j)处的颜色，颜色值为0到k 的整数。下面的算法将指定点(i0,j0)所在的同色邻接区域的颜色置换为给定的颜色值。约定所有与点(i0,j0)同的上、下、左、右可连通的点组成同色邻接区域。
例如，一幅8×9 像素的图像如图1-1 所示。设用户指定点(3,5)，其颜色值为0，此时其上方(2,5)、下方 (4,5)、右方(3,6)邻接点的颜色值都为0，因此这些点属于点(3,5)所在的同色邻接区域，再从上、下、左、右四个方向进行扩展，可得出该同色邻接区域的其他点（见图1-1 中的阴影部分）。将上述同色区域的颜色替换为颜色值7所得的新图像如图1-2 所示。
[算法]
输入：矩阵 G，点的坐标(i0,j0)，新颜色值newcolor。
输出：点(i0,j0)所在同色邻接区域的颜色置换为newcolor之后的矩阵G。
算法步骤(为规范算法，规定该算法只在第七步后结束)：
第一步：若点(i0,j0)的颜色值与新颜色值newcolor相同,则(1) ；
第二步：点(i0,j0)的颜色值→oldcolor；创建栈S，并将点坐标(i0,j0)入栈；
第三步：若 (2) ，则转第七步；
第四步：栈顶元素出栈→(x,y)，并(3) ；
第五步：1) 若点(x,y-1)在图像中且G[x,y-1]等于oldcolor，则(x,y-1)入栈S；
2) 若点(x,y+1)在图像中且G[x,y+1]等于oldcolor，则(x,y+1)入栈S；
3) 若点(x-1,y)在图像中且G[x-1,y]等于oldcolor，则(x-1,y)入栈S；
4) 若点(x+1,y)在图像中且G[x+1,y]等于oldcolor，则(x+1,y)入栈S；
第六步：转 (4) ；
第七步：算法结束。
[问题]
是否可以将算法中的栈换成队列？回答： (5) 。
正确答案：