查字典查字典考研网快讯,据河南工业大学研究生院消息2015年河南工业大学计算机技术考研大纲已发布,详情如下:
830数据结构
【考查目标】
1.理解数据结构的基本概念;掌握数据的逻辑结构、存储结构及其差异,以及各种基本操作的实现。
2.掌握基本的数据处理原理和方法的基础上,能够对算法进行设计与分析。
3.能够选择合适的数据结构和方法进行问题求解。
一、线性表
(一)线性表的定义和基本操作
(二)线性表的实现
1.顺序存储结构
2.链式存储结构
3.线性表的应用
二、栈、队列和数组
(一)栈和队列的基本概念
(二)栈和队列的顺序存储结构
(三)栈和队列的链式存储结构
(四)栈和队列的应用
(五)特殊矩阵的压缩存储
三、树与二叉树
(一)树的概念
(二)二叉树
1.二叉树的定义及其主要特征
2.二叉树的顺序存储结构和链式存储结构
3.二叉树的遍历
4.线索二叉树的基本概念和构造
5.二叉排序树
6.平衡二叉树
(三)树、森林
1.书的存储结构
2.森林与二叉树的转换
3.树和森林的遍历
(四)树的应用
1.等价类问题
2.哈夫曼(Huffman)树和哈夫曼编码
四、图
(一)图的概念
(二)图的存储及基本操作
1.邻接矩阵法
2.邻接表法
(三)图的遍历
1.深度优先搜索
2.广度优先搜索
(四)图的基本应用及其复杂度分析
1.最小(代价)生成树
2.最短路径
3.拓扑排序
4.关键路径
五、查找
(一)查找的基本概念
(二)顺序查找法
(三)折半查找法
(四)B-树
(五)散列(Hash)表及其查找
(六)查找算法的分析及应用
六、内部排序
(一)排序的基本概念
(二)插入排序
1.直接插入排序
2.折半插入排序
(三)气泡排序(bubblesort)
(四)简单选择排序
(五)希尔排序(shellsort)
(六)快速排序
(七)堆排序
(八)二路归并排序(mergesort)
(九)基数排序
(十)各种内部排序算法的比较
(十一)内部排序算法的应用
【知识点解析】
1.线性表
线性表是一种最简单的数据结构,在线性表方面,主要考查线性表的定义和基本操作、线性表的实现。在线性表实现方面,要掌握的是线性表的存储结构,包括顺序存储结构和链式存储结构,特别是链式存储结构,是考查的重点。另外,还要掌握线性表的基本应用。
2.栈、队列和数组
栈和队列是两种特殊的线性表,在这方面,要求我们掌握栈和队列的基本概念,以及他们之间的区别。对于栈和队列的存储结构(包括顺序存储结构、链式存储结构)要有较深的理解,对于栈和队列的应用,例如,排队问题、子程序调用问题、表达式问题等,要搞清楚。
一维数组属于线性表范畴,但多维数组不属于线性表。在这方面,主要掌握数组的存储结构,例如按行优先、按列优先等,某个元素存在的地址是什么。对于特殊矩阵(二维数组)的压缩存储原理也要搞清楚。
3、树与二叉树
二叉树和树是两种不同的概念,这一点是必须要搞清楚的。在这个部分,我们要掌握树的定义、二叉树的定义及主要特征(特殊的二叉树、二叉树的性质)。在二叉树的顺序存储结构和链式存储结构方面,特别是链式存储结构,因为很多应用都是建立在链式存储基础上,例如,二叉树的遍历(前序遍历、中序遍历、后序遍历)就是一种典型的应用。
在特殊的二叉树中,完全二叉树的概念是必须要搞清楚的,其次,线索二叉树的基本概念和构造、二叉排序树、平衡二叉树的基本概念和应用,特别是二叉排序树的基本性质和特点要能很好地理解。
多棵独立的树就组成了森林,树的存储结构和遍历、森林的遍历、树和二叉树的转换、森林和二叉树的转换等知识,也要有了了解。
最后就是树的应用,通常会作为综合应用类试题出现,包括等价类问题、哈夫曼(Huffman)树和哈夫曼编码等。
4、图
在数据结构中,图的结构是最复杂的,这里的概念也是最多的。我们要掌握图的基本概念(有向图、无向图、连通、路径、子图、出度、入度、生成树、最短路径、关键路径等)。
图的存储及基本操作主要有邻接矩阵法和邻接表法,我们要掌握这有向图和无向图的这2种存储方法,要清楚图的连通和存储方法之间的关系。例如,一个顶点的出度和临界矩阵中1的个数有什么关系,等等。
图的遍历方法有深度优先搜索和广度优先搜索,我们要掌握这2种遍历方法的算法实现。给出一个具体的图,要能知道它的遍历次序。
在数据结构课程中,图的基本应用是最多的,也是最复杂的,我们要掌握这些应用的复杂度分析。要掌握的具体应用主要包括最小(代价)生成树、最短路径、拓扑排序、关键路径。在给出的一个具体的图中,我们要会利用已知条件,求出上述应用的结果。
5、查找
在给定的数据集合中查找某个关键值就是查找,查找的基本方法主要有顺序查找法、折半查找法、B-树、散列(Hash)表及其查找。考的比较多的是折半查找和散列表,我们要掌握它们的基本概念和方法,例如散列表的碰撞如何解决,装载因子的概念等。
另外,我们要掌握各种查找算法的分析及应用,最好能把各种查找在查找成功、查找失败的情况下的最好、平均、最坏的平均查找次数的计算方法搞清楚。
6、内部排序
根据考试大纲,只考查内部排序。所谓内部排序,就是在内存中进行排序。在这一部分中,主要要掌握直接插入排序、折半插入排序、冒泡排序(bubblesort)、简单选择排序、希尔排序(shellsort)、快速排序、堆排序、二路归并排序(mergesort)、基数排序的基本概念和方法。搞清楚这些排序方法的流程,以及它们之间的区别。
在这个知识点,一个很重要的考查点就是各种内部排序算法的比较,一般的书上都会有这样的一个表格,列出了所有排序在各种情况下(最好、最坏、平均)的时间复杂度和空间复杂度,这个表是需要我们记下来的。当然,如果我们能掌握复杂度的计算方法,自己能推算出来,那就更好了。
最后,就是要掌握内部排序算法的基本应用,以及算法的实现。
【复习方法】
1、教材的选择
从考试大纲来看,所要求的知识在一般的大学数据结构教材中都已经包含,所以,选择哪本书并不是最重要的事情。不过,根据希赛教育推荐,对于数据结构的复习,可以选择清华大学出版社的《数据结构(第二版)》(严蔚敏主编)。这本书有多种语言的版本,建议选择C语言的版本,在复习的过程中,还可以配以相应的习题集。
2、学习方法
对于数据结构的学习,难在其中的算法及实现。有条件的考生,可以在计算机上编写程序,自己实现教材上的算法(要注意,书上的算法通常都采用伪代码编写,需要我们自己用某种程序设计语言去具体实现)。如果没有条件,那就只有在心里进行推导了,可以使用实际的例子,手工"实现"算法。
859计算机网络
科目名称:计算机网络科目代码:859
一、课程的性质、目的与任务
《计算机网络》是计算机科学与技术、网络工程和软件工程本科专业开设的一门重要基础课,主要介绍计算机网络的基本概念,基本原理和方法。通过本课程的学习,使学生掌握计算机网络的基本概念、基本原理、基本方法,理解网络分层体系结构、网络协议设计原理与工作机理,具备一定的网络设计与分析、网络组建、网络运维管理等网络技术应用能力,以及较好的网络工程素养,为今后从事计算机、数据通信网络等相关领域的技术研发、工程应用等打下良好基础。课程教学强调培养学生的独立思考能力、科学思维方法和求知创新精神。
二、教学内容及基本要求
1计算机网络概论
1.目的和要求:
了解计算机网络的形成与发展;了解计算机网络技术发展三条主线;掌握计算机网络的概念、分类、组成以及结构等;理解分组交换的工作原理;掌握分组交换技术的基本概念。
2.知识点:
(1)计算机网络的形成与发展
计算机网络的形成与发展;宽带城域网与三网融合技术;物联网技术形成与发展;网络安全。
(2)计算机网络定义与分类
计算机网络定义;计算机网络分类。
(3)计算机网络的组成与结构
计算机网络的组成与结构;ISP的层次结构;Internet的网络结构。
(4)计算机网络拓扑结构
计算机网络拓扑的定义、分类及特点。
(5)分组交换技术
数据交换方式(线路交换、分组交换、数据报)的分类、特点及对比;面向连接服务与无连接服务。
3.考核知识点:
计算机网络的定义、分类、组成与结构等概念;线路交换、分组交换和报文交换的概念和工作原理。
2网络体系结构与网络协议
1.目的和要求:
掌握网络分层结构、协议、接口、服务等概念,掌握ISO/OSI参考模型和TCP/IP模型的区别与联系,了解本课程体系与内容。
2.知识点
(1)网络体系结构的基本概念
网络协议、接口与体系结构的基本概念。
(2)OSI参考模型
OSI参考模型的结构;OSI参考模型各层的主要功能;OSI环境中的数据传输过程。
(3)TCP/IP参考模型
TCP/IP参考模型的结构;TCP/IP参考模型各层的功能;OSI参考模型与TCP/IP参考模型的比较。
3.考核知识点:
网络体系结构的基本概念,以及各层的主要功能。服务与协议的概念及二者的区别。
3物理层
1.目的和要求:
掌握物理层的基本概念,数据通信的基础知识,以及模拟传输和数字传输的一些常用技术,掌握信道、信号、码元、波特、编码与调制、等基本概念,了解频带传输技术、基带传输技术、多路复用技术和接入技术。
2.知识点
(1)物理层与物理层协议的基本概念
物理层的基本服务和功能;物理层协议的类型。
(2)数据通信的基本概念
信息、数据与信号等术语;数据通信方式;传输介质的主要类型与特性;数据编码分类。
(3)频带传输技术
模拟数据编码方法;波特率的定义。
(4)基带传输技术
基带传输的定义;数字数据编码方法;比特率的定义;奈奎斯特准则与香农定理
(5)多路复用技术
多路复用的基本概念;时分多路复用;频分多路复用;波分多路复用
3.考核知识点:
物理层的基本概念,数据通信的基础知识,奈奎斯特准则与香农定理,频带传输技术、基带传输技术、多路复用技术。
4数据链路层
1.目的和要求:
掌握数据链路层的基本主要功能,掌握差错产生与差错控制方法;掌握PPP协议的工作原理及其帧结构:了解局域网的分类与特点;掌握介质访问控制方法CSMA/CD的基本原理;掌握Ethernet局域网的基本工作原理;掌握网络互连基本概念与网桥的基本工作原理;了解高速局域网、交换局域网、虚拟局域网和无线局域网的基本工作原理。
2.知识点
(1)数据链路层的基本概念
物理线路与数据链路;数据链路层的主要功能;数据链路层向网络层提供的服务;数据链路层协议的分类。
(2)差错产生与差错控制方法
设计数据链路层的原因;差错产生的原因和差错类型;误码率的定义;检错码与纠错码;循环冗余编码工作原理;差错控制机制。
(3)点-点协议PPP
PPP协议的主要特点;PPP协议帧结构;PPP协议工作过程。
(4)局域网技术的发展与演变
局域网技术的研究与发展;介质访问控制方法CSMA/CD;局域网参考模型与协议标准
(5)Ethernet基本工作原理
Ethernet技术的研究与发展;Ethernet数据发送流程分析;Ethernet帧结构;Ethernet接收流程的分析;Ethernet网卡设计与物理地址;Ethernet物理层标准命名方法。
(6)局域网互联与网桥
局域网互联与网桥的基本概念;网桥的工作流程;生成树协议;网桥与中继器、集线器、交换机的比较。
(7)高速Ethernet
FastEthernet;GigabitEthernet;10GigabitEthernet;40GigabitEthernet与100GigabitEthernet;光以太网与城域以太网。
(8)交换式局域网、虚拟局域网和无线局域网技术
交换式局域网技术;虚拟局域网技术;无线局域网发展背景;无线局域网IEEE802.11标准。
3.考核知识点:
数据链路层中实现链路控制与差错控制的主要方法;PPP协议的工作原理及其帧结构;介质访问控制方法CSMA/CD的基本原理;Ethernet局域网的基本工作原理;网络互连基本概念与网桥的基本工作原理;高速局域网、交换局域网、虚拟局域网和无线局域网的基本工作原理。
5网络层
1.目的和要求:
了解路由器的作用及其工作原理;理解IP协议的作用及IP地址分类;理解ARP协议的作用及其工作原理;重点理解并熟练掌握划分子网和CIDR地址块划分的方法,子网掩码的作用;理解分组转发的流程;理解ICMP协议的作用以及ICMP报文的使用;理解RIP协议、OSPF协议和BGP协议的特点;掌握RIP协议采用距离向量算法更新路由表的过程;了解OSPF报文和BGP报文的使用;
2.知识点:
(1)网络层与IP协议
网络层基本概念;IP协议的发展与演变;IP协议的主要特点。
(2)IPv4协议
IPv4分组格式;IPv4地址的基本概念;标准分类IP地址;划分子网的三级地址结构;无类别域间路由CIDR;网络地址转换NAT。
(3)路由选择协议
路由表的建立、更新与路由选择协议;路由信息协议RIP;最短路径优先协议OSPF;外部网关协议BGP;路由器与第三层交换技术。
(4)Internet控制报文协议--ICMP
ICMP协议的作用与特点;ICMP报文类型;Ping与Traceroute命令。
(5)地址解析协议ARP
IP地址与物理地址的映射;地址解析工作过程。
(6)IPv6协议
IPv6协议的基本概念;IPv6协议的主要特征;IPv6地址;IPv6分组结构与基本报头;IPv4到IPv6过渡的基本方法。
3.考核知识点:
路由器的作用;分类的IP地址;IP地址与硬件地址的关系;ARP协议的工作原理;子网划分和子网掩码的使用,转发分组的流程;CIDR地址块的划分,斜线表示法,最长网络前缀;ICMP报文及其适用情况;路由选择策略的分类,Internet分层路由思想;RIP协议的优缺点及其要点,距离向量算法更新路由表;OSPF协议和BGP协议的要点。
6传输层
1.目的和要求:
了解传输层的作用,掌握传输层与网络层的主要区别,重点理解端口的概念、作用、分类;理解UDP协议的优点,了解TCP协议的特点、TCP报文段的首部字段,掌握TCP控制报文段发送的3种基本机制,理解并掌握TCP的流量控制方法、可靠传输机制以及拥塞控制的4种方法,掌握TCP连接的建立和释放过程。
2.知识点:
(1)传输层和传输层协议
传输层的基本功能;传输协议数据单元的基本概念;应用进程、传输层接口与套接字;网络环境中分布式进程标识方法;传输层的多路复用与多路分解;TCP、UDP协议与应用层协议的关系
(2)用户数据报协议UDP
UDP协议的主要特点;UDP协议报文格式;UDP校验和的基本概念与计算示例;UDP协议适用的范围
(3)传输控制协议TCP
TCP协议的主要特点;TCP协议报文格式;TCP连接建立与释放;TCP协议滑动窗口与确认、重传机制;TCP协议滑动窗口与流量控制、拥塞控制
3.考核知识点:
传输层的作用,传输层与网络层的主要区别;端口的概念、作用、分类;UDP协议的优点;TCP协议的特点、TCP报文段的首部字段;TCP控制报文段发送的3种基本机制;可靠传输机制;TCP的流量控制方法和拥塞控制的4种方法;TCP连接的建立和释放过程。
7应用层
1.目的和要求:
了解应用层提供的服务。重点理解因特网的域名结构和域名解析的工作原理,在此基础上掌握应用层常见几种服务所使用的协议,如HTTP、FTP、SMTP等的工作方式与工作原理;掌握动态主机配置协议DHCP和简单网络管理协议;了解超文本标记语言HTML和应用进程跨越网络的通信。
2.知识点:
(1)Internet应用于应用层协议的分类:
Internet应用技术发展的三个阶段;C/S模式与P2P模式的比较。
(2)域名系统DNS
DNS域名空间;域名服务器;域名解析
(3)远程登录服务与TELNET协议
TELNET协议产生的背景;TELNET协议基本工作原理。
(4)电子邮件服务与SMTP协议
电子邮件服务的基本概念;电子邮件服务的工作过程;POP3、IMAP4协议与基于Web的电子邮件。
(5)Web与基于Web的网络应用
Web服务的基本概念;超文本传输协议HTTP;超文本标记语言HTML;Web浏览器;搜索引擎
(6)主机配置与动态主机配置协议DHCP
动态主机配置的基本概念;DHCP的基本内容
(7)网络管理与简单网管协议SNMP协议
网络管理的基本概念;SNMP协议的基本内容
(8)典型应用层协议--FTP的分析
FTP模型与测试分析环境;FTP控制连接建立过程的分析;FTP用户登录与身份验证过程的分析;FTP数据连接建立过程的协议分析;FTP数据传输过程的分析;FTP用户退出登录过程的分析;FTP连接释放过程的分析
6.考核知识点:
域名结构和域名解析的工作原理;常见服务协议的工作过程,涉及进程、端口概念;区分IP地址静态配置和动态主机配置协议DHCP;超文本标记语言HTML以及基本网页程序设计。
三、课程教材和主要参考资料
1.《计算机网络(第5版)》.谢希仁著.电子工业出版社,2008年
2.《计算机网络(第3版)》.吴功宜编著.清华大学出版社,2011年
3.《计算机网络(第5版)》.AndrewS.Tanenbaum著.清华大学出版社,2012年
4.《计算机网络自顶向下方法(原书第四版)》,JamesF.Kurose,KeithW.Ross著,陈鸣等译,人民邮电出版社,2009
5.《TCP/IP详解卷一:协议》,KevinR.Fall,W.RichardStevents著,机械工业出版社,2012