Операция проверки на пустоту, добавление объекта

Вопросы к экзамену

«Информатика»

Направление:

«Математическое обеспечение

И администрирование информационных систем»,

Курс, 2 семестр

Время выполнения программ. Проблема выбора алгоритма. Пример.

(Память или время) Типичным примером в данном случае служит алгоритм поиска кратчайшего пути.

Время выполнения программ. Асимптотические соотношения. Примеры.

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

Вычисление времени выполнения. Правило сумм. Пример.

Если же основная программа вызывает процедуры по очереди, то их сложности складываются: O(N^2 )+O(N^3 )=O(N^3).

Вычисление времени выполнения. Правило произведений. Пример.

Если во внутренних циклах процедуры Fast происходит вызов процедуры Slow, то сложности процедур перемножаются. В данном случае сложность алгоритма составляет O(N^2 )*O(N^3 )=O(N^5).

Некоторые правила анализа программ. Пример анализа нерекурсивной процедуры.
Сортировка, основные понятия. Обзор основных методов.

Все сортировки !!!!!!!!!!!!

Метод “пузырька”. Пример. Временная сложность n^2 и подсчет перестановок.(n^2 /4)
Сортировка вставками. Пример. Временная сложность и подсчет перестановок.

Сортировка посредством выбора. Пример. Временная сложность и подсчет перестановок.

Быстрая сортировка. Пример. .
Временная сложность быстрой сортировки.

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

Время выполнения быстрой сортировки в среднем.
Пирамидальная сортировка. Пример.

Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей»^[1]) — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов.^[2] Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).

Время выполнения пирамидальной сортировки. (n log n)
Время выполнения алгоритмов сортировок «сравнениями». Дерево решений. -
Сортировки за линейное время. Сортировка подсчетом.

Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза.

Сортировки за линейное время. Поразрядная сортировка.

Числа сортируются по разрядам. Существует два варианта least significant digit (LSD) и most significant digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие.

Понятие ООП. Инкапсуляция, наследование, полиморфизм.

Инкапсуляция (encapsulation) - это механизм, который объединяет данные и код, манипулирующий зтими данными, а также защищает и то, и другое от внешнего вмешательства или неправильного использования.

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

Наследование (inheritance) - это процесс, посредством которого один объект может приобретать свойства другого. Точнее, объект может наследовать основные свойства другого объекта и добавлять к ним черты, характерные только для него.

Понятие класса, объекта. Описание класcа, работа с классом. Примеры.

( )

Конструкторы. Примеры.

Это специальная член-функция которая выполняется каждый раз, когда создается новый объект класса.

Понятие линейного списка, операции с линейными списками. Виды списков. Примеры.

Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на следующий элемент.

Операция проверки на пустоту, добавление объекта

Стек. Представление стека с помощью указателей. Операции со стеком.

Стек-частный случай списка все опирации с которыми (добавление просмотр и выборка) выполняются с 1 конца.

Очередь. Представление очереди с помощью указателей. Операции с очередью.

Очередь-частичный случай списка, добавление элементов происходит с одного конца, а выборка и просмотр с другого.

Односвязный список общего вида, основные операции. Примеры. .(как вставить или убрать элемент)(инцилизация списка,добавлен и удаление элементов из произв места, поиск в списке по ключу, просмотр элементов без извлечения)

Двусвязный список общего вида, основные операции. Примеры.(как вставить или убрать элемент)

Дата добавления: 2020-04-25; просмотров: 153; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!