有一个有序文件，其中各记录的关键字为：{3，4，5，6，7，8，10，17，19，20，27，32，43，54，65，76，87}，当用折半查找算法查找关键字为4，20，65时，其比较次数分别为多少？请画出折半查找树，并计算平均查找长度。

当用折半查找算法查找关键字为4时，比较次数为1次；查找关键字为20时，比较次数为4次；查找关键字为65时，比较次数为5次。

折半查找树如下图所示：

                             32
                            /  \
                           /    \
                          /      \
                         7       65
                        / \      / \
                       /   \    /   \
                      4    10  54   76
                     / \   / \   |    |
                    /   \ /   \  |    |
                   3    5 19  20 |    |
                                43   87

平均查找长度为：

`ASL = (1/9) * (1 + 4 + 5) = 2.22`

相关问题

索引文件、索引顺序文件的索引表项要按关键字排序吗，为什么。各记录要顺序排列吗

索引文件和索引顺序文件的索引表项一般都需要按照关键字进行排序。这是因为索引的主要作用是为了提高数据的检索效率，而排序可以使得数据在检索时更加有序，从而方便快速地查找到需要的记录。在实际应用中，索引表项的排序方式一般会根据具体的应用需求来确定，例如可以按照升序或降序排列。

而对于各记录是否要顺序排列，这取决于具体的应用需求。在一些应用场景中，记录的顺序可能并不重要，只需要保证数据的完整性和准确性即可。但在一些其他的场景中，例如需要对记录进行顺序遍历或是进行范围查询时，记录的顺序就显得非常重要了。此时，可以在索引文件或索引顺序文件中通过调整记录的存储位置来实现记录的顺序排列。

创建三个python源文件，分别在其中编写 3 种算法的程序，具体如下： （1）打开包含英文单词的文件，读取其中所有的英文单词。 （2）将所有的英文单词依次存入一个顺序表 ST 中。 （3）由用户输入一个单词，分别利用顺序查找、折半查找和索引查找算法查找该单词。 （4）对这 3 种算法的性能进行比较。 实验提示 （1）索引查找算法需要先创建索引表，索引项中的关键字为“a”到“z”的字母，查找该单词时，先在索引表中查找以确定该单词所在的范围。 （2）在性能比较时，可从查找单词花费的时间和所需占用的存储空间等方面进行考虑。由于顺序查找表不要求表中数据有序，而折半查找要求表中所有数据有序，索引查找要求索引表中数据有序，因此在比较 3 种算法的性能时，需考虑上述因素

好的，我已经了解您的问题。以下是我的回答：

首先，我们需要创建三个 Python 源文件，分别命名为 "sequential_search.py"、"binary_search.py" 和 "index_search.py"。在每个文件中，我们将编写一个算法来查找给定的单词。下面是每个文件中的代码实现：

sequential_search.py：

def sequential_search(word, word_list):
    """
    顺序查找算法
    """
    for i in range(len(word_list)):
        if word_list[i] == word:
            return i
    return -1

binary_search.py：

def binary_search(word, word_list):
    """
    折半查找算法
    """
    low = 0
    high = len(word_list) - 1
    while low <= high:
        mid = (low + high) // 2
        if word_list[mid] == word:
            return mid
        elif word_list[mid] < word:
            low = mid + 1
        else:
            high = mid - 1
    return -1

index_search.py：

def create_index_table(word_list):
    """
    创建索引表
    """
    index_table = {}
    for i in range(len(word_list)):
        first_letter = word_list[i][0]
        if first_letter in index_table:
            index_table[first_letter].append(i)
        else:
            index_table[first_letter] = [i]
    return index_table


def index_search(word, word_list):
    """
    索引查找算法
    """
    index_table = create_index_table(word_list)
    first_letter = word[0]
    if first_letter not in index_table:
        return -1
    else:
        index_items = index_table[first_letter]
        for i in index_items:
            if word_list[i] == word:
                return i
        return -1

接下来，我们需要读取包含英文单词的文件，并将所有单词存储到顺序表 ST 中。这里我们将使用 Python 的内置函数 open() 和 readlines()：

with open('words.txt', 'r') as f:
    ST = f.readlines()

然后，我们将提示用户输入一个单词，并对该单词使用三种算法进行查找。这里我们将使用 Python 的内置函数 input()：

word = input("请输入一个单词：")

然后，我们可以分别调用三种算法来查找该单词，并记录每种算法的耗时。这里我们将使用 Python 的内置函数 time.perf_counter() 来计算执行时间：

import time

start_time = time.perf_counter()
index = index_search(word, ST)
end_time = time.perf_counter()
index_search_time = end_time - start_time

start_time = time.perf_counter()
index = binary_search(word, ST)
end_time = time.perf_counter()
binary_search_time = end_time - start_time

start_time = time.perf_counter()
index = sequential_search(word, ST)
end_time = time.perf_counter()
sequential_search_time = end_time - start_time

最后，我们可以比较三种算法的性能，包括它们的查找时间和所需占用的存储空间。顺序查找表不要求表中数据有序，而折半查找要求表中所有数据有序，索引查找要求索引表中数据有序，因此我们需要考虑这些因素。

总结一下，以下是完整的代码实现：

import time


def sequential_search(word, word_list):
    """
    顺序查找算法
    """
    for i in range(len(word_list)):
        if word_list[i] == word:
            return i
    return -1


def binary_search(word, word_list):
    """
    折半查找算法
    """
    low = 0
    high = len(word_list) - 1
    while low <= high:
        mid = (low + high) // 2
        if word_list[mid] == word:
            return mid
        elif word_list[mid] < word:
            low = mid + 1
        else:
            high = mid - 1
    return -1


def create_index_table(word_list):
    """
    创建索引表
    """
    index_table = {}
    for i in range(len(word_list)):
        first_letter = word_list[i][0]
        if first_letter in index_table:
            index_table[first_letter].append(i)
        else:
            index_table[first_letter] = [i]
    return index_table


def index_search(word, word_list):
    """
    索引查找算法
    """
    index_table = create_index_table(word_list)
    first_letter = word[0]
    if first_letter not in index_table:
        return -1
    else:
        index_items = index_table[first_letter]
        for i in index_items:
            if word_list[i] == word:
                return i
        return -1


# 读取单词列表
with open('words.txt', 'r') as f:
    ST = f.readlines()

# 提示用户输入单词
word = input("请输入一个单词：")

# 使用三种算法查找单词，并计算执行时间
start_time = time.perf_counter()
index = index_search(word, ST)
end_time = time.perf_counter()
index_search_time = end_time - start_time

start_time = time.perf_counter()
index = binary_search(word, ST)
end_time = time.perf_counter()
binary_search_time = end_time - start_time

start_time = time.perf_counter()
index = sequential_search(word, ST)
end_time = time.perf_counter()
sequential_search_time = end_time - start_time

# 输出结果
print("索引查找算法耗时：{:.6f} 秒".format(index_search_time))
print("折半查找算法耗时：{:.6f} 秒".format(binary_search_time))
print("顺序查找算法耗时：{:.6f} 秒".format(sequential_search_time))

希望这可以帮助您解决问题！