北京交通大学软件工程专业隶属于软件学院，该学院是教育部37所国家示范性软件学院之一，而北京交通大学软件工程专业的本科教育就已经获首批国家级一流专业建设点。近几年，北京交通大学开设软件工程专业在职研究生教育，考生报考需要参加考试。其复试科目之一为《数据结构》。下面介绍2022年北京交通大学在职研究生考试大纲之复试《数据结构》。

　　参加北京交通大学在职研究生的考生，可以将严蔚敏、吴伟民编著的《数据结构》(C 版)作为参考书目，并掌握以下八个知识点。

　　第一，考生应理解数据结构的基本概念、算法的五个特性、抽象数据类型，掌握计算语句频度和估算算法时间复杂度和空间复杂度的方法。

　　第二，考生应理解线性表的逻辑结构、 从时间、空间复杂度的角度比较线性表两种存储结构的不同特点及 其适用场合，掌握线性表的顺序存储结构和链式存储结构、线性表在顺序结构上实现基本操作的方法以及线性表在链式结构上实现基本操作的方法。

　　第三，考生应理解栈的特点、递归算法中栈的作用、队列的特点、掌握在顺序存储结构上栈的基本操作的实现、在链式存储结构上栈的基本操作的实现、栈的典型应用实例、在顺序存储结构上循环队列基本操作的实现、在链式存储结构上链队列的基本操作的实现、队列的典型应用实例。

　　第四，考生应理解数组的存储结构、稀疏矩阵的三元组表示以及运算处理方法、广义表的概念，掌握数组在行序为主序的存储结构中的地址计算方法以及特殊矩阵的压缩存储方法。

　　第五，考生应理解二叉树的概念、树的各种存储结构及其特点、树与二叉树、森林与二叉树的相互转换以及树与等价类划分问题，掌握二叉树的各种存储结构、二叉树的性质、按各种次序遍历二叉树的递归算法、按各种次序遍历二叉树的非递归算法、建立二叉树的各种算法以及建立最优二叉树和哈夫曼编码的方法。

　　第六，考生应理解图的基本概念，掌握图的存储结构、图的深度优先遍历和广度优先遍历、最小生成树、某一点到其他各点之间的最短路径、拓扑排序以及关键路径和关键活动。

　　第七，考生应理解索引查找的过程和特点、B-树的特点及其建立过程和查找过程，掌握顺序查找算法及特点、折半查找算法及特点、二叉排序树的构造方法和查找过程、二叉平衡树的旋转平衡方法、哈希表的构造方法和查找方法、各种查找算法在等概率情况下查找成功和查找失败时的平均查找长度的计算方法。

　　第八，考生应理解SHELL 插入排序方法的排序过程、 基数排序方法的排序过程和特点、各种排序方法的算法实现以及时间复杂度和空间复杂度分析，掌握方法的排序过程和特点、交换排序方法的排序过程和特点、选择排序的排序过程和特点以及归并排序方法的排序过程和特点。

　　以上是有关2022年北京交通大学在职研究生考试大纲之复试《数据结构》的详细介绍。如果还有其他疑问需要解答，可登录本网站咨询本站老师。