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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что делает хеш-функция в хеш-таблице?

  1. AОтображает ключ в индекс таблицы
  2. BСортирует ключи в таблице
  3. CШифрует значения в таблице
  4. DПодсчитывает, сколько ключей хранится
2.Лёгкая

Что такое взвешенный граф?

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

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

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

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

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

Какова стоимость вставки элемента в середину массива из n элементов?

  1. AO(n), потому что последующие элементы нужно сдвинуть
  2. BO(log n) из-за двоичного поиска
  3. CO(n²), потому что каждый элемент сдвигается n раз
  4. DO(1), потому что индекс известен
6.Средняя

Симметричный обход (in-order) двоичного дерева поиска посещает ключи:

  1. AПо уровням
  2. BВ порядке вставки
  3. CВсегда в порядке убывания
  4. DВ порядке возрастания (отсортированно)
7.Сложная

Удаление узла с двумя потомками из двоичного дерева поиска обычно выполняют так:

  1. AМеняют его местами с корнем
  2. BПерестраивают поддерево под ним с нуля и заново вставляют каждый содержавшийся в нём ключ
  3. CУдаляют всё поддерево
  4. DЗаменяют его in-order преемником (или предшественником) и удаляют тот узел
8.Сложная

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

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

Ответы

  1. 1. A · Отображает ключ в индекс таблицы
  2. 2. D · Граф, в котором у каждого ребра есть числовое значение, например стоимость или расстояние
  3. 3. A · Оно хранит элементы без повторений
  4. 4. A · В двусвязном списке
  5. 5. A · O(n), потому что последующие элементы нужно сдвинуть
  6. 6. D · В порядке возрастания (отсортированно)
  7. 7. D · Заменяют его in-order преемником (или предшественником) и удаляют тот узел
  8. 8. D · Левый поворот в левом потомке, затем правый поворот в узле

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