True/False with justifications: Write out the word true or false in full, and th

Question

True/False with justifications: Write out the word true or false in full, and then write a brief but topical justification The justification is worth 2 of the 4 pts. for each question O (ns) 1. 999m2 +99n +9 2. If f(n) O (n)) and g (n) O(t(n)), then f(n) g(n) -O (n)) 3. If a class Foo has a field Bar* p, then the destructor Foo C) should always include the line delete p; 4. If a class Foo has a field vector elements; then the default assignment operator will copy the vector's pointers, but will not copy the Bar objects they point to. 5. If itr is a bi-directional iterator, then these lines always return the value of x. *itr++ x; *itr y return (--itr); 6. The middle element in an array with an odd number of elements can always be accessed in O(1) time. 7. The middle element in a doubly-linked list with an odd number of elements can always be accessed in O(1) time.

Explanation / Answer

1. False. Little-o notation states that f(n) must be less than g(n) for all k > 0. If we take k = 1, we have f(1) = 999(1)^2 + 99(1) + 9 = 1107 and g(1) = (1)^3 = 1, therefore f(n) is not less than g(n) for all k > 0.

2. True. f(n) + g(n) = O(t(n) + t(n)) = O(2t(n)) = O(t(n))

3. False. The only time you would need to delete the pointer in the destructor is if the pointer was pointing to a dynamically allocated object and it was the responsibility of the Foo class to clean that memory up. We can have pointers to other things that are not dynamically allocated, for example, p could contain the address of another field of Foo, such as an int, which is not dynamically allocated. This means we would not need to delete p when the object is being destroyed.

4. True. The default assignment operator of a class will copy the vector<Bar*>, which will in turn copy only the values of the pointers it contains. This means we will have two vectors each with pointers that point to the same Bar objects in memory.

5. True. We are using the post-fix increment operator in the first statement, which returns a copy of the original pointer value in itr. We then dereference it, and assign it the value x. In the second statement, we are dereferencing the incremented pointer and assigning it a value of y. The third statement uses the pre-fix decrement operator which first decrements the itr pointer. We dereference the decremented pointer value and return it. This means that we will be returning the value x.

6. True. Arrays are stored contiguously in memory and we can use pointer arithmetic to calculate the address of the middle element which takes constant time.

7. False. Linked lists are not stored contiguously in memory like arrays are, meaning that we must traverse the list in order to know which element is next. This means that we cannot possibly calculate the address of the middle element as we did with arrays, because each element can be stored at an arbitrary address. This means that it will take O(n) time to find the middle element where n is the number of elements in the linked list.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.