” 辅导ECS 32B程序、 写作Data Structures编程ECS 32B Introduction to Data StructuresHomework 04Due: Friday, May 14, 2020, 5:00pm PSTImportant: You may upload as many times as you want before the deadline. Each time the autograder will letyou know how many of the test cases you have passed/failed. To prevent people from manipulatingthe autogader, the content of some test cases are hidden. Please do not copy others Answers. Autograder can detect similar code.Problem 1 (5 points)For Problem 2 in Homework 03, the recursive version of transform can be written as:1 def transformRecursive ( lst ) :2 if not lst :3 return []4 return [ lst . val ] + transformRecursive ( lst . next )Let head be the head of the linked list 10 6 3 13 2. Visualize the call transformRecursive(head)using the activation stack model; and the substitution model.(Please follow the definiton Of transformRecursive above instead of your own version in homework 03.)Problem 2 (5 points)For Problem 3 in Homework 03, the recursive version of concatenate can be written as:1 def concatenateRecursive ( lst1 , lst2 ) :2 return concatenateRecursive_helper ( lst1 , lst2 , lst1 )34 def concatenateRecursive_helper ( lst1 , lst2 , cur ) :5 if not lst1 :6 return lst27 if not cur . next :8 cur . next = lst29 return lst110 return concatenateRecursive_helper ( lst1 , lst2 , cur . next )1Let head1 be the head of the linked list 8 20 4 5 10, and head2 the head of the linked list7 2 3. Visualize the call concatenateRecursive(head1, head2) using the activation stack model; and the substitution model.(Please follow the definiton of concatenateRecursive above instead of your own version in homework 03.)Problem 3 (28 points)1. (8 points) Suppose we have a hash table of size 29 and we want to implement a system for lookingup a friends information given his/her name. Which of the following hash functions is the best(none of them is perfect)? Justify your choice. (Assuming none of the names is empty.)(a) h(x) = x(b) h(x) = len(x) % 29(c) h(x) = 29(d) h(x) =len(x)i=0ord(x[i]), where x[i] the ith character in x, and ord(c) returns the ordinal value of acharacter. (Instruction on the summation symbol httpss://www.mathsisfun.com/algebra/sigma-notation.html)2. (4 points each) Given a hash table with size 7, a hash function hash(x) = x % 7, and keys 5, 7, 14, 1,19, 21.(a) Hash the keys using Chaining to resolve collisions. Show your work.(b) Hash the keys using linear probing to resolve collisions. Show your work.(c) Hash the keys using quadratic probing to resolve collisions. Show your work.(d) Hash the keys using double hashing to resolve collisions. Suppose the second hash functionhash0(x) = 3 (x % 3). Show your work.(e) What is the load factor after the keys are hashed?Problem 4 (23 points)Download the run_sort.py, num1.txt, num2.txt, and num_sorted.txt files from Canvas Files Homework Homework 04.The run_sort.py file contains code to import data from num1.txt into a Python list, run Bubble sorton the Python list for 10 times, record the start and end time, and calculate how long it takes to run. Youmay run the file in your IDE directly. It might take a couple of minutes to run. Record the time it takesto run in Column 1, Row 1 in the table below.Then replace num1.txt by num2.txt and num_sorted.txt and fill in the rest of row 1 in the table.num1.txt and num2.txt contain a large amount of unsorted data, and num_sorted.txt containssorted data.2Replace the Bubble sort function by each of the sorting algorithms we have learned (use the code in thelecture slides, not the textbook), run the sorting algorithms on all the three text files one by one, and fillin the rest of the table. Also write what you think about the following questions: Which combination of sorting algorithm and data file runs fast and why? Which combination of sorting algorithm and data file runs slowest and why?The functions for merge sort and quick sort are recursive. You will notice that Python throws a RecursionError,saying maximum recursion depth exceeded in comparison. To allow more recursion calls, youmay add1 import sys2 sys . setrecursionlimit (20000)at the top.Sorting Algorithm Num1.txt num2.txt num_sorted.txtBubble sortShort BubbleSelection sortInsertion sortMerge sortQuick sortProblem 5Given a sorted (in ascending order) Python list of distinct integers, return all the indices i such that theelements at index i equals i. There may be more than one such index, so the return type is a Python listcontaining all indices that satisfy the criteria.Write two functions for the same problem. The first function, linearSearchValueIndexEqual, uses linearsearch, and the second function, binarySearchValueIndexEqual, uses binary search. The test cases for thetwo functions in Gradescope are the same.When the input list is empty, return an empty list.Examples: Input: [0, 2, 5, 7]Output: [0]Explanation: The element at index 0 is 0, so the value equals its index. Input: [-5, 1, 2]Output: [1, 2]Explanation: The element at index 1 is 1, and the element at index 2 is 2.Problem 6Suppose you need to write an anonymous letter and disguise your handwriting. You decide to cutthe characters you need from a book and paste the characters on a paper to form the letter. (Note that3we mean a physical book and a physical letter, not digital.) Given the content of a book book and thecontent of the letter letter (each is reprented as a string), write a function anonymousLetter(book, letter)that determines if it is possible to write the anonymous letter using the book.Note: Your algorithm must use hashing (or dictionary in Python). The time complexity is O(max(m, n)), where m is the length of the book string and n is the lengthof the letter.Examples: Let the book be I am a Book. Not a letter. and the letter be I am a letter.anonymousLetter(book, letter) should return True. Let the book be I am a book. Not a letter. and the letter be I am a letter!anonymousLetter(book, letter) should return False. Let the book be abcde and the letter be abcdefanonymousLetter(book, letter) should return False.请加QQ:99515681 或邮箱:99515681@qq.com WX:codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助,或点击联系老师1对1在线指导。