Комбинаторные алгоритмы для программистов

Упражнение 1:

Номер 1

Что называется стеком?

Ответ:

(1) одномерная структура данных, загрузка или увеличение элементов для которой осуществляется с помощью указателя стека в соответствии с правилом FIFO ("first-in, first-out"- "первым введен, первым выведен")

(2) одномерная структура данных, загрузка или увеличение элементов для которой осуществляется с помощью индекса стека в соответствии с правилом LIFO ("last-in, first-out" - "последним введен, первым выведен")

(3) одномерная структура данных, загрузка или увеличение элементов для которой осуществляется с помощью адреса стека в соответствии с правилом LIFO ("last-in, first-out" - "последним введен, первым выведен")

(4) одномерная структура данных, загрузка или увеличение элементов для которой осуществляется с помощью указателя стека в соответствии с правилом LIFO ("last-in, first-out" — "последним введен, первым выведен")

Номер 2

Что содержится в указателе стека  sp (steck pointer)?

Ответ:

(1) адрес первого элемента, который является единственным элементом стека, доступным в данный момент времени для обработки

(2) значение текущего элемента, который является единственным элементом стека, доступным в данный момент времени для обработки

(3) индекс (адрес) текущего элемента, который является единственным элементом стека, доступным в данный момент времени для обработки

(4) ссылка на текущей элемент, который является единственным элементом стека, доступным в данный момент времени для обработки

Номер 3

Какие существуют основные базисные операции для работы со стеком?

Ответ:

(1) начальная установка; загрузка элемента x в стек; извлечение элемента из стека; проверка на переполнение и загрузка элемента в стек; проверка наличия элементов и извлечение элемента стека; чтение данных из указателя стека без извлечения элемента

(2) начальная установка; загрузка элемента x в стек; проверка на переполнение и загрузка элемента в стек; проверка наличия элементов и извлечение элемента стека; чтение данных из указателя стека без извлечения элемента

(3) начальная установка; загрузка элемента x в стек; извлечение элемента из стека; проверка наличия элементов и извлечение элемента стека; чтение данных из указателя стека без извлечения элемента

(4) начальная установка; загрузка элемента x в стек; извлечение элемента из стека; проверка на переполнение и загрузка элемента в стек; проверка наличия элементов и извлечение элемента стека

Упражнение 2:

Номер 1

Что называется очередью?

Ответ:

(1) одномерная структура данных, для которой загрузка или извлечение элементов осуществляется с помощью указателей начала извлечения (head) и конца (tail) очереди в соответствии с правилом LIFO

(2) одномерная структура данных, для которой загрузка или извлечение элементов осуществляется с помощью указателей начала извлечения (head) и конца (tail)

(3) одномерная структура данных, для которой загрузка или извлечение элементов осуществляется с помощью указателей начала извлечения (head) и конца (tail) очереди в соответствии с правилом FIFO ("first-in, first-out" - "первым введен, первым выведен")

(4) одномерная структура данных, для которой загрузка или извлечение элементов осуществляется с помощью указателей начала извлечения (head) и конца (tail) очереди в соответствии с правилом LIFO ("last-in, first-out" - "последним введен, первым выведен")

Номер 2

Какие существуют основные базисные операции для работы с очередью?

Ответ:

(1) начальная установка; добавление элемента; проверка переполнения очереди и включение в нее элемента; проверка элементов и исключение элемента

(2) начальная установка; добавление элемента; исключение элемента; проверка переполнения очереди и включение в нее элемента; проверка элементов и исключение элемента

(3) начальная установка;добавление элемента; проверка переполнения очереди и включение в нее элемента; проверка элементов и исключение элемента

(4) начальная установка; добавление элемента; исключение элемента; проверка элементов и исключение элемента

Номер 3

Что называется связанным списком?

Ответ:

(1) структура данных, которая состоит из узлов (как правило, записей), содержащих указатели на следующий узел. Указатель, который ни на что не указывает, снабжается значением nil. Таким образом, в каждый элемент связанного списка добавляется указатель (звено связи)

(2) структура данных, которая состоит из узлов (как правило, записей), содержащих ссылки на следующий узел. Указатель, который ни на что не указывает, снабжается значением nil. Таким образом, в каждый элемент связанного списка добавляется указатель (звено связи)

(3) структура данных, которая состоит из узлов (как правило, записей), содержащих адреса следующего узла. Указатель, который ни на что не указывает, снабжается значением nil. Таким образом, в каждый элемент связанного списка добавляется указатель (звено связи)

(4) структура данных, которая состоит из узлов (как правило, структур), содержащих указатели на следующий узел. Указатель, который ни на что не указывает, снабжается значением nil. Таким образом, в каждый элемент связанного списка добавляется указатель (звено связи)

Упражнение 3:

Номер 1

Каковы основные базисные операции для работы с  однонаправленным связанным списком?

Ответ:

(1) включение элемента; исключение преемника элемента; включение элемента перед заданным элементом; отметим, что исключение последнего элемента из однонаправленного списка связано с просмотром всего списка

(2) включение элемента; включение элемента перед заданным элементом; отметим, что исключение последнего элемента из однонаправленного списка связано с просмотром всего списка

(3) исключение преемника элемента; включение элемента перед заданным элементом; отметим, что исключение последнего элемента из однонаправленного списка связано с просмотром всего списка

(4) включение элемента; исключение преемника элемента

Номер 2

Каковы основные базисные операции для работы с двунаправленным связанным списком?

Ответ:

(1) включение y перед элементом x; включение элемента y после элемента x; исключение элемента x

(2) включение элемента y после элемента x; исключение элемента x

(3) включение y перед элементом x; включение элемента y после элемента x

(4) включение y перед элементом x; исключение элемента x

Номер 3

Что такое двоичное дерево?

Ответ:

(1) это такое ориентированное дерево, в котором: имеется ровно одна вершина, в которую не входит ни одного ребра. Эта вершина называется корнем двоичного дерева; в каждую вершину, кроме корня, входит одно ребро; из каждой вершины (включая корень) исходит не более двух ребер

(2) это такое ориентированное дерево, в котором: имеется ровно одна вершина, в которую не входит ни одного ребра; эта вершина называется корнем двоичного дерева

(3) это такое ориентированное дерево, в котором: в каждую вершину, кроме корня, входит одно ребро; из каждой вершины (включая корень) исходит не более двух ребер

(4) это такое ориентированное дерево, в котором: в каждую вершину, кроме корня, входит одно ребро; из каждой вершины (включая корень) исходит не более двух ребер

Комбинаторные алгоритмы для программистов - тест 11