Алгоритмы и сложность в C — бесплатный тест онлайн

Вопрос 1 из 30

Почему компаратор `return *(int*)a - *(int*)b;` ненадёжен?

int cmp(const void *a,const void *b){
  int x=*(const int*)a, y=*(const int*)b;
  return x-y;
}

Переполнение возможно только при равных значениях, когда компаратор возвращает ноль Разность сохраняет правильный знак, но одинаковые ключи могут нарушить транзитивность сравнения Разность может переполниться, и знак результата перестанет отражать порядок значений Компаратор ненадёжен, потому что стандарт требует нормировать результат строго к значениям -1, 0 и 1 Проблема возникает из-за чтения через `const int *`: компаратор обязан сначала копировать значения через `memcpy`

Вопрос 2 из 30

Какое свойство сортировки важно, если записи уже упорядочены по вторичному ключу?

/* сначала сортировка по фамилии, затем по отделу */
stable_sort(records,n,by_department);

Устойчивость Обязательная O(1) память Рекурсивность Случайность Работа без сравнений

Вопрос 3 из 30

Функция `partition` возвращает окончательный индекс опорного элемента `p`, а границы `lo` и `hi` включены. Что неверно в рекурсивных вызовах?

size_t p = partition(a, lo, hi); /* p — окончательный индекс опорного элемента */
quick(a, lo, p);
quick(a, p, hi);

Для индексов `size_t` рекурсивная быстрая сортировка недопустима из-за беззнакового типа Оба вызова снова включают `p`; при крайнем значении `p` один из диапазонов может не уменьшиться Перед каждым рекурсивным вызовом требуется выделять новый временный массив длиной диапазона Оба диапазона должны иметь одинаковую длину, иначе алгоритм перестаёт быть быстрой сортировкой Левый вызов обязан начинаться с `lo + 1`, иначе опорный элемент будет сравнен повторно

Вопрос 4 из 30

При последовательном обходе миллионов небольших структур какая организация данных обычно лучше использует кэш процессора?

Связный список, потому что дополнительный указатель в узле помогает процессору заранее найти следующий элемент Непрерывный массив: соседние элементы обычно попадают в одни строки кэша и читаются предвыборкой Обе структуры дают одинаковую локальность, если содержат одно и то же число элементов Связный список, если распределитель памяти выдаёт узлы последовательно в порядке вставки Связный список, потому что каждый узел можно разместить отдельно и не перемещать при росте

Вопрос 5 из 30

Какой вызов передаёт `qsort` ровно `n` элементов массива `values` и правильный размер одного элемента?

int values[] = {7, 2, 9, 2};
size_t n = sizeof values / sizeof values[0];
/* Выберите корректный вызов qsort для массива values. */

`qsort(values, n, sizeof values, cmp)` `qsort(values, sizeof values, sizeof values[0], cmp)` `qsort(values, n, sizeof values[0], cmp)` `qsort(values, n, sizeof(int *), cmp)` `qsort(values + 1, n, sizeof values[0], cmp)`

Вопрос 6 из 30

Почему формула `mid=(lo+hi)/2` может быть опасна?

size_t lo = first;
size_t hi = last;
size_t mid = (lo + hi) / 2;

Сложение индексов меняет требуемое выравнивание адреса среднего элемента Деление целых индексов пополам теряет дробную часть и пропускает каждый второй элемент Формула корректна только для знакового типа, поскольку двоичный поиск использует отрицательные индексы При нечётной длине диапазона `mid` обязательно выходит за правую границу Сумма `lo + hi` может обернуться по модулю `size_t` ещё до деления

Вопрос 7 из 30

Какой инвариант соответствует поиску нижней границы в полуинтервале `[lo, hi)`?

`hi` обозначает первый проверенный элемент, который строго меньше ключа Все элементы до `lo` меньше ключа, а все элементы начиная с `hi` не меньше ключа `lo` обозначает последний проверенный элемент, который равен ключу До `lo` находятся элементы не меньше ключа, а начиная с `hi` — строго меньше Ключ гарантированно существует и на каждом шаге остаётся строго внутри `[lo, hi)`

Вопрос 8 из 30

