Топ-50 запитань і відповідей на інтерв’ю про структуру даних

Ось питання та відповіді на співбесіді щодо Data Structures для нових і досвідчених кандидатів, щоб отримати роботу своєї мрії.

1) Що таке структура даних?

Структура даних стосується способу організації та обробки даних. Він прагне знайти способи зробити доступ до даних більш ефективним. Маючи справу зі структурою даних, ми зосереджуємося не лише на одній частині даних, але й на іншому наборі даних і тому, як вони можуть організовано зв’язуватися між собою.

---

2) Розрізняйте файлову та структурну структуру зберігання.

Ключовою відмінністю між обома структурами даних є область пам’яті, до якої здійснюється доступ. Коли мова йде про структуру, яка містить основну пам’ять комп’ютерної системи, це називається структурою зберігання. Маючи справу з допоміжною структурою, ми називаємо її файловою структурою.

Безкоштовне завантаження PDF: Структури даних, запитання та відповіді на інтерв’ю

---

3) Коли найкраще застосовувати двійковий пошук?

Двійковий пошук — це алгоритм, який найкраще застосовувати для пошуку в списку, коли елементи вже впорядковані або відсортовані. Пошук у списку починається з середини, таким чином, якщо це середнє значення не є цільовим ключем пошуку, буде перевірено, чи продовжиться пошук у нижній половині списку чи у вищій. Потім розділення та пошук продовжаться таким же чином.

---

4) Що таке a пов'язаний список?

Зв’язаний список — це послідовність вузлів, у якій кожен вузол з’єднаний із наступним за ним вузлом. Це утворює ланцюжок для зберігання даних.

---

5) Як посилатися на всі елементи в одному вимірі масив?

Щоб звернутися до всіх елементів одновимірного масиву, потрібно використовувати індексований цикл, таким чином, щоб лічильник виконував значення від 0 до розміру масиву мінус один. Таким чином, ви можете звернутися до всіх елементів послідовно, використовуючи лічильник циклу як нижній індекс масиву.

---

6) У яких сферах застосовуються структури даних?

Структури даних важливі майже в кожному аспекті, де задіяні дані. Загалом, алгоритми, які включають ефективну структуру даних, застосовуються в таких областях: чисельний аналіз, операційна система, штучний інтелект, дизайн компілятора, керування базами даних, графіка та статистичний аналіз – це лише деякі з них.

---

7) Що таке LIFO?

LIFO — це коротка форма «Останній прийшов, перший вийшов». Це стосується того, як дані отримують доступ, зберігаються та витягуються. Використовуючи цю схему, дані, які зберігалися останніми, повинні витягуватися першими. Це також означає, що для того, щоб отримати доступ до перших даних, усі інші дані, які зберігалися до цих перших даних, повинні бути спочатку отримані та витягнуті.

---

8) Що таке черга?

Черга — це структура даних, яка може імітувати список або потік даних. У цій структурі нові елементи вставляються з одного кінця, а існуючі елементи видаляються з іншого кінця.

---

9) Що таке бінарні дерева?

Бінарне дерево — це один тип структури даних, який має два вузли, лівий вузол і правий вузол. У програмуванні двійкові дерева є розширенням зв'язаних спискових структур.

---

10) Які структури даних застосовуються при роботі з рекурсивною функцією?

Рекурсія — це функція, яка викликає сама себе на основі умови завершення, використовує стек. Використовуючи LIFO, виклик рекурсивної функції зберігає адресу повернення, щоб вона знала, як повернутися до викликаючої функції після завершення виклику.

---

11) Що таке стек?

Стек — це структура даних, у якій доступний лише верхній елемент. Оскільки дані зберігаються в стеку, усі дані зміщуються вниз, залишаючи останні додані дані зверху.

---

12) Поясніть бінарне дерево пошуку

Двійкове дерево пошуку зберігає дані таким чином, що їх можна отримати дуже ефективно. Ліве піддерево містить вузли, ключі яких менші за значення ключа вузла, а праве піддерево містить вузли, ключі яких більші або дорівнюють значенню ключа вузла. Крім того, обидва піддерева також є бінарними деревами пошуку.

