itgle.com

在查找算法中，可用平均查找长度(记为ASL)来衡量一个查找算法的优劣，其定义为：此处Pi为表中第i个记录被查找的概率，Ci为查找第i个记录时同关键字比较的次数，n为表中记录数。以下叙述中均假定每一个记录被查找的概率相等，即Pi=//n(i=1，2，…，n)。当表中的记录连续存储在一个一维数组中时，可采用顺序查找与折半查找方法(折半查找要求表是按关键字有序排列的)。顺序查找时的ASL为(19)，折半查找时的ASL为(20)。记录的关键字有序时，用二叉排序树查找记录，在最坏的情况下，ASL为(21)。当二叉排

题目

在查找算法中，可用平均查找长度(记为ASL)来衡量一个查找算法的优劣，其定义为：

此处Pi为表中第i个记录被查找的概率，Ci为查找第i个记录时同关键字比较的次数，n为表中记录数。

以下叙述中均假定每一个记录被查找的概率相等，即Pi=//n(i=1，2，…，n)。当表中的记录连续存储在一个一维数组中时，可采用顺序查找与折半查找方法(折半查找要求表是按关键字有序排列的)。顺序查找时的ASL为(19)，折半查找时的ASL为(20)。记录的关键字有序时，用二叉排序树查找记录，在最坏的情况下，ASL为(21)。当二叉排序树是一棵平衡树时，ASL为(22)。在平衡树上删除一个结点后可以通过旋转使其平衡，最坏的情形下需(23)次旋转。

A．O(1)

B．O(log2n)

C．O(log2n2)

D．O(nlog2n)

E．O(n)

相似考题

1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为()。A.(n-1)/2 B.n/2 C.(n+1)/2 D.n

2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（)A．(n-1)/2B．n/2C．(n+1)/2D．n

3.对长度为4的顺序表进行查找，若查找第一个记录的概率为1/24, 查找第二个记录的概率为1/6, 查找第三个记录的概率为2/3, 查找第四个记录的概率为1/8,则查找任意一个记录的平均查找长度为（）。A．23/8B．20/8C．17/8D．13/8

4.在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为____。A．nB．n/2C．(n+1)/2D．(n-1)/2

更多“ 在查找算法中，可用平均查找长度(记为ASL)来衡量一个查找算法的优劣，其定义为：此处Pi为表中第i个记录被查找的概率，Ci为查找第i个记录时同关键字比较的次数，n为表中记录数。以下叙述中均假定每一个记录被查找的概”相关问题

  • 第1题：

    6、对长度为4的顺序表进行查找，若查找第一个记录的概率为1/24，查找第二个记录的概率为1/6，查找第三个记录的概率为2/3，查找第四个记录的概率为1/8，则查找任意一个记录的平均查找长度为 。

    A．23/8

    B．20/8

    C．17/8

    D．14/8


    A

  • 第2题：

    若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（)。

    A．(n-1)/2

    B．n/2

    C．(n+1)/2

    D．n


    (n+1)/2

  • 第3题：

    5、对长度为4的顺序表进行查找，若查找第一个记录的概率为1/24, 查找第二个记录的概率为1/6, 查找第三个记录的概率为2/3, 查找第四个记录的概率为1/8,则查找任意一个记录的平均查找长度为（）。

    A．23/8

    B．20/8

    C．17/8

    D．13/8


    A

  • 第4题：

    【单选题】若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（)。

    A．(n-1)/2

    B．n/2

    C．(n+1)/2

    D．n


    O（log 2 n）

  • 第5题：

    【单选题】1.若查找每个记录的概率相等,则在具有n个的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL为（)。

    A．(n-1)/2

    B．n/2

    C．(n+1)/2

    D．n


    n+12

相关内容