数据结构与微机原理

一．       考试的总体要求

本考试内容由数据结构和微机原理两部分组成，各占总分的50％（75分）。

数据结构是计算机科学与技术专业基础课,要求学生掌握基本的数据结构及相关的存储方式、基本运算和算法, 掌握实际数据处理中常用的几种排序方法和几种常用的数据查找方法，以及不同查找算法对查找速度的影响情况。并能应用高级语言编写算法（C/C++）。

微机原理部分要求学生掌握：计算机及微处理器的基本知识，汇编语言程序设计及关于键盘与CRT的DOS、BIOS调用，存储器原理及连接，输入/输出接口基本原理、基本知识与应用，IBM PC/XT微型计算机系统总线与I/O扩展。需要掌握的接口芯片：8255A，8251，8259，8253/8254，8237，ADC0809，AD574,DAC0832,RS232等。另外，本课程试题凡涉及到具体微处理器、并行接口芯片、定时器芯片时，均以Intel8086系统为例，其工作在最小组态和实模式下。

二．考试的内容及比例

（一）数据结构部分（占总分的50％，75分 ）：

1、 线性表、顺序表、链表的存储结构及相关的各种基本运算；（10分）

2、 栈与队列的概念、特点、存储表示、基本运算；栈的应用；链队列；循环队列；（6分）

3、 数组的顺序存储表示和实现；特殊矩阵和稀疏矩阵的压缩存储；广义表的定义及存储结构；（4分）

4、 二叉树的定义、性质及存储结构；遍历二叉树；二叉树的应用；森林与二叉树的转换；哈夫曼树及其应用；与二叉树的应用相关的递归方法；(16分)

5、 图的定义、存储结构；图的遍历；最小生成树；拓扑排序；关键路径；最短路径；与图的应用相关的递归方法；(15分)

6、 静态表查找与动态表查找；哈希表的构造及处理冲突；(12分)

7、 内部排序的概念；插入排序、快速排序、选择排序、归并排序、基数排序等内部排序的特点与算法。(12分)

（二）微机原理部分：（占总分的50％，75分）

1、基本知识及基本概念（15分）：

计算机基础，微型计算机的基本组成与工作原理，微处理器的寻址方式与指令系统，微处理器的时序，存储器，输入、输出与中断，接口芯片的基本结构及应用。

2、汇编语言程序设计（20分）：                       

对给出的问题按汇编语言格式（包括宏汇编和小汇编两种方式），正确使用指令，编写符合结构化要求和相应功能的程序。

3、微型计算机硬件系统的设计（25分）：

给出系统的存储器容量、并行接口、串行接口、定时器/计数器接口要求，设计相应的硬件电路，编写相应的汇编语言程序。

4、接口应用（15分）：

对给出的包括输入/输出、定时器/计数器、A/D或D/A的综合应用问题，设计相应的汇编语言程序。

三．试卷类型及比例

（一）数据结构部分：

1．填空题    （ 10分）

2．回答问题  （ 50分）其中包括叙述题、画图题、计算题等。

3．算法题    （ 15分）

（二）微机原理部分：

1．填空题（20分）

2．程序设计题（15分）

3．硬件系统设计题（30分）

4．综合应用题（10分）。

四．考试形式及时间

“数据结构与微机原理”考试形式为笔试，考试时间为3小时。

五、 主要参考教材（参考书目）

1. 严蔚敏，吴伟民编   《数据结构》 C语言版    清华大学出版社

2．戴梅萼，《微型计算机及应用》，清华大学出版社

3．周明德，《微型计算机系统原理及应用》，清华大学出版社