Question

跪求这两道数据结构题的答案！谢谢大家了

1.设有一个含n个元素的数组，数组元素为自然数,写出一个算法，将所有值为素数的元素排在所有值为奇数的元素之前，将所有值为奇数的元素排在所有值为偶数的元素之前，要求该算法的时间复杂度为O(n)。
2.编写一个算法判断无向连通图中是否有回路。

Answer 1

题1，
遍历数组，如素数添加到素数链表，如奇数添加到奇数链表，如偶数添加到偶数链表，最后合并三个链表
判断素数时 可以先定义好允许范围内足够大的素数表，先查表判断，如超出表的范围，则从表中尝试选取例如50或100个不同的数利用费马小定理判断

题2，
设有i个节点，用2维数组V（i，i）表示图，用一维数组A(i)表示每个节点是否被访问，用队列L表示待访问列表
=>任选一个起始节点a，标记为已访问
=>将所有连通a的节点标记为已访问，并压入队列L，L中需要记录待访问节点名及其前溯（此处即a）
循环以下步骤：
从L中取出节点p，找到与p连通的非前溯节点，如这些节点已被访问，则存在回路跳出；
否则将这些节点标记为已访问并压入队列L（并记录其前溯p），直至队列为空