821数据结构考试大纲

一、考查目标

1．理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。

2．掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。

3．能够选择合适的数据结构和方法进行问题求解。

 

二、考试形式和试卷结构

1．试卷满分及考试时间

试卷满分150分，考试时间180分钟。

2．答题方式

答题方式为笔试、闭卷。

3．试卷内容与题型结构

单选题           10题      每小题 2分          共20分

填空题           10题      每小题 2分          共20分

简答题           5题      每小题 5分          共25分

综合题           3题      每小题15分         共45 分

算法题           4题      每小题10分         共40 分

 

三、考查内容

1．概念

（1）基本概念和术语

l  数据

l  数据结构

l  抽象数据类型

（2）算法的描述和分析

l  算法、算法的时间复杂度和空间复杂度概念

l  算法描述和算法分析的方法，对于一般算法能分析出时间复杂度

2．线性表

（1）线性表的概念

l  线性表的逻辑结构

l  线性表的存储结构：顺序表，单链表，双链表，循环链表，静态链表

（2）线性表的实现

l  顺序存储结构：查找、插入、删除等基本操作及其平均时间性能分析

l  链式存储结构：查找、插入、删除等基本操作及其平均时间性能分析

3．栈、队列

（1）栈和队列的概念

l  栈和队列的逻辑结构

l  栈和队列的存储结构：顺序栈，循环队列，链式栈，链式队列

（2）栈和队列的实现

l  顺序存储结构：入栈、出栈、入队、出队等基本操作及其平均时间性能分析

l  链式存储结构：入栈、出栈、入队、出队等基本操作及其平均时间性能分析

4．数组和广义表

（1）数组和广义表的概念

l  数组和广义表的逻辑结构

l  数组的存储结构：特殊矩阵压缩存储、稀疏矩阵压缩存储（三元组表）

l  广义表的存储结构：链式存储

（2）数组和广义表的实现

l  数组顺序存储结构：一般数组顺序存储的地址计算方法

l  广义表链式存储结构：非空广义表的求表头和表尾等基本操作

5．树和二叉树

（1）树和二叉树的概念

l  树和二叉树的逻辑结构

l  树和二叉树的存储结构：树的孩子兄弟表示法、二叉树的二叉链表

l  树和二叉树的遍历：树的三种遍历方法、二叉树的三种遍历方法

l  树和二叉树的转换方法

（2）树和二叉树的实现

l  二叉树的递归遍历

l  Huffman树

l  Huffman编码

6．图

（1）图的概念

l  图的逻辑结构

l  图的存储结构：邻接矩阵、邻接表

l  图的遍历：深度优先搜索方法、广度优先搜索方法

（2）图的实现

l  最小（代价）生成树：Prim和Kruskal方法

l  最短路径：Dijkstra方法

l  拓扑排序

l  关键路径

7．查找

（1）查找的概念

l  查找表、查找分类、查找结构

l  查找算法效率的评判标准：平均查找长度

（2）静态表及其查找

l  顺序查找

l  折半查找

（3）动态表及其查找

l  二叉排序树

l  平衡二叉树

（4）Hash表及其查找

l  Hash函数

l  处理冲突方法

l  Hash查找

（5）各种查找算法的分析

8．排序

（1）排序的概念

l  排序方法稳定性、排序分类

l  排序算法效率的评判标准

（2）插入排序

l  简单插入排序

l  希尔排序

（3）交换排序

l  冒泡排序

l  快速排序

（4）选择排序

l  简单选择排序

l  堆排序

（5）归并排序

l  二路归并排序

l  分治归并排序

（6）各种排序算法的比较

 

四、题型举例

1．选择题

在单链表中成功查找一个元素的等概率下的平均搜索长度是        。

A. n                            B. n/2                         C. (n+1)/2                         D. n+1

2．填空题

深度为5的二叉树至多有        个结点。

3．简答题

请比较顺序表和单链表在存储空间和数据访问方面的特点。

4．综合题

已知一棵二叉树的先序遍历的结果是ABDECF，中序遍历的结果是DEBAFC，请画出这棵二叉树，并写出该二叉树的后序遍历结果。

5．算法题

分析下面算法功能，以及时间复杂度。

#define List_Size 100

typedef struct  {

ElemType          elem[List_Size];

int              length;

} SqList;

void ex(SqList la, SqList lb, SqList &lc)  {

         i=0;  j=0;  k=0;

while(i  {

if(la.elem[i]<=lb.elem[j])  lc.elem[k++]=la.elem[i++];

                            else  lc.elem[k++]=lb.elem[j++];

           }

           while(i  lc.elem[k++]=la.elem[i++];

while(j  lc.elem[k++]=lb.elem[j++];

} // ex

(2) 用循环单链表实现队列，要求该队列只使用一个指向队尾指针。请写出结点和队列的类型定义，并分别编写队列初始化、入队、出队算法。

 

五、参考教材

       (1) 数据结构-基于C语言的描述，彭波主编，清华大学出版社

       (2) 数据结构，严蔚敏编著，清华大学出版社