设散列表长度为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