北京交通大学925数据结构2021年初试大纲.pdf
需积分: 1 134 浏览量
2024-03-11
13:12:07
上传
评论
收藏 208KB PDF 举报
用银行家算法给出避免死锁的资源分配方案，死锁检测算法及应用。
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）熟练掌握哈希表的构造
方法和处理冲突的方法。
资源评论
