А.А. Белеванцев, С.С. Гайсарян, В.П. Иванников, Л.С. Корухова, В.А. Падарян - Задачи экзаменов по вводному курсу программирования (1113412), страница 5
Текст из файла (страница 5)
Для приведенного фрагмента Си-кода написать соответствующийфрагмент ассемблерной программы. static int *p[10]; static int x; x = *p[8] + 1; 4. Восстановите по приведенному ниже фрагменту ассемблернойреализации соответствующий фрагмент Си-кода. Необходимо правильнозаполнить пробелы, указав типы переменных, управляющие выраженияоператоров if и вычисляющихся в них выражений. mov ebx, dword [a] mov ecx, dword [b] cmp ebx, ecx 34 jg .L7 jl .L8 xor eax, eax jmp .L9 .L8: mov edx, dword [c] mov eax, edx sar edx, 31 sub ecx, ebx idiv ecx jmp .L9 .L7: mov edx, dword [c] mov eax, edx sar edx, 31 sub ebx, ecx idiv ebx .L9: mov dword [d], eax ... static _____________________ a; static _____________________ b; static _____________________ c; static _____________________ d; if (__________) { d = ________________; } else if (__________) { d = ________________; } else { d = ________________; } ... 355.
Напишите ассемблерную программу, проверяющую симметричностьстатического массива (N элементов типа int, N – константа, N < 220):одинаковые значения имеют первый и последний, второй ипредпоследний, и т.д. Выполнять ввод значений элементов массива ивыравнивать стек не требуется. Если массив симметричный, на выходе изфункции CMAIN регистр EAX должен иметь значение 0, в противномслучае – 1. Запрещается использовать строковые инструкции ииспользовать стек. Программа должна содержать не более 16инструкций. Учитываются все инструкции, включая ret.6.
В приведенном фрагменте Си-кода используются константы H и J.Исходя из построенного компилятором кода, восстановите значенияконстант H и J. int array1[H][J]; int array2[J][H]; void copy_array(int x, int y) { array2[y][x] = array1[x][y]; } copy_array: push ebp mov ebp, esp mov eax, dword [ebp + 8] mov edx, dword [ebp + 12] lea ecx, [eax + 4 * edx] lea eax, [edx + 8 * eax] mov eax, dword [array1 + 4 * eax] mov dword [array2 + 4 * ecx], eax pop ebp ret 7.
Тело Си-функции f, использующей соглашение cdecl, было переведенокомпилятором в следующий код. Восстановите объявление функции f. *b = x; return c ‐ y; movsx ecx, byte [ebp + 8] mov eax, dword [ebp + 16] mov ebx, dword [ebp + 20] mov edx, dword [ebp + 12] sub eax, ecx mov word [edx], bx 36 8. Используя соглашение cdecl, напишите на языке Ассемблерареализацию Си-функции seq.
Следует считать, что при вызове функцииseq стек уже выровнен по 16-байтной границе. int *seq(int size) { int *p = (int *) malloc(size * sizeof(int)); for (int i = 0; i < size; i++) { p[i] = i; } return p; } 9. а) нарисуйте схему логических вентилей, выполняющую сравнениедвух битовб) Оцените среднее время доступа для диска со следующимихарактеристикамиСкорость вращения 5 400 RPM Среднее время поиска дорожки 12 мс.Среднее количество секторов на дорожке 300. 10. а) Укажите верную последовательность вызова драйверомкомпилятора gcc служебных действий. Компоновщик, препроцессор, компилятор, ассемблер. Препроцессор, компилятор, ассемблер, компоновщик. Компилятор, ассемблер, препроцессор, компоновщик. Компоновщик, компилятор, ассемблер, препроцессор. Препроцессор, компилятор, компоновщик, ассемблер. б) В сборке Си-программы участвуют два приведенных ниже файла:f1.c и f2.c.
Отметьте верные высказывания. Ошибка компоновки: два сильных символа f. Ошибка компоновки: два сильных символа y. Запись в y (файл f2.c) меняет значение переменных y и z в файле f1.c. Запись в y (файл f2.c) меняет значение переменной y и не меняет z в файле f1.c. 37 Для переменных y будут отведены два различных места в памяти. Запись в x (файл f1.c) необязательно будет менять значение переменной x в файле f2.c. f1.c int x; int y = 7; int z; void f() { … } f2.c float x; double y; int f() { … } 383.ОТВЕТЫ, УКАЗАНИЯ И РЕШЕНИЯ3.1. ВАРИАНТ_1.
2012 г. ( “Алгоритмы иалгоритмические языки”)1. Диаграмма выглядит следующим образом:0r100l1rλ.L r.λ11λr01l0r2. Решение:void move_elts_keys (struct list **src,struct list **dst) {struct list *p, *q;/* p – предыдущий элемент,q – текущий */p = NULL; q = *src;while (q) {if (q->key % 2 == 0) {struct list *t = q->next; /* t – следующийиз исходного списка */q->next = *dst;*dst = q;/* Добавляем q в голову dst */if (p)p->next = t; /* Если был предыдущий,исправляем исходный список */else39*src = t;q = t;} else {p = q;q = q->next;/* Иначе меняем его голову *//* Следующий на обработку *//* Двигаем ссылки на текущийи предыдущий элементы */}}}3. Ответы:1) -1,y = -12) 1063) -210, x = 41, y = -2104) 1, y = 25) -64, x = 43, y = -1066) -105, x = -105, y=424.
Ответ: 1 4 1 3 15. Решение:switch (i) {case -1: j = i; break;case 1: case 2: case 3: j = 10 – i;default: abort ();}6. Решение:for (i = 0, pairs = 0; i < N – 1; i++)pairs += (a[i] % 2 != a[i+1] % 2 ? 1 : 0);7. Решение:int scalar (void) {int x, y, sum = 0;scanf ("%d", &x);40while (x) {scanf ("%d", &y);sum += (x*y);scanf ("%d", &x);}return sum;}8. Решение:void erase (char *s, const char *w) {char *olds = s;while (*s) {char *p = s; char c;while (isalpha (*p))p++;/* Теперь между s и p первое слово, p указываетна пробел или 0-терминатор */c = *p; *p = '\0'; /* чтобы можно былоиспользовать strstr */if (strstr (s, w)) {/* удаляем слово сдвигом конца строки вначало, также можно использовать memmove */if (c == '\0') {/* удаляемое слово было последним, надозаписать 0-терминатор или сразу в s,или стереть предыдущий пробел, если текущееслово не первое */if (s > olds)s--;*s = 0;}else {char *q = s;*p = c; /* вернем стертый символ, это будетпробел */p++; /* слово было не последнее, значит,41это можно делать */do {*q++ = *p++;} while (*(p – 1)); /* Копируем и нулевойсимвол тоже */}} else {*p = c; /* вернем стертый символ, это будетпробел или 0-терминатор */s = *p ? p + 1 : p; /* если пробел, топропустим его */}}}9.
Решение: необходимо построить дерево Фибоначчи заданной высоты.static struct avltree *build_rec (int h, int min, int*p) {struct avltree *t = (struct avltree *) malloc(sizeof (struct avltree));int last;if (h == 1) { /* листовое дерево */t->left = t->right = NULL;t->x = min;*p = min + 1;return t;}t->left = build_rec (h – 1, min, &last);t->x = last++; /* Левый сын занял от 1 доlast–1 элементов, корень – last */if (h == 2)t->right = NULL; /* Правый сын нулевой */elset->right = build_rec (h – 2, last, &last);*p = last;return t;42}struct avltree *build (int h) {int last;return build_rec (h, 1, &last);}10.
Результирующее дерево:3.2. ВАРИАНТ_2. 2012 г. (“Алгоритмы и алгоритмическиеязыки”)1. Заданная диаграмма описывает машину Тьюринга,которая инвертирует каждый второй символ из парысимволов, пары отсчитываются, начиная от первогосимвола слова. Предлагаемый алгоритм Маркова:*1→1#*0→0##0→1*#1→0*#*→*2. Приведем одно из решений (возможно также значительно болеекороткое решение):struct list * merge_lists (struct list *l1, structlist *l2) {43/* явно держим указатель на выходнойсписок и вставляем по очереди */struct list *p = NULL, *h = NULL;int flag = 1;while (l1 || l2) {struct list *q = flag ? l1 : l2;if (p)p->next = q, p = p->next;elsep = h = q;/* обязательно в таком порядке */if (flag)l1 = l1->next;elsel2 = l2->next;p->next = NULL;flag = 1 – flag;}/* не забываем про конец списка */if (l1 || l2) {if (p)p->next = l1 ? l1 : l2;elseh = l1 ? l1 : l2;}return h;}3.
Ответы:1) -8, x= 12, y = -8442) 913) -160, x = -10, y = -1604) ошибка5) -70, x = 12, y = -816) -69, x= 114. Ответ: 3 2 0 0 08 15. Решение:int sum = 0, ineg = 0, ipos = N – 1, i;/* внешний цикл может быть бесконечным */for (i = 0; i < N/2; i++) {for (; ineg < N && a[ineg] >= 0; ineg++);for (; ipos >= 0 && a[ipos] <= 0; ipos--);if (ineg == N || ipos == -1)break;sum += a[ineg++]*a[ipos--];}6.
Решение:void large_sons (struct tree *t) {if (!t)return;if (t->left && t->left->key > t->key)printf ("%d\n", t->left->key);if (t->right && t->right->key > t->key)printf ("%d\n", t->right->key);large_sons (t->left);large_sons (t->right);45}7. Решение:int count (const char *s) {int res = 0, len = strlen (s) - 3, i;for (i = 0; i < len; i++)if (s[i] == '2' && s[i+1] == '0'&& s[i+2] == '1' && s[i+3] == '2')res++;return res;}8. Результирующее дерево показано на рисунке.3.3. Коллоквиум №2.
2012 г. ( “Алгоритмы иалгоритмические языки”)1. Ответы:1) 22) 32771 или 0x80033) 65534 или 0xFFFE, m = 655344) -18, s.p.x = -185) 186) 4, p = &a[1], pp = &p467) ошибка – *pp + y + a[2] = &a[12], разыменовывать этотуказатель нельзя, т.к. в массиве a 10 элементов8) 20, s.p.y = 20, p = &a[9]2. Решение:struct str {char *s;int cnt;};struct str *task2 (char ** a) {int i, j, n = 0, sz = 0;struct str *out = NULL;/* Строим массив структур */for (; *a; a++) {for (i = 0; i < n; i++)if (! strcmp (*a, out[i].s)) {out[i].cnt++;break;}if (i >= n) {/* Встретили новую строку */if (i >= sz) {out = realloc (out, 2 * sz + 1);sz = 2 * sz + 1;}out[n].s = strdup (*a);out[n++].cnt = 1;}}/* Сортируем массив */for (i = 0; i < n - 1; i++)for (j = i + 1; j < n; j++)if (out[i].cnt < out[j].cnt|| strcmp (out[i].s, out[j].s) > 0) {struct str tmp = out[i];47out[i] = out[j];out[j] = tmp;}return out;}3.
Решение:struct list {int key;struct list *next;};void remove_odd (struct list **pl) {int num = 1;struct list *p = *pl, *q = NULL;while (p) {if (num % 2 == 1) {struct list *t = p;if (!q)/* Удаляем первый элемент*/*pl = p->next;else/* Сдвигаем ссылку с предыдущего */q->next = p->next;p = p->next;free (t);} else {q = p;p = p->next;}num++;}}4. Решение:struct tree {int key;48struct tree *left, *right;};struct tree *build_tree (int *a, int i, int n) {struct tree *t;if (i >= n)return NULL;t = (struct tree *) malloc(sizeof (struct tree));t->key = a[i];t->left = build_tree (a, 2*i + 1, n);t->right = build_tree (a, 2*i + 2, n);return t;}/* Функция проверяет, все ли вершины поддерева Tвходят в необходимый диапазон значений */int is_bin (struct tree *t, int *pmin, int *pmax) {int ans = 1;if (!t)return ans;/* Нулевое значение указателя означает отсутствиесоответствующего ограничения */if ((pmin && t->key <= *pmin)|| (pmax && t->key >= *pmax))return 0;ans = is_bin (t->left, pmin, &t->key);ans = ans && is_bin (t->right, &t->key, pmax);return ans;}struct tree *task4 (int *a, int n, int *pbin) {struct tree * t = build_tree (a, 0, n);*pbin = is_bin (t, NULL, NULL);return t;}493.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
