Deck 14: An Introduction to Data Structures

Question 1

What is the instance variable representing a reference to the first node in the linked-list class called?

A) null
B) head
C) node
D) link

Answer 1

B

Question 2

When testing the delete method of a linked list, what scenarios do we want to test?

A) Attempt to delete an item not in the list.
B) Delete the first item in the list.
C) Delete an item in the middle of a list.
D) All of these are correct.

Answer 2

D

Question 3

When testing the insert method of a linked list (one that inserts at the beginning of the list), what scenarios do we want to test?

A) Insert in an empty list (only).
B) Insert in an empty list and a nonempty list.
C) Insert in a nonempty list (only).
D) There is no need to test if we think the method is properly coded.

Answer 3

B

Question 4

Consider a queue represented by a circular array of 10 elements and front and back the two instance variables representing the indexes of the front and the back of the queue, respectively. If the value of front is 0 and the value of back is 9, what can you tell about the queue?

A) It is empty.
B) It is full.
C) It is neither empty nor full.
D) It is either empty or full.

Question 5

Data stored in a linked list must be of the primitive data types.

Question 6

It is good practice to provide an accessor to the head of a linked list.

Question 7

Assuming the number of items is an instance variable of a linked list class, it is good practice to provide a mutator for it.

Question 8

In a queue represented by a linked list, we delete, or dequeue, at the end of the list.

Question 9

In a queue represented by a linked list, we delete, or dequeue, based on the value of the item stored in a node.

Question 10

When using an array to represent a queue, we should deal with the array as if it were __________.

Question 11

A Player class encapsulates a player; a(n) ____________ encapsulates a node; and a PlayerLinkedList encapsulates the linked list.

Question 12

What is the return value of the method insert( Player p )?

Question 13

With a linked list, you should provide which of the following functions?

A) Insert an item.
B) Delete an item.
C) List the items in the list and return that list as a String.
D) All of these are correct.

Question 14

Two instance variables in the IntegerNode class are an int and an IntegerNode object reference, representing the next node.

Question 15

Which of the following is true about both delete( int searchID ) and peek( int searchID )?

A) Both return the first Player in the list with an ID equal to searchID.
B) Both remove the first Player in the list with an ID equal to searchID.
C) Both methods always throw a DataStructureException.
D) All of these are correct.

Question 16

It is good practice to define your own exception class as a subclass of another exception class because your class will inherit the existing functionality of the exception class, which simplifies coding the new class; you need to code only the constructor.

Question 17

A ____________ is a linear data structure that organizes items in a last in, first out manner.

A) stack
B) push
C) pop
D) LIFO

Question 18

The following code segment is used with the ________ approach.
16 /** enqueue method
17 * @param p Player object to insert
18 */
19 public void enqueue( Player p )

A) LIFO
B) FIFO
C) stack
D) getPlayer

Question 19

A tail reference can be used to:

A) enqueue an item.
B) pop an item.
C) dequeue an item.
D) push an item.

Question 20

Ivanna has a restaurant that prides itself in fresh produce. She always wants to serve the freshest produce she has. She should use a LIFO approach for her produce inventory.

Question 21

In a LIFO approach, the push method is used to delete the last item inserted.

Question 22

If the linked list is empty, deleting an item in a linked list representing a queue would result in a NullPointerException at run time.

Question 23

_______ represents the index of the element of the array stack that is at the top of the stack.

A) pop
B) stack
C) top
D) push

Question 24

Unlike a linked list, an array has a fixed size, so the array could be completely filled with elements of the stack.

Question 25

The number of available elements for the queue in the array will expand over time as we enqueue and dequeue, since enqueueing and dequeueing both advance their indexes toward the end of the array.

Question 26

When implementing a queue as an array, you can think of it as a circular array.

Question 27

The isFull and isEmpty methods enable a client program to check if the queue is full or empty before enqueueing or dequeueing a Player.

Question 28

A linked list that stores its values in ascending order (or descending order) according to a key value is called a(n) _______-linked list.

A) stack
B) sorted
C) ID
D) arrange

Question 29

setData( int i ) is the best choice for coding the insert method of the Node class to enter the days of the week.

Question 30

A doubly linked list provides two links between nodes, one forward and one backward.

