Пусть a — вещественный массив размера n (индекс элементов меняется от 0 до n-1). Определить, содержит ли следующий фрагмент программы ошибку (т.е. действительно ли тело цикла сохраняет инвариант): // Программа Быстрая сортировка дано: цел n; вещ a[n]; // вещественный массив размера n цел m; // индекс медианы утверждение: n >= 2 и 0 <= m и m < n; надо: // разделить массив на три части: // 1) слева элементы, меньшие медианы; // 2) в центре медиана; // 3) справа элементы, большие или равные медиане. цел i, j, k; вещ t; i := (-1); j := n; цикл пока i+1 < m или m < j-1 | инвариант: a[0], a[1], ..., a[i] < a[m] и | a[m] <= a[j], a[j+1], ..., a[n-1] и | i < m и m < j | | если i+1 < m | | то | | если a[i+1] < a[m] | | | то i := i+1; // расширяем левую часть | | иначе если j-1 > m | | | иначе | | | утверждение: a[i+1] >= a[m]; | | | // меняем местами элементы a[i+1] и a[j-1] | | | t := a[i+1]; a[i+1] := a[j-1]; a[j-1] := t; | | | если j-1 == m | | | | то m := i+1; // новое положение медианы | | | конец если | | | j := j-1; // расширяем правую часть | | конец если | | иначе | | утверждение: j-1 > m; | | . . . // этот случай рассматривается аналогично | | . . . // случаю i+1 < m | | | конец если конец цикла утверждение: 0 <= m и m < n и a[0], a[1], ..., a[m-1] < a[m] и a[m] <= a[m+1], a[m+2], ..., a[n-1]

Правильный ответ:

• # Пусть в красно-черном дереве число черных вершин (не включая внешние, или нулевые, вершины) равно 21. Какое максимальное количество красных вершин может быть в дереве?
• # Как нумеруются биты внутри байта или машинного слова?
• # Пусть регистр EBX содержит адрес массива целых чисел, регистр ECX — количество элементов массива. Указать, что будет содержать регистр EAX в результате выполнения следующего фрагмента кода на Ассемблере "Masm" для процессора Intel 80x86: mov EAX, 2147483647 ; EAX := плюс бесконечность L1: ; метка начала цикла cmp ECX, 0 ; сравнить ECX с нулем jle L2 ; переход, если меньше или равно mov EDX, [EBX] ; EDX := число с адресом EBX cmp EDX, EAX ; сравнить EDX с EAX jge L3 ; переход, если больше или равно mov EAX, EDX ; EAX := EDX L3: ; add EBX, 4 ; EBX := EBX+4 dec ECX ; уменьшить ECX jmp L1 ; переход на метку L1 L2: ; метка конца цикла
• # Являются ли локальные переменные функции общими для разных нитей (threads), работающих параллельно в рамках одного процесса?
• # Пусть описан тип R2Vector, представляющий вектор на плоскости с вещественными координатами, typedef struct { double x; double y; } R2Vector; также описаны три переменные u, v и w типа вектор и вещественная переменная s: R2Vector u, v, w; double s; при этом переменная u содержат конкретный вектор единичной длины, а вектор v получается из u вращением на 30 градусов по часовой стрелке. Указать, чему будет приблизительно равно значение вещественной переменной s в результате выполнения следующего фрагмента программы: w.x = (-u.y); w.y = u.x; s = v.x * w.x + v.y * w.y;