2023王道数据结构考研习题汇总

这里是总目录
2023王道数据结构考研习题汇总

---

---

10

1)算法的基本设计思想：
可将这个问题视为把数组ab转换成数组ba（a代表数组的前p个元素，b代表数组中余下的n-p个元素），先将a逆置得到a(-1)b,再将b逆置得到a(-1)b(-1),最后将整个a(-1)b(-1)逆置得到ba。

设Reverse函数执行将数组元素逆置的操作。
2)使用C语言描述算法如下：

void Reverse(int R[], int from, int to) {
    int i, temp;
    for (i = 0; i < (to - from + 1) / 2; i++) {
        temp = R[from + i];
        R[from + i] = R[to - i];
        R[to - i] = temp;
    }
}//Reverse
void Converse(int R[], int n, int p) {
    Reverse(R, 0, p - 1);
    Reverse(R, p, n - 1);
    Reverse(R, 0, n - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3) 上述算法中三个Reverse函数的空间复杂度分别为O(p/2),O((n-p)/2)和O(n/2),故设计的算法的时间复杂度为O(n)，空间复杂度为O(1).
另解：借助辅助函数来实现。算法思想：创建大小为p的辅助数组S，将R中前p个整数依次暂存在S中，同时将R中的后n-p个整数左移，然后将S中暂存的p个数依次放回到R中的后续单元。时间复杂度为O(n),空间复杂度为O(p)。

---

11

1)算法的基本设计思想如下：
分别求两个升序序列A，B的中位数，设为a和b，求序列A，B的中位数过程如下：

1. 若a=b，则a或b即为所求中位数，算法结束。
2. 若a
3. 若a>b，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求两次舍弃的长度相等。

在保留的两个升序序列中，重复上述123过程，直到两个序列中只含有一个元素时为止，较小者即为所求的中位数。
2)本题代码如下：

int M_Search(int A[], int B[], int n) {
    int s1 = 0, d1 = n - 1, m1, s2 = 0, d2 = n - 1, m2;
    //分别表示序列A和B的首位数，末位数和中位数
    while (s1 != d1 || s2 || d2) {
        m1 = s1 + ((d1 - s1) >> 1);
        m2 = s2 + ((d2 - s2) >> 1);
        if (A[m1] == B[m2])
            return A[m1];   //满足条件1
        if (A[m1] < B[m2]) {//满足条件2
            if ((s1 + d1) % 2 == 0) {//若元素个数为奇数
                s1 = m1;    //舍弃A中间点以前的部分并保留中间点
                d2 = m2;    //舍弃B中间点以后的部分并保留中间点
            }else{       //若元素个数为偶数
                s1 = m1 + 1;//舍弃A中间点及中间点之前部分
                d2 = m2;    //舍弃B中间点以后部分并保留中间点
            }         
        }
        else {              //满足条件3
            if ((s2 + d2) % 2 == 0) {//若元素个数为奇数
                d1 = m1;    //舍弃A中间点以后的部分并保留中间点
                s2 = m2;    //舍弃B中间点以前的部分并保留中间点
            }
            else { //元素个数为偶数
                d1 = m1;    //舍弃A中间点以后部分并保留中间点
                s2 = m2 + 1;//舍弃B中间点及中间点以前的部分
            }
        }
    }return A[s1] < B[s2] ? A[s1] : B[s2];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

3）算法的时间复杂度为O(log2n),空间复杂度为O(1)。

---

12

1)算法基本设计思想：
算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数，确认Num是否是逐元素。
算法可分为以下两步：
1.选取候选的逐元素。依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1；若遇到的下一个整数仍等于Num，则计数加1，否则，计数减1；当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。
2.判断c中元素是否是真正的主元素。再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素；否则，序列中不存在主元素。
2)算法实现如下

