Билет №28

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

Классификация динамических структур данных

Во многих задачах требуется использовать данные, у которых конфигурация, размеры и состав могут меняться в процессе выполнения программы. Для их представления используют динамические информационные структуры. К таким структурам относят:

• однонаправленные (односвязные) списки;

• двунаправленные (двусвязные) списки;

• циклические списки;

• стек;

• дек;

• очередь;

• бинарные деревья.

Объявление динамических структур данных

Каждая компонента любой динамической структуры представляет собой запись, содержащую, по крайней мере, два поля: одно поле типа указатель, а второе – для размещения данных. В общем случае запись может содержать не один, а несколько указателей и несколько полей данных. Поле данных может быть переменной, массивом или структурой. Для наилучшего представления изобразим отдельную компоненту в виде:

где поле Р – указатель; поле D – данные.

Элемент динамической структуры состоит из двух полей:

• информационного поля (поля данных), в котором содержатся те данные, ради которых и создается структура; в общем случае информационное поле само является интегрированной структурой – вектором, массивом, другой динамической структурой и т.п.;

• адресного поля (поля связок), в котором содержатся один или несколько указателей, связывающий данный элемент с другими элементами структуры;

Объявление элемента динамической структуры данных выглядит следующим образом:

struct имя_типа {

информационное поле;

адресное поле;

};

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

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

Указатель содержит адрес определенного объекта в динамической памяти. Адрес формируется из двух слов: адрес сегмента и смещение. Сам указатель является статическим объектом и расположен в сегменте данных

Работа с памятью при использовании динамических структур

В программах, в которых необходимо использовать динамические структуры данных, работа с памятью происходит стандартным образом. Выделение динамической памяти производится с помощью операции new или с помощью библиотечной функции malloc (calloc). Освобождение динамической памяти осуществляется операцией delete или функцией free.

Например, объявим динамическую структуру данных с именем Node с полями Name, Value и Next, выделим память под указатель на структуру, присвоим значения элементам структуры и освободим память.

2. Задачі на оброблення рядків, використовуючи функції для роботи із рядками та покажчиками на рядки.

/*Вывести на экран часть строки после первого пробела*/

#include "stdafx.h"

#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[]){

setlocale(LC_ALL,"Russian");

char s[80], *p;

int i;

printf("ввести строку: ");

gets(s);

/*найти первый пробел или конец строки*/

for(i=0; s[i] && s[i]!=' '; i++);

p = &s[i];

printf(p);

system("pause");

return 0;

}

Екзаменаційний білет № 29

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

Из всего многообразия связанных списков можно выделить следующие основные:

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

Описание простейшего элемента такого списка выглядит следующим образом:

struct имя_типа {информационное поле;aдресное поле 1;адресное поле 2;};

где информационное поле – это поле любого, ранее объявленного или стандартного, типа;адресное поле 1 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка ;адресное поле 2 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес предыдущего элемента списка.Например:struct list { type elem ;list *next, *pred ; }list *headlist ;

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

Для описания алгоритмов этих основных операций используется следующее объявления:struct Single_List {//структура данных int Data; //информационное поле Single_List *Next; //адресное поле };

Single_List *Head; //указатель на первый элемент списка

Single_List *Current;

//указатель на текущий элемент списка

2. /*Генерация целочисленного массива числами с клавиатуры и вывод массива в строку*/

#include "stdafx.h"

#include <iostream>

using namespace std;

#define max 20

void gen (int k,int *pp);//прототип функции генерации массива

void out (int k,int x[max]);//прототип функции вывода массива

int _tmain(int argc, _TCHAR* argv[]){

int a[max],n,*p;

do {

printf("\nВведите количество элементов массива n (n<=20):");

scanf ("%d",&n);

}

while (n>max); //проверка выхода за границы массива

p=a;

gen(n,p);

out(n,a);

system("pause");

return 0;

}//Описание функции генерации массива с клавиатуры

void gen(int k,int *pp){

/*передача указателя как параметра позволяет вернуть

сформированный массив в основную программу*/

int i;

printf("\nВведите значения %d элементов массива: \n",k);

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

printf("x[%d]= ",i);

scanf("%d",pp++);

}

}//Описание функции вывода массива в строку

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

int i;

printf("\nВывод значений %d элементов массива в строку: \n",k);

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

