Introduction to Programming Using Python, Y. Daniel Liang

This quiz is for students to practice. A large number of additional quiz is available for instructors from the Instructor's Resource Website.

Chapter 18 Linked Lists, Stacks, Queues, and Priority Queues

Section 18.2 Linked Lists
18.1  ________ is a data structure to store data in a sequential order.
A. A list
B. A set
C. A dictionary
D. A heap

18.2  If a pointer p does not point to anything, assign ________ to p.
A. null
B. none
C. None
D. 0

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

18.4  Which of the following operations are supported by a list?
A. Retrieve an element from this list.
B. Insert a new element to this list.
C. Delete an element from this list.
D. Find how many elements are in this list.
E. Find whether an element is in this list.

18.5  list is more efficient than LinkedList for the following operations:
A. Insert/delete an element in the middle of the list.
B. Insert/delete an element in the beginning of the list.
C. Insert/delete an element at the end of the list.
D. Retrieve an element given the index.

18.6  LinkedList is more efficient than list for the following operations:
A. Insert/delete an element in the middle of the list.
B. Insert/delete an element in the beginning of the list.
C. Insert/delete an element at the end of the list.
D. Retrieve an element given the index.

18.7  Suppose list1 is a list and list2 is a LinkedList. Both contains 1 million double values. Analyze the following code:

A:
while len(list1) > 0:
    del list1[0]

B:
while list2.getSize() > 0:
    list2.removeFirst()
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.

18.8  Suppose list1 is a list. Analyze the following code:

A:
while len(list1) > 0:
    del list1[len(list1) - 1]

B:
while len(list1) > 0:
    list1.remove(list1.get(len(list1) - 1))
A. Code fragment A runs faster than code fragment B beacuse 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 beacuse 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 faster beacuse code fragment A has less overhaed.

18.9  Suppose list1 is a list and list2 is a LinkedList. Both contains 1 million double values. Analyze the following code:

A:
while len(list1) > 0:
    del list1[len(list1) - 1]

B:
while list2.getSize() > 0:
    list2.removeLast()
A. Code fragment A runs faster than code fragment B beacuse 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 beacuse 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 faster beacuse LinkedList has more overhaed on creating object for each node in the linked list.

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

A:
while len(list2) > 0:
    list2.remove(list2.get(len(list2) - 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.

18.11  Suppose list1 is a list and list2 is a LinkedList. Both contains 1 million double values. Analyze the following code:

A:
for i in range(100000):
    list1.insert(0, i)

B:
for i in range(100000):
    list2.insert(0, 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.

18.12  Suppose list1 is a list and list2 is a LinkedList. Both contains 1 million double values. Analyze the following code:

A:
for i in range(100000):
  list1.append(i);

B:
for i in range(100000):
  list2.add(i);
A. Code fragment A runs faster than code fragment B beacuse 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 beacuse 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(1), but A runs faster beacuse LinkedList has more overhaed on creating object for each node in the linked list.

18.13  Suppose list1 is a list and list2 is a LinkedList. Both contains 1 million double values. Analyze the following code:

A:
for i in range(100000):
  sum += list1[i];

B:
for i in range(100000):
  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.

Section 18.3 Iterators
18.14  Which of the following are true?
A. An iterator is an object that provides a uniformed way for traversing the elements in a container object.
B. To enable the traversal using a for loop in a container object, the container class must implement the __iter__(self) method that returns an iterator.
C. An iterator class must contains the __next__(self) method that returns the next element in the container object.
D. When there are no items left to iterate, the __next__() method must raise a StopIteration exception.

Section 18.4 Generators
18.15  Which of the following are true?
A. Generators are special Python functions for generating iterators.
B. When you define an iterator class, the __next__ and __iter__ methods must be defined explicitly. Using a generator, these two methods are automatically defined when you create an iterator from a generator.
C. A generator uses the yield keyword to return data rather than using the return keyword.
D. When the generator terminates, it automatically raises a StopIteration exception.

Sections 18.5-18.6
18.16  Which of the following are true?
A. A stack can be viewed as a special type of list, where the elements are accessed, inserted, and deleted only from the end, called the top, of the stack.
B. A queue represents a waiting list. A queue can be viewed as a special type of list, where the elements are inserted into the end (tail) of the queue, and are accessed and deleted from the beginning (head) of the queue.
C. Since the insertion and deletion operations on a stack are made only at the end of the stack, using an array list to implement a stack is more efficient than a linked list.
D. Since deletions are made at the beginning of the list, it is more efficient to implement a queue using a LinkedList than a list.

18.17  In the implementation of Stack and Queue, which of the following are true?
A. Stack contains all the methods defined in list.
B. Queue contains all the methods defined in LinkedList.
C. Stack contains a list for storing elements.
D. Queue contains a linked list for storing elements.

Section 18.7 Priority Queues
18.18  Which data structure is appropriate to store patients in an emergency room?
A. Stack
B. Queue
C. Priority Queue
D. Linked List
E. list

18.19  Which data structure is appropriate to store customers in a clinic for taking flu shots?
A. Stack
B. Queue
C. Priority Queue
D. list
E. Linked List

18.20  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. list
D. Linked List