首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设有二维整数数组(矩阵)A[1:m,1:n],其每行元素从左到右是递增的,每列元素从上到下是递增的。以下流程图旨在该矩阵中寻找与给定整数X相等的数。如果找不到则输出“False”;只要找到一个(可能有多个)就输出“True”以及该元素的下标i和j。
设有二维整数数组(矩阵)A[1:m,1:n],其每行元素从左到右是递增的,每列元素从上到下是递增的。以下流程图旨在该矩阵中寻找与给定整数X相等的数。如果找不到则输出“False”;只要找到一个(可能有多个)就输出“True”以及该元素的下标i和j。
admin
2018-04-19
46
问题
设有二维整数数组(矩阵)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
程序员下午应用技术考试
软考初级
相关试题推荐
《信息技术汉字字型要求和检测方法》(GB/T11460一一2009)属于______。
下列操作中______可以随意改变窗口大小。
下列关于系统软件的叙述中,正确的是(7)。
下图主板接口中,①处是(28),②处可以接的设备是(29),③处可以接的设备是(30)30.
在Windows7系统运行时,用户为了获得联机帮助,可以直接按功能键(24)________________。
对同一事物进行多次测量所得的结果可能不一致,这是幽测量误差所致。利用______可使误差基本抵消。
桌面上有各种图标,图标在桌面上的位置()。
在Word编辑状态下,移动鼠标至某段左侧,当鼠标光标变成箭头时连击左键3下,结果会选中文档的(45)。
由若干条直线段和圆弧等构成的图形,可以用一系列指令来描述。用这种方法描述的图形称为_________。
随机试题
患者,女,31岁。右侧牙痛3天,龈肿,痛剧,伴口臭,口渴,大便3日未行,舌苔黄,脉洪。治疗除取颊车、下关穴外,还应加( )。
甲公司与乙公司签订委托合同,约定甲公司将一批浓硫酸委托乙公司保管于仓库。不料乙公司所在地刮起台风,大水将甲公司的浓硫酸冲走,浓硫酸泄漏,将丙家鱼塘中的鱼毒死,丙将死鱼打捞上来,出卖给丁。丁吃了毒死的鱼,导致中毒,其家人急忙送丁去医院,因为出租车司机A拒载,
系统安全理论中阐述导致事故原因的一种理论,它认为事故是由于______产生的。
理财规划师书写的综合理财建议书的特点不包括()。[2009年11月真题]
人们在有他人旁观的情况下,工作表现要比自己单独进行时更好,这种现象称为()。
新成立的单位应当自成立之日起()内办理住房公积金缴存登记。[2012年5月、2008年11月三级真题]
下面是某教师讲授“百家争鸣”一课时的板书,该板书的类型属于()。
北京市委,市政府决定,由市政府纠风办组织协调,组成治理“三乱”领导小组,对“三乱”采取明察暗访,协调裁决的做法,先后撤消了不符合国家规定的各种检查站36处,合并了业务相似,重复收费的收费站21个,拆除或责令停止整顿的汽车清洗站6个,使北京地区公路上基本无“
Howlongistheseminarseries?
Inanaveragewinter,highwaydepartmentsspreadsometenmilliontonsofsalttokeeproadssafe.Thecorrosiveeffectsarewel
最新回复
(
0
)