Что происходит при вызове функции с `n == 0`?

size_t last(const int *a,size_t n,int key){
  size_t hi=n;
  if(a[hi-1]==key) return hi-1;
  return SIZE_MAX;
}

Функция сразу возвращает `SIZE_MAX`, потому что `hi` инициализирован нулём Возвращается значение, эквивалентное `-1`, без обращения к памяти Условие не выполняется, и функция возвращает нулевой индекс как начало пустого диапазона Результат зависит от того, разрешил ли оптимизатор заменить проверку прямым возвратом Выражение `hi - 1` оборачивается, после чего происходит обращение за пределы массива

Вопрос 9 из 30

Когда `bsearch` имеет право дать бессмысленный результат, даже если компаратор корректен?

Когда массив не упорядочен тем же отношением сравнения, которое передано в `bsearch` Когда компаратор получает указатель на ключ другого, но совместимого целочисленного типа Когда ключ совпадает с несколькими элементами и вызывающий ожидает первый из них Когда число элементов передано как `sizeof array`, а не как количество записей Когда массив отсортирован другим компаратором, но оба компаратора считают равные элементы равными

Вопрос 10 из 30

Как отличить «не найдено» от корректного индекса 0, если функция работает с `size_t`?

bool find(const int *a,size_t n,int key,size_t *pos);

Вернуть `-1`: после преобразования к `size_t` вызывающий код сам распознает ошибку Вернуть ноль и считать его одновременно первым индексом и признаком отсутствия Вернуть отдельный признак успеха либо документированное значение `SIZE_MAX` Проверять `errno`, хотя функция его не устанавливает и не документирует Вернуть `NULL`, не меняя возвращаемый тип `size_t`

Вопрос 11 из 30

Как корректно сравнить два `uint64_t` для qsort?

static int cmp_u64(const void *pa, const void *pb) {
    uint64_t x = *(const uint64_t *)pa;
    uint64_t y = *(const uint64_t *)pb;
    /* Выберите безопасное выражение return. */
}

return (int)(x-y); return x==y; return memcmp(&x,&y,8); return (x>y)-(x<y); return x-y;

Вопрос 12 из 30

Почему `memcmp` не подходит как общий числовой компаратор значений `int`?

return memcmp(a,b,sizeof(int));

`memcmp` работает только с массивами символов, но не с произвольной памятью Она сравнивает только первый байт независимо от переданного размера Она возвращает лишь ноль или единицу, поэтому не подходит для `qsort` Функция не принимает указатели на `const`-объекты Побайтовый порядок представления `int` не совпадает с числовым порядком

Вопрос 13 из 30

Компаратор иногда возвращает 1 и для a<b, и для a>b. Что нарушено?

Компаратор смешивает владение элементами и может освободить один из аргументов Неверно задан размер элемента, поэтому компаратор читает соседние байты Нарушена только устойчивость: порядок равных элементов больше не сохраняется Нарушается только выравнивание аргументов, а отношение порядка остаётся корректным Знак результата не задаёт согласованного строгого порядка элементов

Вопрос 14 из 30

Как поступить с NaN при сортировке double, если нужен воспроизводимый полный порядок?

if(isnan(x)) return isnan(y)?0:1;
if(isnan(y)) return -1;

Приравнять каждый NaN к нулю, чтобы компаратор сохранял транзитивность для отрицательных чисел Сравнивать объектные представления через `memcmp`, полагая, что порядок битов совпадает с числовым Отбрасывать NaN до сортировки, поскольку стандартная библиотека не разрешает хранить их в массиве Использовать только `x < y` и `x > y`: для NaN обе проверки ложны, что автоматически ставит его в конец Заранее определить положение NaN в порядке и отдельно сравнивать пары, где хотя бы один операнд — NaN

Вопрос 15 из 30

Какой дефект у компаратора строк?

int cmp(const void *a,const void *b){
  return strcmp((const char*)a,(const char*)b);
}

