首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设有n个结点进行排序,不稳定排序是(1);快速排序的最大比较次数是(2)。
设有n个结点进行排序,不稳定排序是(1);快速排序的最大比较次数是(2)。
admin
2019-04-09
24
问题
设有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
程序员上午基础知识考试
软考初级
相关试题推荐
在Windows操作系统中,要查看已知文件类型的扩展名,需要在磁盘目录下执行命令(4)设置;用键盘上的Delete删除U盘中的文件时,该文件(5);在硬盘上要直接删除文件而不让文件进入回收站,可以用键盘(6)操作。
在Windows操作系统中,要查看已知文件类型的扩展名,需要在磁盘目录下执行命令(4)设置;用键盘上的Delete删除U盘中的文件时,该文件(5);在硬盘上要直接删除文件而不让文件进入回收站,可以用键盘(6)操作。
计算机通信网中传输的是(22)。
Unix操作系统的进程控制块中,常驻内存的是(2)。
SNMP中用于数据传送与接收的默认端9是(54),SNMPv1使用了(55)种格式的PDU(协议数据单元)。
安装简单网络管理软件以便跟踪网络的故障和基本情况,适合未来发展的需要。SNMP工作在OSI模型的下三层,只能管到(34)
设某单总线LAN,总线长度为1000m,数据率为10Mb/s,数字信号在总线上的传输速度为2C/3(C为光速),则每个信号占据的介质长度为(47)m。当采用CSMA/CD(非噩EE用802.3标准)访问方式时,如只考虑数据帧而忽略其他一切因素,则最小时间
某C语言程序中,x是一个浮点型变量,m是一个值为正整数的整型常量,表达式x%m(x被m除取余数)在(1)_____时会报错,这是一种(2)______错误。(2)_____A.词法B.语法C.语义D.运行
在Windows的命令行窗口中输入命令:C:\>nslookupsettype=SOA>202.30.192.2这个命令序列的作用是查询________。
某市场调研公司对品牌商品销售情况进行调查后,得到下图(a)所示的销量统计数据。将图(a)所示的销售量按产品类别分类汇总,得到如图(b)所示的汇总结果。在进行分类汇总前,应先对图(a)的数据记录按(2)字段进行排序;选择“数据/分类汇总”命令,在弹出的“
随机试题
我认为你们的建议和他们的一样有价值。
设A为3阶矩阵,非齐次线性方程组AX=则与(A-E)*相似的对角矩阵为().
在确定函证对象时,下列项目中,通常情况下最应当纳入函证范围的是()
牙龈退缩青少年后牙周炎
在评标工作的初步评审阶段,投标文件的形式评审的内容包括()。
【背景资料】某实施监理的工程项目,采用以直接费为计算基础的全费用单价计价,混凝土分项工程全费用单价为446元/m3,直接费为350元/m3,间接费费率为12%,利润率为10%,营业税税率为3%,城市维护建设税率为7%,教育费附加费率为3%。施工合同约定:
设计方进度控制的任务是依据()对设计工作进度的要求,控制设计工作进度。
根据《合同法》规定,租赁合同租赁期限不得超过一定期限,否则超过部分无效,该期限是()年。
设窗体名称为frmTest,为了在程序代码中将窗体的标题改为“等级考试”,其代码应该是()。
Comparisonsweredrawnbetweenthedevelopmentoftelevisioninthe20thcenturyandthediffusionofprintinginthe15thand1
最新回复
(
0
)