printf("%d\t",x[i]);

}

Екзаменаційний білет № 30

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

Синтаксис:

Тип * ИмяМассива;

Для того чтобы выделить память под одномерный динамический массив в языке С++ существует 2 способа.

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

Синтаксис:

ИмяМассива = new Тип [ВыражениеТипаКонстанты];

2) при помощи библиотечной функции malloc (calloc), которая служит для выделения динамической памяти.

Синтаксис:

ИмяМассива = (Тип *) malloc(N*sizeof(Тип));

Адресация элементов динамического массива осуществляется аналогично адресация элементов статического массива, то есть с помощью индексированного имени.

Синтаксис:

ИмяМассива[ВыражениеТипаКонстанты];

или

ИмяМассива[ЗначениеИндекса];

Например:

mas[5] – индекс задается как константа,

sl[i] – индекс задается как переменная,

array[4*p] – индекс задается как выражение.

2. /*Циклический сдвиг элементов в массиве с нулевой позиции на одну позицию вправо*/

#include "stdafx.h"

#include <iostream>

#include <time.h>

using namespace std;//подключение модуля для генератора случайных чисел

#define max 100

void gen (int k, int a, int b,int x[max]);//прототип функции генерации массива

void out (int k, int x[max]);//прототип функции вывода массива

void sdvig (int k, int x[max]);//прототип функции циклического сдвига элементов массива

int _tmain(int argc, _TCHAR* argv[]){

int mas[max];

int n;

do {

printf("\nВведите количество элементов массива n (n<=100):");

scanf("%ld", &n);

}

while (n>max);

gen(n,-10,10,mas);

printf("Вывод сгенерированного массива из %d элементов: \n",n);

out(n,mas);

sdvig (n,mas);

printf("\nВывод массива после циклического сдвига элементов: \n");

out(n,mas);

system("pause");

return 0;

}//Описание функции генерации массива

void gen(int k,int a, int b, int x[max]){

int i;

srand(time(NULL)*1000);

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

x[i]=rand()%(b-a)+a;

}

}//Описание функции вывода массива в строку

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

int i;

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

printf("%d ",x[i]);

} //Описание функции циклического сдвига элементов массива

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

int i,buf;

buf=x[k-1];

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

x[i]=x[i-1];

x[0]=buf;

}

Екзаменаційний білет № 31

1. Указатель на структуру объявляется точно так же, как и указатель на данные простых типов: используется операция '*' и указывается тип данных. Тип данных структуры указывается заданием ключевого слова struct и имени шаблона этой структуры.

Синтаксис:

ИмяСтруктурногоТипа *ИмяУказателяНаСтруктуру

Например:

struct goods *p_goods;

struct student *p_stu1, *p_stu2;

Указатели на структуры могут вводиться и для безымянных (не имеющих имен) структурных типов.

Например:

struct {

char *name;

int age;

} *person; //указатель на структуру

Указатель на структуру обеспечивает доступ к ее элементам двумя способами:

(*УказательНаСтруктуру).ИмяЭлемента

или

УказательНаСтруктуру->ИмяЭлемента

2. //Замена отрицательных значений элементов противоположными

#include "stdafx.h"

#include <iostream>

#include <time.h>

using namespace std;

//подключение модуля для генератора случайных чисел

#define max 100

void gen (int k, int a, int b,int x[max]);

//прототип функции генерации массива

void out (int k, int x[max]);

//прототип функции вывода массива

void zamena (int k, int x[max]);//прототип функции замены

int _tmain(int argc, _TCHAR* argv[]){

int mas[max];

int n;

do {

printf("\nВведите количество элементов массива n (n<=100):");

scanf("%ld", &n);

}

while (n>max);

gen(n,-50,50,mas);

printf("Вывод сгенерированного массива из %d элементов: \n", n);

out(n,mas);

zamena (n,mas);

printf("\nВывод массива после замены отрицательных элементов на протипоположные:\n");

out(n,mas);

system("pause");

return 0;

}//Описание функции генерации массива

void gen(int k,int a, int b, int x[max]){

int i;

srand(time(NULL)*1000);

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

x[i]=rand()%(b-a)+a;

}

}

//Описание функции вывода массива в строку

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

int i;

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

printf("%-6d",x[i]);

}

//Описание функции замены

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

int i;

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

