首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: (1)当n=7时,在最好情况下需进行多少次比较?请说明理由。 (2)当n=7时,给出一个最好情况的初始排序的实例。 (3)当n=7时,在最坏情况下需进行多少次比较?
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: (1)当n=7时,在最好情况下需进行多少次比较?请说明理由。 (2)当n=7时,给出一个最好情况的初始排序的实例。 (3)当n=7时,在最坏情况下需进行多少次比较?
admin
2023-02-06
75
问题
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问:
(1)当n=7时,在最好情况下需进行多少次比较?请说明理由。
(2)当n=7时,给出一个最好情况的初始排序的实例。
(3)当n=7时,在最坏情况下需进行多少次比较?请说明理由。
(4)当n=7时,给出一个最坏情况的初始排序的实例。
选项
答案
(1)在最好情况下,假设每次划分能得到两个长度相等的子文件,文件的长度n=2k-1,那么第一遍划分得到两个长度均为[n/2]的子文件,第二遍划分得到4个长度均为[n/4]的子文件,以此类推,总共进行k=log
2
(n+1)遍划分,各子文件的长度均为1,排序完毕。当n=7时,k=3,在最好情况下,第一遍需比较6次,第二遍分别对两个子文件(长度均为3,k=2)进行排序,各需2次,共10次即可。 (2)在最好情况下快速排序的原始序列实例:4,1,3,2,6,5,7。 (3)在最坏情况下,若每次用来划分的记录的关键字具有最大值(或最小值),那么只能得到左(或右)子文件,其长度比原长度少1。因此,若原文件中的记录按关键字递减次序排列,而要求排序后按递增次序排列时,快速排序的效率与冒泡排序相同,其时间复杂度为O(n
2
)。所以当n=7时,最坏情况下的比较次数为21次。 (4)在最坏情况下快速排序的初始序列实例:7,6,5,4,3,2,1,要求按递增排序。
解析
转载请注明原文地址:https://kaotiyun.com/show/IBwD777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
个体身心的某些方面在较早的年龄就已达到较高的发展水平,而有些方面则需要到较晚的年龄阶段才能达到成熟水平。这一特点要求()。
现代心理学研究表明,如果教学目标是传递言语信息,那么,在有现成的文字教材的条件下,对中学生而言,最适当的方法是()。
根据下面资料,回答下列问题。【资料】上课了,章老师走进了八年级(1)班的教室,手里没拿书,只拿了一架已经折好的纸飞机和一张纸。同学们疑惑地看着张老师。有同学问:“老师,这节课我们不上课吗?”章老师坦然地说:“不上啦,我们玩纸飞机好吗?”同学们很高兴,
赵老师在历史课的教学中,为了帮助学生更好地理解和记忆,用讲解和讨论的方法来教授有关美国的内容,用团队合作的方法来教授有关英国的内容,用观看影片的方法来教授有关法国的内容。赵老师这一做法所依据的记忆理论是()。
数学课的教学,要培养学生处理数量问题的技能和有效运用这些技能于生活、学习、工作中的能力。这说明课程内容的组织需要坚持()。
与“莱特兄弟:飞机”这组词逻辑最为相近的一项是()。
操作条件反射理论的提出者是()。
给定资料: 1.世界经济的迅猛发展带来了诸如资源短缺、环境污染、臭氧层被破坏、全球气候变暖、生态失衡等一系列世界性的环境恶化问题。同时,随之而来的环境污染对食物的危害,使人们认识到环境污染、自然生态系统失衡,最终将危及人类自身的生存和发展。许多国际环境公
某市民中心广场钟楼上东、西、南、北四面各有一个挂钟,则每日早8点至晚8点,任意相邻两个钟的时针互相垂直的次数是:
把下面的六个图形分为两类,使每一类图形都有各自的共同特征或规律,分类正确的一项是:
随机试题
工艺规程的作用是什么?
A.头痛、呕吐、视乳头水肿B.血压升高、脉搏、呼吸变慢C.头痛、呕吐、颈项强直,早期出现呼吸改变,而意识、瞳孔改变较晚D.头痛、呕吐、意识障碍,病变同侧瞳孔散大伴对侧瘫痪E.对侧肢体偏瘫Cushing综合征表现为
男性,61岁。心悸、乏力、消瘦1年余,未就医诊治。2周前开始发热,T37℃~38℃,伴咳嗽、咳痰,服用止咳祛痰药物,近3天心悸、乏力症状明显加重,体温持续39.0℃以上。查体:P110次/分,R32次/分,BP180/50mmHg。消瘦,意识模糊,烦躁不安
收回货款1500元存入银行,记账凭证误填为15000元,并已入账。正确的更正方法是()。
下列选项中哪些属于“企业名称”的规范()
设栈S和队列Q的初始状态为空,元素e1、e2、e3、e4、e5和e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的顺序是e2、e4、e3、e6、e5、e1,则栈S的容量至少应该是______。
操作系统中的文件管理系统为用户提供的功能是()。
Theabilitytocommunicateistheprimaryfactorthatdistinguisheshumanbeingsfromanimals.Anditistheabilitytocommunic
AlthoughIlikedtheappearanceofthehouse,whatreallymademedecidetobuyitwasthebeautiful______throughthewindow.
ThroughoutGeorgeBush’spresidency,thefederalgovernmenthasrefusedtosupportanyregulationofthegreenhousegasesthatc
最新回复
(
0
)