Использование структур для битового представления чисел

Написать функцию для вывода на экран битового представления в ЭВМ числа в заданном формате. Выполнить задание двумя способами: через объединение (union) и через структуру с битовыми полями. Сравнить результаты.

1. bool

2. char

3. long

4. short

5. int

6. float

7. double

8. void *

9. unsigned long

10. unsigned short

11. unsigned int

12. int *

 

 

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

Динамическое выделение памяти для массивов

7.1.1. Выполнить задание, используя динамическое выделение памяти для одномерного массива. Дано (в текстовом файле) n>10⁹ натуральных чисел (каждое число £10⁴). Ограничение на объем используемой памяти 1 Мб. Получить массив за один просмотр элементов файла:

1. в котором все числа исходного файла расположены по возрастанию значений (без повторений);

2. в котором все числа исходного файла расположены по убыванию значений (без повторений);

3. образованный из натуральных чисел £10⁴, не встречающихся в исходном файле, по возрастанию;

4. образованный из натуральных чисел £10⁴, не встречающихся в исходном файле, по убыванию;

5. образованный из исходного исключением чисел, которые встречаются в исходном файле ровно один раз, по возрастанию значений (без повторений);

6. образованный из чисел, встречающихся в исходном файле более одного раза, по возрастанию (без повторений);

7. образованный из чисел, встречающихся в исходном файле более одного раза, по убыванию без повторений;

8. образованный из чисел, встречающихся в исходном файле ровно два раза, по возрастанию (без повторений);

9. образованный из чисел, встречающихся в исходном файле ровно два раза, по убыванию (без повторений);

10. образованный из исходного исключением повторных вхождений одного и того же числа по возрастанию значений;

11. в котором все числа исходного файла расположены по возрастанию (без повторений);

12. в котором все числа исходного файла расположены по убыванию (без повторений).

 

 

7.1.2. Выполнить задание, используя динамическое выделение памяти для двумерного массива, двумя способами:

· описывая двумерный массив как одномерный, с расчетом смещения элемента массива по линейной формуле;

· описывая двумерный массив как указатель на массив указателей.

1. Дана вещественная квадратная матрица А порядка n, векторы х, у с n элементами. Составить функцию, которая позволяет получить вектор c = А × (x + y).

2. Даны вещественные квадратные матрицы А, В, C порядка n. Составить функцию для получения матрицы D = А × (В + С)

3. Дана вещественная квадратная матрица А порядка n, вектор b с n элементами. Составить функцию, которая позволяет получить вектор c = А² × b.

4. Составить функцию, которая позволяет по заданной квадратной матрице размером n x n построить вектор длиной 2 n – 1, элементы которого – максимумы элементов главной диагонали и диагоналей, параллельных ей.

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

6. Составить функцию, которая позволяет возвести вещественную матрицу произвольного размера в степень n, где n – натуральное заданное число.

7. Даны вещественные квадратные матрицы А, В порядка n. Составить функцию для получения матрицы С = А × В + B × A.

8. Дана вещественная квадратная матрица А порядка n. Составить функцию для получения матрицы B = Е + А + А ² + … + А^m, где m – заданное натуральное число.

9. Дана вещественная квадратная матрица А порядка n. Составить функцию для получения матрицы B = А + А ² + А ⁴+ А ⁸.

10. Следом матрицы называется сумма элементов, расположенных на главной диагонали. Даны вещественная квадратная матрица А порядка m, натуральное число n. Составить функцию для получения суммы следов матриц А, А ², … Аⁿ.

11. Составить функцию, которая позволяет возводить в квадрат комплексную квадратную матрицу произвольного размера.

12. Составить функцию, которая позволяет возводить в восьмую степень комплексную квадратную матрицу произвольного размера.

Линейный список

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

1. По исходному списку определить ФИО самого младшего студента на каждом курсе. Сформировать список из этих студентов, удалив их из исходного списка.

2. По исходному списку определить ФИО самого старшего студента на каждом курсе. Сформировать список из этих студентов, удалив их из исходного списка.

3. По исходному списку определить всех студентов, ФИО которых начинается на заданную букву. Сформировать список из этих студентов, удалив их из исходного списка.

4. По исходному списку определить всех студентов, возраст которых превышает заданный. Сформировать список из этих студентов, удалив их из исходного списка.

5. По исходному списку определить всех студентов n курса. Сформировать список из этих студентов, удалив их из исходного списка.

6. По исходному списку определить всех отличников. Сформировать список из этих студентов, удалив их из исходного списка.

7. По исходному списку определить всех отличников n курса. Сформировать список из этих студентов, удалив их из исходного списка.

8. По исходному списку определить всех неуспевающих студентов. Сформировать список из этих студентов, удалив их из исходного списка.