---

13) Що таке багатовимірні масиви?

Багатовимірні масиви використовують кілька індексів для зберігання даних. Це корисно, коли зберігаються дані, які неможливо представити за допомогою одновимірного індексування, наприклад, представлення даних у настільній грі, таблиці з даними, що зберігаються в кількох стовпцях.

---

14) Чи вважаються пов’язані списки лінійними чи нелінійними структурами даних?

Це залежить від того, де ви збираєтеся застосувати пов’язані списки. Якщо ви ґрунтуєтеся на пам’яті, пов’язаний список вважається нелінійним. З іншого боку, якщо ви базуєтеся на стратегіях доступу, зв’язаний список вважається лінійним.

---

15) Як динамічний розподіл пам’яті допомагає в управлінні даними?

Окрім можливості зберігати прості структуровані типи даних, динамічний розподіл пам’яті може поєднувати окремо виділені структуровані блоки для формування складених структур, які розширюються та звужуються за потреби.

---

16) Що таке FIFO?

FIFO розшифровується як First-in-First-out і використовується для представлення того, як здійснюється доступ до даних у черзі. Дані, які були вставлені в список черги, найдовші – це ті, які видаляються першими.

---

17) Що таке впорядкований список?

Упорядкований список — це список, у якому позиція кожного вузла в списку визначається значенням його ключового компонента, так що ключові значення утворюють зростаючу послідовність у міру проходження списку.

---

18) Що таке сортування злиттям?

Сортування злиттям – це метод сортування даних за принципом «розділяй і володарюй». У послідовності даних суміжні дані об’єднуються та сортуються для створення більших відсортованих списків. Ці відсортовані списки потім знову об’єднуються для формування ще більшого відсортованого списку, і цей процес триває до отримання єдиного відсортованого списку.

---

19) Розрізняйте NULL і VOID

Null — це значення, а Void — ідентифікатор типу даних. Змінна, якій надано значення Null, означає порожнє значення. Пустота використовується для ідентифікації вказівників як таких, що не мають початкового розміру.

---

20) Яка головна перевага пов’язаного списку?

Зв’язаний список є ідеальною структурою даних, оскільки його можна легко змінювати. Це означає, що редагування пов’язаного списку працює незалежно від кількості елементів у списку.

---

21) Яка різниця між PUSH і POP?

Проштовхування та витягування застосовуються до способу зберігання та отримання даних у стеку. Проштовхування означає, що до нього додаються дані, тобто дані «виштовхуються» в стек. З іншого боку, pop позначає пошук даних і, зокрема, стосується найвищих даних, до яких здійснюється доступ.

---

22) Що таке лінійний пошук?

Лінійний пошук означає спосіб пошуку цільового ключа в послідовній структурі даних. У цьому методі кожен елемент у списку перевіряється та порівнюється з цільовим ключем. Процес повторюється до тих пір, поки не буде знайдено або якщо файл досягнуто кінця.

---

23) Як оголошення змінної впливає на розподіл пам'яті?

Обсяг пам'яті, який буде виділено або зарезервовано, залежатиме від типу даних змінної, що оголошується. Наприклад, якщо оголошено змінну цілого типу, то для цієї змінної буде зарезервовано 32 біти пам’яті.

---

24) У чому перевага купи над стеком?

Купа більш гнучка, ніж стек. Це тому, що простір пам’яті для купи можна динамічно розподіляти та вилучати за потреби. Однак пам'ять купи іноді може бути повільнішою порівняно з цим стеком.

---

25) Що таке постфіксальний вираз?

Постфіксний вираз — це вираз, у якому кожен оператор слідує за своїми операндами. Перевага цієї форми полягає в тому, що немає необхідності групувати підвирази в дужках або враховувати пріоритет операторів.

---

26) Що таке абстракція даних?

Абстракція даних є потужним інструментом для розбиття складних проблем із даними на керовані блоки. Це застосовується шляхом початкового визначення задіяних об’єктів даних і операцій, які мають виконуватися над цими об’єктами даних, не надто турбуючись про те, як об’єкти даних будуть представлені та збережені в пам’яті.

