Podcast
Questions and Answers
The advantage of a linear search is that
The advantage of a linear search is that
A(n) ______ search is more efficient than a(n) ______ search.
A(n) ______ search is more efficient than a(n) ______ search.
The linear search is adequate for searching through ______ arrays, but not through ______ ones.
The linear search is adequate for searching through ______ arrays, but not through ______ ones.
Using a linear search, you are more likely to find an item than if you use a binary search.
Using a linear search, you are more likely to find an item than if you use a binary search.
Signup and view all the answers
A binary search begins by examining the ______ element of an array.
A binary search begins by examining the ______ element of an array.
Signup and view all the answers
If the item being searched for is not in the array, binary search stops looking for it and reports that it is not there when
If the item being searched for is not in the array, binary search stops looking for it and reports that it is not there when
Signup and view all the answers
When searching for an item in an unordered set of data, binary search can find the item more quickly than linear search.
When searching for an item in an unordered set of data, binary search can find the item more quickly than linear search.
Signup and view all the answers
A search can be performed on an array of
A search can be performed on an array of
Signup and view all the answers
A sorting algorithm can be used to arrange a set of ______ in ______ order.
A sorting algorithm can be used to arrange a set of ______ in ______ order.
Signup and view all the answers
The ______ sort usually performs fewer exchanges than the ______ sort.
The ______ sort usually performs fewer exchanges than the ______ sort.
Signup and view all the answers
To find a value that is in an unordered array of 100 items, how many values must linear search examine on average?
To find a value that is in an unordered array of 100 items, how many values must linear search examine on average?
Signup and view all the answers
To determine that an item is not in an unordered array of 100 items, how many values must linear search examine on average?
To determine that an item is not in an unordered array of 100 items, how many values must linear search examine on average?
Signup and view all the answers
To find a value in an ordered array of 100 items, how many values must binary search examine at most?
To find a value in an ordered array of 100 items, how many values must binary search examine at most?
Signup and view all the answers
If a bubble sort is used to arrange the numbers 7 5 3 9 2 6 in ascending order, what order will the data be in after the first pass?
If a bubble sort is used to arrange the numbers 7 5 3 9 2 6 in ascending order, what order will the data be in after the first pass?
Signup and view all the answers
If a selection sort is used to arrange the numbers 7 5 3 9 2 6 in ascending order, what order will the data be in after the first pass?
If a selection sort is used to arrange the numbers 7 5 3 9 2 6 in ascending order, what order will the data be in after the first pass?
Signup and view all the answers
When sorting an array of objects, if the values in the data member being sorted on are out of order for two objects, those two data values should be swapped.
When sorting an array of objects, if the values in the data member being sorted on are out of order for two objects, those two data values should be swapped.
Signup and view all the answers
Any sorting algorithm, such as bubble sort or selection sort, that can be used on data stored in an array can also be used on data stored in a vector.
Any sorting algorithm, such as bubble sort or selection sort, that can be used on data stored in an array can also be used on data stored in a vector.
Signup and view all the answers
If algorithm A requires 2n + 1 basic operations to process an input of size n, and Algorithm B requires 3n + 2 basic operations to process the same input, algorithms A and B are considered to be equally efficient.
If algorithm A requires 2n + 1 basic operations to process an input of size n, and Algorithm B requires 3n + 2 basic operations to process the same input, algorithms A and B are considered to be equally efficient.
Signup and view all the answers
A ______ search uses a loop to sequentially step through an array.
A ______ search uses a loop to sequentially step through an array.
Signup and view all the answers
A binary search requires that the elements be in order.
A binary search requires that the elements be in order.
Signup and view all the answers
The ______ search is adequate for searching through small arrays, but not through large ones.
The ______ search is adequate for searching through small arrays, but not through large ones.
Signup and view all the answers
Using a binary search, you are more likely to find an item than if you use a linear search.
Using a binary search, you are more likely to find an item than if you use a linear search.
Signup and view all the answers
If a binary search is used to search for the number 4 in the 11-element array shown here
int A[] = {1, 2, 3, 4, 6, 7, 8, 9, 10, 12, 17};
which value will the 4 be compared to first?
If a binary search is used to search for the number 4 in the 11-element array shown here int A[] = {1, 2, 3, 4, 6, 7, 8, 9, 10, 12, 17}; which value will the 4 be compared to first?
Signup and view all the answers
To determine that a value is not present in an unordered array of 50 items, how many values must linear search examine on average?
To determine that a value is not present in an unordered array of 50 items, how many values must linear search examine on average?
Signup and view all the answers
To find a value that is in an unordered array of 50 items, how many values must linear search examine on average?
To find a value that is in an unordered array of 50 items, how many values must linear search examine on average?
Signup and view all the answers
To find a value in an ordered array of 50 items, how many values must binary search examine at most?
To find a value in an ordered array of 50 items, how many values must binary search examine at most?
Signup and view all the answers
When searching for a particular object in an array of objects, it is necessary to compare the search key to the value in each examined object's key field.
When searching for a particular object in an array of objects, it is necessary to compare the search key to the value in each examined object's key field.
Signup and view all the answers
A(n) ______ algorithm arranges data into some order.
A(n) ______ algorithm arranges data into some order.
Signup and view all the answers
Sorted data can be ordered
Sorted data can be ordered
Signup and view all the answers
When an array is sorted from highest to lowest, it is said to be in ascending order.
When an array is sorted from highest to lowest, it is said to be in ascending order.
Signup and view all the answers
If a bubble sort is used to arrange the numbers 8 6 4 9 3 7 in ascending order, what order will the data be in after the first pass of the sort is completed?
If a bubble sort is used to arrange the numbers 8 6 4 9 3 7 in ascending order, what order will the data be in after the first pass of the sort is completed?
Signup and view all the answers
If a selection sort is used to arrange the numbers 8 6 4 9 3 7 in ascending order, what order will the data be in after the first pass of the sort is completed?
If a selection sort is used to arrange the numbers 8 6 4 9 3 7 in ascending order, what order will the data be in after the first pass of the sort is completed?
Signup and view all the answers
The ______ sort usually performs more exchanges than the ______ sort.
The ______ sort usually performs more exchanges than the ______ sort.
Signup and view all the answers
Selection sort requires _____ passes to put n data items in order.
Selection sort requires _____ passes to put n data items in order.
Signup and view all the answers
When sorting an array of objects, if the values in the data member being sorted on are out of order for two objects, those two data values should be swapped.
When sorting an array of objects, if the values in the data member being sorted on are out of order for two objects, those two data values should be swapped.
Signup and view all the answers
Any sorting algorithm, such as bubble sort or selection sort, that can be used on data stored in an array can also be used on data stored in a vector.
Any sorting algorithm, such as bubble sort or selection sort, that can be used on data stored in an array can also be used on data stored in a vector.
Signup and view all the answers
We can estimate the ______ of an algorithm by counting the number of basic steps it requires to solve a problem.
We can estimate the ______ of an algorithm by counting the number of basic steps it requires to solve a problem.
Signup and view all the answers
If algorithm A requires 2n + 1 basic operations to process an input of size n, and Algorithm B requires 3n + 2 basic operations to process the same input, algorithms A and B are considered to be equally efficient.
If algorithm A requires 2n + 1 basic operations to process an input of size n, and Algorithm B requires 3n + 2 basic operations to process the same input, algorithms A and B are considered to be equally efficient.
Signup and view all the answers
Study Notes
Chapter 9 Test 1 and 2
- Linear Search Advantage: Simple, usable on unordered data.
- Binary Search Advantage: More efficient than linear search for ordered data.
- Linear Search Use Cases: Arrays of ints, doubles, chars and strings. Not ideal for large ordered arrays.
- Linear Search Limitations: Not efficient on large or ordered data.
- Binary Search Use Cases: Ordered arrays to find a specific item quickly.
- Binary Search for Missing Item: Array index first is greater than array last, or boolean variable found equals false.
- Binary Search Starting Point: Examines the middle element of the array.
- Binary Search Efficiency: More efficient for searching ordered data.
- Sorting Algorithm Use Cases: Arranging data (numbers, strings, etc.) in ascending or descending order.
- Bubble Sort: A sorting algorithm that progressively moves values to their correct positions.
- Bubble Sort Pass Order: Values are swapped on each pass to move larger values towards the end
- Selection Sort Pass Order: Finds the smallest element in each pass and places it in the beginning.
- Sorting Algorithms and STL Vectors: Possible to use bubble and selection sort with STL vectors.
- Algorithm Complexity: Measured by the number of basic steps for a given input size.
- Object Comparison in Arrays of Objects: Compare search key with a certain field in each object.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
This quiz covers key concepts from Chapter 9 related to linear and binary search algorithms, including their advantages, use cases, and limitations. Additionally, it discusses sorting algorithms, focusing on bubble sort and its operational mechanics. Test your understanding of these fundamental data structures and algorithms.
