猪脚说第十四期

数据结构期末复习

复习知识点自查

考试时查看不了上机作业，因此大家一定要记得将前七次作业的网页保存为PDF格式存在本地（Ctrl+P）

栈与队列（第四次作业）

• 数据从哪儿存入，从哪儿取出，注意选填一定要看清楚栈顶、队头、队尾在哪儿（选择题13，填空题6）；
• 中缀表达式与后缀表达式的转换（选择题6，填空题5），如果不确定可以本地运行代码得结果；
• 栈的合法输出与容量（选择题3、4、5、12，填空题2、4）；
• 栈与队列的概念、性质、应用等（选择题1、2、8、9、11）。

树（第五次作业）

对于选填中的计算题，如果不确定怎么算，或者想验证结果是否正确，只需要列举一棵具体的树。

• 各名词术语（结点的度、树的度、叶节点、树的深度等）（选择题1、2、5，填空题2、3）；
• 二叉树的性质（选择题3、4、6，填空题1、5、7、9）；
• 每年都考！！！通过给出的两个遍历序列，求二叉树的另一个遍历序列（填空题6）；
• 每年都考！！！哈夫曼编码以及带权路径长度计算（选择题9、10，填空题10）。

查找与排序（第六次作业）

• 各种算法的查找长度、比较次数、每一趟的结果等题目，实际是考察不同算法的实现原理（选择题1、2、3、4、7、8、9、10、11、14、15，填空题1、2、5），请一定对照老师的ppt复习！！！
• 每年都考！！！散列表及其冲突处理（选择题6，填空题4）。

图（第七次作业）

• 图的顶点、边、邻接表、邻接矩阵的关系（选择题1、2、3、4，填空题1、2、3、7）；
• 每年都考！！！Kruskal和Prim算法求最小生成树（填空题5、6）；
• 每年都考！！！用迪杰斯特拉算法求最短路径（填空题9）。

考试可能用到的函数模版

中缀转后缀

该模版可以帮助你验证“中缀转后缀”的选填题目结果

/*
 将一个不含空格的中缀表达式s数组转化成后缀表达式；
 数字存储在num中，运算符存储在op中，且按总体下标顺序，
 插空存储，例如 (1+2)*3= 的存储方式为：
 num[0]=1, num[1]=2, op[2]='+', num[3]=3, op[4]='*'
*/
int num[512];
char op[512];
void Change(char s[]){
    int i, j=0, stacktop=-1;
    char stack[201] = {0};
    for(i = 0; s[i] != '\0';){
        while(isdigit(s[i])){
            num[j] = num[j] * 10 + s[i++] - '0';
            if(!isdigit(s[i]))
                j++;
        }
        if(s[i] == '\0')
            break;
        if(s[i] == '(')
            stack[++stacktop] = s[i];
        else if(s[i] == '+' || s[i] == '-'){
            while(stacktop > -1){
                if(stack[stacktop] == '(')
                    break;
                else
                    op[j++] = stack[stacktop--];
            }
            stack[++stacktop] = s[i];
        }
        else if(s[i] == '*' || s[i] == '/'){
            while(stacktop > -1){
                if(stack[stacktop]=='('||stack[stacktop]=='+'||stack[stacktop]=='-')
                    break;
                else
                    op[j++] = stack[stacktop--];
            }
            stack[++stacktop] = s[i];
        }
        else if(s[i] == ')'){
            while(stack[stacktop] != '(')
                op[j++] = stack[stacktop--];
            stacktop--;
        }
        i++;
    }
    while(stacktop>-1)
        op[j++] = stack[stacktop--];
}

后缀转中缀

该转化的难点在于如何添加括号。基本思路为先把后缀表达式转化为表达式树，再进行中序遍历。

typedef struct Node{
    int num;
    char op;
    struct Node *left, *right, *leftpa, *rightpa;
}Tree; // 子节点与祖先节点都需要存储，若 a 为 b 的左节点，则 b 为 a 的右祖先
Tree *numjudge;
char temp[20]={0};
void middle_order(Tree *t){
    memset(temp,0,sizeof(temp));
    if(t!=NULL){
        middle_order(t->left);
        if(t->op!='\0'){
            if(t->op=='*'||t->op=='/'){
                if(t->left->op!='\0'){
                    if(t->left->op=='+'||t->left->op=='-')
                        printf(")");
                }
            }
            printf("%c", t->op);
            if(t->op=='*'||t->op=='/'){
                if(t->right->op!='\0'){
                    printf("(");
                }
            }
        }
        else{
            if(t->rightpa!=NULL){
                numjudge=t->rightpa;
                while(numjudge->rightpa!=NULL){
                    if(numjudge->rightpa->op=='*'||numjudge->rightpa->op=='/'){
                        if(numjudge->op=='+'||numjudge->op=='-')
                            printf("(");
                    }
                    numjudge=numjudge->rightpa;
                }
            }
            printf("%d", t->num);
            if(t->leftpa!=NULL){
                numjudge=t->leftpa;
                while(numjudge->leftpa!=NULL){
                    if(numjudge->leftpa->op=='*'||numjudge->leftpa->op=='/')
                            printf(")");
                    numjudge=numjudge->leftpa;
                }
            }
        }
        middle_order(t->right);
    }
} // 根据存储好的表达式树，输出中缀表达式

