Data Structures Lec 4 - 8: Vectors, Lists, Stacks, Queues

200 question-and-answer style flashcards covering template classes, vectors, linked lists, stacks, queues, deques, iterators, and related algorithms from the lecture notes.

What is a C++ template class?

A. Class parameterized by type.

B. A precompiled library.

C. A function pointer.

D. An object instance.

A. Class parameterized by type.

Which keyword syntax begins a template class declaration in C++?

A. class<T>

B. template<typename T>

C. typedef<T>

D. generic<class T>

B. template<typename T>

In the STL, what kind of container is called a sequence?

A. Elements inserted/removed arbitrarily.

B. Key-value pairs organized.

C. Sorted unique elements.

D. Fixed-size memory storage.

A. Elements inserted/removed arbitrarily.

What header file must be included to use std::vector?

A. <list>

B. <array>

C. <vector>

D. <memory>

C.

What placeholder represents the actual data type in a template class declaration?

A. Type identifier.

B. Template parameter T.

C. Argument type.

D. Generic placeholder K.

B. Template parameter T.

What header file must be included to use std::vector?

A. <list>

B. <array>

C. <vector>

D. <memory>

C. <vector>

Give an example of instantiating a template class called some_container with Person objects.

A. some_container<Person> example;

B. some_container example;

C. some_container(Person) example;

D. some_container<object> example;

A. some_container<Person> example;

Name one key advantage a vector has over a built-in array?

A. Faster access by index.

B. Automatic size growth.

C. Stores different types.

D. Lower memory usage.

B. Automatic size growth.

What operation adds an element to the end of a vector?

A. add()

B. insert_end()

C. push_front()

D. push_back()

D. push\_back

Which vector member function returns the current number of stored elements?

A. capacity()

B. length()

C. size()

D. count()

C. size()

Which vector property indicates how many elements it can store before reallocating?

A. size

B. length

C. capacity

D. limit

C. capacity

Which member function reserves storage space for future vector growth?

A. allocate()

B. resize()

C. reserve()

D. expand()

C. reserve()

Which vector member function inserts an element at a specified position?

A. add_at()

B. place()

C. insert()

D. append()

C. insert()

Which vector member function removes an element at a specified position?

A. remove()

B. clear_at()

C. delete_at()

D. erase()

D. erase()

What is the difference between operator[] and at() when accessing vector elements?

A. at() is faster.

B. operator[] checks range.

C. at() throws exception.

D. operator[] is safer.

C. at() throws exception.

What is the average time complexity of vector::push\\_back?

A. O(n)

B. O(log n)

C. O(1)

D. O(1) amortized.

D. O(1) amortized.

How does a vector typically grow when it runs out of capacity?

A. Adds one element.

B. Doubles capacity.

C. Increases by 50%.

D. Creates a new vector.

B. Doubles capacity.

Which vector member function creates a deep copy of another vector during assignment?

A. copy()

B. clone()

C. Assignment operator (operator=).

D. duplicate()

C. Assignment operator (operator=).

What three special functions make up C++’s Rule of Three?

A. Constructor, destructor, method.

B. Copy constructor, assignment, destructor.

C. Push, pop, top.

D. Begin, end, size.

B. Copy constructor, assignment, destructor.

What does a vector’s destructor do?

A. Clears all elements.

B. Deletes dynamic array memory.

\n\n C. Shrinks capacity.

D. Resets size to zero.

B. Deletes dynamic array memory.

What data field in a custom vector tracks the physical size of the underlying array?

A. logical_size

B. current_capacity

C. element_count

D. allocated_size

B. current\_capacity

What data field in a custom vector tracks the logical number of items?

A. max_capacity

B. num_items

C. array_size

D. current_elements

B. num\_items

Why is size\_t used for vector indexes?

A. Requires less memory.

B. Faster arithmetic.

C. Unsigned, non-negative index.

D. Universal integer type.

C. Unsigned, non-negative index.

What is the time complexity of inserting an element in the middle of a vector?

A. O(1)

B. O(log n)

C. O(n)

D. O(n^2)

C. O(n)

What is a node in a linked list?

A. A data item.

B. A pointer to data.

C. Data and pointers.

D. A list segment.

C. Data and pointers.

In a singly linked list node, what does the field next store?

A. Pointer to previous node.

B. Data value.

C. Pointer to next node.

