首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设有二维整数数组(矩阵)A[1:m,1:n],其每行元素从左到右是递增的,每列元素从上到下是递增的。以下流程图旨在该矩阵中寻找与给定整数X相等的数。如果找不到则输出“False”;只要找到一个(可能有多个)就输出“True”以及该元素的下标i和j。
设有二维整数数组(矩阵)A[1:m,1:n],其每行元素从左到右是递增的,每列元素从上到下是递增的。以下流程图旨在该矩阵中寻找与给定整数X相等的数。如果找不到则输出“False”;只要找到一个(可能有多个)就输出“True”以及该元素的下标i和j。
admin
2018-04-19
50
问题
设有二维整数数组(矩阵)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(m
2
+n
2
)
选项
答案
(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
如果比较X
A[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的增加尚未越界,则说明还需要继续对下一个矩阵元素进行比较。
如果在X
A[i,j]也不成立(N),则说明A[i,j]与给定整数X相等,即已经在矩阵A中找到了一个与给定整数X相等的数,此时应输出“True”,以及当时的行号i和列号j。
当问题的规模(如本题中的参数m和n)充分大时,算法大致需要的计算工作量就是算法的时间复杂度(忽略常数因子和常数附加项)。本算法的计算量主要是比较的次数。最多的比较次数为m+n-1(沿从矩阵右上角到左下角所走的路径),因此该算法的时间复杂度为O(m+n)。其中,大写的O表示“增长的速度相当于”。
转载请注明原文地址:https://kaotiyun.com/show/E2jZ777K
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
双击某个非可执行程序的文件名将(24)。
据某地区统计,今年中小学生中肥胖学生约占10%,而且,肥胖学生人数正在以8%的速度增长。假设近年中小学生的总量变化不大,据此我们可以推算出,明年该地区中小学生中肥胖学生的比例约为(64)。
某信息处理技术员正在做大批数据处理的大项目时,领导又交宋了另一项临时性的紧迫工作,要求优先处理。该信息处理技术员需要转而做新的工作,他对原工作的处理方式应该是(69)。
收集数据时,设计调查的问题很重要。此时,需要注意的原则不包括(8)。
在WindowsXP中,删除某个应用程序在桌面上的快捷方式,则(42)。
张、王、李三个平等的评委独立对三部电影甲、乙、丙进行了评分(三人的满分标准不同),结果如下表:按合理的平均得分计算,第一、二、三名电影应分别授予(69)。
以下定性的分类变量中,(9)属于有序变量(能排序)。
文件的扩展名可以说明文件类型。下面的“文件类型一扩展名”对应关系错误的是:
桌面上有各种图标,图标在桌面上的位置()。
阅读以下说明,回答问题1至问题4。说明某公司A楼高40层,每层高3.3米,同一楼层内任意两个房间最远传输距离不超过90米,A楼和B楼之间距离为500米,需在整个大楼进行综合布线,结构如图1-1所示。为满足公司业务发展的需要,要求为楼内客户机提供数
随机试题
常用的剖视图有:_______、_______、_______和剖面图。
夏日高热无汗,宜用哪味中药煎汤熏洗躯体( )
一个估价项目完成后,应保存的档案资料包括()。
监理单位的产品是( )。
按照上海证券交易所配股规则,拥有某种股票配股权证的投资者,可委托买入不超过可配股数的股票,具体方式为向场内申报( )。
詹森是一名运动员,平时训练有素,实力雄厚,但在体育赛场上却连连失利,让自己和他人失望,不难看出这主要是压力过大,过度紧张所致。由此人们把这种平时表现良好,但由于缺乏应有的心理素质而导致正式比赛失败的现象称为詹森效应。下列各项,没有体现詹森效应的一项是(
多项式f(x)=x3+a2x2+ax-1被x+1除余-2,则实数a等于().
以下叙述中正确的是
掩码“LLL000”对应的正确输入数据是
Inlastweek’sTribune,therewasaninterestingletterfromMr.J.StewartCook,inwhichhesuggestedthatthebestwayofavo
最新回复
(
0
)