851计算机基础综合考试大纲.doc

　851计算机基础综合考试大纲 I数据结构 1. 链表、间接寻址和模拟指针 2．数组和矩阵 　　3．堆栈和队列及其应用 　　4．跳表和散列 　　5．二叉树和其他树 　　6．合并/有哪些信誉好的足球投注网站应用，堆和堆排序 　　7．左高树，霍夫曼编码和竞赛树 　　8．有哪些信誉好的足球投注网站树，AVL树或红黑树，直方图 　　9．图 　　10．图和贪婪算法 　　11．货箱装载，0/1背包，最短路径和生成树 　　12．分而治之算法 　　13．动态编程 　　14．回溯和分枝定界算法 　　II操作系统 　　一、导论 　　操作系统的概念 　　计算机系统的操作、存储结构、输入输出结构和计算机系统的体系结构 　　操作系统的结构组成、操作系统的操作及各部分的功能、高速缓冲存储器CACHE 　　操作系统的分类和运行环境 　　二、操作系统结构 　　操作系统提供的服务类型 　　操作系统的用户接口类型 　　系统调用及类型 　　操作系统的设计和实现方法 　　操作系统的结构分类及优缺点 　　虚拟机的基本概念和原理 　　三、进程 　　进程的概念、组织、控制和状态转换 　　进程调度的基本概念 　　进程的操作，包括进程的生成、终止等 　　进程通信 　　四、线程 　　线程的概念与动机 　　多线程模型 　　五、CPU调度 　　调度的基本概念 　　调度的时机、切换和过程 　　调度的基本准则 　　典型调度方法：先来先服务调度算法、最短作业优先调度算法、优先级调度算法、时间片轮转调度算法、多级队列调度算法、多级反馈队列调度算法 　　线程调度 　　调度算法的性能评估 　　六、进程同步 　　进程同步的基本概念 　　临界区访问的原则及实现临界区互斥的基本方法：软件实现方法和硬件实现方法 　　信号量概念与基本机制 　　经典同步问题：生产者－消费者问题、读者－写者问题、哲学家就餐问题和理发师问题。 　　管程的基本概念、原理和实现 　　七、死锁 　　死锁的概念及条件 　　死锁的处理策略 　　死锁的预防及实现方法 　　死锁的避免：系统安全状态、资源分配图算法、银行家算法 　　死锁的检测方法和解除 　　八、主存 　　内存管理的基本概念：程序的装入与链接、逻辑地址与物理地址、内存保护 　　交换技术 　　内存的分配管理方法：连续分配管理方法、分页管理方法、分段管理方法、段页式管理方法。 　　九、虚拟内存 　　虚拟内存的基本概念 　　请求分页管理方法 　　页面置换算法：先进先出置换算法、最佳置换算法、最近最少使用（近似）置换算法、近似最近最少使用置换算法 　　帧的分配策略 　　抖动现象的原因及解决方法 　　内核内存的分配方法 　　虚拟内存中需要考虑的其他问题：预调页、页大小的影响、TLB的有哪些信誉好的足球投注网站能力、逆向页表等 　　十、文件系统接口 　　文件的基本概念 　　文件的结构：顺序文件、索引文件等 　　文件的访问方法 　　目录结构：文件的存储结构、单级目录结构、两级目录结构、树形目录结构、无环图目录结构、通用图目录结构 　　文件共享 　　十一、文件系统实现 　　文件系统的结构 　　文件系统的实现 　　目录的实现 　　文件的磁盘空间分配方法：连续、链式、索引 　　空闲空间的管理 　　十二、大容量存储 　　磁盘的结构 　　磁盘的调度方法：先到先服务调度算法、最短寻道时间调度算法、SCAN调度算法、C－SCAN调度算法、LOOK调度算法、C－LOOK调度算法 　　磁盘管理：格式化、引导块、坏块的处理 　　RAID结构 　　十三、输入/输出系统 　　输入/输出硬件 　　输入/输出访问控制方式 　　输入/输出应用接口 　　内核输入/输出子系统：输入/输出调度、缓存、缓冲、假脱机与设备预留、错误处理、输入/输出保护、内核数据结构 　　输入/输出从请求到硬件操作的转换过程 　　十四、保护 　　保护的目标与原则 　　保护域 　　访问矩阵及实现方法：全局表、访问列表、能力表 　　十五、安全 　　系统中存在的安全问题以及安全措施的级别 　　程序的威胁：木马、后门、逻辑炸弹、栈与缓冲溢出、病毒 　　系统与网络威胁：蠕虫、端口扫描、DoS 　　III计算机组成原理 　　计算机系统概述 　　计算机发展历程 　　计算机系统层次结构 　　计算机硬件的基本组成 　　计算机软件的分类 　　计算机的工作过程 　　计算机性能指标 　　吞吐量、响应时间；CPU时钟周期、主频、CPI、CPU执行时间；MIPS、MFLOPS。 　　数据的表示和运算 　　数制与编码 　　进位计数制及其相互转换 　　真值和机器数 　　BCD码 　　字符与字符串 　　校验码 　　定点数的表示和运算 　　定点数的表示 　　无符号数的表示；有符号数的表示。 　　定点数的运算 　　定点数的位移运算；原码定点数的加/减运算；补码定点数的加/减运算；定点数的乘/除运算；溢出概念和判别方法。 　　浮点数的表示和运算