【1.设有一个含n个元素的数组,数组元素为自然数,写出一个算法,将所有值为素数的元素排在所有值为奇数的元素之前,将所有值为奇数的元素排在所有值为偶数的元素之前,要求该算法的时间复】
1人问答
问题描述：
1.设有一个含n个元素的数组,数组元素为自然数,写出一个算法,将所有值为素数的元素排在所有值为奇数的元素之前,将所有值为奇数的元素排在所有值为偶数的元素之前,要求该算法的时间复杂度为O(n).
2.编写一个算法判断无向连通图中是否有回路.
曹咏回答：
题1,
遍历数组,如素数添加到素数链表,如奇数添加到奇数链表,如偶数添加到偶数链表,最后合并三个链表
判断素数时可以先定义好允许范围内足够大的素数表,先查表判断,如超出表的范围,则从表中尝试选取例如50或100个不同的数利用费马小定理判断
题2,
设有i个节点,用2维数组V（i,i）表示图,用一维数组A(i)表示每个节点是否被访问,用队列L表示待访问列表
=>任选一个起始节点a,标记为已访问
=>将所有连通a的节点标记为已访问,并压入队列L,L中需要记录待访问节点名及其前溯（此处即a）
循环以下步骤：
从L中取出节点p,找到与p连通的非前溯节点,如这些节点已被访问,则存在回路跳出；
否则将这些节点标记为已访问并压入队列L（并记录其前溯p）,直至队列为空
其它推荐
其它推荐
最新更新
精品分类
优秀其它推荐
热门其它
邮箱： 