if (x[i]<0) x[i]=-x[i];

}

Екзаменаційний білет № 32

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

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

Основные операции, осуществляемые с циклическим двунаправленным списком:создание списка;печать (просмотр) списка;вставка элемента в список;удаление элемента из списка;поиск элемента в спискепроверка пустоты списка;удаление списка.

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

2. //Поиск наименьшего элемента в массиве

#include "stdafx.h"#include <iostream>#include <time.h> using namespace std;//подключение модуля для генератора случайных чисел#define max 100

void gen (int k,int a, int b,int x[max]); //прототип функции генерации массиваvoid out (int k,int x[max]);

//прототип функции вывода массиваint minimum (int k,int x[max]); //прототип функции поиска минимального элемента

int _tmain(int argc, _TCHAR* argv[]){ int mas[max],n;

do { printf("\nВведите количество элементов массива n (n<=100):"); scanf ("%d",&n);

} while (n>max); gen(n,-100,100,mas); out(n,mas);

printf ("\nНаименьший элемент в массиве равен %d", minimum(n,mas)); system("pause");

return 0;}//Описание функции генерации массива

void gen(int k,int a, int b, int x[max]){

int i;

srand(time(NULL)*1000);

//устанавливает начальную точку генерации случайных чисел

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

x[i]= rand()%(b-a)+a;

//функция генерации случайных чисел на [a,b)

}}//Описание функции вывода массива в строку

void out (int k,int x[max]){ int i;

printf("\nВывод значений %d элементов массива в строку: \n",k);

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

printf("%-6d",x[i]);

}//Описание функции поиска минимального элемента

int minimum (int k,int x[max]) {

int i,min=x[0];

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

if (min>x[i]) min=x[i];

return min;}

Екзаменаційний білет № 33

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

Вид f(n)	Характеристика класса алгоритмов
1	Большинство инструкций большинства функций запускается один или несколько раз.
log N	Когда время выполнения программы является логарифмическим, программа становится медленнее с ростом N.
N	Когда время выполнения программы является линейным, это обычно значит, что каждый входной элемент подвергается небольшой обработке.
N log N	Время выполнения, пропорциональное N log N, возникает тогда, когда алгоритм решает задачу, разбивая ее на меньшие подзадачи, решая их независимо и затем объединяя решения.
N2	Квадратичное время выполнения обычно появляется в алгоритмах, которые обрабатывают все пары элементов данных (возможно, в цикле двойного уровня вложенности).
N3	Похожий алгоритм, который обрабатывает тройки элементов данных (возможно, в цикле тройного уровня вложенности)
2N	Лишь несколько алгоритмов с экспоненциальным временем выполнения имеет практическое применение, хотя такие алгоритмы возникают естественным образом при попытках прямого решения задачи, например полного перебора.

• Трудоемкость конструкции "Следование" есть сума трудоемкостей блоков, следующих друг за другом: f=f₁+f₂+...+f_n.

• Трудоемкость конструкции "Ветвление" определяется через вероятность перехода к каждой из инструкций, определяемой условием. При этом проверка условия также имеет определенную трудоемкость. Для вычисления трудоемкости худшего случая может быть выбран тот блок ветвления, который имеет большую трудоемкость, для лучшего случая – блок с меньшей трудоемкостью. f_if=f₁+f_thenxp_then+f_elsex(1-p_then)

• Трудоемкость конструкции "Цикл" зависит от вида цикла. Для цикла с параметрами будет справедливой формула:f_for=1+3n+nf, где n – количество повторений тела цикла, f – трудоемкость тела цикла.

Реализация цикла с предусловием и с постусловием не меняет методики оценки его трудоемкости. На каждом проходе выполняется оценка трудоемкости условия, изменения параметров (при наличии) и тела цикла. Общие рекомендации для оценки циклов с условиями затруднительны. Так как в значительной степени зависят от исходных данных.

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

2. /*Генерация целочисленного массива числами с клавиатуры и вывод массива в строку*/

#include "stdafx.h"

#include <iostream>

#include <time.h>

using namespace std;

#define max 30

void gen (int k,int *pp);//прототип функции генерации массива

void out (int k,int x[max]);//прототип функции вывода массива

void BubbleSort (int k,int x[max]);

