itgle.com

对于关键码序列18，30，35，10，46，38，5，40，进行堆排序（假定堆的根结点是最小关键码），在初始建堆过程中需进行的关键码交换次数为 （ ） 。

题目

对于关键码序列18，30，35，10，46，38，5，40，进行堆排序（假定堆的根结点是最小关键码），在初始建堆过程中需进行的关键码交换次数为 （ ） 。

相似考题

1.（5）设待排序关键码序列为(25,18,9,33,67,82,53,95,12,70)，要按关键码值递增的顺序进行排序，采取以第一个关键码为分界元素的快速排序法，第一趟完成后关键码33被放到了第___________个位置。

2.（ 5 ）堆排序是对直接选择排序的改进，在第一次选择出最小关键码的同时为以后的选择准备了条件。堆实质上是一棵 【 5 】 树结点的层次序列。

3.对于关键码序列18，30，35，10，46，38，5，40进行堆排序（假定堆的根结点为最小关键码），在初始建堆过程中需进行的关键码交换次数为 ( )。

4.设待排序关键码序列为（25，18，9，33，67，82，53，95，12，70），要按关键码值递增的顺序进行排序，采取以第一个关键码为分界元素的快速排序法，第一趟完成后，关键码25被放到了第（ ）个位置。A．4B．3C．7D．8

