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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что содержит каждый узел двусвязного списка?

  1. AДве копии данных и один указатель
  2. BДанные и только указатель на следующий узел
  3. CДанные, указатель на следующий узел и указатель на предыдущий узел
  4. DДанные и два указателя: один на следующий узел и один на узел после него
2.Лёгкая

Какая структура данных работает по принципу «последним пришёл — первым ушёл» (LIFO)?

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

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

  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Обход массива занимает в сумме O(1), а связного списка — O(n)
6.Средняя

Что верно для матрицы смежности неориентированного графа?

  1. AВ каждой строке ровно одна 1
  2. BОна всегда верхнетреугольная
  3. CОна симметрична относительно главной диагонали
  4. DНа её главной диагонали всегда стоят единицы
7.Сложная

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

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

Чем radix-дерево (сжатое префиксное дерево) лучше обычного trie?

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

Ответы

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

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