Вопросы

Набор для практики

Краткие итоги

Ключевые термины

Бинарный (двоичный, дихотомический) поиск – это поиск заданного элемента на упорядоченном множестве, осуществляемый путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей.

Ключ поиска – это поле записи, по значению которого происходит поиск

Поиск – это процесс нахождения конкретной информации в ранее созданном множестве данных.

Поиск с барьером – это модификация алгоритма последовательного поиска, ускоряющая процесс путем определения граничного элемента.

Последовательный (линейный) поиск – это простейший вид поиска заданного элемента на некотором множестве, осуществляемый путем последовательного сравнения очередного рассматриваемого значения с искомым до тех пор, пока эти значения не совпадут.

1. Одним из важнейших действий со структурированной информацией является поиск.

2. Существует множество различных алгоритмов поиска, которые принципиально зависят от способа организации данных. У каждого алгоритма поиска есть свои преимущества и недостатки.

3. Последовательный (линейный) поиск является простейшим видом поиска заданного элемента на некотором множестве, осуществляемым путем последовательного сравнения очередного рассматриваемого значения с искомым до тех пор, пока эти значения не совпадут.

4. Существует модификация алгоритма последовательного поиска, которая ускоряет поиск путем установки в рассматриваемом множестве барьера.

5. Бинарный (двоичный, дихотомический) поиск является поиском заданного элемента на упорядоченном множестве, осуществляемым путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей. Бинарный поиск применяется к отсортированным множествам.

6. Преимуществом бинарного поиска является более низкая трудоемкость по сравнению с бинарным поиском. Недостаток бинарного поиска состоит в том, что он применим только на отсортированных множествах.

1. Чем можно объяснить многообразие алгоритмов поиска в линейных структурах?

2. В чем преимущества поиска с барьером по сравнению с последовательным поиском?

3. Нахождение какого по порядку элемента в линейном множестве (первого, последнего) гарантирует алгоритм прямого поиска? Как в этом случае должен быть выполнен просмотр?

4. Нахождение какого по порядку элемента в линейном множестве (первого, последнего) гарантирует алгоритм бинарного поиска? Ответ обоснуйте.

5. Как трудоемкость алгоритма бинарного поиска на дискретном множестве зависит от мощности множества?

6. Почему время выполнения алгоритма бинарного поиска на вещественном множестве не зависит от количества элементов?

Дата добавления: 2014-01-04