首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设有n个结点进行排序,不稳定排序是(1);快速排序的最大比较次数是(2)。
设有n个结点进行排序,不稳定排序是(1);快速排序的最大比较次数是(2)。
admin
2019-04-09
45
问题
设有n个结点进行排序,不稳定排序是(1);快速排序的最大比较次数是(2)。
选项
A、n1og
2
n
B、n
2
C、n
2
/2
D、n
答案
B
解析
在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若具有相同关键字
的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。题目选项中,只有shell排序是不稳定的。第1空的正确答案为选项C。
快速排序利用分治法的基本思想:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。它的最坏情况是,每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录,划分的结果是基准左边的子区间为空(或右边的子区间为空),而划分所得的另一个非空的子区间中记录数目,仅仅比划分前的无序区中记录个数减少一个。因此,快速排序必须做n-1次划分,第i次划分开始时区间长度为n-i+1,所需的比较次数为n-i(1≤i≤n-1),故总的比较次数达到最大值:
Cmax=n(n-1)/2=n
2
第2空的正确答案为选项B。
转载请注明原文地址:https://kaotiyun.com/show/vCVZ777K
本试题收录于:
程序员上午基础知识考试题库软考初级分类
0
程序员上午基础知识考试
软考初级
相关试题推荐
在OSI网络管理标准中,将网络管理分为系统管理、层管理和层操作。在(41)中提出了故障管理、配置管理、计费管理、性能管理和安全管理。其中(42)保证网络不被非法使用。
(66)是为硬件配置较低的移动设备访问Web网络采用的协议,它与标准的(67)环境条件有很大的不同。
最适合从一个源向多个目的地传送多媒体数据流的方式是(40),该方式采用的协议是(41)。
TCP/IP协议集由Internet工作委员会发布并已成为(26)标准。与(27)的情况不同,从来不存在正式的TCP/IP层次结构模型,但根据已开发的协议标准,可以根据通信任务将其分成4个比较独立的层次,即网络接9层、网络互联层、(28)、应用层。
Access提供多种视图模式,其中在(17)模式下可以删除数据表中的记录。
已知八位机器码10111010(最高位为符号位),当它是原码时表示的十进制数是(7):当它是补码时表示的十进制数是(8);当它是反码时表示的十进制数是(9)。
IPv6是下一代IP协议,其基本报头中的(70)字段指明了一个特定的信源向某个特定信宿发送的分组序列,各个中间路由器要对该分组序列进行特殊处理以满足应用程序的特殊传输需求。
在Windows的命令行窗口中输入命令:C:\>nslookupsettype=SOA>202.30.192.2这个命令序列的作用是查询________。
IEEE 802.11定义了无线局域网的两种工作模式,其中的(44)模式是一种点对点连接的网络,不需要无线接入点和有线网络的支持,用无线网卡连接的设备之间可以直接通信。IEEE 802.11的物理层规定了三种传输技术,即红外技术、直接序列扩频(DSSS)和
阅读下列函数说明和C代码,将应填入(n)处的字句写在答题纸的对应栏内。函数说明函数sort(iraa[],intn)的功能是对数组a中的a[0]~a[n-1]这n个元素进行排序。排序过程如下:第一趟对所有的偶数下标p,比较a[p]和a[p+1]
随机试题
下列公路工程进度计划的主要形式中,论述正确的是()。
隋代工匠李春设计的赵州桥,是世界上最早的敞肩石拱桥,比欧洲类似的桥早了1000多年。()
未与中央苏区连成一片的苏区地方政府的层级包括()
A.肺癌B.肺炎C.肺结核D.肺脓肿E.肺栓塞患者,男,60岁。咳嗽、痰中带血1个月,声音嘶哑1周,吸烟40年,每日20支。胸片示右上叶肺不张,最可能的诊断是
厌氧菌只能在无氧环境中生长的主要原因是
郁李仁具有的功效是
患者面容灰白、表情淡漠、冷汗淋漓,常见于()
在对可燃纤维织物加工车间配置灭火器时,除水基型灭火器外,下列灭火器中,应选择的是()。
对于保管期满的会计档案可以直接销毁。()
课外、校外教育是指_________和_________以外的有计划、有目的的教育活动。
最新回复
(
0
)