А.А. Белеванцев, С.С. Гайсарян, В.П. Иванников, Л.С. Корухова, В.А. Падарян - Задачи экзаменов по вводному курсу программирования, страница 3

Относительный порядок всех остальныхслов должен остаться неизменным. Измененная таким образом строка sдолжна удовлетворять всем тем же ограничениям, что и входная. Памятьпод все временные массивы должна выделяться динамически иосвобождаться в конце работы функции.9. Дано описание:structavltree*right;};Напишите функцию{intx;16structavltree*left,struct avltree *build (int h),которая строит АВЛ-дерево заданной высоты h, содержащее минимальноеколичество узлов n из всех АВЛ-деревьев с этой высотой. Значенияключей в элементах АВЛ-дерева должны быть от 1 до n.10.

Нарисуйте дерево цифрового поиска для алфавита{В, М, И, К}, которое содержит следующие ключи: КИМ, МИКИ, ВИМ, ИМ,ИК, ВК, МИМ, ВМК, В, МИ, ВМИК, МИМИ.2.2. ВАРИАНТ_2. 2012 г. ( “Алгоритмы иалгоритмические языки”)1. Напишите нормальный алгоритмМаркова (не более 7 правилподстановки),эквивалентныйзаданной диаграмме Тьюринга надалфавитом А2={0, 1}. Диаграммаиспользует элементарные машины l,r, L, R, символ (сдвиг головки наодну ячейку влево/вправо, сдвигголовки на одно слово влево/вправо,запись символа в ячейку, соответственно). В начале работы головка МТрасположена сразу после входного слова.2.

Дано описание:struct list {int key; struct list *next;};Напишите функциюstruct list * merge_lists(struct list *l1,struct list *l2),которая объединяет два списка, вставляя элементы списка l2 междуэлементами списка l1: результирующий список состоит из первогоэлемента списка l1, первого элемента списка l2, второго элемента спискаl1, второго элемента списка l2 и т.д. Если элементы одного из списковзакончились, далее в результирующем списке должны идти элементыдругого списка по порядку. Функция возвращает указатель на головурезультирующего списка. Считайте, что заголовочного элемента в обоих17списках нет, списки могут быть как пустыми, так и непустыми.Дополнительную динамическую память выделять запрещается.3.

Пусть int x = 11; int y = -80;Для каждого из 6 отдельных независимых выражений указать егозначение и побочные эффекты (если они есть) либо “ошибка”, есливыражение ошибочно.1) y %= ++x2) x | (-y ^ 1)3) y <<= (x -= 10) && (x -= 11)4) x++ + --x5) x++ + --y6) x++, --x, x + x, y + x4.

Что будет напечатано при выполнении программы:#include <stdio.h>int x = 5, y = 2;int a[5] = { 1, 2, 3 };int f (int *p, int *q) {static int a = 3;if (--a)return *p++ += *q--;return *q++ -= *p--;}int main (void) {int x = 2 * a[--y], b = 0;for (int y = x; y >= b; --y, ++x)b = f (a + b, a + y);printf ("%d %d %d %d %d\n",a[0], a[1], a[2], a[3], a[4]);printf ("%d %d\n", x, y);return 0;}185. С использованием оператора цикла for (возможно, нескольких)напишите фрагмент программы, который по заданному массивуint a[N] формирует в переменной sum суммуx yi i,iгде xi – i-й отрицательный элемент массива a, считая от начала массива, а yi– i-й положительный элемент массива a, считая от конца массива.Количество положительных и отрицательных элементов в массиве aодинаково и больше нуля.

Операторы перехода и другие операторы циклаиспользовать запрещено.6. Дано описание:struct tree {int key; struct tree *left, *right;}; Неиспользуя операторы цикла и перехода, глобальные и статическиепеременные, напишите функциюvoid large_sons (struct tree *t),которая печатает на стандартный поток вывода ключи тех элементов издвоичного дерева t, ключи которых больше, чем ключи их родителей.Дерево t может быть как пусто, так и не пусто.

Для корня дерева ничегопечатать не нужно.7. Напишите функциюint count (const char *s),которая подсчитывает все вхождения подстроки 2012 в строку s(например, для строки "28012012-пересдача" функция должнавернуть 1). Строка s может состоять из любых символов и быть какпустой, так и не пустой. Размер требуемой для функции памяти не должензависеть от длины строки.8. В соответствии с алгоритмом вставки ибалансировки АВЛ-деревьев, вставьте вуказанное АВЛ-дерево вершину с ключом 5.Нарисуйте полученное АВЛ-дерево и укажитедля каждой вершины этого дерева показательсбалансированности.192.3. Коллоквиум №2. 2012 г. (“Алгоритмы иалгоритмические языки”)1. Пусть определены следующие переменные:int x = 2, y = 4, z = 6;short n = 0x7FFF; unsigned short m = 0x7FFFU;struct S { struct P { int x, y; } p; struct S *n; } s= { { -10, -20 }, &s };unsigned int a[10] = { 2, 4, 6, 8, 10, 12, 14, 16,18, 20 };unsigned int *p, **pp;Для каждого из 8 отдельных независимых выражений указать егозначение и побочные эффекты (если они есть) либо “ошибка”, есливыражение ошибочно.1) x | y ^ z2) n + 43) m <<= 14) s.p.x = x + s.n->p.y5) *(a + 4 * x)6) p = a + 1, **(pp = &p)7) *pp = &a[2], *(*pp + y + a[2])8) p = a + a[3], s.p.y = ++p - aУКАЗАНИЕ.В задачах 2-4 определите все необходимые переменные и типы.Считайте, что вызовы функций выделения памяти всегда заканчиваютсяуспешно.2.

