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

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

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

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

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

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

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

ВАРИАНТ_1. 2011 г. ( “Алгоритмы иалгоритмические языки”)1. а) Определение: два алгоритма эквивалентны в алфавите А (намножестве слов из алфавита А), если:*они одновременно либо- на одинаковых словах из Aостанавливаются, либо зацикливаются (т.е. области ихприменимости совпадают); и для любого слова из областиприменимости их результаты совпадают.Другие варианты ответа а1) . Возможно и такое определениеэквивалентности - Два алгоритма, заданные в алфавите А,эквивалентны, если их области применимости совпадают, и для любогослова из области применимости эти алгоритмы получают одинаковыйрезультат.a2). Два алгоритма, заданные в алфавите А, эквивалентны, если ониреализуют одно и то же преобразование (отображение) на множестве***слов A ( A → A )1.

б) Ответ: ДА.1. в) Обоснование: алгоритмы Т1 и Т2 применимы только к пустомуслову, которое они и выдают в качестве ответа, а на любом непустомслове из алфавита {a, b} они зацикливаются (правда, зацикливаются поразному, но это не играет никакой роли).2. Возможны различные решения задачи (но использование рекурсииобязательно), приведем два варианта решения :Вариант 2.1:voidinsert(struct list **L, int x) {struct list *p;if (*L == NULL || (*L)->key > x) {// вставка в началоp = malloc(sizeof(*p));p->key = x;p->next = *L;*L = p;} else {insert(&((*L)->next), x);50}}// Вызовinsert(&А, 5);Вариант 2.2struct list *insert(struct list *L, int x) {struct list *p;if (L == NULL || L->key > x) {// вставка в началоp = malloc(sizeof(*p));p->key = x;p->next = L;L = p;} else {L->next = insert(L->next, x);}return L;}// Вызов:А = insert(А, 5);3.

Ответы1) 2, x :=11, y :=22) 14 , x :=143) 11, x :=11, y :=14) 205) 0, x :=06) 30, x :=304. Ответ:1 4 5 1 25. Решение:Пояснение. В непустом АВЛ-дереве у каждой вершины разность высотеё левого и правого поддеревьев должна равняться 0 или ±1 (какследствие, в АВЛ-дереве любое поддерево – АВЛ-дерево).51Для каждой вершины надо проверять две вещи:1) являются ли её левое и правое поддеревья АВЛ-деревьями;2) модуль разности высот этих поддеревьев ≤ 1.)Вариант решенияintheight(struct tree *T) {int hleft, hright;if (T == NULL) return 0;hleft = height(T->left);hright = height(T->right);return 1 + ((hleft > hright) ? hleft : hright);}int abs(int x) {return (x >= 0)? x : -x;}int is_avl(struct tree *T) {if (T == NULL) return 1;if (abs(height(T->left) – height(T->right)) > 1)return 0;return is_avl(T->left) && is_avl(T->right);}6.

Ответ: Неверно (или нет).Объяснение: – в сумме будет отсутствовать число 1007. Заданный : алгоритм неприменим к словам, где нет c, но и при этоместь a или b.а): Алгоритм применим к заданному слову в алфавите, если оностановится (не зациклится), начав работу над этим словом. ccbbб): aa 8. Ответы : а) Верноб) Неверно (нет)в) Верно529. Порядок занесения ключей в таблицу Т1 такой: 19, 6, 23, 27, 18.Ответ:АдресТ1Т20612323404271423782791855106366191911121810.

Ответ: нетОбоснование:Число вершин в дереве Фибоначчи высоты h равно nf(h) = F h+2 -1 (где Fh+2- число Фибоначчи с номером h+2). Дерево Фибоначчи является АВЛдеревом с минимальным числом вершин при заданной высоте h.1) Любое поддерево в дереве Фибоначчи (д.Ф.) является д.Ф.2) Для любого д.Ф. высоты h верна формула N0=0, N1=1, Nh=Nh-1+Nh-2+1,где Nh, Nh-1 и Nh-2 – число вершин соответственно в самом этом дереве и вего поддеревьях.3) Поэтому заданный вопрос эквивалентен вопросу о том, есть ли такоеh10, для которого выполняется условие Nh-1–Nh-2>50.4) Поскольку N0=0, N1=1, N2=2, N3=4, N4=7, N5=12, N6=20, N7=33,N8=54, N9=88, N10=143, …то наибольшее значение разности Nh-1–Nh-2 при h10 равно N9–N8=88–54=34<50, поэтому такого значения h нет3.5.

