首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设有二维整数数组(矩阵)A[1:m,1:n],其每行元素从左到右是递增的,每列元素从上到下是递增的。以下流程图旨在该矩阵中寻找与给定整数X相等的数。如果找不到则输出“False”;只要找到一个(可能有多个)就输出“True”以及该元素的下标i和j。
设有二维整数数组(矩阵)A[1:m,1:n],其每行元素从左到右是递增的,每列元素从上到下是递增的。以下流程图旨在该矩阵中寻找与给定整数X相等的数。如果找不到则输出“False”;只要找到一个(可能有多个)就输出“True”以及该元素的下标i和j。
admin
2018-04-19
47
问题
设有二维整数数组(矩阵)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
程序员下午应用技术考试
软考初级
相关试题推荐
评价信息系统时需要听取各有关方面的意见。在听取系统操作人员的意见时,主要讨论信息系统的______。
为了提高磁盘存取效率,人们常每隔一段时间进行磁盘碎片整理。所谓磁盘碎片是指磁盘使用一段时间后,(20)。
删除Windows中某个应用程序的快捷方式,意味着(39)。
企业信息化总体架构中,计算机硬件、网络系统、操作系统、数据库管理系统等属于(16)。
下图主板接口中,①处是(28),②处可以接的设备是(29),③处可以接的设备是(30)29.
在Excel中,设单元格A1中的值为80,B1中的值为35,若在C1单元格中输入函数“=IF(AND(A1>=60,B1>=60),“不及格”,“补考”)”,按回车键后,C1单元格中的值为()。
在Excel2010中,一个宗箱的函数计算包括()。
下列关于Word绘图功能的叙述中,不正确的是__________。
在计算机程序设计语言中,可以直接被计算机识别并执行的是______。
资源记录文件位于/var/named目录下。这个目录是在以上的(1)文件中定义的。从备选选项中选择(6)~(10)处的解答。在问题4的named.abc.net文件中,出现了5种类型的记录。其中SOA是(6),NS是(7),MX是(8),A是
随机试题
王禹偁的_______有意效法自居易的平易诗风,其近体诗、绝句则不乏_______的格调,在文的方面,王禹偁既能写古文,又是四六文的高手,王禹偁的文章多有________。
对于二尖瓣狭窄伴主动脉瓣关闭不全,下列哪项不正确()(2000年)
《药品管理法》规定,劣药是指
A.机械性肠梗阻B.单纯性肠梗阻C.麻痹性肠梗阻D.痉挛性肠梗阻E.绞窄性肠梗阻外伤性腹膜后巨大血肿易发生()
依据我国现行法律的规定及相关诉讼理论,关于当事人诉讼权利能力,下列哪一选项是正确的?()(司考.四川.2008.3.48)
房地产居间服务应有如下意识()。
项目结构图是一个重要的组织工具,其反映的是()。
一般会计软件都提供数据备份功能。()
现行《宪法》规定,中央军事委员会主席向()负责。
【2009-3】人力资本理论认为,人力资本是经济增长的关键,教育是形成人力资本的重要力量。这一理论的缺陷是()。
最新回复
(
0
)