Перед каждым сравнением нужно выделять копии обеих строк через `malloc` Элементы массива имеют тип `char *`; параметры нужно разыменовать до указателей на строки `strcmp` возвращает логическое значение, а `qsort` требует точную разность длин `strcmp` нельзя вызывать из компаратора `qsort`, потому что она меняет строки Компаратор обязан дополнительно получать длину каждой строки отдельным аргументом

Вопрос 16 из 30

Почему список может проиграть массиву даже при одинаковой O(n) сложности обхода?

Во время каждого шага обхода список обязан заново выделять память для следующего узла Разброс узлов и лишние чтения указателей ухудшают работу кэша Локальность массива даёт преимущество только после векторизации; при скалярном коде размещение элементов не влияет на задержки памяти Стандарт C задаёт верхнюю границу числа машинных инструкций для доступа к элементу массива, но не для перехода по списку Дополнительное чтение поля `next` меняет асимптотику последовательного обхода списка с `O(n)` на `O(n log n)`

Вопрос 17 из 30

Какой риск создаёт `realloc` ровно на один новый элемент в каждой итерации?

for (size_t i = 0; i < n; ++i) {
    /* (i + 1) * sizeof *a заранее проверено на переполнение */
    int *tmp = realloc(a, (i + 1) * sizeof *a);
    if (tmp == NULL) {
        handle_allocation_error();
        break;
    }
    a = tmp;
}

При каждом `realloc` все существующие элементы инициализируются нулями После первого `realloc` массив становится неизменяемым для следующих итераций Повторное копирование растущего массива может дать квадратичную суммарную стоимость Любой успешный `realloc` неизбежно теряет старый блок и создаёт утечку Первый успешный `realloc` кэширует финальный размер; повторные вызовы ничего не делают и возвращают тот же блок

Вопрос 18 из 30

Что измерять при выборе между двумя реализациями хеш-таблицы?

Время компиляции на одном наборе заголовков как замену измерению работы таблицы Среднюю длину исходного кода и число вспомогательных функций в каждой реализации Только теоретическое название хеш-функции без проверки распределения на рабочих данных Реальные распределения ключей, коэффициент заполнения, коллизии, промахи кэша и выделения памяти Размер итогового бинарника без учёта профиля ключей и частоты операций

Вопрос 19 из 30

Какое изменение снижает число выделений при сортировке строковых записей?

Перед сортировкой преобразовать каждую запись в односвязный список байтов Сохранять записи в отдельных блоках и копировать строку в новый блок при каждом сравнении Сортировать исходные записи на месте, но предварительно отключить оптимизацию компилятора Создавать временную копию строки внутри компаратора, освобождая её после сравнения Сортировать указатели или индексы, не перемещая записи

Вопрос 20 из 30

Почему микроизмерение на массиве из 8 элементов не доказывает выбор алгоритма для миллиона?

bench(8);
/* По этому единственному измерению пытаются выбрать алгоритм для n ≈ 1 000 000. */

O-нотация применима только к 8 Компилятор запрещает большие массивы Миллион элементов всегда помещается в кэш На восьми элементах постоянные расходы скрывают масштабирование Таймер не работает с int

Вопрос 21 из 30

Какое свойство удобно проверять для любой сортировки?

assert(sorted(out,n));
assert(same_multiset(in,out,n));

Число вызовов компаратора совпало с заранее рассчитанной формулой для одного алгоритма Результат размещён по другому адресу, даже если сортировка заявлена как выполняемая на месте Каждый ключ встречается в результате не более одного раза, даже если во входе были дубли Первый элемент равен минимальному значению типа, а последний — максимальному Результат не убывает и является перестановкой входа

Вопрос 22 из 30

Оптимизированный поиск иногда расходится с линейным на случайных малых массивах. Первый шаг?

Увеличить массивы до производственного размера: на малых данных расхождения несущественны Добавить задержку между сравнениями, чтобы исключить влияние слишком быстрого выполнения Заменить индексы `size_t` на `double`, чтобы избежать ошибок целочисленного деления Удалить линейную реализацию, чтобы в тестах остался только оптимизированный код Сохранить зерно и уменьшить вход без потери расхождения

Вопрос 23 из 30

Какой инвариант должен выполняться после шага разделения в быстрой сортировке?

