给定记录的关键字序列为：15，3，7，21，3，16，18，15，画出构造好的二叉排序树，并计算等概率下查找成功时平均查找长度ASL

这是一棵构造好的二叉排序树：

            15
           /  \
          3   21
           \    \
            7   30
               /  \
             16   18

ASL的计算公式为：ASL = ∑(深度×概率)

其中，深度为从根节点到目标节点的距离，概率为查找目标节点的概率。由于每个节点的查找概率相等，因此概率为1/9。

我们可以通过遍历二叉排序树来计算每个节点的深度和概率：

| 节点 | 深度 | 概率 |
| --- | --- | --- |
| 15 | 1 | 1/9 |
| 3 | 2 | 2/9 |
| 7 | 3 | 1/9 |
| 21 | 2 | 1/9 |
| 16 | 4 | 1/9 |
| 18 | 4 | 1/9 |

因此，ASL = (1×1/9) + (2×2/9) + (3×1/9) + (2×1/9) + (4×1/9) + (4×1/9) = 2.67。

答案：ASL = 2.67。

相关问题

给定结点的关键字序列为：47，7，29，11，16，92，22，8，3，哈希表的长度为11。 设散列函数为：H（K）=K %11。试画出链地址法解决冲突时所构造的哈希表，并求出其平均查找长度。

好的，我明白了。下面是您所要求的答案。

根据散列函数H（K）=K，对给定的关键字序列进行哈希，得到的哈希地址为：

47 % 11 = 3
7 % 11 = 7
29 % 11 = 7
11 % 11 = 0
16 % 11 = 5
92 % 11 = 4
22 % 11 = 0
8 % 11 = 8
3 % 11 = 3

因为哈希表的长度为11，所以我们需要构造一个长度为11的链表数组，用于存放同一个哈希地址上的所有元素。

我们可以画出以下哈希表：

0 -> 11 -> 22
1 ->
2 ->
3 -> 47 -> 3
4 -> 92
5 -> 16
6 ->
7 -> 7 -> 29
8 -> 8
9 ->
10 ->

平均查找长度指的是在查找时平均需要遍历的节点数。对于链地址法，平均查找长度为：

((n+1)/2m) + ((n+2)/2m) + ((n+3)/2m) + ... + ((n+m)/2m)

其中，n为元素的个数，m为哈希表的长度。

带入数值：

n = 9
m = 11

((9+1)/2*11) + ((9+2)/2*11) + ((9+3)/2*11) + ... + ((9+11)/2*11)
= (10/22) + (11/22) + (12/22) + (13/22) + (14/22) + (15/22) + (16/22) + (17/22) + (18/22) + (19/22) + (20/22)
= 1.136

因此，该哈希表的平均查找长度为1.136。

设散列表长度为11，散列函数H（x）=x % 11，给定的关键字序列为：1，13，12，34，38，33，27，22。试画出分别用拉链法和线性探测法解决冲突时所构造的散列表，并求出在等概率的情况下，这两种方法查找成功和失败时的平均查找长度。

首先，我们根据散列函数H(x)=x%11，计算出每个关键字的散列地址（即在散列表中的位置）：

1 -> 1
13 -> 3
12 -> 1
34 -> 1
38 -> 5
33 -> 0
27 -> 5
22 -> 0

接下来，我们分别采用拉链法和线性探测法来解决冲突。

1. 拉链法

对于每个散列表位置，我们使用一个链表来存储所有散列到该位置的关键字。因此，我们需要一个Node结构体来表示链表节点：

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(nullptr) {}
};

然后，我们可以使用一个数组bucket来表示散列表，其中每个bucket[i]表示散列地址为i的链表的头节点。具体代码如下：

Node* bucket[11] = {nullptr};

// 将关键字插入散列表
void insert(int x) {
    int h = x % 11;
    Node* p = new Node(x);
    p->next = bucket[h];
    bucket[h] = p;
}

// 查找关键字
bool search(int x) {
    int h = x % 11;
    Node* p = bucket[h];
    while (p != nullptr) {
        if (p->val == x) {
            return true;
        }
        p = p->next;
    }
    return false;
}

在这个版本的散列表中，插入操作和查找操作的时间复杂度都是O(1)，因为它们都只需要计算一次散列地址，然后在链表中进行查找即可。由于我们在等概率情况下插入了8个关键字，因此成功查找的平均查找长度ASL(success)为：

ASL(success) = (1/8)*(1 + 1 + 1 + 2 + 1 + 2 + 2 + 2) = 1.5

其中，1、1、1、2分别表示在散列地址为1、3、0、5的位置查找成功时的平均查找长度，其余的位置都没有查找成功。类似地，如果采用拉链法进行查找失败的平均查找长度ASL(failure)为：

ASL(failure) = (1/11)*(1 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2) = 1.818

其中，1表示在散列地址为2的位置查找失败时的平均查找长度，其余的位置都没有查找失败。

下面是使用拉链法构造的散列表的示意图：

0 -> 33 -> 22
1 -> 12 -> 34 -> 1
2 -> 
3 -> 13
4 -> 
5 -> 38 -> 27
6 -> 
7 -> 
8 -> 
9 -> 
10 -> 

2. 线性探测法

使用线性探测法时，如果散列到的位置已经被占用，则向后查找直到找到一个空闲位置。为了方便表示，我们可以将散列表中的每个位置都看成一个键值对，其中键表示散列地址，值表示关键字。

int bucket[11] = {-1};

// 插入关键字
void insert(int x) {
    int h = x % 11;
    int pos = h;
    while (bucket[pos] != -1) {
        pos = (pos + 1) % 11;
    }
    bucket[pos] = x;
}

// 查找关键字
bool search(int x) {
    int h = x % 11;
    int pos = h;
    while (bucket[pos] != -1) {
        if (bucket[pos] == x) {
            return true;
        }
        pos = (pos + 1) % 11;
    }
    return false;
}

由于我们在等概率情况下插入了8个关键字，因此成功查找的平均查找长度ASL(success)为：

ASL(success) = (1/8)*(1 + 1 + 1 + 2 + 1 + 3 + 2 + 3) = 1.5

其中，1、1、1、2、1、3、2、3分别表示在散列地址为1、3、0、5、6、7、2、4的位置查找成功时的平均查找长度。类似地，如果采用线性探测法进行查找失败的平均查找长度ASL(failure)为：

ASL(failure) = (1/11)*(1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11) = 6

其中，1、2、3、4、5、6、7、8、9、10、11分别表示在散列地址为0、1、2、3、4、5、6、7、8、9、10的位置查找失败时的平均查找长度。

下面是使用线性探测法构造的散列表的示意图：

0 -> 33
1 -> 1
2 -> 12
3 -> 13
4 -> 34
5 -> 38
6 -> 27
7 -> 
8 -> 
9 -> 
10 -> 22