北京交通大学2019计算机考试大纲.pdf
计算 机 与 信息技术 学院硕士研究生入学考试 自命题科目考试范围 一 、 920 数字信号处理 1、离散时间信号与系统。 ( 1)离散时间信号(序列):常用序列、序列基本运算、周期性等;( 2)线性移不变系统:线性、移不变、因果性、稳定性;( 3)连续时间信号抽样:理想抽样、实际抽样、抽样定理。 2、 z 变换。 ( 1) z 变换的定义与收敛域: z 变换定义、右边序列、因果序列、左边序列、双边序列的收敛域;( 2) z 变换性质:线性、移位、尺度变换、微分、共轭、卷积、翻转、初值、终值等;( 3) z 反(逆)变换:部分分式展开法、典型序列的 z 变换及收敛域;( 4)序列的 z 变换与连续信号的拉普拉斯变换、傅里叶变换的关系;( 5)序列的傅里叶变换:正变换与反变换定义,对称性质;( 6)系统函数:系统函数与系统的稳定性、差分方程与系统函数、离散系统的频率响应、相位响应与群延时等。 3、 离散傅里叶变换( DFT) 。( 1)傅里叶变换的四种形式;( 2)周期序列的傅里叶级数:正反变换定义、性质;( 3)离散傅里叶变换:正反变换定义;( 4)离散傅里叶变换的性质:线性、圆周移位、共轭对称、圆周卷积、线性卷积与圆周卷积的关系;( 5)频域抽样定理;( 6) DFT 应用的几个问题: 混叠失真、频率泄漏、栅栏效应、频率分辨率。 4、 快速傅里叶变换( FFT) 。( 1) DFT 存在问题与改进途径;( 2)时间抽取基 -2FFT 算法:算法原理、蝶形图、运算量、原位运算、倒序;( 3)频率抽取基 -2FFT 算法:算法原理、蝶形图、运算量、原位运算;( 4)离散傅里叶反变换( IFFT):方法与蝶形图;( 5)线性卷积的 FFT 算法。 5、 数字滤波器。( 1) 数字滤波器结构表示方法:方框图与信号流图;( 2) IIR 数字滤波器的基本结构:直接 I 型、直接 II 型、级联型、并联型;( 3) FIR 数字滤波器的基本结构:直接型、级联型 、快速卷积结构、线性相位 FIR 滤波器的结构;( 4)简单数字滤波器的频谱:一阶 FIR 与 IIR 低通、高通滤波器的频谱结构;滤波器类型的判断方法(几何确定法)等。 6、 IIR 数字滤波器设计 。( 1)全通系统:频谱响应特点、零极点位置、应用;( 2)最小相位与最大相位系统:零极点位置、稳定性、因果性;( 3)冲激响应不变法:变换原理、混叠失真、优缺点;( 4)双线性变换法:变换原理、常数 c 选择、优缺点;( 5)模拟低通滤波器设计:设计原理、巴特沃思低通滤波器特点及其设计、切比雪夫滤波器与椭圆滤波器特点;( 6) IIR 滤波器的两 种频率变换法:低通 低通、低通 高通、低通 带通、低通 带阻。 7、 FIR 数字滤波器设计。 ( 1)线性相位 FIR 滤波器的特点:线性相位条件、频率响应特点、零点位置、四种 FIR 滤波器的性质;( 2)窗函数设计法:设计方法、吉布斯效应、各种窗函数特点;( 3)频率抽样设计法:设计方法;( 4) IIR 与 FIR 比较。 8: 功率谱估计。 ( 1)随机信号的数字特征:均值、方差、自相关函数、互相关函数;( 2)功率谱:定义、与相关函数之间的关系;( 3)经典功率谱估计:直接法(周期图法)、间接法(相关法)。 二 、 923 操作系统原理 1、引论。 ( 1)要求理解的内容包括:操作系统的概念、设计目标、功能及特征,操作系统运行硬件基础,操作系统接口分类及组成,操作系统内核用典型数据结构;( 2)要求掌握的内容包括:系统调用实现机制,操作系统启动引导过程。 2、处理机管理。 ( 1)要求理解的内容包括:多道程序设计技术,程序、进程、线程的区别与联系,线程实现方式,进程状态变迁,进程控制,处理机调度类型与模型,处理机调度实现机理,调度算法与评价准则;( 2)要求掌握的内容包括:处理机主要调度算法设计实现及应用。 3、同步通信及死锁处理。 ( 1)要求理解的内容包括:进程同步基本准则,进程同步软硬件解决方案,整型信号量、记录型信号量、管程,经典同步问题,进程通信机制,线程同步机制,死锁及处理方法;( 2)要求掌握的内容包括:利用记录型信号量解决同步问题,利用银行家算法给出避免死锁的资源分配方案,死锁检测算法及应用。 4、存储管理。 ( 1)要求理解的内容包括:程序处理与内存管理,分区存储管理及相关技术(拼凑、覆盖、对换、伙伴系统),分页 /分段 /段页式存储管理,虚拟存储技术,请求分页 /分段存储管理,多级页表和反置页表,内存保护机制;( 2)要求掌握的内容包括 :分页 /分段地址变换,页面淘汰算法设计实现及应用,请求分页 /分段地址变换,动态分区存储管理设计与实现。 5、设备管理 。( 1)要求理解的内容包括: I/O 系统组成及 I/O 控制方式,设备管理目标、功能及层次结构,缓冲管理,设备分配及假脱机技术,设备驱动及中断处理,磁盘存储器管理方法与技术;( 2)要求掌握的内容包括:磁盘调度算法设计及应用,磁盘数据访问过程及时间开销。 6、文件管理。 ( 1)要求理解的内容包括:文件及典型存取操作逻辑流程,文件系统层次模型,文件的逻辑结构和物理结构,外存空间管理方法,文件目录结构及管理 ,文件共享与保护,磁盘容错技术,文件系统性能改善策略及数据一致性控制;( 2)要求掌握的内容包括:目录检索过程,文件数据访问基本过程, FAT 文件系统设计实现。 7、操作系统发展与演化 。( 1)要求理解的内容包括:批处理、分时和实时系统的概念,操作系统结构设计及演化,操作系统发展趋势。 三 、 925 数据结构 1、绪论。 ( 1)掌握相关的基本概念,如数据结构、逻辑结构、存储结构、数据类型、抽象数据类型等;( 2)掌握算法设计的原则,掌握计算语句频度和估算算法时间复杂度和空间复杂度的方法;( 3)了解使用类 C 语言描述算法 的方法。 2、线性表。 ( 1)掌握线性表的逻辑结构和存储结构;( 2)掌握线性表在顺序结构和链式结构上实现基本操作的方法; ( 3)理解线性表两种存储结构的不同特点及其适用场合,会针对需求选用合适的存储结构解决实际问题;( 4)了解一元多项式的表示方法和基本运算的实现方法。 3、栈和队列。 ( 1)了解栈和队列的特点;( 2)掌握在两种存储结构上栈的基本操作的实现;( 3)掌握栈的各种应用,理解递归算法执行过程中栈状态的变化过程;( 4)掌握循环队列和链队列的基本运算;( 5)会应用队列结构解决实际问题。 4、串。 ( 1)掌握串的基本运算的定义,了解利用基本运算来实现串的其它运算的方法;( 2)了解在顺序存储结构和在堆存储结构以及块链存储结构上实现串的各种操作的方法;( 3)理解 KMP 算法,掌握 NEXT 函数和改进 NEXT 函数的定义和计算。 5、数组和广义表。 ( 1)掌握数组在以行为主和以列为主的存储结构中的地址计算方法;( 2)掌握矩阵压缩存储时的下标变换方法,了解以三元组表示稀疏矩阵的方法;( 3)理解广义表的定义及其存储结构,理解广义表的头尾和子表两种分析方法。 6、树和二叉树。 ( 1)熟练掌握二叉树的结构特点和性质,掌握二叉树各 种存储结构及构建方法;( 2)掌握按先序、中序、后序和层次次序遍历二叉树的算法,理解二叉树的线索化实质和方法;( 3)利用二叉树的遍历求解实际问题;( 3)掌握树的各种存储结构及其特点,掌握树的各种运算的实现算法;( 4)掌握建立最优二叉树和哈夫曼编码的方法。 7、图。 ( 1)熟练掌握图的基本概念,会构建各种图的存储结构;( 2)掌握深度优先搜索遍历图和广度优先搜索遍历图的算法;( 3)灵活运用图的遍历算法求解各种路径问题,包括最小生成树最短路径拓扑排序关键路径等。 8、查找。 ( 1)熟练掌握各种静态查找和动态查找算 法,会计算查找成功时和失败时的平均查找长度;( 2)掌握二叉排序树的建立、插入和删除过程,掌握二叉平衡树的建立和旋转平衡方法;( 3)掌握 B-树的建立、插入和删除结点的过程;( 4)熟练掌握哈希表的构造方法和处理冲突的方法。 9、排序。 ( 1)掌握各种排序算法,包括插入类、交换类、选择类、归并类排序及基数排序;( 2)能够对各种排序方法进行比较分析,如稳定性、时间和空间性能等,了解各种排序方法的特点和不同并灵活应用;( 3)理解外部排序的主要思想和过程。 四 、 926 软件工程理论与技术 1、软件工程学概述。 ( 1)了解 软件开发技术的发展历史及特点;( 2)了解软件危机及产生的原因、解决办法;( 3)了解软件的特点、传统的生命周期模型 熟悉软件工程的基本原理和方法;( 4)重点掌握软件工程的概念和基本原理;( 5)掌握生命周期方法学内容以及各阶段的划分和基本任务。 2、可行性研究 深刻理解可行性研究的必要性。 ( 1)掌握可行性研究的任务及可行性研究的具体步骤;( 2)了解系统流程图的作用及符号表示;( 3)重点掌握数据流图的画法及数据字典的编写。 3、需求分析。 ( 1)深刻理解需求分析阶段的概念及任务;( 2)熟练掌握数据流图的细化及 ER 图 、 IPO 图的画法;( 3)掌握需求分析过程及各种图形工具的应用。 4、总体设计。 ( 1)深刻理解软件总体设计的基本任务;( 2)理解软件设计的基本原理 理解模块化、抽象、信息隐蔽、模块独立性等概念;( 3)明确度量模块独立性的校准 -偶和性及内聚性;( 4)熟练掌握结构化设计方法 (要求能划分数据流的类型,将其能换成软件结构图,并能根据优化准则将其优化 )。 5、详细设计 。( 1)能熟练的使用详细设计描述工具来设计模块中的算法及程序的逻辑结构;( 2)理解 Jackson 方法的概念及程序复杂度的度量方法;( 3)学会使用 Jackson 方法设计输入输出数据结构和程序结构。 6、实现。 ( 1)了解几种常见的程序设计语言的特点;( 2)领会程序设计中应注意的问题,注意培养良好的编程风格;( 3)掌握测试阶段的内容、测试方法及测试步骤;( 4)深刻理解白盒、黑盒测试技术;( 5)深刻理解测试过程中单元测试、集成测试、验收测试的任务及使用的方法;( 6)掌握调试程序的方法;( 7)熟练掌握针对某一问题采用白盒法或黑盒法进行测试用例的设计。 7、维护。 ( 1)掌握软件维护的内容、特点、方法、技术、文档;( 2)了解软件维护的各种困难、软件维护的特点及 软件维护的文档;( 3)理解软件维护的内容及维护任务的实施;( 4)深刻理解如何提高软件的维护性。 8、面向对象方法学引论。 ( 1)深刻理解对象、类、类的层次结构、方法和消息的实质;( 2)深刻理解对象模型、动态模型、功能模型的元素、结构和构造方法;( 3)掌握画对象图、画状态图、画数据流程图;( 4)确定对象类、确定关联、确定属性、识别继承。 9、面向对象分析。 ( 1)了解需求陈述,掌握面相对象分析过程;( 2)掌握面向对象分析的概念和基本任务;( 3)掌握对象模型、动态模型、功能模型的建模方法。 10、面向对象设计。 ( 1)掌握面向对象设计的概念和准则;( 2)掌握软件重用概念及提高重用的方法。 11、面向对象实现。 ( 1)掌握面向对象对象的测试,保证良好的程序设计风格须遵守的原则。 12、软件项目管理。 ( 1)了解软件管理的特点和软件管理的基本过程;( 2)掌握文档管理的重要性与方法。 五 、 929 通信系统原理及应用 1、基本概念和基本理论。 ( 1)理解和掌握通信系统的组成、质量指标、信道分类和信道特征;( 2)熟练掌握随机变量和随机过程的概念、统计特性、数字特征、通过线性系统的传输特性以及平稳随机过程的概念、数字特征、各态历经性和功率谱,并可以对各类噪声进行计算。 2、模拟调制系统和模拟信号数字化。 ( 1)掌握线性调制系统和非线性调制系统的基本理论和分析计算方法。 3、模拟信号数字化。 ( 1)掌握线性 PCM 概念、量化噪声分析方法、线性 PCM 系统中的误码噪声、对数压扩 PCM;( 2)理解和掌握多路复用概念和传码率的计算方法;( 3)熟练掌握增量调制的实现方法、不过载条件、量化信噪比分析、传码率计算;( 4)了解 DPCM、ADPCM 预测编码的基本概念。 4、数字信号的基带与频带传输。 ( 1)掌握数字基带信号的常见码型和功率谱、基带传输系统组成及符号间干扰、基带数字信号的波形形成和 Nyquist 准则、基带传输的误码率计算、第一类、第四类部分响应系统以及信道均衡的基本知识和分析计算方法;( 2)掌握好二元与四元数字调制、多元数字调制以及 QAM、 CPFSK 和 MSK 现代调制技术的原理与性能分析。 5、数字信号的最佳接收。 ( 1)掌握最佳接收准则,并可以利用匹配滤波器进行最佳接收分析以及最佳接收误码率分析。 6、信道编码。 ( 1)掌握差错控制基 本原理,对线性分组码和循环码能够进行分析;( 2)了解卷积码的概念、基本原理以及编、解码方法。 7、无线通信。 ( 1)掌握电波传播的主要方式和损耗特性;( 2)多径衰落信道的分类以及基于典型电波传播损耗预测模型的路径损耗计算;( 3)了解移动环境下干扰的主要形式;( 4)能够配置小区和信道;( 5)掌握主要多址接入方式的原理,能够对主要多址接入方式移动通信系统的容量进行计算。 8、计算机网络。 ( 1)了解计算机网络的发展过程和基本组成,掌握计算机网络的体系结构和各层的服务和功能;( 2)掌握 IP 地址组成和 IP 路由协议。 六 、 02101 信号与系统 1、 连续时间信号与系统的时域分析。 ( 1)信号与系统基本概念;( 2)信号的基本运算与变换:信号的加法和乘法运算、信号的反转、平移与尺度变换;( 3)阶跃函数和冲激函数:阶跃函数、冲激函数的定义及其关系,冲激函数的性质,利用冲激函数的抽样性质计算某些积分;( 4)线性时不变连续系统的响应:零输入响应、零状态响应、自由响应、强迫响应、全响应的概念和求解,用卷积积分法求零状态响应,系统框图;( 5)单位冲激响应与阶跃响应的定义和计算;( 6)卷积的定义、性质和计算,线性时不变连续系统输入输出关系 。 2、 连续系统的频域分析。 ( 1)周期信号的频谱与傅里叶级数分析;( 2)非周期信号的频谱:傅里叶变换对和非周期信号频谱的特点,常用非周期信号的频谱;( 3)傅里叶变换的性质和应用;( 4)连续系统的频域分析;( 5)抽样定理。 3、 连续系统的复频域分析。 ( 1)拉普拉斯变换;( 2)拉普拉斯变换的性质;( 3)拉普拉斯反(逆)变换;( 4)连续系统的复频域分析;( 5)系统函数和系统稳定性判断。 4、 离散时间系统的时域分析。 ( 1)离散时间信号:常用序列、序列基本运算、周期性等;( 2)线性移不变系统:线性、移不变、因果性、稳 定性;( 3)离散系统的时域分析:差分方程的求解方法、系统零输入响应和零状态响应的计算、单位序列响应的计算、卷积和的计算。 5、 离散时间系统的 z 域分析。 ( 1) z 变换: z 变换定义和常用序列的 z 变换、信号的 z变换及其收敛域;( 2) z 变换的性质、利用部分分式求反(逆) z 变换;( 3)离散系统的 z域分析:差分方程的变换域解法、系统函数的求解、系统的因果稳定性判断。 七 、 02102 离散数学 1、命题逻辑的基本概念。 掌握命题、联结词、命题公式、真值表。 2、命题逻辑等值演算。 掌握等价公式、重言式、蕴含式、等值演算,合取范式、析取范式、主合取范式及主析取范式。 3、命题逻辑的推理理论。 掌握命题推理理论。 4、一阶逻辑基本概念。 掌握谓词、量词、谓词公式。 5、一阶逻辑等值演算与推理。 掌握谓词演算公式的前束范式,谓词演算公式真值的求解方法,谓词推理理论。 6、集合代数理解集合运算和集合等式证明。 掌握集合的概念和表示,集合元素计数。 7、二元关系。 ( 1)理解关系的定义,表示和性质,等价关系与划分;( 2)掌握关系的定义,表示和性质,偏序关系,哈斯图与极值。 8、函数。 了解函数的定义与性质,函数复合运算与逆函数。 9、代数系统。 掌握代数系统概念,代数系统同态,同构映射。 10、群与环。 掌握半群,独异点,单位元,零元,群,子群,交换群,循环群,有限群,置换群,商群,陪集,环,整环,无零因子环的定义;( 2)群,子群,循环群,有限群,环,整环的性质和判别方法。 11、格与布尔代数。 ( 1)理解格的同态的概念;( 2)掌握格、子格、分配格和有补格的定义和基本性质;( 3)子格、分配格和有补格的判定方法;( 4)有限布尔代数的结构和性质。 12、 图的基本概念。 ( 1)了解图的运算。理解有向 图、无向图、通路、回路;( 2)掌握握手定理及推论,图的矩阵表示及应用。 13、欧拉图与哈密顿图。 ( 1)理解欧拉图,欧拉通路和回路,哈密尔顿图,哈密尔顿通路和回路;( 2)掌握欧拉图的性质和判定方法,哈密尔顿图的性质和某些哈密尔顿图的判定方法, Dijkstra 标号法求最短路径;( 3)了解中国邮递员问题,货郎担问题。 14、树。 ( 1)掌握求最小生成树的多种算法,根树的行遍方法,最优二叉树和 Huffman 算法;( 2)熟练无向树及其性质,根树的相关概念。 15、平面图。 ( 1)理解平面图的概念,平面图的对偶图及其应 用;( 2)掌握欧拉公式及相关定理,平面图或极大平面图的性质和判定条件。 16、理解支配集、点独立集、点覆盖集、边覆盖集、匹配, Hall 定理。 掌握边覆盖与匹配之间的关系、最大匹配或完美匹配存在的条件;了解点着色,点色数,边色数,色多项式,平面图 4 色猜想。 八 、 02103: 程序 设计基础 1、过程化程序设计基础 ( 1) C 语言基础、基本数据类型、基本 I/O、运算符表达式与流程控制、函数与递归、参数传递; ( 2)数组和指针、字符串处理、变量及其存储、内存管理、结构、位运算、文件 I/O;( 3) C 预处理器及运行库、 多模块程序设计、数据抽象、流程图、程序设计规范。 2、 面向对象程序设计基础 ( 1) OOP 基本思想与方法:类、对象、属性、方法、重载 /覆盖、封装、继承 /派生、多态、模板 (集合与泛型 )、异常处理等基础知识。( 2) OOP 程序设计语言( C#、 Java 等)、简单设计模式、包、类图、程序设计规范。 3、 基础算法与数据结构 ( 1)算法复杂度分析、基础输入输出、简单实现、暴力、枚举、贪心、排序、搜索 (BFS/DFS)、二分;( 2)简单数学推理、串处理、栈、队列、简单树 /图算法。