Тест по Computer Science — вопросы

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
Тест по Computer Science, подготовил Участник:Akazikov

Вариант 115155013.


Ваше имя*:


Вопрос 1

Какой из следующих алгоритмов имеет время выполнения O(n²) в наихудшем случае, но O(nlog(n)) в среднем?

  1.  Быстрая сортировка
  2.  Турнирная (Tournament) сортировка
  3.  Сортировка слиянием
  4.  Пузырьковая сортировка
  5.  Пирамидальная сортировка (сортировка кучей)

Вопрос 2

Хэш-таблицы могут способствовать эффективному решению всех проблем, описанных ниже КРОМЕ

  1.  Поиск в таблице символов: по заданному идентификатору программы найдите ее тип и адрес
  2.  Динамический словарь: Поддерживает операции вставки, удаления и поиска в словаре
  3.  Поиск по диапазону: по заданным значениям a и b найдите все записи, ключевое значение которых находится в диапазоне [a, b]
  4.  Поиск пересечений: При наличии двух наборов ключей найдите все значения ключей, общие для обоих наборов
  5.  Подсчет различных значений: При наличии набора из n ключей определите количество различных значений ключа

Вопрос 3

Какие из следующих свойств включает в себя объектно-ориентированная парадигма?

  • Инкапсуляция
  • Наследование
  • Рекурсия
  1.  Только 2
  2.  1 и 2
  3.  2 и 3
  4.  1, 2, 3
  5.  Только 1

Вопрос 4

Какое из следующих утверждений об Ethernet-сетях является ЛОЖНЫМ?

  1.  Пакеты, отправляемые по Ethernet-сетям, ограничены по размеру
  2.  В Ethernet-сетях используются шины с несколькими ведущими устройствами
  3.  Протоколы Ethernet используют метод обнаружения коллизий для обеспечения правильной передачи сообщений
  4.  Длина сетей, подключенных с помощью Ethernets, ограничена несколькими сотнями метров
  5.  Ethernets-сети используют коммутацию каналов для отправки сообщений

Вопрос 5

Чтобы найти решение уравнения для полинома степени с производной , метод Ньютона делает итерации вида

начиная с некоторого начального значения , достаточно близкого к желаемому решению , чтобы обеспечить сходимость к для фиксированных значений и , что из приведенного ниже представляет порядок увеличения минимального числа итераций, необходимого для вычисления с точностью до бит как функции из ?

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

Ниже приведен граф приоритетов (precedence graph) для набора задач, которые должны быть выполнены в системе параллельных вычислений S

[svg]

Эффективность определяется как соотношение между ускорением и количеством процессоров

(Ускорение определяется как отношение времени, затраченного на выполнение набора задач на одном процессоре, к времени, затраченному на выполнение того же набора задач на параллельном процессоре)

Система S имеет четыре процессора (CPU)

Если каждая из задач выполняется за одинаковое время, то какова эффективность этой системы S?

  1.  100%
  2.  %
  3.  125%
  4.  50%
  5.  25%

Вопрос 7

Рассмотрите следующие возможные структуры данных для набора из n различных целых чисел

  • Минимальная куча
  • Массив длиной n, отсортированный в порядке возрастания
  • Сбалансированное дерево бинарного поиска

Для какой из этих структур данных требуется количество шагов, чтобы найти и удалить 7-й по величине элемент O(logn) в наихудшем случае?

  1.  2 и 3
  2.  1 и 2
  3.  1 и 3
  4.  Только 2
  5.  Только 1

Вопрос 8

Предположим, что целевой объект t — это целочисленное значение, хранящееся в некотором элементе целочисленного массива x, который отсортирован в неубывающем порядке, и рассмотрим следующую схему цикла для поиска t

  <initialization of h and k>
  while (x[h] != t)
  {
    P;
  }

Если initialization устанавливает инвариант , какое из следующих определений для P, взятое по отдельности, гарантирует, что цикл завершится с , предпологая, что t появляется в массиве?

  • if x[h] < t then h := h + 1
  • h := h + 1
  • k := k — 1
  1.  1 и 2
  2.  Только 1
  3.  Только 3
  4.  1 и 3
  5.  Только 2

Вопрос 9

Согласно стандарту IEEE, 32-разрядное число с плавающей запятой одинарной точности N определяется как

где S — знаковый бит, F — дробная мантисса, а E — смещенный показатель степени

Число с плавающей запятой хранится в формате S : E : F, где S, E и F хранятся в 1 бите, 8 битах и 23 битах соответственно

Каково десятичное значение числа с плавающей запятой C1E00000 (шестнадцатеричная система счисления)?

  1.  26
  2.  −15
  3.  −26
  4.  −59
  5.  −28

Вопрос 10

Какие из следующих задач будут решаться с помощью алгоритмов за полиномиальное время, если предполагается, что ?

  • Дана комбинационная схема с n входами и m выходами и вентилями, где каждый вентиль является либо AND, OR, или NOT, и заданы m значений в качестве выходных данных или определяют, что не является возможным выходным сигналом схемы
  • Учитывая n на n матриц A с рациональными числовыми элементами, либо найдите точное значение, обратное для A, либо определите, что не существует. (Предположим, что каждое рациональное число выражается в виде пары целых чисел a/b (), где a и b выражены в двоичной системе счисления)
  • Задан ориентированный граф с узлами, пронумерованными , и заданными целыми положительными весами, присвоенными ребрам, либо найдите длину кратчайшего пути от узла 1 до узла n, либо определите, что такого пути не существует. (Здесь длина контура равна сумме длин реберных весов на контуре)
  1.  1 и 2
  2.  Только 3
  3.  Только 1
  4.  2 и 3
  5.  Только 2