对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：当n=7时，在最好情况下需进行多少次比较?请说明理由。

admin2019-08-15 42

问题对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：
当n=7时，在最好情况下需进行多少次比较?请说明理由。

选项

答案在最好情况下，假设每次划分能得到两个长度相等的子文件，文件的长度n=2k一1，那么第一遍划分得到两个长度均为[n／2]的子文件，第二遍划分得到4个长度均为[n／4]的子文件，以此类推，总共进行k=log₂(n+1)遍划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一遍需比较6次，第二遍分别对两个子文件(长度均为3，k=2)进行排序，备需2次，共10次即可。

解析

转载请注明原文地址:https://kaotiyun.com/show/tKCi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：当n=7时，在最好情况下需进行多少次比较?请说明理由。

计算机408

学硕统考专业

什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后，得到IP地址都不一样，可能吗?为什么?

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

ICMP在TCP／IP协议集中属于()。

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

某浮点机字长16位，其浮点数格式为：阶码5位(含1位阶符)，采用补码表示，尾数11位(含1位数符)，采用补码表示，且尾数为规格化形式。已知X=0．1011000011×20.0101，Y=0．0001100000×20.1000，试求X+Y．要求写出详细的

有一个仓库，可以存放A和B两种产品，但要求：(1)每次只能存入一种产品(A或B)；(2)-N＜A产品的数量-B产品的数量＜M。其中，N和M是正整数。试用P，V操作描述产品A与产品B的入库过程。

某阅览室晚间开放，第一个进入的读者开灯，最后一个离开的读者关灯。利用P、V原语操作实现读者进程。

我们所建设的社会主义和谐社会，应该是民主法治、公平正义、诚信友爱、充满活力、安定有序、人与自然和谐相处的社会。这六个方面是相互联系、相互作用的，既包括社会关系的和谐，也包括人与自然关系的和谐。体现了

()对于新闻报道相当于溺水对于()。

Hehasatalent______painting.

关于处方后记，下列说法正确的是

不属于全身性用氟防龋措施的是()

患儿，26天。面、目、皮肤发黄，颜色较深，晦暗无华，日益加重，右胁下痞块，小便黄短，大便灰白，舌见瘀点，苔黄腻。治疗应首选（　　）。

在假设检验中，设显著性水平α＝0.05，则下列表述正确的有()。

A、Showhispassport.B、Givehisaddress.C、Payadeposit.D、Fillinaform.D事实细节题，题目询问女士在对话最后让男士做什么。在对话的最后，女士让男士justfilloutt

对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问： 当n=7时，在最好情况下需进行多少次比较?请说明理由。

计算机408

学硕统考专业

什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后，得到IP地址都不一样，可能吗?为什么?

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

ICMP在TCP／IP协议集中属于()。

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

某浮点机字长16位，其浮点数格式为：阶码5位(含1位阶符)，采用补码表示，尾数11位(含1位数符)，采用补码表示，且尾数为规格化形式。已知X=0．1011000011×20.0101，Y=0．0001100000×20.1000，试求X+Y．要求写出详细的

有一个仓库，可以存放A和B两种产品，但要求：(1)每次只能存入一种产品(A或B)；(2)-N＜A产品的数量-B产品的数量＜M。其中，N和M是正整数。试用P，V操作描述产品A与产品B的入库过程。

某阅览室晚间开放，第一个进入的读者开灯，最后一个离开的读者关灯。利用P、V原语操作实现读者进程。

我们所建设的社会主义和谐社会，应该是民主法治、公平正义、诚信友爱、充满活力、安定有序、人与自然和谐相处的社会。这六个方面是相互联系、相互作用的，既包括社会关系的和谐，也包括人与自然关系的和谐。体现了

()对于新闻报道相当于溺水对于()。

Hehasatalent______painting.

关于处方后记，下列说法正确的是

不属于全身性用氟防龋措施的是()

患儿，26天。面、目、皮肤发黄，颜色较深，晦暗无华，日益加重，右胁下痞块，小便黄短，大便灰白，舌见瘀点，苔黄腻。治疗应首选（ ）。

在假设检验中，设显著性水平α＝0.05，则下列表述正确的有()。

A、Showhispassport.B、Givehisaddress.C、Payadeposit.D、Fillinaform.D事实细节题，题目询问女士在对话最后让男士做什么。在对话的最后，女士让男士justfilloutt

对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：当n=7时，在最好情况下需进行多少次比较?请说明理由。

患儿，26天。面、目、皮肤发黄，颜色较深，晦暗无华，日益加重，右胁下痞块，小便黄短，大便灰白，舌见瘀点，苔黄腻。治疗应首选（　　）。