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

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

Вариант 429533517.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

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

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

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

Вопрос 3

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

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

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

Вопрос 4

Выходные данные процедуры mystery зависят от используемого метода передачи параметров

  procedure mystery
    a : integer;
    b : integer;
    procedure enigma(x,y)
    begin
      y = y + b;
      x = b + x;
      b = x + b;
      a = y;
    end enigma;
  begin
    a = 2; b = 7;
    enigma(a,b);
    write(a); write(b);
  end mystery;

Предположим, что все параметры передаются по значению

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

  1.  a = 9 b = 14
  2.  a = 2 b = 7
  3.  a = 2 b = 9
  4.  a = 14 b = 16
  5.  a = 30 b = 30

Вопрос 5

k-ary tree — это дерево, в котором каждый узел имеет не более k детей.

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

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

  1.  Преобразование типов
  2.  Совместимость типов
  3.  Длина идентификатора
  4.  Приоритет оператора
  5.  Максимальный уровень вложенности

Вопрос 7

Пусть k — целое число, большее 1. Какое из следующих значений соответствует порядку возрастания выражения в зависимости от n?

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 8

Шаблон проектирования Singleton используется, чтобы гарантировать, что может быть создан только один экземпляр класса

Что из приведенного ниже верно для этого шаблона проектирования?

  • Класс Singleton имеет статический фабричный метод для cоздания своего экземпляра
  • Класс Singleton может быть подклассом другого класса
  • У класса Singleton есть собственный конструктор
  1.  1 и 3
  2.  Только 1
  3.  Только 2
  4.  1, 2, 3
  5.  Только 3

Вопрос 9

Одним из подходов к обработке данных нечеткой логики может быть разработка компьютера с использованием троичной логики (base-3), чтобы данные могли храниться в виде «true», «false» и «unknown»

Если каждый элемент троичной логики называется flit, то сколько таких элементов требуется для представления как минимум 256 различных значений?

  1.  6
  2.  4
  3.  8
  4.  5
  5.  7

Вопрос 10

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

  1.  Нахождение крупнейшей клики в G
  2.  Нахождение самого длинного простого цикла в G
  3.  Нахождение раскраски вершин G (в которой соседние вершины имеют разные цвета) с минимальным количеством цветов
  4.  Нахождение кратчайшего цикла в G
  5.  Нахождение всех прямых деревьев G