《数据结构》c语言版 严蔚敏 吴伟民 试题

1. 请简述线性表的定义和特点。

答：线性表是由n个数据元素组成的有限序列，数据元素之间的关系是一对一的关系。线性表的特点包括：有且仅有一个首元素和一个尾元素，除首元素和尾元素外，每个元素都有一个前驱和后继，元素之间的关系是线性的。

2. 请说明顺序存储结构和链式存储结构的优缺点。

答：顺序存储结构的优点包括：存储密度高，可以随机存取元素，存储结构简单易于实现；缺点包括：插入和删除元素需要移动大量元素，造成时间和空间的浪费，不适用于频繁插入和删除的场合。链式存储结构的优点包括：插入和删除元素方便快捷，可以动态分配存储空间，适用于频繁修改的场合；缺点包括：存储密度低，不易随机存取元素，需要额外的指针存储关系信息，实现复杂。

3. 请简述栈和队列的定义和特点，并说明它们的应用场景。

答：栈是一种先进后出的线性数据结构，只允许在栈顶进行插入和删除操作。队列是一种先进先出的线性数据结构，只允许在队尾插入元素，在队头删除元素。栈的应用场景包括：函数调用、表达式求值、括号匹配等场合。队列的应用场景包括：模拟排队等待、广度优先搜索等场合。

4. 请简述二叉树的定义和特点，并说明它的应用场景。

答：二叉树是一种特殊的树形结构，每个节点最多有两个子节点。二叉树的特点包括：每个节点最多有两个子节点，左子树和右子树是有序的，对于任意一个节点，左子树中所有节点的值都小于它的值，右子树中所有节点的值都大于它的值。二叉树的应用场景包括：二叉查找树、哈夫曼树、二叉排序树等场合。

5. 请简述图的定义和特点，并说明它的应用场景。

答：图是由节点和边组成的一种非线性数据结构。图的特点包括：节点之间的关系可以是任意的，边可以有权值，图可以有多个连通分量。图的应用场景包括：社交网络、路网规划、电路设计等场合。