《數(shù)據(jù)結(jié)構(gòu)》02272國開形考任務(wù)(1-4)試題解析及答案

《數(shù)據(jù)結(jié)構(gòu)》02272國開形考任務(wù)(1-4)試題解析及答案數(shù)據(jù)結(jié)構(gòu)02272國開形考任務(wù)(1-4)試題解析及答案任務(wù)1題目解析題目要求實現(xiàn)一個二叉樹的前序遍歷算法，并給出遍歷結(jié)果。答案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))任務(wù)2題目解析題目要求實現(xiàn)一個鏈表的插入排序算法，并給出排序結(jié)果。答案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任務(wù)3題目解析題目給出一個有向圖的鄰接矩陣表示方式，要求實現(xiàn)一個深度優(yōu)先搜索算法，并給出搜索結(jié)果。答案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))任務(wù)4題目解析題目給出一個有向圖的鄰接矩陣表示方式，要求實現(xiàn)一個廣度優(yōu)先搜索算法，并給出搜索結(jié)果。答案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,