2019年计算机软件基础考试大纲
考试科目：数据结构与算法、程序设计基础
考试形式和试卷结构
一、试卷满分及考试时间
试卷满分为150分，考试时间为180分钟。 二、试卷内容结构
数据结构与算法 约73% 程序设计基础 约27% 三、试卷题型结构
单项选择题 10小题，每小题2分，共20分 填空题 5小题，每小题2分，共10分 判断题 5小题，每小题2分，共10分 解答题 7-8小题，共70分 程序设计题 3-4小题，共40分
数据结构与算法
一、数据结构基本概念
考试内容
数据、数据元素、数据项、数据对象、数据结构的定义； 数据的逻辑结构、数据的物理结构、数据的运算的定义； 数据类型以及抽象数据类型的定义。
考试要求
掌握数据、数据元素、数据项之间的关系； 掌握数据结构的定义； 掌握数据结构的三要素；
掌握数据类型、抽象数据类型和数据结构之间的关系。
二、算法和算法分析
考试内容
算法的定义、算法的特性、算法的时间复杂度和算法的空间复杂度的定义及计算。
考试要求
了解算法的定义以及特性；
了解衡量算法在资源上的两个方面；
掌握算法的渐进性分析方法，会用该方法对算法进行评估；
1 / 5
掌握Ο标记法、，理解大Ο标记法的意义； 掌握Ω标记法、，理解大Ω标记法的意义； 掌握Θ标记法、，理解大Θ标记法的意义； 了解时空权衡原则。
三、线性表
考试内容
线性表的定义；
顺序表的定义及其特点； 链式表的定义及其特点； 线性表的应用。
考试要求
掌握线性表的逻辑结构，以及基本操作；
掌握用顺序存储结构对线性表基本操作的实现；
掌握链式存储结构的实现技术，比如单向链表、双向链表、单循环链表、双向循环链表以及带头节点的链表；
掌握链式存储结构对线性表基本操作的实现； 具有在实际中选取不同存储结构的判断能力。
四、栈和队列
考试内容
栈和队列的定义；
顺序栈和链式栈的定义及其特点； 顺序队列和链式队列的定义及其特点； 栈和队列的应用。
考试要求
掌握栈、队列的逻辑结构，以及基本操作； 掌握顺序存储结构对栈和队列基本操作的实现； 掌握链式存储结构对栈和队列基本操作的实现； 掌握顺序存储结构中实现循环队列的具体要求； 理解递归调用和栈之间的关系； 掌握栈和队列的经典应用。
五、二叉树、树和森林
考试内容
二叉树、树和森林的定义；
二叉树的实现（包括顺序存储结构和链式存储结构）、二叉树的遍历；
2 / 5
二叉树结构下的应用，包括二叉检索树、Huffman编码以及堆； 平衡二叉树的定义、平衡因子的定义以及平衡二叉树的旋转操作； 树和森林的存储结构、树和森林的遍历以及森林与二叉树的转换； 并查集抽象数据类型的定义以及实现；
考试要求
掌握二叉树、树和森林的定义以及它们之间的异同点；
掌握二叉树的四种遍历，并具有能够依赖遍历完成对二叉树进行操作的能力； 理解二叉树采用顺序存储结构和链式存储结构的差异性； 掌握二叉树检索树、Huffman编码以及堆的实现； 理解平衡二叉树的意义； 掌握平衡二叉树的旋转操作；
掌握树、森林能够采用的各种存储方式的差异性； 掌握树和森林与二叉树的转换；
掌握树、森林在遍历方面和二叉树的不同以及相关性； 理解并查集的意义，以及掌握并查集的基本操作的实现。
六、图
考试内容
图的定义；
图的实现（包括邻接矩阵和邻接表）和基本操作； 图的两种遍历；
图的基本应用，包括最小支撑树、最短路径、拓扑排序和关键路径。
考试要求
掌握图的定义，包括完全图、连通图、简单路径、有向图、无向图、无环图等，明确理解图和二叉树、树和森林这种结构之间的异同点；
掌握图采用邻接矩阵和邻接表进行存储的差异性； 掌握广度优先遍历和深度优先遍历；
掌握最小支撑树（Prim算法、Kruskal算法）、最短路径（Dijkstra算法）、拓扑排序以及关键路径的实现过程。
七、查找
考试内容
查找的定义；
查找的如下算法：顺序查找法、折半查找法、散列（Hash）技术。
考试要求
理解查找的定义；
3 / 5