2021年西北工业大学考研真题解析，这次主要讲的是算法这块儿。把免费的真题和期末题发给大家，先给复习计划做个体检，省得有同学没买真题不知道方向。咱们就不想那么多复杂的了，只为让大家复习得更高效点。随时欢迎大家提意见，我会继续改进。答案部分稍微收点费，毕竟人力成本高，还请理解。希望所有考研的瓜大儿们都能顺顺利利考上。 这次真题解析分为六道大题，每道题都有详细的思路点拨。第一题是关于二叉树的遍历和中缀表达式，20分。给定一棵二叉树，要求写出前序遍历和后序遍历序列，还要设计算法输出中缀表达式。前序遍历的顺序是根-左-右，后序遍历的顺序是左-右-根。中缀表达式则可以用递归的思想来实现，遍历节点时遇到操作符就入栈，遇到非操作符就直接输出，最后把栈里的操作符按照优先级连接起来。 第二题是稀疏矩阵的转置问题，20分。给出一个4x4稀疏矩阵A的三元组表，需要把它转置为矩阵B，并按照行优先排序。三元组转置算法其实很简单，把行和列交换一下就行，值保持不变。如果要按行优先排序的话，可以先遍历原矩阵的每一行，再遍历每一列，收集新的行列值，最后再排序一下就行了。时间复杂度主要是遍历和排序这两个步骤决定的，大概是O(n log n)。 第三题是有向图最短路径问题，20分。给了一个邻接矩阵表格和一个图2021-2，要求画出带权有向图和邻接表，还要设计算法求0顶点到各点的最短路径。这道题可以用Floyd-Warshall算法或者Dijkstra算法来解决。不过题目只要求到各点最短路径，Dijkstra算法更直观一些。步骤是先初始化dist[0][i]为边权，然后进行松弛操作直到找不到更短边为止。时间复杂度大概是O(n²)。 第四题是有向图拓扑排序问题，15分。根据图2021-2来回答拓扑排序的算法思想和结果。拓扑排序可以利用入度表来实现：入度为0的节点先出队，出队后把其邻接节点的入度减1，继续判断直到队列为空为止。如果图中有环的话，拓扑排序结果会循环回到起点；如果没有环的话就能产生唯一的线性序。 第五题是快速排序问题，15分。给定待排序列17、6、26、9、10、7、10、4，使用快速排序升序排列。快速排序的基本思想是分而治之：选一个主元pivot，把比pivot小的元素放到左边，比pivot大的元素放到右边，然后递归处理左右子数组。以第一个元素为主元为例，过程就是分区-递归左子数组-递归右子数组。 最后一道题是二叉树权值比较与查找问题，10分。需要设计算法判断两棵二叉树所有节点的权值之和是否相同，还要在二叉排序树中查找给定关键字并输出路径或者提示信息。第一问直接递归遍历两棵树比较权值总和即可；第二问先判断是不是二叉排序树（中序遍历应该是递增的），再用递归或者迭代找到目标值。如果找到了就回溯记录路径；如果没找到就输出提示信息。