2018年国家电网数据结构与算法试题(1)

设关键字序列(k1，k2，…，kn-1)是堆，设计算法将关键字序列(k1，k2，…，kn-1，x)调整为堆。

设计在二叉排序树上查找结点X的算法。

设计在链式存储结构上合并排序的算法。

下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。

下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。

设有向图G中的有向边的集合E={<1，2>，<2，3>，<1，4>，<4，5>，<5，3>，<4，6>，<6，5>}，则该图的一个拓扑序列为_________________________。

设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟简单选择排序后的结果为______________________。

设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟冒泡排序结束后的结果为_____________________。

设无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为_________；用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为_________。

设散列表的长度为8，散列函数H(k)=k % 7，用线性探测法解决冲突，则根据一组初始关键字序列(8，15，16，22，30，32)构造出的散列表的平均查找长度是________。