Экзаменационные вопросы

1. Алгоритмизация процессов обработки данных. Понятие алгоритма и его основные свойства. Сущность алгоритмизации вычислительных процессов.

2. Данные и алгоритмы. Основные способы задания алгоритмов.

3. Основные структуры алгоритмов. Этапы решения задач на ПЭВМ. Примеры алгоритмов.

4. Структурная организация данных

5. Одномерные массивы: задачи поиска, замены и перестановок элементов массива.

6. Одномерные массивы: задачи сортировок элементов массива.

7. Двумерные массивы: задачи поиска, замены и суммирования элементов двумерного массива.

8. Двумерные массивы: задачи сортировок и перестановок в двумерных массивах.

9. Структуры.

10. Структуры и указатели.

11. Объединения.

12. Битовые поля.

13. Стандартные файлы и функции по работе с ними.

14. Обработка файлов в потоковом режиме.

15. Прямой доступ к данным файла.

16. Работа с элементами файлов.

17. Решение задач на обработку файлов.

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

19. Одномерные динамические массивы.

20. Двумерные динамические массивы.

21. Решение задач на динамические массивы.

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

23. Динамические структуры данных: однонаправленные и двунаправленные списки.

24. Динамические структуры данных: очередь и стек.

25. Динамические структуры данных: бинарные деревья.

26. Решение задач на динамические структуры данных.

27. Алгоритмы обработки данных.

28. Рекурсия и рекурсивные алгоритмы.

29. Решение задач на использование рекурсивных алгоритмов.

30. Алгоритм перебора с возвратом.

31. Алгоритмы поиска в линейных структурах.

32. Алгоритмы хеширования данных.

33. Алгоритмы поиска в тексте.

34. Алгоритмы поиска на основе деревьев.

35. Алгоритмы сжатия данных.

36. Алгоритмы сортировки массивов. Внутренняя сортировка.

37. Алгоритмы сортировки массивов. Внешняя сортировка.

38. Алгоритмы на графах. Алгоритмы обхода графа.

39. Алгоритмы на графах. Алгоритмы нахождения кратчайшего пути.

40. Решение задач на использование алгоритмов обработки данных.

Практические задания:

Составить блок-схему алгоритма решения задачи и программу на языке С++

Строки

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

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

3. Дана строка-предложение из символов латинского алфавита. Вывести самое короткое слово в предложении (если таких слов несколько, то вывести первое из них).

4. Дана строка, состоящая из символов латинского алфавита, разделенных пробелами (одним или несколькими). Определить длину самого длинного слова.

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

6. Дана строка-предложение из символов латинского алфавита. Преобразовать строку так, чтобы каждое слово начиналось с заглавной буквы.

7. Дана строка-предложение из символов латинского алфавита. Вывести самое длинное слово в предложении (если таких слов несколько, то вывести последнее из них).

8. Определить, сколько раз в строке встречается заданное слово.

Одномерный массив: преобразование массива

9. Заменить все положительные элементы целочисленного массива, состоящего из n элементов, на значение минимального.

10. Дан массив, состоящий из n элементов. Переставить в обратном порядке элементы массива, расположенные между его минимальным и максимальным элементами.

11. Дан массив, состоящий из n элементов. Назовем серией группу подряд идущих одинаковых элементов, а длиной серии – количество этих элементов (длина серии может быть равна 1). Заменить каждую серию, длина которой больше k, на один наименьший элемент массива. Если таких серий нет, то массив оставить без изменений.

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

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

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

15. Дан целочисленный массив, состоящий из n элементов. Удалить из массива все элементы, встречающиеся менее двух раз.

16. Дан массив, состоящий из n элементов. Преобразовать его, вставив перед каждым положительным элементом минимальный элемент.

Одномерный массив: сортировка массива

17. Отсортируйте в массиве нечетные элементы по убыванию.

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

19. Сортировка подсчетом. Выходной массив заполняется значениями –1. Затем для каждого элемента определяется его место в выходном массиве путем подсчета количества элементов, строго меньших данного. Естественно, что все одинаковые элементы попадают на одну позицию, за которой следует ряд значений –1. После этого оставшиеся в выходном массиве позиции со значением –1 заполняются копией предыдущего значения.

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

21. Организуйте массив, содержащий 2n целых чисел. Отсортируйте элементы с нечётными индексами по возрастанию.

22. Дан массив размера N. Вывести индексы массива в том порядке, в котором соответствующие им элементы образуют возрастающую последовательность.

23. Отсортируйте в массиве четные элементы по возрастанию.