9. По исходному списку определить всех неуспевающих студентов n курса. Сформировать список из этих студентов, удалив их из исходного списка.

10. По исходному списку определить студентов, имеющих средний бал успеваемости выше общего среднего бала. Сформировать список из этих студентов, удалив их из исходного списка.

11. По исходному списку определить студентов на n курсе, имеющих средний бал успеваемости выше среднего бала по его курсу. Сформировать список из этих студентов, удалив их из исходного списка.

12. По исходному списку определить студентов на n курсе, имеющих средний бал успеваемости выше среднего бала по его курсу. Сформировать список из этих студентов, удалив их из исходного списка.

 

7.3. Линейные списки

Выполнить задания с использованием связанных динамических структур данных.

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

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

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

4. Описать функцию, которая формирует список символов-букв L 2, включив в него те символы-буквы, которые не входят в список L 1.

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

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

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

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

9. Описать функцию, которая из списка символов L удаляет все вхождения списка L 1 (если такой есть).

10. Описать функцию, которая в списке символов L заменяет первое вхождение списка L 1 (если такой есть) на список L 2.

11. Описать функцию, которая в списке символов L заменяет все вхождения списка L 1 (если такой есть) на список L 2.

12. Описать функцию, которая в списке символов L заменяет последнее вхождение списка L 1 (если такой есть) на список L 2.

 

 

7.4. Двухсвязные списки

Выполнить задания с использованием двухсвязных списков.

1. Даны натуральное число n, действительные числа x ₁, x ₂,... x_n. Разработать программу вычисления значения выражения следую­щего вида: .

2. Даны натуральное число n, действительные числа x ₁, x ₂,... x_n. Разработать программу вычисления значения выражения следующего вида: .

3. Даны натуральное число n, действительные числа x ₁, x ₂,... x_n. Разработать программу вычисления значения выражения следую­щего вида: .

4. Даны натуральное число n, действительные числа x ₁, x ₂,... x_n. Разработать программу вычисления значения выражения следую­щего вида: .

5. Даны натуральное число n, действительные числа a ₁, a ₂,... a _{2 n} . Получить .

6. Даны натуральное число n, действительные числа a ₁, a ₂,... a _{2 n} . Получить .

7. Даны натуральное число n, действительные числа a ₁, a ₂,..., a _{2 n} . Получить .

8. Даны натуральное число n, действительные числа a ₁, a ₂,..., a _{2 n} . Получить .

9. Даны натуральное число n, действительные числа a ₁, a ₂,..., a _{2 n} . Получить .

10. Даны натуральное число n, действительные числа a ₁, a ₂,..., a _{2 n} . Получить .

11. Даны натуральное число n, действительные числа a ₁, a ₂,..., a _{2 n} . Получить .

12. Даны натуральное число n, действительные числа a ₁, a ₂,..., a _{2 n} . Получить .

 

 

Деревья

По заданной последовательности различных целых чисел построить соот­ветствующее бинарное дерево поиска T. Выполнить следующие задания и вывести элементы дерева на экран.

1. Определяет значение самого левого листа дерева.

2. Определить число листьев дерева.

3. Удалить вершину с минимальным значением элементов.

4. Удалить вершину с максимальным значением элементов.

5. Определить число элементов k-ого уровня.

6. Вывести на экран все листья дерева.

7. Определить номер уровня, в котором содержится максимальное количество вершин.

8. Определить максимальную глубину дерева.

9. Удалить все листья дерева.

10. Определить число ветвей от корня до вершины с заданным элементом. Вывести часть дерева от вершины до данного элемента на экран.

11. Определить число ветвей n -го уровня этого дерева.

12. Дополнить полученное дерево новыми вершинами так, чтобы каждая вершина, которая не является листом, имела ровно двух преемников, значения элементов в дополнительных вершинах задавать равными значениям их предшественников.

Графы

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

1. Найти все вершины заданного графа, недостижимые от заданной его вершины.

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

3. Определить, является ли связным заданный граф.

4. Найти длину кратчайшего цикла в графе.

5. Для двух выделенных вершин графа найти соединяющий их простой путь.

6. Найти самый длинный простой путь в графе.

7. Найти все вершины графа, к которым существует путь заданной длины от выделенной его вершины.

8. Найти все вершины орграфа, от которых существует путь заданной длины к выделенной вершине.

9. Источником орграфа назовем вершину, от которой достижимы все другие вершины; стоком – вершину, достижимую от всех других вершин. Найти все источники и стоки данного орграфа.

10. Найти такую вершину заданного графа, которая принадлежит каждому пути между двумя выделенными (различными) вершинами и отлична от каждой из них.

11. Найти диаметр графа, т. е. максимум расстояний между всевозможными парами его вершин.

12. Найти медиану графа, т. е. такую его вершину, что сумма расстояний от нее до остальных вершин минимальна.