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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что делает операция peek (или top) стека?

  1. AУдаляет верхний элемент и возвращает его
  2. BВозвращает нижний элемент стека
  3. CВозвращает верхний элемент, не удаляя его
  4. DУдаляет все элементы из стека
3.Лёгкая

Что такое коэффициент заполнения (load factor) хеш-таблицы?

  1. AЧисло корзин, делённое на среднюю длину хранимых ключей
  2. BЧисло коллизий на данный момент
  3. CВремя загрузки таблицы с диска
  4. DЧисло хранимых элементов, делённое на число корзин
4.Средняя

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

  1. AВ динамическом массиве
  2. BВ двусвязном списке
  3. CВ отсортированном массиве
  4. DВ односвязном списке
5.Средняя

Как вставляется новый элемент в двоичную кучу?

  1. AЕго помещают в корень и опускают вниз
  2. BЕго вставляют в отсортированную позицию, сдвигая все бо́льшие элементы на одно место вправо
  3. CВсю кучу перестраивают с нуля
  4. DЕго помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
6.Средняя

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков обратный обход (postorder)?

  1. A4 5 2 3 1
  2. B4 2 5 1 3
  3. C1 2 4 5 3
  4. D5 4 3 2 1
7.Сложная

Узел АВЛ-дерева разбалансирован, потому что правое поддерево его левого потомка стало слишком высоким (случай левый–правый). Какое исправление применяется?

  1. AПравый поворот в левом потомке, затем левый поворот в узле
  2. BЛевый поворот в левом потомке, затем правый поворот в узле
  3. CОдиночный левый поворот в узле
  4. DОдиночный правый поворот в узле
8.Сложная

Что делает косое дерево (splay tree) после каждого обращения?

  1. AПоворотами поднимает узел, к которому обращались, в корень
  2. BПеремещает узел, к которому обращались, в лист
  3. CПерекрашивает узлы на пути поиска
  4. DПерестраивает всё дерево в сбалансированном виде

Ответы

  1. 1. B · Оно хранит элементы без повторений
  2. 2. C · Возвращает верхний элемент, не удаляя его
  3. 3. D · Число хранимых элементов, делённое на число корзин
  4. 4. B · В двусвязном списке
  5. 5. D · Его помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
  6. 6. A · 4 5 2 3 1
  7. 7. B · Левый поворот в левом потомке, затем правый поворот в узле
  8. 8. A · Поворотами поднимает узел, к которому обращались, в корень

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