以下为《15级数据结构考试》的无排版文字预览,完整格式请下载
下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。
2、已知模式串P=“abaaba”和目标串T=“aabaaabba”,试计算模式串的next[0]至next[5]的值(含修正后的值),画出利用next数组实现模式串与目标串的匹配过程示意图。
3、已知一组外部结点的权为{10,8,3,4,12,13,16,12},试构造一棵带权外部路径长度之和最小的最优二叉树。
4、画出下列带权有向图的邻接多重表表示。
得分
四、算法填空题(共2小题,每小题10分,共20分)
1、Prim算法是求网络的最小代价生成树的方法,下面的声明给出了最小代价生成树边结点的结构,Prim算法实现时用一个一维数组T记录最小代价生成树的生长过程,请填写算法中的空框使算法正确。
typedef struct
{
int vi, vj; //边上两个顶点的编号,图中顶点编号为1,2,…,n
int weight; //边上的权
}edge;
edge T[n-1]; //记录最小代价生成树
void prim(void)
{
int m,v,min,max=32767,d; //假设边上的权不超过32767
edge e;
for(int j=1;j
以上为《15级数据结构考试》的无排版文字预览,完整格式请下载
下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。