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

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

Вариант 4185131277.


Ваше имя*:


Вопрос 1

Определенный рандомизированный алгоритм A предназначен для определения того, является ли данное входное значение n с положительным числом простым, путем генерации случайной битовой строки r и, основываясь на значениях n и r, путем вывода либо Yes (что указывает на то, что n является простым), либо No (что указывает на то, что n является составным)

Выполнение алгоритма А гарантирует следующее

  • Если n — простое число, то результатом A всегда будет Yes
  • Если n является составным, то существует вероятность p > 0, так что результатом A будет No с вероятностью p и Yes с вероятностью 1 — p

На входе m алгоритм A выполняется k раз (k > 0) и генерирует случайную строку при i-м выполнении , где являются взаимно независимыми

Если m является составным, какова вероятность того, что в каждом из k различных вариантов выполнения результат A будет YES ?

  1.  
  2.  
  3.   —
  4.  
  5.  1

Вопрос 2

k-ary tree — это дерево, в котором каждая вершина имеет не более k дочерних элементов

В k-ary tree с n вершинами и высотой h, какое из следующих значений является верхней границей для максимального числа листьев в зависимости от h, k и n?

  1.  
  2.  
  3.  
  4.   —
  5.  

Вопрос 3

Пусть  — конечный ориентированный ациклический граф с

Что из следующего должно быть истинным ?

  • У G есть вершина без входящего ребра
  • G имеет вершину без исходящего ребра
  • G имеет изолированную вершину, то есть вершину, у которой нет ни входящего, ни исходящего ребра
  1.  1 и 2 —
  2.  только 1
  3.  только 2
  4.  1, 2, 3
  5.  только 3

Вопрос 4

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

  1.  Таблица символов —
  2.  Абстрактное синтаксическое дерево (AST)
  3.  Семантический стек
  4.  Атрибутивная грамматика
  5.  Таблица синтаксического анализа

Вопрос 5

Что из перечисленного не является свойством растровой графики ?

  1.  Полигоны могут быть заполнены сплошными цветами и текстурами
  2.  Сложность представления изображения не зависит от самого изображения
  3.  Для эффективного перемещения блоков пикселей существует быстрое аппаратное обеспечение
  4.  Все отрезки линии могут отображаться как прямые —
  5.  Можно создать реалистичное освещение и затенение

Вопрос 6

Сортировка слиянием выполняется путем разделения списка из n чисел пополам, рекурсивной сортировки каждой половины и объединения двух половин

Какая из следующих структур данных позволит выполнить сортировку слиянием за раз ?

  • Односвязный список
  • Двусвязный список
  • Массив
  1.  2 и 3
  2.  Только 3
  3.  1, 2, 3 —
  4.  1 и 2
  5.  Нет правильного ответа

Вопрос 7

Для каждого неотрицательного целого числа n пусть  — максимально возможное число областей, на которые плоскость может быть разделена n прямыми линиями

Например, и

Тогда имеет порядок

  1.   —
  2.  
  3.  
  4.  
  5.  

Вопрос 8

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

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

Вопрос 9

Центральный процессор имеет арифметический модуль, который добавляет байты, а затем устанавливает свои флаговые биты V, C и Z следующим образом

Бит V устанавливается, если происходит арифметическое переполнение (в арифметике дополнения two)

Бит C устанавливается, если во время операции выполняется выполнение из старшего по значению бита

Бит Z устанавливается, если результат равен нулю

Каковы значения флаговых битов V, C и Z после добавления 8-битных байтов 1100 1100 и 1000 1111 ?

  1.  V = 0 °C = 0 Z = 0
  2.  V = 0 °C = 0 Z = 1
  3.  V = 1 °C = 1 Z = 1
  4.  V = 1 °C = 1 Z = 0 —
  5.  V = 0 °C = 1 Z = 0

Вопрос 10

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

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

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

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

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