CSCI 262 Data Structures Sample Exam 1 Problem 1 20 5 4 points Circle the answer which best matches the term or concept a Abstract data type i A general speci cation of the interface for a type specifying domain principal behaviors and possibly performance characteristics ii A de nition of a library class including public and private member variables methods and constructors iii A type speci cation for a theoretical type which has no practical application or implementa tion used for thought experiments in type theory i A last in rst out LIFO data structure ii A rst in rst out FIFO data structure iii A delicious dish best served with coleslaw and hushpuppies i An operator used to insert items into a set or map ii An operator used to access member variables and methods in an object pointed to by the left iii An operator used to subtract and then compare the left operand with the right operand b Queue c operand d Heap e Dereferencing i The list of classes which are ancestors of a class in an inheritance hierarchy ii A variant of a stack in which items are stored in an inverted tree iii The region of memory where dynamically allocated objects and arrays live i Taking the address of a variable using the operator ii Getting the value pointed to by a pointer using the operator iii Releasing the memory of a dynamically allocated object back to the heap Answer a i b ii c ii d iii e ii 1 Problem 2 10 5 5 points Find the bug Circle the one choice which best describes the bug in each code fragment below a 1 2 3 4 5 6 7 8 9 10 b 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 vector string foo foo add apple foo add pear foo add peach for int i 0 i foo size i cout foo i is of length cout foo i length endl i In lines 8 and 9 the expression foo i is illegal because foo is not an array ii In line 8 the code will attempt to reference foo 0 which is out of bounds iii In line 8 the code will attempt to reference foo 3 which is out of bounds iv In line 9 cannot call a function length on an element of a vector must remove the element from the vector rst Answer iii int r a n d 1 0 0 0 int ans 1000 for int i 0 i 1000 i ans i rand return ans int main while true return 0 int dist r a n d 1 0 0 0 double sum 0 0 for int i 0 i 1000 i sum dist i cout Average is sum 1000 endl i The function rand1000 returns a pointer to a locally stack allocated array This could cause a memory exception when the pointer is used in main ii The function main never calls delete to clean up the array dist This will cause a memory iii In line 12 division by an integer value will cause truncation in the result iv The code in line 14 is never reached leak Answer i 2 Problem 3 20 10 10 points a Write the function word count whose header is given below This function returns the number of occurrences of a word in a vector of strings For example if animal list is the vector shown below the call word count animal list dog should evaluate to 2 since dog appears twice vector string animal list bird cat dog bird cat mouse bird dog int w o r d c o u n t const vector string words string word Answer int count 0 for string s words if s word count return count b Write the function modal value whose header is shown below This function returns the string that occurs most frequently in its parameter words If there are ties i e more than one string occurs most frequently return any maximally occurring string If the vector is empty return an empty string For example if animal list is the vector shown on the previous problem the call modal value animal list should return bird since bird occurs more often than any other string in list In writing modal value you can if you wish call function word count from part a Assume that word count works as speci ed regardless of what you wrote for part a string m o d a l v a l u e const vector string words Answer if words empty return int most 0 int mode for string s words int wc w o r d c o u n t s if wc most most wc mode s return mode 3 Problem 4 10 points For this problem refer to the diagram of a stack string below left This stack initially has three elements apple pear and peach assuming the stack is named fruit draw the stack after the push and pop operations shown below right fruit push cherry fruit pop fruit pop fruit push guava fruit push banana fruit push papaya fruit push quince fruit pop fruit push s t r a w b e r r y fruit pop fruit pop Answer banana guava pear apple 4 Problem 5 10 5 5 points For each program write down what the program outputs to stdout a class dog public void speak int void dog speak int i if i 3 0 cout Woof else if i 3 1 cout Yelp else cout Arf cout endl int main dog d for int i 0 i 5 i d speak i return 0 Answer Woof Yelp Arf Woof Yelp b int main int ten 10 for int i 0 i 10 i ten i i int p ten while p ten 10 cout p p 2 cout endl p while p ten cout p p return 0 Answer 0 2 4 6 8 9 8 7 6 5 4 3 2 1 0 5 Problem 6 20 points Imagine that you re writing software that tracks families You have a map that maps each person by name to the name of their mother Write a function is female ancestor that takes in the map and two string parameters child and possible ancestor The function should return true if the possible ancestor is the child s mother or the child s mother s mother etc This question may be solved with recursion although it is not required You can assume the map is well formed e g does not have anybody as their own ancestor If the child is not a key in the map is female ancestor should return false Note that family histories only go back so far so eventually you may nd a mother in the map who s mother is not known e g Eve in the map below Example my mother map stores the following key value pairs Sharon Sharon Steve Jane Sharon Lisa Lisa Eve Then i s f e m a l …