15级数据结构考试

本文由用户“cs8960171”分享发布 更新时间:2023-01-04 15:39:19 举报文档

以下为《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级数据结构考试》的无排版文字预览,完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。

图片预览