## Sample Data Structures Questions Chapter 5 Linked Lists

### Data Structures and Other Objects Using C++ by Michael Main and Walter Savitch Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000

#### 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 29 short answer questions and 16 multiple choice questions in this file.

 Short Answers Sections 5.1-5.2 Linked List Fundamentals The node definition: ```class node { // TYPEDEF typedef double value_type; // CONSTRUCTOR node( const value_type& init_data = value_type( ), node* init_link = NULL ) { data_field = init_data; link_field = init_link; } // Member functions to set the data and link fields: void set_data(const value_type& new_data) { data_field = new_data; } void set_link(node* new_link) { link_field = new_link; } // Constant member function to retrieve the current data: value_type data( ) const { return data_field; } // Two slightly different member functions to retreive // the current link: const node* link( ) const { return link_field; } node* link( ) { return link_field; } private: value_type data_field; node* link_field; }; }; ```

1. What is the one statement that can be used to insert a new node at the head of a linked list. Assume that the list's head_pointer is called `head_ptr` and the that the data for the new node is called `entry`.

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 definition (with member functions 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 definition (with member functions called data and link), and that locate_ptr is pointing to a node in a linked list. Write a 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 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(const node* head_ptr);
// 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(const node* head_ptr);
// 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(const node* head_ptr);
// 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(const node* head_ptr);
// 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(const node* head_ptr);
// 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::value_type& entry);
// 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(const node* head_ptr, const node* p);
// (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(const node* head_ptr, const node* p);
// (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.

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 erase_one function for the bag that is implemented using a fixed-sized array, and the erase_one function for the bag that is implemented using a linked list.

18. Tell me about one of the sequence 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 sequence 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 sequence that is implemented using a fixed-sized array, and the insert function for the sequence 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 sequence that is implemented using a fixed-sized array, and the remove function for the sequence that is implemented using a linked list.

 Short Answer Section 5.5 Dynamic Arrays vs. Linked Lists vs. Doubly Linked Lists ``` class dnode { public: // CONSTRUCTOR: Creates a dnode containing a specified initial values. dnode( int init_data = 0, dnode* init_fore = NULL, dnode* init_back = NULL ) { data_field = init_data; link_fore = init_fore; link_back = init_back; } // Member functions to set the fields: void set_data(int new_data) { data_field = new_data; } void set_fore(dnode* new_fore) { link_fore = new_fore; } void set_back(dnode* new_back) { link_back = new_back; } // Const member functions to retrieve current data: int data( ) const { return data_field; } // Two slightly different member functions to retrieve each link: const dnode* fore( ) const { return link_fore; } dnode* fore( ) { return link_fore; } const dnode* back( ) const { return link_back; } dnode* back( ) { return link_back; } private: int data_field; dnode *link_fore; dnode *link_back; }; ```

22. 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.

24. Implement the following function using the `dnode` class that is shown above. It is NOT a member function).
```int sum_data(const dnode* head_ptr);
// POSTCONDITION: The return value is the sum of all the data fields
// of the dnodes in the linked list.
```

25. Implement the following function using the `dnode` class that is shown above. It is NOT a member function.
```dnode* find_data(dnode* head_ptr, int target)
// POSTCONDITION: The return value is a pointer to the first dnode in
// the linked list that contains the target as its data. If there is no
// such dnode, then the return value is NULL.
```

26. Implement the following function using the `dnode` class that is shown above. It is NOT a member function. Your function should not cause a heap leak.
```void delete_dnode(dnode* p)
// PRECONDITION: p is a non-NULL pointer to a dnode in a linked list.
// It is neither the first nor the last dnode.
// POSTCONDITION: The dnode *p has been removed from the list.
```

27. Implement the following function using the `dnode` class that is shown above. It is NOT a member function.
```void insert_dnode(dnode* p, int new_data)
// PRECONDITION: p is a non-NULL pointer to a dnode in a linked list.
// It is neither the first nor the last dnode.
// POSTCONDITION: A new dnode with new_data has been inserted into the
```

28. Suppose that a program has declared these three variables using the `dnode` class shown above.
```dnode *b;
dnode *h;
dnode *z;
```
After executing part of the program, the pointer `b` is a head pointer for a non-empty linked list. Write some code that can be placed in the program at this point to make a complete copy of `b`'s linked list. At the end of your code, `b` should be unchanged, `h` should be the head pointer of the new list, and `z` should be the tail pointer of the new list. If necessary, you may declare other `dnode *` variables to use in your algorithm.

29. This question is appropriate if you have implemented the polynomial with a linked list from www.cs.colorado.edu/~main/projects/chap05d.html. In my dynamic polynomial, the `set_recent` function includes this line:
```    recent_ptr = recent_ptr->fore( );
```
A. Describe the effect of this statement in one clear English sentence.
B. The `set_recent` function is a const member function, which means that normally it is not permitted to change any member variables. Explain why the compiler permits `set_recent` to change the `recent_ptr` member variable.

#### Multiple Choice

 Multiple Choice Sections 5.1-5.2 Linked List Fundamentals
1. Suppose cursor points to a node in a linked list (using the node definition with member functions 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 functions 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. Why does our node class have two versions of the link member function?
• A. One is public, the other is private.
• B. One is to use with a const pointer, the other with a regular pointer.
• C. One returns the forward link, the other returns the backward link.
• D. One returns the data, the other returns a pointer to the next node.

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);
// 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. const node
• C. node*
• D. const node*

6. Suppose that f is a function with a prototype like this:
```    void f(________ head_ptr);
// 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. 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

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

12. For the linked-list version of the sequence 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 sequence is implemented with a linked list. Which of these operations are likely to have a constant worst-case time?
• A. insert
• B. size
• C. remove_current
• 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 sequence ADT implemented as a linked list with Item defined as integer:
```    sequence x;
sequence y;
x.insert(41);    // Inserts 41 into the sequence 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
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 sequence 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.