猪脚说第十四期

猪脚说第十四期

Diandian funny boy
  2023-07-14 23:07 2023-07-14 23:07 Created   2023-07-14 23:02:39 2023-07-14 23:02:39 Updated    2.1k Words  9 Mins  

数据结构期末复习

复习知识点自查

考试时查看不了上机作业，因此大家一定要记得将前七次作业的网页保存为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）。

考试可能用到的函数模版

中缀转后缀

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

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
 将一个不含空格的中缀表达式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--];
}

后缀转中缀

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

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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);
    }
} // 根据存储好的表达式树，输出中缀表达式

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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);

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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，你可以考虑纯数组实现树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

  • Title: 猪脚说第十四期
  • Author: Diandian
  • Created at : 2023-07-14 23:00:07
  • Updated at : 2023-07-14 23:02:39
  • Link: https://cutedian.github.io/2023/07/14/猪脚说第十四期/
  • License: This work is licensed under CC BY-NC-SA 4.0.
推荐阅读
猪脚说第十二期 猪脚说第十二期 猪脚说第五期 猪脚说第五期 猪脚说第九期 猪脚说第九期
推荐阅读
猪脚说第十二期 猪脚说第十二期 猪脚说第五期 猪脚说第五期
Comments
On this page
猪脚说第十四期
  1. 1. 数据结构期末复习
    1. 1.1. 复习知识点自查
      1. 1.1.1. 栈与队列（第四次作业）
      2. 1.1.2. 树（第五次作业）
      3. 1.1.3. 查找与排序（第六次作业）
      4. 1.1.4. 图（第七次作业）
    2. 1.2. 考试可能用到的函数模版
      1. 1.2.1. 中缀转后缀
      2. 1.2.2. 后缀转中缀
      3. 1.2.3. 前、中、后序遍历一般写法
      4. 1.2.4. 遵循一定规则的树节点插入
      5. 1.2.5. 更简便的树的实现方式
  2. 2. 其他科目复习材料
  3. 3. 一些复习建议
    1. 3.0.1. 数分
    2. 3.0.2. 离散
    3. 3.0.3. 物理
  • 祝大家考试顺利！