Data Structures Test 2 Review Queues

Question 1

Singly Linked List

Answer 1

a structure consisting of a sequence of nodes

Question 2

A singly linked list stores a _________ to the first node (head) and last (tail)

Answer 2

pointer

Question 3

In a singly linked list, each node stores…

Answer 3

an elementa link to the next node

Question 4

template class SLinkedListNode { public: Type elem; [WHAT GOES HERE?] };

Answer 4

SLinkedListNode *next;

Question 5

Singly Linked List Operation: insertFront(e):

Answer 5

inserts an element on the front of the list

Question 6

Singly Linked List Operation: removeFront():

Answer 6

returns and removes the element at the front of the list

Question 7

Singly Linked List Operation: insertBack(e):

Answer 7

inserts an element on the back of the list

Question 8

Singly Linked List Operation: removeBack():

Answer 8

returns and removes the element at the end of the list

Question 9

Stack with a Singly Linked List: The _______ element of the stack is the ______ ______ of the list

Answer 9

topfirst node

Question 10

Stack with a Singly Linked List: The space used is ______ and each operation of the Stack ADT takes _______ time

Answer 10

O(n)O(1)

Question 11

Stack Operation: push(e) is most like what Singly Linked List Operation?

Answer 11

insertFront(e)

Question 12

Stack Operation: pop() is most like what Singly Linked List Operation?

Answer 12

removeFront()

Question 13

What 2 Singly Linked List Operations do not work with Stack Operations?

Answer 13

insertBack(e)removeBack()

Question 14

With minor alteration or addition, top() could be very similar to…

Answer 14

removeFront()

Question 15

_______ and ________ would require the addition of a counter that increments each time push() is called and decrements when pop() is called

Answer 15

size() isEmpty()

Question 16

Queues store…

Answer 16

arbitrary objects

Question 17

Main queue operations:

Answer 17

enqueue(e)dequeue()

Question 18

Enqueue(e): aka addQueue, aka push

Answer 18

inserts an element at the end of the queue

Question 19

Dequeue(): aka deleteQueue, aka pop

Answer 19

removes and returns the element at the front of the queue

Question 20

Auxiliary queue operations:

Answer 20

front()size()isEmpty()

Question 21

Less common queue operations

Answer 21

back()isFullQueue()

Question 22

front():

Answer 22

returns the element at the front without removing it

Question 23

size():

Answer 23

returns the number of elements stored

Question 24

isEmpty():

Answer 24

returns a Boolean value indicating if there are no elements in the queue

Question 25

back():

Answer 25

returns the element at the back without removing it

Question 26

isFullQueue():

Answer 26

returns if queue is full

Question 27

In a queue, insertions are at the _____ of the queue and removals are at the ______ of the queue

Answer 27

endfront

Question 28

Queue exceptions: Attempting to execute dequeue or front on an empty queue throws a(n)…

Answer 28

EmptyQueueException

Question 29

template class queueADT { public: virtual bool isEmptyQueue() const = 0; }

Answer 29

// function to determing whether the queue is empty// post condition: returns true if the queue is empty, otherwise returns false

Question 30

template class queueADT { public: virtual bool isFullQueue() const = 0; }

Answer 30

// function to determine whether the queue is full// post condition: returns true if the queue is full, otherwise returns false

Question 31

template class queueADT { public: virtual void initializeQueue() const = 0; }

Answer 31

// function to initialize the queue to an empty state// post condition: the queue is empty

Question 32

template class queueADT { public: virtual Type front() const = 0; }

Answer 32

// function to return the first element of the queue// precondition: the queue exists and is not empty// post condition: if the queue is empty, the program terminates; otherwise, the first element of the queue is returned

Question 33

template class queueADT { public: virtual Type back() const = 0; }

Answer 33

// function to return the last element of the queue// precondition: the queue exists and is not empty// post condition: if the queue is empty, the program terminates; otherwise, the first element of the queue is returned

Question 34

template class queueADT { public: virtual void addQueue(const Type& queueElement) = 0; }

Answer 34

// function to add queueElement to the queue// precondition: the queue exists and is not full// post condition: the queue is changed and queueElement is added to the queueaka pushaka enqueue

Question 35

template class queueADT { public: virtual void deleteQueue() const = 0; }

Answer 35

// function to remove the first element of the queue// precondition: the queue exists and is not empty// post condition: the queue is changed and the first element is removed from the queueaka popaka dequeue

Question 36

Main queue operation: enqueue(e) is most like what Singly Linked List Operation?

Answer 36

insertBack(e)

Question 37

Main queue operation: dequeue() is most like what Singly Linked List Operation?

Answer 37

removeFront()

Question 38

Main queue operation: front() would require a minor alteration or addition to LinkedList and would be very similar to…

Answer 38

removeFront()

Question 39

Doubly Linked List

Answer 39

a structure consisting of a sequence of nodes