СПЕЦИФИКАЦИЯ ТЕСТА

по дисциплине «Алгоритмы и структуры данных»

комплексного тестирования в магистратуру
(вступает в силу с 2024 года)

1. Цель составления: Определение способности продолжать обучение в

организациях реализующих программы послевузовского образования
Республики Казахстан.
2. Задачи: Определение уровня знаний поступающего по следующим
группам образовательных программ:
М094 Информационные технологии
Шифр наименование группы образовательных программ
3. Содержание теста:
Содержание темы Уровень Количес
№ трудности тво
заданий
Базовый процедурно-ориентированный А 2
алгоритмический язык. В 1
Алфавит языка. Правила записи основных
объектов языка. Типы данных. Константы.
Переменные. Метки. Выражения.
1 Арифметические и логические выражения.
Описание линейных и разветвляющихся
структур алгоритмов. Организация
алгоритмов циклической структуры.
Алгоритмическое описание вложенных
циклических структур.
Операторы алгоритмического языка. А 2
Структура программы В 1
Классификация операторов алгоритмического
2 языка. Оператор присваивания. Операторы
управления. Организация ввода-вывода
данных. Структура программы. Переход от
схемы алгоритма к схеме программы.
3 Программирование различных структур А 2
алгоритмов В 1
Программирование линейных структур
алгоритмов. Программирование
разветвляющихся структур.
Программирование циклических структур
алгоритмов (на примерах задач численного
анализа, обработки числовых массивов, задач
упорядочения компонент массивов).
Программирование ввода-вывода массивов.
 Строковые данные. Программирование задач