int _tmain(int argc, _TCHAR* argv[]){

int a[max],n,*p;

do { printf("\nВведите количество элементов массива n (n<=100):");

scanf ("%d",&n);

}

while (n>max); //проверка выхода за границы массива

p=a;

gen(n,p);

BubbleSort(n,a);

out(n,a);

system("pause");

return 0;

}//Описание функции генерации массива с клавиатуры

void gen(int k,int *pp){/*передача указателя как параметра позволяет вернуть

сформированный массив в основную программу*/

int i;

printf("\nВведите значения %d элементов массива: \n",k);

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

printf("x[%d]= ",i);

scanf("%d",pp++);

}

}//Описание функции вывода массива в строку

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

int i;

printf("\nВывод значений %d элементов массива в строку: \n",k);

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

printf("%d\t",x[i]);

}//Описание функции сортировки методом "пузырька"

void BubbleSort (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;

}

}

Екзаменаційний білет № 34

1. Рекурсия в широком смысле – это определение объекта посредством ссылки на себя. Рекурсия в программировании – это пошаговое разбиение задачи на подзадачи, подобные исходной.

Рекурсивный алгоритм – это алгоритм, в определении которого содержится прямой или косвенный вызов этого же алгоритма.

Для решения задач рекурсивными методами разрабатывают следующие этапы, образующие рекурсивную триаду:

• параметризация – выделяют параметры, которые используются для описания условия задачи, а затем в решении;

• база рекурсии – определяют тривиальный случай, при котором решение очевидно, то есть не требуется обращение функции к себе;

• декомпозиция – выражают общий случай через более простые подзадачи с измененными параметрами.

2.

#include "stdafx.h"

#include <iostream>

#include <iomanip>

#define n 4

using namespace std;

void random(int x[2*n][2*n])

{

int min=-100;

int max=100;

srand(time(NULL));

for(int i=0;i<2*n;i++)

{ for(int j=0;j<2*n;j++)

x[i][j]=rand()%(max-min+1)+min;

}

}

void vuvod(int x[2*n][2*n])

{ for(int i=0; i<2*n; i++)

{for(int j=0; j<2*n; j++)

{ printf("%5d",x[i][j]);

}

cout<<endl;

} cout<<endl;

}

void sort(int x[2*n][2*n])

{ int a=0;

for(int i=0;i<2*n;i++)

{

for(int o=0;o<2*n;o++)

{ for(int j=2*n-1;j>o;j--)

{ if(x[i][j-1]<x[i][j])

{ a=x[i][j-1];

x[i][j-1]=x[i][j];

x[i][j]=a;

} } } }}

void perest(int x[2*n][2*n])

{ int k=0;

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

{ for(int j=0;j<2*n;j++)

{k=x[2*n-i-1][j];

x[2*n-i-1][j]=x[i][2*n-j-1];

x[i][2*n-j-1]=k;

} }}

int _tmain(int argc, _TCHAR* argv[])

{ int a[2*n][2*n];

random(a);

vuvod(a);

sort(a);

vuvod(a);

perest(a);

vuvod(a);

return 0;

}

Екзаменаційний білет № 35

1. Рекурсивный алгоритм – это алгоритм, в описании которого прямо или косвенно содержится обращение к самому себе.

Пример. Для целого неотрицательного числа n найдите его факториал.

Разработаем рекурсивную триаду.

Параметризация: n – неотрицательное целое число.

База рекурсии: для n =0 факториал равен 1.

Декомпозиция: n!=(n-1)!xn.

long factor (int n) {

if (n<0) return 0; // для отрицательных чисел

if (n==0) return 1; // базовый случай: n=0

return factor(n-1)*n; // общий случай (декомпозиция)

}

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

2. //Инициализация структуры и вывод значений ее элементов

#include "stdafx.h"

#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[]) {

struct goods {

char* name;

long price;

float percent;

int vol;

char date[9];

};

struct goods coat={"пиджак черный",4000,7.5,220,"12.01.09"};

printf("\n Товар на складе:");

printf("\n Наименование: %s.", coat.name);

printf("\n Оптовая цена: %ld руб.", coat.price);

printf("\n Наценка: %3.1f %%.", coat.percent);

printf("\n Цена товара: %ld руб.",

(long)(coat.price*(1.0+coat.percent/100)));

printf("\n Объем партии: %d штук.", coat.vol);

printf("\n Дата поставки: %s.",coat.date);

