Робочий аркуш «Структури даних» з відповідями

Безкоштовний робочий аркуш для друку «Структури даних»: 8 задач від легких до рівня іспиту, з ключем відповідей. Роздрукуйте його або збережіть як PDF.

Новий робочий аркушТренуватися онлайн з підказками

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

Ім’я: ____________________   Дата: ____________

1.Легка

Що містить вказівник next останнього вузла однозв'язного списку?

  1. AКількість вузлів у списку
  2. BАдресу першого вузла
  3. CNull (жодного вузла)
  4. DАдресу попереднього вузла
2.Легка

Яка структура даних працює за принципом «останнім прийшов — першим вийшов» (LIFO)?

  1. AЧерга
  2. BЗв'язний список
  3. CГеш-таблиця
  4. DСтек
3.Легка

Яку структуру даних використовують для обходу дерева по рівнях?

  1. AСтек
  2. BЧергу
  3. CЧергу з пріоритетом
  4. DГеш-таблицю
4.Середня

Чергу реалізовано двома стеками: push у стек «in» і pop зі стека «out», який поповнюють із «in», коли він порожній. Яка амортизована вартість однієї операції?

  1. AO(log n)
  2. BO(1)
  3. CO(n²)
  4. DO(n)
5.Середня

Скільки пам'яті займає матриця суміжності графа з V вершинами?

  1. AO(V + E)
  2. BO(log V)
  3. CO(E)
  4. DO(V²)
6.Середня

Чому бінарну купу можна зберігати в масиві без жодних вказівників?

  1. AМасиви автоматично зберігають ключі відсортованими, тож вказівники не потрібні
  2. BУсі ключі в купі однакові
  3. CЦе повне бінарне дерево, тож позиції визначаються простими формулами індексів
  4. DКупи ніколи не містять понад 100 елементів
7.Складна

Яка пара обходів завжди однозначно визначає бінарне дерево з різними ключами?

  1. AПрямий і симетричний обходи
  2. BПрямий і зворотний обходи
  3. CЛише обхід по рівнях
  4. DЛише прямий обхід
8.Складна

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

  1. AЩоб масив залишався відсортованим
  2. BБо зменшення вдвічі за половинного заповнення призвело б до втрати елементів
  3. CБо розподілювач пам'яті може звільняти пам'ять лише чвертями блока
  4. DЩоб уникнути повторних змін розміру, коли push і pop чергуються біля межі

Ключ відповідей

  1. 1. C · Null (жодного вузла)
  2. 2. D · Стек
  3. 3. B · Чергу
  4. 4. B · O(1)
  5. 5. D · O(V²)
  6. 6. C · Це повне бінарне дерево, тож позиції визначаються простими формулами індексів
  7. 7. A · Прямий і симетричний обходи
  8. 8. D · Щоб уникнути повторних змін розміру, коли push і pop чергуються біля межі

Повні покрокові розв’язки: тренуйте цю тему на examproblems.com.