обработки символьных данных.
Функции и рекурсивные функции А 1
Необходимость использования функций. В 2
Синтаксис объявления функции. Ключевое
4
слово void при работе с функциями.
Аргументы функции. Передача массива в
функцию. Перегрузка функций. Рекурсия.
Алгоритмы сортировки и поиска A 1
Линейный поиск. Двоичный поиск. В 2
Пузырьковая сортировка. Сортировка
5 вставкой. Сортировка выбором. Сортировка
подсчётом. Поразрядная сортировка.
Алгоритм сортировки слиянием. Быстрая
сортировка. Сортировка кучей.
Оценка сложности алгоритмов А 1
Константная сложность. Линейная сложность. В 1
Логарифмическая сложность. Линейно- С 1
6 логарифмическая сложность. Квадратичная
сложность. Кубическая сложность.
Экспоненциальная сложность. Факториальная
сложность
Линейные структуры данных В 1
7 Массивы, стеки, очереди, списки, связные и C 2
двусвязные списки
Хэш таблицы и Хэш функции B 1
Производительность хэш-таблицы. Дизайн С 2
хэш-функций. Схемы разрешения
8 столкновений: отдельная цепочка, открытая
адресация, линейное зондирование,
квадратичное зондирование, двойное
хеширование
Дерево и двоичная куча. B 1
Наивное бинарное дерево. Сбалансированные С 2
9 деревья. Дерево выражений. BST (Двоичное
дерево поиска). AVL деревья. Красно-чёрное
дерево. Двоичная куча.
Графы и графовые алгоритмы B 1
Понятие графов. Работа с графами. Поиск в С 2
глубину (BFS). Поиск в ширину (DFS).
10
Алгоритм Беллмана-Форда. Алгоритм
Дейкстра. Алгоритм Флойда. Алгоритм
Прима. Алгоритм Крускала.
Количество заданий одного варианта теста 30
4. Описание содержания заданий:
Тест включает 30 вопросов по Дисциплине «Алгоритмы и структуры
данных» на следующие темы:
Функции (библиотеки в C); Циклы; Типы в C; Процедуры; Форматы данных;
Регистры; Операнды; Унарные операторы; Бинарные операторы; Операторы
сдвига; Управление памятью; указатели; Структуры в С; стек; Очередь;
Приоритетная очередь; Связанные списки; Двойные связанные списки;
Regular Expressions; Лексемы; Обозначение Big O; Оценка сложности
алгоритма; Одномерные массивы; Многомерные массивы; Алгоритмы
сортировки: Блочная сортировка, Сортировка подсчётом, Поразрядная
сортировка, алгоритм сортировки слиянием; Двоичная куча; Сортировка
кучи; Хэш-таблицы; Хэш-функции; Производительность хеш-таблицы;
Дизайн хэш-функций; Схемы разрешения столкновений: отдельная цепочка,
открытая адресация, линейное зондирование, квадратичное зондирование,
двойное хеширование; Графовые алгоритмы; Поиск в глубину (BFS); Поиск в
ширину (DFS); Алгоритм Беллмана-Форда; Алгоритм Дейкстра; Алгоритм
Флойда; Алгоритм Прима; Алгоритм Крускала; Задача о ранце
(Динамическое программирование); Конечные автоматы; деревья; Наивное
бинарное дерево; Сбалансированные деревья; Дерево выражений; BST
(Двоичное дерево поиска); AVL деревья; Красно-чёрное дерево.
5.Среднее время выполнение задания:
Продолжительность выполнения одного задания - 2 минуты.
Общее время теста составляет 60 минут
6. Количество заданий в одной версии теста:
В одном варианте теста - 30 заданий.
Распределение тестовых заданий по уровню сложности:
- легкий (A) - 9 заданий (30%);
- средний (B) - 12 заданий (40%);
- сложный (C) - 9 заданий (30%).
7. Форма задания:
Тестовые задания представлены в закрытой форме, что требует выбора
одного правильного ответа из пяти предложенных.
8. Оценка выполнения задания:
При выборе правильного ответа претенденту присуждается 1 (один) балл, в
остальных случаях – 0 (ноль) баллов.
9. Список рекомендуемой литературы:
1. Дэйтл Х.М., Как программировать на C++, Prentice Hall, , 10 издание.
2017.-1568 стр.
2. Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск = The
Art of Computer Programming. Volume 3. Sorting and Searching / под ред.
В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва:
Вильямс, 2007. — Т. 3. — 832 с. — ISBN 5-8459-0082-1.
3. Брюс Эккель, Thinking in C++, Volume 1, 2nd Edition, 2015.- 840 p.
4. Пащенко Г.Н. Tutorial on course “Algorithms, data structures and
programming”, -Almaty, 2017.-202 p.
5. Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман, Структуры
данных и алгоритмы, Вильямс, 2016
6. Объектно-ориентированное программирование в С++, Лафоре Роберт –
Питер 2018. – 928 стр.
7. Структуры данных и алгоритмы в Java, Лафоре Роберт – Питер 2018, 704
стр.
8. Дональд Кнут: Искусство программирования. Том 2. Получисленные
алгоритмы / Переводчик: Красиков И. В., Тертышный В. Т., Козаченко Ю.
В. Издательство: Диалектика, 2020 г.
9. Альфред В. Ахо, Джон Э. Хопкрофт, Джеффи д. Ульман, Структуры
данных и алгоритмы, Вильяму, 2016
10. Хайнеман, Джордж, Пояяис, Гэри, Сеяков, Стэнли. Х15 Алгоритмы.
Справочник с примерами на С, С++, Java и Python, 2-е изд.: Пер, с англ. –
СпБ.: ООО «Альфа-книга», 2017. – 432 с.:ил.– Парал.тит.англ.ISBN 978-5-
9908910-7-7 (рус).
11. Фофанов О.Б. Алгоритмы и структуры данных: учебное пособие/
О.Б.Фофанов; Томский политехнический университет. Томск: Изд-во
Томского политехнического университета, 2014.-126с
12. Курносов М.Г. Введение в структуры и алгоритмы обработки данных. –
Новосибирск: Автограф, 2015.-179
13. Сейкетов А.Ж. Алгоритмдер және деректер құрылымдары: оқу құралы/
А.Ж. Сейкетов, Д.Р. Рахимова, Г.А. Мирзахмедова. – Алматы: Қазақ
университеті, 2017. –162 бет.
14. Мақашев Е.П. Алгоритмдер және программалау: оқу құралы. –
Алматы: Қазақ университеті, 2014 – 105бет.
15. Назаренко П.А. Алгоритмы и структуры данных: учебное пособие/
П.А.назаренко – Самара: ПГУТИ, 2015 – 196 стр.
16. Стивенс Род. Алгоритмы. Теория и практическое применение /Род
Стивенс. – Москва: Издательство «Э»,2016,-544с
17. Седживк Роберт Фундаментальные алгоритмы на С.Анализ/Структры
данных/Сортировка/Поиск/Алгоритмы на графах: Пер. с англ./Роберт
Седжвик.-СПб:ООО «ДиаСофтЮП»,2003.-1136с.
18. Керниган Б., Ритчи Д., Язык программирования, 3-е изд., испр. – СПб.:
«Невский Диалект», 2001. – 352с.
19. О.И.Ремизова, Алгоритмизация и программирования (С++) Москва
МИСиС, 2021, 76 с.
20. Y. Daniel Liang, Introduction to Programming with C++ (3rd Edition),
2015.
21. Francesco Zoffoli, C++ Fundamentals, 2019.
22. Josh Lospinoso, C++ Crash Course: A Fast-Paced Introduction, 2019.