首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设有二维整数数组(矩阵)A[1:m,1:n],其每行元素从左到右是递增的,每列元素从上到下是递增的。以下流程图旨在该矩阵中寻找与给定整数X相等的数。如果找不到则输出“False”;只要找到一个(可能有多个)就输出“True”以及该元素的下标i和j。
设有二维整数数组(矩阵)A[1:m,1:n],其每行元素从左到右是递增的,每列元素从上到下是递增的。以下流程图旨在该矩阵中寻找与给定整数X相等的数。如果找不到则输出“False”;只要找到一个(可能有多个)就输出“True”以及该元素的下标i和j。
admin
2018-04-19
29
问题
设有二维整数数组(矩阵)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
程序员下午应用技术考试
软考初级
相关试题推荐
评价信息系统时需要听取各有关方面的意见。在听取系统操作人员的意见时,主要讨论信息系统的______。
在Excel的A1单元格中输入函数“=IF(12,1,2)”,按回车键后,A1单元格中的值为()。
在Word的编辑状态下,先后新建了两个文档,但并没有对这两个文档做“保存”或“另存为”操作,则______。
对新买的计算机需要记录保存的硬件主要参数中,不包括_______。
在计算机网络的数据通信中广泛使用的校验方式是(15)。
在Word中可以用“编辑”→“定位”命令对需要寻找的位置进行快速定位,(48)不属于定位目标。
某公司下设4个分公司A、B、C、D,上月各分公司的销售额及其在总公司所占比例如下表所示。由于此表单受潮,有些数据看不清了,但还可以推算出来。根据推算, D公司上月的销售额为(68)万元。
信息处理工作前期,首先需要收集所需的数据,常常要做原始统计记录。做原始统计记录需要注意的事项中一般不包括(32)。
在Exeel2010中,___________可以对A1单元格数值的小数部分进行四舍五入运算。
随机试题
巩固马克思主义在意识形态领域的指导地位,巩固全党全国人民团结奋斗的共同思想基础,是我国出版业不可推卸的政治责任,也是我国出版物发行工作必须完成的首要任务。()
患者女性,50岁。因急性梗阻性化脓性胆管炎行急诊胆总管切开取石、T管引流术,术后3天肛门排气后拔除胃管,第4天开始出现腹胀、呕吐。查体:全腹膨胀,全腹轻压痛,无反跳痛及肌紧张,血清钠135mmol/L,血清钾2.5mmol/L,RBC为4.5×1012/L
患者李某,女性,43岁。于夜晚外出后感寒,症见恶寒发热,无汗,头痛项强,肢体酸楚疼痛,口苦而渴。应首选方剂是
A、 B、 C、 D、 A观察第一组图形,每个图形内部都有一个三角形,且第一个图形外部图形和第二个图形的外部图形的笔画数相加为第三个图形外部图形的笔画数;第二组图形中,外部都有一个椭圆,内部图形规律同第一组图
信息传输的安全应保证信息在网络传输的过程中不被泄露和不被攻击。下列哪些属于攻击方法? Ⅰ.复制信息 Ⅱ.剪裁信息 Ⅲ.窃听信息
执行下列命令后:XYZ=123.456CH=’XYZ’?INT(&CH)命令?输出的值为
数据库DB、数据库系统DBS、数据库管理系统DBMS之间的关系是
Howmuchmoneydidthewomangiveaway?
Talkingofcampaignsbyourcharitytophaseoutthekeepingofanimalsincaptivity,DartmoorzooownerBenMeesays:"Actually
Notsolongagocompaniestouredtheacademicinstitutions,competingwitheachothertorecruitgraduates.However,nowadaysgr
最新回复
(
0
)