山东大学

824-计算机基础考试大纲

计算机基础包括数据结构、计算机网络两部分内容，每部分内容各占1/2。

I 数据结构

课程基本要求：

数据结构是在计算机科学中是一门综合性的专业基础课。课程主要内容包括线性表、栈和队列、串、数组和广义表、树和二叉树、图、内排序、文件管理和外排序等。考试的具体要求包括：

1. 全面系统地掌握队列、堆、栈、树、图等基本数据结构，深刻理解和熟练掌握课程中的典型算法;

2. 提高对各种数据结构与算法的程序设计能力，提高对数据结构与算法的实际运用能力。

考试内容：

1. 线性表

1.1. 线性表的类型定义

1.2. 线性表的顺序表示与实现

1.3. 线性表的链式表示与实现

2. 栈和队列

2.1. 栈的定义与实现

2.2. 栈与递归的实现

2.3. 队列的定义与实现

3. 串

3.1. 串的定义与实现

3.2. 串的模式匹配算法

4. 数组和广义表

4.1. 数组的定义与实现

4.2. 矩阵的压缩存储

4.3. 广义表的定义与实现

4.4. 广义表的递归算法

5. 树和二叉树

5.1. 树的定义和基本术语

5.2. 二叉树的定义、性质和存储结构

5.3. 遍历二叉树和线索二叉树

5.4. 树和森林

5.5. 赫夫曼树及其应用

5.6. 回溯法与树的遍历

6. 图

6.1. 图的定义和术语

6.2. 图的存储结构

6.3. 图的遍历

6.4. 最短路径

7. 动态存储管理

7.1. 边界标识法

7.2. 伙伴系统

7.3. 存储紧缩

8. 查找

8.1. 静态查找表

8.2. 动态查找表

8.3. 哈希表

9. 内部排序

9.1. 内部排序算法，插入排序、快速排序、选择排序、归并排序和基数排序等

9.2. 内部排序算法的比较

10. 外部排序

10.1. 外存信息的存取

10.2. 多路平衡归并的实现

10.3. 选择排序

10.4. 最佳归并树

11. 文件

11.1. 有关文件的基本概念

11.2. 顺序文件与索引文件

11.3. 直接存取文件(散列文件)

11.4. 多关键字文件

参考书目：

1. 《数据结构(C语言版)》

作者：严蔚敏，吴伟民

出版社：清华大学出版社

ISBN：9787302023685

2. 《数据结构与算法》

作者：张铭，王腾蛟，赵海燕

出版社：高等教育出版社

ISBN：9787040239614

II 计算机网络

课程基本要求

1. 掌握计算机网络的基本概念、基本原理和基本方法。

2. 掌握计算机网络的体系结构和典型网络协议，了解典型网络的组成和特点，理解典型网络设备的工作原理。

3. 能够运用计算机网络的基本概念、基本原理和基本方法进行网络系统的分析、设计和应用。

考试内容

一、计算机网络体系结构

(一)计算机网络概述

1.计算机网络的概念、组成与功能

2.计算机网络的分类

3.计算机网络的标准化工作及相关组织

(二)计算机网络体系结构与参考模型

1.计算机网络分层结构

2.计算机网络协议、接口、服务等概念

3.ISO/OSI参考模型和TCP/IP模型

二、物理层

(一)通信基础

1.信道、信号、宽带、码元、波特、速率、信源与信宿等基本概念

2.奈奎斯特定理与香农定理

3.编码与调制

4.电路交换、报文交换与分组交换

5.数据报与虚电路

(二)传输介质

1.双绞线、同轴电缆、光纤与无线传输介质

2.物理层接口的特性

(三)物理层设备

1.中继器

2.集线器

三、数据链路层

(一)数据链路层的功能

(二)组帧

(三)差错控制

1.检错编码

2.纠错编码

(四)流量控制与可靠传输机制

1.流量控制、可靠传输与滑动窗口机制

2.停止-等待协议

3.后退N帧协议(GBN)

4.选择重传协议(SR)

(五)介质访问控制

1.信道划分

频分多路复用、时分多路复用、波分多路复用、码分多路复用的概念和基本原理。

2.随机访问

ALOHA协议，CSMA协议，CSMA/CD协议，CSMA/CA协议。

3.轮询访问

令牌传递协议

(六)局域网

1.局域网的基本概念与体系结构

2.以太网与IEEE802.3

3.IEEE802.11

4.令牌环网的基本原理

(七)广域网

1.广域网的基本概念

2.PPP协议

3.HDLC协议

(八)数据链路层设备

1.网桥的概念及其基本原理

2.局域网交换机及其工作原理。

四、网络层

(一)网络层的功能

1.异构网络互连

2.路由与转发

3.拥塞控制

(二)路由算法

1.静态路由与动态路由

2.距离-向量路由算法

3.链路状态路由算法

4.层次路由

(三)IPv4

1.IPv4分组

2.IPv4地址与NAT

3.子网划分、路由聚集、子网掩码与CIDR

4.ARP协议、DHCP协议与ICMP协议

(四)IPv6

1.IPv6的主要特点

2.IPv6地址

(五)路由协议

1.自治系统

2.域内路由与域间路由

3.RIP路由协议

4.OSPF路由协议

5.BGP路由协议

(六)IP组播

1.组播的概念

2.IP组播地址

(七)移动IP

1.移动IP的概念

2.移动IP通信过程

(八)网络层设备

1.路由器的组成和功能

2.路由表与路由转发

五、传输层

(一)传输层提供的服务

1.传输层的功能

2.传输层寻址与端口

3.无连接服务与面向连接服务

(二)UDP协议

1.UDP数据报

2.UDP校验

(三)TCP协议

1.TCP段

2.TCP连接管理

3.TCP可靠传输

4.TCP流量控制与拥塞控制

六、应用层

(一)网络应用模型

1.客户/服务器模型

2.P2P模型

(二)DNS系统

1.层次域名空间

2.域名服务器

3.域名解析过程

(三)FTP

1.FTP协议的工作原理

2.控制连接与数据连接

(四)电子邮件

1.电子邮件系统的组成结构

2.电子邮件格式与MIME

3.SMTP协议与POP3协议

(五)WWW

1.WWW的概念与组成结构

2.HTTP协议

参考书目

1. 《计算机网络(第7版)》，谢希仁 著，电子工业出版社

2. 《计算机网络：自顶向下方法(原书第7版)》，(美)詹姆斯·F. 库罗斯(James F. Kurose);(美)基思·W. 罗斯(Keith W. Ross)著，陈鸣 译，机械工业出版社