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