ВАРИАНТ_1. 2012 г. ( “Архитектура ЭВМ и языкассемблера”)1.Ответы:А) 0xffffee10Б) 0xffee102aВ) 0x00102a002.Решение:static signed char **a;  static int b;  53static short c;  c = (*a)[4 * b]; Альтернативный вариантвыражение:c = *((*a) + 4 * b);решения,не3. Решение:#define N ...  static int a[N];  static int b[N];  static int c[N];  static int d;      for (int i = 0; i < d; i++) {       c[i] = a[i] + b[i];       if (c[i] < 0) {          c[i] = ‐c[i];       }   } 4. Ответы:А) 28Б) 24Решение:В)mov byte [o + 18], 0Г)mov eax, dword [po] mov eax, dword [eax + 4]  mov dword [x], eax5.Решение:int f(int*  v,  54использующийиндексное      int*        int         unsigned char    *w = y << x;    *v = y;    return *w; w,  y,  x) { }6.

Решение:section .rodata    fmt1 db “%hd”, 0    fmt2 db `%d\n`, 0  section .text g: push ebp    mov epb, esp    sub esp, 24    mov [esp], fmt1    mov eax, [ebp+8]    mov [esp+4], eax    call scanf    mov [ebp‐4], eax    mov [esp+4], eax    mov [esp], fmt2    call printf    mov eax, [ebp‐4]    mov esp, ebp    pop ebp    ret 7. Решение:   inc dword [a]    mov eax, dword [a]    je .1    mov eax, dword [b]    cdq    idiv dword [a]     mov dword [c], eax    test eax, eax    cmovnz eax, 1 .1: 558.

Решение:   mov esi, dword [a]     mov edi, dword [b]     mov ecx, 16  .1:mov ax, word [esi]    mov dx, word [edi]    add esi, 2    add edi, 2    dec ecx    cmp ax, dx     jecxz .2    jne .1 .2 Альтернативный вариант решения, использующий инструкцию loopne.   mov esi, [a]     mov edi, [b]     mov ecx, 16  .1:mov ax, [esi]    cmp ax, [edi]    lea esi, [esi+2]    lea edi, [edi+2]    loopne .1 9.Ответ:ЧислоНаибольшее нормализованноеНаименьшееденормализованное2/513Битовое представление0_110_11111_000_11110_001_10100_110_101010.

Ответ:АдресПромах/Попаданиепромахпопаданиепромахпромах 2 = 00010b   3 = 00011b   8 = 01000b  16 = 10000b  56промахпромахпопадание29 = 11101b   8 = 01000b  28 = 11100b 3.6. Коллоквиум №1. 2012 г. ( “Архитектура ЭВМ и языкассемблера”)1. Ответ: AL = 0x2E (16-ричн.), 46 (10-тичн. зн.), 46 (10-тичн.

б./зн.)CF = 1, OF = 1, ZF = 0, SF = 02. Ответ: EAX = 0xFFFF00793. Решение:static int a;  static int b;  static short c;  static short d;   a = a – (a*b‐d)/c;  4. Решение:static int  a;  static int **b;  static int c;   c = *((*b) ‐ a);  Для вычисляемого выражения допустима и такая форма записи:c = (*b)[‐a]; 5. Решение:#define N   16  #define C 1024      static int a[N];    static int sum;     sum = 0;    for (int i = 0; i != N; i++) { 57      if (a[i] > C) {          a[i] = C;       }       sum += a[i];    } 6.

Решение:   INC DWORD [B]    MOV EAX, DWORD[B]    MOV DWORD [A], EAX     TEST EAX, EAX     JZ .END    MOV EAX, DWORD [C]     IMUL EAX, EAX, 7     MOV DWORD [C], EAX     TEST EAX, EAX    JZ .END    MOV EAX, 1 .END: 3.7. Коллоквиум №2. 2012 г. ( “Архитектура ЭВМ и языкассемблера”)1. Поскольку в условии указана ОС Windows и в union  i_faceприсутствует поле типа double, выравнивание для union  i_face и длявсей структуры gadget будет выполняться по границе в 8 байт.Ответ:А) sizeof(struct gadget) = 24Б) Смещение поля prototype = 16В) sizeof(union i_face) = 8Г) Смещение поля magic = 82. Ответ:   int** f(signed char a,                    int* d ,                   short b ,                   int** c) {       *c = d ‐ a;       *d = b;       return c; 58   }3.