更多“对于关键码序列18，30，35，10，46，38，5，40，进行堆排序（假定堆的根结点是最小关键码），在初始建堆过程中需进行的关键码交换次数为 （ ） 。”相关问题

  • 第1题：

    【 】树的所有关键码都出现在叶结点上,上面各层结点中的关键码均是下层相应结点中最大关键码的复写。


    正确答案：B+
    B+ 解析：本题主要考查了B+树。 B+树的所有关键码都出现在叶结点上,上面各层结点中的关键码均是下层相应结点中最大关键码的复写。

  • 第2题：

    对一组记录的关键码（54，36，72，15，40，38，91）进行堆排序时，初始化堆后，最后4个记录为 【】


    正确答案：（15,36,38,54）
    堆积排序(Heapsort)是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。先建一个“大顶堆”，即先选得一个关键字为最大的记录，然后与序列中最后一个记录交换，之后继续对序列中前 n-1 记录进行“筛选”，重新将它调整为一个“大顶堆”再将堆顶记录和第 n-1 个记录交换，如此反复直至排序结束。所谓“筛选”指的是对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树为堆。

  • 第3题：

    设待排序关键码序列为(24，19，32，43，38，6，13，22)，要按关键码值递增地顺序进行排序，采取以第一个关键码为分界元素的快速排序法，第一趟完成后关键码43被放到第（ ）个位置。


    正确答案：B
    快速排序是起泡排序的改进。在快速排序中，任取一个记录，以它为基准用交换的方法将所有的记录分成两部分，关键码值比它小的在一部分，关键码值比它大的在另一部分，再分别对两个部分实施上述过程，一直重复到排序完成。本题中第一趟完成后的记录是(22，19，13，6，24，38，43，32)。可见43移向到第7个位置。

  • 第4题：

    对于n个结点的序列，利用直接插入排序的方法总的关键码的比较次数约为

    A．n

    B．n2

    C．log2n

    D．n2/4


    正确答案：D
    解析：对于n个结点的序列，利用直接插入排序的方法总的关键码的比较次数约为n2/4。

  • 第5题：

    对于关键码序列18，30，35，10，46，38，5，40，进行堆排序(假定堆的根结点是最小关键码)，在初始建堆过程中需进行的关键码交换次数为( )。

    A．2次

    B．3次

    C．4次

    D．5次


    正确答案：B
    解析：原始的堆如图1所示：因为n=8，所以n/2=4，所以从K4=10开始，第一次比较1040，不用交换：第二次比较35＞5，两者相互交换，交换后如图2所示：第三次比较30＞10，两者相互交换，交换后如图3所示；第四次比较18＞5，两者相互交换，交换后如图4所示。所以交换的次数为3次。

  • 第6题：

    设有关键码序列(Q，G，M，Z，A，N，B，P，X，H，Y，S，T，L，K，E)，采用堆排序法进行排序，经过初始建堆后关键码值A在序列中的序号是（ ）。

    A．1

    B．4

    C．8

    D．12


    正确答案：A

  • 第7题：

    ●非空二叉排序树的定义是：若根结点具有左子树，则左子树中所有结点的关键码均小于根结点的关键码；若根结点具有右子树，则右子树中所有结点的关键码均大于根结点的关键码；左、右子树也是二叉排序树。由此可知，在一个二叉排序树中,(40)。

    (40)

    A．从根结点到任何一个叶子结点的路径上，结点的关键码序列呈递增排列

    B．从根结点到任何一个叶子结点的路径上，结点的关键码序列呈递减排列

    C．同层次结点从左向右排列，结点的关键码序列呈递增排列

    D．同层次结点从左向右排列，结点的关键码序列呈递减排列


    正确答案：C

  • 第8题：

    对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是：在插入第i个关键码Ki时，其前面的i-1个关键码己排好序，因此令Ki与Ki-1、Ki-2、...，依次比较，最多到K1为止，找到插入位置并移动相关元素后将Ki插入有序子序 列的适当位置，完成本趟（即第i-1趟）排序。以下关于直接插入排序的叙述中，正确的是（ ）。

    A. 若原关键码序列已经升序排序，则排序过程中关键码间的比较次数最少
    B.若原关键码序列已经降序排序，则排序过程中关键码间的比较次数最少
    C.第1趟完成后即可确定整个序列的最小关键码
    D.第1趟完成后即可确定整个序列的最大关键码

    答案：A
    解析：

  • 第9题：

    对n个记录组成的任意序列进行简单选择排序，所需进行的关键码间的比较次数总共为（）。


    正确答案:比较次数=（n-1）+（n-2）+…+2+1=n×（n-1）/2

  • 第10题：

    设待排序关键码序列为（25，18，9，33，67，82，53，95，12，70），要按关键码值递增的顺序进行排序，采取以第一个关键码为分界元素的快速排序法，第一趟完成后关键码33被放到了第（）个位置。


    正确答案:9

  • 第11题：

    填空题
    对n个记录组成的任意序列进行简单选择排序，所需进行的关键码间的比较次数总共为（）。

    正确答案： 比较次数=（n-1）+（n-2）+…+2+1=n×（n-1）/2
    解析： 暂无解析

  • 第12题：

    填空题
    在一棵m阶的B—树中，当将一个关键码插入某结点而引起该结点分裂时，此结点原有（）个关键码；若删去某结点中的一个关键码，而导致结点合并时，该结点原有（）个关键码。

    正确答案： m-1,[m/2]-1
    解析： 暂无解析

  • 第13题：

    设有关键码序列(Q，G，M，Z，A，N，B，P，X，H，Y，S，T，L，K，E)采用堆徘序法进行排序，经过初始建堆后关键码值B在序列中的序号是（ ）。

    A. 1

    B. 3

    C. 7

    D. 9


    正确答案：B
    建堆的算法：首先将要排序的所有关键码放到一棵完全二叉树的各个结点中(这时的二叉树不具备堆的特性)，然后，从i=[n/2](n为结点的个数)的结点K．开始，逐步把以I(K(n/2)’K[n/2]-1，K[n/2]-2…为根的子树排成堆，直到以K1为根的树排成堆，就完成了建堆过程。此题中，n=16，i=[16/2]=8，即从第8个结点开始，建堆完成后如图35所示

    所以经过初始建堆后关键码值B在序列中的序号是3。

  • 第14题：

    对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是：在插入第i个关键码Ki时，其前面的i-1个关键码己排好序，因此令Ki与Ki-1、Ki-2、...，依次比较，多到K1为止，找到插入位置并移动相关元素后将Ki插入有序子序列的适当位置，完成本趟（即第i-1趟）排序。以下关于直接插入排序的叙述中，正确的是（）。

    A.若原关键码序列已经升序排序，则排序过程中关键码间的比较次数最少

    B.若原关键码序列已经降序排序，则排序过程中关键码间的比较次数最少

    C.第1趟完成后即可确定整个序列的最小关键码

    D.第1趟完成后即可确定整个序列的最大关键码


    正确答案：A

  • 第15题：

    设有关键码序列(O, G, M, Z, A, N, B, P, X, H, Y, S, T, L, K, E)，要按关键码值递增的顺序进行排序，采用堆排序法进行，经过初始建堆后关键码值A在序列中的序号是______。


    正确答案：√
    1

  • 第16题：

    下面关于二叉排序树叙述中，正确的是

    A．右结点的度大于左结点的度

    B．右子树的度大于左子树的度

    C．左子树中所有的结点的关键码值都小于该结点的关键码值

    D．右子树中所有的结点的关键码值都小于该结点的关键码值


    正确答案：C
    解析：二叉排序树的特点是：左子树中所有的结点的关键码值都小于该结点的关键码值，而右子树中所有的结点的关键码值都大于该结点的关键码值。

  • 第17题：

    对于n个结点的序列,利用shell排序的方法进行比较时,总的关键码的比较次数约为

    A．n13

    B．n2

    C．log2n

    D．n2/4


    正确答案：A
    解析：本题主要考查了shell排序方法的比较次数。对于n个结点的序列,利用shell排序的方法总的关键码的比较次数约为n13。

  • 第18题：

    设有关键码序列(Q；G，M，Z，A，N，B，P，X，H，Y，S，T，L，K，E)，采用堆排序法进行排序，经过初始建堆后关键码值B在序列中的序号是（ ）。

    A)1

    B)3

    C)7

    D)9


    正确答案：B
    建堆的算法：首先将要排序的所有关键码放到一棵完全二叉树的各个结点中(这时的二叉树不具备堆的特性)，然后，从i=[n/2](n为结点的个数)的结点Ki开始，逐步把以K[n/2]，K[n/2]-1,K[n/2]-2，..为根的子树排成堆，直到以K1为根的树排成堆，就完成了建堆过程。此题中，n=16，i=[16/2]=8，即从第8个结点开始，建堆完成后如下图：

    所以经过初始建堆后关键码值B在序列中的序号是3。

  • 第19题：

    对于n个元素的关键码序列{k1，k2，…，Kn}，当且仅当满足下列关系时称其为堆。

    以下关键码序列中，（ ）不是堆。

    A.12, 25, 22, 53, 65, 60, 30
    B.12, 25, 22, 30, 65,60, 53
    C.65, 60,25, 22, 12, 53, 30
    D.65,60, 25, 30, 53, 12,22

    答案：C
    解析：
    本题考察数据结构与算法的基础知识。对于C选项，其k1k2,但k3k5,因此不满足堆的条件。

  • 第20题：

    非空二叉排序树的定义是：若根结点具有左子树，则左子树中所有结点的关键码均小于根结点的关键码：若根结点具有右子树，则右子树中所有结点的关键码均大于根结点的关键码;左、右子树也是二叉排序树。由此可知，在一个二叉排序树中（ ）。

    A.从根结点到任何一个叶子的路径上，结点的关键码序列呈递增排序
    B.从根结点到任何一个叶子的路径上，结点的关键码序列呈递减排序
    C.同层次结点从左向右排序，结点的关键码序列呈递增排序
    D.同层次结点从左向右排序，结点的关键码序列呈递减排序

    答案：C
    解析：
    本题考查二叉排序树基本概念。 某二叉排序树如下图所示。

    显然，在二叉排序树中，同层次的就结点从左至右呈递增排列。

  • 第21题：

    在一棵m阶的B—树中，当将一个关键码插入某结点而引起该结点分裂时，此结点原有（）个关键码；若删去某结点中的一个关键码，而导致结点合并时，该结点原有（）个关键码。


    正确答案:m-1；[m/2]-1

  • 第22题：

    对于B—树中任何一个非叶结点中的某个关键码k来说，比k大的最小关键码和比k小的最大关键码一定都在叶结点中。


    正确答案:正确

  • 第23题：

    判断题
    对于B—树中任何一个非叶结点中的某个关键码k来说，比k大的最小关键码和比k小的最大关键码一定都在叶结点中。
    A

    对

    B

    错


    正确答案： 对
    解析： 暂无解析

相关内容