甘肃政法学院专升本考试计算机专业课考试大纲

　　一、参考书目

　　⒈《操作系统基础》(第三版)，屠祁、屠立德等编著，清华大学出版社出版。

　　⒉《实用数据结构基础》，陈明编著，清华大学出版社出版。

　　二、考试内容

　　㈠操作系统

　　⒈基本概念

　　操作系统、多道程序设计、多道批处理操作系统、分时系统、实时系统、网络操作系统、分布式操作系统、重定位、微程序设计、进程、线程、临界段、信号量、同步、互斥、管程、死锁、微内核。

　　⒉基本知识

　　①缓冲技术、中断技术、操作系统与其他系统软件的关系、操作系统的接口功能。

　　②进程管理：进程的描述、进程的状态、进程的控制，进程的调度、进程间的通信，进程的同步和互斥，线程的状态和线程管理，多线程的实现，管程，UNIXSVR4的进程管理、进程同步和通信。

　　③处理器管理：多处理系统、对称式多处理系统，作业调度和调度层次，单处理系统的处理器调度算法。

　　④死锁：死锁的条件、预防，死锁的避免和银行家算法，死锁的检测与恢复。

　　⑤主存储器管理：固定分区、可变分区多道管理技术，分页、分段、内核主存管理。

　　⑥虚拟存领储管理：分页存储管理、分段存储管理、段页式存储管理、页的置换算法、页架的分配策略，主存共享、快表一致性问题。

　　⑦设备管理：I/O子系统的层次模型、I/O硬件组成，设备驱动程序、I/O子系统、流，磁盘调度，虚拟设备和SPOOL系统。

　　⑧文件系统：文件、目录，文件系统的实现，文件的安全性和保护。

　　⒊扩展知识

　　分布式操作系统的特点、分布式操作系统的进程通信，微内核结构、操作系统的设计、操作系统的结构。

　　㈡数据结构

　　⒈基本概念

　　数据结构、基本术语、线性表、栈、队列、串、递归、数组、广义表、树、二叉树、图。

　　⒉基本知识

　　①数据的逻辑结构和存储结构，数据的运算，算法的描述和分析。

　　②线性表的顺序存储和运算，线性表的链式存储，线性链表及运算、循环链表及运算、双向链表及运算、链式存储结构的应用。

　　③栈的顺序存储、栈的链式存储，栈的应用(算术表达式求值)，队列的顺序存储、队列的链式存储，队列的应用。

　　④递归问题及实现，递归转化为非递归的一般过程。

　　⑤串的静态存储结构、串的动态存储结构，串的基本运算，实现串的基本运算的算法，模式匹配。

　　⑥数组的基本操作、数组的顺序存储结构。

　　⑦树的表示形式、树的常用术语、树的基本操作，二叉树的性质、二叉树的存储结构、二叉的遍历及应用，森林与二叉树的转换，哈夫曼树的定义及构造。

　　⑧图的遍历，生成树(普里姆算法)，最短路径，关键路径。

　　⑨线性表的查找，二叉查找树，哈希表及基本构造方法。

　　⑩插入排序、冒泡排序、快速排序、选择排序、归并排序、基数排序。

　　⒊扩展知识

　　文件的组织，顺序文件、索引文件、散列文件。

　　三、试题满分为200分，考试时间为150分钟。