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

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

• # Рассмотрим два способа представления матрицы размера 4×4. В первом случае используется массив из четырех элементов типа «массив из четырех элементов»: double a[4][4]; Во втором случае используется линейный массив из шестнадцати элементов: double a[16]; В первом случае обращение к элементу матрицы с индексами i, j осуществляется с помощью выражения a[i][j], во втором — с помощью выражения a[4*i + j]. Есть ли существенная разница в эффективности программы в первом и втором случаях при использовании оптимизирующего компилятора?
• # Выражение записано с использованием обратной польской записи: 1, 2, 3, +, *, 4, *, 5, * Чему равняется его значение?
• # В хеш-реализации множества хеш-функция принимает 10 различных значений с равной вероятностью. Пусть множество содержит 3 элемента. Какова вероятность коллизии? (Коллизией называется ситуация, когда у двух элементов значения хеш-функции совпадают.)
• # В какой аргумент помещается результат команды с двумя аргументами (например, сложения) при использовании Ассемблера "Masm" фирмы Microsoft для процессоров Intel 80x86?
• # Где располагаются глобальные переменные?