close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
ЛКШ-2006
Список вопросов к теоретическому зачёту группы С2
Структуры данных, сортировка и поиск
Указатели. Работа с указателями.
Стек, очередь, дек. Реализация стека, дека, очереди при помощи массивов и списков.
Списки. Ссылочная реализация списков.
Поиск данных. Линейный поиск. Двоичный (бинарный) поиск.
Пирамида (куча, heap). Реализация пирамиды. Процедуры добавления и удаления
элементов.
6. Пирамидальная сортировка (heapsort).
7. Быстрая сортировка Хоара (qsort).
8. k-ая порядковая статистика за время O(n).
1.
2.
3.
4.
5.
Графы, поиск в глубину и ширину
9. Графы. Представление графов в памяти компьютера. Матрица смежности. Списки
смежности.
10. Поиск в ширину.
11. Поиск в глубину. Рекурсивная и нерекурсивная реализация.
12. Проверка графа на наличие циклов.
13. Топологическая сортировка.
Нахождение наименьшего каркаса в графе
14. Теорема о разрезе.
15. Алгоритм Краскала.
16. Алгоритм Прима.
Нахождение кратчайших путей в взвешенном графе
17. Алгоритм Дейкстры.
18. Алгоритм Флойда. Нахождение цикла отрицательного веса при помощи алгоритма
Флойда.
19. Алгоритм Форда-Беллмана. Нахождение цикла отрицательного веса при помощи
алгоритма Форда-Беллмана.
Эйлеров и гамильтонов цикл
20. Эйлеров цикл.
21. Гамильтонов цикл. Задача коммивояжера.
Комбинаторика
22. Перестановки. Рекурсивный и нерекурсивный алгоритм генерации перестановок в
лексикографическом порядке.
23. Перестановки. Определение перестановки по номеру и номера по перестановке.
24. Генерация всех слов заданной длины в конечном алфавите. Рекурсивная и
нерекурсивная реализации.
25. Генерация всех подмножеств мощности k в множестве из n элементов. Рекурсивная и
нерекурсивная реализации.
Геометрия
26. Векторы и координаты. Сложение векторов, умножение вектора на число,
нормирование вектора, коллинеарные векторы. Построение ортогональных векторов.
27. Скалярное произведение векторов. Свойства скалярного произведения. Векторное
произведение векторов. Ориентированная площадь треугольника. Свойства
векторного произведения.
28. Принадлежность точки прямой, лучу, отрезку.
29. Расстояние от точки до прямой, луча, отрезка.
30. Определение взаимного расположения двух отрезков. Нахождение точки пересечения
двух прямых.
31. Уравнение прямой, проходящей через две различные точки, заданные своими
координатами. Связь координат точек с коэффициентами A, B и C. Нормаль к прямой.
32. Уравнение прямой, заданной одной из ее точек и вектором нормали к ней. Уравнение
прямой, перпендикулярной данной и проходящей через заданную точку.
33. Уравнение биссектрисы угла. Уравнение прямой, параллельной данной и
находящейся на заданном расстоянии от нее.
34. Уравнение окружности. Алгоритм построения касательной к окружности
(нахождение точек касания).
35. Нахождение точек пересечения окружности и прямой.
36. Вычисление площади простого многоугольника.
37. Проверка принадлежности точки внутренней области простого многоугольника.
38. Проверка выпуклости многоугольника.
39. Выпуклая оболочка. Алгоритм Джарвиса.
40. Выпуклая оболочка. Алгоритм Грэхема.
41. Формула Пика.
Арифметика
42. Длинная арифметика. Представление длинных чисел. Процедуры ввода и вывода
длинных чисел.
43. Длинная арифметика. Сравнение, сложение, вычитание, умножение длинных целых
чисел. Деление длинного числа на короткое.
44. Бинарный алгоритм Евклида.
45. Алгоритм возведения в степень за время O(log n).
Динамическое программирование
46. Разные методы вычисления биномиальных коэффициентов и их сравнение.
47. Понятие о динамическом программировании. Сравнение динамического
программирования с рекурсией.
48. Правильные скобочные последовательности. Числа Каталана.
49. Построение наибольшей возрастающей подпоследовательности за время O(n2).
50. Задача о рюкзаке.
1/--страниц
Пожаловаться на содержимое документа