D. Node index.

C. Pointer to next node.

Why are insertions and removals after a referenced node in a singly linked list O(1)?

A. Cache hit rates are high.

B. Pointer assignments, no shifting.

C. Directly addressed.

D. Small data size.

B. Pointer assignments, no shifting.

Why is inserting at an arbitrary position in a vector O(n)?

A. Memory must be reallocated.

B. Elements must shift.

C. Accessing index takes time.

D. Sorting is required.

B. Elements must shift.

When building a list by adding each new node to the front, which pointer must be updated?

A. Tail pointer.

B. Current pointer.

C. Head pointer.

D. Last pointer.

C. Head pointer.

To insert a node after a referenced node in a singly list, how many pointer changes are needed?

A. One.

B. Two.

C. Three.

D. Four.

B. Two.

To remove the node after a referenced node in a singly list, what must you do first?

A. Update the next pointer.

B. Save node pointer.

C. Set node to NULL.

D. Adjust head pointer.

B. Save node pointer.

Why can’t singly linked lists be traversed backward without additional data?

A. No previous link.

B. Only forward link.

C. Data stored elsewhere.

D. Not designed for it.

B. Only forward link.

What is the average complexity of inserting a node before a given node in a singly list?

A. O(1)

B. O(\log n)

C. O(n)

D. O(n \text{ log n})

C. O(n) for predecessor.

What extra pointer does a doubly linked list node contain beyond next?

A. first

B. prev

C. parent

D. back

B. prev

How long does it take to insert a node before a known node in a doubly linked list?

A. O(n)

B. O(log n)

C. O(1)

D. O(n^2)

C. O(1)

What is the primary disadvantage of doubly linked lists compared to singly lists?

A. Slower traversal.

B. More complex deletion.

C. More memory, overhead.

D. Cannot be reversed.

C. More memory, overhead.

What simple modification turns a doubly linked list into a circular list?

A. Set head to tail.

B. Link the tail’s next to head.

C. Make all nodes self-referential.

D. Add a counter.

B. Tail links to head.

What major risk comes with circular lists during traversal?

A. Memory leaks.

B. Data corruption.

C. Infinite loop.

D. Stack overflow.

C. Infinite loop.

How can you detect if a list is circular given a pointer to any node?

A. Check if head is NULL.

B. Return to start node.

C. Compare node addresses.

D. Count total nodes.

B. Return to start node.

What is an iterator?

A. A fixed memory address.

B. A movable container position marker.

C. A direct data pointer.

D. A container's size.

B. Movable container position marker.

What does operator\\* on a list iterator return?

A. The iterator itself.

B. A copy of the data.

C. Reference to data.

D. The node address.

C. Reference to data.

Which operator advances a list iterator to the next node?

A. operator--

B. operator+

C. operator++

D. operator->

C. operator++

What is a const\\_iterator used for?

A. Modifying container elements.

B. Read-only iteration.

C. Backward traversal only.

D. Iterating constant containers.

B. Read-only iteration.

Which list member returns an iterator to the first element?

A. front()

B. begin()

C. start()

D. head()

B. begin()

Which list member returns an iterator that represents the position past the last element?

A. last()

B. end()

C. tail()

D. out()

B. end()

Which list function inserts at the front of a doubly linked list?

A. add_front()

B. insert_first()

C. push_front()

D. prepend()

C. push\_front()

What does list::insert return?

A. The inserted data.

B. Iterator to new node.

C. A boolean indicating success.

D. Number of elements.

B. Iterator to new node.

Which function removes the first node of a list?

A. remove_first()

B. delete_front()

C. pop_front()

D. shift()

C. pop\_front()

Which function removes the last node of a list?

A. remove_last()

B. erase_end()

C. pop_back()

D. cut_end()

C. pop\_back()

What does list::erase(pos) return?

A. Iterator to erased node.

B. Iterator to preceding node.

C. Iterator to following node.

D. void.

C. Iterator to following node.

How does the list copy constructor usually copy another list?

A. Copies memory block.

B. Deep copies pointers.

C. push\_back each element.

D. Swaps contents.

C. push\_back each element.

Why should a list destructor delete nodes directly instead of using pop\_back in a loop?

A. More readable code.

B. Avoid unnecessary traversal.

C. Ensures proper memory access.

D. Better error handling.

