问答题

试题一
阅读以下说明和算法,完善算法并回答问题。
【说明】
假设以二维数组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[x,y]←newcolor,或G......

(↓↓↓ 点击下方‘点击查看答案’看完整答案、解析 ↓↓↓)
热门 试题

问答题
试题三 阅读以下说明和C函数,将应填入(n)处的字句写在答题纸的对应栏内。 [说明] 若一个矩阵中的非零元素数目很少且分布没有规律,则称之为稀疏矩阵。对于m行n列的稀疏矩阵M,进行转置运算后得到n行m列的矩阵MT,如图3-1所示。 为了压缩稀疏矩阵的存储空间,用三元组(即元素所在的行号、列号和元素值)表示稀疏矩阵中的一个非零元,再用一维数组逐行存储稀疏矩阵中的所有非零元素(也称为三元组顺序表)。例如,图3-1所示的矩阵M相应的三元组顺序表如表3-1所示,其转置矩阵MT的三元组顺序表如表3-2所示。 函数TransposeMatrix(MatrixM)的功能是对用三元组顺序表表示的稀疏矩阵M进行转置运算。 对M实施转置运算时,为了将M中的每个非零元素直接存入其转置矩阵MT三元组顺序表的相应位置,需先计算M中每一列非零元素的数目(即MT中每一行非零元素的数目),并记录在向量num中;然后根据以下关系,计算出矩阵M中每列的第一个非零元素在转置矩阵MT三元组顺序表中的位置: cpot[0]=0 cpot[j]=cpot[j-1]+num[j-1] *j为列号* 类型ElemType、Triple和Matrix定义如下: typedefintElemType; typedefstruct{ *三元组类型* intr,c; *矩阵元素的行号、列号* ElemTypee; *矩阵元素的值* }Triple; typedefstruct{ *矩阵的三元组顺序表存储结构* introws,cols,elements; *矩阵的行数、列数和非零元素数目* Tripledata[MAXSIZE]; }Matrix; [C函数] intTransposeMatrix(MatrixM) { intj,q,t; int*num,*cpot; MatrixMT; *MT是M的转置矩阵* num=(int*)malloc(M.cols*sizeof(int)); cpot=(int*)malloc(M.cols*sizeof(int)); if(!num||!cpot) returnERROR; MT.rows=(1); *设置转置矩阵MT行数、列数和非零元数目* MT.cols=(2); MT.elements=M.elements; if(M.elements>0){ for(q=0;qnum[q]=0; for(t=0;tnum[M.data[t].c]++; *计算矩阵M中每列第一个非零元素在其转置矩阵三元组顺序表中的位置* (3); for(j=1;jcpot[j]=(4); *以下代码完成转置矩阵MT三元组顺序表元素的设置* for(t=0;tj=(5); *取矩阵M的一个非零元素的列号存入j* *q为该非零元素在转置矩阵MT三元组顺序表中的位置(下标)* q=cpot[j]; MT.data[q].r=M.data[t].c; MT.data[q].c=M.data[t].r; MT.data[q].e=M.data[t].e; ++cpot[j]; *计算M中第j列的下一个非零元素的目的位置* } *for* } *if* free(num);free(cpot); *此处输出矩阵元素,代码省略* returnOK; } *TransposeMatrix*