一、考试内容概述

(一)基础理论知识

1.数据结构的基本概念和术语，算法的描述，时间复杂度和空之间复杂度的分析。

2.线性表的定义，线性表上经常执行的基本操作，以及这些操作在顺序和链式存储结构下的实现和复杂性分析。

3.栈和队列的定义、特征、表示和实现。

4.字符串的定义及其基本操作。

5.数组的定义、运算和存储，稀疏矩阵的压缩存储，广义表的定义和基本运算。

6.树的定义、基本术语和存储结构，二叉树的定义和性质，二叉树的存储结构和各种运算，哈夫曼和哈夫曼编码。

7.图的定义和常用术语，图的存储结构及其遍历操作，寻找最小生成树和最短路径的算法，拓扑排序。

8.各种搜索方法的算法、适用范围和时间复杂度分析。

9.各种内部排序算法的基本思想和时间复杂度分析，以及不同排序方法的比较。

(2)基本技能

1.能够阅读用c语言编写的算法。

2.可以分析算法实现的功能、运行结果和时间，以及空之间的复杂度。

3.能够根据需要用C类语言写一些经典的，常用的算法。

二、考试形式

考试采用闭卷、笔试答题的考试方式。

满分:150分(单科成绩)。

考试时间:120分钟。

三、试题难度分布

容易题占50%左右

中考占30%左右

难题占20%左右

四、题型及题型分数的分布

单选题约占20%

选择题占10%左右

填写空题约占15%

算法阅读题约占10%

综合题占30%左右

编程题占15%左右

动词 （verb的缩写）含量比例

靠前章绪论约占5%

第二章线性表约占10%

第三章书库和队列约占15%

第四章字符串约占5%

第五章数组和广义表约占5%

第六章树和二叉树约占15%

4.理解二叉树线索的本质和过程。

5.了解树的存储结构，以及如何将树和森林转化为二叉树。

6.掌握树路径长度和加权路径长度的计算方法，哈夫曼树的构造方法和哈夫曼编码。

第七章图

1.理解图形的定义。

2.理解图的基本术语:图与无向图、有向图、网、子图、连通图、强连通图、顶点度、进度、出度、顶点间路径、路径长度、回路。

3.理解图的两种存储结构:邻接矩阵和邻接表(包括逆邻接表)。

4.掌握遍历图的两种方法:深度优先搜索和广度优先搜索遍历图的算法及其时间复杂度。

5.理解生成树和最小生成树的概念，掌握最小生成树的构造过程(Prim算法和Kmskal算法)及其时间复杂度。

6.掌握拓扑排序的方法和最短路径的计算。

7.掌握最短路径问题的Dijkstra算法，理解弗洛伊德算法。

第八章抬头

1.了解搜索、关键词、平均搜索长度的概念。

2.静态查找表:掌握顺序搜索(哨兵)、二分搜索法算法及其效率(最差和平均搜索长度)分析，了解分块搜索算法及其效率分析。

3.动态查找表:掌握二叉排序树的定义、构造过程、搜索算法和效率分析，掌握平衡二叉树的定义和构造过程。

4.了解哈希表的特点，掌握构造哈希函数的方法(留下余数的方法除外等。)，并掌握处理冲突的方法和效率分析。

第九章内部排序

1.了解排序的目的、分类以及排序方法稳定性的定义。

2.插入人排序:掌握直接插入、拆分插入、希尔排序的排序算法。

3.快速排序:掌握冒泡排序的算法和快速排序的思路。

4.选择性排序:掌握选择性排序的简单算法，堆的定义，堆排序的思想。

5.了解归并排序的思想，基数排序的思想和特点。

6.了解各种内部排序方式的比较。

部分内容来源于网络转载、学生投稿，如有侵权或对本站有任何意见、建议或者投诉，请联系邮箱（1296178999@qq.com）反馈。 未经本站授权，不得转载、摘编、复制或者建立镜像， 如有违反，本站将追究法律责任！