考试纲要¶

没有 C++ 代码，只有算法分析和数据结构的理论知识，有伪代码。

算法分析，\(O\) 和 \(\varTheta\) 等渐近分析记号的使用。分治策略，主定理和对应的归纳法证明。
基本数据结构，数组、链表、栈、队列、树、图等的定义和实现。
二叉搜索树和 AVL 树的定义，插入和删除操作的复杂度分析。(不要求伸展树等高级结构)
最大堆、最小堆和堆排序算法的定义和实现。(不要求左堆、斜堆等高级结构)
排序算法的稳定性和复杂度分析，包括插入排序、归并排序、快速排序、堆排序等。
并查集 (union-find) 的定义和实现。注意并查是同步发生的。要求并查集的效率提升技巧。
图的表示方法，邻接矩阵和邻接表的优缺点。图的遍历算法，深度优先搜索和广度优先搜索。
最小生成树算法，对算法的理解，实现和证明。
最短路径算法，对算法的理解。要求单源最短路径，正边权最短路径算法。
动态规划算法，要求理解，证明和实现。Quick Reply

recitation¶

归并排序的两个函数
拷贝构造、赋值运算、移动构造
list 的列表构造，find，insert
计算表达式的中缀、后缀表达，互相转换，后缀表达式进行计算

C++

string infix2postfix(string infix){
    std::stack<char> operators;
    string postfix;

    for(char c:infix){
        if(isnum(c))postfix+=c;
        else if (c=='(')operators.push(c);
        else if (c==')'){
            while(!operators.empty() && operators.top()!='('){
                prefix = operators.pop();
            }
            operators.pop();
        }
        else if(isoperator(c)){
            while(!operators.empty() && operators.top()!='(' && precedence(operators.top())>precedence(c))postfix+=operators.pop();// 高优先级的栈内全部弹出
        }
        operators.push(c);
    }
}