2012甘肃专升本计算机科学与技术考试大纲.docx

《2012甘肃专升本计算机科学与技术考试大纲》是针对西北师范大学专升本招生的专业综合课考试，旨在评估学生对计算机科学与技术专业核心课程《数据结构》和《操作系统》的理解程度。以下是对大纲中涉及的主要知识点的详细说明。 **数据结构部分** 1. **数据结构的概念**：数据结构包括逻辑结构（如集合、线性结构、树形结构、图结构）、存储结构（如顺序存储、链式存储）以及对数据的操作。算法是解决问题的步骤，需要进行时间和空间复杂度的分析。算法不同于程序，它更注重逻辑和抽象。 2. **线性表**：包括顺序表和链表。顺序表是元素按线性顺序排列，支持查找、插入和删除等操作。链表分为单链表和双链表，它们在存储表示和操作上有所不同，如单链表只能向前查找，而双链表则可以双向查找。 3. **栈和队列**：栈是一种后进先出（LIFO）的数据结构，通常用于表达式求值和递归。队列是一种先进先出（FIFO）的数据结构，常见于任务调度和数据传输。 4. **树和二叉树**：树是多个节点的非线性结构，二叉树是每个节点最多有两个子节点的特殊树。二叉树有多种遍历方法，如前序遍历、中序遍历和后序遍历，这些遍历方法可用于搜索和构建数据结构。 5. **图**：图是由节点和边构成的非线性结构，有多种表示方法如邻接矩阵、邻接表等。图的遍历、最小生成树、拓扑排序和最短路径等是图论中的重要概念。 6. **查找**：包括顺序查找、折半查找和二叉排序树等。其中，哈希法是一种快速查找方法，通过哈希函数将关键字映射到表中特定位置，处理冲突的方法有拉链法和开地址法。 7. **内排序**：内排序是在内存中完成的排序，包括稳定性、分类、基本思想、算法和复杂度分析。常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序等。 **操作系统部分** 1. **基本概念**：操作系统是管理和控制计算机硬件和软件资源的软件，提供用户接口和系统调用。了解操作系统的分类，如批处理、分时和实时系统。 2. **进程管理和处理器管理**：涉及并发执行、进程状态转换、调度算法（如FCFS、SJF、RR等）、进程同步和互斥（如信号量机制）、死锁及其解决策略。 3. **存储管理**：涵盖虚拟存储器的概念，如页式、段式和段页式管理，以及页面置换算法（如FIFO、LRU等）。 4. **文件管理系统**：文件系统是存储和组织文件的机制，包括文件的逻辑结构、物理结构、存取方法、目录结构和存储空间管理。 5. **设备管理**：涉及I/O设备类型、I/O控制方式（如程序控制、中断控制、DMA、通道）以及磁盘调度算法。 6. **常用操作系统**：Windows和UNIX是两种广泛使用的操作系统，各有其特点和应用领域。 这个考试大纲覆盖了计算机科学与技术的基础知识，包括数据结构的抽象和操作，以及操作系统对资源的管理，是计算机专业学习的重要组成部分。考生需要对这些内容有深入理解和实践能力，才能在考试中取得好成绩。