ch4i.txt

（英文原版）数据结构与算法分析（C++版）单选试题与答案

Chapter 4 Lists, Stacks and Queues: Instructor's CD questions

1. An ordered list is one in which:
a) The element values are in sorted order.
*b) Each element a position within the list.

2. An ordered list is most like a:
a) set.
b) bag.
*c) sequence.

3. As compared to the linked list implementation for lists, the
   array-based list implementation requires:
a) More space
b) Less space
*c) More or less space depending on how many elements are in the list.

4. Here is a series of C++ statements using the list ADT in the book.

L1.append(10);
L1.append(20);
L1.append(15);

If these statements are applied to an empty list, the result will look
like:
a) < 10 20 15 >
*b) < | 10 20 15 >
c) < 10 20 15 | >
d) < 15 20 10 >
e) < | 15 20 10 >
f) < 15 20 10 | >

5. When comparing the array-based and linked implementations, the
array-based implementation has:
*a) faster direct access to elements by position,
but slower insert/delete from the current position.
b) slower direct access to elements by position,
but faster insert/delete from the current position.
c) both faster direct access to elements by position, and faster
insert/delete from the current position.
d) both slower direct access to elements by position, and slower
insert/delete from the current position.

6. For a list of length n, the linked-list implementation's prev
   function requires worst-case time:
a) O(1).
b) O(log n).
*c) O(n).
d) O(n^2).

7. Finding the element in an array-based list with a given key value
   requires worst case time:
a) O(1).
b) O(log n).
*c) O(n).
d) O(n^2).

8. In the linked-list implementation presented in the book, a header
   node is used:
*a) To simplify special cases.
b) Because the insert and delete routines won't work correctly without
   it.
c) Because there would be no other way to make the current pointer
   indicate the first element on the list.

9. When a pointer requires 4 bytes and a data element requires 4
   bytes, the linked list implementation requires less space than the
   array-based list implementation when the array would be:
a) less than 1/4 full.
b) less than 1/3 full.
*c) less than half full.
d) less than 2/3 full.
e) less than 3/4 full
f) never.

10. When a pointer requires 4 bytes and a data element requires 12
   bytes, the linked list implementation requires less space than the
   array-based list implementation when the array would be:
*a) less than 1/4 full.
b) less than 1/3 full.
c) less than half full.
d) less than 2/3 full.
e) less than 3/4 full
f) never.

11. When we say that a list implementation enforces homogeneity, we
    mean that:
a) All list elements have the same size.
*b) All list elements have the same type.
c) All list elements appear in sort order.

12. When comparing the doubly and singly linked list implementations,
    we find that the doubly linked list implementation
*a) Saves time on some operations at the expense of additional space.
b) Saves neither time nor space, but is easier to implement.
c) Saves neither time nor space, and is also harder to implement.

13. We use a comparator function in the Dictionary class ADT:
a) to simplify implementation.
*b) to increase the opportunity for code reuse.
c) to improve asymptotic efficiency of some functions.

14. All operations on a stack can be implemented in constant time
    except:
a) Push
b) Pop
c) The implementor's choice of push or pop (they cannot both be
    implemented in constant time).
*d) None of the above.

15. Recursion is generally implemented using
a) A sorted list.
*b) A stack.
c) A queue.