首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设有二维整数数组(矩阵)A[1:m,1:n],其每行元素从左到右是递增的,每列元素从上到下是递增的。以下流程图旨在该矩阵中寻找与给定整数X相等的数。如果找不到则输出“False”;只要找到一个(可能有多个)就输出“True”以及该元素的下标i和j。
设有二维整数数组(矩阵)A[1:m,1:n],其每行元素从左到右是递增的,每列元素从上到下是递增的。以下流程图旨在该矩阵中寻找与给定整数X相等的数。如果找不到则输出“False”;只要找到一个(可能有多个)就输出“True”以及该元素的下标i和j。
admin
2018-04-19
33
问题
设有二维整数数组(矩阵)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
程序员下午应用技术考试
软考初级
相关试题推荐
在编辑Word2007文档时,若多次使用剪贴板移动文本内容,当操作结束时,剪贴板中的内容为__________。
为将演示文稿置于另一台不带PowerPoint系统的计算机上放映,那么在放映前应该对演示文稿进行()。
用普通电话线拨号上网,必须有的一个关键设备是(15)。
计算机病毒是一段程序,一般隐藏在______中。
在计算机网络的数据通信中广泛使用的校验方式是(15)。
为使双击指定类型的文件名就能调用相应的程序来打开处理它,需要将这种文件类型与相应的程序建立文件(23)。
张、王、李三个平等的评委独立对三部电影甲、乙、丙进行了评分(三人的满分标准不同),结果如下表:按合理的平均得分计算,第一、二、三名电影应分别授予(69)。
内存用于存放计算机运行时的指令、程序、需处理的数据和运行结果。但是,存储在(2)中的内容是不能用指令修改的。
一批数据的__________代表这批数据的一般水平,掩盖了其中各部分数据的差异。
框架在网页布局中主要起什么作用?主页中定义了几个框架,分别显示哪个文档?网页中使用的数据库连接引擎是什么?连接的后台数据库文件名是什么?
随机试题
汽车空调用的_______是控制发动机和压缩机之间的动力传递。
目前适用于T+1交收方式的有()
对家庭权利结构的理解,正确的是
A.辛温解表B.辛凉解表C.清暑解表D.消食导滞E.安神镇惊
(操作员:苏会计;账套:201账套;操作日期:2014年1月31日)1月19日,用工行转账支票向东方股份有限公司购买甲材料(计划成本核算)。数量800千克,单价50元,增值税税率17%,转账支票号码008,材料尚未验收入库,请填制记账凭证。
下列各项,属于现金流量表中现金及现金等价物的有()。
某企业采用应收账款余额百分比法计提坏账准备。已知年末应收账款余额为50万元,核定的坏账计提比例为10%,且企业本年是初次计提坏账,不考虑其他因素,年末计提坏账的会计处理为()。
()是指当市场达到客户预先设定的触发价格时,即变为市价指令予以执行的一种指令。
中国画按题材可分为()。
根据所给资料,下列推断不正确的一项是()。
最新回复
(
0
)