首页
登录
从业资格
对数组A=(2,8,7,1,3,5,6,4)用快速排序算法的划分方法进行一趟划分
对数组A=(2,8,7,1,3,5,6,4)用快速排序算法的划分方法进行一趟划分
练习题库
2022-08-02
69
问题
对数组A=(2,8,7,1,3,5,6,4)用快速排序算法的划分方法进行一趟划分后得到的数组A为( )(非递减排序, 以最后一个元素为基准元素)。进行一趟划分的计算时间为( )。A.(1,2,8,7,3,5,6,4)B.(1,2,3,4,8,7,5,6)C.(2,3,1,4,7,5,6,8)D.(2,1,3,4,8,7,5,6)A.O(1)B.O(Ign)C.O(n)D.O(nlgn)
选项
答案
CC
解析
本题根据快速排序的过程,首先选定基准元素为最后一个元素(题干给出的要求),下面进行排序过程:
(1)基准元素4与另一端待排第一个元素2进行比较,满足非递减,不需要交换;
(2)基准元素4与另一端待排第一个元素8进行比较,不满足非递减,交换位置,此时序列为(2,4,7,1,3,5,6,8);
(3)基准元素4与另一端待排第一个元素6进行比较,满足非递减,不需要交换;
(4)基准元素4与另一端待排第一个元素5进行比较,满足非递减,不需要交换;
(5)基准元素4与另一端待排第一个元素3进行比较,不满足非递减,交换位置,此时序列为(2,3,7,1,4,5,6,8);
(6)基准元素4与另一端待排第一个元素7进行比较,不满足非递减,交换位置,此时序列为(2,3,4,1,7,5,6,8);
(7)基准元素4与另一端待排第一个元素1进行比较,不满足非递减,交换位置,此时序列为(2,3,1,4,7,5,6,8)。
综上,本题第一空选择C选项。
因为一趟划分的过程会与整个序列n个元素进行比较,因此一趟划分的时间复杂度为O(n),第二空选择C选项。
转载请注明原文地址:https://tihaiku.com/congyezige/2409353.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
在采用结构化开发方法进行软件开发时,设计阶段接口设计主要依据需求分析阶段的()
在实体类型及实体之间联系的表示方法上,层次模型采用()结构,网状模型采用(
在软件工程的设计阶段中,有3种常用的设计方法:结构化设计(SD)方法、Jac
在面向数据流的设计方法中,一般把数据流图中的数据划分为()两种。A.数据流和事
在面向对象方法中,多态指的是()A.客户类无需知道所调用方法的特定子类的实现
在实体类型及实体之间联系的表示方法上,层次模型采用(请作答此空)结构,网状模型
在采用结构化开发方法进行软件开发时,设计阶段接口设计主要依据需求分析阶段的(请作
项目管理工具中,将网络方法用于工作计划安排的评审和检查的是_()_。A.Gan
在软件工程的设计阶段中,有3种常用的设计方法:结构化设计(SD)方法、Jac
若对27个元素只进行三趟多路归并排序,则选取的归并路数为()。A.2 B.3
随机试题
Ⅰ.Urbanproblems1)problemstobothdevelopedanddevelopingcountri
[originaltext]W:Thisisawonderfuldinner,Scott.Ican’tbelieveyoucooked
Companiesaroundtheglobehaveworktodotoimproveworkersatisfaction,b
[originaltext]W:John,IwanttoaskifyouknowanythingabouthotelsontheC
斯蒂文·芬克提出的危机传播理论是A.战略分析理论 B.阶段分析理论 C.焦点
公路水运工程试验检测,是指根据国家有关法律、法规的规定,依据工程建设技术标准、规
男性,30岁,腹痛、腹泻、间断低热3年,结肠镜见回肠末段病变呈跳跃性,见纵行溃疡
人体内的淀粉酶是A.α淀粉酶 B.γ淀粉酶 C.A和C D.β淀粉酶 E
请在Ⅰ、Ⅱ两道试题中任选一题....作答。若两题都答,只按第Ⅰ道题的成绩计分
预付账款是指企业按照合同规定预付的款项。预付款项情况不多的企业,可以不设置“预付
最新回复
(
0
)