墨尔本大学COMP90038Assignment2课业解析

 题意：

对排序和查找算法进行分析  

解析：

 第一个题涉及一个特殊的链式结构，每个节点包含它的值和上下左右四个节点的信息，链表的节点值会有1/2的概率重复，将重复的节点接到原始节点后面，第一小问是实现InsertNode(x,u)函数，在节点u后插入值为x的新节点，第二小问是在O（m+n）时间内合并两个列表。第二个题是选出两个整数数组中的罕见数，其中第一种方法是基于预先排序的，即先将数组中的整数先进行排序，再找出罕见数，要求时间复杂度为O(nlogn)；第二种是创建一个哈希表，将元素一一放进哈希表中，这样就能够用O(n)的复杂度找出罕见数。 第三题是一个找寻最小子树的问题，找寻这颗树里面尴尬值最小的一个子树。这里可以用到先序遍历计算子节点对父节点的尴尬值的和，然后通过递归对左子树和右子树进行同样的操作，这样就能找到最小的尴尬值。

涉及知识点：

链表、哈希表、树、递归

更多可加微信讨论

微信号yzr5211234

pdf