Структури і алгоритми обробки даних
МОДУЛЬ 1. ТИПИ І СТРУКТУРИ ДАНИХ
З чого складається перераховується тип даних?
з кінцевого числа впорядкованих іменованих значень
Який цикл використовується в разі, якщо заздалегідь не відомо, скільки разів знадобитися виконати цикл?
while
Під ніж розуміється можливість дисциплінованого створення нових типів на основі вже певних?
під спадкуванням типів
Як називаються беззнакові типи даних в лінії мов Паскаль?
CARDINAL
Для чого використовується процедура new (var) в мовах лінії Паскаль?
для запиту динамічних змінних
Що з перерахованого не відноситься до типів циклів в С ++?
begin
Які логічні значення виробляють операції порівняння?
TRUE, FALSE, UNKNOWN
Що з перерахованого не відноситься до типів колекцій?
типи предиката
Як називається частина коду, яка періодично виповнюється в циклі?
тіло циклу
Як називається іменоване безліч значень деякого вбудованого типу, обмежене умовою?
домен
Що називається блоком?
тіло циклу, укладену в фігурні дужки
Який з операторів є найбільш простим з операторів розгалуження?
if
Чим може бути будь-який вбудований або певний тип?
базовим типом
Що існує для будь-якого значення будь-якого вбудованого типу?
зовнішнє литеральное уявлення
Який цикл організовує виконання фрагмента програми фіксоване число раз?
for
Як виглядає визначення типу масиву в мові Паскаль?
type T = array [I] of T0
У яких мовах підтримуються типи множин?
в розвинених сильно типізованих мовах
Яка операція, за допомогою якої можна звертатися до значення типу даних, відноситься до неявній?
операція перетворення значення цілого типу до значення плаваючого
Яке з перерахованих виразів називають инкрементируются?
j ++
Які типи даних називаються типами даних символьних рядків?
CHARACTER
Яка конструкція використовується, щоб оголосити змінну var в Сі?
Т0 * var
Які підходи при програмуванні з використанням абстрактних типів даних (АТД)?
перед початком написання основної програми повністю визначити всі необхідні типи даних, визначити тільки ті характеристики АТД, які потрібні для написання програми і перевірки її синтаксичної коректності, скористатися готовими бібліотечними визначеннями
Який оператор розгалуження в С ++ є найбільш важливим?
if ... else
Який алгоритм знаходить перше входження в першу послідовність другий послідовності і повертає ітератор на останній збігається елемент?
find_end
Яка функція алгоритму find_if?
виконує пошук значення, відповідного заданому предикату
Що відбувається в двійковому пошуку, якщо деякий елемент дорівнює х?
пошук закінчується
На чому грунтується БМ-пошук?
на порівнянні символів, яке починається з кінця способу
Яка функція алгоритмів сімейства find?
здійснюють пошук в послідовності
Який алгоритм виконує знаходження пари сусідніх значень?
adjacent_find
Яке умова порівняння рядків в пошуку в таблиці?
WHILE (x [i] = y [i]) (X [i] <> 0C) DO i: = i + 1
Як називають пошук в масиві?
пошук в таблиці
Який алгоритм знаходить перше входження в першу послідовність елемента з другої послідовності?
find_first_of
Який алгоритм знаходить в послідовності підпослідовність, що складається з принаймні n значень value?
search_n
Який алгоритм знаходить перше входження в першу послідовність другий послідовності і повертає ітератор на перший співпадає елемент?
search
Яке максимальне число порівнянь символів в КМП-пошуку?
М + N
Який розмір рядків?
змінний
Які умови закінчення лінійного пошуку?
елемент знайдений
Який алгоритм виконує підрахунок кількості входжень значення в послідовність?
count
Куди повертають алгоритми сімейства find итератор в разі успішного пошуку?
на найлівіше знайдене значення
Яка форма алгоритму adjacent_find знаходить в послідовному контейнері пару сусідніх однакових значень і повертає ітератор на перше з них або кінець послідовності?
перша
Який алгоритм виконує попарне порівняння елементів двох послідовностей?
equal
Який алгоритм шукає першу пару незбіжних елементів двох послідовностей і повертає ітератори на цю пару?
mismatch
Який алгоритм викликає для кожного елемента послідовності задану функцію?
for_each
Яке максимальне число порівнянь в довічним пошуку?
LOG2 (N)
Для чого використовують немодіфіцірующіе операції з послідовностями?
для отримання інформації про послідовність або для визначення положення елемента
Для якого пошуку задано два масиви s і p?
для пошуку рядка
Що задається за допомогою ітераторів?
кордону послідовності
В якому році був винайдений алгоритм Кнута, Моріса і Пратта?
в 1970 р
МОДУЛЬ 3. СОРТИРОВКИ
Яка загальна формула для обчислення максимального числа порівняння ключів в прямому виборі?
(N2-n) / 2
Яке призначення алгоритму partition?
розміщує елементи, що задовольняють заданій умові, перед іншими елементами
Яке призначення алгоритму equal_range?
виконує знаходження меж послідовності елементів
Яке призначення алгоритму binary_search?
виконує пошук заданого значення
Як називається сортування включеннями з зменшуваним відстанню?
сортування методом Шелла
Яке призначення алгоритму inplace_merge?
виконує злиття двох відсортованих частин однієї послідовності
У чому ідея сортування за допомогою піраміди?
замість повного дерева порівняння вихідний масив перетворюється в піраміду, що володіє тим властивістю, що для кожного а [i] виконуються умови і
Яке мінімальне число пересилань для методу простої обмінного сортування?
0
Яка загальна формула для обчислення мінімального числа порівняння ключів в прямому обміні?
М = 0
Яка загальна формула для обчислення мінімального числа порівняння ключів в прямому включенні?
C = n-1
Як називається метод сортування, якщо при його застосуванні не змінюється відносне положення записів з рівними значеннями ключа?
стійким
Що з перерахованого не відноситься до основних методів внутрішнього сортування?
сортування за допомогою рівності
Який алгоритм виконує часткову сортування масиву?
nth_element
Яке призначення алгоритму lexicographical_compare?
виконує поелементне порівняння двох послідовностей
Яка особливість сортування за допомогою дерева?
чим більше n, тим краще працює сортування
Яке необхідне число порівнянь для методу сортування простим вибором?
n (n-1) / 2
Який алгоритм виробляє чергову перестановку в лексикографічному порядку?
next_permutation
Який алгоритм знаходить итератор на перший з елементів відсортованої послідовності?
lower_bound
Яка формулювання теореми, справедливою для сортування Шелла?
якщо k-відсортовану послідовність i-відсортувати, то вона залишається k-відсортованої
Яким алгоритмом потрібні ітератори довільного доступу?
sort
Ким був запропонований метод сортування поділом?
Хоаром
Як називається сортування масивів записів, цілком розташованих в основній пам'яті?
внутрішня сортування
Який порядок виконання процедури сортування за допомогою піраміди?
n * log
Який алгоритм повертає ітератор на найбільше значення в послідовності?
max_element
МОДУЛЬ 4. СОРТИРОВКИ ПОСЛІДОВНОСТЕЙ
Яка функція алгоритму generate?
виконує заміну всіх елементів результатом операції
Яка функція алгоритму random_shuffle?
виконує переміщення елементів відповідно до випадковим рівномірним розподілом
Коли завершується процес сортування в природному злитті?
коли в файлі А залишається тільки одна серія записів
Яку операцію виконує друга форма алгоритму transform?
бінарну операцію
Яка сортування називається «зовнішньої»?
сортування послідовних файлів, розташованих у зовнішній пам'яті
Коли файл введення починають використовувати для виведення серій в багатофазної сортування?
коли файл стає порожнім
Яка форма алгоритму transform виконує унарна операцію?
перша форма
На якому етапі виконується розподіл файлу А по файлах В і С в природному злитті методу зовнішньої сортування?
на кожному кроці
В основі чого лежить розподіл серій вихідного файлу по m допоміжних файлів?
в основі методу зовнішньої сортування збалансованим багатоколійні злиттям
Що відбувається в прямому злитті як методу зовнішньої сортування?
розподіл стану файлу А в файли В, С, а потім злиття файлів В і С в файл А
Яке призначення алгоритмів сімейства replace?
виконує заміну елементів із заданим значенням на нове значення
Який алгоритм виконує обмін місцями елементів в двох зазначених діапазонах?
iter_swap
Що відбувається на другому кроці простого злиття як методу зовнішньої сортування?
послідовно читається файл А, і в файл В записуються послідовні пари з непарними номерами, а в файл С - з парними
Який алгоритм виконує заміну всіх елементів послідовності, визначеній за допомогою ітераторів first і last, заданим значенням value?
fill
Який алгоритм виконує видалення з послідовності сусідніх елементів, рівних один одному?
unique
Що з перерахованого не відноситься до методів внутрішнього сортування?
методи, засновані на об'єднаннях
Коли з'явилися методи зовнішньої сортування?
коли найбільш поширеними пристроями були магнітні стрічки
Для чого використовують алгоритми модифікують операцій з послідовностями?
для копіювання, видалення, заміни та зміни порядку проходження елементів послідовності
Які алгоритми не включаються в сімейство remove?
remove_off
Який алгоритм виконує циклічне переміщення елементів послідовності?
rotate
Яка функція алгоритму iter_swap?
виконує обмін місцями двох елементів
Який алгоритм змінює порядок проходження елементів послідовності на зворотний?
reverse
МОДУЛЬ 5. рекурсивних АЛГОРИТМИ
Яка функція алгоритму set_intersection?
створює відсортоване перетин множин
Яка результуюча послідовність в алгоритмі set_symmetric_difference?
не повинна перекриватися з жодною з вихідних
Скільки ходів потрібно обчислити, щоб знайти послідовність ходів, при якій кінь обійде всі шахове поле розміром N × N?
N * N - 1
Як можна уявити узагальнену схему рекурсивної підпрограми?
як деяку композицію
Які функції алгоритмів роботи з множинами і пірамідами?
виконують сортування множин і операції з пірамідами
Пірамідою називається послідовність, для всіх елементів якої виконуються умови
a (i)<=a(2i+1) и a(i)<=a(2i+2)
Яка функція алгоритму includes?
виконує перевірку включення однієї послідовності в іншу
Який елемент створює відсортоване об'єднання множин?
set_union
Що входить в основний спосіб докази кінцівки рекурсії?
визначається функція f (x), така, що з f (x) <0 следует ложность условия В, и доказывается, что при каждой новой активации Р значение f(x) уменьшается
В якому випадку результат роботи алгоритму includes дорівнює true?
в тому випадку, коли кожен елемент послідовності [first2, last2) міститься в послідовності [first1, last1)
Що потрібно для роботи з пірамідою?
итератор довільного доступу
Що є постійною для всіх діагоналей, паралельних діагоналі, що з'єднує лівий верхній і правий нижній кути дошки в задачі про восьми ферзів?
різницю
Яким розташований максимальний елемент піраміди?
першим
Яка функція елемента make_heap?
виконує перетворення послідовності з довільним доступом в піраміду
Коли алгоритм push_heap виконує перетворення послідовності в піраміду?
після додавання в послідовність останнього елемента
Швидше чого працює алгоритм sort_heap?
звичайної сортування
Який алгоритм перетворює піраміду в відсортовану по зростанню послідовність?
sort_heap
Що не використовують форми, існуючі для алгоритмів роботи з множинами і пірамідами?
операцію>
Який з перерахованих випадків використання інструменту рекурсії неправильний?
обчислення факторіала
Що з перерахованого є прикладом піраміди з 10 цілих чисел?
23 20 21 17 19 18 15 12 10 14
Як простіше обчислювати числа Фібоначчі?
по ітераційної схемою
Який елемент послідовності видаляє елемент pop_heap?
перший
Якого виду рекурсивної підпрограми не існує?
назад рекурсивної