分块查找索引表如图：，则关键字20可能存在于起始地址是（ ）的块。 A 10 B 0 C 5 D 15

根据分块查找的原理，我们需要先找到关键字 20 所在的块。根据题目给出的索引表，可以发现每个块的大小为 5，因此第一块包含的元素是 0 到 4，第二块包含的元素是 5 到 9，以此类推。

由于关键字 20 大于第二块的最大值 9，所以它可能存在于第三块或第四块。而第三块的起始地址是 10，第四块的起始地址是 15，因此关键字 20 可能存在于起始地址是 15 的块，答案是 D。

相关问题

c语言编程实现如下功能： ①建立索引查找表； ②利用索引查找确定给定记录在索引查找表中的块号和在块中的位置。 索引查找表有索引表和块表两部分所构成，其中索引表存储的是各块记录中的最大关键字值和各块的起始存储地址，用顺序存储结构，各块的起始存储地址的初始值置为空指针；而块表中存储的是查找表中的所有记录并且按块有序，用链式存储或顺序存储结构，在此用链式存储结构。

以下是实现功能的C语言代码：

#include <stdio.h>
#include <stdlib.h>

// 定义索引表结构体
typedef struct {
    int maxKey;  // 块内最大关键字
    int start;  // 块的起始地址
} indexItem;

// 定义块表结构体
typedef struct {
    int key;  // 关键字
    int next;  // 下一个元素的位置
} blockItem;

// 建立索引查找表
void createIndexTable(indexItem indexTable[], blockItem blockTable[], int n, int blockSize) {
    int index = 0;  // 当前索引表位置
    int block = 0;  // 当前块表位置
    int maxKey = 0;  // 当前块内最大关键字
    indexTable[index].start = 0;  // 第一个块的起始地址为0

    for(int i = 0; i < n; i++) {
        printf("请输入第%d个记录的关键字：", i+1);
        scanf("%d", &blockTable[block].key);
        if(blockTable[block].key > maxKey) {
            maxKey = blockTable[block].key;
        }
        block++;
        if(block % blockSize == 0) {  // 块已满，需要新建块
            indexTable[index].maxKey = maxKey;  // 将当前块内最大关键字存入索引表
            maxKey = 0;  // 重置当前块内最大关键字
            indexTable[++index].start = block;  // 新建块的起始地址为当前块的下一个位置
        }
    }
    if(block % blockSize != 0) {  // 最后一个块未满，需要将其最大关键字存入索引表
        indexTable[index].maxKey = maxKey;
    }
}

// 索引查找
void indexSearch(indexItem indexTable[], blockItem blockTable[], int n, int blockSize, int x) {
    int index = 0;
    while(index < n && x > indexTable[index].maxKey) {  // 在索引表中查找块号
        index++;
    }
    if(index == n) {  // 未找到块号
        printf("未找到该记录！\n");
        return;
    }
    int block = indexTable[index].start;  // 块起始位置
    while(block < n && block - indexTable[index].start < blockSize && blockTable[block].key != x) {  // 在当前块中查找记录
        block = blockTable[block].next;
    }
    if(block >= n || block - indexTable[index].start >= blockSize) {  // 未找到记录
        printf("未找到该记录！\n");
        return;
    }
    printf("该记录位于第%d块第%d个位置。\n", index+1, block-indexTable[index].start+1);
}

int main() {
    int n, blockSize, x;
    printf("请输入查找表中记录的个数：");
    scanf("%d", &n);
    printf("请输入每个块的大小：");
    scanf("%d", &blockSize);

    blockItem *blockTable = (blockItem*)malloc(n * sizeof(blockItem));  // 动态分配块表空间
    indexItem *indexTable = (indexItem*)malloc((n/blockSize + 1) * sizeof(indexItem));  // 动态分配索引表空间

    createIndexTable(indexTable, blockTable, n, blockSize);  // 建立索引查找表

    while(1) {
        printf("请输入要查找的记录的关键字（输入-1退出）：");
        scanf("%d", &x);
        if(x == -1) {
            break;
        }
        indexSearch(indexTable, blockTable, n, blockSize, x);  // 索引查找
    }

    free(blockTable);  // 释放块表空间
    free(indexTable);  // 释放索引表空间
    return 0;
}

设计算法对一个已知分块大小的分块有序表建立索引表，设计分块搜索算法。在一个已经建立索引表的分块有序表上搜索指定关键字值的记录

一、建立索引表

对于一个已知分块大小的分块有序表，我们可以按照一定的规则建立索引表。一种比较常见的方法是：每个索引项记录一个关键字和该关键字所在块的起始位置。

具体建立索引表的过程如下：

1. 确定每个块的起始位置和结束位置；
2. 对于每个块，选择一个代表该块的关键字，通常是该块中间位置的关键字；
3. 将每个代表关键字和起始位置记录在索引表中。

二、分块搜索算法

对于一个已经建立索引表的分块有序表，我们可以采用分块搜索算法来查找指定关键字值的记录。具体算法如下：

1. 在索引表中找到第一个大于等于指定关键字值的索引项，记为 $i$。如果没有找到，说明指定关键字值不存在，直接返回；
2. 在索引项 $i$ 所指向的块中进行二分查找，找到指定关键字值的记录或者没有找到。如果找到了，返回记录的位置；如果没有找到，继续向下查找；
3. 重复 1 和 2 步骤，直到找到指定关键字值的记录或者查找结束。

需要注意的是，我们可以将分块大小设置得比较大，这样可以减少索引表的长度，但是会增加每个块内部的查找时间；也可以将分块大小设置得比较小，这样可以减少块内部的查找时间，但是会增加索引表的长度。因此，在实际应用中需要根据具体情况进行权衡和选择。