Алгоритмдер және деректер құрылымы»

«Алгоритмдер және деректер құрылымы»

пәні бойынша магистратураға түсуге арналған кешенді тестілеудің

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

(2020 дан бастап қолдану үшін бекітілген)

1. Құрудың мақсаты: Қазақстан Республикасы жоғары оқу орнынан кейінгі білім беру ұйымдарында оқуды жалғастыра алу қабілетін анықтау.

2. Міндеті:Келесі білім беру бағдарламалары тобы үшін түсушінің білім деңгейін анықтау:

М094 – Ақпараттық технологиялар

Шифр білім беру бағдармалар тобы

3. Тест мазмұны:

№	Тақырыптар мазмұны	Қиындық деңгейі	Тапсырмалар саны
	Негізгі процедуралық-бағытталған алгоритмдік тіл. Тілдің алфавиті. Тілдің негізгі объектілерін жазу ережелері. Мәліметтер типтері. Тұрақтылар. Айнымалылар. Тегтер. Өрнектер. Арифметикалық және логикалық өрнектер. Алгоритмдердің сызықты және тармақталушы құрылымдарының сипаттамасы. Циклдік құрылым алгоритмдерін ұйымдастыру. Кірістірілген циклдік құрылымдардың алгоритмдік сипаттамасы.	А В
	Алгоритмдік тіл операторлары. Бағдарлама құрылымы Алгоритмдік тіл операторларының жіктелуі. Тағайындау операторы. Басқару операторлары. Деректерді енгізу-шығаруды ұйымдастыру. Бағдарлама құрылымы. Алгоритм схемасынан программа схемасына көшу.	А В
	Алгоритмдердің әртүрлі құрылымдарын бағдарламалау Алгоритмдердің сызықтық құрылымын бағдарламалау. Тармақталған құрылымдар бағдарламалау. Алгоритмдердің циклдік құрылымын бағдарламалау (мысалы, сандық талдау, сандық массивтерді өңдеу, массив компоненттерін ретке келтіру мәселелері). Массивті енгізу / шығару. String деректер. Символдық деректер өңдеуді бағдарламалау.	А В
	Функциялар және рекурсивті функциялар. Функциялар пайдалану қажеттілігі. Функция декларациясының синтаксисі. Функциялармен жұмыс жасағанда void кілт сөзi. Функцияның дәлелдері. Массивті функцияға өткізу. Функцияның жүктелуі. Рекурсия.	А В
	Сұрыптау және іздеу алгоритмдері Сызықтық іздеу. Екілік іздеу Көпіршікті сұрыптау. Кірістіру бойынша сұрыптау. Таңдау бойынша сұрыптау. Есеп сұрыптау. Түбір сұрыптау. Біріктіру сұрыптау алгоритмі. Жылдам сұрыптау. Пирамидалық сұрыптау.	A В
	Алгоритмді бағалау Тұрақты күрделілік. Сызықтық күрделілік. Логарифмдік күрделілік. Сызықтық логарифмдік күрделілік. Квадраттық күрделілік. Текше күрделілігі. Экспоненциалды күрделілік. Факторлық күрделілігі	А В С
	Сызықтық мәліметтер құрылымы Массивтер, стектер, кезектер, тізімдер, байланысқан және қосарланған тізімдер	В C
	Хэш кестелері және хэш функциялары Хэш кестесінің өнімділігі. Хэш функцияларын жобалау. Соқтығуды шешудің схемалары: бір тізбекті, ашық адресация, сызықты зондтау, квадраттық зондтау, қос хэш	B С
	Ағаш және екілік үйінділер. Аңғал екілік ағаш. Теңдестірілген ағаштар. Өрнек ағашы. BST (екілік іздеу ағашы). AVL ағаштары. Қызыл-қара ағаш. Екілік үйінді.	B С
	Графтар және графтар алгоритмдер Графтар туралы түсінік. Графтармен жұмыс. Терең ізденіс (BFS). Кең ізденіс (DFS). Беллман-Форд алгоритмі. Дихстстраның алгоритмі. Флойдтың алгоритмі. Примнің алгоритмі. Крускал алгоритмі.	B С
Бір тест нұсқасы үшін тапсырмалардың саны

4. Жұмыс мазмұнын сипаттау:

«Алгоритмдер және деректер құрылымы» пәні бойынша емтиханға келесі тақырыптар бойынша 30 сұрақ кіреді:

Функциялар (C бағдарлама тiлi); Циклдар; С бағдарлама тiлi типтері; Рәсімдер; Деректер форматтары; Тіркеушілер; Операндалар; Бірыңғай операторлар; Екілік операторлар; Ауысым операторлары; Жадты басқару; Көрсеткіштер; С құрылымдары; Стек; Кезек; Басымдық кезегі; Байланыстырылған тізімдер; Қосарланған тізімдер; Тұрақты тіркестер; Токендер; Үлкен 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 стр.