Спецификация ТЕСТА
По дисциплине «Алгоритмы и структуры данных»
Комплексного тестирования в магистратуру
(вступает в силу с 2020 года)
1. Цель составления: Определение способности продолжать обучение в организациях реализующих программы послевузовского образования Республики Казахстан.
2. Задачи: Определение уровня знаний поступающего по следующим группам образовательных программ:
М094 Информационные технологии
Шифр наименование группы образовательных программ
3. Содержание теста:
| № | Содержание темы | Уровень трудности | Количество заданий |
| Базовый процедурно-ориентированный алгоритмический язык. Алфавит языка. Правила записи основных объектов языка. Типы данных. Константы. Переменные. Метки. Выражения. Арифметические и логические выражения. Описание линейных и разветвляющихся структур алгоритмов. Организация алгоритмов циклической структуры. Алгоритмическое описание вложенных циклических структур. | А В | ||
| Операторы алгоритмического языка. Структура программы Классификация операторов алгоритмического языка. Оператор присваивания. Операторы управления. Организация ввода-вывода данных. Структура программы. Переход от схемы алгоритма к схеме программы. | А В | ||
| Программирование различных структур алгоритмов Программирование линейных структур алгоритмов. Программирование разветвляющихся структур. Программирование циклических структур алгоритмов (на примерах задач численного анализа, обработки числовых массивов, задач упорядочения компонент массивов). Программирование ввода-вывода массивов. Строковые данные. Программирование задач обработки символьных данных. | А В | ||
| Функции и рекурсивные функции Необходимость использования функций. Синтаксис объявления функции. Ключевое слово void при работе с функциями. Аргументы функции. Передача массива в функцию. Перегрузка функций. Рекурсия. | А В | ||
| Алгоритмы сортировки и поиска Линейный поиск. Двоичный поиск. Пузырьковая сортировка. Сортировка вставкой. Сортировка выбором. Сортировка подсчётом. Поразрядная сортировка. Алгоритм сортировки слиянием. Быстрая сортировка. Сортировка кучей. | A В | ||
| Оценка сложности алгоритмов Константная сложность. Линейная сложность. Логарифмическая сложность. Линейно-логарифмическая сложность. Квадратичная сложность. Кубическая сложность. Экспоненциальная сложность. Факториальная сложность | А В С | ||
| Линейные структуры данных Массивы, стеки, очереди, списки, связные и двусвязные списки | В C | ||
| Хеш таблицы и Хеш функции Производительность хеш-таблицы. Дизайн хеш-функций. Схемы разрешения столкновений: отдельная цепочка, открытая адресация, линейное зондирование, квадратичное зондирование, двойное хеширование | B С | ||
| Дерево и двоичная куча. Наивное бинарное дерево. Сбалансированные деревья. Дерево выражений. BST (Двоичное дерево поиска). AVL деревья. Красно-чёрное дерево. Двоичная куча. | B С | ||
| Графы и графовые алгоритмы Понятие графов. Работа с графами. Поиск в глубину (BFS). Поиск в ширину (DFS). Алгоритм Беллмана-Форда. Алгоритм Дейкстра. Алгоритм Флойда. Алгоритм Прима. Алгоритм Крускала. | B С | ||
| Количество заданий одного варианта теста |
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. Кнут Д. Э. Искусство программирования. Том 1. Основные алгоритмы = The Art of Computer Programming. Volume 1. Fundamental Algorithms / под ред. С. Г. Тригуб (гл. 1), Ю. Г. Гордиенко (гл. 2) и И. В. Красикова (разд. 2.5 и 2.6). — 3. — Москва: Вильямс, 2002. — Т. 1. — 720 с. — ISBN 5-8459-0080-8.
3. Кнут Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы = The Art of Computer Programming. Volume 2. Seminumerical Algorithms / под ред. Л. Ф. Козаченко (гл. 3, разд. 4.6.4 и 4.7), В. Т. Тертышного (гл. 4) и И. В. Красикова (разд. 4.6). — 3. — Москва: Вильямс, 2001. — Т. 2. — 832 с. — ISBN 5-8459-0081-6.
4. Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с. — ISBN 5-8459-0082-1.
5. Брюс Эккель, Thinking in C++, Volume 1, 2nd Edition, 2015.- 840 p.
6. Пащенко Г.Н. Tutorial on course “Algorithms, data structures and programming”, -Almaty, 2017.-202 p.
7. Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман, Структуры данных и алгоритмы, Вильямс, 2016
8. Объектно-ориентированное программирование в С++, Лафоре Роберт – Питер 2018. – 928 стр.
9. Структуры данных и алгоритмы в Java, Лафоре Роберт – Питер 2018, 704 стр.