Question 31

Which of the following is correct regarding the GenericLinkedList class and the PlayerLinkedList class?

A) The code differs in the class header.
B) The code for the declaration of the instance variable head is different.
C) The classes implement the same methods.
D) All of these are correct.

Question 32

A recursively defined linked list is made up of:

A) first and rest.
B) the most important list items in the node.
C) linked lists that can be accessed only through the node class.
D) All of these are correct.

Question 33

In a circular array of 5 elements, the element after the element at index 4 is the element at index:

A) 5.
B) 0.
C) -1.
D) 4.

Question 34

Consider a queue represented by an array of 10 elements and front and back, the two instance variables representing the indexes of the front and the back of the queue, respectively. If the value of front is 8 and the value of back is 7, what can you tell about the queue?

A) It is empty.
B) It is full.
C) It is neither empty nor full.
D) It is either empty or full.

Question 35

When we delete the first node in a list, we always set head to null.

Question 36

When we successfully delete an item from a list, the number of items in a list decreases by 1.

Question 37

Assuming a linked list is properly coded, attempting to delete from an empty list should not result in a NullPointerException.

Question 38

A stack is never empty.

Question 39

In a queue represented by a linked list, we insert, or enqueue, at the beginning of the list.

Question 40

We can only have a sorted linked list of basic data types.

Question 41

A doubly linked list allows us to go either forward or backward from a given node.

Question 42

We cannot use recursion in linked lists.

Question 43

A queue is never empty.

Question 44

Visiting each node in a list by following the links is called __________.

Question 45

When coding a method of a recursively defined linked list, not testing for all base case scenarios could result in a(n) __________ at runtime.

Question 46

A linked list:

A) has a fixed size.
B) can grow and shrink as items are added or deleted.
C) can grow but not shrink because items can be added but not deleted.
D) can shrink but not grow because items can be deleted but not added.

Question 47

A node of a linked list typically has which of the following?

A) Two attributes: data and the location of the next node
B) Only one attribute: data
C) Only one attribute: the location of the next node
D) None of these is correct.

Question 48

A queue uses:

A) )last in, first out.
B) first in, last out.
C) first in, first out.

Question 49

When inserting an element in the middle of a doubly linked list, how many pointers need to be reset?

A) 0
B) 1
C) 2
D) 3
E) 4

Question 50

When deleting an element in the middle of a doubly linked list, how many pointers need to be reset?

A) 0
B) 1
C) 2
D) 3
E) 4

Question 51

When using an identifier, for example T, to represent a class that uses generics, what characters surround that identifier?

A) [ and ]
B) { and }
C) < and >
D) ( and )

Question 52

When we attempt to delete an item from a list but it is not on the list, the method returns void.

Question 53

Unless we run out of memory, we can always insert in a linked list.

Question 54

In an empty list, head is null.

Question 55

In a stack represented by a linked list, we push at the beginning of the list.

Question 56

In a stack represented by a linked list, we pop at the end of the list.

Question 57

In a stack represented by a linked list, we delete based on the value of the item stored in a node.

Question 58

If we know in advance the maximum number of items we will have in a stack, then we can use an array to represent the stack.

Question 59

If we know in advance the maximum number of items we will have in a queue, then we can use an array to represent the queue.

Question 60

In a sorted linked list, we insert in such a way that the list is still sorted after the insertion.

Question 61

In a sorted linked list, we always insert in the middle of the list.

Question 62

In a sorted linked list, it is possible that the linked list may not be sorted after a deletion.

Question 63

Consider a stack represented by an array and top, the instance variable representing the index of the top of the stack; when the stack is empty, the value of top is __________.

Question 64

Consider a stack represented by an array of five elements and top, the instance variable representing the index of the top of the stack; when the stack is full, the value of top is __________.

Question 65

For a linked list of objects, a delete method that returns an object (the object deleted, if any) throws an exception. Why?

Question 66

In a linked list representing a queue, what extra instance variable is desirable to have and why?

Question 67

Evaluate what is wrong with the following code, and recommend an alternative code.
while ( current.getData( ) != value && current != null )

Question 68

Analyze why a mutator method should not be included for the number of items in a list.

Question 69

In a queue represented by an array, how do we tell if the queue is empty or full?