system("pause");

return 0;

}

Екзаменаційний білет №36

1. Рекурсивный алгоритм – это алгоритм, в описании которого прямо или косвенно содержится обращение к самому себе. В технике процедурного программирования данное понятие распространяется на функцию, которая реализует решение отдельного блока задачи посредством вызова из своего тела других функций, в том числе и себя самой. Если при этом на очередном этапе работы функция организует обращение к самой себе, то такая функция является рекурсивной. Прямое обращение функции к самой себе предполагает, что в теле функции содержится вызов этой же функции, но с другим набором фактических параметров. Такой способ организации работы называется прямой рекурсией. Например, чтобы найти сумму первых n натуральных чисел, надо сумму первых (n-1) чисел сложить с числом n, то есть имеет место зависимость: S_n=S_n-1+n. При косвенном обращении функция содержит вызовы других функций из своего тела. При этом одна или несколько из вызываемых функций на определенном этапе обращаются к исходной функции с измененным набором входных параметров. Такая организация обращений называется косвенной рекурсией.

2. #include "stdafx.h"

#include <stdio.h>

#include <string.h>

#include <iostream>

using namespace std;

struct student {

char name[10];

char surname[15];

int age;

} stud;

//переменная stud объявлена как структура типа student

int _tmain(int argc, _TCHAR* argv[]) {

struct student *s; // указатель на структуру student

s=&stud; // инициализация указателя

strcpy(s->name,"Larry");

//обращение как к указателю на структуру

strcpy(s->surname,"Johnson");

(*s).age=34; //обращение как к переменной

printf("\n Имя: %s \n Фамилия: %s \n Возраст = %i",

s->name,s->surname,s->age);

system("pause");

return 0;

}

Екзаменаційний білет № 37

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

Идея этого метода заключается в следующем. Множество элементов просматривается последовательно в некотором порядке, гарантирующем, что будут просмотрены все элементы множества (например, слева направо). Если в ходе просмотра множества будет найден искомый элемент, просмотр прекращается с положительным результатом; если же будет просмотрено все множество, а элемент не будет найден, алгоритм должен выдать отрицательный результат.

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

Шаг 1. Полагаем, что значение переменной цикла i=0.

Шаг 2. Если значение элемента массива x[i] равно значению ключа key, то возвращаем значение, равное номеру искомого элемента, и алгоритм завершает работу. В противном случае значение переменной цикла увеличивается на единицу i=i+1.

Шаг 3. Если i<k, где k – число элементов массива x, то выполняется Шаг 2, в противном случае – работа алгоритма завершена и возвращается значение равное -1.

При наличии в массиве нескольких элементов со значением key данный алгоритм находит только первый из них (с наименьшим индексом).

int LinearSearch(int *x, int k, int key){

int i = 0;

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

if ( x[i] == key )

break;

return i < k ? i : -1;

}

2. #include "stdafx.h"

#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[]) {

struct s_tag { char c;

int i; double d;

} s_item;

union u_tag {

char c;

int i;

double d;

} u_item;

printf("Размер структуры = %d\n", sizeof(s_item));

printf("Размер объединения = %d\n", sizeof(u_item));

system("pause");

return 0;

}

Екзаменаційний білет № 38

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

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

Алгоритм Бойера и Мура – это алгоритм поиска подстроки в строке, при котором первоначально строится таблица смещений для искомой подстроки, проверка начинается с последнего символа подстроки после совмещения начала строки и подстроки.

Алгоритм Кнута, Морриса и Пратта – это алгоритм поиска подстроки в строке, при котором сдвиг подстроки выполняется на некоторое переменное количество символов.

Алгоритм прямого поиска – это алгоритм поиска подстроки в строке, при котором происходит посимвольное сравнение строки с подстрокой.

2. //Поиск множества неповторяющихся символов строки

#include "stdafx.h"

#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[]){

char st[80];

int i,j,flag,len;

printf("Введите строку: ");

gets(st);

len=strlen(st); //длина строки

printf("Неповторяющиеся символы строки образуют множество: ");

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

flag=0; //флаг проверки на совпадение

for (j=0;j<i;j++) //сравнение символа с предыдущими

if (st[i]==st[j]) flag=1;

if (flag==0)printf("%c",st[i]);

}

system("pause");

return 0;

}