Общие сведения. Часть 3. Типовые структуры данных

Часть 3. Типовые структуры данных

Контрольные вопросы

1. К какой группе методов проектирования относится классическая (водопадная) модель разработки приложений?

2. Что определяет цели в водопадной модели разработки программного средства?

3. Что такое внешний проект?

4. За счет чего достигается концептуальная целостность внешних спецификаций?

5. Какую задачу решает инкрементная модель разработки приложений?

6. Какие этапы включает спиральная модель разработки приложений?

7. Что является характеристиками модуля?

8. Что такое сцепление модулей?

9. Что такое экстремальное программирование (XP)?

10. Что показывает сравнение эволюционной и инкрементной стратегий?

11. Что известно при тестировании по методу белого ящика?

12. Что исследуется при тестировании по методу белого ящика?

13. Что гарантирует в идеале тестирование по методу базового пути?

14. Чему соответствуют узлы (вершины) графа в потоковом графе?

15. Что определяет цикломатическая сложность?

16. Что исследуется при тестировании по методу черного ящика?

17. Как выбираются классы при тестировании способом разбиения по эквивалентности?

18. Как необходимо разрабатывать тесты при тестировании методом анализа граничных значений?

19. За счет чего обеспечивается высокая скорость разработки по RAD- технологии?

Особый интерес среди структур данных представляют циклические структуры. Под циклической структурой данных понимается набор однотипных элементов. Есть три типа циклических структур.

1. Множества — важен только факт вхождения элемента в структуру; примеры: математические множества, таблицы реляционных баз данных.

2. Массивы — важно местоположение (номер) элемента; пример: массивы различной размерности.

3. Графы — важны связи между элементами; пример: деревья, сети, графы.

Одним из показателей качества алгоритма обработки циклической структуры данных является его вычислительная сложность. Вычислительная сложность представляется в виде функции зависимости времени, затрачиваемого на выполнение алгоритма, от количества элементов структуры. Так как точное время выполнения зависит от аппаратных средств и других факторов, то на практике вычисляют асимптотическую сложность, то есть учитывают время выполнения с точностью до некоторого постоянного сомножителя. Наиболее часто используют асимптотическое ограничение сверху, обозначаемое как o(g(n)). Такая запись обозначает, что существует такое положительное C, для которого время выполнения алгоритма не превысит С∙g(n), где n – количество элементов структуры.