2025年数据结构课程终极备考攻略与重点难点梳理.doc

《数据构造》課程考试大纲

課程编号：

課程名称：数据构造（DataStructure）

使用教材：严蔚敏、吴伟民编著，数据构造（C語言版），清华大学出版社，1999年2月

该課程的性质、目的及任务：

“数据构造”是一门专业技术基础課。目的就是要培养他們的数据抽象能力，学会分析研究计算机加工的数据构造的特性，以便為应用波及的数据选择合适的逻辑构造、存储构造及实現应用的对应算法，并掌握分析算法的時间和空间复杂度的技术。

考试内容及规定：

绪论：熟悉各名詞、术語的含义，掌握基本概念，尤其是数据的逻辑构造和存储构造之间的关系；理解抽象数据类型的定义、表达和实現措施；熟悉类C語言的书写规范，尤其要注意值调用和引用调用的区别，输入、输出的方式以及錯误处理方式；理解算法五个要素确实切含义；掌握计算語句频度和估算算法時间复杂度的措施。

线性表：线性表的逻辑构造定义、抽象数据类型定义和多种存储构造的描述措施；在线性表的两类存储构造（次序存储和链式存储）上实現基本操作；一元多项式的抽象数据类型定义、表达及加法的实現。

栈和队列：栈和队列的构造特性；在两种存储构造上怎样实現栈和队列的基本操作和栈和队列在程序设计中的应用以及怎样运用堆栈去模拟递归程序的运行。

串：串的数据类型定义；串的三种存储表达：定長次序存储构造、块链存储构造和堆分派存储构造；串的多种基本操作的实現及应用；串的模式匹配算法。

数组和广义表：数组的类型定义和表达措施；特殊矩阵和稀疏矩阵的压缩存储措施及运算的实現；广义表的逻辑构造和存储构造、m元多项式的广义表表达以及广义表的操作的递归算法举例。

树和二叉树：二叉树的定义、性质和存储构造；二叉树的遍历和线索化以及遍历算法的多种描述形式；树和森林的定义、存储构造、树和森林与二叉树的转换、遍历；树的多种应用；平衡二叉树、平衡二叉排序树的定义、性质极其应用。本章是该課程的重点内容之一。

图：图的定义和术語；图的四种存储构造：数组表达法、邻接表、十字链表和邻接多重表；图的两种遍历方略：深度优先搜索和广度优先搜索；图的连通性：连通分量和最小生成树；拓扑排序和关键途径；两类求最短途径问題的解法。

查找：讨论查找表（包括静态查找表和动态查找表）的多种实現措施：次序表、有序表、树表和哈希表；有关衡量查找表的重要操作——查找的查找效率的平均查找長度的讨论。

内部排序：讨论比较多种内部排序措施，插入排序、互换排序、选择排序、归并排序和基数排序的基本思想、算法特点、排序过程以及它們的時间复杂度分析。在每类排序措施中，从简朴措施入手，重点讨论性能先进的高效措施（如，插入排序类中的希尔排序、互换排序类中的迅速排序、选择排序类中的堆排序等）。

外部排序：实現外部排序的基本措施；為减少平衡归并排序中所需进行的外存读/写次数可采用的措施：运用败者树实現多路归并，通过置换-选择排序产生初始归并段，并对所得長度不等的归并段构造最佳归并树。

总之，规定学生掌握基本概念、重要数据构造、基本算法，掌握多种数据构造的逻辑构造、存储构造和实現算法。根据目前计算机的应用发展举例阐明数据构造的描述及应用的实現算法。

“微机原理及接口技术”入学考试大纲

第一章

微型计算机的基础知识

微型计算机中常用的术語，名詞

微型计算机的基本构造

第二章16位微处理器及微机控制关键的构成

2．18088微处理器

8088微处理器的内部构造及其重要功能

8088微处理器程序可访问的内部寄存器及其重要功能

在最小模式和最大模式的引脚及其功能

8088基本時序概念

8088指令系统（寻址方式及指令的简朴编程使用）

2在IBMPC/XT中8087怎样配合8088工作

2．38284時钟发生器/驱动器的重要功能

2．48288总线控制器各命令输出信号和控制输出信号的功能

第三章半导体存储器的连接使用

3．1概述

存储器的一般概念

存储器芯片的重要技术指标

3．2随机存储器的连接使用措施

3．3存储器的奇偶校验原理

3．4EEPROM的连接使用措施

第四章可编程高性能支援芯片及接口电路

4．1可编程并行接口8255

8255的构造框图

8255的控制命令字及工作方式

8255的连接使用及初始化编程

4．28253计数器/定期器

1．8253的构造框图

2．8253的控制命令字及工作方式

3．8253的连接使用及初始化编程

4．38259中断控制器

8259的构造框图

8259的初始化命令字和操作命令字

IBMPC/XT的中断控制逻辑

4．48237DMA控制器

DMA的工作过程

8237的引脚功能

8237的工作方式

4．5可编程串行接口8250

8250编程使用

8250的