《XX理工大学20X年全国硕士研究生招生考试自命题科目《数据结构》考试大纲.docx》由会员分享，可在线阅读，更多相关《XX理工大学20X年全国硕士研究生招生考试自命题科目《数据结构》考试大纲.docx（4页珍藏版）》请在课桌文档上搜索。
1、XX理工大学2023年全国硕士研究生招生考试自命题科目考试大纲科目代码：823考试科目：数据结构一、考试性质本课程是计算机类专业、网络空间安全专业的专业基础必修课，其涵盖知识和能力培养是上述专业研究生开展创新研究必须具备的基础。二、考查目标本课程主要考核常见数据结构（线性表、树、图等）表示方法、操作及应用；常用查找技术与排序算法等。主要考查目标有：1 .数据结构和算法设计基础知识，计算机内部数据对象表示和特性，线性表、树、图等常见数据逻辑结构、存储结构表示及其差异，针对具体问题的模型分析与求解。2 .常见数据结构上的基本操作和算法；排序、查找等算法原理及实现；算法的时间复杂度和空间复杂度分析方
2、法。3 .综合运用课程知识开展数据结构、算法的设计、分析和应用。三、适用范围本考试大纲适用于大数据技术与工程专业的硕士研究生招生考试。四、考试形式和试卷结构1 .试卷满分及考试时间试卷满分：150分；考试时间：180分钟。2 .试卷内容结构1）数据结构、算法相关基础知识：约20分；2）数据结构、算法相关分析与应用：约80分；3）数据结构、算法的代码分析、设计和实现：约50分。3 .试卷题型结构及分值比例（注：题型和分值是参考值）题型单项选择题计算或分析题程序阅读和填空题算法设计题分值30703020备注：命题可根据考核需要，对试卷内容结构、题型结构及分值比例做适当调整。五、考查内容1.数据结构
3、与算法绪论1）数据结构的基本概念，包括数据的逻辑特点、存储表示；2）数据抽象方法，数据结构的抽象数据类型ADT表示；3）算法描述方法、算法精化过程和算法时间、空间复杂度分析方法。2 .线性表1）线性表的逻辑结构和抽象数据类型定义；2）线性表的顺序存储和链式存储，线性表创建、插入、删除和查找等基本操作的实现以及算法时间复杂度分析；3）能分析不同存储结构的优缺点和适用场合，能分析不同的存储方式对算法性能的影响；4）单循环链表、双链表和循环双链表的实现以及应用；5）线性表的应用实例分析：一元多项式运算；Josephus问题；6）字符串的逻辑结构、存储结构和模式匹配。3 .栈和队列1）栈和队列的逻辑特
4、点、抽象数据类型；2）栈和队列的顺序表示和链接表示，以及基于不同存储结构的基本操作的实现3）递归函数的执行过程以及使用栈进行递归函数与非递归函数的转换;4）栈的应用：数制转换；迷宫问题；5）队列的应用：农夫过河问题；银行业务模拟；密码加密解密问题；6）深度优先和广度优先搜索策略的原理、不同之处以及应用场合。4,树与二叉树1）树与二叉树抽象数据类型、不同存储实现与约束分析；2）树与二叉树周游算法及复杂度分析；3）最优前缀编码问题及算法分析；4）线索二叉树；5）二叉排序树表示、操作实现以及时间、空间复杂度分析；6）平衡二叉排序树表示、操作实现以及时间、空间复杂度分析；5.图1）图的抽象数据类型、不
5、同存储结构与适用性分析；2）图的深度优先周游和广度优先周游两类策略和实现方法，能基于图的具体存储结构分析周游的处理过程，并分析两类周游算法的复杂度；3）面向应用的核心算法实现与分析，包括Prim和KrUSkal最小生成树算法、Dijkstra和Floyd最短路径算法；4）面向特定应用的图形态，包括AOV网和AOE网。6.集合与字典1）集合与字典的顺序表示、操作实现以及时间、空间复杂度分析；2）字典的散列表示、操作实现以及时间、空间复杂度分析。7.排序1）插入类排序：直接插入、二分插入和希尔插入排序；2）选择类排序：直接选择和堆排序；3）交换类排序：冒泡排序和快速排序；4）分配类排序：基数排序；5）归并类排序：两路归并排序；6）各种排序算法时间复杂度、空间复杂度、算法稳定性等方面的综合比较，根据应用场合选择合适的排序算法。六、参考书目X.算法与数据结构（C语言描述）XX出版社，20XX年
