Упражнение 1. Простые цепочки списков - ориентировочное время 40 мин.

Упражнение 1. Простые цепочки списков - ориентировочное время 40 мин.
Мы рассматриваем списки натуральных чисел (положительных или нулевых целых чисел). Для кодирования этих списков мы используем простую строковую структуру, каждый узел которой представляет собой структуру с двумя полями: целочисленное значение и указатель на следующий узел. На протяжении всего упражнения стоимостью процедуры будет количество узлов, посещенных в списке (ах) во время ее выполнения.
Вопрос 1. Напомним определение структуры узла и типа списка. Нарисуйте структуру цепочки, которая представляет список L1 = (11, 5, 7, 2, 9, 6, 1). Задайте два значения: L1-> next-> next-> value, L1-> next-> next-> next-> next-> value.
Вопрос 2. Напишите итеративную процедуру ?listlength (L: list): целое число, которое возвращает количество узлов списка L.
Вопрос 3. Мы хотим убедиться, что список содержит не более 10 узлов. Предлагаем следующую процедуру
auPlusDix (L: список): bool?een
return listLength (L) <= 10
Приведите стоимость этой процедуры как функцию количества узлов в списке L. Выведите класс сложности этой процедуры. Почему эта процедура не эффективна? Предложите итерационную процедуру, максимальная стоимость которой не зависит от размера списка.
Вопрос 4. Дайте итеративную процедуру presentListeIt (L: list, x: integer): boolean, которая возвращает True, если x является значением L, и False в противном случае. Предоставьте рекурсивную версию этой процедуры.
Вопрос 5. Предположим, что два списка L1 и L2 кодируют два набора E1 и E2 (поэтому каждый список состоит из различных значений). Используйте процедуру presentListeIt (L: list, x: integer): boolean, чтобы написать процедуру под Set1 (L1, L2: list): boolean, которая возвращает True, когда все значения L1 находятся в списке L2, и False в противном случае. Приведите стоимость этой процедуры как функцию от n1, количества узлов L1 и n2, количества узлов L2.
Вопрос 6. * Теперь предположим, что списки L1 и L2 отсортированы. Задайте процедуру underSet2 (L1, L2: list): boolean, которая возвращает True, когда все значения L1 находятся в списке L2, и False в противном случае. Приведите стоимость этой процедуры как функцию от n1, количества узлов L1 и n2, количества узлов L2. Например, если L1 = (2, 4, 5) и L2 = (1, 2, 4, 5, 7), процедура возвращает True, а если L1 = (2, 3, 5) и L2 = (1, 2, 4) , 5, 7) процедура возвращает False.