2020-2021-1期中卷

2019级，其实是答案

比较不全，仅供参考

算法分析与设计期中考参考答案

选择题

1-7 ACACABB

6.Solution: False. As we saw in lecture, for any input, the expected running time of quicksort is \(O(n \lg n)\), where the expectation is taken over the random choices made by quicksort, independent of the choice of the input.

7.Solution: False. The number of leaves of a decision tree which sorts 5 numbers is \(5!\) and the height of the tree is at least \(\lg(5!)\). Since \(5! = 120\), \(2^6 = 64\), and \(2^7 = 128\), we have \(6 < \lg(5!) < 7\). Thus at least 7 comparisons are required.

算法复杂度分析

A-D: \(\Theta(n^2),\Theta(nlgn),\Theta(nlgn),\Theta(nlgn)\)

E-H: \(\Theta(n^{lg7}),\Theta(n^2),\Theta(n^2),\Theta(n^2)\)

I-J: \(\Theta(n^2),\Theta(n)\)

简答题

1建堆过程+排序过程+排序结果

2解决哈希冲突的方法一般有：开放定址法、链地址法（拉链法）、再哈希法、建立公共溢出区等方法。

① 开放定址法

A.线性探查法

线性探查法是开放定址法中最简单的冲突处理方法，它从发生冲突的单元起，依次判断下一个单元是否为空，当达到最后一个单元时，再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止。

B.平方探查法

平方探查法即是发生冲突时，用发生冲突的单元 \(d[i]\), 加上 \(1^2\)、\(2^2\)等。即 \(d[i] + 1^2\), \(d[i] + 2^2\), \(d[i] + 3^2\)...直到找到空闲单元。

在实际操作中，平方探查法不能探查到全部剩余的单元。不过在实际应用中，能探查到一半单元也就可以了。若探查到一半单元仍找不到一个空闲单元，表明此散列表太满，应该重新建立。

C.双散列函数探查法

这种方法使用两个散列函数 \(h1\) 和 \(h2\)。其中 \(h1\) 和前面的 \(h\) 一样，以关键字为自变量，产生一个 \(0\) 至 \(m-1\) 之间的数作为散列地址；\(h2\) 也以关键字为自变量，产生一个 \(1\) 至 \(m-1\) 之间的、并和 \(m\) 互素的数(即 \(m\) 不能被该数整除)作为探查序列的地址增量(即步长)，探查序列的步长值是固定值 \(1\)；对于平方探查法，探查序列的步长值是探查次数 \(i\) 的两倍减 \(1\)；对于双散列函数探查法，其探查序列的步长值是同一关键字的另一散列函数的值。

② 链地址法（拉链法）

链接地址法的思路是将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第 \(i\) 个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。

③ 再哈希法

就是同时构造多个不同的哈希函数：

\(H_i = RH_i(key) \quad i= 1,2,3 ... k;\)

当 \(H_1 = RH_1(key)\) 发生冲突时，再用 \(H_2 = RH_2(key)\) 进行计算，直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间。

④ 建立公共溢出区

将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

程序编程题

①Merge sort

void merge(int arr[], int start, int mid, int end) {
    int result[ArrLen];
    int k = 0;
    int i = start;
    int j = mid + 1;
    while (i <= mid && j <= end) {
        if (arr[i] < arr[j]){
            result[k++] = arr[i++];
        }
        else{
            result[k++] = arr[j++];
        }
    }
    if (i == mid + 1) {
        while(j <= end)
            result[k++] = arr[j++];
    }
    if (j == end + 1) {
        while (i <= mid)
            result[k++] = arr[i++];
    }
    for (j = 0, i = start ; j < k; i++, j++) {
        arr[i] = result[j];
    }
}

void mergeSort(int arr[], int start, int end) {
    if (start >= end)
        return;
    int mid = ( start + end ) / 2;
    mergeSort(arr, start, mid);
    mergeSort(arr, mid + 1, end);
    merge(arr, start, mid, end);
}

②SELECT

int FindMedian(a, p, r) {
    for (i = p; i <= r - 5; i += 5) {
        InsertionSort(a, i, i + 4);
        num = i - p;
        Median[num / 5] = a[i + 2];
    }
    remain = r - i;
    InsertionSort(a, i, r);
    num = i - p;
    Median[num / 5] = a[i + remain / 2];

    elem = (r - p) / 5;
    if ((r - p) % 5 != 0) { elem = elem + 1; }
    else { return FindMedian(Median, 0, elem); }
}

int Index(a, p, r) {
    for (int i = p; i <= r; i++) {
        if (a[i] == FindMedian(a, p, r))
            return i;
    }
}

int Partition(a, p, r) {
    index = Index(a, p, r);
    exchange a[r] and a[index];
    i = p - 1; x = a[r];
    for (j = p; j <= r - 1; j++) {
        if (a[j] <= x) {
            i = i + 1;
            exchange a[i] and a[j];
        }
    }
    exchange a[i + 1] and a[r];
    return i + 1;
}

void InsertionSort(a, p, r) {
    int i, j, key;
    for (i = 2; i <= n; i++) {
        key = a[i]; j = i - 1;
        while (j > 0 && a[j] > key) {
            a[j + 1] = a[j];
            j = j - 1;
        }
        a[j + 1] = key;
    }
}

计算题

六．证明题