B. Avoid unnecessary traversal.

What does the list assignment operator typically do internally?

A. Direct memory copy.

B. Copy-and-swap.

C. Shallow copy.

D. Resizes memory.

B. Copy-and-swap.

What storage policy governs a stack?

A. First-In, First-Out (FIFO).

B. Last-In, First-Out (LIFO).

C. Random Access.

D. Priority-based.

B. Last-In, First-Out (LIFO).

Name the four fundamental public operations of a stack.

A. add(), remove(), get(), is_empty()

B. push(), pop(), peek(), size()

C. empty(), top(), pop(), push()

D. insert(), delete(), front(), back()

C. empty(), top(), pop(), push()

Which stack member returns its logical size?

A. count()

B. length()

C. capacity()

D. size()

D. size()

When implementing a stack with a vector, which vector function is used for push?

A. insert()

B. add()

C. push_back()

D. append()

C. push\_back()

In a linked-list stack, what pointer points to the stack’s top?

A. bottom_of_stack

B. tail

C. top_of_stack (head).

D. current_node

C. topofstack (head).

Which stack-based algorithm can determine whether a string is a palindrome?

A. Recursively compare halves.

B. Use a two-pointer approach.

C. Push/pop for reverse.

D. Store in a hash table.

C. Push/pop for reverse.

How can a stack convert a positive decimal integer to binary?

A. Iterate and concatenate.

B. Push/pop remainders.

C. Convert to hexadecimal first.

D. Use bitwise operations.

B. Push/pop remainders.

Which data structure is most suitable for checking balanced parentheses?

A. A queue.

B. A stack.

C. A linked list.

D. A vector.

B. A stack.

What condition indicates a mismatch when checking parentheses?

A. Stack overflow occurs.

B. Empty or no match.

C. Non-parenthesis character.

D. String is too long.

B. Empty or no match.

How can undo/redo be modeled with stacks?

A. Use a single queue.

B. Two stacks: undo, redo.

C. A doubly linked list.

D. Store actions in an array.

B. Two stacks: undo, redo.

What storage policy governs a queue?

A. Last-In, First-Out (LIFO).

B. First-In, First-Out (FIFO).

C. Random access.

D. Priority-based.

B. First-In, First-Out (FIFO).

Name three basic public operations of a queue.

A. add(), remove(), get()

B. insert(), delete(), peek()

C. enqueue(), dequeue(), peek()

D. push(), pop(), front().

D. push(), pop(), front().

In a linked-list queue, which pointer references the node to be removed next?

A. back_of_queue

B. front_of_queue

C. current_node

D. head

B. frontofqueue

Why is a circular array queue more efficient than a simple array queue for pop?

A. Uses less memory.

B. No element shifting.

C. Easier to implement.

D. Faster initial setup.

B. No element shifting.

Which two indexes are tracked in a circular array queue?

A. start_index, end_index

B. head_index, tail_index

C. front_index, rear_index

D. first, last_element

C. frontindex, rearindex

When a circular queue becomes full, what must be done before inserting?

A. Wait for space.

B. Reallocate larger array.

C. Discard oldest element.

D. Throw an error.

B. Reallocate larger array.

After reallocation of a circular queue, to what does front\_index reset?

A. To original front.

B. To current rear.

C. 0.

D. To capacity - 1.

C. 0

What field in a circular queue tracks the number of stored items?

A. max_size

B. capacity

C. num_items

D. item_count

C. num\_items

What is the advantage of a circular queue’s O(1) push/pop operations?

A. Uses contiguous memory.

B. Reduced memory footprint.

C. No element shifting.

D. Simplified iterator design.

C. No element shifting.

How does a simple priority queue differ from a FIFO queue?

A. Enqueue is faster.

B. Pop removes highest value.

C. It's a LIFO structure.

D. Only stores integers.

B. Pop removes highest value.

What feature distinguishes a deque from both a stack and a queue?

A. Supports random access.

B. Insert/remove both ends.

C. Guaranteed sorted order.

D. Fixed memory size.

B. Insert/remove both ends.

Why does std::deque support random-access iterators while std::queue does not?

A. std::queue is abstract.

B. std::deque uses linked list.

C. Block-based storage.

D. std::queue is for LIFO.

C. Block-based storage.

In a block-based deque implementation, what does offset store?

A. Total memory used.

B. Current block number.

