prosdo.ru 1

Вопросы к экзамену по САОД


Билет на экзамен состоит из 8-ми вопросов:


  • Теоретический вопрос с примером.

  • 7 практических заданий.


Список теоретических вопросов:

  1. Сортировка посредством выбора. Пояснить алгоритм сортировки, привести пример сортировки массива.

  2. Сортировка обменом. Пояснить алгоритм сортировки, привести пример сортировки массива.

  3. Сортировка вставками. Пояснить алгоритм сортировки, привести пример сортировки массива.

  4. Сортировка с разделением (быстрая). Пояснить алгоритм сортировки, привести пример сортировки массива.

  5. Внешний поиск. Пояснить алгоритм внешнего поиска на примере.

  6. Сортировка прямым слиянием. Пояснить алгоритм сортировки на примере.

  7. Использование стека для разработки «Электронных калькуляторов». Пояснить алгоритм «Электронного калькулятора» на примере.

  8. Алгоритм поразрядной сортировки. Привести пример сортировки массива методом поразрядной сортировки.

  9. Идеально сбалансированные деревья. Пояснить на примере алгоритм построения идеально сбалансированного дерева.

  10. Деревья двоичного поиска. Пояснить на примере алгоритм построения дерева двоичного поиска.

  11. Алгоритмы обхода двоичного дерева: инфиксный, префиксный, постфиксный. Привести примеры, иллюстрирующие рассматриваемые алгоритмы обхода дерева.

  12. Алгоритм поперечного прохождения дерева. Привести пример.

  13. Турнирная сортировка. Пояснить алгоритм сортировки на примере.

  14. Пирамиды. Алгоритм преобразования массива в пирамиду, привести пример.

  15. Пирамиды. Алгоритмы включения и удаления элементов из пирамиды, привести пример.

  16. Пирамидальная сортировка. Пояснить алгоритм сортировки на примере.
  17. Нахождение центра ориентированного графа. Пояснить алгоритм на примере.


  18. Остовные деревья минимальной стоимости (ОДМС). Алгоритм Прима, привести пример построения ОДМС на основе алгоритма Прима.

  19. Остовные деревья минимальной стоимости (ОДМС). Алгоритм Крускала, привести пример построения ОДМС на основе алгоритма Крускала.

  20. Эйлеровы пути и циклы. Алгоритм нахождения Эйлерова пути. Привести пример нахождения Эйлерова пути в связном графе.


Перечень заданий, входящих в практическую часть:

  1. Сложность алгоритмов.

  2. Принцип работы стека.

  3. Принцип работы очереди.

  4. Работа с динамическими списками.

  5. Построение дерева двоичного поиска.

  6. Обходы дерева двоичного поиска.

  7. Добавление и удаление элемента в дерево двоичного поиска.

  8. Двоичные деревья, представленные в виде массива.

  9. Пирамиды.

  10. Пирамидальная сортировка.

  11. Способы представления графов.

  12. Матрица достижимости.

  13. Обходы графов.

  14. ОДМС.

  15. Центр ориентированного графа.

  16. Эйлеровы пути и циклы.

  17. Гамильтонов путь.

  18. Паросочетания.


Пример билета на экзамен:


  1. Остовные деревья минимальной стоимости (ОДМС). Алгоритм Крускала, привести пример построения ОДМС на основе алгоритма Крускала.

  2. Цикл является главным компонентом для алгоритма. Определить порядок сложности алгоритма.
    for (i=0;i

  3. Дан пустой стек и функции работы со стеком: push - функция включения элемента в стек и pop - функция исключения элемента из стека. Опишите содержимое стека после выполнения каждой из операций:
    push(1);
    push(2);
    x=pop();
    push(9);
    x=pop();
    push(-x);
    y=pop();
  4. Имеется двусвязный список DNODE и указатели. Нарисуйте, как изменится список после выполнения команд.

    p1=h;
    while (p1!=p3)
    { p1->dann=h->dann-3; p1=p1->prev;}


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

  6. Нарисуйте бинарное дерево поиска для приведенной числовой последовательности и осуществите его прохождение обратным методом: 68, 25, 70, 99, 15, 3, 110, 33, 38, 59, 62, 34

  7. Перечислить вершины графа, полученные при обходе его методом поиска в ширину (начальная вершина С):


  8. Для заданного графа найдите его центр, для каждой вершины определите эксцентриситет.