---

27) Як вставити новий елемент у бінарне дерево пошуку?

Припускаючи, що дані, які потрібно вставити, є унікальним значенням (тобто не наявним записом у дереві), спочатку перевірте, чи дерево порожнє. Якщо він порожній, просто вставте новий елемент у кореневий вузол. Якщо він не порожній, зверніться до ключа нового елемента. Якщо він менший за ключ кореня, вставте його в ліве піддерево кореня, інакше вставте його в праве піддерево кореня.

---

28) Як сортування вибору працює для масиву?

Сортування вибору є досить інтуїтивно зрозумілим алгоритмом сортування, хоча і не обов’язково ефективним. У цьому процесі найменший елемент спочатку знаходиться та перемикається з елементом у нульовому індексі, таким чином розміщуючи найменший елемент у першій позиції.

Найменший елемент, що залишився у підмасиві, потім розташовується поруч із нижніми індексами від 1 до n-1 і замінюється елементом під індексом 1, таким чином розміщуючи другий найменший елемент у другій позиції. Етапи повторюються таким же чином до останнього елемента.

---

29) Як числа зі знаком і без знаку впливають на пам'ять?

У випадку чисел зі знаком перший біт використовується для позначення того, чи є число додатним чи від’ємним, що залишає один біт недостигаючим. У випадку чисел без знака доступні всі біти для цього числа. Ефект найкраще видно в діапазоні чисел (8-бітове число без знака має діапазон від 0 до 255, тоді як 8-бітове число зі знаком має діапазон від -128 до +127).

---

30) Яку мінімальну кількість вузлів може мати бінарне дерево?

Бінарне дерево може мати мінімум нульових вузлів, що відбувається, коли вузли мають значення NULL. Крім того, бінарне дерево також може мати 1 або 2 вузли.

---

31) Що таке динамічні структури даних?

Динамічні структури даних — це структури, які розширюються та звужуються під час виконання програми. Він надає гнучкі засоби маніпулювання даними, оскільки він може налаштовуватися відповідно до розміру даних.

---

32) У яких структурах даних застосовуються покажчики?

Покажчики, які використовуються у зв’язаному списку, мають різні застосування в структурі даних. Структури даних, які використовують цю концепцію, включають стек, чергу, пов’язаний список і бінарне дерево.

---

33) Чи всі оператори декларації призводять до фіксованого резервування в пам’яті?

Більшість оголошень так, за винятком покажчиків. Оголошення покажчика виділяє пам'ять не для даних, а для адреси змінної покажчика. Фактичний розподіл пам'яті для даних відбувається під час виконання.

---

34) Що таке МАСИВИ?

При роботі з масивами дані зберігаються та витягуються за допомогою індексу, який посилається на номер елемента в послідовності даних. Це означає, що дані можуть бути доступні в будь-якому порядку. У програмуванні масив оголошується як змінна, що має ряд індексованих елементів.

---

35) Яка мінімальна кількість черг необхідна для реалізації пріоритетної черги?

Мінімальна кількість черг, необхідних у цьому випадку, становить дві. Одна черга призначена для сортування пріоритетів, а інша використовується для фактичного зберігання даних.

---

36) Який алгоритм сортування вважається найшвидшим?

Існує багато типів алгоритмів сортування: швидке сортування, бульбашкове сортування, сортування в кулі, сортування за основою, сортування злиттям тощо. Жоден із них не може вважатися найшвидшим, оскільки кожен алгоритм розроблено для певної структури даних і набору даних. Це залежатиме від набору даних, який ви хочете відсортувати.

---

37) Відрізнити STACK від ARRAY.

Стек дотримується шаблону LIFO. Це означає, що доступ до даних відбувається за послідовністю, в якій останні дані, які зберігаються, одночасно з першими, які вилучаються. З іншого боку, масиви не дотримуються певного порядку, а доступ до них можна отримати, посилаючись на індексований елемент у масиві.

---

38) Наведіть базовий алгоритм пошуку в бінарному дереві пошуку.

