|
|
|
|
友情提示：本站提供全国400多所高等院校招收硕士、博士研究生入学考试历年考研真题、考博真题、答案，部分学校更新至2012年，2013年；均提供收费下载。 下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载
824 计算机专业基础 A 研究生入学考试大纲-南京理工大学
离散数学部分：
1 命题演算基础
1．1 命题与联结词
①命题 ②联结词 ③合式公式 ④命题的符号化
1.2 真假性
①解释 ②等价公式 ③联结词的完备集 ④对偶式和内否式。
1.3 范式及其应用
①范式 ②主范式
2 命题演算的推理理论
2.1 命题演算的公理系统
①公理系统的组成部分 ②公理系统的推理过程
2.2 命题演算的假设推理系统
①假设推理系统的组成 ②假设推理系统的推理过程
2.3 命题演算的归结推理法
①归结证明过程②归结证明方法
3 谓词演算基础
3.1 谓词和个体
①个体 ②谓词 ③语句的符号化
3.2 函数和量词
①函数项 ②量词
3.4 永真性和可满足性
①真假性 ②同真假性 ③永真性和可满足性 ④范式
4 谓词演算的推理理论
4.1 谓词演算的永真公理系统
①公理系统的组成部分 ②公理系统的推理过程
4.2 谓词演算的假设推理系统
①假设推理系统的组成及证明方法 ②定理的推导过程
4.3 谓词演算的归结系统
①置换 ②归结反演系统 ③霍恩子句逻辑程序
5 递归函数论
5.1 数论函数和数论谓词
5.2 函数的构造
6 集合
6．1 集合的基本概念
①集合；②子集合；③空集合；④集合的相等。
6．2 集合的基本运算
①集合的运算；②集合的交；③集合的并；④集合的差；⑤集合的对称差；⑥集合的广义交；
⑦集合的广义并；⑧幂集合。
6．3 全集和集合的补
①全集；②集合的补；③德·摩根定律。
6．4 自然数与自然数集
①自然数；②自然数集；③数学归纳法；④集合的归纳定义。
6．5 包含与排斥原理
①有限集；②包含与排斥原理。
7 关系
7．1 集合的笛卡尔积集
①有序对；②集合的笛卡尔积集；③有序 n(n 2)元组；④n 重(n 2)笛卡尔积集。
7．2 二元关系的基本概念
①二元关系；②二元关系的表示；③二元关系的图形表示；④二元关系的矩表示；⑤二元关
系的运算；⑥二元关系的复合运算；⑦二元关系的逆关系。
7．3 二元关系的性质
①二元关系的性质；②自反的二元关系；③反自反的二元关系 ；④对称的二元关系；⑤反
对称的二元关系；⑥传递的二元关系。
7．4 二元关系的闭包运算
①二元关系的闭包运算；②自反闭包；③对称闭包；④传递闭包。
7．5 等价关系与集合的划分
①等价关系；②等价类；③集合的划分；④商集合。
7．6 偏序关系和格
①偏序关系；②偏序集；③极大元；④极小元；⑤最大元；⑥最小元； ⑦最小上界；⑧最
大下界；⑨可比；⑩覆盖；⑾有序集；⑿良序集；⒀格。
8 函数与集合的势
8．1 函数的基本概念
①函数（映射）；②定义域；③陪域；④值域；⑤象集；⑥原象集；⑦单射函数；⑧满射函
数；⑨双射函数。
8．2 函数的复合与可逆函数
①函数的复合；②左可逆函数；③右可逆函数；④可逆函数。
8．3 无限集
①集合的势；②无限集；③集合的势相等；④可数无限集；⑤不可数无限集； ⑥集合势大
小的比较。
9 图论
9．1 图的基本概念
①有向图；②无向图；③顶点集；④边集；⑤自环；⑥孤立点；⑦多重边；⑧简单图；⑨完
全图；⑩关联；⑾邻接；⑿图的同构；⒀子图；⒁生成子图；⒂补图；⒃图的顶点度数（次
数）；⒄图的顶点度数和与边数关系。
9．2 图中的通路、图的连通性与图的矩阵表示
①图中的通路；②简单通路；③初等通路；④回路；⑤简单回路；⑥初等回路（圈）；⑦连
通图；⑧有向连通图；⑨有向单侧连通图；⑩有向强连通图；⑾ 图的邻接矩阵；⑿图的关
联矩阵；⒀图的可达矩阵。
9．3 带权图与带权图中最短通路
①带权图；②带权图的最短通路；③狄克斯瑞（Dijkstra）算法。
9．4 欧拉图
①欧拉图；②欧拉通路；③欧拉回路；④欧拉定理。
9．5 哈密尔顿图与货郎担问题
①哈密尔顿通路；②哈密尔顿回路（圈）；③哈密尔顿图；④哈密尔顿图的必要条件；⑤哈
密尔顿图的充分条件；⑥货郎担问题；⑦最邻近算法。
9．6 二部图
①二部图（偶图）；②二部图的充要条件；③二部图的匹配；④二部图的极大匹配；⑤二部
图的完美匹配。
9．7 平面图
①平面图；②平面图的欧拉定理；③平面图的必要条件；④平面图的区域着色。
10 树
10．1 树的基本概念
①树；②树中顶点与边关系公式；③树的等价定义。
10．2 连通图的生成树与带权图的最小生成树
①连通图的生成树；②割集；③割集与生成树的关系；④带权图最小生成树的算法。
10．3 有序树
①有向树；②根树；③有序树；④有序 n (n 2)分树；⑤正则有序 n (n 2) 分树。
10．4 前缀码和最优二分树
①前缀码；②带权图的最优二分树；③霍夫曼（Huffman）算法。
11 群和环
11．1 代数运算的基本概念
①二元运算；②封闭的二元运算；③可结合的二元运算；④可交换的二元运算；⑤n 元运算
11．2 代数系统和半群
①代数系统；②左么元；③右么元；④么元；⑤半群；⑥含么半群（独异点）；⑦半群的同
态；⑧子半群；⑨子含么半群。
11．3 群的基本概念
①左逆元；②右逆元；③逆元；④群；⑤有限群；⑥交换群；⑦群同态；⑧群同构；⑨群中
元素的阶。
11．4 变换群和置换群
①变换含么半群；②变换群；③置换群；④n 个文字对称群。
11．5 循环群
①循环群。
11．6 子群、群的子集生成的群
①子群。
11．7 子群的陪集
①子群的陪集；②子群在群中的指数；③群中拉格朗日定理。
11．8 正规子群、商群、群同态
①正规子群；②商群；③群的同态基本定理。
主要参考教材：朱保平,叶有培,张琨.离散数学(第 2 版).北京：北京理
工大学出版社，2014
数据结构部分：
一、课程的地位与作用
《数据结构》课程是计算机专业的核心课程之一，是一门综合性的专业基础课，它介于数
学，计算机硬件，计算机软件之间。是高级程序设计语言，编译原理，操作系统，数据库，人
工智能等课程的基础。同时，数据结构的技术也广泛应用于信息科学、系统工程，应用数学，
以及各种工程技术领域。
二、课程的教学目标与基本要求
课程目的是使学生了解计算机应用中数据对象的特性，学会在应用中, 根据现实世界中的
问题选择适当的数据逻辑结构和存储结构以及相应算法, 并且培养基本的、良好的程序设计技
能。
三、课程内容（重点△，难点★）
1 绪论
1．1 数据结构的有关概念
1．2 数据结构发展概况
1．3△关于算法及算法的分析
1．3．1 算法
1．3．2 算法设计要求
1．3．3 ★时间复杂度
2 线性表
2. 1 线性表的逻辑结构
2. 2 △线性表的顺序存储结构及运算实现
2. 3 △线性表的链式存储结构及运算
2. 3. 1 线性链表
2. 3. 2 循环链表
2. 3. 3 双向链表
2. 3. 4 静态链表
2. 4 ★一元多项式的表示及相加
3 栈和队列
3．1 栈的定义及运算
3．2 △栈的存储结构及运算实现
3．3 栈应用举例
3．4 队的定义及运算
3．5 △队的存储结构及运算实现
3．5．1 队的链式存储和运算
3．5．2 循环队---队的顺序存储和运算
4 数组
4．1 数组的定义
4．2 ★稀疏矩阵的三元组表示及有关算法
4．3 稀疏矩阵的十字链表表示及相加
5 树和二叉树
5．1 树的定义及有关术语
5．2 △二叉树
5．2．1 二叉树的定义
5．2．2 二叉树的性质
5．2．3 二叉树的存储结构
5．3 △二叉树的遍历算法及线索二叉树
5．3．1 二叉树的遍历
5．3．2 ★线索二叉树
5．4 树和森林
5．4．1 树的存储结构
5．4．2 森林与二叉树的转换
5．4．3 树和森林的遍历
5．5 哈夫曼树及其应用
5．5．1 哈夫曼树
5．5．2 哈夫曼编码
6 图
6．1 图的定义及逻辑结构、存储方法
6．2 △图的遍历算法
6．2．1 图的深度优先搜索
6．2．2 图的广度优先搜索
6．3 △无向图的连通性
6．3．1 无向图的连通分量
6．3．2 无向图的生成树
6．3．3 ★最小生成树
6．4 △有向无环图及其应用
6．4．1 拓扑排序;
6．4．2 ★关键路径
6．5 △★单源点最短路径
7 查找
7．1 △静态查找表
7．1．1 顺序表的查找
7．1．2 有序表的折半查找
7．1．3 索引顺序表的查找
7．2 △动态查找表
7．2．1 二叉排序树
7．2．2 ★平衡二叉树
7．2．3 ★B-树
7．3 △哈希表
7. 3. 1 哈希表的定义
7. 3. 2 哈希函数
7. 3. 3 冲突处理方法
7. 3. 4 哈希表的查找
8 △内部排序
8．1 排序的概念
8．2 插入排序
8．2．1 直接插入排序
8．2．2 插入排序
8．2．3 希尔排序
8．3 快速排序
8．4 选择排序
8．4．1 简单选择排序
8．4．2 堆排序
8．5 各种内部排序方法的比较
四、时间分配
课程分
段标识
序号 教 学 内 容
教学环节（学时）
讲
课
习
题
实
验
上
机
课
外
小
计
1 绪论 2 2
2 线性表 5 3 7
3 栈和队列 4 7
4 数组 4 4
5 树和二叉树 7 3 10
6 图 7 7
7 查找 7 2 7
8 内部排序 4 4
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
总 计 40 8 48
五、课程说明
课程英文名称 Data Structure
主要先修课程 C++程序设计
适用专业类别 计算机科学与技术
主要教材（作者、教材
名称、出版社）
“数据结构与算法分析” 张琨 张宏 朱保平 人民邮电出版
社,2016
考核方式 考试
课程简介 各种类型的数据结构和查找，排序的各种方法
必 开
实 验
项 目
序号 项 目 名 称 学时
1 线性表链式存储结构的应用 3
2 二叉树 2
3 Hash 表应用 2
4
5
6
7
8
操作系统部分：
1 绪论
1.1 操作系统的目标和作用
1.2 操作系统的发展过程
1.3 操作系统的基本特征
1.4 操作系统的主要功能
1.5 操作系统结构设计
1.6 硬件保护
2 进程管理
2.1 进程概念
2.1.1 进程的定义
2.1.2 程序的并发执行及其特征
2.1.3 进程的特征与状态
2.1.4 进程控制块
2.2 进程控制
2.2.1 进程的创建
2.2.2 进程的终止
2.2.3 进程的阻塞与唤醒
2.2.4 进程的挂起与激活
2.3 进程同步
2.3.1 进程同步的基本概念
2.3.2 硬件和软件解决进程互斥
2.3.3 信号量机制
2.4 经典进程同步问题
2.5 进程通信
2.5.1 进程通信类型
2.5.2 消息传递通信的实现方法
2.6 线程
2.6.1 线程的基本概念
2.6.2 线程的实现方式
3 处理机调度与死锁
3.1 处理机调度的层次
3.1.1 高级调度
3.1.2 低级调度
3.1.3 中级调度
3.2 调度队列模型和调度准则
3.2.1 调度队列模型
3.2.2 选择调度方式和调度算法的若干准则
3.3 调度算法
3.3.1 先来先服务和短作业优先
3.3.2 优先权调度算法
3.3.3 时间片轮转的调度算法
3.3.4 高响应比优先的调度算法
3.3.5 多级反馈队列调度算法
3.4 产生死锁的原因和必要条件
3.4.1 产生死锁的原因
3.4.2 产生死锁的必要条件
3.4.3 处理死锁的基本方法
3.5 预防死锁的方法
3.5.1 预防死锁
3.5.2 系统安全状态
3.5.3 银行家算法
3.6 死锁的检测与解除
4 存储器管理
4.1 程序的装入和链接
4.1.1 程序的装入
4.1.2 程序的链接
4.2 连续分配方式
4.2..1 单一连续分配
4.2..2 固定分区分配
4.2..3 动态分区分配
4.2..4 伙伴系统
4.2..5 可重定位分区分配
4.3 基本分页存储管理
4.3.1 页面与页表
4.3.2 地址变换机构
4.3.3 两级和多级页表
4.4 基本分段存储管理
4.5.1 分段存储管理方式的引入
4.5.2 分段系统的基本原理
4.5.3 信息共享
4.5.4 段页式存储管理
4.5 虚拟存储器的基本概念
4.5.1 虚拟存储器的引入
4.5.2 虚拟存储器的实现方法
4.5.3 虚拟存储器的特征
4.6 请求分页存储管理
4.6.1 请求分页中的硬件支持
4.6.2 内存分配策略和分配算法
4.6.3 调页策略
4.7 页面置换算法
4.7.1 最佳置换算法和先进先出置换算法
4.7.2 LRU 置换算法
4.7.3 CLOCK 置换算法
4.7.4 其他置换算法
4.8 请求分段存储管理
4.8.1 请求分段中的硬件支持
4.8.2 分段的共享和保护
5 设备管理
5.1 缓冲管理
5.1.1 缓冲的引入
5.1.2 单缓冲和双缓冲
5.1.3 循环缓冲
5.1.4 缓冲池
5.2 I/O 软件
5.2.1 I/O 软件的设计目标和原则
5.2.2 中断处理程序
5.2.3 设备驱动程序
5.2.4 设备独立性软件
5.2.5 用户层的 I/O 软件
5.3 设备分配
5.3.1 设备分配中的数据结构
5.3.2 设备分配时应考虑的因素
5.3.3 独占设备的分配程序
5.3.4 SPOOLing 技术
5.4 磁盘存储器的管理
5.4.1 磁盘调度
5.4.2 磁盘高速缓存
5.4.3 提高磁盘 I/O 速度的其它方法
6 文件管理
6.1 文件和文件系统
6.1.1 文件、记录和数据项
6.1.2 文件类型和文件系统模型
6.1.3 文件操作
6.2 文件的逻辑结构
6.2.1 文件逻辑结构的类型
6.2.2 顺序文件
6.2.3 索引文件
6.2.4 索引顺序文件
6.3 外存分配方式
6.3.1 连续分配
6.3.2 链接分配
6.3.3 FAT 和 NTFS 技术
6.3.4 索引分配
6.4 目录管理
6.4.1 文件控制块和索引结点
6.4.2 目录结构
6.4.3 目录查询技术
6.5 文件存储空间的管理
6.5.1 空闲表法和空闲链表法
6.5.2 位示图法
6.5.3 成组链接法
6.6 文件共享与文件保护
6.6.1 基于索引结点的共享方式
6.6.2 利用符号链实现文件共享
参考书籍 1) 《计算机操作系统（第三版）》西安电子科技大学出版社
汤小丹等
2) 《操作系统概念 (中译版) (第七版)》 高等教育出版社
Abraham Silberschatz 等
免责声明：本文系转载自网络，如有侵犯，请联系我们立即删除，另：本文仅代表作者个人观点，与本网站无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
|
|
|
上一篇文章： 2018年南京理工大学基础英语考研大纲硕士研究生入学考试初试大纲
下一篇文章： 2018年南京理工大学计算机专业基础（B）考研大纲硕士研究生入学考试初试大纲
|
|
|
|
|
|
文章搜索
您现在的位置： 
