数据结构复习-铁宇彤完整版 v.0.1VIP免费

考试题型选择题：21分填空题：18分判断题：15分图表题：26分算法题：20分1

什么是图的邻接矩阵表示法

什么是图的邻接表表示法

在这两种存储结构上如何计算顶点的度

邻接矩阵一个有n个顶点的图G=(V,E)的邻接矩阵是一个nn的矩阵A，A的每个元素是0或1

设V={0,1,2,……,n-1},如果G是无向图，则A的元素定义为：1(u,v)EA(u,v)=0其他如果G是有向图，则A的元素定义为：1EA(u,v)=0其他如果G是带权的图，则邻接矩阵中值为1的元素应替换为权值，有时需要将0替换为

(详见PPTunit7-120-21)邻接表要点：1

为图中每一个顶点建立一个单链表；2

顶点u的单链表中，每一个结点v表示一个邻接点，即代表一条边(u,v)或3

结点和边的结构如下：4

每个单链表的头指针存入一个一维数组，以表示一个图

(详见PPTunit7-120-21)2

什么是最大堆

什么是最小堆

如何利用下推（筛选）操作建堆

如何利用逐步插入结点（上推）的操作建堆

一个大小为n的堆（heap）是一棵包含n个结点的完全二叉树

每个结点的关键字值大于等于双亲结点的关键字值的堆称为最小堆（MinHeap）

最小堆的另一定义当完全二叉树以顺序方式存储时，实际上得到的是结点序列，所以最小堆又可以定义为：堆是n个元素的序列（k1,k2,…,kn），当且仅当满足kik2i且kik2i+1,(i=1,2,…,n/2)时,称为最小堆

函数AdjustDown（向下调整）设序列以顺序方式保存在一维数组中，数组元素具有可比较大小的类型

函数AdjustDown假定从数组中r+1到n，这n-r个位置上的元素已满足kik2i且kik2i+1,(i=r+1,2,…,n/2)条件，现向下调整第r位置上的元素，如果kr大于k2r和k2r+1,(即左、右孩子)中的较小的元素，