《数据结构》02272国开形考任务(1-4)试题解析及答案

《数据结构》02272国开形考任务(1-4)试题解析及答案数据结构02272国开形考任务(1-4)试题解析及答案任务1题目解析题目要求实现一个二叉树的前序遍历算法，并给出遍历结果。答案defpreorder_traversal(root):result=[]ifroot:result.append(root.val)result+=preorder_traversal(root.left)result+=preorder_traversal(root.right)returnresult示例用法root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)print(preorder_traversal(root))任务2题目解析题目要求实现一个链表的插入排序算法，并给出排序结果。答案classListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefinsertion_sort(head):ifnotheadornothead.next:returnheaddummy=ListNode(0)dummy.next=headcurr=head.nexthead.next=Nonewhilecurr:prev=dummywhileprev.nextandprev.next.val<curr.val:prev=prev.nexttemp=currcurr=curr.nexttemp.next=prev.nextprev.next=tempreturndummy.next示例用法head=ListNode(4)head.next=ListNode(2)head.next.next=ListNode(1)head.next.next.next=ListNode(3)sorted_head=insertion_sort(head)whilesorted_head:print(sorted_head.val)sorted_head=sorted_head.next任务3题目解析题目给出一个有向图的邻接矩阵表示方式，要求实现一个深度优先搜索算法，并给出搜索结果。答案defdfs(adj_matrix,start_node):visited=set()result=[]stack=[start_node]whilestack:node=stack.pop()ifnodenotinvisited:visited.add(node)result.append(node)forneighborinrange(len(adj_matrix)):ifadj_matrix[node][neighbor]==1andneighbornotinvisited:stack.append(neighbor)returnresult示例用法adj_matrix=[[0,1,1,0],[1,0,0,1],[1,0,0,0],[0,0,1,0]]start_node=0print(dfs(adj_matrix,start_node))任务4题目解析题目给出一个有向图的邻接矩阵表示方式，要求实现一个广度优先搜索算法，并给出搜索结果。答案fromcollectionsimportdequedefbfs(adj_matrix,start_node):visited=set()result=[]queue=deque([start_node])whilequeue:node=queue.popleft()ifnodenotinvisited:visited.add(node)result.append(node)forneighborinrange(len(adj_matrix)):ifadj_matrix[node][neighbor]==1andneighbornotinvisited:queue.append(neighbor)returnresult示例用法adj_matrix=[[0,1,1,0],[1,0,0,1],[1,0,