Sample Data Structures Questions
Chapter 5
Linked Lists

Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch
ISBN 0-8053-7470-1, Softcover, 784 pages, 1997

The Purpose of These Questions

These are typical exam questions from Chapter 5 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.) There are 23 short answer questions and 16 multiple choice questions in this file (which was last updated on Monday, March 17, 1997).

Short Answers

Short Answers Sections 5.1-5.2 Linked List Fundamentals

The Node definition: struct Node { typedef double Item; Item data; Node *link; };

1. What are the steps to inserting a new item at the head of a linked list? Use one short English sentence for each step.
2. Suppose that p is a pointer to a Node in a linked list, and *p is not the tail node. What are the steps to removing the Node after *p? Use one short English sentence for each step.
3. Suppose we are using the usual Node struct definition (with member variables called data and link). Your program is using a Node* variable called head_ptr to point to the first node of a linked list (or head_ptr == NULL for the empty list). Write a few lines of C++ code that will print all the double numbers on the list.
4. Suppose we are using the usual Node struct definition (with member variables called data and link), and that locate_ptr is pointing to a node in a linked list. Write an assignment statement that will make locate_ptr point to the next node in the list (if there is one). If there is no next node, then your assignment statement should set locate_ptr to NULL.
5. Implement the following function as a new function for the linked list toolkit. (Use the usual Node definition with member variables called data and link.)

    size_t count_42s(Node* head_ptr);
    // Precondition: head_ptr is the head pointer of a linked list.
    // The list might be empty or it might be non-empty.
    // Postcondition: The return value is the number of occurrences
    // of 42 in the data field of a node on the linked list.
    // The list itself is unchanged.

6. Implement the following function as a new function for the linked list toolkit. (Use the usual Node definition with member variables called data and link.)

    bool has_42(Node* head_ptr);
    // Precondition: head_ptr is the head pointer of a linked list.
    // The list might be empty or it might be non-empty.
    // Postcondition: The return value is true if the list has at least
    // one occurrence of the number 42 in the data part of a node.

7. Implement the following function as a new function for the linked list toolkit. (Use the usual Node definition with member variables called data and link.)

    bool all_42s(Node* head_ptr);
    // Precondition: head_ptr is the head pointer of a linked list.
    // The list might be empty or it might be non-empty.
    // Postcondition: The return value is true if every node in the
    // list contains 42 in the data part. NOTE: If the list is empty,
    // then the function returns true.

8. Implement the following function as a new function for the linked list toolkit. (Use the usual Node definition with member variables called data and link. The data field is an int.)

    int sum(Node* head_ptr);
    // Precondition: head_ptr is the head pointer of a linked list.
    // The list might be empty or it might be non-empty.
    // Postcondition: The return value is the sum of all the data components
    // of all the nodes. NOTE: If the list is empty, the function returns 0.

9. Implement the following function as a new function for the linked list toolkit. (Use the usual Node definition with member variables called data and link. The data field is an int.)

    int product(Node* head_ptr);
    // Precondition: head_ptr is the head pointer of a linked list.
    // The list might be empty or it might be non-empty.
    // Postcondition: The return value is the product of all the data components
    // of all the nodes. NOTE: If the list is empty, the function returns 1.

10. Implement the following function as a new function for the linked list toolkit. (Use the usual Node definition with member variables called data and link.)

    void list_tail_insert(Node* head_ptr, const Node::Item& entry);
    // Precondition: head_ptr is the head pointer of a non-empty
    // linked list.
    // Postcondition: A new node has been added at the tail end
    // of the list. The data in the new node is taken from the
    // parameter called entry.

11. Implement the following function as a new function for the linked list toolkit. (Use the usual Node definition with member variables called data and link.)

    bool data_is_on(Node* head_ptr, Node* p);
    // Precondition: head_ptr is the head pointer of a linked list
    // (which might be empty, or might be non-empty). The pointer p
    // is a non-NULL pointer to some Node on some linked list.
    // Postcondition: The return value is true if the data in *p
    // appears somewhere in a data field of a node in head_ptr's
    // linked list. Otherwise the return value is false.
    // None of the nodes on any lists are changed.

