- 2uestion 8 13 Points Purpose Students Will Practice The Following Skills Simple Recursion On Seqnode Chains Degr 1 (111.68 KiB) Viewed 46 times
2uestion 8 (13 points): Purpose: Students will practice the following skills: - Simple recursion on seqnode-chains. Degree of Difficulty: Moderate References: You may wish to reviow the following: - Chapter 19: Recursion Restrictions: This question is homework assigned to students and will be graded. This question shall not be distributed to any person except by the instructors of CMPT 145 . Solutions will be made available to students registered in CMPT 145 after the due date. There is no educational or pedagogical reason for tutors or experts outside the CMPT 145 instructional team to provide solutions to this question to a student registered in the course. Students who solicit such solutions are committing an act of Academic Misconduct, according to the University of Saskatchewan Policy on Academic Misconduct. Task overview In preparation for our up-coming unit on trees, where recursive functions are the only option, we will practice writing recursive functions using node chains. Note that the node ADT is recursively defined, since the next field refers to another node-chain (possibly empty). We are practicing recursion in using a familiar ADT, so that when we change to a new ADT, we will have some experience. Below are three exercises that ask for recursive functions that work on node-chains inot Linked Lists, and not Python lists). You MUST implement them using the node ADT (given), and you MUST use recursion (even though there are other ways). We will impose very strict rules on implementing these functions which will benefit your understanding of our upcoming work on trees. For ene-of-the these questions you are not allowed to use any data collections (lists, stacks, queues). Instead, recursively pass any needed information as arguments. Do not add any extra parameters. None are needed. Learn to work withing the constraints, because you will need ths skills! You will implement the following functions: (a) to_atring (node_chain): For this function, you are going to re-implement the to_string () operation from Assignment 5 using recursion. Recall, the function does not do any console output. It should tionally, for a completely empty chain, the to_string() should return the string EMPTY. (b) In Assignment 5, Question 2, we defined a function called check_chains (chain1, chain2). Its purpose was to examine 2 node-chains, and determine if they contained the same data. In this question. we're going to deal with a slightly simpler, but related, task. - check_chains (chain1, chain2) will return True if they have the same data values in the same order. - check_chains (chain1, chain2) will return False if there is any difference in the data values. You do not need to return the index where the two chains differ. This is supposed to be a simpler task! (c) copy(node_chain): A new node-chain is created, with the same values, in the same order, but it's a separate distinct chain. Adding or removing something from the copy must not affect the original chain. Your function should copy the node chain, and return the reference to the first node in the new chain. Note: Only a shallow copy is required; if data stored in the original node chain is mutable, it does not also need to be copied. (d) replace (node_chain, target, replacement): Replace every occurrence of the data target in node_chain with replacement. Your function should return the reference to the first node in the chain.
What to Hand In - A Python program named a7q8.py containing your recursive functions described above. - A Python script named a7q8_testing. py: include the cases above and tests you consider important. Be sure to include your name, NSID, student number, course number and laboratory section at the top of all documents. Evaluation - 2 marks: to_string (node_chain). Full marks if it is recursive, zero marks otherwise. - 2 marks: check_chains (chain1, chain2). Full marks if it is recursive. zero marks otherwise. - 2 marks: copy (node_chain). Full marks if it is recursive, zero marks otherwise. - 2 marks: replace(node_chain, target, replacement). Full marks if it is recursive, and if it works, zero marks otherwise. - 5 marks: Your functions are tested and have good coverage.