А.А. Белеванцев, С.С. Гайсарян, В.П. Иванников, Л.С. Корухова, В.А. Падарян - Задачи экзаменов по вводному курсу программирования, страница 6
Описание файла
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.а): Алгоритм применим к заданному слову в алфавите, если оностановится (не зациклится), начав работу над этим словом. ccbbб): aa 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) Поэтому заданный вопрос эквивалентен вопросу о том, есть ли такоеh10, для которого выполняется условие 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 при h10 равно 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.