Напишите функцию, принимающую единственный параметр – массивстрок (указателей типа char *). Последний элемент массива содержитнулевой указатель. Функция должна возвратить указатель наразмещенный в динамической памяти массив структур, в которых первоеполе есть указатель на копию одной из входных строк, а второе поле –количество раз, которое данная строка встречалась во входном массиве (с20учетом регистра символов).

Одинаковые строки (с учетом регистрасимволов) должны содержаться в выходном массиве только в одномэкземпляре, поле с указателем может указывать на любую из них.Выходной массив должен быть отсортирован сначала по убыванию повторому полю, а затем в лексикографическом порядке по первому полю.3. Напишите функцию, которая удаляет из односвязного списка всеэлементы с нечетными номерами. Порядок следования всех остальныхэлементов должен остаться неизменным.

Память, занятая удаляемымиэлементами списка, должна быть освобождена с помощью вызовафункции free. Считайте, что заголовочного элемента в списке нет иэлементы списка нумеруются с 1. Ваша функция должна соответствоватьпрототипуvoid remove_odd (struct list **);где struct list описывает элемент списка с целочисленным ключом.4. Напишите функцию, принимающую три параметра – массив целыхчисел, его длину и указатель на целое число.

Элементы массива образуют(возможно пустое) двоичное дерево (для элемента a[i] его детьми вдвоичном дереве являются элементы a[2*i+1] и a[2*i+2], элементa[0] – корень дерева). Функция должна возвратить указатель напостроенное в динамической памяти (в виде рекурсивной ссылочнойструктуры) двоичное дерево, в котором для каждого узла детьмиявляются те же числа, что и во входном массиве (или нулевой указательдля пустого дерева). По указателю, который является третьимпараметром, необходимо записать 1, если построенное дерево являетсядвоичным деревом поиска, и 0 в противном случае.2.4.

ВАРИАНТ_1. 2011 г. (“Алгоритмы иалгоритмические языки”)1. а) Дать определение эквивалентности двух алгоритмов в некоторомалфавите.б)Ответитьнавопрос: abэквивалентны ли в алфавите {a, b} T1: указанныесправанормальныеbaалгоритмы T1 и T2?в) Обосновать ответ на вопрос б).21 a  aaT2:  b  bb2.

Дано описание:struct list { int key; struct list *next; } *A;Не используя операторы цикла и перехода, а также глобальные истатические (static) переменные, описать функцию insert(L, x), котораявставляет в упорядоченный по возрастанию ключей список L, новыйэлемент, имеющий в поле key ключ х (x – целое, не содержащееся ранее всписке).

После вставки список остается упорядоченным по возрастанию.Список L – однонаправленный, некольцевой, без заглавного звена; звеньясписка имеют тип struct list, все ключи – различны. Выписать такжепример вызова функции для вставки в описанный выше список А ключа5.3. Пусть int x = 10 ; int y = 20;Для каждого из 6 отдельных выражений указать его значение и побочныеэффекты (если они есть) либо “ошибка”, если выражение ошибочно.1) x +=(y = 1), y = 22) x ^= (x & y) + 43) x +=((y=1)||(y=2))4) !x ? x : y5) x %= y / 46) x += y++4. Что будет напечатано при выполнении программы:#include <stdio.h>int a[] = {1, 2, 3}; int b = 0, c = 2;int p (int *a, int x) {static int c = 3;b = *++a; *a = b + x;return --c;}int main (void) {int i, b = c;22for (i = 0; i < b; ++i)b = p (a + i, b);printf ("%d %d %d %d %d\n",a[0], a[1], a[2], b, c);return 0;}5.

Дано описание:struct tree { int x; struct tree *left, *right; };Не используя операторы цикла и перехода, а также глобальные истатические (static) переменные, описать функциюint is_avl (struct tree *T),которая возвращает ненулевое значение, если заданное двоичное деревопоиска Т является АВЛ-деревом, и ноль – в противном случае.Разрешается описывать дополнительные функции (с соблюдением тех жеограничений). Исходное дерево Т портить запрещается.6. Верно ли решена задача: «найти сумму первых 100 натуральныхчисел»? Если неверно – объяснить, почему.for (i = 0, sum = 0; i++, i < 100; sum += i);7. а) Дайте определение применимости алгоритма к словув алфавите.б) Напишите нормальный алгоритм Маркова, в которомне более 4 формул подстановки и который применим ктем и только тем словам в алфавите {a,b,c}, к которымнеприменим алгоритм, указанный слева.cc bb a  a8. Верно ли утверждение: «действие оператора continue; в приведенныхниже примерах эквивалентно действию оператора goto next; » (здесь E,E1, E2, E3 - выражения допустимого в этом случае типа ; S произвольный оператора) while (E) {S; for (E1; E2; E3){S; continue; S; next: ;} S;}б) do { S; continue; S; } while (E); next: ;в) for ( E1; E2; E3) { S; continue; S; next: ;}9.