北航计算机专业课-复习大纲
461 计算机专业技术基础 复习大纲
《计算机专业技术基础》共包括三门课程的内容：数据结构、计算机组成原理和操作系统，各占50分，总分150分。
《数据结构》部分
第一章 绪论
什么是结构？什么是数据的逻辑结构与存储结构？通常二者之间应有何联系？
顺序存储结构与链式存储结构的构造原理分别是什么？
什么是算法？一个完整的算法应该具有那些特征？算法与程序有何区别？
算法正确是什么含义？算法分析是指什么？通常从哪几个方面对一个算法进行分析？
第二章 线性表
1．什么是线性关系？线性表的基本操作有哪些？其中最基本与最重要的操作有哪些？
2．线性表的顺序存储结构的构造原理是什么？线性表的顺序存储结构的特点(优点与缺点)是什么？
3．在线性表的顺序存储结构下如何计算一个数据元素的存储位置？
4．掌握线性表在顺序存储结构下插入一个数据元素与删除一个数据元素的算法设计。
5．线性表的链式存储结构的构造原理是什么？（线性链表、循环链表、双向链表）
6．掌握线性表在各种链式存储结构下的链表建立、插入、删除等算法的设计。
第三章 数组
1．数组是一种什么样的线性结构？其基本操作有哪些？
2．数组的存储方法。
3．矩阵的压缩存储是什么含义？熟悉对称矩阵、三对角矩阵和稀疏矩阵的压缩存储方法。(稀疏矩阵的十字链表方法知道即可)
第四章 堆栈和队列
1．堆栈与队列分别是一种什么样的结构？堆栈与队列的基本操作有哪些？
2．堆栈与队列的顺序存储结构和链式存储结构的构造原理是什么？重点掌握在不同的存储结构下往堆栈和队列中插入一个新的元素，和删除堆栈和队列中一个元素的过程；掌握堆栈与队列在各种存储结构下插入和删除操作对应的算法设计。
3．了解堆栈和队列在解决实际问题过程中的具体应用。（如递归问题的解决）
第七章 树与二叉树
1．树型结构的基本特征是什么？从逻辑上看，树型结构有何特点？
2．记住树型结构中常用的名词术语的含具体义(如：结点的度、树的度、叶结点、分支结点、层次的定义、深度的定义、树的有序性概念)。
3．掌握二叉树的基本概念，从概念上了解二叉树与一般树的区别。
4．什么是满二叉树与完全二叉树？二者有和关系？
5．二叉树有哪些基本性质？记住结论，尽可能了解结论的证明或推导过程。
6．掌握二叉树的顺序存储结构与链式存储结构(二叉链表)的构造原理，后者作为重点。
7．什么是二叉树的遍历操作？通常有哪几种常用的遍历方法？掌握各种遍历方法的基本原理和遍历过程。
8．以中序遍历为例，掌握二叉树遍历操作对应的非递归算法的设计方法。
9．掌握由遍历序列恢复二叉树的基本方法。即掌握由给出的包括中序序列在内的两种序列，求第三种序列的方法。
10．什么是二叉排序树？二叉排序树有何特点？
11．掌握由给出的数据元素序列建立二叉排序树的二叉链表的“逐点插入法”的基本原理，包括非递归算法的设计。
12．如何利用二叉排序树将一个按值任意的数据元素序列转换为按值有序的数据元素序列。
13．掌握在二叉排序树中查找一个结点的过程。
第八章 图
1．图结构的基本特征是什么？从逻辑上看，图结构有何特点？
2．掌握图结构中常用的名词术语的具体含义，包括：顶点的度以及相关结论、路径、路径长度、子图、图的连通和生成树的概念与特点。
3．掌握图邻接矩阵和邻接表存储方法的构造原理。邻接矩阵和邻接表各有什么特点？
4．了解图的遍历的基本概念、遍历方法以及遍历过程。
5．什么是最小生成树？最小生成树有何特点？
6．掌握当给定一个图(以定义的方式、或以存储结构的方式、或给出邻接矩阵的三元组表形式)时，如何求出图的最小生成树或者指定源点到图中其他各顶点的最短路径。
第九章 文件及查找
1．数据文件的基本操作有哪些？其中最基本和重要的操作是什么？
2．什么数据文件是顺序文件？什么是排序顺序文件与一般顺序文件？划分的原则是什么？什么是连续顺序文件与链接顺序文件？划分的根据是什么？什么是排序连续顺序文件？它有什么特点？
3．掌握连续顺序文件的顺序查找方法的查找原理和查找过程。掌握排序连续顺序文件的折半查找方法的查找原理和查找过程，包括非递归算法的设计。
4．索引文件由哪几部分组成？其中索引表有何特点？
5．了解在稠密索引文件与非稠密索引分块文件中查找一个记录存在与否的过程。
6．哈希(Hash)文件有和特点？建立哈希文件的步骤是什么？掌握在哈希文件中查找一个记录的过程。
7．何谓哈希(Hash)冲突？处理哈希冲突的常用方法有哪几种？
第十章 内排序
1．重点掌握插入排序法、选择排序法、泡排序法、谢尔排序法、快速排序法和堆积排序法等各种排序方法的排序原理和排序过程。包括了解各种方法的排序趟数排序与过程中所进行的元素之间的比较次数的特点。
2．了解插入排序法、选择排序法(包括折半插入排序法)、泡排序法等简单排序算法的设计。
3．什么是堆积？堆积有何特点？
《计算机组成原理》部分
要求掌握的内容：
运算器及运算方法
运算器的基本结构
加（减）法及其实现
乘法运算及其逻辑实现
浮点数的运算规则
运算器性能指标
存储系统
主存储器组成与工作原理，包括：存储单元电路及其工作原理、存储芯片结构及其工作原理、存储器的扩展方式、动态存储器的刷新。
高速缓冲存储器的组成、结构和工作原理，包括：高速缓冲存储器的功能和工作原理、高速缓冲存储器的结构、地址映射方式。
虚拟存储系统的工作原理，包括：虚拟存储系统的基本概念、页式虚拟存储系统的工作原理。
磁盘存储器的结构、访问特征和性能参数计算。
指令系统
指令格式；
寻址方式；
指令系统的设计。
CPU
CPU的功能与结构
控制方式、指令周期
指令执行过程、指令执行微操作流程分析
微程序原理、微指令格式、微程序控制器设计
输入输出技术及输入输出汇编语言程序设计（16学时）
总线分类、总线的控制方式（仲裁方式）
中断响应与中断处理
DMA输入输出方式的工作原理
《操作系统》部分
要求掌握的内容：
第一章 概述了操作系统的形成、类型、特征和功能等。要求掌握操作系统的基本概念。
第二章、第三章和第四章 讲述了进程、进程同步和通信、进程调度和死锁等基本概念和相关算法。这是操作系统的核心，要求清楚理解进程等基本概念，熟练掌握各种算法。
第五章和第六章 介绍存储器管理，包括重定位和虚拟存储器等基本概念，分区、分页、分段以及段页式存储管理。这一章是操作系统的重点，要求清楚理解基本概念，熟练掌握各种分配算法。
第七章 介绍I/O设备管理、调度、分配机制。要求掌握I/O管理的基本概念。
第八章 讲述了文件系统，包括文件的组织方式、目录结构、存取控制。要求清楚理解文件系统的基本概念。
第九章 介绍磁盘存储器管理，包括磁盘扫描算法、外存分配方法、空闲存储空间管理等方面。要求清楚理解基本概念，熟练掌握各种分配算法。
第十章 介绍了操作系统和用户之间的接口。要求掌握作业管理的基本概念和接口种类。
精彩内容载入中...
搜索更多相关主题的帖子:
北航 计算机 专业课 大纲