Решение:f: MOV EAX, ECX ; первый параметр   MOV ECX, EDX ; второй параметр   CDQ  IDIV ECX  SHR EAX, 10  RET 4. Решение:section .rodata g.fstr db ‘%d %d’, 0   section .text CEXTERN scanf  g: PUSH EBP  MOV EBP, ESP  SUB ESP, 24        ; общий размер фрейма 32 байта   MOV DWORD [ESP], g.fstr        ; форматная строка   LEA EAX, DWORD [EBP‐4]                      ; tmp   MOV DWORD [ESP+4], EAX  MOV EAX, DWORD [EBP+8]                        ; p   MOV DWORD [ESP+8], EAX  CALL scanf   MOV EAX, DWORD [EBP+8]  MOV EAX, DWORD [EAX]  SUB EAX, DWORD [EBP‐4]  MOV ESP, EBP   POP EBP  RET 5. Ответ:А) ESI = 0x40C8Б) EDI = 0x40B8В) ECX = 146. Ответ:Описание Ноль Наибольшее Точное значениеБитовое представление 0.0 0_0000_00000 (63/32)*(2^7)=252  0_1110_11111 59нормализованное Наименьшее положительное 1/3 (1/32)*(1/64)= 2^(‐11) 21*2^(‐6) 0_0000_00001 0_0101_01010 В рамках данной кодировки нечетные номера групп не могут быть точнопредставлены.

Ниже приведен ответ, где для таких номеров выполненоокругление к наименьшему представимому числу.Группа №101 Группы №№102 и 103 Группы №№104 и 105 Группа №106 100.0 102.0 104.0 106.0 0_1101_10010 0_1101_10011 0_1101_10100 0_1101_10101 3.8. ВАРИАНТ_1. 2011 г. ( “Архитектура ЭВМ и языкассемблера”)1. Ответ:а) AL = 7С (16-ричн.), 124 (10-тичн. б/зн.), 124 (10-тичн. зн.)CF = 1, SF = 0, OF = 1, ZF = 0.б) AL = FA (16-ричн.), 250 (10-тичн. б/зн.), -6 (10-тичн.

зн.)CF = 1, SF = 1, OF = 0, ZF = 0.2. Ответ:EAX = 0xDDE3. Решение:MOV EAX, DWORD [p + 32] MOV EAX, DWORD [EAX] INC EAX MOV DWORD [x], EAX 4. Решение:   static int a;    static int b;    static int c;    static int d;    if (a > b) {       d = c / (a ‐ b);    } else if (a < b) { 60      d = c / (b ‐ a);    } else {       d = 0;    } 5. Решение:section .bss    a resd N  section .text CMAIN:    XOR ECX, ECX     MOV EBX, N‐1  .loop:    MOV EAX, DWORD [A+4*ECX]    CMP EAX, DWORD [A+4*EBX]    JNE .set_false     INC ECX    DEC EBX    CMP ECX, EBX    JL .loop    MOV EAX, 0    JMP .end .set_false:    MOV EAX, 1 .end:    RET 6.

Ответ:H = 4, J = 87. Решение:int f(signed char y, short *b, int c, int x);  Помимо приведенного решения, для переменных b и x допустим типunsigned; для переменной x – тип short8. Решение:CEXTERN malloc  seq:    PUSH EBP    MOV EBP, ESP 61   SUB ESP, 8     ; общий размер фрейма 16 байт     MOV EDX, DWORD [EBP+8]    MOV EAX, EDX    SAL EAX, 2    MOV [ESP], EAX    CALL MALLOC     XOR ECX, ECX  .loop:    MOV DWORD [EAX+4*ECX], ECX    INC ECX    CMP ECX, EDX    JL .loop    MOVE SP, EBP    POP EBP    RET 9. Ответы:а)Помимо того, допустима реализация сравнения двух битов с применениемэлемента Xor.б) Tдоступа = Tср. поиск + Tср. вращения + Tср.

передачаTср. вращения = 1/2 x 1/RPM x 60 с / 1 мин.62Tср. передача = 1/RPM x 1/(ср. # секторов на дорожке) x 60 с./1 мин.Tдоступа = 12 + 5,(5) + 0,(037) = 17,593 мкс.10. Ответы:а) Препроцессор, компилятор, ассемблер, компоновщик.б) Ошибка компоновки: два сильных символа f.Запись в y (файл f2.c) меняет значение переменной y в файле f1.c.63СОДЕРЖАНИЕВВЕДЕНИЕ ............................................................................................... 31.ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ ПО КУРСУ ................ 41.1.

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