24. Создайте целочисленный массив, содержащий 2n различных чисел. Отсортируйте первую половину массива по возрастанию, а вторую по убыванию. Выведите на экран, отсортированный таким образом массива.

Двумерный массив

25. Дана квадратная матрица порядка 2n + 1. Зеркально отразить ее элементы относительно горизонтальной оси симметрии матрицы.

26. Дана матрица размера n × m. Поменять местами ее столбцы так, чтобы их максимальные элементы образовывали убывающую последовательность.

27. Найдите квадратную матрицу, обратную данной с размером n × n.

28. Дана квадратная матрица порядка 2n. Повернуть ее на 180 градусов в положительном направлении.

29. Заполнить двумерный квадратный массив целыми числами от 1 до 100 по спирали, как показано на следующем рисунке.

30. Дана матрица размера n × m. Поменять местами столбцы, содержащие минимальный и максимальный элементы матрицы.

31. Даны две матрицы n × m и m ×  k. Получите их произведение.

32. Дана матрица размера n × m. Поменять местами ее строки так, чтобы их максимальные элементы образовывали возрастающую последовательность.

Файлы

33. Даны два текстовых файла с именами Name1 и Name2. Добавить в конец каждой строки файла Name1 соответствующую строку файла Name2. Если файл Name2 короче файла Name1, то выполните переход к началу файла Name2.

34. Организовать текстовый файл, состоящий из N строк. Определить максимальный и минимальный размер строки в файле и вывести их в другой файл.

35. В отсортированный файл фамилий добавить новую фамилию, не нарушив его упорядоченность.

36. В файле хранятся названия товаров и цены в рублях 1997 г. Создать новый файл, преобразовав цены товара в рубли и копейки 1998 г., добавив наименование «руб.» и «коп.». В указанный год цены уменьшились в 1000 раз.

Тестовые задания:

Модуль 1 «Алгоритмы поиска, замены и сортировки данных»

Тесты «Массивы»

Задача 1.

Вариант 1 Задачи 1. В программе объявлен и проинициализирован массив int a[]={9,8,7,6,5,4,3,2,1,0}. Укажите значение a[a[a[9]]].

а) 9

б) +0

в) 1

г) элемент с таким индексом в данном массиве не определен

Вариант 2 Задачи 1. В программе объявлен и проинициализирован массив int a[]={2,4,6,8,10,12,14,16}. Укажите значение *(a+a[2]).

а) элемент с таким индексом в данном массиве не определен

б) 2

в) 10

г) +14

Вариант 3 Задачи 1. В программе объявлен и проинициализирован массив int a[]={1,3,8,5,0,4,9,2,13}. Укажите значение a(a[7]+a[1]).

а) элемент с таким индексом в данном массиве не определен

б) 8

в) +4

г) 13

Задача 2.

Вариант 1 Задачи 2. Укажите название алгоритма сортировки, фрагмент кода которой представлен ниже.

void Sort (int k,int x[max]) {

int i,j,min,temp;

for (i=0;i<k-1;i++) {

min=i;

for (j=i+1;j<k;j++){

if (x[j]<x[min])

min=j;

}

temp=x[i];

x[i]=x[min];

x[min]=temp;

}

}

а) пузырьковая сортировка

б) шейкерная сортировка

в) + сортировка методом простого выбора

г) сортировка методом простого включения

Вариант 2 Задачи 2. Укажите название алгоритма сортировки, фрагмент кода которой представлен ниже.

void Sort (int k,int x[max]) {

int i,j, temp;

for (i=0;i<k;i++) {

temp=x[i];

for (j=i-1; j>=0 && x[j]>temp; j--)

x[j+1]=x[j];

x[j+1]=temp;

}

}

а) пузырьковая сортировка

б) шейкерная сортировка

в) +сортировка методом простого выбора

г) сортировка методом простого включения

Вариант 3 Задачи 2. Укажите название алгоритма сортировки, фрагмент кода которой представлен ниже.

void Sort (int k,int x[max]) {

int i,j,buf;

for (i=k-1;i>0;i--)

for (j=0;j<i;j++)

if (x[j]>x[j+1]) {

buf=x[j];

x[j]=x[j+1];

x[j+1]=buf;

}

}

а)+пузырьковая сортировка

б) шейкерная сортировка

в) сортировка методом простого выбора

г) сортировка методом простого включения

Задача 3.

Вариант 1 Задачи 3. Укажите обращение, аналогичное обращению mas[i][j] к элементу двумерного массива размерности M×N.

а) mas[i,j]

б) +*(*(mas+i)+j)

