新祥旭考研官网 http:/www.xxxedu.net/西安交通大学 2020 年 915 计算机软件基础考研科目参考书目及考试大纲考试科目：数据结构与算法、程序设计基础考试形式和试卷结构一、试卷满分及考试时间试卷满分为 150分，考试时间为 180分钟。二、试卷内容结构数据结构与算法 约 73%程序设计基础 约 27%三、试卷题型结构单项选择题 10 小题，每小题 2分，共 20分填空题 5 小题，每小题 2分，共 10分判断题 5 小题，每小题 2分，共 10分解答题 7-8 小题，共 70分程序设计题 3-4 小题，共 40分数据结构与算法一、数据结构基本概念考试内容数据、数据元素、数据项、数据对象、数据结构的定义；数据的逻辑结构、数据的物理结构、数据的运算的定义；数据类型以及抽象数据类型的定义。考试要求掌握数据、数据元素、数据项之间的关系；掌握数据结构的定义；掌握数据结构的三要素；掌握数据类型、抽象数据类型和数据结构之间的关系。二、算法和算法分析考试内容算法的定义、算法的特性、算法的时间复杂度和算法的空间复杂度的定义及计算。考试要求了解算法的定义以及特性；了解衡量算法在资源上的两个方面；掌握算法的渐进性分析方法，会用该方法对算法进行评估；掌握 标记法、，理解大 标记法的意义；掌握 标记法、，理解大 标记法的意义；新祥旭考研官网 http:/www.xxxedu.net/掌握 标记法、，理解大 标记法的意义；了解时空权衡原则。三、线性表考试内容线性表的定义；顺序表的定义及其特点；链式表的定义及其特点；线性表的应用。考试要求掌握线性表的逻辑结构，以及基本操作；掌握用顺序存储结构对线性表基本操作的实现；掌握链式存储结构的实现技术，比如单向链表、双向链表、单循环链表、双向循环链表以及带头节点的链表；掌握链式存储结构对线性表基本操作的实现；具有在实际中选取不同存储结构的判断能力。四、栈和队列考试内容栈和队列的定义；顺序栈和链式栈的定义及其特点；顺序队列和链式队列的定义及其特点；栈和队列的应用。考试要求掌握栈、队列的逻辑结构，以及基本操作；掌握顺序存储结构对栈和队列基本操作的实现；掌握链式存储结构对栈和队列基本操作的实现；掌握顺序存储结构中实现循环队列的具体要求；理解递归调用和栈之间的关系；掌握栈和队列的经典应用。五、二叉树、树和森林考试内容二叉树、树和森林的定义；二叉树的实现（包括顺序存储结构和链式存储结构）、二叉树的遍历；二叉树结构下的应用，包括二叉检索树、Huffman 编码以及堆；平衡二叉树的定义、平衡因子的定义以及平衡二叉树的旋转操作；树和森林的存储结构、树和森林的遍历以及森林与二叉树的转换；并查集抽象数据类型的定义以及实现；考试要求新祥旭考研官网 http:/www.xxxedu.net/掌握二叉树、树和森林的定义以及它们之间的异同点；掌握二叉树的四种遍历，并具有能够依赖遍历完成对二叉树进行操作的能力；理解二叉树采用顺序存储结构和链式存储结构的差异性；掌握二叉树检索树、Huffman 编码以及堆的实现；理解平衡二叉树的意义；掌握平衡二叉树的旋转操作；掌握树、森林能够采用的各种存储方式的差异性；掌握树和森林与二叉树的转换；掌握树、森林在遍历方面和二叉树的不同以及相关性；理解并查集的意义，以及掌握并查集的基本操作的实现。六、图考试内容图的定义；图的实现（包括邻接矩阵和邻接表）和基本操作；图的两种遍历；图的基本应用，包括最小支撑树、最短路径、拓扑排序和关键路径。考试要求掌握图的定义，包括完全图、连通图、简单路径、有向图、无向图、无环图等，明确理解图和二叉树、树和森林这种结构之间的异同点；掌握图采用邻接矩阵和邻接表进行存储的差异性；掌握广度优先遍历和深度优先遍历；掌握最小支撑树（Prim 算法、Kruskal 算法）、最短路径（Dijkstra 算法）、拓扑排序以及关键路径的实现过程。七、查找考试内容查找的定义；查找的如下算法：顺序查找法、折半查找法、散列（Hash）技术。考试要求理解查找的定义；掌握对查找算法进行衡量的一些指标：平均查找长度、成功查找的查找长度、不成功查找的查找长度；掌握顺序查找法和折半查找法，并理解二者之间的异同点；掌握散列技术，包括散列函数、散列表、散列冲突的发生及其解决和负载因子；理解不同查找技术的优缺点。八、排序考试内容排序的定义，包括内排序和外排序；新祥旭考研官网 http:/www.xxxedu.net/排序的稳定性定义；直接插入排序、冒泡排序、简单选择排序、Shell 排序、快速排序、堆排序、归并排序、基数排序、K 路归并排序的排序过程。考试要求理解内排序和外排序的区别；掌握排序的稳定性；对直接插入排序、冒泡排序、简单选择排序、Shell 排序、快速排序、堆排序、归并排序、基数排序这些算法，掌握其在时间复杂度、空间复杂度以及是否稳定等方面的特点；了解 K路归并的外排序算法；具有在不同的应用需求下，能够根据各种排序算法特点选择合适排序算法的能力。九、矩阵和串考试内容矩阵和串的定义；特殊矩阵的压缩存储、稀疏矩阵的三元组表示法；串的模式匹配。考试要求掌握特殊矩阵的压缩存储方法；掌握稀疏矩阵的三元组表示法以及相应的操作；掌握多维数组和一维数组的映射；掌握模式匹配的两个算法：Brute-Force 和 KMP。程序设计基础一、基本输入输出考试内容控制台形式的输入语法；控制台形式的输出语法；考试要求掌握对不同类型数据的控制台输入方法；掌握对不同类型数据的控制台输出方法，包括一些输出格式。二、数据类型及运算考试内容相应编程语言内置的数据类型的使用；相应编程语言内置的运算符的使用；相应编程语言对自定义数据类型的语法。考试要求掌握语言内置的数据类型的正确定义、声明和使用；新祥旭考研官网 http:/www.xxxedu.net/掌握语言内置的运算符的正确使用；具有自定义数据类型的能力。三、语句考试内容顺序语句、选择语句和循环语句。考试要求掌握相应语言对顺序语句、选择语句和循环语句的语法以及运用。四、函数考试内容函数的语法定义；函数的嵌套调用，特别包括递归调用。考试要求掌握相应语言对函数定义的语法；掌握递归思想，具有能够合理使用函数递归调用完成算法设计与实现的能力。