836 计算机学科基础

一、考试目标

计算机学科基础综合考试涵盖数据结构、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。

二、考试形式

闭卷、笔试。满分为150分，考试时间为180分钟。

三、试卷结构

判断题、名词解释、简答题、综合题

四、考试内容

（一）数据结构（60分）

　1、线性表和链表
  线性表、单向链表、双向链表、循环链表。
 2、栈和队列
  栈和队列的逻辑结构、存储结构，栈和队列的应用。
 3、树和二叉树
  树的基本概念和术语、二叉树的定义、遍历二叉树。
 4、图
  图的定义和术语、图的存储结构、图的遍历算法。
 5、查找
  顺序查找、二分查找、哈希表。
 6、内部排序
 折半插入算法、希尔排序、冒泡排序、快速排序、直接选择排序的基本思想和实现算法。 （二）操作系统（60分）

　　1、进程管理

典型调度算法设计及应用（先来先服务、短作业优先、优先级调度、高响应比优先调度）、利用PV操作解决同步和互斥，利用银行家算法给出避免死锁的资源分配方案

　 2、内存管理

分页/分段地址变换，页面淘汰算法设计实现及应用，请求分页/分段地址变换，动态分区存储管理设计与实现

　　3、文件管理

文件及典型存取操作逻辑流程、文件目录结构及管理

　　4、输入输出(I／O)管理

设备驱动及中断处理、缓冲管理、磁盘数据访问过程及时间开销

（三）计算机网络（30分）

计算机网络体系结构

协议的概念、OSI/RM七层模型、TCP/IP参考模型2、物理层与、数据链路层

物理层与数据链路层的基本概念、有关数据通信的基本概念（单工通信，半双工通信，全双工通信，基带信号，宽带信号，波特与比特）、网络适配器与帧的概念

　　3、网络层与传输层

IP地址的分类以及IP地址与物理地址之间的关系、传输层协议（TCP）的作用、两种传输层协议TCP与UDP的特点，以及各自所适合的应用

　5、应用层

C/S结构的基本概念、域名系统的基本功能、HTTP协议的操作过程