Элемент дерева на который не ссылаются другие называется
Перейти к содержимому

Элемент дерева на который не ссылаются другие называется

Элемент дерева на который не ссылаются другие называется

Граф — это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта.

6.2.2. Логическое представление и изображение деревьев.
6.2.3. Бинарные деревья.
6.2.4. Представление любого дерева, леса бинарными деревьями.
  • 1. В каждом узле оставить только ветвь к старшему сыну (вертикальное соединение);
  • 2. Соединить горизонтальными ребрами всех братьев одного отца;
  • 3. Таким образом перестроить дерево по правилу:
    • левый сын — вершина, расположенная под данной;
    • правый сын — вершина, расположенная справа от данной (т.е. на одном ярусе с ней).
    6.2.5. Машинное представление деревьев в памяти ЭВМ.
    LPTR DATA RPTR
    6.2.6. Основные операции над деревьями.
    • 1) Поиск узла с заданным ключом ( Find ).
    • 2) Добавление нового узла ( Dob ).
    • 3) Удаление узла ( поддерева ) ( Udal ).
    • 4) Обход дерева в определенном порядке:
      • Нисходящий обход ( процедура Preorder , рекурсивная процедура r_Preoder);
      • Смешанный обход (процедура Inorder, рекурсивная процедура r_Inorder);
      • Восходящий обход ( процедура Postorder, рекурсивная процедура r_Postorder).
      • процедура включения в стек при нисходящем обходе (Push_st);
      • функция извлечения из стека при нисходящем обходе (Pop_st);
      • процедура включения в стек при восходящем и смешанном обходе (S_Push);
      • функция извлечения из стека при восходящем и смешанном обходе (S_Pop).
      • функция нахождения сына данного узла ( Inson );
      • функция нахождения отца данного узла ( Inp );
        • процедура включения в дерево узла слева от данного (leftIn);
          
        Function Find(k:KeyType;d:TreePtr;var rez:TreePtr):bollean; 
        < где k - ключ, d - корень дерева, rez - результат > 
        Var 
        p,g: TreePtr; 
        b: boolean; 
        Begin 
        b:=false; p:=d; < ключ не найден > 
        if d <> NIL then 
        repeat q: =p; if p^.key = k then b:=true < ключ найден > 
        else begin q:=p; < указатель на отца > 
        if k < p^.key then p:=p^.left < поиск влево > 
        else p:=p^.right < поиск вправо> 
        end; until b or (p=NIL); 
        Find:=b; rez:=q; 
        End;
         
        Procedure Dob (k:KeyType; var d:TreePtr; zap:data); 
        < k - ключ, d - узел дерева, zap - запись > 
        Var 
        r,s: TreePtr; 
        t: DataPtr; 
        Begin 
        if not Find(k,d,r) then 
        begin (* Занесение в новое звено текста записи *) 
        new(t); t^:=zap; new(s); s^.key:=k; 
        s^.ssil:=t; s^.left:=NIL; s^.right:=NIL; 
        if d = NIL then d:=s (* Вставка нового звена *) 
        else if k < r^.key
        then r^.left:=s 
        else r^.right:=s; 
        end; End;

        тесты2

        Только сегодня: скидка до 20% в подарок на первый заказ.
        Какую работу нужно написать?

        Другую работу

        Помощник Анна

        1. Структура данных представляет собой
        1. набор правил и ограничений, определяющих связи между отдельными элементами и группами данных
        2. набор правил и ограничений, определяющих связи между отдельными элементами данных
        3. набор правил и ограничений, определяющих связи между отдельными группами данных
        4. некоторую иерархию данных
        1. Линейный список, в котором доступен только последний элемент, называется
        1. стеком
        2. очередью
        3. деком
        4. массивом
        5. кольцом
        1. Структура данных работа с элементами которой организована по принципу FIFO (первый пришел — первый ушел) это –

        а) Стек б) Дек в) Очередь г) Список

        1. Линейный последовательный список, в котором включение исключение элементов возможно с обоих концов, называется
        1. стеком
        2. очередью
        3. деком
        4. кольцевой очередью
        1. В чём особенности очереди ?
        1. открыта с обеих сторон ;
        2. открыта с одной стороны на вставку и удаление;
        3. доступен любой элемент.
        1. В чём сосбенности стека ?
        1. открыт с обеих сторон на вставку и удаление;
        2. доступен любой элемент;
        3. открыт с одной стороны на вставку и удаление.
        1. Какую дисциплину обслуживания принято называть FIFO ?

        a) стек; b)очередь; c) дек.

        1. Какая операция читает верхний элемент стека без удаления ?

        a) pop; b) push; b)stackpop. 9. Каково правило выборки элемента из стека ? a)первый элемент; b)последний элемент; c)любой элемент. 10. Как освободить память от удаленного из списка элемента ? a) p=getnode; b) ptr(p)=nil; c) freenode(p); d) p=lst. 11.Как создать новый элемент списка с информационным полем D ? a)p=getnode; b)p=getnode; info(p)=D;c)p=getnode; ptr(D)=lst. 12. Как создать пустой элемент с указателем p? a) p=getnode; b) info(p); c) freenode(p); d) ptr(p)=lst. 13Сколько указателей используется в односвязных списках? a) 1 b) 2; c) сколько угодно. 14.В чём отличительная особенность динамических объектов ? a)порождаются непосредственно перед выполнением программы; b)возникают уже в процессе выполнения программы; c)задаются в процессе выполнения программы. 15. При удалении элемента из кольцевого списка… a)список разрывается; b)в списке образуется дыра; c)список становится короче на один элемент . 16.Для чего используется указатель в кольцевых списках ? a)для ссылки на следующий элемент; b)для запоминания номера сегмента расположения элемента; c)для ссылки на предыдущий элемент ; d)для расположения элемента в списке памяти. 17. Чем отличается кольцевой список от линейного ? a)в кольцевом списке последний элемент является одновременно и первым; b)в кольцевом списке указатель последнего элемента пустой; c)в кольцевых списках последнего элемента нет ; d)в кольцевом списке указатель последнего элемента не пустой.

          1. Элемент дерева, который не ссылается на другие, называется
        1. корнем
        2. листом
        3. узлом
        4. промежуточным

        19.Элемент дерева, на который не ссылаются другие, называется

        1. корнем
        2. листом
        3. узлом
        4. промежуточным

        20. Элемент дерева, который имеет предка и потомков, называется

        1. корнем
        2. листом
        3. узлом
        4. промежуточным
          1. Высотой дерева называется
        1. максимальное количество узлов
        2. максимальное количество связей
        3. максимальное количество листьев
        4. максимальная длина пути от корня до листа

        22. Степенью дерева называется

        1. максимальная степень всех узлов
        2. максимальное количество уровней его узлов
        3. максимальное количество узлов
        4. максимальное количество связей
        5. максимальное количество листьев
        1. Как определяется длина пути дерева
        1. как сумма длин путей всех его узлов
        2. как количество ребер от узла до вершины
        3. как количество ребер от листа до вершины
        4. как максимальное количество ребер
        5. как максимальное количество листьев
        6. как длина самого длинного пути от ближнего узла до какого-либо листа
        1. Дерево называется бинарным, если
        1. количество узлов может быть либо пустым, либо состоять из корня с двумя другими бинарными поддеревьями
        2. каждый узел имеет не менее двух предков
        3. от корня до листа не более двух уровней
        4. от корня до листа не менее двух уровней

        множество узлов, которое

        1. Бинарное дерево можно представить
        1. с помощью указателей
        2. с помощью массивов
        3. с помощью индексов
        4. правильного ответа нет
        1. Какой метод поиска представлен в следующем фрагменте REPEAT I:=I+1 UNTIL (A[I]=X) OR (I=N);
        1. последовательный
        2. двоичный
        3. восходящий
        4. нисходящий
        5. смешанный
        1. Какой метод поиска представлен в следующем фрагменте

        REPEAT K:=(I+J)DIV 2; IF X>A[K] THEN I=K+1 ELSE J:=K-1; UNTIL (A[K]=X) OR (I>J);

        1. последовательный
        2. бинарный
        3. восходящий
        4. нисходящий
        5. смешанный
        1. Реализация поиска в линейном списке выглядит следующим образом
        1. WHILE (P<>NIL) AND (P^.KEY<>X) DO P:=P^.NEXT
        2. WHILE (P<>NIL) DO P:=P^.NEXT
        3. WHILE AND (P^.KEY<>X) DO P:=P^.NEXT
        4. WHILE (P<>NIL) AND (P^.KEY<>X) P:=P^.NEXT
        5. WHILE (P<>NIL P^.KEY<>X) DO P:=P^.NEXT
        1. Как называются предки узла, имеющие уровень на единицу меньше уровня самого узла
        1. детьми
        2. родителями
        3. братьями
        1. В графах общая идея поиска в глубину состоит в следующем:
        1. Поиск начинаем с некоторой фиксированной вершиныv0. Затем выбираем произвольную вершинуu, смежную сv0, и повторяем просмотр отu. Предположим, что находимся в некоторой вершинеv. Если существует ещё не просмотренная вершинаu,u—v, то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной сv, не существует, то возвращаемся в вершину, из которой попали вv, и продолжаем поиск (еслиv=v0, то поиск закончен);
        2. Поиск начинаем с некоторой фиксированной вершины v0. Затем выбираем произвольную вершину u, смежную с v0, и повторяем просмотр от u. Предположим, что находимся в некоторой вершине v. Если существует ещё не просмотренная вершина u, u-v, то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной с v, не существует, то возвращаемся в вершину, из которой попали в v, и продолжаем поиск (если v=u, то поиск закончен);
        3. Поиск начинаем с некоторой фиксированной вершины v0. Затем выбираем произвольную вершину u, смежную с v0, и повторяем просмотр от u. Предположим, что находимся в некоторой вершине v. Если существует ещё не просмотренная вершина u, то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной с v, не существует, то возвращаемся в вершину, из которой попали в v, и продолжаем поиск (если v=v0, то поиск закончен).
        1. Стандартным способом устранения рекурсии при поиске в глубину является использование:
        1. массива;
        2. очереди;
        3. стека;
        4. циклического списка.
        1. При поиске в ширину используется:
        1. массив;
        2. очередь;
        3. стек;
        4. циклический список.
        1. В последовательном файле доступ к информации может быть
        1. только последовательным
        2. как последовательным, так и произвольным
        3. произвольным
        4. прямым
        1. Граф – это
        1. Нелинейная структура данных, реализующая отношение «многие ко многим»;
        2. Линейная структура данных, реализующая отношение «многие ко многим»;
        3. Нелинейная структура данных, реализующая отношение «многие к одному»;
        4. Нелинейная структура данных, реализующая отношение «один ко многим»;
        5. Линейная структура данных, реализующая отношение «один ко многим».
        1. Узлам (или вершинам) графа можно сопоставить:
        1. отношения между объектами;
        2. объекты;
        3. связи
        4. типы отношений
        5. множества
        1. Рёбрам графа можно сопоставить:
        1. связи
        2. типы отношений
        3. множества
        4. объекты;
        5. отношения между объектами;
        1. Граф, содержащий только ребра, называется.
        1. ориентированным
        2. неориентированным
        3. простым
        4. смешанным
        1. Граф, содержащий только дуги, называется.
        1. ориентированным
        2. неориентированным
        3. простым
        4. смешанным
        1. Граф, содержащий дуги и ребра, называется.
        1. ориентированным
        2. неориентированным
        3. простым
        4. смешанным
        1. Есть несколько способов представления графа в ЭВМ. Какой из способов приведенных ниже не относится к ним.
        1. матрица инциденций;
        2. матрица смежности;
        3. список ребер;
        4. массив инцидентности.
        1. Если последовательность вершин v0, v1, …vp определяет путь в графе G, то его длина определяется:
        1. ; правильный ответ
        2. ;
        3. ;
        4. .
        1. Каким образом осуществляется алгоритм нахождения кратчайшего пути от вершины s до вершины t
        1. нахождение пути от вершиныsдо всех вершин графа
        2. нахождение пути от вершины s до заданной вершины графа
        3. нахождение кратчайших путей от вершины s до всех вершин графа
        4. нахождение кратчайшего пути от вершины s до вершины t графа
        5. нахождение всех путей от каждой вершины до всех вершин графа
        1. Суть алгоритма Дейкстры — нахождения кратчайшего пути от вершины s до вершины t заключается
        1. вычислении верхних ограниченийd[v] в матрице весов дугa[u,v] дляu,v
        2. вычислении верхних ограничений d[v]
        3. вычислении верхних ограничений в матрице весов дуг a[u,v]
        4. вычислении нижних ограничений d[v] в матрице весов дуг a[u,v] для u, v
        1. Улучшение d[v] в алгоритме Форда- Беллмана производится по формуле
        1. D[v]:=D[u]+a[u,v]
        2. D[v]:=D[u]-a[u,v]
        3. D[v]:=a[u,v]
        4. D[v]:=D[u]
        1. Строка представляет собой
        1. конечную линейно-упорядоченную последовательность простых данных символьного типа
        2. конечную последовательность простых данных символьного типа
        3. конечную последовательность простых данных
        4. последовательность данных символьного типа
        1. Граф, содержащий только ребра, называется
        1. ориентированным
        2. неориентированным
        3. простым
        4. связным
        1. Граф, содержащий только дуги, называется
        1. ориентированным
        2. неориентированным
        3. простым
        4. связным
        1. Граф, содержащий ребра и дуги, называется
        1. неориентированным
        2. простым
        3. смешанным
        4. связным

        16.02.2016 642.56 Кб 50 Тесты ЭиМОТ 6.doc

        16.02.2016 225.28 Кб 42 Тесты ЭиМОт 8.doc

        16.02.2016 227.84 Кб 37 Тесты ЭиМОТ 9.doc

        16.02.2016 211.46 Кб 345 Тесты ЭТ 1.doc

        16.02.2016 630.27 Кб 101 Тесты ЭТ 2.doc

        16.02.2016 99.33 Кб 403 тесты2.doc

        24.11.2019 474.11 Кб 46 Технология циркония и гафния. Акимов, Григорьев. doc

        06.09.2019 667.65 Кб 5 ТИ.doc

        16.02.2016 51.2 Кб 45 ТМО — Заочники_Тесты.doc

        16.02.2016 1.15 Mб 418 ТМО — учебное пособие для заочников.doc

        22.11.2018 2.7 Mб 112 Токовые дифференциальные реле серий РНТ-560 и Д. doc

        Ограничение

        Для продолжения скачивания необходимо пройти капчу:

        Клуб студентов «Технарь». Уникальный сайт с дипломами и курсовыми для технарей.

        1. Структура данных представляет собой
        a) набор правил и ограничений, определяющих связи между отдельными элементами и группами данных
        b) набор правил и ограничений, определяющих связи между отдельными элементами данных
        c) набор правил и ограничений, определяющих связи между отдельными группами данных
        d) некоторую иерархию данных

        2. Линейный список, в котором доступен только последний элемент, называется
        a) стеком
        b) очередью
        c) деком
        d) массивом
        e) кольцом

        3. Структура данных, работа с элементами которой организована по принципу FIFO (первый пришел — первый ушел) это –
        a) Стек
        b) Дек
        c) Очередь
        d) Список

        4. Линейный последовательный список, в котором включение исключение элементов возможно с обоих концов, называется
        a) стеком
        b) очередью
        c) деком
        d) кольцевой очередью

        5. В чём особенности очереди?
        a) открыта с обеих сторон;
        b) открыта с одной стороны на вставку и удаление;
        c) доступен любой элемент.

        6. В чём особенности стека?
        a) открыт с обеих сторон на вставку и удаление;
        b) доступен любой элемент;
        c) открыт с одной стороны на вставку и удаление.

        7. Какую дисциплину обслуживания принято называть FIFO?
        a) стек;
        b) очередь;
        c) дек.

        8. Какая операция читает верхний элемент стека?
        a) exit;
        b) push;
        c) pop.

        9. Каково правило выборки элемента из стека?
        a) первый элемент;
        b) последний элемент;
        c) любой элемент.

        10. Как освободить память от удаленного из списка элемента?
        a) p=getnode;
        b) ptr(p) =nil;
        c) freenode(p);
        d) p=lst.

        11.Как создать новый элемент списка с информационным полем D?
        a) p=getnode;
        b) p=getnode; info(p) =D;
        c) p=getnode; ptr=lst.

        12. Как создать пустой элемент с указателем p?
        a) p=getnode;
        b) info(p);
        c) freenode(p);
        d) ptr(p) =lst.

        13Сколько указателей используется в конструкции узла односвязного списка?
        a) 1
        b) 2;
        c) сколько угодно.

        14.В чём отличительная особенность динамических объектов?
        a) порождаются непосредственно перед выполнением программы;
        b) возникают уже в процессе выполнения программы;
        c) задаются в процессе выполнения программы.

        15. При удалении элемента из кольцевого списка…
        a) список разрывается;
        b) в списке образуется дыра;
        c) список становится короче на один элемент.

        16.Для чего используется указатель в кольцевых списках?
        a) для ссылки на следующий элемент;
        b) для запоминания номера сегмента расположения элемента;
        c) для ссылки на предыдущий элемент;
        d) для расположения элемента в списке памяти.

        17. Чем отличается кольцевой список от линейного?
        a) в кольцевом списке последний элемент является одновременно и первым;
        b) в кольцевом списке указатель последнего элемента пустой;
        c) в кольцевых списках последнего элемента нет;
        d) в кольцевом списке указатель последнего элемента не пустой.

        18. Сколько указателей используется при программировании односвязного кольцевого списка?
        a) 1;
        b) 2;
        c) сколько угодно.

        19. В каких направлениях можно перемещаться в кольцевом двунаправленном списке?
        a) в обоих;
        b) влево;
        c) вправо.

        20. С помощью какой структуры данных наиболее рационально реализовать очередь?
        a) стек;
        b) список;
        c) дек.

        21. В памяти ЭВМ бинарное дерево удобно представлять в виде:
        a) связанных линейных списков;
        a) массивов;
        b) связанных нелинейных списков.

        22. Элемент t, на который нет ссылок:
        a) корнем;
        b) промежуточным;
        c) терминальным (лист).

        23. Дерево называется полным бинарным, если степень исходов вершин равна:
        a) 1 или 2;
        b) 2 или 0;
        c) 2;
        d) М или 0;
        e) M.

        24. Односвязный список, последний элемент которого ссылается на головной, называется
        a) стеком
        b) очередью
        c) кольцом
        d) деком
        e) цепью

        25. Чем отличается кольцевой список от линейного?
        a) в кольцевом списке последний элемент ссылается на первый;
        b) в кольцевом списке указатель последнего элемента пустой;
        c) в кольцевых списках нет первого и последнего элемента;

        26. Если символы \’D\’, \’C\’, \’B\’, \’A\’ помещены в очередь по порядку и затем будут по одному удалены, в каком порядке это произойдет?
        a) DCBA;
        b) DCAB;
        c) ABCD;
        d) ABDC.

        27. Структура данных, работа с элементами которой организована по принципу LIFO это –
        а) Стек
        б) Дек
        в) Очередь
        г) Список

        28. Что делает функция с параметром lst, тело которой приведено ниже?
        list * p = lst;
        cout while (p != NULL)
        cout p = (*p).next;
        >
        cout a) печатает название списка;
        b) печатает данные списка;
        c) печатает указатели на элементы списка;
        d) переходит он начала списка к концу.

        29. Какой вид списка может быть реализован посредством следующей структуры?
        struct list int info;
        list *next;
        >;
        a) односвязный;
        b) двухсвязный;
        c) трехсвязный;
        d) бессвязный;
        e) кольцевой.

        30. Как корректно вывести все данные, содержащиеся в стеке?
        a) пройти по элементам стека и вывести их значения;
        b) последовательно извлечь все данные без разрушения стека;
        c) последовательно извлечь все данные, разрушив стек полностью;
        d) необходимо извлекать элементы, выводить их и снова добавлять в стек.

        31. Как линейный односвязный список превратить в кольцевой?
        a) инициализировать указатель последнего элемента ссылкой на первый элемент;
        b) инициализировать указатель первого элемента ссылкой на последний элемент;
        c) скопировать указатель первого элемента в указатель последнего элемента.

        32. В какую сторону правильно перемещаться в кольцевом двухсвязном списке?
        a) против часовой стрелки;
        b) по часовой стрелке;
        c) от головы списка вправо;
        d) от головы списка влево;
        e) вправо и влево;
        f) верны все вышеперечисленные ответы.

        33. Что такое список?
        a) упорядоченное множество элементов одного типа;
        b) упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения;
        c) упорядоченное множество, состоящее из постоянного числа связанных между собой элементов.

        34. Что есть длина списка?
        a) нет такого понятия;
        b) число элементов, содержащихся в списке;
        c) числу элементов, содержащихся в списке, за вычетом головного элемента.

        35. В каком из видов списка нет головного элемента?
        a) в односвязном;
        b) в двухсвязном;
        c) в кольцевом;
        d) ни один из вышеуказанных ответов не верен.

        36. При обходе дерева…
        a) каждый узел посещается только один раз;
        b) каждый узел посещается произвольное число раз;
        c) все узлы должны быть посещены;
        d) все узлы, за исключением листьев, должны быть посещены.

        37. Какая структура данных соответствует принципу: LIFO?
        a) Очередь
        b) Стек
        c) B-дерево
        d) Односвязные циклические списки

        38. При обходе дерева слева направо получаем последовательность…
        a) отсортированную по убыванию;
        b) неотсортированную;
        c) отсортированную по возрастанию.

        39. При обходе дерева слева направо его элемент заносится в массив…
        a) при втором заходе в элемент;
        b) при первом заходе в элемент;
        c) при третьем заходе в элемент.

        40. Где эффективен линейный поиск?
        a) в списке;
        b) в массиве;
        c) в массиве и в списке.

        41. Какой поиск эффективнее?
        a) линейный;
        b) бинарный;
        c) без разницы.

        42. В чём суть бинарного поиска?
        a) нахождение элемента массива x путём деления массива пополам каждый раз, пока элемент не найден;
        b) нахождение элемента x путём обхода массива;
        c) нахождение элемента массива х путём деления массива.

        43. Как расположены элементы в массиве бинарного поиска?
        a) по возрастанию;
        b) хаотично;
        c) по убыванию.

        44. В чём суть линейного поиска?
        a) производится последовательный просмотр от начала до конца и обратно через 2 элемента;
        b) производится последовательный просмотр элементов от середины таблицы;
        c) производится последовательный просмотр каждого элемента.

        45. Где наиболее эффективен метод транспозиций?
        d) в массивах и в списках;
        e) только в массивах;
        f) только в списках.

        46. В чём суть метода транспозиции?
        a) перестановка местами соседних элементов;
        b) нахождение одинаковых элементов;
        c) перестановка найденного элемента на одну позицию в сторону начала списка.

        47. Что такое уникальный ключ?
        a) если разность значений двух данных равна ключу;
        b) если сумма значений двух данных равна ключу;
        c) если в таблице есть только одно данное с таким ключом.

        48. В чём состоит назначение поиска?
        a) среди массива данных найти те данные, которые соответствуют заданному аргументу;
        b) определить, что данных в массиве нет;
        c) с помощью данных найти аргумент.

        49. Элемент дерева, который не ссылается на другие, называется
        a) корнем
        b) листом
        c) узлом
        d) промежуточным

        50. Элемент дерева, на который не ссылаются другие, называется
        a) корнем
        b) листом
        c) узлом
        d) промежуточным

        51. Элемент дерева, который имеет предка и потомков, называется
        a) корнем
        b) листом
        c) узлом
        d) промежуточным

        52. Высотой дерева называется
        a) максимальное количество узлов
        b) максимальное количество связей
        c) максимальное количество листьев
        d) максимальная длина пути от корня до листа

        53. Степенью дерева называется
        a) максимальная степень всех узлов
        b) максимальное количество уровней его узлов
        c) максимальное количество узлов
        d) максимальное количество связей
        e) максимальное количество листьев

        54. Как определяется длина пути дерева
        a) как сумма длин путей всех его узлов
        b) как количество ребер от узла до вершины
        c) как количество ребер от листа до вершины
        d) как максимальное количество ребер
        e) как максимальное количество листьев
        f) как длина самого длинного пути от ближнего узла до какого-либо листа

        55. Дерево называется бинарным, если
        a) количество узлов может быть либо пустым, либо состоять из корня с двумя другими бинарными поддеревьями
        b) каждый узел имеет не менее двух предков
        c) от корня до листа не более двух уровней
        d) от корня до листа не менее двух уровней
        e) множество узлов, которое

        56. Бинарное дерево можно представить
        a) с помощью указателей
        b) с помощью массивов
        c) с помощью индексов
        d) правильного ответа нет

        57. Какой метод поиска представлен в следующем фрагменте
        do I:=I+1 while ((A=X) || (I=N));
        a) последовательный
        b) двоичный
        c) восходящий
        d) нисходящий
        e) смешанный

        58. Какой метод поиска представлен в следующем фрагменте
        do K=(I+J) % 2; IF (X>A[K]) I=K+1 ELSE J=K-1;
        while ((A[K]=X) || (I>J));
        a) последовательный
        b) бинарный
        c) восходящий
        d) нисходящий
        e) смешанный

        59. Реализация поиска в линейном списке выглядит следующим образом
        a) WHILE ((P<>NIL) && (P.KEY<>X)) P=P.NEXT;
        b) WHILE (P<>NIL) P=P.NEXT;
        c) WHILE && (P.KEY<>X) P=P.NEXT;
        d) WHILE (P<>NIL) && (P.KEY<>X) P=P.NEXT;
        e) WHILE (P<>NIL P.KEY<>X) P=P.NEXT

        60. Как называются предки узла, имеющие уровень на единицу меньше уровня самого узла
        a) детьми
        b) родителями
        c) братьями

        61. В графах общая идея поиска в глубину состоит в следующем:
        a) Поиск начинаем с некоторой фиксированной вершины v0. Затем выбираем произвольную вершину u, смежную с v0, и повторяем просмотр от u. Предположим, что находимся в некоторой вершине v. Если существует ещё не просмотренная вершина u, u-v, то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной с v, не существует, то возвращаемся в вершину, из которой попали в v, и продолжаем поиск (если v=v0, то поиск закончен);
        b) Поиск начинаем с некоторой фиксированной вершины v0. Затем выбираем произвольную вершину u, смежную с v0, и повторяем просмотр от u. Предположим, что находимся в некоторой вершине v. Если существует ещё не просмотренная вершина u, u-v, то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной с v, не существует, то возвращаемся в вершину, из которой попали в v, и продолжаем поиск (если v=u, то поиск закончен);
        c) Поиск начинаем с некоторой фиксированной вершины v0. Затем выбираем произвольную вершину u, смежную с v0, и повторяем просмотр от u. Предположим, что находимся в некоторой вершине v. Если существует ещё не просмотренная вершина u, то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной с v, не существует, то возвращаемся в вершину, из которой попали в v, и продолжаем поиск (если v=v0, то поиск закончен).

        62. Стандартным способом устранения рекурсии при поиске в глубину является использование:
        a) массива;
        b) очереди;
        c) стека;
        d) циклического списка.

        63. При поиске в ширину используется:
        a) массив;
        b) очередь;
        c) стек;
        d) циклический список.

        64. В последовательном файле доступ к информации может быть
        a) только последовательным
        b) как последовательным, так и произвольным
        c) произвольным
        d) прямым

        65. Граф – это
        a) Нелинейная структура данных, реализующая отношение «многие ко многим»;
        b) Линейная структура данных, реализующая отношение «многие ко многим»;
        c) Нелинейная структура данных, реализующая отношение «многие к одному»;
        d) Нелинейная структура данных, реализующая отношение «один ко многим»;
        e) Линейная структура данных, реализующая отношение «один ко многим».

        66. Узлам (или вершинам) графа можно сопоставить:
        a) отношения между объектами;
        b) объекты;
        c) связи
        d) типы отношений
        e) множества

        67. Рёбрам графа можно сопоставить:
        a) связи
        b) типы отношений
        c) множества
        d) объекты;
        e) отношения между объектами;

        68. Граф, содержащий только ребра, называется.
        a) ориентированным
        b) неориентированным
        c) простым
        d) смешанным

        69. Граф, содержащий только дуги, называется.
        a) ориентированным
        b) неориентированным
        c) простым
        d) смешанным

        70. Граф, содержащий дуги и ребра, называется.
        a) ориентированным
        b) неориентированным
        c) простым
        d) смешанным

        71. Есть несколько способов представления графа в ЭВМ. Какой из способов приведенных ниже не относится к ним.
        a) матрица инциденций;
        b) матрица смежности;
        c) список ребер;
        d) массив инцидентности.

        72. Если последовательность вершин v0, v1, …vp определяет путь в графе G, то его длина определяется:
        a) ;
        b) ;
        c) ;
        d) .

        73. Каким образом осуществляется алгоритм нахождения кратчайшего пути от вершины s до вершины t
        a) нахождение пути от вершины s до всех вершин графа
        b) нахождение пути от вершины s до заданной вершины графа
        c) нахождение кратчайших путей от вершины s до всех вершин графа
        d) нахождение кратчайшего пути от вершины s до вершины t графа
        e) нахождение всех путей от каждой вершины до всех вершин графа

        74. Суть алгоритма Дейкстры — нахождения кратчайшего пути от вершины s до вершины t заключается
        a) вычислении верхних ограничений d[v] в матрице весов дуг a[u,v] для u, v
        b) вычислении верхних ограничений d[v]
        c) вычислении верхних ограничений в матрице весов дуг a[u,v]
        d) вычислении нижних ограничений d[v] в матрице весов дуг a[u,v] для u, v

        75. Улучшение d[v] в алгоритме Форда- Беллмана производится по формуле
        a) D[v]:=D +a[u,v]
        b) D[v]:=D -a[u,v]
        c) D[v]:=a[u,v]
        d) D[v]:=D

        76. Строка представляет собой
        a) конечную линейно-упорядоченную последовательность простых данных символьного типа
        b) конечную последовательность простых данных символьного типа
        c) конечную последовательность простых данных
        d) последовательность данных символьного типа

        77. Граф, содержащий только ребра, называется
        a) ориентированным
        b) неориентированным
        c) простым
        d) связным

        78. Граф, содержащий только дуги, называется
        a) ориентированным
        b) неориентированным
        c) простым
        d) связным

        79. Граф, содержащий ребра и дуги, называется
        a) неориентированным
        b) простым
        c) смешанным
        d) связным

        80. Путь(цикл), который содержит все ребра графа только один раз, называется
        a) Эйлеровым
        b) Гамильтоновым
        c) декартовым
        d) замкнутым

        81. Требуется структура данных для хранения только различных элементов (без дубликатов), при этом она должна поддерживать операции добавления и удаления элементов. Какая структура данных из перечисленных лучше всего подойдет для этих целей:
        a) список
        b) очередь
        c) множество
        d) хеш-таблица
        e) стек

        82. Какая из следующих строк кода удалит два последовательных элемента связного линейного списка (с более чем двумя элементами) после элемента X? (Здесь \’LINK[X]\’ означает поле адреса элемента X)
        a) LINK[X]:=LINK[LINK[X]]
        b) LINK[X]:=LINK[LINK[LINK[X]]]
        c) LINK[LINK[X]]:=X
        d) X:=LINK[LINK[X]]

        83. Какая структура данных соответствует принципу: FIFO?
        a) Очередь
        b) Стек
        c) B-дерево
        d) Односвязные циклические списки

        84. Какие из перечисленных операций для односвязного списка всегда изменяют состояние начального элемента?
        a) Удаление последнего элемента
        b) Вставка после первого элемента
        c) Вставка после последнего элемента
        d) Удаление первого элемента

        85. Если куча реализована с использованием одномерного массива data с n элементами (n > 0), где будет находится элемент с наибольшим значением?
        a) data[0]
        b) data[2*n + 1]
        c) data[n]
        d) data[n-1]

        86. В какой структуре данных вставка и удаление происходят на одном конце?
        a) Дерево
        b) Связный список стеков
        c) Связный список
        d) Стек

        87. Какие из указанных структур данных могут хранить в себе одновременно элементы различных (произвольных) типов?
        a) Массив
        b) Куча
        c) Объединение

        88. Минимальное количество обменов требуемое для свертки массива [89,19,14,75,17,12,10,2,5,7,11,6,9,70] в кучу с максимальным элементом в корне:
        a) 0
        b) 1
        c) 2
        d) 3

        89. Какие операции из перечисленных являются стандартными для структуры данных стек?
        a) push, delete
        b) push, pop
        c) put, extract
        d) insert, pop

        90. data — циклический массив из N элементов и last — индекс в этом массиве, какая формула индекса следующего после last элемента?
        a) (last % 1) + N 162 / 2646
        b) last + (1 % N) 237 / 2646
        c) (last + 1) % N 1964 / 2646
        d) last % (1 + N) 254 / 2646

        91. Какой тип списка предпочтительнее всего использовать если нужно получить элемент, находящийся на позиции n?
        a) Односвязный список
        b) Двусвязный список
        c) Список, реализованный как массив
        d) Двусвязный и односвязный списки одинаково подходят

        92. По какому принципу работает Стек?
        a) LIFO
        b) FIFO
        c) OIFO
        d) Как в очереди

        93. Какими свойствами обладает AVL-дерево?
        a) Сбалансировано по высоте
        b) Высота двух поддеревьев различается не более чем на 1
        c) Значения ключей узлов дерева распределены по нему в произвольном порядке.
        d) Оба поддерева — левое и правое, являются двоичными деревьями поиска
        e) Является двоичным деревом поиска

        94. Дано AVL-дерево с балансом узла — 1. Какие из следующих утверждений корректны?
        a) Левое поддерево больше чем правое
        b) AVL-дерева с балансом -1 не существует
        c) Дерево сбалансировано по высоте
        d) Правое поддерево больше чем левое

        95. Термин, которым называют ситуацию, когда совершается попытка удаления данных из пустой структуры называется _____.
        a) переполнение (Overflow)
        b) Сборка мусора (garbage collection)
        c) опустошение
        d) null

        96. В связном представлении разреженной матрицы, голова списка столбцов хранит.
        указатель на голову следующего столбца
        a) номер столбца
        b) указатель на первый узел списка столбцов
        c) все вышеуказанное

        97. Какая структура данных позволяет производить вставку и удаление элемента с обоих концов?
        a) дек
        b) стек
        c) очередь

        98. Каких методов в представленном шаблоне класса не существует для бинарного дерева поиска?
        Template class BinaryTreeSearch
        <
        node* head;
        public:
        void insert_node(node* currentNod; //1
        void left_rotate(node* rotateNod; //2
        void right_rotate(node* rotateNod; //3
        void delete_node(node* deleteNod; //4
        void inorder_tree_walk(node* walkNod; //5
        node* tree_search(X dat; //6
        >;
        a) все существуют
        b) 2, 3
        c) 5, 6
        d) 5
        e) 6
        f) 2, 3, 5, 6

        99. Какое положение будет верно относительно B-дерева?
        a) Все записи узла больше чем или равняются записям узлов-потомков
        b) Все нелистовые узлы имеют одинаковое число потомков
        c) Все узлы имеют одинаковое количество записей
        d) Все листья находятся на нижнем уровне

        100. Какие из перечисленных операций более затратны (по времени) для реализации списка через массив относительно реализации через динамически создаваемый связный список?
        a) Обход
        b) Удаление
        c) Поиск
        d) Вставка

        Комментарии: Зачет,год сдачи 2020.
        Можем помочь с другими вариантами и работами,пишите. Сессия под ключ. sibguti_do@mail.ru
        https://vk.com/club86603542

        Размер файла: 190 Кбайт
        Фаил: (.doc)

        Скачано: 2 Коментариев: 0

        Элемент дерева на который не ссылаются другие называется

        По книге Laszlo
        «Вычислительная геометрия и компьютерная графика на С++»

        Двоичные деревья представляют эффективный способ поиска. Двоичное дерево представляет собой структурированную коллекцию узлов. Коллекция может быть пустой и в этом случае мы имеем пустое двоичное дерево. Если коллекция непуста, то она подразделяется на три раздельных семейства узлов: корневой узел n (или просто корень), двоичное дерево, называемое левым поддеревом для n, и двоичное дерево, называемое правым поддеревом для n. На рис. 1а узел, обозначенный буквой А, является корневым, узел В называется левым потомком А и является корнем левого поддерева А, узел С называется правым потомком А и является корнем правого поддерева А.

        Рис. 1: Двоичное дерево с показанными внешними узллами (а) и без них (б)

        Двоичное дерево на рис. 1а состоит из четырех внутренних узлов (обозначенных на рис. кружками) и пяти внешних (конечных) узлов (обозначены квадратами). Размер двоичного дерева определяется числом содержащихся в нем внутренних узлов. Внешние узлы соответствуют пустым двоичным деревьям. Например, левый потомок узла В — непустой (содержит узел D), тогда как правый потомок узла В — пустое дерево. В некоторых случаях внешние узлы обозначаются каким-либо образом, в других — на них совсем не ссылаются и они считаются пустыми двоичными деревьями (на рис. 16 внешние узлы не показаны).

        Основанная на генеалогии метафора дает удобный способ обозначения узлов внутри двоичного дерева. Узел р является родителем (или предком) узла n, если n — потомок узла р. Два узла являются братьями, если они принадлежат одному и тому же родителю. Для двух заданных узлов n1 и nk таких, что узел nk принадлежит поддереву с корнем в узле n1, говорят, что узел nk является потомком узла n1, а узел n1 — предком узла nk. Существует уникальный путь от узла n1 вниз к каждому из потомков nk, a именно: последовательность узлов n1 и n2. nk такая, что узел ni является родителем узла ni+1 для i = 1, 2. k-1. Длина пути равна числу ребер (k-1), содержащихся в нем. Например, на рис. 1а уникальный путь от узла А к узлу D состоит из последовательности А, В, D и имеет длину 2.

        Глубина узла n определяется рекурсивно:

        < 0 если n — корневой узел
        глубина (n) =
        < 1 + глубина (родителя (n)) в противном случае

        Глубина узла равна длине уникального пути от корня к узлу. На рис. 1а узел А имеет глубину 0, а узел D имеет глубину, равную 2.

        Высота узла n также определяется рекурсивно:

        < 0 если n — внешний узел
        высота (n) =
        < 1 + max( высота(лев(n)), высота(прав(n)) ) в противном случае

        где через лев(n) обозначен левый потомок узла n и через прав(n) — правый потомок узла n. Высота узла n равна длине самого длинного пути от узла n вниз до внешнего узла поддерева n. Высота двоичного дерева определяется как высота его корневого узла. Например, двоичное дерево на рис. 1а имеет высоту 3, а узел D имеет высоту 1.

        При реализации двоичных деревьев, основанной на точечном представлении, узлы являются объектами класса TreeNode.

        template class TreeNode < protected: TreeNode *_lchild; TreeNode *_rchild; Т val; public: TreeNode(T); virtual ~TreeNode(void); friend class SearchTree; // возможные пополнения friend class BraidedSearchTree; // структуры >;

        Элементы данных _lchild и _rchild обозначают связи текущего узла с левым и правым потомками соответственно, а элемент данных val содержит сам элемент.

        Конструктор класса формирует двоичное дерево единичного размера — единственный внутренний узел имеет два пустых потомка, каждое из которых представлено нулем NULL:

        template TreeNode::TreeNode(T v) : val(v), _lchild(NULL), _rchild (NULL)

        Деструктор ~TreeNode рекурсивно удаляет оба потомка текущего узла (если они существуют) перед уничтожением самого текущего узла:

        template TreeNode::~TreeNode(void)

        Основное назначение двоичных деревьев заключается в повышении эффективности поиска. При поиске выполняются такие операции, как нахождение заданного элемента из набора различных элементов, определение наибольшего или наименьшего элемента в наборе, фиксация факта, что набор содержит заданный элемент. Для эффективного поиска внутри двоичного дерева его элементы должны быть организованы соответствующим образом. Например, двоичное дерево будет называться двоичным деревом поиска, если его элементы расположены так, что для каждого элемента n все элементы в левом поддереве n будут меньше, чем n, а все элементы в правом поддереве — будут больше, чем n. На рис. 2 изображены три двоичных дерева поиска, каждое из которых содержит один и тот же набор целочисленных элементов.

        Рис. 2: Три двоичных дерева поиска с одним и тем же набором элементов

        В общем случае существует огромное число двоичных деревьев поиска (различной формы) для любого заданного набора элементов.

        Предполагается, что элементы располагаются в линейном порядке и, следовательно, любые два элемента можно сравнить между собой. Примерами линейного порядка могут служить ряды целых или вещественных чисел в порядке возрастания, а также слов или строк символов, расположенных в лексикографическом (алфавитном, или словарном) порядке. Поиск осуществляется путем обращения к функции сравнения для сопоставления любых двух элементов относительно их линейного порядка. В нашей версии деревьев поиска действие функции сравнения ограничено только явно определенными объектами деревьев поиска.

        Также очень полезны функции для обращения к элементам дерева поиска и воздействия на них. Такие функции обращения могут быть полезны для вывода на печать, редактирования и доступа к элементу или воздействия на него каким-либо иным образом. Функции обращения не принадлежат деревьям поиска, к элементам одного и того же дерева поиска могут быть применены различные функции обращения.

        Определим шаблон нового класса SearchTree для представления двоичного дерева поиска. Класс содержит элемент данных root, который указывает на корень двоичного дерева поиска (объект класса TreeNode) и элемент данных cmp, который указывает на функцию сравнения.

        template class SearchTree < private: TreeNode *root; int (*) (T,T) cmp; TreeNode*_findMin(TreeNode *); void _remove(T, TreeNode * &); void _inorder(TreeNode *, void (*) (T) ); public: SearchTree (int(*) (Т, Т) ); ~SearchTree (void); int isEmpty (void); Т find(T); Т findMin(void); void inorder (void(*) (T) ); void insert(T); void remove(T); T removeMin (void); >;

        Для упрощения реализации предположим, что элементами в дереве поиска являются указатели на объект заданного типа, когда шаблон класса SearchTree используется для создания действительного класса. Параметр Т передается в виде типа указателя.

        Конструкторы и деструкторы

        Конструктор SearchTree инициализирует элементы данных cmp для функции сравнения и root для пустого дерева поиска:

        template SearchTree::SearchTree (int (*с) (Т, Т) ) : cmp(с), root (NULL)

        Дерево поиска пусто только, если в элементе данных root содержится нуль (NULL) вместо разрешенного указателя:

        template int SearchTree::isEmpty (void)

        Деструктор удаляет все дерево путем обращения к деструктору корня:

        template SearchTree::~SearchTree (void)

        Поиск

        Чтобы найти заданный элемент val, мы начинаем с корня и затем следуем вдоль ломаной линии уникального пути вниз до узла, содержащего val. В каждом узле n вдоль этого пути используем функцию сравнения для данного дерева на предмет сравнения val с элементом n->val, записанном в n. Если val меньше, чем n->val, то поиск продолжается, начиная с левого потомка узла n, если val больше, чем n->val, то поиск продолжается, начиная с правого потомка n, в противном случае возвращается значение n->val (и задача решена). Путь от корневого узла вниз до val называется путем поиска для val.

        Этот алгоритм поиска реализуется в компонентной функции find, которая возвращает обнаруженный ею указатель на элемент или NULL, если такой элемент не существует в дереве поиска.

        template T SearchTree::find (T val) < TreeNode *n = root; while (n) < int result = (*cmp) (val, n->val); if (result < 0) n = n->_lchild; else if (result > 0) n = n->_rchild; else return n->val; > return NULL; >

        Этот алгоритм поиска можно сравнить с турниром, в котором участвуют некоторые кандидаты. В начале, когда мы начинаем с корня, в состав кандидатов входят все элементы в дереве поиска. В общем случае для каждого узла n в состав кандидатов входят все потомки n. На каждом этапе производится сравнение val с n->val. Если val меньше, чем n->val, то состав кандидатов сужается до элементов, находящихся в левом поддереве, а элементы в правом поддереве n, как и сам элемент n->val, исключаются из соревнования. Аналогичным образом, если val больше, чем n->val, то состав кандидатов сужается до правого поддерева n. Процесс продолжается до тех пор, пока не будет обнаружен элемент val или не останется ни одного кандидата, что означает, что элемент val не существует в дереве поиска.

        Для нахождения наименьшего элемента мы начинаем с корня и прослеживаем связи с левым потомком до тех пор, пока не достигнем узла n, левый потомок которого пуст — это означает, что в узле n содержится наименьший элемент. Этот процесс также можно уподобить турниру. Для каждого узла n состав кандидатов определяется потомками узла n. На каждом шаге из состава кандидатов удаляются те элементы, которые больше или равны n->val и левый потомок n будет теперь выступать в качестве нового n. Процесс продолжается до тех пор, пока не будет достигнут некоторый узел n с пустым левым потомком и, полагая, что не осталось кандидатов меньше, чем n->val, и будет возвращено значение n->val.

        Компонентная функция findMin возвращает наименьший элемент в данном дереве поиска, в ней происходит обращение к компонентной функции _findMin, которая реализует описанный ранее алгоритм поиска, начиная с узла n :

        template T SearchTree::findMin (void) < TreeNode*n = _findMin (root); return (n ? n->val : NULL); > template TreeNode *SearchTree::_findMin (TreeNode *n) < if (n == NULL) return NULL; while (n->_lchild) n = n->_lchild; return n; >

        Наибольший элемент в дереве поиска может быть найден аналогично, только отслеживаются связи с правым потомком вместо левого.

        Симметричный обход

        Обход двоичного дерева — это процесс, при котором каждый узел посещается точно только один раз. Компонентная функция inorder выполняет специальную форму обхода, известную как симметричный обход. Стратегия заключается сначала в симметричном обходе левого поддерева, затем посещения корня и потом в симметричном обходе правого поддерева. Узел посещается путем применения функции обращения к элементу, записанному в узле.

        Компонентная функция inorder служит в качестве ведущей функции. Она обращается к собственной компонентной функции _inorder, которая выполняет симметричный обход от узла n и применяет функцию visit к каждому достигнутому узлу.

        template void SearchTree::inorder (void (*visit) (Т) ) < _inorder (root, visit); >template void SearchTree::inorder (TreeNode *n, void(*visit) (T) < if (n) < _inorder (n->_lchild, visit); (*visit) (n->val); _inorder (n->_rchild, visit); > >

        При симметричном обходе каждого из двоичных деревьев поиска, показанных на рис. 2, узлы посещаются в возрастающем порядке: 2, 3, 5, 7, 8. Конечно, при симметричном обходе любого двоичного дерева поиска все его элементы посещаются в возрастающем порядке. Чтобы выяснить, почему это так, заметим, что при выполнении симметричного обхода в некотором узле n элементы меньше, чем n->val посещаются до n, поскольку они принадлежат к левому поддереву n, а элементы больше, чем n->val посещаются после n, поскольку они принадлежат правому поддереву n. Следовательно, узел n посещается в правильной последовательности. Поскольку n — произвольный узел, то это же правило соблюдается для каждого узла.

        Компонентная функция inorder обеспечивает способ перечисления элементов двоичного дерева поиска в отсортированном порядке. Например, если а является деревом поиска SearchTree для строк, то эти строки можем напечатать в лексикографическом порядке одной командой а.inorder(printstring). Для этого функция обращения printstring может быть определена как:

        void printstring(char *s)

        При симметричном обходе двоичного дерева узел, посещаемый после некоторого узла n, называется последователем узла n, а узел, посещаемый непосредственно перед n, называется предшественником узла n. Не существует никакого предшественника для первого посещаемого узла и никакого последователя для последнего посещаемого узла (в двоичном дереве поиска эти узлы содержат наименьший и наибольший элемент соответственно).

        Включение элементов

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

        Компонентная функция insert включает элемент val в это двоичное дерево поиска:

        Рис. 3: Включение элемента в двоичное дерево поиска

        template void SearchTree::insert(T val) < if (root == NULL) < root = new TreeNode(val); return; > else < int result; TreeNode*p, *n = root; while (n) < p = n; result = (*cmp) (val, p->val); if (result < 0) n = p->_lchild; else if (result > 0) n = p->_rchild; else return; > if (result < 0) p->_lchild = new TreeNode(val); else p-> rchild = new TreeNode(val); > >

        Удаление элементов

        Удаление элемента из двоичного дерева поиска гораздо сложнее, чем включение, поскольку может быть значительно изменена форма дерева. Удаение узла, у которого есть не более чем один непустой потомок, является равнительно простой задачей — устанавливается ссылка от предка узла на потомок. Однако ситуация становится гораздо сложнее, если у подлежащего удалению узла есть два непустых потомка: предок узла может быть связан с одним из потомков, а что делать с другим? Решение может заключаться не в удалении узла из дерева, а скорее в замене элемента, содержащегося в нем, на последователя этого элемента, а затем в удалении узла, содержащего этот последователь.

        Рис. 4: Три ситуации, возникающие при удалении элемента из двоичного дерева поиска

        Чтобы удалить элемент из дерева поиска, вначале мы отслеживаем путь поиска элемента, начиная с корня и вниз до узла n, содержащего элемент. В этот момент могут возникнуть три ситуации, показанные на рис. 4:

        1. Узел n имеет пустой левый потомок. В этом случае ссылка на n (записанная в предке n, если он есть) заменяется на ссылку на правого потомка n.
        2. У узла n есть непустой левый потомок, но правый потомок пустой. В этом случае ссылка вниз на n заменяется ссылкой на левый потомок узла n.
        3. Узел n имеет два непустых потомка. Найдем последователя для n (назовем его m), скопируем данные, хранящиеся в m, в узел n и затем рекурсивно удалим узел m из дерева поиска.

        Очень важно проследить, как будет выглядеть результирующее двоичное дерево поиска в каждом случае. Рассмотрим случай 1. Если подлежащий удалению узел n, является левым потомком, то элементы, относящиеся к правому поддереву n будут меньше, чем у узла р, предка узла n. При удалении узла n его правое поддерево связывается с узлом р и элементы, хранящиеся в новом левом поддереве узла р конечно остаются меньше элемента в узле р. Поскольку никакие другие ссылки не изменяются, то дерево остается двоичным деревом поиска. Аргументы остаются подобными, если узел n является правым потомком, и они тривиальны, если n — корневой узел. Случай 2 объясняется аналогично. В случае 3 элемент v, записанный в узле n, перекрывается следующим большим элементом, хранящимся в узле m (назовем его w), после чего элемент w удаляется из дерева. В получающемся после этого двоичном дереве значения в левом поддереве узла n будут меньше w, поскольку они меньше v. Более того, элементы в правом поддереве узла n больше, чем w, поскольку (1) они больше, чем v, (2) нет ни одного элемента двоичного дерева поиска, лежащего между v и w и (3) из них элемент w был удален.

        Заметим, что в случае 3 узел m должен обязательно существовать, поскольку правое поддерево узла n непустое. Более того, рекурсивный вызов для удаления m не может привести к срыву рекурсивного вызова, поскольку если узел m не имел бы левого потомка, то был бы применен случай 1, когда его нужно было бы удалить.

        На рис. 5 показана последовательность операций удаления, при которой возникают все три ситуации. Напомним, что симметричный обход каждого дерева в этой последовательности проходит все узлы в возрастающем порядке, проверяя, что в каждом случае это двоичные деревья поиска.

        Компонентная функция remove является общедоступной компонентной функцией для удаления узла, содержащего заданный элемент. Она обращается к собственной компонентной функции _remove, которая выполняет фактическую работу:

        Рис. 5: Последовательность операций удаления элемента: (а) и (б) — Случай 1: удаление из двоичного дерева элемента 8; (б) и (в) — Случай 2: удаление элемента 5; (в) и (г) — Случай 3: удаление элемента 3

        template void SearchTree::remove(Т val) < _remove(val, root); >template void SearchTree::_remove(Т val, TreeNode * &n) < if (n == NULL) return; int result = (*cmp) (val, n->val); if (result < 0) _remove(val, n->_lchild); else if (result > 0) _remove (val, n->_rchild); else < // случай 1 if (n->_lchild == NULL) < TreeNode*old = n; n = old->_rchild; delete old; > else if (n->_rchild == NULL < // случай 2 TreeNode *old = n; n = old->_lchild; delete old; > else < // случай 3 TreeNode *m = _findMin(n->_rchild); n->val = m->val; remove(m->val, n->_rchild); > > >

        Параметр n (типа ссылки) служит в качестве псевдонима для поля ссылки, которое содержит ссылку вниз на текущий узел. При достижении узла, подлежащего удалению (old), n обозначает поле ссылки (в предке узла old), содержащее ссылку вниз на old. Следовательно команда n=old->_rchild заменяет ссылку на old ссылкой на правого потомка узла old.

        Компонентная функция removeMin удаляет из дерева поиска наименьший элемент и возвращает его:

        template Т SearchTree::removeMin (void)

        Древовидная сортировка — способ сортировки массива элементов — реализуется в виде простой программы, использующей деревья поиска. Идея заключается в занесении всех элементов в дерево поиска и затем в интерактивном удалении наименьшего элемента до тех пор, пока не будут удалены все элементы. Программа heapSort(пирамидальная сортировка) сортирует массив s из n элементов, используя функцию сравнения cmp:

        template void heapSort (T s[], int n, int(*cmp) (T,T) ) < SearchTreet(cmp); for (int i = 0; i

        Также доступна реализация двоичного дерева на Си с базовыми функциями. Операторы typedef T и compGT следует изменить так, чтобы они соответствовали данным, хранимым в дереве. Каждый узел Node содержит указатели left, right на левого и правого потомков, а также указатель parent на предка. Собственно данные хранятся в поле data. Адрес узла, являющегося корнем дерева хранится в укзателе root, значение которого в самом начале, естественно, NULL. Функция insertNode запрашивает память под новый узел и вставляет узел в дерево, т.е. устанавливает нужные значения нужных указателей. Функция deleteNode, напротив, удаляет узел из дерева (т.е. устанавливает нужные значения нужных указателей), а затем освобождает память, которую занимал узел. Функция findNode ищет в дереве узел, содержащий заданное значение.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *