一、基本内容
l 数据结构部分(占50%)
1.数据类型和数据结构的基本概念
逻辑结构和物理存储结构;数据结构的抽象数据类型表示;数据结构的应用;
2.线性表存储结构及实现
动态数组的空间申请和空间管理;动态数组的声明和实现;
链表的基本结构和创建方式;链表的遍历;链表的插入和删除;链表的归并和拆分;链表应用;
3.栈和队列
栈的基本结构和创建方式;栈的基本属性和基本操作;栈的应用;中缀转后缀算法;后缀表达式计算;
队列的基本结构和创建方式;队列的基本属性和基本操作;队列的应用;
4.双向链表
双向链表的基本结构和创建方式;双向链表的遍历、插入和删除方法;双向链表的应用;
5. 递归算法
递归算法的基本概念和实现方法;数制转换、汉诺塔;
6.二叉树
二叉树的基本概念和表示方法;二叉树的创建、递归遍历方法;二叉树的非递归遍历方法;二叉搜索树的创建、插入、删除方法;二叉平衡树及平衡的调整方法;
7.堆
完全二叉树结构;堆的创建方法、堆调整;堆的插入、删除方法;优先队列概念;堆的应用-优先队列;
|
8.霍夫曼树
编码压缩方法;霍夫曼编码;霍夫曼树创建方法;
9.复杂树结构
2-3-4树创建方法;B树创建、插入和删除方法;
10.查找算法
顺序查找算法及时间复杂度;折半查找算法及时间复杂度;哈希表构造方法(开散列、闭散列);哈希查找算法及冲突解决方法;
11.排序算法
排序算法及时间复杂度(选择排序、交换排序、冒泡排序、插入排序、快速排序、堆排序、归并排序、基数排序);理解算法的最好排序时间、最坏排序时间及平均排序时间;
12.图
图的基本结构(无向图和有向图);图的基本表示方法;图的基本遍历算法(深度、广度遍历)、插入和删除算法;最短路径算法;最小生成树算法;
l 计算机网络部分(占50%)
1. 计算机网络概述
计算机网络的分类,互联网的组成,计算机网络主要性能指标,计算机网络体系结构,OSI体系结构、TCP/IP体系结构。
2. 物理层
物理层特性,数据通信的基础知识,传输媒体,网络交换技术,调制编码技术,信道复用技术,数字传输系统,宽带接入技术。
3. 数据链路层
数据链路层的功能及设计问题,数据链路成帧,透明传输,差错检测,点对点协议PPP,CSMA/CD协议,以太网,透明网桥,扩展的以太网。
4. 网络层
网络层提供的两种服务,网际协议IP,划分子网和构造超网,网际控制报文协议ICMP,互联网路由选择协议,虚拟专用网VPN和网络地址转换NAT。
5. 运输层
进程间通信,运输层的端口,用户数据报协议UDP,传输控制协议TCP,可靠传输的工作原理及TCP可靠传输的实现,TCP流量控制,TCP拥塞控制机制,TCP连接管理。
6. 应用层
域名系统DNS,万维网WWW,电子邮件协议,网络编程基础。
7. 网络安全
数据加密模型,对称密钥密码体制,公开密钥体制,数字签名,鉴别,密钥分配,防火墙与入侵。检测。
|
二、考试要求(包括考试时间、总分、考试方式、题型、分数比例等)
考试时间:180分钟
总分:150分
考试方式:闭卷笔试
题型、分数比例:简答题(约40%)、综合题(约60%)
|
三、主要参考书目
1、数据结构与算法分析-C++语言描述(第2版),Larry Nyhoff著,黄达明等译,清华大学出版社出版, 2006年
2、计算机网络(第7版),谢希仁编著,电子工业出版社,2017.1
3、计算机网络(英文版第5版),Andrew S.Tanenbaum和DJ.Wetherall,机械工业出版社,2011年10月。
|