23级中国矿业大学数据结构期末考试回忆版-MuQYY的博客

一、分析题（30分）

1、ABCD入栈序列，找出以B开头的所有合法出栈序列
2、双链表插入节点过程，用C++答过程(prev, next)
3、给二叉树的中序和后序序列，构建二叉树并且写出前序序列
4、计算完全二叉树的n0、n1、n2 共114个节点
5、中缀转后缀
6、希尔排序(d = 5、3、1)

二、应用题（40分）

1、Dijkstra写过程，先建图写邻接矩阵
2、无向图写邻接矩阵，构建DFS树
3、哈夫曼树编码, 求编码后的平均编码长度、与等长编码相比节省了多少比特
4、哈希表构建和查找，算ASL成功和ASL失败

三、算法分析与设计

1、链表的算法设计
struct{
int key;
int id;
}Node;
链表结构为head -> 2 -> 3 -> 0 …类型的（其中2、3可以是任何数，任意个，但只有一个零）
要求输出0前面的n个数，时间复杂度O(m), 空间复杂度O(1)
①要求用自己的语言描述算法设计思路
②写C++代码实现过程
③分析为什么你的算法符合这个时空复杂度

2、胜者树
①给你一串数字，构造胜者树（伪代码）
②如果修改一个节点的值，如何更新这棵树
③我们定义两棵胜者树的相似条件为：
Ⅰ.都为空树或者只有一个根节点
Ⅱ.两棵树的左子树和右子树都分别相似
写一个函数bool SimilarTree(T t1, T t2)判断相似性

最后一题我详细说一下，最后一题实际上是一个不带懒标记的线段树，给你偶数个点，求区间内最大值，其中第二小问实际上是线段树的modify操作，感兴趣的可以去看看下面的一个小问题。

题目描述、最大数

给定一个正整数数列 $a_1,a_2,…,a_n$，每一个数都在 $0∼p−1$之间。

可以对这列数进行两种操作：

添加操作：向序列后添加一个数，序列长度变成 $n+1$。
询问操作：询问这个序列中最后 L个数中最大的数是多少。

程序运行的最开始，整数序列为空。

一共要对整数序列进行 $m$次操作。

写一个程序，读入操作的序列，并输出询问操作的答案。

输入格式：

第一行有两个正整数 $m,p$，意义如题目描述；

接下来 $m$ 行，每一行表示一个操作。

如果该行的内容是 Q L，则表示这个操作是询问序列中最后 L个数的最大数是多少；

如果是 A t，则表示向序列后面加一个数，加入的数是 $(t+a) % p$
。其中，t 是输入的参数，a是在这个添加操作之前最后一个询问操作的答案（如果之前没有询问操作，则 a=0）。

第一个操作一定是添加操作。对于询问操作，$L>0$且不超过当前序列的长度。

输出格式：

对于每一个询问操作，输出一行。该行只有一个数，即序列中最后 $L$个数的最大数。

数据范围：

$1≤m≤2×10^5$
$1≤p≤2×10^9$
$0≤t

输入样例：

输出样例：

样例解释：

最后的序列是 97,14,60,96。

示范代码：

#include 
using namespace std;
const int N = 200010;
typedef long long LL;
int n = 0;//当前节点数量 1 2 3 4...
int m, p, last = 0;
struct Node{
    int l, r;
    int v;
}tr[4 * N];
//线段树结点数量 < 4N
void pushup(int u){//用子节点更新父节点, u是父节点的idx
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

void bulid(int u,int l,int r){//u为当前节点的idx,区间为[l,r]
    tr[u] = {l , r};
    if(l == r) return;//建到叶子节点，回溯
    int mid = l + r >> 1;
    bulid(u << 1, l, mid);//左节点
    bulid(u << 1 | 1, mid + 1, r);//右节点
}

int query(int u,int l,int r){//以tr[u]为根节点,找区间[l,r]的最大值
    //1、[l,r]完全包含tr[u]
    // l-------------r
    //   Tl------Tr
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;
    int mid = tr[u].l + tr[u].r >> 1;
    int v = 0;
    //2、[l,r]与[Tl,mid]有交集
    //    l--r
    // Tl-----m------Tr
    if(l <= mid) v = query(u << 1, l, r);//找左节点
    //3、[l,r]与[mid + 1,Tr]有交集
    //            l--------r
    //  Tl-----m------Tr
    if(r > mid) v = max(v, query(u << 1 | 1, l ,r));//找右节点
    return v;
}

void modify(int u,int x,int v){//以u为根节点,找到节点x并更新
    //区间l---------x--------r
    if(tr[u].l == x && tr[u].r == x) {
        tr[u].v = v;
        return;
    }//叶子节点,递归出口
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid){//在区间左半边
            modify(u << 1, x, v);
        }
        else{//在区间右半边
            modify(u << 1 | 1, x, v);
        }
        //回溯，用子节点更新父节点
        pushup(u);
    }
}

int main(){
    scanf("%d%d",&m,&p);
    bulid(1, 1, m);//m次操作，所以建一棵[1,m]区间长度的线段树
    while(m--){
        char op;
        cin >> op;
        if(op == 'Q'){
            int L;
            cin >> L;
            last = query(1, n - L + 1, n);
            cout << last << endl;
        }
        else{
            int t;
            cin >> t;
            modify(1, n + 1, ((LL)t + last) % p);
            n++;
        }
    }
    return 0;
}