Тест контроля усвоения материала раздела «ДЕРЕВЬЯ» Поиска элемента в упорядоченном дереве, состоящем из N узлов, требует: Вопрос 1Выберите один ответ: a. всегда N шагов поиска. b. в среднем N шагов поиска. c. максимально N/2 шагов поиска. d. максимально логарифм по основанию 2 от N (log2N) шагов поиска. e. в среднем N/2 шагов поиска. Поиска элемента в упорядоченном идеально сбалансированном дереве, состоящем из N узлов, требует: Вопрос 2Выберите один или несколько ответов: a. в среднем не больше N/2 шагов поиска b. в среднем N шагов поиска. c. максимально логарифм по основанию 2 от N (log2N) шагов поиска. d. максимально N/2 шагов поиска e. всегда N шагов поиска Вопрос 3 Пока нет ответа Балл: 1,00 Отметить вопрос Текст вопроса Уровнем узла называется: Вопрос 3Выберите один ответ: a. Количество ребер между листом и узлом. b. Количество узлов от корня до узла. c. Количество ребер между корнем и узлом. d. порядковый номер узла. e. Количество узлов, с которым связан узел. Дерево является идеально сбалансированным если: Вопрос 4Выберите один ответ: a. для каждого узла количество узлов в его поддеревьях имеет одинаковую величину b. для корневого узла количество узлов в его поддеревьях различается не более чем на единицу. c. есть хотя бы один узел, для которого количество узлов в его поддеревьях различается не более чем на единицу. d. есть хотя бы один узел, для которого количество узлов в его поддеревьях равны между собой e. для каждого узла количество узлов в его поддеревьях различается не более чем на единицу. По местоположению узла в дереве существуют следующие типы узлов: Вопрос 5Выберите один или несколько ответов: a. свободный узел. b. связующий узел. c. лист d. узел ветвления e. корневой узел. Удаление узла из идеально сбалансированного дерева: Вопрос 6Выберите один или несколько ответов: a. в ряде случаев сохраняет условия идеальной сбалансированности дерева b. c) нарушает упорядоченность, если дерево было упорядоченным. c. в ряде случаев нарушает условие идеальной сбалансированности. d. преобразует дерево в сбалансированное. e. сохраняет дерево идеально сбалансированным. К базовым операциям со структурой дерево, в частности, относятся: Вопрос 7Выберите один или несколько ответов: a. удаление узла из дерева. b. включение узла в дерево. c. обход дерева. d. поиск узла в дереве. e. определение количества узлов в дереве.

Ответы:

Вопрос 1: d. максимально логарифм по основанию 2 от N (log2N) шагов поиска.

Вопрос 2: a. в среднем не больше N/2 шагов поиска, c. максимально логарифм по основанию 2 от N (log2N) шагов поиска.

Вопрос 3: b. Количество узлов от корня до узла.

Вопрос 4: a. для каждого узла количество узлов в его поддеревьях имеет одинаковую величину.

Вопрос 5: c. лист, e. корневой узел.

Вопрос 6: a. в ряде случаев сохраняет условия идеальной сбалансированности дерева, c. в ряде случаев нарушает условие идеальной сбалансированности.

Вопрос 7: a. удаление узла из дерева, b. включение узла в дерево, c. обход дерева, d. поиск узла в дереве.