Exam 1-4 and Sets, Maps, Hash tables and Graphs for Data Structures 2025 with Hailey Fields
Studied by 0 people
Learn
Practice Test
Spaced Repetition
Match
Flashcards1/92
There's no tags or description
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced |
|---|
No study sessions yet.
93 Terms
Which statement is correct?
Every data structure has a specific algorithm to implement a certain operation
3 multiple choice options
Which of the following best describes the relationship between the list ADT and the array data structure?
An array is one of several data structures that can be used to implement the list ADT
3 multiple choice options
In a computational problem for finding the highest salary of an employee in a company, what is the input?
The list of employees' salaries
3 multiple choice options
Space complexity analysis helps in avoiding algorithms with _____.
high memory usage
3 multiple choice options
An algorithm's _____ runtime complexity is the scenario where the algorithm does the minimum possible number of operations.
best case
3 multiple choice options
Which is NOT a known characteristic of an NP-complete problem?
All NP-complete problems can be solved efficiently.
3 multiple choice options
ADTs allow programmers to _____.
focus on higher-level operations as per a program's needs
3 multiple choice options
The process of providing only the essentials and hiding the details is known as _____.
abstraction
3 multiple choice options
What is the difference between best case and worst case runtime complexity?
Best case: the scenario where the algorithm does the minimum possible number of operations
Worse case: the scenario where the algorithm does the maximum possible number of operations
3 multiple choice options
Which is an abstract data type (ADT)?
A list
3 multiple choice options
Which of the following statements best describes the relationship between data structures and algorithms?
An efficient algorithm is only as efficient as its choice of data structure
3 multiple choice options
An algorithm to determine the top five salespersons is most likely to utilize what other algorithm?
An algorithm to sort an array in descending order
3 multiple choice options
Which of the following statements is true with reference to searching algorithms?
Binary search starts from the center of a sorted list.
3 multiple choice options
The best case runtime complexity of an algorithm that searches an array of size N is _____.
O(1)
3 multiple choice options
Which of the following statements is true?
Linear search will compare all elements if the search key is not present.
3 multiple choice options
What is the worst-case runtime complexity of the binary search algorithm?
O(log n)
3 multiple choice options
Which is the BEST case scenario when the linear search algorithm searches an array for key 42?
42 is the array's first element
3 multiple choice options
Identify the correct sequence of performing a binary search.
1. Binary search first checks the middle element of the list.
2. If the search key is not found, the algorithm:
i. checks the left sublist if the search key is less than the middle element or
ii. checks the right sublist if the search key is greater than the middle element.
3 multiple choice options
An call is made to RecursiveBinarySearch with array = [0, 1, 1, 2, 4, 5, 8, 13, 17], key = 5, low = 0, and high = 8. What is the index of the middle element?
4
3 multiple choice options
An call is made to RecursiveBinarySearch with array = [0, 1, 1, 2, 3, 5, 8, 13, 17], key = 5, low = 0, and high = 8. What are the low and high argument values for the next call to RecursiveBinarySearch()?
low =5, high= 4
3 multiple choice options
The Big O notation for an algorithm with exactly 50 constant time operations is _____.
O(1)
3 multiple choice options
The lower bound of an algorithm's runtime complexity is _____.
<= best case
3 multiple choice options
Which of the following is an example of constant time O(1)?
accessing an element of an array
A recursive function calls _____.
itself
3 multiple choice options
The Big O notation of the runtime 7+12N+3N2 is _____.
O(n^2)
3 multiple choice options
The worst-case runtime of an algorithm is _____ number of steps taken to execute a program.
the max
3 multiple choice options
In a recursive function, the base case _____ the function.
terminates
3 multiple choice options
Which of the following is a constant time operation?
finding the sum of two numbers input by the user
3 multiple choice options
Quicksort's partitioning algorithm uses a low index and a high index. Partitioning is complete when _____.
the low index is greater than or equal to the high index
What is the merge sort algorithm's runtime?
O(Nlogn)
3 multiple choice options
Which is the BEST case runtime for the quicksort algorithm?
O(Nlogn)
3 multiple choice options
Which is the WORST case runtime for the quicksort algorithm?
O(n^2)
Complete the following to declare a type parameter.
template
T SomeFunction(T arg) {
... .. ...
}
typename
3 multiple choice options
Which is the correct syntax for defining a class's function outside the class declaration?
returnType MyClass
3 multiple choice options
What property of a vector is changed when a vector's reserve function is called?
the capacity of the vector
3 multiple choice options
The vector class we defined had three member variables: elements, dataEnd, and memoryEnd. Which of the following statements can be used to return the capacity of the vector?
return memoryEnd - elements;
The vector class we defined had three member variables: elements, dataEnd, and memoryEnd. Which of the following statements should be used in the destructor?
delete[] elements;
3 multiple choice options
Suppose you have a program in which you use a vector to hold your data and you want to use a built-in function which takes an array parameter. Which of the following functions would be best to use in this situation to allow the built-in function to be called?
The vector's data function
What attribute of a vector is changed when a vector's resize function is called?
the size of vector
3 multiple choice options
Under what condition does calling a vector's push_back function cause additional memory to be reserved?
when the size equals the capacity
3 multiple choice options
The vector class we defined had three member variables: elements, dataEnd, and memoryEnd. Which of the following statements can be used to return the size of the vector?
return dataEnd - elements
3 multiple choice options
Which of the following correctly removes the first node from a singly-linked list that contains more than one node?
Node* temp = head;
head = head->next;
delete temp;
3 multiple choice options
What is the runtime complexity of the pop_back (remove from the end) operation in a singly-linked list?
O(n)
3 multiple choice options
The find function visits _____ when searching for 83 in the singly-linked list (80, 81, 82, 83).
all the nodes
3 multiple choice options
Which of the following pointers need to be updated to correctly insert a node at the end (push_back) of an empty singly-linked list?
the head pointer and tail pointer
3 multiple choice options
In a singly-linked list with 1 element, the tail pointer ____ and the next pointer of the head node ____.
points to the head node, is null
3 multiple choice options
Which of the following is an example of a linked list traversal operation?
printing the list
3 multiple choice options
Given the doubly-linked list animalList (Cat, Dog), which nodes will be the head and tail nodes after the following operations?
Insert node Bird after node Cat
Insert node Fish after node Dog
Remove node Cat from list
Remove node Fish from list
head = node Bird
Tail = node Dog
3 multiple choice options
The doubly-linked list append (push_back) operation changes the list's _____ if the list is empty and changes the list's _____ if the list is not empty.
head and tail, tail
3 multiple choice options
The doubly-linked list prepend (push_front) operation changes the list's _____ if the list is empty and changes the list's _____ if the list is not empty.
head and tail, head
3 multiple choice options
Given the doubly-linked list students (Tom, Sam), what will be the second node in the list after the following operations?
Node Hal is inserted after the tail
Node Pam is inserted after the head
Pam
3 multiple choice options
Which of the following pointers need to be updated to correctly insert a node at the end (push_back) of a non-empty doubly-linked list?
The next pointer of the tail nodeThe prev pointer of the node to insertThe tail pointer
3 multiple choice options
The find operation in a doubly-linked list has a worst case time complexity of _____.
O(N)
3 multiple choice options
Which function adds an element to the beginning of a std::list?
push_front()
3 multiple choice options
Which function adds an element to the back end of a std::list?
push_back()
3 multiple choice options
Which operation is valid for bidirectional iterators but not valid for forward iterators?
--
3 multiple choice options
Which of the following statement about the std::end function is true?
std::end returns an iterator to past-the-end element
3 multiple choice options
Which of the following containers can NOT be used in a call to the std::begin function?
stack
3 multiple choice options
Which of the following statements about using the operators ++, ==, and != with iterators and pointers is true?
Both pointers and iterators support all three operators (++, ==, and !=), with identical behavior across both types
3 multiple choice options
Which of the following iterator types satisfies the requirements of each other iterator type?
random-access
3 multiple choice options
Which of the following statements about using iterators to iterate over a std::list is true?
Bidirectional iterators can be used with std::list, allowing traversal both forward and backward
3 multiple choice options
Which of the following statements regarding the dereference operator (*) is true?
The dereference operator can be used with both pointers and iterators, allowing access to the value they point to or refer to
3 multiple choice options
Which of the following is an L-value?
an int variable named x
3 multiple choice options
Which of the following statements about input iterators and output iterators is true?
Input iterators are used for reading data from a container, while output iterators are used for writing data to a container
3 multiple choice options
Which of the following containers can be sorted by calling the std::sort function?
vector
Which stack functions can safely be called on an empty stack?
size, push
3 multiple choice options
What is the result of calling the pop method on a stack?
It removes the top element from the stack
3 multiple choice options
Which statement declares a C++ stack with integer items named numberStack?
stack
3 multiple choice options
Given the stack: Tom, Sam (top is Tom), what is the stack after the following four operations?
1) Push Hal
2) Push Raj
3) Pop
4) Pop
Tom, Sam (top is Tom)
3 multiple choice options
Which C++ function performs the peek operation on a stack?
top
3 multiple choice options
Which C++ function performs the peek operation on a queue?
front
3 multiple choice options
Given the queue myData 12, 24, 48 (front is 12), where will the new item 72 be enqueued?
after 48
3 multiple choice options
Which of the following structures use a std::deque as the default underlying container?
std::stack
std::queue
3 multiple choice options
Which of the following statements is NOT true about C++ std::queue?
the pop function can be called on a queue at any time
3 multiple choice options
Does an error exist in the code below?
queue
items.push("Hello");
cout << items.front() << endl;
No. The code outputs "Hello".
3 multiple choice options
In a queue, a dequeue operation always removes _____ element.
the front
3 multiple choice options
Which of the following operations are NOT efficient for a deque to perform?
insert/remove in middle
3 multiple choice options
Given the queue myData 12, 24, 36 (front is 12), what is the result of the following operations?
myData.pop();
myData.pop();
myData.pop();
cout << myData.size();
0
3 multiple choice options
Given the queue myData 12, 24, 48 (front is 12), what will be the queue contents after the following operations?
myData.push(72);
myData.pop();
24, 48, 72
3 multiple choice options
Which abstract data type best fits the following verse?
"So the last will be first, and the first last." Matthew 20:16
stack
3 multiple choice options
What is a leaf node?
a node with no children
3 multiple choice options
What is the minimum height of a binary tree containing n nodes?
O(log n)
3 multiple choice options
Which of the following best describes a max-heap?
A complete binary tree in which every node's key is greater than or equal to the node's children's keys
3 multiple choice options
What is the maximum height of a binary tree containing n nodes?
O(n)
3 multiple choice options
What happens when a leaf node is removed?
The parent's left or right child node becomes null
3 multiple choice options
When is a new node inserted as the left child?
When the new node's key is less than the current node and the current node's left child is null
3 multiple choice options
Which of the following rules does a valid BST follow?
Left subtree keys ≤ node's keys
3 multiple choice options
What is the height of a BST built by inserting nodes in the order 12, 24, 23, 48, 47?
3
3 multiple choice options
What is the height of a BST built by inserting nodes in the order 20, 10, 30?
1
3 multiple choice options
Which is the worst-case height of AVL?
Less than or equal to 1.5 times compared to minimum binary tree height
3 multiple choice options
What are the worst-case time complexities of the insert, remove, and search operations for BSTs?
insert: O(n)
remove: O(n)
search: O(n)
3 multiple choice options
Which of the following statements is true about a perfect BST?
A perfect BST is a valid AVL tree and also a valid Red Black tree (given all nodes are colored black)
3 multiple choice options
What are the worst-case time complexities of the insert, remove, and search operations for AVL and Red Black trees?
insert: O(log n)
remove: O(log n)
search: O(log n)
3 multiple choice options
Note 
Flashcards (63)