Com S 228 --- Introduction to Data Structures HOMEWORK 11: Test Preparation (File $Date: 1995/04/10 04:51:04 $) Due: problems 1 and 2, in your discussion section the week of April 13. (You'll probably want to do some of the other problems before April 18, but these problems are not to be handed in.) This homework is a review for the test on Tuesday, April. 18. The readings are those from the syllabus in the units: Records & Variants, Pointers & Dynamic Data, and Linked Lists. The collected readings are thus as follows. (The DD readings are only recommended, the HR readings are the essential ones.) HEADINGTON & RILEY: 5, 7, 8 DEITEL & DEITEL: 16.2-4, 18.12, 5, 7.5-6, 15.4 Topics for the test are as follows: - C++ structs - purpose, when to use classes vs. structs - client code - meaning of default assignment operator and copy constructor - parameter passing with structs - type equality - nested data structures - declarations - client access to parts - variants - purpose, when to use - client code - storage costs - safety issues - pointers - purpose, when to use (and when to use vs. references) - drawing pictures - meaning of declarations (including using const) - pointer arithmetic - relationship to arrays - dynamic data - purpose, when to use - how to use operators new and delete - pitfalls: dangling pointers (and references), memory leaks - how to write classes with dynamic data - destructors - deep copy in assignment operator and copy constructor - linked lists - pointers and structs - writing code with the dynamic data implementation of singly-linked lists - variations on singly-linked lists - head nodes - doubly linked lists - circular lists - array implementation - managing the free store (heap) The material on "C++ structs" and "nested data structures" is foundational (important and used in the rest of the topics). I'd rank the importance of the other topics as follows. Important: 1. Pointers (including dealing with C++'s type char *) 2. Dynamic data used to implement classes (such as String) 3. singly-linked lists and doubly-linked lists 4. variants Less important: - variations on singly-linked lists: head nodes and circular - array implementation of linked lists 1. (10 points) For each of the specific topics above, write down where you think they would appear on the test. That is group the topics above as to where in the four problem kinds listed below they are to appear. (So your answer for this problem is a list with parts numbered 1 to 4.) (1) an easy problem, perhaps a brief essay answer in English to a conceptual question, or a simple function to implement. (2) a short programming or conceptual problem, probably implementing some function, probably on one of the topics of lesser importance. (3) a medium-sized programming problem, probably not involving a class, but involving pointers in some way. (4) a harder problem, perhaps one that combines several topics into one. (An example of combining several topics was the "implement class CharStack using class CharList problem on the previous test.) This should be on an important topic or combination of important topics. You will receive full credit for handing in your list, with solved problems. We will not grade this, except to see that you made an honest effort. In your discussion section, you'll discuss your list with the others and with the class as a whole. 2. (50 points) Design a practice test consisting of four (4) problems (of the kind described above in problem 1 of this homework). Write out the problems with the kind of detail seen on previous tests. Don't make the problems too easy, it's best to actually pick topics that (a) are important, and (b) are something you feel a bit unsure about. (If you are stumped, you can use some of the suggested practice problems.) See the appendix below for the subset of C++ you will be able to use on the test, and for the parts of C++ you may *not use on the test. (Don't copy these onto the test you create, although they will appear on the real test cover.) Then take 50 minutes, and write out the practice test by hand on paper. Do *not* use a computer for this, this is to be handwritten only! Hand in your handwritten work on paper, a printout is *not* acceptable. (You can save a photocopy of your work, or type it in as part of problem 2.) You will receive full credit for handing in your test, with solved problems. We will not grade this, except to see that you wrote something out by hand, and that you made an honest effort of it. In your discussion section, you'll see what problems others made up, and will have an opportunity to ask questions and discuss solutions with the class as a whole. We won't check the details of your work (see problem 3 below). 3. (suggested practice) Check your answers to the practice test on the computer. You will have to write test harnesses for some of the problems. 4. (suggested practice) If you haven't done the suggested practice problems from homeworks 8-10, now is the time to do them. They will make good practice for the test. APPENDIX: directions about C++ that will appear on the test. Subset of C++ You May Use You may use recursion on this test. Unless otherwise stated in a problem, when solving problems you may only use standard features of the language that we discussed in class, classes and utilities we discussed in class, and helping functions that you define yourself. So for headers, you may only use macros, objects, and functions declared in the following header files (see HR appendix G, DD appendix B). "Deallocate.h" "IntFlexVec.h" "String.h" "ask_yn.h" "bool.h" "clist.h" "cqueue.h" "cset.h" "cstack.h" "password.h" "pretend_bool.h" "prompt.h" "rand2.h" "swap.h" "vector.h" Parts of C++ You May *Not* Use Unless otherwise stated in a problem, you are prohibited from using derived classes (don't worry if you don't know what that is) and the following C++ keywords. asm catch goto template throw try virtual