集美大学2023研究生考试大纲：数据结构

集美大学2023年硕士研究生入学考试初试自命题考试大纲已经发布，本次考试科目代码为[822]，考试科目名称为“数据结构”。本文将从目标、试卷结构、考试内容和答题方式四个角度进行分析，为考生提供一些参考意见。

考试目标

通过本次考试，考官将考查考生对基本数据结构相关知识的理解，包括逻辑结构、存储结构和运算三者的关系，以及考生对不同算法开销的分析能力。还将考查考生对线性结构、树、图和查找、排序算法的掌握程度，并要求考生在指定的数据结构和算法中完成特定问题的求解。此外，考官还将考查考生分析问题及设计简单解决方案的能力，要求考生能够针对实际问题，选择合适的数据结构和算法，设计问题求解方案。

试卷结构

本次考试总时长为180分钟，总分为150分。试卷结构包括选择题、程序填空题、综合应用题和算法设计题四种题型。其中，选择题占30分，程序填空题占20分，综合应用题占40分，算法设计题占60分。

答题方式

本次考试为闭卷笔试。

考试内容

本次考试共分为四个部分，分别为绪论、线性表、栈和队列、串。

1. 绪论

绪论部分主要考察考生对数据结构、算法等的基本概念的掌握情况，包括抽象数据类型、算法的描述和算法分析等。考生需要掌握数据逻辑结构的四种基本结构、数据结构中的物理存储结构与逻辑结构。此外，还需要熟练掌握时间复杂度与空间复杂度、语句频度等概念及计算，了解语句频度与时间复杂度的不同，掌握大O表示法来表示时间复杂度。

2. 线性表

线性表部分主要考察考生对线性表的数据结构的掌握情况，包括线性表的顺序存储结构、链式存储结构，以及单链表、循环链表和双向链表等。考生需要熟练掌握线性表的基本操作：查找、插入、删除，尤其是链式存储结构上的编程实现，如指针在链表中的操作。同时，考生需理解随机访问的含义。

3. 栈和队列

栈和队列部分主要考察考生对栈和队列的掌握情况，包括栈的抽象数据类型、表示与实现、应用、队列的抽象数据类型、链式队列、循环队列等。考生需要掌握栈的操作特性及其应用，掌握顺序栈和链栈的四要素，掌握栈的常见应用示例。还需掌握队列的操作特性及其应用，掌握顺序队列、循环队列和链队列的表示，掌握队列的常见应用示例。

4. 串

串部分主要考察考生对串的掌握情况，包括串类型的定义、表示和实现、串的模式匹配、串操作应用等。考生需要掌握顺序串和链串的主要特点及其应用场合。同时，考生需掌握KMP算法的原理和代码实现。