12. Implement the following function as a new function for the linked list toolkit. (Use the usual Node definition with member variables called data and link.)

    bool is_on(Node* head_ptr, Node* p);
    // Precondition: head_ptr is the head pointer of a linked list
    // (which might be empty, or might be non-empty). The pointer p
    // is a non-NULL pointer to some Node on some linked list.
    // Postcondition: The return value is true if p actually points to
    // one of the Nodes in the head_ptr's linked list. For example,
    // p might point to the head node of this list, or the second node,
    // or the third node, and so on. Otherwise the return value is
    // false. None of the nodes on any lists are changed.

13. Implement the following function as a new function for the linked list toolkit. Do not call any of the other toolkit functions from within your implementation. (Use the usual Node definition with member variables called data and link.)

    void list_insert_zero(Node* previous_ptr);
    // Precondition: previous_ptr is a pointer to a node on a linked list.
    // Postcondition: A new node has been added to the list after
    // the node that previous_ptr points to. The new node contains 0.

14. Suppose that p, q, and r are all pointers to nodes in a linked list with 15 nodes. The pointer p points to the first node, q points to the 8th node, and r points to the last node. Write a few lines of code that will make a new copy of the list. You code should set THREE new pointers called x, y, and z so that: x points to the first node of the copy, y points to the 8th node of the copy, and z points to the last node of the copy. Your code may NOT contain any loops, but it can use the toolkit functions.

Short Answers Section 5.3 The Bag ADT with a Linked List

15. Suppose that a_ptr and b_ptr are Node pointers. Write one clear sentence to tell me when the expression (a_ptr==b_ptr) will be true.
16. Compare the worst-case big-O time analysis for these two functions: The insert function for the Bag that is implemented using a fixed-sized array, and the insert function for the Bag that is implemented using a linked list.
17. Compare the worst-case big-O time analysis for these two functions: The remove function for the Bag that is implemented using a fixed-sized array, and the remove function for the Bag that is implemented using a linked list.

Short Answers Section 5.4 The List ADT with a Linked List

18. Tell me about one of the List operations that is more efficient because the class keeps a tail pointer as a private member variable. Provide a specific example showing why the operation would be less efficient without the tail pointer.
19. Tell me about one of the List operations that is easier to program because the class keeps a precursor (rather than just a cursor). Provide a specific example showing why the operation would be harder to program without the precursor.
20. Compare the worst-case big-O time analysis for these two functions: The insert function for the List that is implemented using a fixed-sized array, and the insert function for the List that is implemented using a linked list.
21. Compare the worst-case big-O time analysis for these two functions: The remove function for the List that is implemented using a fixed-sized array, and the remove function for the List that is implemented using a linked list.

Short Answer Section 5.5 Dynamic Arrays vs. Linked Lists vs. Doubly Linked Lists

22. Write a struct definition that could be used to define a node in a doubly linked list. Also write one sentence to describe a situation when a doubly linked list is appropriate.
23. Describe a situation where storing items in an array is clearly better than storing items on a linked list.

Multiple Choice

Multiple Choice Sections 5.1-5.2 Linked List Fundamentals

The Node definition: struct Node { typedef double Item; Item data; Node *link; };

1. Suppose cursor points to a node in a linked list (using the Node definition with member variables called data and link). What statement changes cursor so that it points to the next node?
• A. cursor++;
• B. cursor = link;
• C. cursor += link;
• D. cursor = cursor->link;
2. Suppose cursor points to a node in a linked list (using the Node definition with member variables called data and link). What Boolean expression will be true when cursor points to the tail node of the list?
• A. (cursor == NULL)
• B. (cursor->link == NULL)
• C. (cursor->data == NULL)
• D. (cursor->data == 0.0)
• E. None of the above.
3. What is the fundamental difference between a struct and a class?
• A. By default the members of structs are private.
• B. By default the members of structs are public.
• C. Structs can only contain data members.
• D. Structs must contain a pointer member variable.
4. Suppose that p is a pointer variable that contains the NULL pointer. What happens if your program tries to read or write *p?
• A. A syntax error always occurs at compilation time.
• B. A run-time error always occurs when *p is evaluated.
• C. A run-time error always occurs when the program finishes.
• D. The results are unpredictable.
5. Suppose that f is a function with a prototype like this:

    void f(________ head_ptr);
    // Precondition: head_ptr is a head pointer for a linked list.
    // Postcondition: The function f has done some computation with
    // the linked list, but the list itself is unchanged.