int Majority(int A[], int n) {
    int i, c, count = 1;    //c用来保存候选主元素，count用来计数
    c = A[0];   //设置A[0]为候选主元素
    for (i = 1; i < n; i++) {
        if (A[i] == c)
            count++;
        else {//处理不是候选主元素的情况
            if (count > 0)
                count--;
            else {
                c = A[i];//更换候选主元素，重新计数
                count = 1;
            }
        }
    }//end of for
    if (count > 0) {
        for (i = count = 0; i < n; i++)//统计候选主元素的实际出现次数
            if (A[i] == c)
                count++;
    }if (count > n / 2)return c;//确定候选主元素
    else return -1;//不存在主元素
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3)实现的程序的时间复杂度为O(n)，空间复杂度为O（1）。
！！！说明
本题如果采用先排好序再统计的方法（时间复杂度可为O（nlog2n）），只要解答正确，最高可拿11分。即便是写出O（n^2）的算法，最高也能拿10分，因此对于统考算法题，花费大量时间去思考最优解法是得不偿失的。

---

13

1）算法的基本设计思想：
要求在时间上尽可能高效，因此采用时间换空间的办法。分配一个用于标记的数组B[n]，用来记录A中是否出现了1-n中的正整数，B[0]对应正整数1，B[n-1]对应正整数n，初始化B中全部为0。由于A中含有n个整数，因此可能返回的值是1~n+1。当数组A中出现了小于等于0或大于n的值时，会导致1 ~n中出现空余位置，返回结果必然在1 ~n中，因此对于A中出现了小于等于0或大于n的值可以不采取任何操作。
经过上述分析可以得出算法流程，从A[0]开始遍历A，若0 2）算法实现：

int findMissMin(int A[], int n) {
    int i, * B;
    B = (int*)malloc(sizeof(int) * n);//分配空间
    memset(B, 0, sizeof(int) * n);  //赋初值为0
    for (i = 0; i < n; i++) {
        if (A[i] > 0 && A[i] <= n) //若A[i]的值介于1~n，则标记数组B
            B[A[i] - 1] = 1;
    }
    for (i = 0; i < n; i++)//扫描数组B，找到目标值
        if (B[i] == 0)break;
    return i + 1;//返回结果
}
1
2
3
4
5
6
7
8
9
10
11
12

3）时间复杂度，A遍历一次，B遍历一次，两次循环内操作步骤为O（1）量级，因此时间复杂度为O（n）。空间复杂度：额外分配了B[n]，空间复杂度为O(n)。

---

14

分析:
由D=|a-b|+|b-c|+|c-a|>=0有如下结论：
1.当a=b=c时，距离最小。
2.其余情况，不失一般性，假设a<=b<=c,观察下面的数轴：

由D的表达式可知，事实上决定D大小的关键是a和c之间的距离，于是问题就可以简化为每次固定c找一个a，使得L3=|c-a|最小。
1)算法的基本设计思想

2）算法实现

#define INT_MAX 0x7fffffff
int abs_(int a) {
    //计算绝对值
    if (a < 0)return -a;
    else return a;
}
bool xls_min(int a, int b, int c) {
    //a是否是三个数中的最小值
    if (a <= b && a <= c)return true;
    return false;
}
int findMinoTrip(int A[], int n, int B[], int m, int C[], int p) {
    //D_min用于记录三元组的最小距离，初值赋为INT_MAX
    int i = 0, j = 0, k = 0, D_min = INT_MAX, D;
    while (i < n && j < m && k < p && D_min>0) {
        D = abs_(A[i] - B[j]) + abs_(B[j] - C[k]) + abs_(C[k] - A[i]);//计算D
        if (D < D_min) D_min = D;//更新D
        if (xls_min(A[i], B[j], C[k]))i++;//更新a
        else if (xls_min(B[j], C[k], A[i]))j++;
        else k++;
    }return D_min;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3）设n=(|S1|+|S2|+|S3|),时间复杂度为O(n),空间复杂度为O(1)。

---

By——Suki整理