АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Лабораторная работа «SPLAY-дерево»

Читайте также:
  1. IV. Работа в режиме быстрой маски
  2. V. Работа с рисунками – символами, иллюстрациями
  3. Б. Работа стали на продольный изгиб
  4. Бычий цепень. Систематическое положение, морфология, цикл развития, лабораторная диагностика, профилактика.
  5. В двухъярусных березово-еловых насаждениях (II ярус-лесные культуры ели), разработайте лесоводственные мероприятия, направленные на постоянство лесопользования.
  6. В ходе защиты курсовая работа оценивается комиссией кафедры ТМПО.
  7. Внутренняя энергия. Работа газа. Первый закон термодинамики
  8. Вопрос 21. Определение потребности в рабочих на нормируемых работах
  9. Вопрос № 12. Чему равно минимальное напряжение ЛЭП, когда работа стреловыми кранами на расстоянии ближе 30 м от крайнего провода выполняется по наряду – допуску?
  10. Вред, который причиняет работа женщине
  11. Глава 9. Работа с симптомами-мишенями.
  12. Десять самых убедительных доводов в пользу того, чтобы продолжать работать на фирму

Входной файл: input.txt

Выходной файл: output.txt

Ограничение времени: 1 секунда на тест

 

Дана последовательность операций «добавить вершину», «удалить вершину» и «найти ключ» над SPLAY-деревом. Выполнить эти операции.

Вход

Во входном файле записана последовательность команд вида “+s” или “-s” или “?s” или “E”. Здесь s - слово длиной не более 10 символов. Команда "+s" означает "добавить в дерево слово s", команда "-s" означает "удалить из дерева слово s", команда "?s" - "найти в дереве слово s". Команда "E" означает "завершить операции с деревом". Каждая команда записана в отдельной строке, начиная с первой позиции, и не содержит пробелов.

Выход

В выходной файл запишите результаты выполнения команд "?s" в том порядке, в котором они присутствуют во входном файле. Если слово найдено, записать в файл его глубину в дереве, в противном случае - символ 'n'.

Примеры входа и выхода

input.txt output.txt
+глокая +куздра ?бокра -куздра ?куздра ?глокая E nn1  

 


Упражнение «Декартово дерево»

Входной файл: input.txt

Выходной файл: output.txt

Ограничение времени: 1 секунда на тест

 

Выполнить последовательность операций ADD, DELETE и SEARCH над декартовым деревом.

Вход

В текстовом файле INPUT.TXT записана последовательность команд вида “+x y” или “-x” или “?x” или “E”. Здесь x, y - натуральные числа, не превосходящие 106. Команда "+x y" означает "добавить в декартово дерево вершину с ключами x, y", команда "-x" означает "удалить из декартова дерева вершину с ключом x, “?x" - "найти в декартовом дереве вершину с ключом x". Команда "E" означает "завершить операции с декартовым деревом". Каждая команда записана в отдельной строке, начиная с первой позиции, и не содержит пробелов, кроме команды “+”, содержащей один пробел.

Выход

В текстовый файл OUTPUT.TXT записать результаты выполнения команд "?x" в том порядке, в котором они присутствуют в файле INPUT.TXT. Если вершина найдена, записать в файл глубину вершины в дереве (глубина корня равна 1), в противном случае - символ “n”. После каждого выведенного данного (числа / символа) выводить один пробел.

Примеры входа и выхода

input.txt output.txt
?1 +3 6 -1 +2 1 -8 +6 4 -2 ?6 -3 -5 E n 2  

 


 

Лабораторная работа «Декартово дерево по неявному ключу»

Входной файл: input.txt

Выходной файл: output.txt

Ограничение времени: 1 секунда на тест

Дана последовательность операций «добавить вершину», «вставить вершину», «удалить вершины» и «найти ключ» над декартовым деревом по неявному ключу. Выполнить эти операции.

Вход

Во входном файле записана последовательность команд вида “ ADD s ” или “ INS s k ” или “ DEL a b ” или “ KEY p ”, или “ END ”. Здесь s - слово длиной не более 10 символов. Команда " ADD s " означает "добавить в дерево справа вершину со словом s ". Команда “ INS s k ” означает «вставить в дерево вершину со словом s в k -ю позицию». Команда “ DEL a b ” означает "удалить из вершины с номерами от a до b включительно. Команда " KEY p " означает "вывести слово, записанное в вершине с номером p. Команда " END " означает "завершить операции с деревом". Здесь k, a, b, p – натуральные числа. Каждая команда записана в отдельной строке, начиная с первой позиции, слова и числа, составляющие команду, разделяются ровно одним пробелом. Вершины дерева нумеруются, начиная с единицы. Если в команде “ INS s k ” величина k превышает текущее количество вершин, вместо неё следует выполнить команду " ADD s ". Если в команде “ DEL a b ” величина a превышает текущее количество вершин, то ничего не нужно делать, в противном случае, если величина b превышает текущее количество вершин, то следует удалить все вершины, начиная с a -ой.

Выход

В выходной файл запишите результаты выполнения команд " KEY p " в том порядке, в котором они присутствуют во входном файле. Если величина p не превышает текущее количество вершин, то запишите в отдельной строке слово, записанное в вершине с номером p, в противном случае запишите в отдельной строке «OUT OF RANGE».


1 | 2 | 3 | 4 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)