CS163 Lab 1 Practice

CS163 Lab #1 – Practice Questions Work on these after finishing the lab or to practice outside of Lab Practice LLL: The following questions should be implemented on a continual basis to prepare for your midterm proficiency demo. Start by implementing these iteratively, then implement each recursively. We suggest working in the CS163/mpdemo directory for these. After completing each of these, re-examine each with a tail pointer. Implement them first iteratively and then follow that with recursive solutions! Make sure you can draw the pointer diagram for each of the above! a. Solve each Iteratively b. Solve each Recursively c. Double check that each path through the function returns the correct value if you implement this with more than a single return statement in the function d. Make sure when calling the function that the returned value is being used! Level 1 - Introductory 1. Display the contents of all of the data in a linear linked list. • Return the number of items displayed 2. Display just the last piece of data in a linear linked list • Return the data displayed 3. Display the last two items in a linear linked list • Return the sum of the last two items 4. Display the last item in a linear linked lists, but only if it isn’t a 2 • Return the number of items displayed (0 or 1) 5. Add a node at the beginning of a non-empty linear linked list. 6. Add a node to the end of a linear linked list. • Return the number of items in the list, after the new node was added 7. Count the number of nodes in a linear linked list • Return the count 8. Remove just the last node in a linear linked list • Return the data of the “new” last node in the list Lab #1 - Linear Linked Lists – Page 1

Level 2 - Intermediate 9. Move the first node and add it to the end of a linear linked list • Return the sum of all the data in the list 10. Duplicate the first node and place it at the end of a linear linked list • Return the sum of the last two nodes in the list 11. Remove all BUT the last node in a linear linked list • Return the sum of all of the data in the list 12. Remove the last two nodes from a linear linked list • Return the new last node’s data value 13. Count the number of values smaller than 10 in a linked list of numbers • Return the count Level 3 - Proficient 14. Copy the contents of a linear linked list and make a new linear linked list • Return the number of items in the new list 15. Copy the contents of a linear linked list and place the data into an array. • Return the number of items copied Lab 1 – Linear Linked Lists – Page 2

CS163 Lab #1 – Self-Check Quiz Test to see if you are ready with this material! Perform the following individually and “closed book, closed notes”. This will indicate if you have learned the necessary knowledge and skills from the lectures, readings, and lab: LLL Questions Level 1 - Introductory 1. True or False – Traversing a singly linked list from back to front is more convenient than traversing it from front to back 2. True or False - When we work with recursive data structure solutions, we need to pass at least head pointers to the public member functions of our classes 3. True or False - Inserting at the head is a special case but adding at the end with a tail pointer is not 4. Where in the list is it most efficient to add when we have a head but no tail? _____ 5. A tail pointer should be included when we are frequently __________ at the end Level 2 - Intermediate 6. Explain when a LLL would be a better data structure than a dynamically allocated array in terms of the following criteria: a. Memory:___________________________________________ b. Run time performance:________________________________ 7. Assume that we have a struct node. The data in the node is a dynamically allocated array of characters (called data). Our head pointer is set up to point to the first node. Answer each of the following: a. What is the data type of: *head _______________________ b. To access the data for the first node we say: ______________ c. To access the pointer to the next node:___________________ d. Explain what this means: *head.data____________________ What is being dereferenced?___________________________ Should there be parens? If so, where?____________________ What is the difference between *head->data?______________ Lab 1 – Linear Linked Lists – Page 3

8. With Lab#1 we had both a tail and head pointer for a linear linked list. Answer the following questions for this data structure: a. The constructor must set what pointers to NULL?_______________ b. The destructor must loop until what pointer is NULL?___________ c. The destructor must also make sure to set what pointer to NULL?_________ d. When inserting a node at the beginning, is tail affected?_________________ e. When adding a node at the end, is head affected?_______________________ 9. Write the code to count the number of times the first node’s data appears in a LLL; assume the data is a dynamically allocated array of characters. 10. Write the code to remove the first and last node in a linear linked list a. Would you have a tail pointer? ______________ b. Write the code: Level 3 - Proficient 11. Select the correct term for each of the following parallel activities Choices: thread, synchronization, data parallel, task parallel, pipelining, data race a. Performing two different tasks simultaneously ______________ b. Two tasks storing their answers in the same memory, running in parallel___________ c. Performing the same task on different data simultaneously_________ d. A task that can be performed in parallel_____________ e. Communication between tasks to determine when a task is done or needs a result_________________ Lab 1 – Linear Linked Lists – Page 4

Lab 1 – Linear Linked Lists – Page 5