2. 计算机
  3. 设有二维整数数组(矩阵)A[1：m，1：n]，其每行元素从左到右是递增的，每列元素从上到下是递增的。以下流程图旨在该矩阵中寻找与给定整数X相等的数。如果找不到则输出“False”；只要找到一个(可能有多个)就输出“True”以及该元素的下标i和j。

设有二维整数数组(矩阵)A[1：m，1：n]，其每行元素从左到右是递增的，每列元素从上到下是递增的。以下流程图旨在该矩阵中寻找与给定整数X相等的数。如果找不到则输出“False”；只要找到一个(可能有多个)就输出“True”以及该元素的下标i和j。

admin2018-04-19  53
问题   设有二维整数数组(矩阵)A[1：m，1：n]，其每行元素从左到右是递增的，每列元素从上到下是递增的。以下流程图旨在该矩阵中寻找与给定整数X相等的数。如果找不到则输出“False”；只要找到一个(可能有多个)就输出“True”以及该元素的下标i和j。
    例如，在如下矩阵中查找整数8，则输出为：True，4，l
    2    4    6     9
    4    5    9     l0
    6    7    10    12
    8    9    11    13
    流程图中采用的算法如下：从矩阵的右上角元素开始，按照一定的路线逐个取元素与给定整数X进行比较(必要时向左走一步或向下走一步取下一个元素)，直到找到相等的数或超出矩阵范围(找不到)。
【流程图】
【问题】
    该算法的时间复杂度是(5)_________。
    供选择答案：A．0(1)    B．O(m+n)    C．O(m*n)    D．O(m2+n2)
选项
答案(1)n (2) j-1→i或其等价形式 (3)i+1→i或其等价形式 (4)j (5)B或O(m+n)
解析 本题考查程序员在设计算法、理解并绘制程序流程图方面的能力。
    由于在矩阵A中查找给定整数X是从矩阵的右上角(第1行第n列元素)开始的，因此，初始的下标应是i=l，j=n，从而空(1)处应填写“n”。
    接着比较X    如果比较XA[i，j]两种情况。如果判断X>A[ij]成立(Y)，则应在矩阵A中向下走一步取下一个元素，因此，空(3)处应更新i，即填入“i+1→i”。接着需要判断行号i的增加是否越界(注意行号的最大值是m)，即比较i=m+l是否成立。如果i=m+1成立(Y)，则说明查找已越界，即没有找到。输出“False”；如果i=m+1不成立(N)，即i的增加尚未越界，则说明还需要继续对下一个矩阵元素进行比较。
    如果在XA[i,j]也不成立(N)，则说明A[i,j]与给定整数X相等，即已经在矩阵A中找到了一个与给定整数X相等的数，此时应输出“True”，以及当时的行号i和列号j。
    当问题的规模(如本题中的参数m和n)充分大时，算法大致需要的计算工作量就是算法的时间复杂度(忽略常数因子和常数附加项)。本算法的计算量主要是比较的次数。最多的比较次数为m+n-1(沿从矩阵右上角到左下角所走的路径)，因此该算法的时间复杂度为O(m+n)。其中，大写的O表示“增长的速度相当于”。
转载请注明原文地址:https://www.kaotiyun.com/show/E2jZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

相关试题推荐
随机试题
最新回复(0)