题目内容
(请给出正确答案)
[主观题]
试修改起泡排序算法,在正反两个方向交替进行扫描,即第一趟把排序码最大的元素放到序列的最后,第二趟把排序码最小的元素放到序列的最前面。如此反复进行。
查看答案
如果结果不匹配,请 联系老师 获取答案
A.±360°
B.±540°
C.±720°
D.±180°
a)试按照以上思路,实现一个排序算法:
b)你的这一算法,时间和空间复杂度各是多少?
c)改进你的算法,使之能够在O(n+M)时间内对来自[0,M)范围内的n个整数进行排序,且使用的辅助空间不超过O(M)。
a)试证明,在后一类树中,新成员的权重(频率)总是最大;
b)试利用以上性质设计一个算法,在O(n)时间内完成Huffman编码。
试扩充深度优先搜索算法,在遍历图的过程中建立生成森林的子女-兄弟链表。算法的首部为其中,指针t指向生成森林上具有图顶点v信息的根结点。(提示:在继续按深度方向从根v的某一未访问过的邻接顶点w向下遍历之前,建立子女结点。但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树)