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

admin2019-08-01 54

问题对于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://www.kaotiyun.com/show/0NCi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

下列哪一个不是罗马王政时代的管理机构?()

在1875年宪法中关于法国立法权的叙述，不正确的是()。

唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落，而且对后来的历史产生了严重影响。据此回答问题下列有关唐朝后期藩镇割据局面形成原因的表述，不正确的是()

重庆谈判签署的文件是()。

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：二里头文化在类型上可以分为()

在操作系统中，P，V操作是一种()。

分时系统里，在条件相同的情况下，通常KLT(内核级线程)比ULT(用户级线程)得到更多的CPU时间，请简要解释之。

从下面关于虚拟设备的论述中，选择一条正确的论述()。

简述DMA的工作流程。

水制法包括漂洗、浸泡、、喷洒、等方法。

变形链球菌与龋病密切相关的血清型是

患者，女，45岁。诉头晕，心悸，全身乏力。体查：体温38℃，面色苍白，巩膜轻度黄染，脾脏肋下2cm。血常规：血红蛋白80g/L，网织红细胞12％。如患者为冷抗体型自身免疫溶血性贫血，则抗体类型主要为

关于牙本质龋，描述错误的是

题36～37：某承受轴心压力的砖柱，截面尺寸为370mm×490mm，采用MU10烧结普通砖、M7.5混合砂浆砌筑，柱的计算高度为4.5m。假定甲已知，试问，砖柱的轴心受压承载力(kN)与下列何项数值最为接近?

隧道采用环形开挖留核心土法施工时，拱部超前支护完成后，方可开挖上台阶环形导坑；留核心土长度宜为()m，宽度宜为隧道开挖宽度的()。

以下关于计量的说法，正确的有()。

在咨询开始时，心理咨询员应首先向求助者说明心理咨询的()。(2003年12月三级真题)

Theuseofnuclearpowerhasalreadyspreadallovertheworld.(1)_____,scientistsstillhavenotagreedwithwhatshouldbed

Thetiresomecongressionalinvestigationssoonlostmostoftheirlisteners.

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

计算机408

学硕统考专业

下列哪一个不是罗马王政时代的管理机构?()

在1875年宪法中关于法国立法权的叙述，不正确的是()。

唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落，而且对后来的历史产生了严重影响。据此回答问题下列有关唐朝后期藩镇割据局面形成原因的表述，不正确的是()

重庆谈判签署的文件是()。

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：二里头文化在类型上可以分为()

在操作系统中，P，V操作是一种()。

分时系统里，在条件相同的情况下，通常KLT(内核级线程)比ULT(用户级线程)得到更多的CPU时间，请简要解释之。

从下面关于虚拟设备的论述中，选择一条正确的论述()。

简述DMA的工作流程。

水制法包括漂洗、浸泡、____________、喷洒、____________等方法。

变形链球菌与龋病密切相关的血清型是

患者，女，45岁。诉头晕，心悸，全身乏力。体查：体温38℃，面色苍白，巩膜轻度黄染，脾脏肋下2cm。血常规：血红蛋白80g/L，网织红细胞12％。如患者为冷抗体型自身免疫溶血性贫血，则抗体类型主要为

关于牙本质龋，描述错误的是

题36～37：某承受轴心压力的砖柱，截面尺寸为370mm×490mm，采用MU10烧结普通砖、M7.5混合砂浆砌筑，柱的计算高度为4.5m。假定甲已知，试问，砖柱的轴心受压承载力(kN)与下列何项数值最为接近?

隧道采用环形开挖留核心土法施工时，拱部超前支护完成后，方可开挖上台阶环形导坑；留核心土长度宜为()m，宽度宜为隧道开挖宽度的()。

以下关于计量的说法，正确的有()。

在咨询开始时，心理咨询员应首先向求助者说明心理咨询的()。(2003年12月三级真题)

Theuseofnuclearpowerhasalreadyspreadallovertheworld.(1)_____,scientistsstillhavenotagreedwithwhatshouldbed

Thetiresomecongressionalinvestigationssoonlostmostoftheirlisteners.

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

水制法包括漂洗、浸泡、、喷洒、等方法。