数据结构练习解读.ppt

已知一棵树的先根序列和后根序列如下，试构造出该树。 先根序列：ABCDEFGHIJKL 后根序列：CEDGHFBJKLIA 设有六个结点的权值分别为6，2，3，7，4，5，为其构造哈夫曼树，并求出它们的哈夫曼编码及带权路径长度。 * * 数据结构 图 练习 * 具有6个顶点的无向图至少应有_____条边才能确保是一个连通图。 N个顶点的连通图至少__________条边。 具有4个顶点的无向完全图有_____条边。，一个有n个顶点的无向图最多有___________条边。 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_____倍。 一个图中，所有顶点的度数之和等于所有边数的________倍。 n-1 6 n(n-1)/2 5 2 1 * 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是_____。 A. n B. (n-1)2 C. n-1 D. n2 对于一个具有n个顶点和e条边的无向图，若采用邻接表示，则表头向量的大小为__①___，所有邻接表中的结点总数是__②___。 ① A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e C. 2e D. n+e D A C * 已知一个图如下所示，若从顶点a出发按深度有哪些信誉好的足球投注网站法进行遍历，则可能得到的一种顶点序列为 __①___；按宽度有哪些信誉好的足球投注网站法进行遍历，则可能得到的一种顶点序列为__②__。 ① A. a,b,c,d,e,f B. a,c,f,d,e,b C. a,e,b,c,f,d D. a,e,d,f,c,b ② A. a,b,c,d,e,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b B B a b c e f d * 已知一有向图的邻接表存储结构如图所示。 根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是_____ A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5 C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2 根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是_____ A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v2 C B 4 Λ 1 2 Λ 3 5 3 2 4 Λ 4 5 Λ 2 4 Λ 1 2 3 4 5 * 采用邻接表存储的图的深度优先遍历算法类似于二叉树的_____。 A. 先序遍历 B.中序遍历 C. 后序遍历 D. 按层遍历 采用邻接表存储的图的广度优先遍历算法类似于二叉树的_____。 A. 先序遍历 B.中序遍历 C. 后序遍历 D. 按层遍历 在无权图G的邻接矩阵A中，若（vi,vj）或vi,vj属于图G的边集合，则对应元素A[i][j]等于_____，否则等于_____。 在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于_____。 D A 1 0 1 * 已知图G的邻接表如图1所示，其从顶点1出发的深度优先有哪些信誉好的足球投注网站序列为_______________，其从顶点1出发的宽度优先有哪些信誉好的足球投注网站序列为_________________。 1 2 3 6 5 4 1 2 5 4 3 6 * 已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是____________________________。 已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是____________________________。 求出下图中所有的拓扑序列。 求矩阵第i列非零元素之和 将矩阵第i行全部置0 1 2 3 4 5 6 7 8 * 分别使用Prim算法和Kruskal算法，画出求取最小生成树的过程 * * 在一个单链表中的p所指向结点之前插入一个指针s所指向的结点时，可执行如下操作： （1）s-next=_____; (2) p-next= s； (3) t= p-data； (4) p-data=_____； (5) s-data=_____； p-next s-data t * 在双向链表中，每个结点有两个指针域，一个指向_____