в) mas[N*i+j]

г) mas[0][0]+ N*i+j

Вариант 2 Задачи 3. Укажите обращение, аналогичное обращению *(*(mas+i)+j) к элементу двумерного массива размерности M×N.

а) *(mas+N*i+j)

б)+mas[i][j]

в) mas[0][0]+ N*i+j

г) mas[i,j]

Вариант 2 Задачи 3. Укажите обращение, аналогичное обращению (*(arr+i))[j] к элементу двумерного массива размерности M×N.

а) *(mas+N*i+j)

б) +mas[i][j]

в) +*(*(mas+i)+j)

г) mas[i,j]

Задача 4.

Вариант 1 Задачи 4. Укажите в байтах размер памяти, занимаемой массивом, который объявлен так:

int m[][5][3]={{{1,2,3},{1}},{{4},{7,8}}};

а) 28

б) 32

в) +120

г) для безразмерного массива размер не определен

Вариант 2 Задачи 4. Укажите в байтах размер памяти, занимаемой массивом, который объявлен так:

float m[][6]={{6.2},{14.3,0.3},{7.0,1.0,5.5,7.8}};

а) 28

б) 48

в) +72

для безразмерного массива размер не определен

Вариант 3 Задачи 4. Укажите в байтах размер памяти, занимаемой массивом, который объявлен так:

а) int m[][7]={{6,2,4,8},{13},{5,6,7}};

б) +84

в) 32

г) 48

для безразмерного массива размер не определен

Задача 5.

Вариант 1 Задачи 5. Укажите неверные варианты объявления и/или инициализации массива.

а) +int mas[];

б) int mas[]={1,2,3,4,5};

в) +int mas[][]={1,2,3,4,5};

г) int mas[2][3]={1,2,3,4,5};

Вариант 2 Задачи 5. Укажите неверные варианты объявления и/или инициализации массива.

а) +int mas[3]={2.3,4.5,5};

б) +int mas[3]={{1},{2},{3}};

в) int mas[][3]={{1,2,3},{4,5}};

г) int mas[5][3]={{1,2,3},{4,5}};

Вариант 3 Задачи 5. Укажите неверные варианты объявления и/или инициализации массива.

а) int mas[3]={2+5,7,8};

б) int mas[9]={1,2,3,4};

в) +int mas[2][]={{1,2,3},{4,5}};

г) +int mas[2][3]={1,2,3,4,5,6,7,8,9};

Задача 6.

Вариант 1 Задачи 6. Укажите верные аналогичные обращения к элементу одномерного массива в присваивании mas[i]=3.

а) mas+i=3;

б) &mas+i=3;

в) *mas+i=3;

г) +*(mas+i)=3;

Вариант 2 Задачи 6. Укажите верные аналогичные обращения к указателю на одномерный массив в присваивании int *p; p=mas;.

а) int *p; p=mas[0];

б) +int *p; p=&mas[0];

в) int *p; p=*mas[0];

г) int *p; p=*mas;

Вариант 3 Задачи 6. Укажите верные аналогичные обращения к элементу одномерного массива в присваивании *(mas+i)=8;.

а) *mas+i=8;

б) mas+i=8;

в) +mas[i]=8;

г) &mas+i=8;

Модуль 2 «Динамические структуры данных»

Задача 1.

Вариант 1 Задачи 1. Чем ограничен размер динамической памяти?

а) +размером оперативной памяти

б) размером внешних накопителей

в) размером стековой области

г) нет никаких ограничений

Вариант 2 Задачи 1. Из какой области выделяются блоки динамической памяти?

а) стековой области

б) области программы

в) +области свободной памяти

г) области глобальных переменных

Вариант 3 Задачи 1. Динамическая память явно не освобождена в программе. Тогда:

а) она будет занята и после завершения программы

б) +она автоматически освободится после завершения работы программы

в) она освободится только при выходе из среды программирования

г) она освободится только после выключения компьютера

Задача 2.

Вариант 1 Задачи 2. Укажите некорректное выделение динамической памяти, если выполнено объявление int *pt;.

а) pt = new int;

б) pt = new int [15];

в) +pt = new int [];

г) pt = new int (15);

Вариант 2 Задачи 2. Укажите корректное выделение динамической памяти, если выполнено объявление float *pf;.

а) *pf = new float;

б) +pf = new float [15];

в) pf = new float [];

г) pf = new sizeof(float);

Вариант 3 Задачи 2. Укажите ошибку при использовании операции выделения динамической памяти, если выполнено объявление char *ph;.

а) ph = new char [20];

