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

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

PDF-файл А.А. Белеванцев, С.С. Гайсарян, В.П. Иванников, Л.С. Корухова, В.А. Падарян - Задачи экзаменов по вводному курсу программирования, страница 5 Алгоритмы и алгоритмические языки (36714): Книга - 1 семестрА.А. Белеванцев, С.С. Гайсарян, В.П. Иванников, Л.С. Корухова, В.А. Падарян - Задачи экзаменов по вводному курсу программирования: Алгоритмы и алгори2019-04-24СтудИзба

Описание файла

PDF-файл из архива "А.А. Белеванцев, С.С. Гайсарян, В.П. Иванников, Л.С. Корухова, В.А. Падарян - Задачи экзаменов по вводному курсу программирования", который расположен в категории "". Всё это находится в предмете "алгоритмы и алгоритмические языки" из 1 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 5 страницы из PDF

Для приведенного фрагмента Си-кода написать соответствующийфрагмент ассемблерной программы.    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.

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5288
Авторов
на СтудИзбе
417
Средний доход
с одного платного файла
Обучение Подробнее