ВУЗ:
Составители:
Рубрика:
сортировкой, когда вместо начального прохода распределения производится переключение то на распределе-
ние, то на слияние.
Рассмотрите практические аспекты слияния на лентах. Рассмотрите диски и барабаны как средства для
внешней сортировки.
Вопросы для самопроверки
1. Какой смысл вкладывается в понятие модели вычислений?
2. Почему анализ сложности алгоритмов чрезвычайно важен в программировании для ЭВМ и что в себя
включает?
3. Каким образом выполняется анализ времени выполнения алгоритма, и что является результатом такого
анализа?
4. Что понимается под сортировкой, и каковы ее наиболее важные применения?
5. Какой смысл вкладывается в понятия записи, файла, ключа и устойчивой сортировки?
6. Почему внутренняя сортировка так называется?
7. Какие главные стратегии сортировки Вы знаете?
8. В чем заключается главный смысл сортировки подсчетом?
9. Почему при сортировке подсчетом не происходит перемещение записей?
10. Чем отличается от сортировки подсчетом сортировка распределяющим подсчетом?
11. При каких условиях сортировка распределяющим подсчетом является весьма эффективной?
12. На чем основан метод сортировки, называемой сортировкой вставками?
13. Какова роль сортировки простыми вставками в сортировке бинарными вставками?
14. Какой механизм сортировки реализует метод Шелла с убывающим шагом?
15. Как отличается эффективность метода Шелла от сортировки простыми вставками в различных услови-
ях?
16. Какие пути усовершенствования простых вставок, основанные на тщательном анализе структур дан-
ных, Вам знакомы?
17. Какую структуру данных использует алгоритм L, реализующий вставки в список, и перемещает ли он
записи в памяти?
18. Что является основной идеей метода сортировки с вычислением адреса?
19. Удается ли достигнуть экономии времени от использования нескольких списков в методе сортировки с
вычислением адреса вместо одного?
20. Какая стратегия сортировки называется обменной сортировкой?
21. Какой метод является наиболее очевидным способом обменной сортировки?
22. Каково быстродействие "метода пузырька" по сравнению с простыми вставками?
23. В чем могут заключаться возможные усовершенствования "метода пузырька", и каковы его достоинст-
ва?
24. Какую идею реализует метод обменной сортировки со слиянием?
25. Почему метод Хоара "быстрой сортировки" называют обменной сортировки с разделением?
26. Какой из методов сортировки годится для параллельных вычислений, а какой – для вычислительных
машин, работающих последовательно?
27. Каким образом представляются ключи в методе обменной поразрядной сортировки?
28. Какова оценка быстродействия алгоритма R обменной поразрядной сортировки?
29. На чем основано семейство методов сортировки, называемое сортировкой посредством выбора?
30. Какие усовершенствования сортировки простым выбором Вам знакомы?
31. Какова главная идея, положенная в основу множества методов сортировки, называемой сортировкой
слиянием?
32. В чем заключается смысл сортировки двухпутевым слиянием?
33. Какая сортировка называется пирамидальной?
34. Какое отношение класс методов распределяющей сортировки имеет к сортировке слиянием?
35. Что Вы понимаете под внешней сортировкой, и чем она отличается от внутренней?
36. Какую роль внутренняя сортировка играет во внешней сортировке?
37. В чем заключаются методы двухпутевого и многопутевого слияния?
38. Почему одна из внешних сортировок называется осциллирующей сортировкой?
39. Какие практические аспекты слияния на лентах Вам знакомы?
40. Какую особенность имеют диски и барабаны как средства для внешней сортировки?
Литература: [1, с. 129–140], [3, с. 13–23, 93–450], [4, с. 12–52,
70–122, 322–351], [5, с. 110–131], [6, с. 246–254].
Т е м а 3. АЛГОРИТМЫ ПОИСКА
Программа
3.1. Последовательный поиск
Основные понятия. Алгоритмы исчерпывающего поиска.
Страницы
- « первая
- ‹ предыдущая
- …
- 7
- 8
- 9
- 10
- 11
- …
- следующая ›
- последняя »
