2019年计算机软件基础考试大纲

考试科目：数据结构与算法、程序设计基础

考试形式和试卷结构

一、试卷满分及考试时间

试卷满分为150分，考试时间为180分钟。

二、试卷内容结构

数据结构与算法                         　约73%

程序设计基础    　                       约27%

三、试卷题型结构

单项选择题                   10小题，每小题2分，共20分

填空题                        5小题，每小题2分，共10分

判断题                        5小题，每小题2分，共10分

解答题                      7-8小题，共70分

程序设计题                  3-4小题，共40分

数据结构与算法

一、数据结构基本概念

考试内容

数据、数据元素、数据项、数据对象、数据结构的定义；

数据的逻辑结构、数据的物理结构、数据的运算的定义；

数据类型以及抽象数据类型的定义。

考试要求

掌握数据、数据元素、数据项之间的关系；

掌握数据结构的定义；

掌握数据结构的三要素；

掌握数据类型、抽象数据类型和数据结构之间的关系。

二、算法和算法分析

考试内容

    算法的定义、算法的特性、算法的时间复杂度和算法的空间复杂度的定义及计算。

考试要求

了解算法的定义以及特性；

了解衡量算法在资源上的两个方面；

掌握算法的渐进性分析方法，会用该方法对算法进行评估；

掌握Ο标记法、，理解大Ο标记法的意义；

掌握Ω标记法、，理解大Ω标记法的意义；

掌握Θ标记法、，理解大Θ标记法的意义；

了解时空权衡原则。

三、线性表

考试内容

线性表的定义；

顺序表的定义及其特点；

链式表的定义及其特点；

线性表的应用。

考试要求

掌握线性表的逻辑结构，以及基本操作；

掌握用顺序存储结构对线性表基本操作的实现；

掌握链式存储结构的实现技术，比如单向链表、双向链表、单循环链表、双向循环链表以及带头节点的链表；

掌握链式存储结构对线性表基本操作的实现；

具有在实际中选取不同存储结构的判断能力。

四、栈和队列

考试内容

栈和队列的定义；

顺序栈和链式栈的定义及其特点；

顺序队列和链式队列的定义及其特点；

栈和队列的应用。

考试要求

掌握栈、队列的逻辑结构，以及基本操作；

掌握顺序存储结构对栈和队列基本操作的实现；

掌握链式存储结构对栈和队列基本操作的实现；

掌握顺序存储结构中实现循环队列的具体要求；

理解递归调用和栈之间的关系；

掌握栈和队列的经典应用。

五、二叉树、树和森林

考试内容

二叉树、树和森林的定义；

二叉树的实现（包括顺序存储结构和链式存储结构）、二叉树的遍历；

二叉树结构下的应用，包括二叉检索树、Huffman编码以及堆；

平衡二叉树的定义、平衡因子的定义以及平衡二叉树的旋转操作；

树和森林的存储结构、树和森林的遍历以及森林与二叉树的转换；

并查集抽象数据类型的定义以及实现；

考试要求

掌握二叉树、树和森林的定义以及它们之间的异同点；

掌握二叉树的四种遍历，并具有能够依赖遍历完成对二叉树进行操作的能力；

理解二叉树采用顺序存储结构和链式存储结构的差异性；

掌握二叉树检索树、Huffman编码以及堆的实现；

理解平衡二叉树的意义；

掌握平衡二叉树的旋转操作；

掌握树、森林能够采用的各种存储方式的差异性；

掌握树和森林与二叉树的转换；

掌握树、森林在遍历方面和二叉树的不同以及相关性；

理解并查集的意义，以及掌握并查集的基本操作的实现。

六、图

考试内容

图的定义；

图的实现（包括邻接矩阵和邻接表）和基本操作；

图的两种遍历；

图的基本应用，包括最小支撑树、最短路径、拓扑排序和关键路径。

考试要求

掌握图的定义，包括完全图、连通图、简单路径、有向图、无向图、无环图等，明确理解图和二叉树、树和森林这种结构之间的异同点；

掌握图采用邻接矩阵和邻接表进行存储的差异性；

掌握广度优先遍历和深度优先遍历；

掌握最小支撑树（Prim算法、Kruskal算法）、最短路径（Dijkstra算法）、拓扑排序以及关键路径的实现过程。

七、查找

考试内容

查找的定义；

查找的如下算法：顺序查找法、折半查找法、散列（Hash）技术。

考试要求

理解查找的定义；

掌握对查找算法进行衡量的一些指标：平均查找长度、成功查找的查找长度、不成功查找的查找长度；

掌握顺序查找法和折半查找法，并理解二者之间的异同点；

掌握散列技术，包括散列函数、散列表、散列冲突的发生及其解决和负载因子；

理解不同查找技术的优缺点。

八、排序

考试内容

排序的定义，包括内排序和外排序；

排序的稳定性定义；

直接插入排序、冒泡排序、简单选择排序、Shell排序、快速排序、堆排序、归并排序、基数排序、K路归并排序的排序过程。

考试要求

理解内排序和外排序的区别；

掌握排序的稳定性；

对直接插入排序、冒泡排序、简单选择排序、Shell排序、快速排序、堆排序、归并排序、基数排序这些算法，掌握其在时间复杂度、空间复杂度以及是否稳定等方面的特点；

了解K路归并的外排序算法；

具有在不同的应用需求下，能够根据各种排序算法特点选择合适排序算法的能力。

九、矩阵和串

考试内容

矩阵和串的定义；

特殊矩阵的压缩存储、稀疏矩阵的三元组表示法；

串的模式匹配。

考试要求

掌握特殊矩阵的压缩存储方法；

掌握稀疏矩阵的三元组表示法以及相应的操作；

掌握多维数组和一维数组的映射；

掌握模式匹配的两个算法：Brute-Force和KMP。

程序设计基础

一、基本输入输出

考试内容

控制台形式的输入语法；

控制台形式的输出语法；

考试要求

掌握对不同类型数据的控制台输入方法；

掌握对不同类型数据的控制台输出方法，包括一些输出格式。

二、数据类型及运算

考试内容

相应编程语言内置的数据类型的使用；

相应编程语言内置的运算符的使用；

相应编程语言对自定义数据类型的语法。

考试要求

掌握语言内置的数据类型的正确定义、声明和使用；

掌握语言内置的运算符的正确使用；

具有自定义数据类型的能力。

三、语句

考试内容

顺序语句、选择语句和循环语句。

考试要求

掌握相应语言对顺序语句、选择语句和循环语句的语法以及运用。

四、函数

考试内容

函数的语法定义；

函数的嵌套调用，特别包括递归调用。

考试要求

掌握相应语言对函数定义的语法；

掌握递归思想，具有能够合理使用函数递归调用完成算法设计与实现的能力。