903《计算机基础》考试大纲

903《计算机基础》考试大纲

一、参考书目

1.《数据结构（C语言版）》严蔚敏主编，清华大学出版社,2014年，第1版。

2.《计算机网络》谢希仁，电子工业出版社，2017年，第7版。 3.《Computer Networking: A Top Down Approach》, James F. Kurose , 机械工业出版社, 2017第6版。

二、考试内容及要求 （一）数据结构

1．绪论

考试内容：数据结构，抽象数据类型，时间复杂度，空间复杂度。 考试要求：

了解《数据结构》的研究内容，数据结构的基本概念和术语，熟悉抽象数据类型的表示与实现，掌握算法的时间复杂度的计算方法。

2．线性表

考试内容：线性表的类型定义、顺序表示和实现、链式表示和实现，线性表在一元多项式相加中的应用。

考试要求：

（1）了解线性表的逻辑结构特性，线性表的两种存储实现方式和描述方法。 （2）掌握顺序表的定义与实现，包括查找、插入、删除算法的实现。 （3）掌握在各种链式结构中实现线性表操作的基本方法，能在实际应用中

1

选用适当的链表结构。

（4）能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。

（5）了解线性表在一元多项式相加中的应用。 3．栈和队列

考试内容：栈的定义、表示和实现，队列的定义、表示和实现，栈的应用，栈与递归的实现。

考试要求：

（1）了解栈和队列的定义、特性，并能正确应用它们解决实际问题。 （2）掌握栈的顺序表示、链式表示以及相应操作的实现。注意栈空和栈满的条件。

（3）掌握队列的顺序表示、链式表示以及相应操作的实现。注意循环队列中队头与队尾指针的变化情况。

（4）了解栈与递归的实现。 4．串

考试内容：串的类型定义，串的表示和实现，串的模式匹配算法。 考试要求：

（1）了解串的定义、基本操作。

（2）掌握顺序存储结构上串各种操作的方法。 （3）掌握KMP算法。 5．数组与广义表

2

考试内容：数组，稀疏矩阵，数组的顺序表示，压缩存储，广义表。 考试要求：

（1）了解数组的定义，掌握数组的顺序表示和实现。 （2）掌握特殊矩阵、稀疏矩阵压缩存储方式。 （3）了解广义表的概念、表示及存储结构。 6．树和二叉树

考试内容：二叉树与树，二叉树性质，二叉树与树的存储结构，二叉树的遍历和线索化，森林与二叉树的转换，赫夫曼树及其应用。

考试要求：

（1）了解树和二叉树的定义和性质。

（2）掌握二叉树的结构特性、存储结构及适用范围、遍历算法。 （3）掌握树存储结构及其特点、树、森林与二叉树的转换方法。 （4）掌握建立赫夫曼树和赫夫曼编码的方法及带权路径长度的计算。 7．图

考试内容：图的定义和存储结构、图的遍历、图的连通性问题、拓扑排序、关键路径、最短路径。

考试要求：

（1）理解图的基本概念，熟悉图的各种存储结构及其构造算法。 （2）掌握图的深度优先和广度优先两种路径遍历算法。 （3）了解AOV网络、AOE网络。 （4）掌握拓扑排序和关键路径算法。

3

（5）掌握kruskul和prim算法构造最小生成树算法。

（6）掌握Dijkstra算法求解单源最短路径，理解floyd算法求多源顶点间最短路径问题。

7．查找

考试内容：顺序表、有序表的查找，二叉排序树和平衡二叉树，哈希表的构造方法和处理冲突的方法。

考试要求：

（1）掌握顺序表和有序表的查找算法及其性能分析方法。 （2）掌握二叉排序树的构造和查找算法及其性能分析方法。 （3）理解AVL树的维护平衡方法。

（4）理解B_树、B+的特点、查找及构造方法。 （5）掌握哈希函数的构造及解决冲突的方法。 8．查找

考试内容：插入排序，快速排序，选择排序，归并排序，基数排序。 考试要求：

（1）掌握排序的基本概念和各种排序方法的特点，并能加以灵活应用。 （2）掌握插入排序、交换排序、选择排序、归并排序的方法及其性能分析方法。

（3）了解基数排序方法及其性能分析方法。

（二）计算机网络

1．计算机网络体系结构

4