б) +ph = *(new char);

в) ph = new char ('&');

г) ph = new char;

Задача 3.

Вариант 1 Задачи 3. Какая область динамической памяти, выделенной под одномерный массив mass, будет освобождена следующим действием: delete mass;?

а) вся используемая динамическая память

б) область, занятая всеми элементами массива mass

в) +область, занятая только первым элементом массива mass

г) к массиву данная операция не применима

Вариант 1 Задачи 3. Укажите верное освобождение динамической памяти, занятой всеми элементами массива mass.

а) +delete [] mass;

б) delete mass;

в) +free (mass);

г) free (*mass);

Вариант 3 Задачи 3. Какая область динамической памяти, выделенной под одномерный а

массив mass, будет освобождена следующим действием: free (mass);?

а) вся используемая динамическая память

б) +область, занятая всеми элементами массива mass

в) область, занятая только первым элементом массива mass

г) к массиву данная операция не применима

Задача 4.

Вариант 1 Задачи 4. Какие действия выполняет приведенный фрагмент кода?

int *mas, n=10, i;

mas = new int [n];

mas[0]= a[1]=1;

for (i=2; i<n; i++)

mas[i]= mas[i-1]+ mas[i-2];

а) динамическая память под массив не выделена, фрагмент ошибочный

б) обращение к элементам массива неверно, фрагмент ошибочный

в) выделяет динамическую память для 10 целочисленных элементов и заполняет его случайными числами

г) +выделяет динамическую память для 10 целочисленных элементов массива и заполняет его числами Фибоначчи

Вариант 2 Задачи 4. Какие действия выполняет приведенный фрагмент кода?

int n=20, i;

float *mas;

mas = calloc(n,sizeof(float));

for (i=0; i<n; i++)

mas[i]= exp(i);

а) выделяет динамическую память для 20 вещественных элементов и заполняет его случайными числами

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

в) +не выполнено явное преобразование типа указателя при выделении динамической памяти, фрагмент ошибочный

г) во фрагменте ошибка вследствие неверного обращения к элементам массива

Вариант 3 Задачи 4. Какие действия выполняет приведенный фрагмент кода?

int n=15, i;

double *mas;

mas = (double *)malloc(sizeof(double));

for (i=0; i<n; i++)

cin >> mas[i];

а) выделяет динамическую память для 15 вещественных элементов и считывает в него элементы с клавиатуры

б) не выполнено явное преобразование типа указателя при выделении динамической памяти, фрагмент ошибочный

в) во фрагменте ошибка вследствие неверного обращения к элементам массива

г) +динамическая память выделена только для одного вещественного числа, фрагмент ошибочный

Модуль 3 «Алгоритмы обработки данных»

Задача 1.

Вариант 1 Задачи 1. Укажите последовательности, которые являются бинарными пирамидами.

а) +8, 4, 7, 3, 1, 5, 2, 2, 0

б) 8, 7, 4, 3, 1, 5, 2, 2, 0

в) +8, 5, 7, 4, 3, 3, 2, 2, 3

г) 8, 5, 7, 4, 6, 3, 2, 2, 3

Вариант 2 Задачи 1. Укажите последовательности, которые не являются бинарными пирамидами.

а) 7, 5, 7, 4, 2, 6, 5, 3, 2

б) +7, 5, 7, 4, 6, 2, 5, 3, 2

в) 8, 6, 8, 3, 0, 7, 6, 1, 3

г) +8, 6, 8, 3, 0, 7, 6, 1, 3, 1

Вариант 3 Задачи 1. Укажите последовательности, которые являются бинарными пирамидами.

а) +9, 6, 8, 3, 5, 7, 4, 2, 1, 4

б) 9, 5, 8, 3, 4, 7, 4, 2, 1, 6

в) 9, 6, 6, 2, 5, 8, 7, 0, 1, 3

г) +9, 6, 8, 2, 5, 6, 7 0, 1, 3

Задача 2.

Вариант 1 Задачи 2. В вершину пирамиды помещен элемент. На какой позиции он остановится в результате спуска вниз? Нумерация элементов начинается с нуля.

а) 1

б) 3

в) +4

г) 7

Вариант 2 Задачи 2. В вершину пирамиды помещен элемент. На какой позиции он остановится в результате спуска вниз? Нумерация элементов начинается с нуля.

а) 2

б) +5

в) 6

г) 8

Вариант 3 Задачи 2. В вершину пирамиды помещен элемент. На какой позиции он остановится в результате спуска вниз? Нумерация элементов начинается с нуля.

а) 8

б) 4