Разделённый массив не должен содержать нулевых значений Слева нет элементов больше опорного, справа — меньше; части покрывают исходный диапазон Опорный элемент обязан физически находиться по начальному адресу массива После разделения все элементы массива обязаны быть равны опорному Индекс опорного элемента всегда равен половине длины диапазона

Вопрос 24 из 30

Почему тесты только на случайных данных недостаточны?

Стандарт C запрещает использовать псевдослучайные значения в тестах алгоритмов Редкие границы, дубли и упорядоченные входы могут почти не появляться случайно Функция `rand` возвращает только ноль при включённой оптимизации Случайные тесты всегда медленнее исчерпывающих для любого диапазона Случайно созданные массивы нельзя передать функции сортировки без перекодирования

Вопрос 25 из 30

Как локализовать первую операцию, нарушившую кучу?

#ifndef NDEBUG
assert(heap_ok(h));
#endif

Проверять инвариант только после всей серии операций и затем искать место повреждения по последнему состоянию Отключить проверки в отладочной сборке, чтобы получить более полный стек в месте позднего проявления После каждой вставки сортировать внутренний массив и считать совпадение порядка доказательством корректности кучи Проверять инвариант кучи сразу после каждой изменяющей операции и остановиться на первом неверном состоянии Сравнивать адрес корня до и после операции: неизменный адрес означает сохранение всех отношений между элементами

Вопрос 26 из 30

Как безопасно проверить размер выделения `n * sizeof *a`?

if(n > SIZE_MAX/sizeof *a) return ERR_SIZE;
a=malloc(n*sizeof *a);

Вычислить `n * sizeof *a`, вызвать `malloc`, а переполнение проверить по результату `NULL` Прибавить к произведению один элемент: запас компенсирует возможное переполнение Привести `n` к `int`, поскольку знаковое умножение надёжнее беззнакового До умножения убедиться, что n <= SIZE_MAX / sizeof *a Сравнить результат `malloc` с `NULL`; успешное выделение подтверждает корректный размер

Вопрос 27 из 30

Недоверенный ввод задаёт n для алгоритма O(n²). Что важно сделать до запуска?

Скрыть `n` в переменной `static`, чтобы пользователь больше не мог её изменить Печатать каждую итерацию: журналирование предотвратит исчерпание процессора Объявить счётчик цикла `volatile`, сохранив прежнюю сложность Заменить цикл рекурсией, потому что рекурсивная запись автоматически быстрее Ограничить `n` по ресурсному бюджету или выбрать алгоритм с лучшей сложностью

Вопрос 28 из 30

Почему выражение `for(size_t i=n-1;i>=0;i--)` опасно?

for (size_t i = n - 1; i >= 0; --i) {
    use(a[i]);
}

После декремента нулевое значение `size_t` автоматически становится `NULL` Тип `size_t` не поддерживает оператор декремента Цикл всегда выполнится ровно один раз и завершится на нуле Для `size_t` условие `i >= 0` всегда истинно, а после нуля индекс переходит к максимуму Начальное значение `n` должно иметь вещественный тип

Вопрос 29 из 30

Что делать, если временный буфер сортировки выделить не удалось?

Освободить входной массив и вернуть успех, чтобы вызывающий код не увидел частичный результат Продолжить работу с нулевым указателем: сортировка сама пропустит временный буфер Считать, что получен буфер нулевой длины, и записывать в него по обычным индексам Вернуть ошибку без порчи входа либо использовать заранее оговорённый запасной алгоритм Повторять выделение без ограничения, пока операционная система не освободит память

Вопрос 30 из 30

Почему глубина рекурсии quicksort на враждебном входе является вопросом безопасности?

if(depth > limit) heap_sort(a,n);

Глубокая рекурсия делает адреса локальных переменных предсказуемыми, но сама по себе не раскрывает исходный код Стек процесса имеет конечный размер, однако его исчерпание невозможно при хвостовой рекурсии любого вида Стандарт POSIX запрещает рекурсивные сортировки в сетевых службах Опасность возникает лишь тогда, когда значение опорного элемента считается секретным Враждебные разбиения могут дать глубину `O(n)` и исчерпать стек до завершения сортировки