数据结构复习资料--覆盖所有知识点(3)

（1） 每个顶点的入/出度； 顶点 1 2 3 4 5 6 （2） 邻接矩阵； 入度 （3） 邻接表；

出度

（4） 邻接表定义：

typedef struct node {

int adjvex; //邻接点域，存放与Vi邻接的点在表头数组中的位置 struct node *next; //链域，指示下一条边或弧 }JD;

typedef struct node {

char vexdata[100]; //存放顶点信息 JD *firstarc; //指示第一个邻接点 }TD;

TD ga[MAX];

（5） 逆邻接表。

12. 下面的邻接表表示一个给定的无向图

(1) 给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列；（1）V1V2V4V3V5V6

(2)给出从顶点v1开始,对图G用广度优先搜索法进行遍历时的顶点序列。 11

（2）V1V2V3V4V5V6

13. 设无向图G（所下图所示），要求给出该图的深度优先和广度优先遍历的序列，找出下面网

络的最小生成树。

分别说明Huffman算法、Dijkstra算法、Prim算法、Kruskal算法的功能。

Huffman算法:求Huffman树（带权路径长度最短的二叉树） Dijkstra算法:求图中从某个源点到其余各顶点的最短路径 Prim算法:求最小生成树 Kruskal算法:求最小生成树 14. 已知图G如图所示。 （1） 画出图G的邻接表；

（2） 画出从顶点1出发的深度优先生成树和广度优先生

成树；

（3） 写出图G的拓扑排序列； 14.

12

15. 已知AOE网如下，试求其关键路径。要求写出计算过程。

16. 试利用Dijkstra算法求下图中从顶点a到其他个顶点间的最短路径，写出执行算法过程中各

步的状态。

13

17. 设一组记录的关键字为{4，5，7，2，1，3，6}，请回答相关问题：

（1）按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并

求出在等概率情况下查找成功的平均查找长度。

（2）按表中元素的顺序进行插入生成一棵AVL树，画出该树。并求出在等概率情况下查找成功的

平均查找长度。

18. 假定一个线性表为L=（18，75，60，43，54，90，46，31，58，73，15，34）进行散列存

储，采用的Hash函数为H（K）=K mod 13 ，当发生冲突时用线性探测法处理冲突，设Hash表的表长为13，试构造Hash表，并求出平均查找长度。

19. 序列{40，38，60，95，76，10，25，50，99}是堆吗？若不是，首先创建一个堆，然后用堆

排序方法进行从小到大排序。要求写出主要过程。

14

20. 给出如下关键字序列321，156，57，46，28，7，331，33，34，63试按链式基数排序方法，

列出一趟分配和收集的过程。

按LSD法 →321→156→57→46→28→7→331→33→34→63 分配 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 321 33 34 156 57 28 331 63 46 7

收集 →321→331→33→63→34→156→46→57→7→28

四、算法设计题

1. 从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变（采用顺序存储结构实现）。 Status deldup_sq(SqList &L){ int j=0,k;

if(L）length >0)

{ for(int i=1;ij) L.elem [++j]=L.elem [i]; } L.length =j+1; return OK; } else return ERROR;}

15