Introduction to Programming with C++, Third Edition, Y. Daniel Liang

This quiz is for students to practice. A large number of additional quiz is available for instructors using Quiz Generator from the Instructor's Resource Website. Videos for Java, Python, and C++ can be found at https://yongdanielliang.github.io/revelvideos.html.

Many questions in this edition have been updated in the new edition. Please check with the publisher on the newest edition.

Chapter 20 Linked Lists, Stacks, and Queues


Sections 20.2-20.3
20.1  If a pointer p does not point to anything, assign ________ to p.
A. null
B. Null
C. NULL
D. 0

20.2  If a list is empty, which of following statements are true?
A. head is NULL.
B. tail is NULL.
C. head == tail.
D. head < tail.

20.3  The Node class is defined in the text in LinkedList.h. Given the following code:

  Node<string> node1("New York");
  Node<string> node2("Savannah");
     
   Which of the following is the correct code to link node1 with node2?
A. node1.next = node2;
B. node1.next = &node2;
C. node1->next = node2;
D. node1->next = &node2;

20.4  The Node class is defined in the text in LinkedList.h. Given the following code:

  Node<string>* node1 = new Node<string>("New York");
  Node<string>* node2 = new Node<string>("Savannah");
  
   Which of the following is the correct code to link node1 with node2?
A. node1.next = node2;
B. node1.next = &node2;
C. node1->next = node2;
D. node1->next = &node2;

20.5  Which of the following two versions of the class declarations is correct?

Version I:
    class A
    {
    public:
      A()
      {
      }
    
    private:
      A* a;
      int i;
    };

Version II:
    class A
    {
    public:
      A()
      {
      }
    
    private:
      A a;
      int i;
    };
A. Both versions are correct.
B. Version I is correct.
C. Version II is correct.
D. Both versions are wrong.

20.6  What is the value of tail->next?
A. 0
B. NULL
C. head
D. tail

Sections 20.4-20.7
20.7  In the implementation of LinkedList.h, which of the following are true?
A. LinkedList has a size property.
B. LinkedList has the properties named head and tail to point to the nodes in a linked list.
C. If a linked list contains one element, head points to the node and tail is NULL.
D. tail.next is always NULL.

20.8  In the implementation of LinkedList.h, Which of the following statements are to insert a string s to the head of the list?
A. list.addFirst(s);
B. list.add(s);
C. list.add(0, s);
D. list.add(1, s);
E. list.insert(s);

20.9  In the implementation of LinkedList.h, Which of the following statements are to append a string s to the end of the list?
A. list.addFirst(s);
B. list.add(s);
C. list.add(0, s);
D. list.add(1, s);
E. list.insert(s);

20.10  In the implementation of LinkedList.h, Which of the following statements are to remove the first element from the list?
A. list.removeFirst(s);
B. list.removeFirst();
C. list.remove(0);
D. list.removeAt(0);

20.11  In the implementation of LinkedList.h, Which of the following statements are to remove the last element from the list?
A. list.removeLast(s);
B. list.removeLast();
C. list.removeAt(list.getSize() - 1);
D. list.remove(list.getSize() - 1);

20.12  When a new node is inserted to the head of a linked list, will the head pointer and the tail pointer be changed?
A. If the list is empty before the insertion, both head and tail will change.
B. If the list is not empty before the insertion, head will change.
C. head will always change, but tail will never change.
D. both head and tail will change.

20.13  When a new node is inserted to the end of a linked list, will the head pointer and the tail pointer be changed?
A. If the list is empty before the insertion, both head and tail will change.
B. If the list is not empty before the insertion, tail will change.
C. head will always change, but tail will never change.
D. both head and tail will change.

20.14  Suppose v is a vector and list2 is a LinkedList. Both contain 1 million double values. Analyze the following code:

A:
  while (v.size() > 0)
    v.erase(v.begin()); // Erase the first element in v

B:
  while (list2.getSize() > 0)
    list2.removeAt(0);
A. Code fragment A runs faster than code fragment B.
B. Code fragment B runs faster than code fragment A.
C. Code fragment A runs as fast as code fragment B.

20.15  Suppose list1 is a vector and list2 is a LinkedList. Both contain 1 million double values. Analyze the following code:

A:
  while (list1.size() > 0)
    list1.pop_back();

B:
  while (list2.getSize() > 0)
    list2.removeLast();
A. Code fragment A runs faster than code fragment B because the time complexity for code fragment A is O(n) and for B is O(n^2).
B. Code fragment B runs faster than code fragment A.
C. Code fragment A runs as fast as code fragment B because both code fragment A and B have the same time complexity O(n).
D. Both code fragment A and B have the same time complexity O(n), but A runs slightly faster because LinkedList has more overhaed on creating object for each node in the linked list.

20.16  Suppose list1 is a vector and list2 is a LinkedList. Both contain 1 million double values. Analyze the following code:

A:
for (int i = 0; i < 1000000; i++)
  list1.push_back(i);

B:
for (int i = 0; i < 1000000; i++)
  list2.add(i);
A. Code fragment A runs faster than code fragment B because the time complexity for code fragment A is O(n) and for B is O(n^2).
B. Code fragment B runs faster than code fragment A.
C. Code fragment A runs as fast as code fragment B because both code fragment A and B have the same time complexity O(n).
D. Both code fragment A and B have the same time complexity O(n), but A runs slightly faster because LinkedList has more overhead on creating object for each node in the linked list.

20.17  Suppose list1 is a vector and list2 is a LinkedList. Both contain 1 million double values. Analyze the following code:

A:
  for (int i = 0; i < 1000000; i++)
    list1.insert(list1.begin(), i); // Insert an element to the beginning of the vector

B:
  for (int i = 0; i < 1000000; i++)
    list2.addFirst(i);
A. Code fragment A runs faster than code fragment B.
B. Code fragment B runs faster than code fragment A.
C. Code fragment A runs as fast as code fragment B.

20.18  Suppose list1 is a vector and list2 is a LinkedList. Both contain 1 million double values. Analyze the following code:

A:
for (int i = 0; i < list1.size(); i++)
  sum += list1[i];

B:
for (int i = 0; i < list2.getSize(); i++)
  sum += list2.get(i);
A. Code fragment A is more efficient that code fragment B.
B. Code fragment B is more efficient that code fragment A.
C. Code fragment A is as efficient as code fragment B.

20.19  Suppose list2 is a LinkedList. Analyze the following code:

A:
while (list2.getSize() > 0)
  list2.removeAt(list2.get(list2.getSize() - 1));

B:
while (list2.getSize() > 0)
   list2.removeLast();
A. Code fragment A runs faster than code fragment B.
B. Code fragment B runs faster than code fragment A.
C. Code fragment A runs as fast as code fragment B.

Sections 20.8-20.9
20.20  If the number of elements in the program is fixed, what data structure should you use?
A. vector
B. linkedList
C. array
D. Stack

20.21  If you have to add or delete the elements anywhere in a list, what data structure should you use?
A. vector
B. linkedList
C. array
D. Stack

20.22  Which data structure is appropriate to store customers waiting in line at a clinic for a flu shots?
A. Stack
B. Queue
C. array
D. LinkedList
E. PriorityQueue

20.23  Suppose the rule of the party is that the participants who arrive later will leave earlier. Which data structure is appropriate to store the participants?
A. Stack
B. Queue
C. array
D. LinkedList