考核内容

考核要求

第一章  概述

1．数据与数据结构 

2．算法与算法分析

了解：数据结构的基本概念与术语，数据类型的表示、实现与研究内容等。

理解：算法定义与性质，算法的设计要求。

掌握：时间复杂度与空间复杂度的计算。

第二章 线性表

1．线性表的存储方式

2．线性表的基本运算

理解：线性表的顺序存储和链式存储方式。

掌握：线性表的基本运算：插入和删除。

第三章  栈和队列

1．栈

2．队列

3．栈和队列的应用

了解：栈和队列的基本应用。

理解：栈和队列的定义。

掌握：栈和队列的基本运算和操作以及它们的存储方式。

第四章  串

1．串的定义、基本操作

2．串的存储结构

了解：串的应用举例。

理解：串定义。

掌握：串的表示、实现与基本运算。

第五章  数组与广义表

1．数组的定义

2．数组的顺序表示与实现

3．矩阵的压缩存储

4．广义表的定义

5．广义表的存储结构

了解：广义表的存储结构。

理解：数组的定义，广义表的定义。

掌握：数组的基本运算，数组的顺序表示与实现，矩阵的压缩存储。

第六章  树与二叉树

1．树的定义和基本术语

2．二叉树

3．遍历二叉树、线索二叉树

4．树和森林

5．哈夫曼树与哈夫曼编码及其应用

了解：森林与二叉树的转换、树和森林遍历。理解：树和二叉树的定义、基本术语、性质与存储结构。

掌握：遍历二叉树、线索二叉树的实现方法，最优二叉树、哈夫曼编码的实现方法与应用。

第七章  图

1．图的定义和术语

2．图的存储结构

3．图的遍历

4．生成树与最小生成树

5．拓扑排序与关键路径

6．最短路径

了解：十字链表表示法和邻接多重表表示法。

理解：图的定义和术语及其存储结构；生成树定义与最小生成树定义；最短路径的定义

掌握：图的数组表示法和邻接链表表示法；图的深度优先遍历和广度优先遍历；最小生成树的实现方法－－Prim算法与Kruscal 算法；拓扑有序排序和关键路径的求解；最短路径的求解算法－－Dijkstra 算法和Floyd 算法。

第八章  查找

1．静态查找表

2．动态表查找

3．哈希查找

理解：查找表、静态查找表；动态查找表、二叉排序树、二叉平衡树、B-树以及哈希表的定义；哈希冲突与解决冲突的方法及哈希表的查找及其分析。

掌握：顺序表查找、折半查找、分块查找；二叉排序树查找、B-树查找；二叉平衡树的生成；哈希函数的构造方法。

第九章  排序

1．排序的概述插入排序

2．简单排序方法

3．各种排序方法

4．各种排序方法比较

了解：外部信息的采取；外部排序的方法。

理解：排序的基本概念；基数排序的实现；各种排序方法比较。

掌握：直接插入排序、冒泡排序、希尔排序、快速排序、简单选择排序、形选择排序、堆排序树和归并排序的实现方法。

考核内容

考核要求

第一章 概述

1．    算法

2．    程序

3．    算法复杂性分析

了解：衡量算法的优劣的标准。

掌握：算法定义、性质及描述算法的方法。

第二章 穷举法

1．  穷举的概念

2．  水仙花数问题

3．  百鸡百钱问题

理解：穷举法的概念与设计思路。

掌握：用穷举法解决实际问题。

第三章    递推法

1．  递推的概念

2．  阶乘问题

3．  斐波那契（Fibonacci）数列问题

理解：递推法的概念与设计思路。

掌握：用递推法解决阶乘、斐波那契（Fibonacci）数列问题。

第四章 递归法

1．  递归的概念

2．  斐波那契（Fibonacci）数列问题

3．  阶乘问题

4．  排列问题

5．  整数划分问题

6．  Hanoi塔问题

理解：递归法的概念与设计思路。

掌握：用递归法解决排列、整数划分等问题。

第五章 分治法

1．    分治法的概念

2．    二分搜索法

3．    大整数乘法

4．    合并排序

5．    快速排序

理解：分治法的概念与设计思路。

掌握：二分搜索法的实现；用分治法解决各种排序等问题。

第六章 动态规划法

1．    动态规划的概念和基本要素

2．    最长公共子序列

3．    0-1背包问题

理解：动态规划算法的概念与基本要素。

掌握：用动态规划解决0-1背包等问题。

第七章 贪心法

1．    贪心算法的概念

2．    贪心算法的基本要素

3．    活动安排问题

4．    最优装载

5．    哈夫曼编码

理解：贪心算法的概念与基本要素。

掌握：用贪心算法解决最优装载等问题。

第八章 回溯法

1．    回溯法的概念

2．    回溯法的算法框架

3．    装载问题

4．    n后问题

5．    0-1背包问题

理解：回溯法的概念与算法框架。

掌握：用回溯法解决装载问题、0-1背包等问题。

教学内容

教学要求

第一章　微型计算机概述

1．微型计算机的特点和发展

2．微型机的分类

3．微型计算机系统层次结构

4．微型计算机的应用

了解：计算机的发展历程、分类、应用领域。

理解：微型计算机的层次结构。

第二章　16位和32位微处理器

1．16位微处理器8088/8086的编程结构、引脚信号、工作模式、工作时序和编址方式

2．32位微处理器的原理结构、采用的新技术、三种工作模式、寄存器、寻址方法。

了解：32位微处理器的原理结构、采用的新技术、三种工作模式、寄存器、寻址方法。

理解：16位CPU的编程结构、引脚信号、工作模式、工作时序和编址方式。

第三章　微型计算机和外设的数据传输

1. 接口电路概述

2. CPU和输入/输出设备之间的信号

3. 接口部件的I/O端口

4. CPU和外设之间的数据传送方式

理解：接口电路的主要功能、接口与端口的概念、CPU和输入/输出设备之间的信号、CPU和外设之间的数据传送方式（程序方式、中断方式、DMA方式）。

第四章　串并行通信和接口技术

1. 串行接口和串行通信概念。

并行通信和并行接口。

2. 可编程并行通信接口芯片8255A的内部结构、引腿信号、控制字、工作方式、编程与应用举例。

了解：可编程芯片8255A的内部结构与工作原理。

掌握：可编程芯片8255A的编程方法和与CPU的连接方法。

第五章　模/数和数/模转换

1. 模/数和数/模转换概述。

2. DAC工作原理、器件与有关电路。

3. DAC应用举例。

4. ADC工作原理、器件与有关电路。

5. ADC应用举例。

6. 采样保持器

7. 多路模拟开关

了解：模/数和数/模转换器的工作原理。

理解：采样保持器、多路模拟开关的应用场合。

掌握：典型模/数和数/模转换器与CPU的连接与简单应用。

第六章　键盘技术与LED显示

1. 键盘基本工作原理、键的识别与去抖。

2. LED的工作原理、静态显示与动态显示。

3. 键盘与LED显示设计实例。

理解：键盘基本工作原理、键的识别与去抖方法；LED的工作原理、静态显示与动态显示。

掌握：键盘与LED显示设计与编程。