Sample Data Structures Questions

Sample Data Structures Questions
Chapter 4
Linked Lists

Data Structures and Other Objects Using Java (Third Edition)
by Michael Main
ISBN 0-321-37525-4

The Purpose of These Questions

These are typical exam questions from Chapter 4 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 14 multiple choice questions in this file.

Short Answers

Short Answers
Sections 4.1-4.3
Linked List Fundamentals

The IntNode class:

public class IntNode
{
   private int data;
   private IntNode link;
   ...
}

What are the steps to inserting a new item at the head of a linked list? Use one short English sentence for each step.

Suppose that p is a reference to an IntNode in a linked list, and it is not the tail node. What are the steps to removing the node after p? Use one short English sentence for each step.

Suppose we are using the usual IntNode class (with instance variables called data and link). Your program is using an IntNode variable called head to refer to the first node of a linked list (or head is null for the empty list). Write a few lines of Java code that will print all the double numbers on the list.

Suppose we are using the usual IntNode class (with instance variables called data and link), and that locate is refering to a node in a linked list. Write an assignment statement that will make locate refer to the next node in the list (if there is one). If there is no next node, then your assignment statement should set locate to null.

Implement the following method as a new static method for the IntNode class. (Use the usual IntNode class with instance variables called data and link.)

    public static int count42s(IntNode head)
    // Precondition: head is the head reference 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.

Implement the following method as a new static method for the IntNode class. (Use the usual IntNode definition with instance variables called data and link.)

    public static boolean has42(IntNode head)
    // Precondition: head is the head reference 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.

Implement the following method as a new method for the IntNode class. (Use the usual IntNode definition with instance variables called data and link.)

    public static boolean all42s(IntNode head)
    // Precondition: head is the head reference 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 method returns true.

Implement the following method as a new stati method for the IntNode class. (Use the usual IntNode definition with instance variables called data and link.)

    public static int sum(IntNode head)
    // Precondition: head is the head reference 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 method returns 0.

Implement the following method as a new static method for the IntNode class. (Use the usual IntNode definition with instance variables called data and link.)

    public static int product(IntNode head)
    // Precondition: head is the head reference 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 method returns 1.

Implement the following method as a new static method for the IntNode class. (Use the usual IntNode definition with instance variables called data and link.)

    public static void listTailInsert(IntNode head, int entry)
    // Precondition: head is the head reference 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.

Implement the following method as a new static method for the IntNode class. (Use the usual Node definition with instance variables called data and link.)

    public static boolean dataIsOn(IntNode head, IntNode p)
    // Precondition: head is the head reference of a linked list
    // (which might be empty, or might be non-empty). The parameter p
    // is a non-null reference to some IntNode 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's
    // linked list. Otherwise the return value is false.
    // None of the nodes on any lists are changed.

Implement the following method as a new static method for the IntNode class. (Use the usual Node definition with instance variables called data and link.)

    public static boolean isOn(IntNode head, IntNode p)
    // Precondition: head is the head reference of a linked list
    // (which might be empty, or might be non-empty). The parameter p
    // is a non-null reference to some IntNode on some linked list.
    // Postcondition: The return value is true if p actually points to
    // one of the IntNodes in the head'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.

Implement the following method as a new method for the IntNode class. Do not call any of the other class methods from within your implementation, except for the constructor. (Use the usual IntrNode definition with instance variables called data and link.)

    public void listInsertZero(IntNode previous)
    // Precondition: previous is a reference to a node on a linked list.
    // Postcondition: A new node has been added to the list after
    // the node that previous refers to. The new node contains 0.

Suppose that p, q, and r are all references to nodes in a linked list with 15 nodes. The variable p refers to the first node, q refers to the 8th node, and r refers 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 variables called x, y, and z so that: x refers to the first node of the copy, y refers to the 8th node of the copy, and z refers to the last node of the copy. Your code may NOT contain any loops, but it can use the other IntNode methods.

Short Answers
Section 4.4
The Bag ADT
with a Linked List

Suppose that a and b are IntNode variables. Write one clear sentence to tell me when the expression (a==b) will be true.

Compare the worst-case big-O time analysis for these two methods: The add method for the Bag that is implemented using an array, and the add method for the Bag that is implemented using a linked list.

Compare the worst-case big-O time analysis for these two methods: The remove method for the Bag that is implemented using a fixed-sized array, and the remove method for the Bag that is implemented using a linked list.

Short Answers
Section 4.5
The Sequence ADT
with a Linked List