前、中、后序遍历一般写法

typedef struct Node{
    int num;
    struct Node *left, *right;
}Basic_tree;
void trade(Tree *a){
    if(a == NULL)
        return ;
  	Visit(a);// 前序遍历放在此位置
    trade(a->left);
    Visit(a);// 中序遍历放在此位置
    trade(a->right);
  	Visit(a);// 后序遍历放在此位置
}
// 例如，要求前序遍历输出每个节点的值，则 Visit() 函数可写为：
// printf("%d\n", a->num);

遵循一定规则的树节点插入

typedef struct Node{
    int num;
    int height;
    struct Node *left, *right;
}Basic_tree;
Basic_tree *insert(Basic_tree *root, int x, int high){
    high++;
    if(root == NULL){
        root = (Basic_tree*)malloc(sizeof(Basic_tree)); // 一定要记得malloc
        root->num = x;
        root->left = NULL;
        root->right = NULL; // 因为递归涉及非空判断，所以这个地方一定要初始化！
        root->height = high;
    }
    else if(x < root->num)
        root->left = insert(root->left, x, high);
    else
        root->right = insert(root->right, x, high); // 递归调用即可
    return root; // 一定要记得有返回值
}

该函数调用时，写法应为 root = insert(root,int x,int high);，即：每次更新root值。

更简便的树的实现方式

如果你实在弄不明白指针和malloc，你可以考虑纯数组实现树。

struct node {
    int num;
    int left, right;
} tree[100]; // 假设树不超过 100 个节点
// 每读入一个新节点，就存入数组中
// left 和 right 即为左孩子和右孩子在数组中的下标
// 如果用指针实现，无效值应设置为 NULL；类似地，这里可以选择 -1 为无效值

void traverse(int i) {
    // 中序遍历示例
    if (i != -1) {
        traverse(tree[i].left);
        printf("num is %d\n", tree[i].num);
        traverse(tree[i].right);
    }
}

其他科目复习材料

• 数分材料
• 离散材料
• 基物材料
• 史纲材料

一些复习建议

数分

• 看了往年题你会发现这其实是相对好做的一次考试，基本把所有类型的积分考了一遍，然后就没有然后了
• 曲线积分？曲面积分？第一类？第二类？换元？不换元？直角坐标？球坐标？柱坐标？对称？不对称？请务必搞清楚各个类型的计算公式
• 基本考察计算，所以请注重草稿纸画图和演算的规范和正确。当然不排除在列式计算的基础上，对题目小小地拓展，当然这种情况一般会比较简单
• 建议比较流畅地写完三到四套卷子，期间不要参考材料，注意答题和计算的规范

离散

• 线下闭卷考试大量考察定义、概念和公式定理的默写，请背熟并理解！内容参考尹宝林编著的《离散数学（第三版）》
• 对偶定理？完全集？文字？相反的文字？可满足不可满足？约束出现？自由变元？解释？赋值？一定要熟练背诵各种概念，不要出现模糊
• 演算性和说理性考题的类型较固定，难度较低
• 公理系统是必考且比较麻烦的一部分
  • 阅读课件，理解公理系统是在做什么
  • 熟练记住公理系统的内容（显然，这个也可以考默写），然后按照课件的思路学习一些定理的推导（较复杂的量力而行）
  • 集中地做若干套往年题中的公理系统部分，大概能发现考察的规律和变形的技巧

物理

• 注重基本模型和公式，不要被混乱的课件、废话连篇的教材和花里胡哨的课后习题所迷惑
• 一个很好地介绍了各类基本知识点的网课
• 考试主要考察基本公式和推论的应用，大题部分基本上列出三五个式子求解即可，一般不会有特别复杂的模型；小题考查地更加全面，这就看大家复习地是否全面、是否真正理解了。

---

祝大家考试顺利！

Author: diandian, Riccardo