数据结构习题一、名词解释1. 数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、算法、时间复杂度、空间复杂度。2. 线性表、顺序表、单链表、双向链表、循环链表、双向循环链表、三个概念的区别：头指针、头结点、首元结点( 第 1 个元素结点) 。3. 栈（顺序栈、链栈） 、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。4. 树、叶子结点、结点的度、树的度、树的高(深) 度、二叉树、遍历、满二叉树、完全二叉树、哈夫曼树、 WPL、哈夫曼编码。5. 图（有向、无向） 、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量） 、（最小）生成树、邻接矩阵、邻接表、DFS、BFS。6. 查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。7、排序、内（外）排序、稳定性、插入（直接、希尔）， 交换（起泡、快速） ，选择（直接、堆） ，2路归并。一、填空题1.数据结构是研究数据的_逻辑结构 __和___物理结构 __，并在这种结构上定义相关的运算，设计实现这些运算的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为___时间复杂度 ____和__空间复杂度 ___。2.数据的基本单位是__数据元素 __ ，数据的最小单位是__数据项 _ 。3.算法是对特定问题求解___步骤 ___的一种描述，是指令的有限序列。4.一个算法的时间复杂度为(3n3+2n— 7)，其数量级表示为O（n3）_。5.一个算法具有5 个特性：确定性、 可行性、 有穷性、输入和输出。6.算法性能的分析和度量，可以从算法的时间复杂度和空间复杂度来评价算法的优劣。7.数据的逻辑结构包括集合结构、线性结构、 树形结构和 图型结构四种类型。8.数据结构在计算机中的表示称为数据的物理结构，它可以采用 __顺序存储 ___或__链式存储 _两种存储方法。9.线性表有两种存储结构，分别为顺序存储和链式存储。10.链式存储的特点是利用指针来表示数据元素之间的逻辑关系。11.若频繁地对线性表进行插入和删除操作，该线性表宜采用_链式存储 __存储结构。12.线性表中的数据元素之间具有一对一的线性关系，除第一个和最后一个元素外，其他数据元素有且只有一个 直接后继和直接前趋。13.在一个单链表中p 所指结点之后插入一个s 所指结点时，应执行s->next=_ _p->next ______和p->next=__ s______的操作。14.在一个单链表中删除p 的后继结点q 时，应执行以下...
