首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设有n个结点进行排序,不稳定排序是(1);快速排序的最大比较次数是(2)。
设有n个结点进行排序,不稳定排序是(1);快速排序的最大比较次数是(2)。
admin
2019-04-09
47
问题
设有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)保证网络不被非法使用。
中继器对应ISO~OSI开放系统参考模型的物理层,它不转换或过滤数据包,因而要求连接的两个网络(40)。
作业输入到磁盘等外存储器,由操作系统把作业放在特定的存储区域,等待运行称为(30)。
数据库中预防死锁通常有两种方法:一种叫(16),它要求每个事物必须一次将所有要使用的数据全部加锁,否则就不能继续执行。另一种叫(17),它是预先对数据对象规定一个封锁顺序,所有事物都按这个顺序实行封锁。数据库系统中诊断死锁的方法与操作系统类似,一般使用(1
在数据库设计时,为了尽可能地使数据库模式保持最优的特性,应尽可能设计达到(15)模式。
为了推动多媒体会议系统的发展,ITU组织制订了一系列标准,其中(68)标准适用于无线网 WLAN会议通信。
频分复用的特点是(42),时分复用的特点是(43),波分复用技术中使用的通信介质是(44)。
IEEE 802.11定义了无线局域网的两种工作模式,其中的(44)模式是一种点对点连接的网络,不需要无线接入点和有线网络的支持,用无线网卡连接的设备之间可以直接通信。IEEE 802.11的物理层规定了三种传输技术,即红外技术、直接序列扩频(DSSS)和
阅读以下说明和C语言函数,将应填入(n)处的字句写在答题纸的对应栏内。【说明】一棵非空二叉树中“最左下”结点定义为:若树根的左子树为空,则树根为“最左下”结点;否则,从树根的左子树根出发,沿结点的左子树分支向下查找,直到某个结点不存在左子树时
随机试题
《米龙老爹》故事发生的背景是()
既善活血,又善行气者是
McMaster家庭评估模型理解不正确的是
糖尿病性酮症酸中毒多见于
石棉制安全帽
拟发行上市公司不得为控股股东及下属单位、其他关联企业提供担保,但可将以拟发行上市公司名义的借款转借给股东单位使用。( )
税务师在进行房产税征免界限的划分时,应当注意的征免税划分包括()。
以下不属于优抚医院社会工作的是()
()被称为“宇航之父”,他在1883年发表了使用火箭发射太空船的伟大构想。
2010年7月通过的《关于领导干部报告个人有关事项的规定》是为加强对领导干部的管理和监督,促进领导干部廉洁从政,根据《中国共产党章程》规定的。据此,下述人员中,应该报告个人有关事项的有()。
最新回复
(
0
)