Sample Data Structures Questions Chapter 3 Container Classes Data Structures and
ID: 3749270 • Letter: S
Question
Sample Data Structures Questions
Chapter 3
Container Classes
Data Structures and Other Objects Using C++
Fourth Edition
by Michael Main and Walter Savitch
ISBN 0132129485
The Purpose of These Questions
These are typical exam questions from Chapter 3 of the textbook. These exact questions might not be on your exam, but if you research and find the right answers to these questions, that should be good preparation for a real exam. (It's also possible that some of this material was not covered in your class.) At the moment there are 6 short answer questions and 15 multiple choice questions in this file.
Short Answers
Short Answers
Section 3.1
The Bag ADT
The bag class has a member function with this prototype:
void insert(const value_type& entry);
Where is the value_type defined and why is it better to have such a definition (rather than just using an int)?
Suppose that you are storing a collection of items in a partially-filled array. You will declare the array and perhaps a constant to indicate the array's size. What else must you keep track of?
In Chapter 3, the CAPACITY of a bag is declared as a static member constant. In this context, what is the meaning of the word "static"?
Help! I have written the following for-loop to print 42 Ouches, but it's not working as I intended. Why?
std::size_t i;
for (i = 41; i >= 0; --i)
cout << "Ouch!" << endl;
Short Answers
Section 3.2
The Sequence ADT
Suppose that I have the following declarations:
int data[100];
size_t i;
Write a small segment of C++ code that will shift data[50]...data[98] up one spot to the locations data[51]...data[99]. Then insert the number 42 at location data[50].
Suppose that I have the following declarations:
int data[100];
size_t i;
Write a small segment of C++ code that will shift data[51]...data[99] down one spot to the locations data[50]...data[98]. The value of data[99] remains at its original value.
Multiple Choice
Multiple Choice
Section 3.1
The Bag ADT
For the bag class in Chapter 3 (using a fixed array and a typedef statement) what steps were necessary for changing from a bag of integers to a bag of double values?
A. Change the array declaration from
int data[CAPACITY] to double data[CAPACITY] and recompile.
B. Change the int to double in the typedef statement and recompile.
C. Round each double value to an integer before putting it in the bag.
D. Round each double value to an integer after taking it out of the bag.
Who needs to know about the invariant of an ADT?
A. Only the programmer who implements the class for the ADT.
B. Only the programmer who uses the class for the ADT.
C. Both the programmer who implements the class and the programmer who uses the class.
D. Neither the programmer who implements the class nor the programmer who uses the class.
Suppose that the bag is implemented with a fixed-size array. Which of these operations are likely to have a constant worst-case time?
A. insert
B. count
C. erase_one
D. None of (A), (B), and (C) have a constant worst-case time
E. TWO of (A), (B), and (C) have a constant worst-case time
F. ALL of (A), (B), and (C) have a constant worst-case time
Suppose that foo is a new class and you want to declare an array of 10 foo objects. Which constructor will be used to initialize the 10 foo components of the array?
A. Only the copy constructor can be used
B. Only the default constructor can be used
C. Any constructor can be used
Suppose that the bag class is efficiently implemented with a fixed array with a capacity of 4000, as in Chapter 3 of the class text. Choose the best description of b's member variables after we execute these statements:
bag b;
b.insert(5);
b.insert(4);
b.insert(6);
What will be the values of b.used and b.data after the statements?
A. b.used is 3, b.data[0] is 4, b.data[1] is 5, and b.data[2] is 6
B. b.used is 3, b.data[0] is 5, b.data[1] is 4, and b.data[2] is 6
C. b.used is 3, b.data[0] is 6, b.data[1] is 4, and b.data[2] is 5
D. b.used is 3, b.data[0] is 6, b.data[1] is 5, and b.data[2] is 4
Suppose that the bag class is efficiently implemented with a fixed array with a capacity of 4000, as in Chapter 3 of the class text. We execute these statements:
bag b;
b.insert(5);
b.insert(4);
b.insert(6);
b.erase_one(5);
A. b.used is 2, b.data[0] is 4, b.data[1] is 6
B. b.used is 2, b.data[0] is 6, b.data[1] is 4
C. b.used is 3, b.data[0] is 4, b.data[1] is 6
D. b.used is 3, b.data[0] is 6, b.data[1] is 4
I have an array named data, which contains n integers. I want to print all of the numbers, starting at data[0]. BUT if the number 42 occurs, then I want to stop my printing just before the 42 (without printing the 42!) Here is most of my for-loop to accomplish my goal:
for (i = 0; ___________________________________________; i++)
cout << data[i] << endl;
What is the correct way to fill in the blank? (If there is more than one correct answer, please select E.)
A. (data[i] != 42) && (i < n)
B. (data[i] != 42) || (i < n)
C. (i < n) && (data[i] != 42)
D. (i < n) || (data[i] != 42)
E. More than one of the above answers is correct.
Suppose that you are working on a machine where arrays may have up to 4,000,000,000 items. What is the guaranteed range of the size_t data type?
A. Negative 4,000,000,000 to positive 4,000,000,000.
B. Zero to positive 32,767
C. Zero to positive 65,535
D. Zero to 4,000,000,000
E. Zero to 8,000,000,000
Multiple Choice
Section 3.2
The Sequence ADT
In Chapter 3, there was a suggested implementation of the sequence class with a fixed CAPACITY and these private member variables:
class sequence
{
public:
typedef double value_type;
typedef std::size_t size_type;
static const size_type CAPACITY = 30;
...
private:
value_type data[CAPACITY];
size_type used;
};
The sequence's constructor sets used to zero, but does not place any values in the data array. Why?
A. Integer arrays are automatically initialized to zero.
B. The first activation of insert or attach initializes the entire array.
C. The array initialization was part of the project that was left to the student.
D. The programmer who uses the sequence is responsible for initializing the array.
E. When a sequence is first created, none of the array is being used.
This question is appropriate if you implemented the sequence class. The sequence's insert member function normally puts a new item before the current item. What does insert do if there is no current item?
A. The insert precondition is violated.
B. The new item is put at the beginning of the sequence.
C. The new item is put at the end of the sequence.
D. None of the above.
Suppose that the sequence is implemented with a fixed-size array. Which of these operations are likely to have a constant worst-case time?
A. insert
B. count
C. erase_one
D. None of (A), (B), and (C) have a constant worst-case time
E. TWO of (A), (B), and (C) have a constant worst-case time
F. ALL of (A), (B), and (C) have a constant worst-case time
Suppose the bag and sequence are both implemented with a fixed-size array as in Chapter 3. What is the difference between the private member variables of the bag and the private member variables of the sequence?
A. The bag has an extra array of Items.
B. The bag has one extra size_t variable.
C. The sequence has an extra array of Items.
D. The sequence has one extra size_t variable.
Suppose that the bag and the sequence have both been implemented with partially filled arrays. Which statement is true about the worst-case run time of the erase_one operations.
A. Both removal functions have constant worst-case run times.
B. The bag's removal is constant time, but the sequence's removal is not.
C. The sequence's removal is constant time, but the bag's removal is not.
D. Neither removal function has constant worst-case run time.
Suppose that the bag is implemented with a fixed-size array. Which of these operations are likely to have a constant worst-case time?
A. insert
B. count
C. erase_one
D. TWO of the above are likely to have a constant worst-case time.
D. ALL of (A), (B), and (C) are likely to have a constant worst-case time.
Multiple Choice
Section 3.3
Interactive Test Programs
What is the best C++ statement to use when a program must choose between several alternatives that are controlled by the value of a single variable?
A. do-while statement
B. for-statement
C. if-else statement
D. switch statement
E. while statement
Data Structures and Other Objects Using C++
Michael Main (main@colorado.edu)
and
Walter Savitch (wsavitch@ucsd.edu)
Thank you for visiting http://www.cs.colorado.edu/~main/questions/chap03q.html
Copyright © 2000 Addison-Wesley Computer and Engineering Publishing Group
Short Answers
Section 3.1
The Bag ADT
Explanation / Answer
Question 1) The bag class has a member function with this prototype:
void insert(const value_type& entry);
Where is the value_type defined and why is it better to have such a definition
Answer 1) The value_type is defined in the template above the function definition.
It is a better approach because the method is now generic in nature and can accept arguments of type int, double, string, etc, whereas using just int would not allow this method insert to accept argument of other type.
Question 2) Suppose that you are storing a collection of items in a partially-filled array. You will declare the array and perhaps a constant to indicate the array's size. What else must you keep track of?
Answer 2) Along with this data, we would also need to maintain the count of items stored in the partially-filled array. We would need to increment this count whenever we insert an element into the array and decrement it whenever we remove an element from the list.
Question 3) In Chapter 3, the CAPACITY of a bag is declared as a static member constant. In this context, what is the meaning of the word "static"?
Answer 3) Static is a keyword in C++ used to give special characteristics to an element. Static elements are allocated storage only once in a program lifetime in static storage area. And they have a scope till the program lifetime. Hence, the static variable CAPACITY can be used through out the code and it is shared among all the objects of class Bag.
Question 4)
Help! I have written the following for-loop to print 42 Ouches, but it's not working as I intended. Why?
std::size_t i;
for (i = 41; i >= 0; --i)
cout << "Ouch!" << endl;
Answer 4) The size_t type is meant to specify the size of something so it's natural to use it.
But loops like:
for (i = 41; i >= 0; --i)
will cause an infinite loop due to the wrapping behaviour of unsigned values. This can also be alleviated by the (slightly harder to understand but at least immune to wrapping problems):
By shifting the decrement into a post-check side-effect of the continuation condition, this does the check for continuation on the value before decrement, but still uses the decremented value inside the loop.
NOTE: As per Chegg policy, I am allowed to answer only 4 questions on a single post. Kindly post the remaining questions separately and I will try to answer it. Sorry for the inconvenience caused.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.