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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое степень вершины в неориентированном графе?

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

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

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

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

  1. AАдрес первого узла
  2. BNull (узла нет)
  3. CАдрес предыдущего узла
  4. DЧисло узлов в списке
4.Средняя

Как найти минимальный ключ в двоичном дереве поиска?

  1. AИдти от корня по правым потомкам, пока правого потомка не окажется
  2. BОбойти все листья и сравнить их
  3. CПосмотреть только на корень
  4. DИдти от корня по левым потомкам, пока левого потомка не окажется
5.Средняя

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

  1. AЛинейное пробирование
  2. BМетод цепочек (separate chaining)
  3. CДвойное хеширование
  4. DКвадратичное пробирование
6.Средняя

Очередь реализована двумя стеками: push в стек «in», pop из стека «out», который при опустошении заполняется из «in». Какова амортизированная стоимость одной операции?

  1. AO(1)
  2. BO(log n)
  3. CO(n²)
  4. DO(n)
7.Сложная

Каково время работы поиска в ширину на графе с V вершинами, хранящемся в виде матрицы смежности?

  1. AO(V)
  2. BO(V + E)
  3. CO(E log V)
  4. DO(V²)
8.Сложная

Алгоритм Кана для топологической сортировки многократно удаляет вершины с полустепенью захода 0. Какая структура хранит эти вершины?

  1. AСтек всех посещённых рёбер
  2. BМатрица смежности, фиксирующая, какие вершины уже удалены
  3. CОчередь (или любая коллекция) вершин с полустепенью захода 0
  4. DMax-куча, упорядоченная по полустепени исхода

Ответы

  1. 1. C · Число инцидентных ей рёбер
  2. 2. D · Оно хранит элементы без повторений
  3. 3. B · Null (узла нет)
  4. 4. D · Идти от корня по левым потомкам, пока левого потомка не окажется
  5. 5. B · Метод цепочек (separate chaining)
  6. 6. A · O(1)
  7. 7. D · O(V²)
  8. 8. C · Очередь (или любая коллекция) вершин с полустепенью захода 0

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