发布时间 : 星期一 文章数据结构习题集与实验指导更新完毕开始阅读1112372ef5ec4afe04a1b0717fd5360cbb1a8d68
. Vex 0 lowcost Vex 0 lowcost Vex 0 lowcost Vex 0 lowcost 邻接表为： a b c d e f g h 0 0 d 7 0 0 d 7 0 0 f 3 0 0 0 d d 0 6 5 g 0 2 0 0 0 0 0 0 0 {a,c,b,d ,h } {e,f,g } {a,c,b,d ,h ,g} {a,c,b,d ,h ,g, f } {a,c,b,d ,h ,g, f, e } 5 5 7 3 2 6 6
{ f,e } {e } { } → b 4 → c 3 → a 4 → c 5 → a 3 → b 5 → b 5 → c 5 → b 9 → d 7 → d 6 → e 3 → d 5 → f 2 → c 5 → d 4
→ d → d → e → f → g → h → g → e → h → f ^ ^ ^ ^
9 ^ 5 ^
6 → g 5 → h 4^ 克鲁斯卡尔算法步骤 (按边归并,堆排序)： 先罗列：f---2---g a—3--c f—3—e a—4---b d—4—h
(a,b,c) (e,f,g) (d,h) 取b—5—d, g—5--d 就把三个连通分量连接起来了。
3.已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
4.试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。
解：最短路径为：（a,c,f,e,d,g,b）
.
.
四、给定下列网G:
1 试着找出网G的最小生成树，画出其逻辑结构图； 2 用两种不同的表示法画出网G的存储结构图；
3 用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。 解：1. 最小生成树可直接画出，如右图所示。 2. 可用邻接矩阵和邻接表来描述：
??12??4????12?20?89??????20?15??12??? ??15???10???48???6?????9??6????????1210?????A B———————C E————F G————D 注：用两个数组分别存储顶点表和邻接矩阵 #define INFINITY INT_MAX //最大值∞ #define MAX_VERTEX_NUM 20 //假设的最大顶点数（可取为7） Typedef enum {DG, DN, AG,AN } GraphKind; //有向/无向图，有向/无向网Typedef struct ArcCell{ //弧（边）结点的定义 VRType adj; //顶点间关系，无权图取1或0；有权图取权值类型 InfoType *info; //该弧相关信息的指针 }ArcCell, AdjMatrix [ MAX_VERTEX_NUM ] [MAX_VERTEX_NUM ]; Typedef struct{ //图的定义 VertexType vexs [MAX_VERTEX_NUM ] ; //顶点表，用一维向量即可 AdjMatrix arcs; //邻接矩阵 邻接表为： a b c d e f g → b 12 → a 12 → b 20 → c 15 → a 4 → b 9 → c 12 → e 4 → c 20 → d 15 → g 10 → b 8 → e 6 → d 10 ^
8 12 6
^ ^
→ e → g ^ ^
→ f → f 9 ^
五、算法设计题
1试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w) ，即删除一条边的操作。（如果要删
.
.
除所有从第i个顶点出发的边呢？ 提示： 将邻接矩阵的第i行全部置0 ） 解：//本题中的图G均为有向无权图。
Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w) {
if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[i][j].adj) {
G.arcs[i][j].adj=0; G.arcnum--; }
return OK; }//Delete_Arc
2试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。 int visited[MAXSIZE]; //指示顶点是否在当前路径上 int level＝1;//递归进行的层数
int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 {
if(i==j) return 1; //i就是j else {
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc，level--) { level++;
k=p->adjvex;
if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径
}//for }//else
if (level==1) return 0; }//exist_path_DFS
3.邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。
（注1：一条路径为简单路径指的是其顶点序列中不含有重现的顶点。
注2：此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。） int visited[MAXSIZE];
int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G 的顶点i到j是否存在长度为k的简单路径 { {
if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 else if(k>0) {
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
.
.
{
l=p->adjvex; if(!visited[l])
if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for
visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else
return 0; //没找到 }//exist_path_len
第八章 查找
一、填空
1. 2. 3. 4.
从二叉搜索树中查找一个元素时，其时间复杂度大致为_ O(log2n) _______。 2．在一棵高度为5的理想平衡树中，最少含有__16__个结点，最多含有__31_个结点。 3．以二分查找方法从长度为12的有序表中查找一个元素时，平均查找长度为__37/12_。
4．在线性表的散列存储中，装填因子又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则等于___ n/m _。
5. 5．在一棵m阶B_树上，每个非树根结点的关键字数目最少为__ m/2-1_个，最多为__ m-1___
个，其子树数目最少为_ m/2__，最多为_ m 。
二、算法填空
向以BST为树根指针的二叉搜索树上插入值为item的结点的递归算法。 void Insert(BTreeNode*& BST, const ElemType& item) {
if(BST==NULL)
{ BTreeNode* p=new BTreeNode; p->data=item;
____ p->left=p->right=NULL___; BST=p; }
else if(item
三、问答
1．已知一个散列表如下图所示： 35 20 33 48 59
.