Lists, Stacks, and Queues
0.0(0)
Studied by 0 people
Learn
Practice Test
Spaced Repetition
Match
FlashcardsCard Sorting
1/15
Earn XP
Description and Tags
Study Analytics
Name | Mastery | Learn | Test | Matching | Spaced |
|---|
No study sessions yet.
16 Terms
1
New cards
What is the time complexity of the push/enqueue operation for stacks and queues?
\
O(1)
O(n)
O(log n)
\
O(1)
O(n)
O(log n)
O(1)
2
New cards
What is the time complexity of the pop/dequeue operation for stacks and queues?
\
O(n^2)
O(n)
O(1)
\
O(n^2)
O(n)
O(1)
O(1)
3
New cards
What is the time complexity of the top/front/peek operation for stacks and queues?
\
O(n)
O(1)
O(log n)
\
O(n)
O(1)
O(log n)
O(1)
4
New cards
What is the computational complexity of adding an item to a Queue in the worst case in terms of Big O notation?
\
O(log n)
O(n)
O(1)
O(n log n)
\
O(log n)
O(n)
O(1)
O(n log n)
O(1)
5
New cards
Consider the following operations on a stack:
After the completion of all operations, what will size() operation result in? (Note: C++ stacks have a size() method)
After the completion of all operations, what will size() operation result in? (Note: C++ stacks have a size() method)
2
6
New cards
Consider the following operations on a queue:
After completing all of the operations, what value is at the front of the queue?
After completing all of the operations, what value is at the front of the queue?
2
7
New cards
What is the computational complexity of adding an item to a Stack using a Linked List based implementation in the worst case in terms of Big O notation?
\
O(1)
O(log n)
O(n)
O(n^2)
\
O(1)
O(log n)
O(n)
O(n^2)
O(1)
8
New cards
Which of the following statements about linked lists and arrays are TRUE?
\
Linked Lists are more efficient if you have to access elements with O(1) time
Linked Lists are more efficient if you need random access
Both are linear data types
Both data structures can use iterators
Both data structures store elements sequentially (contiguously) in memory
\
Linked Lists are more efficient if you have to access elements with O(1) time
Linked Lists are more efficient if you need random access
Both are linear data types
Both data structures can use iterators
Both data structures store elements sequentially (contiguously) in memory
Both are linear data types
Both data structures can use iterators
Both data structures can use iterators
9
New cards
What is the computational complexity of deleting an element, e from a doubly linked list with tail in the worst case in terms of Big O notation? Assume the list has n items
\
O(log n)
O(n)
O(n^2)
O(1)
\
O(log n)
O(n)
O(n^2)
O(1)
O(n)
10
New cards
Which of the following container(s) is/are List ADT implementation(s) in C++) \[Select all that apply\]
\
main()
Forward List
Array
Vector
Integer
Iterator
\
main()
Forward List
Array
Vector
Integer
Iterator
Forward List
Array
Vector
Array
Vector
11
New cards
Doubly linked lists allow random access in the container in constant time
\
True
False
\
True
False
False
12
New cards
State the output of the following C++ program. If the program has a compiler or runtime error, write error in the box; if the program demonstrates undefined behavior, write undefined in the box)
54321
13
New cards
![What type of iterator does the container in the following C++ code implement \[Select the broadest category\]:
\
Forward
Random access
Bidirectional
Input/Output](https://knowt-user-attachments.s3.amazonaws.com/60aa3c1b75be4a359d4269d7de511a08.jpeg)
What type of iterator does the container in the following C++ code implement \[Select the broadest category\]:
\
Forward
Random access
Bidirectional
Input/Output
\
Forward
Random access
Bidirectional
Input/Output
Bidirectional
14
New cards
What are the four List implementations?
Array
Vector
Forward list, with and without tail
List, with tail
Vector
Forward list, with and without tail
List, with tail
15
New cards
What are the two Stack implementations?
Array
Forward list, no tail
Forward list, no tail
16
New cards
What is an example of a Queue implementation?
Array