C. Size of each block.

D. Index of first element.

D. Index of first element.

How is operator[] implemented for a block-based deque?

A. Linear scan.

B. Compute block/data index.

C. Direct array access.

D. Hash table lookup.

B. Compute block/data index.

When push\_back causes a deque to exceed capacity, what is typically added?

A. New block.

B. Array is doubled.

C. All elements shifted.

D. Memory is reallocated.

A. New block.

What happens when popfront causes offset to equal BLOCKSIZE?

A. Queue becomes empty.

B. First block deleted.

C. Offset is reset to zero.

D. All remaining elements shift.

B. First block deleted.

Give one real-world example where stacks are used in software?

A. Network packet routing.

B. Web browser history.

C. Compilers: function call stack.

D. Online banking transactions.

C. Compilers: function call stack.

Give one real-world example where queues are used?

A. Word processor spell check.

B. Image pixel manipulation.

C. Print spoolers.

D. Game character movement.

C. Print spoolers.

What string constants are often used in balanced-parentheses code for quick matching?

A. BRACKETS, PARENS

B. OPEN, CLOSE strings.

C. BEGIN, END

D. LEFT, RIGHT

B. OPEN, CLOSE strings.

When a postfix evaluator reads a digit token, what does it do with it?

A. Evaluates immediately.

B. Pushes to operator stack.

C. Push to operand stack.

D. Ignores it.

C. Push to operand stack.

In a postfix expression evaluator, what is done when an operator token is read?

A. Store on operator stack.

B. Pop, apply, push.

C. Print to console.

D. Error out.

B. Pop, apply, push.

Why does a palindrome algorithm need to empty the stack at the end?

A. To free memory.

B. Build reverse string.

C. Verify stack integrity.

D. Clear for next use.

B. Build reverse string.

In the decimal-to-binary algorithm, why are remainders pushed on a stack?

A. To calculate sums.

B. Reverse order for pop.

C. To prevent overflow.

D. For quick retrieval.

B. Reverse order for pop.

What is the top pointer set to after a linked-list stack pop?

A. Old node's address.

B. NULL always.

C. topofstack->next.

D. Previous node's address.

C. topofstack->next.

What should a stack pop do if the stack is empty?

A. Return default value.

B. Do nothing silently.

C. Throw exception.

D. Print warning.

C. Throw exception.

What key responsibility does a destructor have in any class that allocates dynamic memory?

A. Initialize all members.

B. Free allocated memory.

C. Close open files.

D. Perform deep copy.

B. Free allocated memory.

When is the copy constructor automatically invoked?

A. Object created with new.

B. Assigning objects.

C. Pass/return/initialize object.

D. Calling member function.

C. Pass/return/initialize object.

What is a shallow copy?

A. Duplicates all data.

B. Pointers duplicated, data shared.

C. Only basic types copied.

D. Creates a new object by default.

B. Pointers duplicated, data shared.

What is a deep copy?

A. Copies pointer values only.

B. Duplicates all pointers.

C. Independent data copy.

D. Copies references to data.

C. Independent data copy.

Why does list::erase return an iterator to the following node?

A. To point to the beginning.

B. Loop can continue safely.

C. It returns the removed node.

D. To indicate end of list.

B. Loop can continue safely.

What must list::begin() return when the list is empty?

A. NULL.

B. The same iterator value as end().

C. A valid iterator to nothing.

D. An error value.

B. Same as end().

How does operator++(int) (postfix) differ from prefix ++ for iterators?

A. Postfix is faster.

B. Prefix returns copy.

C. Postfix returns original.

D. They are identical.

C. Postfix returns original.

What does list::empty() return when the list contains nodes?

A. true

B. 1

C. 0

D. false

D. false

Which list function increases num\_items after adding a node at the front?

A. insert_first()

B. add_head()

C. push_front()

D. increment_size()

C. push\_front()

Which list function decreases num\_items after removing from the back?

A. remove_last()

B. pop_back()

C. delete_end()

D. decrement_size()

B. pop\_back()

In an airline simulation, what variable stores the time the current service will finish?

A. service_time

B. finish_time

C. arrival_time

D. time_done

D. time\_done

What does an arrival\_rate represent in the simulation?

A. Total passengers served.

B. Average wait time.

C. Passenger arrival probability.

D. Service duration.

C. Passenger arrival probability.