1. якщо дерево порожнє, то ціль не знаходиться в дереві, завершити пошук
2. якщо дерево не порожнє, мета знаходиться в дереві
3. перевірте, чи ціль знаходиться в кореневому елементі
4. якщо ціль не знаходиться в кореневому елементі, перевірити, чи ціль менша за значення кореня
5. якщо ціль менша за значення кореня, шукайте ліве піддерево
6. в іншому випадку шукайте потрібне піддерево

---

39) Що таке дечерга?

Дечерга — це двокінцева черга. Це структура, в якій елементи можна вставляти або видаляти з будь-якого кінця.

---

40) Що таке бульбашкове сортування і як його виконати?

Бульбашкове сортування — це метод сортування, який можна застосувати до структур даних, наприклад масиву. Він працює шляхом порівняння суміжних елементів і обміну їхніми значеннями, якщо вони не в порядку. Цей метод дозволяє меншим значенням «виникати» у верхній частині списку, тоді як більші значення опускаються вниз.

---

41) З яких частин складається пов’язаний список?

Зв'язаний список зазвичай складається з двох частин: голови та хвоста. Між головою та хвостом розташовані власне вузли. Усі ці вузли пов'язані послідовно.

---

42) Як працює вибіркове сортування?

Сортування за вибором працює шляхом вибору найменшого числа зі списку та розміщення його на початку. Цей процес повторюється для другої позиції в кінці списку. Це найпростіший алгоритм сортування.

---

43) Що таке графік?

Граф — це один тип структури даних, який містить набір упорядкованих пар. Ці впорядковані пари також називаються ребрами або дугами та використовуються для з’єднання вузлів, де можна зберігати та отримувати дані.

---

44) Відрізнити лінійну структуру даних від нелінійної.

Лінійна структура даних — це структура, в якій елементи даних розташовані поруч один з одним. Приклади лінійної структури даних включають масиви, пов’язані списки, стеки та черги. З іншого боку, нелінійна структура даних — це структура, в якій кожен елемент даних може з’єднуватися з більш ніж двома сусідніми елементами даних. Приклади нелінійної структури даних включають дерева та графи.

---

45) Що таке дерево AVL?

Дерево AVL — це тип бінарного дерева пошуку, який завжди перебуває в стані частково збалансованого. Баланс вимірюється як різниця між висотою піддерев від кореня. Відомо, що це самобалансуюче дерево було першою структурою даних, розробленою як така.

---

46) Що таке двозв'язані списки?

Двозв’язані списки — це особливий тип зв’язаних списків, у якому обхід між елементами даних можна виконувати в обох напрямках. Це стало можливим завдяки наявності двох посилань у кожному вузлі, одного, що зв’язує з наступним вузлом, а іншого – з попереднім вузлом.

---

47) Що таке алгоритм Хаффмана?

Алгоритм Хаффмана використовується для створення розширених бінарних дерев, які мають мінімально зважені довжини шляху із заданих ваг. Він використовує таблицю, яка містить частоту появи для кожного елемента даних.

---

48) Що таке пошук Фібоначчі?

Пошук за Фібоначчі — це алгоритм пошуку, який застосовується до відсортованого масиву. Він використовує підхід «розділяй і володарюй», який може значно скоротити час, необхідний для досягнення цільового елемента.

---

49) Коротко поясніть рекурсивний алгоритм.

Рекурсивний алгоритм націлюється на проблему, розділяючи її на менші, керовані підпроблеми. Результат однієї рекурсії після обробки однієї підпроблеми стає входом для наступного рекурсивного процесу.

---

50) Як ви шукаєте цільовий ключ у пов’язаному списку?

Щоб знайти цільовий ключ у пов’язаному списку, потрібно застосувати послідовний пошук. Кожен вузол проходить і порівнюється з цільовим ключем, і якщо він відрізняється, то він йде за посиланням на наступний вузол. Цей обхід триває до тих пір, поки цільовий ключ не знайдено або не буде досягнуто останнього вузла.

Ці запитання для співбесіди також допоможуть у вашій віва (усній). Наша команда експертів склала список найпоширеніші питання та відповіді на співбесіді з кадрами які інтерв’юери можуть запитати вас під час співбесіди щодо структури даних.