考研大纲包含了硕士研究生考试相应科目的考试形式、要求、范围、试卷结构等指导性考研用书。今天，为了方便2025考研的学子们，小编为大家整理了“2025考研大纲：南京工业大学2025年考研自命题科目 828数据结构与操作系统 考试大纲”的相关内容，谢谢您的关注。
828《数据结构与操作系统》2025年考试大纲
一、考试的基本要求
要求考生比较系统地理解数据结构的基本概念和基本知识，从数据结构的逻辑结构、存储结构和数据的操作三个方面掌握线性表、树、图等常用的数据结构。掌握在各种常用数据结构上实现高效的查找和排序算法，并对算法的时间和空间复杂性有一定的分析能力。针对简单的应用问题，能够选择合适的数据结构设计有效的算法。
另一方面，要求考生比较系统地掌握操作系统各要素的基本概念、基本原理和方法，对操作系统如何管理和控制计算机系统的所有硬件和软件资源以达到方便用户、提高资源的使用效率有较深入的了解。
要求考生具有较强的抽象思维能力、逻辑推理能力、软件设计和实现能力以及综合运用所学的知识分析问题和解决问题的能力。
二、考试方式和考试时间
闭卷考试，总分150（数据结构90+操作系统60），考试时间为3小时。
三、参考书目（仅供参考）
《数据结构与算法》,刘斌，赵艳红，李志芳，上海交通大学出版社，2022年
《计算机操作系统》(第三版)，汤小丹，梁红兵，哲凤屏，汤子瀛，西安电子科技大学出版社，2007年
四、试题类型：
主要包括选择题 、编程题、计算题、综合题等类型，并根据每年的考试要求做相应调整。
五、考试内容及要求
第一部分 数据结构-线性表
掌握：线性表的逻辑结构、存储结构及描述方式；顺序表的定义、插入、删除；STL中容器vector的创建和使用方法；单链表、双向链表和循环链表的定义、插入、删除；STL中容器list的创建和使用方法；顺序栈、链栈的表示、入栈和出栈操作；STL中stack的创建和使用方法；顺序队列、链队列的表示、入队和出队操作；循环队列的队空和队满的判断；STL中queue的创建和使用方法；矩阵的压缩存储的概念以及有关计算方法；稀疏矩阵的三元组表示方法；串的定义、逻辑结构和存储结构；广义表的定义、表示和基本操作。
熟悉：线性结构的定义和特点；顺序表和单链表的组织方法、特点、算法和性能分析；单链表、双向链表和循环链表之间的区别；栈和队的特点；顺序栈和链栈上基本运算的实现和简单算法设计；链队上基本运算的实现和简单算法设计；多维数组的定义以及逻辑结构；特殊矩阵的非零元下标与数组下标的对应关系。
第二部分 数据结构-树
掌握：树的逻辑结构；二叉树的定义以及性质；二叉树的几种表示方法；二叉树的构建方法；二叉树的三种遍历算法；完全二叉树表示方法；堆的创建和维护，完全二叉树转化为堆的方法；STL中的priotity_queue；线索二叉树的定义及构造方法；树的存储结构；哈夫曼树的构建及其应用，哈夫曼编码和解码方法；表达式树的构建及其应用，由表达式数如何得到逆波兰表达式，利用逆波兰表达式求表达式的值；森林的遍历；并查集的两个基本操作和应用；
熟悉：树的常用术语和含义；二叉树性质的证明；利用二叉树的遍历设计有关算法解决简单应用问题；线索二叉树的插入、删除结点算法，利用线索二叉树确定结点的前驱和后继结点；调度场算法；线段树；树状数组；森林与二叉树的转换。
第三部分 数据结构-图
掌握：图的逻辑结构特征；图的邻接矩阵表示方法、vector数组表示法；图的深度优先搜索的算法及应用；图的广度优先搜索算法及应用；求有向图强连通分量的Tarjan算法；最小生成树的概念，用Prim算法和Kruskal算法构造连通图的最小生成树的方法和复杂度；拓扑排序；AOE网的关键路径的基本原理和实现方法；单源最短路径Dijkstra算法和Spfa算法的基本思想和性能分析；利用Floyd算法求图的任意两个顶点之间的最短距离。
熟悉：图的定义和术语；图的链接表表示方法、图的链式前向星的表示方法；求有向图强连通分量的Kosaraju算法；无向图的割点和桥；生成树概念；传递闭包。
第四部分 数据结构-查找和排序
掌握：二分查找的基本条件和方法；分块查找的基本思想和性能分析；二分查找和分块查找的实现方法；STL中的有序表查找算法；字符串的传统匹配方法，字符串的KMP模式匹配方法；二叉查找树的构建、插入结点和删除结点的方法；构建AVL树的基本过程和方法；伸展树的基本原理和基本操作；2-3树的定义和构建方法；散列表技术的相关概念、常用的散列函数、常用的冲突处理方法；散列树的构建方法和查找、插入、删除操作；直接插入排序、希尔排序、直接选择排序、堆排序、交换排序、快速排序、归并排序、计数排序、桶排序、基数排序基本原理、性能分析和稳定性分析；堆排序、快速排序、归并排序的算法实现；STL中排序函数sort的使用方法。
熟悉：跳跃链表的定义、表示和实现方法；红黑树；B-树；B+树；乘法散列函数；散列法效率分析；trie树的定义和基本操作；判定树；外部排序的基本原理；多路归并的基本原理和方法；置换-选择排序的基本原理和性能分析。
第五部分 操作系统-进程管理
掌握：进程的基本概念；进程的特征与状态；进程的创建、终止、堵塞与唤醒、挂起与激活；进程的同步；几个经典的进程同步问题；消息缓冲队列通信机制；线程的同步与通信；
熟悉：程序顺序执行及其特征；程序并发执行及其特征；进程控制块；进程通信类型；消息传递通信的实现方法。
第六部分 操作系统-处理机调度与死锁
掌握：调度队列模型以及选择调度算法的若干准则；高优先权优先调度算法、时间片轮转调度算法、最高响应比调度算法；利用银行家算法避免死锁；死锁的检测与解除；
熟悉：处理机调度的基本概念；先来先服务调度算法、短作业优先调度算法；产生死锁的原因和必要条件；系统安全状态。
第七部分 操作系统-存储器管理
掌握：程序的装入和连接；页面与页表；地址变换机构；两级和多级页表；段页式存储管理方式；虚拟存储器的特征；请求分页存储管理中的内存分配策略、分配算法和调页策略；最佳置换算法和FIFO算法LRU置换算法；Clock置换算法；
熟悉：存储器的层次结构；连续分配方式：固定分区、动态分区、可重定位分区、对换；反向页表；分段存储的基本原理；信息共享；虚拟存储器的实现方法；请求分页中的硬件支持；请求分段中的硬件支持；分段的共享与保护。
第八部分 操作系统-设备管理
掌握： 程序I/O方式；中断驱动I/O控制方法；DMA I/O控制方法；循环缓冲、缓冲池；中断驱动程序；设备驱动程序；独立型设备的分配与去配；共享型设备的分配与去配；磁盘高速缓存；提高磁盘I/O速度的其它方法；
熟悉：I/O设备；总线系统； I/O通道控制方法；I/O软件的设计目标与原则；设备独立性软件；用户层软件；设备分配的相关数据结构；磁盘调度；廉价磁盘冗阵列。
第九部分 操作系统-文件管理与接口命令
掌握：索引文件、索引顺序文件、直接文件和哈希文件；连续分配、链接分派、索引分配；文件存储的空闲表法、空闲链表发、位示图法、成组链接法；基于索引结点的共享方式、利用符号链实现文件共享；数据一致性控制；Shell命令语言；
熟悉： 文件、记录和数据项的基本概念；文件类型和文件系统模型；文件的基本操作；文件逻辑结构的类型；顺序文件；文件控制块与索引结点、目录结构、目录查询技术；重复数据的数据一致性问题；联机用户接口、联机命令类型、键盘终端处理程序；系统调用概念及基本类型；图像界面接口。
以上就是小编整理的“2025考研大纲：南京工业大学2025年考研自命题科目 828数据结构与操作系统 考试大纲”的全部内容，更多关于南京工业大学研究生考试大纲,828数据结构与操作系统考研大纲的信息，尽在“考研大纲”栏目，希望对大家有所帮助！
