2020年国防科技大学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）掌握在各种链式结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。
（4）能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
（5）了解线性表在一元多项式相加中的应用。
3．栈和队列
考试内容：栈的定义、表示和实现，队列的定义、表示和实现，栈的应用，栈与递归的实现。
考试要求：
（1）了解栈和队列的定义、特性，并能正确应用它们解决实际问题。
（2）掌握栈的顺序表示、链式表示以及相应操作的实现。注意栈空和栈满的条件。
（3）掌握队列的顺序表示、链式表示以及相应操作的实现。注意循环队列中队头与队尾指针的变化情况。
（4）了解栈与递归的实现。
4．串
考试内容：串的类型定义，串的表示和实现，串的模式匹配算法。
考试要求：
（1）了解串的定义、基本操作。
（2）掌握顺序存储结构上串各种操作的方法。
（3）掌握KMP算法。
5．数组与广义表
考试内容：数组，稀疏矩阵，数组的顺序表示，压缩存储，广义表。
考试要求：
（1）了解数组的定义，掌握数组的顺序表示和实现。
（2）掌握特殊矩阵、稀疏矩阵压缩存储方式。
（3）了解广义表的概念、表示及存储结构。
6．树和二叉树
考试内容：二叉树与树，二叉树性质，二叉树与树的存储结构，二叉树的遍历和线索化，森林与二叉树的转换，赫夫曼树及其应用。
考试要求：
（1）了解树和二叉树的定义和性质。
（2）掌握二叉树的结构特性、存储结构及适用范围、遍历算法。
（3）掌握树存储结构及其特点、树、森林与二叉树的转换方法。
（4）掌握建立赫夫曼树和赫夫曼编码的方法及带权路径长度的计算。
7．图
考试内容：图的定义和存储结构、图的遍历、图的连通性问题、拓扑排序、关键路径、最短路径。
考试要求：
（1）理解图的基本概念，熟悉图的各种存储结构及其构造算法。
（2）掌握图的深度优先和广度优先两种路径遍历算法。
（3）了解AOV网络、AOE网络。
（4）掌握拓扑排序和关键路径算法。
（5）掌握kruskul和prim算法构造最小生成树算法。
（6）掌握Dijkstra算法求解单源最短路径，理解floyd算法求多源顶点间最短路径问题。
7．查找
考试内容：顺序表、有序表的查找，二叉排序树和平衡二叉树，哈希表的构造方法和处理冲突的方法。
考试要求：
（1）掌握顺序表和有序表的查找算法及其性能分析方法。
（2）掌握二叉排序树的构造和查找算法及其性能分析方法。
（3）理解AVL树的维护平衡方法。
（4）理解B_树、B+的特点、查找及构造方法。
（5）掌握哈希函数的构造及解决冲突的方法。
8．查找
考试内容：插入排序，快速排序，选择排序，归并排序，基数排序。
考试要求：
（1）掌握排序的基本概念和各种排序方法的特点，并能加以灵活应用。
（2）掌握插入排序、交换排序、选择排序、归并排序的方法及其性能分析方法。
（3）了解基数排序方法及其性能分析方法。
（二）计算机网络
1．计算机网络体系结构
考试内容：计算机网络的概念、组成与功能，计算机网络的分类，因特网的组成，计算机网络的性能，计算机网络体系结构与参考模型。
考试要求：
（1）掌握计算机网络的基本概念、组成和基本功能；掌握因特网边缘和电路交换、报文交换与分组交换等因特网核心的基本概念；掌握衡量网络性能的速率、带宽、时延、时延带宽积、往返时间RTT、吞吐量等概念；掌握网络协议分层的基本原理和方法，计算机网络协议、实体、接口和服务等概念；掌握TCP/IP协议的体系结构；掌握客户/服务器、P2P等典型的网络应用模型。
（2）理解计算机网络的分类方法和标准；理解计算机网络的标准化工作及相关组织机构的特点和职能范围；理解因特网的标准化工作过程。
（3）了解计算机网络与因特网的发展历程和发展趋势；了解网络协议的ISO/OSI参考模型。
2．物理层
考试内容：数据通信的基础知识，物理层下面的传输媒体，信道复用技术，数字传输系统，宽带接入技术。
考试要求：
（1）掌握物理层的基本概念、数据通信系统模型、信道和信道容量等基础知识；掌握频分复用、时分复用、码分复用等信道复用技术的基本原理；掌握ADSL、HFC和FTTx等宽带接入技术的基本原理和实现方法。
（2）理解导引型和非导引型各类传输媒体的特点和应用场合；理解奈奎斯特定理与香农定理的基本内容；理解信道编码与调制的基本概念；理解统计时分复用的原理和基本实现方法；理解中继器、集线器等典型物理层设备的工作原理和应用场合。
（3）了解光的波分复用技术；了解SDH和SONET等数字传输系统。
3．数据链路层
考试内容：使用点对点信道的数据链路层和点对点协议PPP，使用广播信道的数据链路层，以太网和CSMA/CD协议，无线局域网WLAN协议，高速以太网。
考试要求：
（1）掌握数据链路和帧的基本概念，数据链路层要解决的封装成帧、透明传输、差错检测三个基本问题；掌握PPP协议的特点、帧格式和工作状态；掌握CSMA/CD协议的基本内容和使用方式；掌握在物理层和链路层扩展以太网的原理和方法；掌握局域网交换机的工作原理和使用方法。
（2）理解以太网MAC层的基本内涵；理解网桥的概念和基本原理；理解无线局域网WLAN协议IEEE 802.11的工作原理和实现方法；理解100BASE-T、吉比特和10吉比特以太网的实现原理和方法；理解使用以太网进行宽带接入的方法。
（3）了解以太网信道利用率的分析和计算方法。
4．网络层
考试内容：网络层提供的服务，IP地址与IP协议，划分子网和构造超网，网际控制报文协议ICMP协议，因特网的路由选择协议；IP多播，虚拟专用网VPN和网络地址转换NAT。
考试要求：
（1）掌握网络层提供的虚电路和数据报服务的基本原理和方法，虚拟互连网络的概念；掌握IP地址、物理地址的概念，地址解析协议ARP作用、工作原理和实现方法；掌握IP层转发分组的基本流程；掌握子网掩码的概念和划分子网的方法、使用子网时分组转发的方法、使用无分类编址CIDR构造超网的原理和方法；掌握网际控制报文协议ICMP的作用、报文的种类和应用场合；掌握静态路由与动态路由的基本概念，内部网关协议RIP、OSPF和外部网关协议BGP等典型因特网路由选择协议的工作原理和应用场合，自治系统的基本概念；掌握虚拟专用网VPN和网络地址转换NAT的基本原理和实现方法。
（2）理解IP数据报的格式及各协议字段的含义；理解地址聚合的概念和作用；理解典型路由器的基本构成部件；理解IP多播的概念、在局域网上进行硬件多播的实现方法、网际组管理协议IGMP和多播路由选择协议的工作原理和实现方法。
（3）了解IPv6的主要特点和各协议字段的含义；了解移动IP的概念和移动IP的通信过程。
5．运输层
考试内容：运输层协议的概念，用户数据报协议UDP，可靠传输的工作原理，传输控制协议TCP的特点、TCP报文段的首部格式和TCP可靠传输的实现方法，TCP的流量控制和拥塞控制，TCP的运输连接管理。
考试要求：
（1）掌握进程间通信的概念、运输层端口的作用和意义；掌握UDP协议的特点、首部格式和应用场合；掌握TCP协议的特点和TCP连接的概念，停止等待协议、连续ARQ协议等可靠传输协议的工作原理；掌握TCP报文段首部各字段的含义和作用，TCP协议实现可靠传输的滑动窗口、字节编号、确认、超时重传等基本机制；掌握拥塞控制的一般原理、TCP协议实现拥塞控制的方法。
（2）理解选择确认SACK的实现方法；理解TCP协议实现流量控制的方法；理解利用随机早期检测RED实现TCP拥塞控制的原理；理解TCP连接的建立、释放等TCP运输连接管理的实现方法。
（3）了解影响TCP效率和TCP连接吞吐量的各类因素和TCP连接吞吐量的基本计算方法；了解TCP协议有限状态机。
6．应用层
考试内容：域名系统DNS，文件传输协议FTP，远程终端协议TELNET，万维网WWW，电子邮件，动态主机配置协议DHCP，简单网络管理协议SNMP，应用进程跨越网络的通信。
考试要求：
（1）掌握域名系统的基本概念、因特网的域名结构、域名服务器概念和作用、域名查询的过程；掌握FTP协议的概念和FTP的基本工作原理；掌握万维网的基本概念，统一资源定位符URL的作用，超文本传送协议HTTP的工作原理和实现方法，万维网文档、信息检索系统和微博的概念；掌握电子邮件的概念，简单邮件传送协议SMTP的工作原理，电子邮件的信息格式，邮件读取协议POP3和IMAP的作用和工作原理，基于万维网实现电子邮件的方法，通用因特网邮件扩充MIME的实现方法；掌握DHCP协议的作用和工作原理；掌握网络管理的基本概念和SNMP协议的实现方法。
（2）理解简单文件传送协议TFTP的工作原理；理解系统调用和应用编程接口的概念。
（3）了解TELNET协议的作用和基本工作原理；了解SNMP的协议数据单元和报文；了解常用的系统调用。
三、试卷结构（满分150分，时间180分钟）
按题型：
|
内 容
|
选择题
|
填空题
|
简答题
|
计算题
|
综合题
|
|
数据结构
|
20分
|
20分
|
0分
|
35分
|
|
计算机网络
|
40分
|
35分
|
按章节内容，数据结构75分，计算机网络75分，具体如下：
|
内 容
|
分 值
|
|
数据
结构
|
绪论
|
5
|
| 线性表、栈、队列
|
20
|
| 串、数组、广义表
|
10
|
| 树和二叉树
|
15
|
| 图
|
15
|
| 查找与排序
|
10
|
|
计算机网络
|
计算机网络体系结构
|
5
|
| 物理层
|
5
|
| 数据链路层
|
10
|
| 网络层
|
25
|
| 运输层
|
20
|
| 应用层
|
10
|
