数据结构（C语言）复习提纲

一、判断题（每题3分，共30分）

知识点：

1.数据、数据元素、数据项、数据对象的概念及相互关系。

题型举例：

（1）数据元素由若干个数据项构成

（2）数据项由若干个数据元素构成

2.线性表的顺序存储方式及链式存储方式的特点。

题型举例：

（1）顺序表的存储单元是连续的

（2）链表的存储单元是连续的

3.子串与母串的概念。

题型举例：

（1）子串长度必须小于母串长度

（2）子串长度必须小于等于母串长度

4.树及二叉树的概念

题型举例：

（1）二叉树的每个结点必须有两个子树

（2）二叉树的每个结点最多有两个子树

5.简单路径和最短路径的概念

题型举例：

（1）简单路径一定是最短路径

（2）最短路径一定是简单路径

6.完全图和连通图的概念

题型举例：

（1）完全图一定是连通图

（2）连通图一定是完全图

7.邻接矩阵和邻接表的构成及特点

题型举例：

（1）同一个图的邻接矩阵是唯一的

（2）同一个图的邻接表是唯一的

8.最小生成树及最短路径的算法

题型举例：

（1）可以用普里姆算法构建最小生成树

（2）可以用弗洛伊德算法构建最小生成树

9.拓扑排序在工程上的应用

题型举例：

（1）拓扑排序可用于升降排序

（2）拓扑排序可用于工程子项目的先后顺序排序

10.关键路径在工程上的应用

题型举例：

（1）关键路径可用于估算工程成本

（2）关键路径可用于估算工程进度

11.顺序查找、二分法查找、分块法查找的适用范围。

题型举例：

（1）顺序查找可用于所有查找表

（2）二分法查找可用于所有查找表

12.满二叉树与完全二叉树的概念

题型举例：

（1）满二叉树一定是完全二叉树

（2）完全二叉树一定是满二叉树

二、简答题（每题10分，共30分）

知识点：

1.顺序表、顺序串、顺序队列、边集数组、二叉树的定义（编程完成）

题型举例：

定义一个有30个边的边集数组

2.邻接矩阵及邻接表的结构

题型举例：

邻接表如何表示图形结构的两个要素？

3.图的遍历次序

题型举例：

图的先序遍历按什么原则进行？

4.循环队列解决标志冲突的办法

题型举例：

循环队列是如何解决标志冲突的？

三、论述题（15分）

知识点：

已知二叉树的先序序列（或后序序列）和中序序列，求后序序列（或先序序列）。

题型举例：

已知二叉树的先序序列是******，中序序列是******，求后序序列。

四、程序分析（25分）

知识点：

阅读教材236页-237页（第3章实验3 参考程序）后回答5个问题，每个问题5分。

题型举例：

（1）该函数的形参分别表示什么？

（2）该函数的返回值分别代表什么？