DSABook – Review questions

6.12 Review questions

This final section contains some review questions about the contents of this chapter.

6.12.1 Review questions: Stacks and queues

Here are some general practice questions about stacks and queues.

Which value of a stack is accessible?

Stacks do not care about the relative order of the values for the items it stores.
A stack gives access only to the last item that was inserted.
This is called the “top” item.

It is an error to pop data from a(n) _______ stack.

“Pop” means to remove.
When can we not remove anything?

In the linked implementation of a queue, a new item would be added:

At the rear
At the head
At the current position
After all other entries that are greater than the new entry
After all other entries that are smaller than the new entry

We don’t care about value order in a queue.
In a queue, we always add at the rear.

The following sequence of operations is performed on a queue:

enqueue(1), enqueue(2), dequeue, enqueue(1), enqueue(2), dequeue, dequeue, dequeue, enqueue(2), dequeue

The values will be output in this order:

Trace the operations, one by one.

One difference between a queue and a stack is:

Queues use two ends of the structure; stacks use only one
Queues require linked lists, but stacks do not
Stacks require linked lists, but queues do not
Stacks use two ends of the structure, queues use only one

Stacks and queues can both be implemented using a linked structure.
The key difference is which end(s) the two stuctures access for insert and remove operations.

If the characters ‘D’, ‘C’, ‘B’, ‘A’ are placed in a stack (in that order), and then removed one at a time, in what order will they be removed?

ABCD
ABDC
DCAB
DCBA

Items come off of a stack in the opposite order from how they went in.

Queue behaviour is typically referred to as:

First-In, First-Out
Last-In, First-Out
First Come, First Served
Just-in-Time

In a queue, we remove the one that came in first.

It is an error to dequeue data from a(n) _______ queue.

Empty
Full
Array-based
Linked

“Dequeue” means to remove. When can we not remove from a queue?-

Which value of a queue is accessible?

In a queue, we remove from (access) the front (and insert at the rear).

The Stack is best characterised as:

Last-In, First-Out
First-In, First-Out
First come, First Served
Just-in-Time

The queue is called “First-in, First-out”
The stack is called “Last-in, First-out”

In the linked implementation of a queue, a new item would be added to the:

Rear
Front
Current position
None of these

In any queue implementation, we always add to the rear.

If the characters ‘D’, ‘C’, ‘B’, ‘A’ are placed in a queue (in that order), and then removed one at a time, in what order will they be removed?

DCBA
ABCD
ABDC
DCAB

Items are removed from a queue in the same order as they arrived.

Stack A has entries a, b, c (in that order with a on top), while Stack B is initially empty. When an entry is popped out of stack A, it can be printed immediately or pushed to stack B. When an entry is popped out of stack B, it can only be printed. Which of the following permutations of a, b, c is not possible to print?

c a b
b a c
b c a
a b c

We can manage to get “c” to print first.
But to do so requires putting “a” and then “b” into stack B.-
Which then means that they must come out of B and be printed in reverse order.

The following sequence of operations is performed on a stack:

push(1), push(2), pop, push(1), push(2), pop, pop, pop, push(2), pop

The values will be output in this order:

Trace the series of operations onto a stack.

6.12.2 Review questions: Linked lists

Answer TRUE or FALSE.

The physical order in memory for the nodes of a linked list is the same as the order in which the nodes appear in the list.

True
False

When you create a new object, you have no control over where it is in memory.

Answer TRUE or FALSE.

In a singly linked list implementation, to access the predecessor of the current node we must start at the first node in the list.

True
False

In a singly linked list we are unable to move directly backwards in the list.
So, the only alternative is to start at the front and move down to the previous node.

In a linked list, the successive elements in the list:

Need not occupy contiguous space in memory
Must occupy contiguous space in memory
Must not occupy contiguous space in memory
None of these

Unlike an array-based list, the linked list is created by linking together separate objects.
Those objects can be created at any time, and you don’t control where they are in memory when they are made.

To find an element with value $X$ in a linked list with $n$ nodes requires how many nodes to be visited in the worst case?

How many nodes might we have to visit to find the one that we are looking for?

Given a linked list implementation, inserting a new element to arbitrary position $i$ takes how long in the average case?

We can’t insert until we reach the proper position.
How long does it take to reach position $i$ in a linked list?
Once we get there, it takes only a couple of assignments to put the new node in place.

Given a linked list implementation, deleting the element at arbitrary position $i$ takes how long in the average case?

You cannot delete a node until you get to it.
Starting from the front, how long does it take to get to the $i$ th node?
Once you do reach the node, then you can remove it in constant time.

To access the node at position $i$ in a singly-linked list

requires that all its predecessors be visited
takes one step
takes two steps
requires that all its successors be visited

How can we reach the $i$ th position?
We have to work from the front.

6.12.3 Review questions: Static array-based lists

In an array-based list, the successive elements in the list:

Must occupy contiguous space in memory
Need not occupy contiguous space in memory
Must not occupy contiguous space in memory
None of these

The list elements are stored in an array.
Where in the array should they go?
The list element in list position $i$ will be stored in array position $i$ .

Given an array-based list implementation, inserting a new element just before the last value takes how long in the worst case?

$O(1)$ time
$O(n)$ time
$O(\log n)$ time
$O(n \log n)$ time

We only need to shift one single value: the last element.

Given an array-based list implementation, inserting a new element to arbitrary position $i$ takes how long in the worst case?

$O(n)$ time
$O(1)$ time
$O(\log n)$ time
$O(n \log n)$ time

Position $i$ could be anywhere in the list.
We will need to shift values from position $i$ to the list end forward by one position.
How many we shift depends on the value of $i$ .
In the worst case, it will be all the elements in the list.

Given an array-based list implementation, deleting the second-to-last element takes how long in the worst case?

$O(1)$ time
$O(n)$ time
$O(\log n)$ time
$O(n \log n)$ time

We only need to shift one single value: the last element.

Given an array-based list implementation, deleting the element at an arbitrary position $i$ takes how long in the worst case?

$O(n)$ time
$O(1)$ time
$O(\log n)$ time
$O(n \log n)$ time

Position $i$ could be anywhere in the list (of $n$ values).
We will need to shift values from position $i$ to the list end back by one position.
How many we shift depends on the value of $i$ .
In the worst case, it will be all the elements in the list.

6.12.4 Summary questions

Here are some general practice questions about various data structures in this chapter.

The term “LIFO” is associated with which data structure?

LIFO means “Last-in, First-out”.

Which of the following is not a linear data structure?

We studied all of these data structures in this chapter.

Which data structure would be used to implement recursion?

When unwinding from recursion, we say that you “pop” the recursive “stack”.

Which data structure allows insertion only at the top, and deletion only at the top?

We use the term “top” with only one of these data structures.
We add and remove at the “top” with the stack.

Which data structure allows insertion only at the back, and removing only from the front?

We did not cover trees in this chapter.
Lists do not restrict where inserts and removes take place.

The terms “enqueue” and “dequeue” are associated with which data structure?

What does “enqueue” and “dequeue” mean?

The terms “add/insert” and “delete” are traditionally associated with which data structure(s)?

Stacks and Queues have special terminology that is used instead of the more general “insert” and “delete”.

The term “FIFO” is associated with which data structure?

FIFO means “first-in, first-out”

Which of the following is not a linear data structure?

Which is the one data structure not covered in this chapter?

The terms “push” and “pop” are associated with which data structure?

“Push” and “pop” are special terminology associated with one of these data structures.
You push items onto a stack, and pull them off.