Лабораторная работа № 12

Динамические структуры данных

 

Задание 12.       Вариант 1.

 

  1. Описать процедуру, которая вставляет в список новый элемент X за каждым вхождением элемента Y.

Построить список из вещественных чисел и после каждого элемента

со значением (–1) вставить элемент со значением 0. Распечатать первоначальный и полученный списки.

  1. Используя очередь или стек, описать процедуру или функцию, которая присваивает параметру значение элемента из самого левого листа непустого дерева. Построить дерево и получить заданный результат.

 

Задание 12.       Вариант 2.

  1. Описать функцию, значением которой является список, построенный из элементов массива. Ввести массив с любым типом элементов и построить указанный список. Распечатать полученный список.
  2. Используя очередь или стек, описать процедуру или функцию, которая вычисляет среднее арифметическое всех  элементов дерева. Построить дерево и получить заданный результат.

 

 Задание 12.       Вариант 3.

 

  1. Описать функцию или процедуру, которая находит сумму последнего и предпоследнего элементов списка, содержащего не менее двух элементов. Создать список из целых чисел и найти указанную сумму. Распечатать полученный список и результат.
  2. Используя очередь или стек, описать процедуру или функцию, которая печатает значения всех элементов дерева, являющихся листьями. Построить дерево и получить заданный результат.

  

Задание 12.       Вариант 4.

 

  1. Описать функцию или процедуру, которая проверяет, упорядочены ли элементы списка по алфавиту. В случае невыполнения условия упорядочить список по алфавиту. Распечатать исходный и полученный списки.
  2. Используя очередь или стек, описать функцию или процедуру, которая подсчитывает число вершин на N-ом уровне непустого дерева. N вводится с клавиатуры. Построить дерево и получить заданный результат.

  

Задание 12.       Вариант 5.

 

  1. Описать функцию или процедуру, которая оставляет в списке только первые вхождения одинаковых элементов. Создать список с любым типом элементов, распечатать первоначальный и полученный списки.
  2. Используя очередь или стек, описать процедуру или функцию, которая находит в непустом дереве длину (число ветвей) пути от корня до ближайшей вершины с элементом X. Если X не входит в дерево, сообщить об этом. Построить дерево и получить заданный результат.

 

Задание 12.       Вариант 6.

 

  1. Описать процедуру, которая из заданного списка строит два новых списка: один из положительных элементов, другой – из остальных. Построить список из вещественных чисел и выполнить указанные действия. Распечатать исходный и полученные списки.
  2. Описать логическую функцию, проверяющую на равенство два непустых дерева. Построить два дерева и сравнить их.

 

 Задание 12.       Вариант 7.

 

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

 

Задание 12.       Вариант 8.

 

  1. Описать процедуру, которая объединяет два упорядоченных по неубыванию списка в один новый упорядоченный по неубыванию список. Построить два упорядоченных списка вещественных чисел, объединить их. Распечатать исходные и полученный списки.
  2. Описать (рекурсивную) функцию или процедуру, которая по заданной формуле строит соответствующее дерево-формулу. Ввести с клавиатуры формулу. Построить дерево и напечатать его. ***Вычислить значение дерева-формулы.

<формула> ::= <терминал> | (<формула> <знак> <формула>)

<знак> ::=  + | - | *

<терминал| 1| 2| 3| 4 | 5| 6| 7 | 8| 9

   

Задание 12.       Вариант 9.

 

  1. Описать процедуру, которая производит операцию пересечения двух списков, построением нового списка, элементами которого являются элементы, входящие в оба списка. Построить два списка вещественных чисел, вычислить их пересечение. Распечатать исходные и полученный списки.
  2. Описать (рекурсивную) функцию или процедуру, которая по заданной формуле строит соответствующее дерево-формулу. Ввести с клавиатуры формулу (+, -, * и скобки), построить дерево и вывести его.  ***Вычислить значение дерева-формулы.

<формула> ::= <терминал> | (<формула> <знак> <формула>)

<знак> ::=  + | - | *

<терминал| 1| 2| 3| 4 | 5| 6| 7 | 8| 9

 

Задание 12.       Вариант 10.

  1. Описать две процедуры или функции, первая из которых переносит в конец непустого списка его первый элемент, вторая – переносит в начало непустого списка его последний элемент. Построить список из любых слов, и если первым словом является слово КОНЕЦ, перенести его в конец, если последним словом является слово НАЧАЛО – перенести его в начало. Распечатать первоначальный и полученный списки.
  2. Описать (рекурсивную) функцию или процедуру, которая проверяет, является ли двоичное дерево деревом-формулой и если является, то печатает его в виде соответствующей формулы. Построить дерево из некоторых элементов и осуществить указанные действия.

<формула> ::= <терминал> | (<формула> <знак> <формула>)

<знак> ::=  + | - | *

<терминал| 1| 2| 3| 4 | 5| 6| 7 | 8| 9

 

 Задание 12.       Вариант 11.

  1. «Считалка». N человек располагаются по кругу. Начав отсчет от первого, удаляют каждого k-ого, смыкая круг после удаления. Ввести текст любой считалки (k – количество слов). Определить порядок удаления: напечатать имена детей в том порядке, в котором они удаляются из круга.
  2. Описать (рекурсивную) функцию или процедуру, которая проверяет, является ли двоичное дерево деревом-формулой и если является, то печатает его в виде соответствующей формулы. Построить дерево из некоторых элементов и осуществить указанные действия.

<формула> ::= <терминал> | (<формула> <знак> <формула>)

<знак> ::=  + | - | *

<терминал| 1| 2| 3| 4 | 5| 6| 7 | 8| 9