What is the best data type for head_ptr in this function?

• A. Node
• B. Node&
• C. Node*
• D. Node*&
6. Suppose that f is a function with a prototype like this:

    void f(________ head_ptr);
    // Precondition: head_ptr is a head pointer for a linked list.
    // Postcondition: The function f has done some manipulation of
    // the linked list, and the list might now have a new head node.

What is the best data type for head_ptr in this function?

• A. Node
• B. Node&
• C. Node*
• D. Node*&

Multiple Choice Section 5.3 The Bag ADT with with a Linked List

7. In the linked list version of the Bag class a member variable many_nodes is used to keep track of how long the linked list is. Why not just make a call to the list toolkit function list_length()?
• A. The list_length() function is O(n) and the alternative is O(1).
• B. The list_length() function is private.
• C. The list_length() function results in an infinite loop for circular lists.
• D. The list_length() function works only for lists of integers.
8. Suppose that the Bag is implemented with a linked list. Which of these operations are likely to have a constant worst-case time?
• A. insert
• B. occurrences
• C. remove
• 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
9. The Bag class in Chapter 5 has a new grab member function that returns a randomly selected item from a Bag (using a pseudorandom number generator). Suppose that you create a Bag, insert the numbers 1, 2, and 3, and then use the grab function to select an item. Which of these situations is most likely to occur if you run your program 300 times (from the beginning):
• A. Each of the three numbers will be selected about 100 times.
• B. One of the numbers will be selected about 200 times; another number will be selected about 66 times; the remaining number will be selected the rest of the time.
• C. One of the numbers will be selected 300 times; the other two won't be selected at all.
10. What is the expression for generating a pseudorandom number in the range 1...N?
• A. rand() % N;
• B. rand() / N;
• C. rand() % (N + 1);
• D. rand() / (N + 1);
• E. (rand() % N) + 1;
11. Which expression computes a pseudorandom integer between -10 and 10 using rand() from stdlib.h?
• A. (rand( ) % 20) - 10
• B. (rand( ) % 21) - 10
• C. (rand( ) % 22) - 10
• D. (rand( ) % 20) - 11
• E. (rand( ) % 21) - 11

Multiple Choice Section 5.4 The List ADT with a Linked List

12. For the linked-list version of the List ADT, which operations are constant time operations in the worst case?
• A. attach is constant time, but not insert
• B. insert is constant time, but not attach
• C. Both attach and insert are constant time
• D. Neither attach nor insert are constant time
13. Suppose that the List is implemented with a linked list. Which of these operations are likely to have a constant worst-case time?
• A. insert
• B. occurrences
• C. remove
• 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
14. What is the output of these statements, using your List ADT implemented as a linked list with Item defined as integer:

    List x;
    List y;
    x.insert(41);    // Inserts 41 into the list x
    x.insert(42);    // Inserts 42, so that x is now 42, 41 with cursor at front
    y = x;
    x.attach(43);    // Attaches 43 so that x is now 42, 43, 41 with cursor at 43
    y.advance( );
    cout "y size is "              << y.size( );
    cout " and y current item is " << y.current( ) << endl;

• A. y size is 2 and y current item is 41.
• B. y size is 2 and y current item is 43.
• C. y size is 3 and y current item is 41.
• D. y size is 3 and y current item is 43.
• E. None of the above.
15. Suppose that you forgot to override the assignment operator in your List ADT implemented as a linked list. What is the most likely output from the previous question?
• A. y size is 2 and y current item is 41.
• B. y size is 2 and y current item is 43.
• C. y size is 3 and y current item is 41.
• D. y size is 3 and y current item is 43.
• E. None of the above.

Multiple Choice Section 5.5 Dynamic Arrays vs. Linked Lists vs. Doubly Linked Lists

16. What kind of list is best to answer questions such as "What is the item at position n?"
• A. Lists implemented with an array.
• B. Doubly-linked lists.
• C. Singly-linked lists.
• D. Doubly-linked or singly-linked lists are equally best

---

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/chap05q.html
Copyright © 1997 Addison-Wesley Computer and Engineering Publishing Group