Tell me about one of the Sequence operations that is more efficient because the class keeps a tail reference as a private instance variable. Provide a specific example showing why the operation would be less efficient without the tail reference.

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.

Compare the worst-case big-O time analysis for these two methods: The addBefore method for the Sequence that is implemented using an array, and the addBefore method for the Sequence that is implemented using a linked list.

Compare the worst-case big-O time analysis for these two methods: The remove method for the Sequence that is implemented using an array, and the remove method for the Sequence that is implemented using a linked list.

Short Answer
Section 4.6
Arrays vs.
Linked Lists vs.
Doubly Linked Lists

Write a class definition that could be used to define a node in a doubly linked list. Include only the instance variables, not the methods. Also write one sentence to describe a situation when a doubly linked list is appropriate.

Describe a situation where storing items in an array is clearly better than storing items on a linked list.

Multiple Choice

Multiple Choice
Sections 4.1-4.3
Linked List Fundamentals

The IntNode definition:

public class IntNode
{
    int data;
    IntNode link;
    ...
}

Suppose cursor refers to a node in a linked list (using the IntNode class with instance variables called data and link). What statement changes cursor so that it refers to the next node?

A. cursor++;
B. cursor = link;
C. cursor += link;
D. cursor = cursor.link;

Suppose cursor refers to a node in a linked list (using the Node class with instance variables called data and link). What boolean expression will be true when cursor refers 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.

Which boolean expression indicates whether the numbers in two nodes (p and q) are the same. Assume that neither p nor q is null.

A. p == q
B. p.data == q.data
C. p.link == q.link
D. None of the above.

Suppose that p is a reference variable that contains the null reference. What happens at runtime if the program tries to activate a method of p?

A. IllegalArgumentException
B. IllegalStateException
C. NullPointerException
D. The results are unpredictable.

Suppose that a method has one node as a parameter and it returns two references to nodes. What's the best header for the method?

A. IntNode foo(IntNode p)
B. IntNode, IntNode foo(IntNode p)
C. IntNode[ ] foo(IntNode p)
D. void foo(IntNode p, IntNode answer1, IntNode answer2)

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

In the linked list version of the Bag class an instance variable manyNodes is used to keep track of how long the linked list is. Why not just make a call to the IntNode method listLength()?

A. The listLength() method is O(n) and the alternative is O(1).
B. The listLength() method is private.
C. The listLength() method results in an infinite loop for circular lists.
D. The listLength() method works only for lists of integers.

Suppose that the Bag is implemented with a linked list. Which of these operations are likely to have a constant worst-case time?

A. add
B. countOccurrences
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

What is the expression for generating a pseudorandom number in the range 1...N?

A. (int) (Math.random() * N);
B. (int) (Math.random() / N);
C. (int) (Math.random() * (N + 1));
D. (int) (Math.random() / (N + 1));
E. (int) (Math.random() * N) + 1;

Which expression computes a pseudorandom integer between -10 and 10 using rand() from stdlib.h?

A. (int) (Math.random( ) * 20) - 10
B. (int) (Math.random( ) * 21) - 10
C. (int) (Math.random( ) * 22) - 10
D. (int) (Math.random( ) * 20) - 11
E. (int) (Math.random( ) * 21) - 11

Multiple Choice
Section 4.5
The Sequence ADT
with a Linked List

For the linked-list version of the Sequence ADT, which operations are constant time operations in the worst case?

A. addAfter is constant time, but not addBefore
B. addBefore is constant time, but not addAfter
C. Both addAfter and addBefore are constant time
D. Neither addAfter nor addBefore are constant time

Suppose that the Sequence is implemented with a linked list. Which of these operations are likely to have a constant worst-case time?

A. addBefore
B. countOccurrences
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

What is the output of these statements, using your Sequence ADT implemented as a linked list:

    DoubleLinkedSeq x = new DoubleLinkedSeq( );
    DoubleLinkedSeq y = new DoubleLinkedSeq( );
    x.addBefore(41);    // Inserts 41 into the list x
    x.addBefore(42);    // Inserts 42, so that x is now 42, 41 with cursor at front
    y = (DoubleLinkedSeq) x.clone( );
    x.addAfter(43);     // Attaches 43 so that x is now 42, 43, 41 with cursor at 43
    y.advance( );
    System.out.println("y size is " + y.size( ));
    System.out.println(" and y current item is " + y.current( ));

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.

Suppose that you forgot to write the extra work after super.clone in your implementation of the sequence clone method. 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 4.6
Arrays vs.
Linked Lists vs.
Doubly Linked Lists

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

Michael Main (main@colorado.edu)