中国传媒大学硕士研究生入学考试算法与数据结构考试大纲.doc

《算法与数据结构》是中国传媒大学硕士研究生入学考试文学院语言学及应用语言学专业语言信息处理方向的重要考试科目。该考试大纲旨在测试考生对于数据结构的逻辑和物理结构、数据运算、算法设计与分析等方面的理解和应用能力。 考试内容涵盖了数据结构的基本概念，包括数据结构的定义、逻辑结构、存储结构、数据运算和抽象数据类型的表示与实现。这些基础知识是理解和掌握后续数据结构的基础。 接着，大纲深入讲解了线性表，包括线性表的顺序表示和链式表示，如顺序表、单链表、循环链表、双向链表等，并强调了链表的应用。此外，栈和队列作为两种重要的线性结构，其基本概念、实现方式及应用也被列入考试范围，包括栈的顺序和链式实现、队列的顺序和链式实现，以及它们在实际问题中的应用，如递归的实现。 串是另一种重要的数据结构，涉及顺序存储、堆分配存储和块链存储，并涵盖模式匹配算法，如Brute-Force和KMP算法。串操作的应用也是考察的重点。 数组和广义表是数据结构中的基本元素，大纲要求考生理解数组的顺序表示、特殊矩阵、稀疏矩阵的概念，以及广义表的定义、存储结构和运算。对于树和二叉树，考生需要掌握基本术语、定义、性质、存储结构、遍历方法、线索二叉树，以及赫夫曼树及其应用。 图作为一种复杂的数据结构，包括图的定义、基本术语、各种表示方法（如数组表示、邻接表、十字链表、邻接多重表）以及图的搜索算法，如深度优先搜索、广度优先搜索，还有连通分量、生成树、强连通分量、最小生成树、拓扑排序、关键路径等概念。 动态存储管理部分，考生需要了解可利用空间表、边界标识法、伙伴系统和无用单元收集等内存管理技术。查找部分包括基本概念、多种查找算法（如顺序查找、二分查找、分块查找、二叉排序树等）以及哈希表的构造和冲突解决方法。 内部排序是算法设计的关键部分，包括直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、树形选择排序、堆排序、归并排序、基数排序等，以及对各种排序算法的性能分析。外部排序则涉及多路平衡归并、置换-选择排序、最佳归并树等。 文件是数据持久化的重要手段，大纲要求考生熟悉文件的基本概念、顺序文件、索引文件、ISAM和VSAM文件、散列文件、多重表文件、倒排文件等不同类型的文件结构。 考试题型多样，包括是非题、选择题、填空题、简答题、算法设计题和综合题，考试形式为笔试，时间三小时，不允许使用任何辅助工具。 通过这份大纲，我们可以看出中国传媒大学对于硕士研究生在算法与数据结构方面的要求是全面而深入的，不仅要求理论知识的掌握，还强调实践能力和问题解决能力的培养。考生需全面复习并熟练掌握这些知识点，以应对考试挑战。