数据结构与算法题库(2)

20.利用Dijkstra算法计算下图中从顶点A到其余各顶点的最短路径。

4B 15 2 A 12 5 D F 3 C 4 10 6 8 E 9 G 已知一个AOE网如下图所示，试计算出该图的关键路径。 21. 用迪杰斯特拉算法求下图中从a到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其长度。 10 20 b 30 a 60 c 40 65 15 f 20 80 d e 35

22. 用迪杰斯特拉算法求下图中从A到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其长度。

23. 已知一组关键字序列12, 23, 45, 57, 20, 3, 78, 31, 15, 36，哈希函数为H(Key) = Key % 13 (1) 利用开放定址法的线性探测再散列解决冲突，构造长度为15的哈希表，计算平均查找长度ASL； (2) 利用链地址法解决冲突，构造长度为10的哈希表，计算平均查找长度ASL；

24．设哈希表长度为10，哈希函数为H(Key) = Key Mod 7，关键字集合为{15，10，12，20，25，35，31，18}。 （1）利用开放定址法的线性探测再散列解决冲突，构造哈希表，计算平均查找长度ASL。 （2）利用链地址法解决冲突构造哈希表，计算平均查找长度ASL。

25.已知一组数据的关键字为（22，41，53，46，30，13，1，67），哈希函数为 H(Key) = (3 Key) % 11，哈希表长度为11。 1）用开放定址法的线性探测在散列解决冲突，构造哈希表，计算平均查找长度ASL。 2）利用链地址法解决冲突构造哈希表，计算平均查找长度ASL。

26. 已知一棵平衡排序二叉树如下图所示：

45

56 72 16 26 78 40 66 90 （1）在上图中若插入结点60后，二叉排序树平衡吗？若不平衡，则属于哪种不平衡类型，并对其进行平衡化处理（画出最后的平衡二叉排序树）。

（2）在上图中若插入结点70后，二叉排序树平衡吗？若不平衡，则属于哪种不平衡类型，并对其进行平衡化处理（画出最后的平衡二叉排序树）。

27. 已知一棵平衡排序二叉树如下图所示

45

78 26

16 40 66 90 56 72 （1）在上图中若插入结点60后，二叉排序树平衡吗？若不平衡，则属于哪种不平衡类型，并对其进行平衡化处理（画出最后的平衡二叉排序树）。 （2）在上图中若插入结点70后，二叉排序树平衡吗？若不平衡，则属于哪种不平衡类型，并对其进行平衡化处理（画出最后的平衡二叉排序树）。

28. 已知一个空的二叉排序树，按照下面的要求画出新的二叉排序树。 （1）设查找序列关键字为{70，30，100，25，85，63，96，125，47，117}，画出生成的二叉排序树T。 （2）画出T删除关键字为47结点后的二叉排序树。 （3）画出T删除关键字为85结点后的二叉排序树。 （4）画出T删除关键字为100结点后的二叉排序树。

29. 已知一个待排序序列为{12, 2, 16, 30, 14, 8}，请按照下面的排序方法写出每一趟排序的序列。 (1)直接插入排序 (2)气泡排序 30. 已知一个待排序序列为（49，38，65，97，76，13，27，50）。 ，请按照下面的排序方法写出每一趟排序的序列。 (1)简单选择排序 (2)气泡排序

31.已知一个序列： （49，38，65，97，76，13，27，50）。

(1) 请写出以49位轴的一趟快速排序后的序列。 (2) 请写归并排序的每一趟过程序列。

32. 已知一个序列：

（05，56，20，23，40，38，29，61，35，76，28，100）。 （1）将这个序列调整成小顶堆；

（2）用堆排序方法计算出前三个最小的元素（要求画出已经调整成堆的二叉树的最后状态

图）。

33. 已知一个序列：

（49，38，65，97，76，13，27，50）。 （1）将这个序列调整成小顶堆；

（2）用堆排序方法计算出前三个最小的元素（要求画出已经调整成堆的二叉树的最后状态图）。

34. 已知关键字序列为{326，259，369，924，726，479，568，25，8}。 （1）将其调整成堆。

（2）画出前2趟推排序状态图。（画出已经调整成堆的二叉树的最后状态图）。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构与算法题库(2)在线全文阅读。