в) +3

г) 2

Задача 3.

Вариант 1 Задачи 3. Дан массив элементов: 4, 7, 3, 8, 5, 6, 3, 7, 2, 6, 8. Укажите порядок элементов этого массива после выполнения первого прохода сортировки Хоара по невозрастанию. Опорный элемент расположен на средней позиции.

а) 8, 8, 7, 7, 6, 6, 5, 4, 3, 3, 2

б) 8, 7, 5, 4, 3, 6, 8, 7, 6, 3, 2

в) +8, 7, 7, 8, 6, 5, 3, 3, 2, 6, 4

г) 7, 4, 8, 3, 6, 5, 7, 3, 6, 2, 8

Вариант 2 Задачи 3. Дан массив элементов: 4, 7, 3, 8, 5, 6, 3, 7, 2, 6, 8. Укажите порядок элементов этого массива после выполнения второго прохода сортировки Хоара по неубыванию. Опорный элемент расположен на средней позиции.

а) +3, 2, 4, 3, 5, 6, 6, 7, 7, 8, 8

б) 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8

в) 4, 3, 3, 2, 5, 6, 7, 7, 8, 6, 8

г) 3, 4, 5, 7, 8, 2, 3, 6, 6, 7, 8

Вариант 3 Задачи 3. Дан массив элементов: 7, 9, 0, 3, 2, 4, 7, 6, 5, 2, 0. Укажите порядок элементов этого массива после выполнения второго прохода сортировки Хоара по невозрастанию. Опорный элемент расположен на средней позиции.

а) 9, 7, 7, 6, 5, 4, 3, 2, 2, 0, 0

б) 7, 9, 5, 6, 7, 4, 2, 3, 0, 2, 0

в) +7, 9, 7, 6, 5, 4, 2, 3, 2, 0, 0

г) 7, 9, 5, 6, 7, 4, 2, 3, 0, 2, 0

Основы алгоритмизации и программировани

Тема. Типы данных в языке С++.

Тип данных – это множество допустимых значений, которые может принимать тот или иной объект, а также множество допустимых операций, которые применимы к нему.

Классификация типов данных в С++

Язык программирования C++ поддерживает следующие типы данных (рис. 1).

• Базовые типы. Базовые типы предопределены стандартом языка, указываются зарезервированными ключевыми словами и характеризуются одним значением.

• Производные типы. Производные типы задаются пользователем, и переменные этих типов создаются как с использованием базовых типов, так и типов классов.

• Типы класса. Экземпляры этих типов называются объектами.

Существует четыре спецификатора типа данных, уточняющих внутреннее представление и диапазон базовых типов:

short (короткий) long (длинный)	длина
signed (знаковый) unsigned (беззнаковый)	знак (модификатор)

Рассмотрим более подробно базовые типы данных.

Основные типы данных

Диапазон значений

-2 147 483 648 до 2 147 483 647

0 до 4 294 967 295

-32 768 до 32 767

0 до 65 535

-2 147 483 648 до 2 147 483 647

0 до 4 294 967 295

-9 223 372 036 854 775 808 до 9 223 372 036 854 775 807

0 до 18 446 744 073 709 551 615

-128 до 127

0 до 255

0 до 65 535

3.4Е-38 до 3.4Е+38 (7 значащих цифр)

1.7Е-308 до 1.7Е+308 (15 значащих цифр)

1.7Е-308 до 1.7Е+308 (15 значащих цифр)

true (1) или false (0)

-2 147 483 648 до 2 147 483 647

Размер памяти, байт (бит)

4 (32)

4 (32)

2 (16)

2 (16)

4 (32)

4 (32)

8 (64)

8 (64)

1 (8)

1 (8)

2 (16)

4 (32)

8 (64)

8 (64)

1 (8)

4 (32)

Название

целый

беззнаковый целый

короткий целый

беззнаковый короткий целый

длинный целый

беззнаковый длинный целый

длинный-предлинный целый

беззнаковый длинный-предлинный целый

байт (целый длиной не менее 8 бит)

беззнаковый байт

расширенный символьный

вещественный одинарной точности

вещественный двойной точности

вещественный максимальной точности

логический

перечисляемый

Обозначение

Другие имена

signed signed int

unsigned

short int signed short int

unsigned short int

long int signed long int

unsigned long int

long long int signed long long int

unsigned long long int

signed char

–

–

–

–

–

–

–

Имя типа

int

unsigned int

short

unsigned short

long

unsigned long

long long

unsigned long long

char

unsigned char

wchar_t

float

double

long double

bool

enum

Тип