Структуры данных: лист заданий с ответами

Бесплатный лист заданий для печати по теме «Структуры данных»: 8 задач от простых до экзаменационного уровня, с ответами. Распечатайте его или сохраните как PDF.

Новый лист заданийЗаниматься онлайн с подсказками

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Хеш-таблица (hash table) хранит данные в виде:

  1. AТолько отсортированного списка
  2. BПар ключ–значение, расположение которых определяет хеш-функция
  3. CДерева с упорядоченными ключами
  4. DСтроки фиксированной длины
2.Лёгкая

В чём главное отличие статического массива от динамического?

  1. AДинамический массив может расти, переходя в больший блок памяти
  2. BСтатический массив даёт более медленный доступ по индексу
  3. CДинамический массив хранит свои элементы в связанных узлах, поэтому может расти по одному элементу
  4. DСтатический массив может хранить только числа
3.Лёгкая

Где находится наименьший элемент двоичной min-кучи?

  1. AВ каком-то листе, который придётся искать
  2. BВ корне
  3. CВ последней позиции массива
  4. DВ самом левом листе
4.Средняя

Что происходит, когда хеш-таблица выполняет рехеширование после превышения порога коэффициента заполнения?

  1. AСамые старые ключи удаляются, чтобы освободить место
  2. BСуществующие ключи сортируются на месте
  3. CВ новый список переполнения в конце таблицы переносятся только конфликтующие ключи
  4. DВыделяется таблица большего размера, и каждый ключ вставляется заново
5.Средняя

Какую структуру данных использует выполняющаяся программа для отслеживания активных вызовов функций и их локальных переменных?

  1. AДвоичное дерево поиска кадров
  2. BХеш-таблицу функций
  3. CСтек вызовов
  4. DОчередь памяти кучи
6.Средняя

В двоичной min-куче, хранящейся в массиве (индексация с 0), потомки узла с индексом i находятся на позициях:

  1. A2i + 1 и 2i + 2
  2. Bi + 1 и i + 2
  3. C2i и 2i + 1
  4. Di/2 и i/2 + 1
7.Сложная

Почему B-деревья используются в базах данных и файловых системах?

  1. AИм не нужна перебалансировка
  2. BОни хранят неотсортированные данные
  3. CОни занимают меньше памяти, чем любой массив, поэтому весь индекс всегда помещается в оперативной памяти
  4. DВысокая степень ветвления делает дерево неглубоким и сокращает число медленных чтений с диска
8.Сложная

В BST с корнем 50, левым поддеревом 30 (потомки 20, 40) и правым поддеревом 70 (потомки 60, 80) корень удаляют с помощью in-order преемника. Какой ключ станет новым корнем?

  1. A80
  2. B70
  3. C60
  4. D40

Ответы

  1. 1. B · Пар ключ–значение, расположение которых определяет хеш-функция
  2. 2. A · Динамический массив может расти, переходя в больший блок памяти
  3. 3. B · В корне
  4. 4. D · Выделяется таблица большего размера, и каждый ключ вставляется заново
  5. 5. C · Стек вызовов
  6. 6. A · 2i + 1 и 2i + 2
  7. 7. D · Высокая степень ветвления делает дерево неглубоким и сокращает число медленных чтений с диска
  8. 8. C · 60

Полные пошаговые решения: занимайтесь этой темой на examproblems.com.