903计算机基础考试大纲.pdfVIP

非淡泊无以明志，非宁静无以致远。——诸葛亮

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

一、参考书目

《数据结构语言版)》严蔚敏主编，清华大学出版社年，第版。

1.(C,20141

《计算机网络》谢希仁，电子工业出版社年，第版。

2.，20177

《》

3.ComputerNetworking：ATopDownApproach，JamesF.Kurose,

机械工业出版社第版。

，20176

二、考试内容及要求

(一)数据结构

1.绪论

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

考试要求：

了解《数据结构》的研究内容，数据结构的基本概念和术语，熟悉抽象数

据类型的表示与实现，掌握算法的时间复杂度的计算方法。

2.线性表

考试内容：线性表的类型定义、顺序表示和实现、链式表示和实现，线性

表在一元多项式相加中的应用。

考试要求：

()了解线性表的逻辑结构特性，线性表的两种存储实现方式和描述方法。

1

()掌握顺序表的定义与实现，包括查找、插入、删除算法的实现。

2

()掌握在各种链式结构中实现线性表操作的基本方法，能在实际应用中

3

选用适当的链表结构。

()能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特

4

非淡泊无以明志，非宁静无以致远。——诸葛亮

点及其适用场合。

()了解线性表在一元多项式相加中的应用。

5

3.栈和队列

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

栈与递归的实现。

考试要求：

()了解栈和队列的定义、特性，并能正确应用它们解决实际问题。

1

()掌握栈的顺序表示、链式表示以及相应操作的实现。注意栈空和栈满的

2

条件。

()掌握队列的顺序表示、链式表示以及相应操作的实现。注意循环队列中

3

队头与队尾指针的变化情况。

()了解栈与递归的实现。

4

4.串

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

考试要求：

()了解串的定义、基本操作。

1

()掌握顺序存储结构上串各种操作的方法。

2

()掌握算法。

3KMP

5.数组与广义表

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

考试要求：

()了解数组的定义，掌握数组的顺序表示和实现。

1

非淡泊无以明志，非宁静无以致远。——诸葛亮

()掌握特殊矩阵、稀疏矩阵压缩存储方式。

2

()了解广义表的概念、表示及存储结构。