Главная / Программирование /
Инструменты, алгоритмы и структуры данных / Тест 6
Инструменты, алгоритмы и структуры данных - тест 6
Упражнение 1:
Номер 1
Какие операции над элементами массива имеют сложность O(n)
:
Ответ:
 (1) чтение значения элемента, зная его номер 
 (2) запись значения элемента, зная его номер 
 (3) вставка нового элемента 
 (4) удаление существующего элемента 
Номер 2
Какие операции над элементами списка имеют сложность O(n)
:
Ответ:
 (1) чтение значения элемента, зная его номер 
 (2) запись значения элемента, зная его номер 
 (3) вставка нового элемента в позицию, определяемую курсором 
 (4) удаление элемента в позиции, определяемой курсором 
Номер 3
Какие операции над элементами списка имеют сложность O(1)
:
Ответ:
 (1) чтение значения элемента, зная его номер 
 (2) запись значения элемента, зная его номер 
 (3) вставка нового элемента в позицию, определяемую курсором 
 (4) удаление элемента в позиции, определяемой курсором 
Упражнение 2:
Номер 1
Какой из библиотечных классов Eiffel является родительским классом для всех библиотечных классов, задающих различные реализации списков?
Ответ:
 (1) LINKED_LIST
 
 (2) ARRAYED_LIST
 
 (3) LIST
 
 (4) TWO_WAY_LIST
 
 (5) MULTI_ARRAYED_LIST
 
Номер 2
Какие утверждения справедливы для библиотечного класса LIST
, определяющего понятие "список"?
Ответ:
 (1) является родительским классом для всех библиотечных классов Eiffel, реализующих списки 
 (2) требует, чтобы классы потомки заново определяли понятия, введенные в классе LIST
 
 (3) является универсальным классом, чей родовой параметр задает тип информационных элементов, хранимых в списке 
 (4) имеет курсор, с помощью которого можно выделять некоторый элемент списка 
Номер 3
Какие утверждения являются справедливыми для понятия "список с курсором"?
Ответ:
 (1) список - это упорядоченная последовательность однородных элементов 
 (2) в языке Eiffel нумерация элементов списка начинается с 1 
 (3) зная номер элемента списка, за константное время O(1)
можно получить доступ к любому элементу списка 
 (4) за константное время O(1)
можно вставить новый элемент в позицию, определяемую курсором списка 
 (5) за константное время O(1)
можно удалить элемент, стоящий в позиции, определяемой курсором списка 
Упражнение 3:
Номер 1
Какие утверждения не являются справедливыми для понятия "список с курсором"?
Ответ:
 (1) список с курсором - это список, в котором есть указатель на направление движения списка 
 (2) список с курсором - это список, в котором есть указатель, позволяющий выделить некоторый элемент списка, задавая позицию этого элемента в списке 
 (3) за константное время O(1)
можно вставить новый элемент в позицию, определяемую курсором 
 (4) за константное время O(1)
можно удалить элемент, стоящий в позиции, определяемой курсором 
 (5) зная номер элемента списка, за константное время O(1)
можно получить доступ к любому элементу списка с курсором 
 (6) за константное время O(1)
можно получить доступ к элементу списка, стоящему в позиции, определяемой курсором 
Номер 2
Какие утверждения справедливы для курсора?
Ответ:
 (1) в списке из n элементов, нумеруемых от 1 до n, курсор может принимать значения от 0 до n+1 
 (2) в списке из n элементов, нумеруемых от 1 до n, курсор может принимать значения от 1 до n 
 (3) если курсор принимает значение 0, то это означает, что курсор находится вне списка - слева от списка 
 (4) если курсор принимает значение n + 1, то это означает, что курсор находится вне списка - справа от списка 
Номер 3
Укажите, какие из запросов не связаны с курсором?
Ответ:
 (1) is_empty
 
 (2) index
 
 (3) before
 
 (4) after
 
 (5) is_first
 
 (6) is_last
 
 (7) off
 
 (8) count
 
Упражнение 4:
Номер 1
Каково число возможных позиций курсора для пустого списка?
Ответ:
 (1) 0 
 (2) 1 
 (3) 2 
 (4) count
 
 (5) count + 1
 
Номер 2
Дан список с курсором, в котором курсор установлен на некотором элементе списка. Каково минимальное число команд достаточно выполнить, чтобы стал истинным запрос after
?
Ответ:
 (1) 1 
 (2) 2 
 (3) count
 
 (4) count + 1
 
 (5) count / 2
 
Номер 3
Дан список с курсором, в котором курсор установлен на некотором элементе списка. Какие две команды нужно выполнить, чтобы стал истинным запрос before
?
Ответ:
 (1) start
 
 (2) finish
 
 (3) item
 
 (4) forth
 
 (5) back
 
Упражнение 5:
Номер 1
Под итерированием списка понимается:
Ответ:
 (1) проход по списку с выполнением некоторой операции над всеми элементами списка 
 (2) выполнение некоторой операции над элементами списка, стоящими слева и справа от курсора 
 (3) проход по списку с выполнением некоторой операции над элементом списка при условии, что для этого элемента выполняется некоторое условие 
 (4) проход по списку, пока не встретится элемент списка, для которого выполняется некоторое условие 
 (5) различные вариации циклической обработки элементов списка 
Номер 2
Пусть объект your_list
задает непустой список с курсором, элементы которого являются целыми числами. Какой из фрагментов кода задает итерирование списка, в результате которого значением переменной temp
станет индекс первого в списке элемента со значением 5 или 0, если такового элемента в списке нет.
Ответ:
 (1) temp: INTEGER
your_list.start
temp := your_list.item
from
your_list.forth
until
your_list.after
loop
temp := temp + your_list.item
your_list.forth
end
 
 (2) temp: INTEGER
your_list.start
temp := your_list.item
from
your_list.forth
until
your_list.after
loop
if (temp < your_list.item)
temp := your_list.item
end
your_list.forth
end
 
 (3) temp: INTEGER
from
temp := 0
your_list.start
until
your_list.after
loop
if (your_list.item = 5)
temp := your_list.index
end
your_list.forth
end
 
 (4) temp: INTEGER
finish: BOOLEAN
from
your_list.start
temp := 0
finish := FALSE
until
your_list.after or else finish
loop
if (your_list.item = 5)
finish := TRUE
temp:= your_list.index
end
your_list.forth
end
 
Номер 3
Пусть объект your_list
задает непустой список с курсором, элементы которого являются целыми числами. Какой из фрагментов кода задает итерирование списка, в результате которого переменная temp
содержит максимальный элемент списка.
Ответ:
 (1) temp: INTEGER
your_list.start
temp := your_list.item
from
your_list.forth
until
your_list.after
loop
temp := temp + your_list.item
your_list.forth
end
 
 (2) temp: INTEGER
your_list.start
temp := your_list.item
from
your_list.forth
until
your_list.after
loop
if (temp < your_list.item)
temp := your_list.item
end
your_list.forth
end
 
 (3) temp: INTEGER
from
temp := 0
your_list.start
until
your_list.after
loop
if (your_list.item = 5)
temp := your_list.index
end
your_list.forth
end
 
 (4) 5.4. temp: INTEGER
finish: BOOLEAN
from
your_list.start
temp := 0
finish := FALSE
until
your_list.after or else finish
loop
if (your_list.item = 5)
finish := TRUE
temp:= your_list.index
end
your_list.forth
end
 
Упражнение 6:
Номер 1
Какие утверждения справедливы для связных списков?
Ответ:
 (1) связный список задается двумя классами - один класс описывает элемент связного списка, другой - сам список 
 (2) связный список - это список, элементы которого создают незаконные побочные связи 
 (3) в зависимости от числа связей связный список может быть односвязным, двусвязным, многосвязным (к - связным) 
 (4) универсальный класс LINKABLE
из библиотеки EiffelBase описывает элемент односвязного списка как пару сущностей. Первый элемент пары, тип которого задается родовым параметром класса, задает информацию, хранимую элементом списка. Вторым элементом пары, базовым типом которого является сам класс LINKABLE
, является ссылочная переменная, задающая связь между элементами списка 
Номер 2
Укажите правильные последовательности действий при вставке элемента в односвязный список класса LINKED_LIST
при условии, что элемент вставляется после существующего в списке элемента, назовем его current
:
Ответ:
 
(1)
Создать новый элемент класса LINKABLE ; |
Определить связь нового элемента, присвоив ей значение current.right ; |
Изменить связь current.right , чтобы она стала ссылкой на вновь созданный элемент; |
Задать значение информационного поля у нового элемента (предполагается, что при вставке нового элемента известна информация, которую должен хранить этот элемент). |
 
 
(2)
Создать новый элемент класса LINKABLE ; |
Изменить связь current.right , чтобы она стала ссылкой на вновь созданный элемент; |
Определить связь нового элемента, присвоив ей значение current.right ; |
Задать значение информационного поля у нового элемента (предполагается, что при вставке нового элемента известна информация, которую должен хранить этот элемент). |
 
 
(3)
Создать новый элемент класса LINKABLE ; |
Задать значение информационного поля у нового элемента (предполагается, что при вставке нового элемента известна информация, которую должен хранить этот элемент). |
Определить связь нового элемента, присвоив ей значение current.right ; |
Изменить связь current.right , чтобы она стала ссылкой на вновь созданный элемент; |
 
 
(4)
Определить связь нового элемента, присвоив ей значение current.right ; |
Изменить связь current.right , чтобы она стала ссылкой на вновь созданный элемент; |
Создать новый элемент класса LINKABLE ; |
Задать значение информационного поля у нового элемента (предполагается, что при вставке нового элемента известна информация, которую должен хранить этот элемент). |
 
Номер 3
При реализации алгоритма обращения списка на том же месте, требующего O(count)
времени, на каждом шаге цикла достаточно выполнить несколько операторов ссылочного присваивания. Сколько требуется операторов?
Ответ:
 (1) 1 
 (2) 2 
 (3) 4  
 (4) 8  
 (5) 16 
Упражнение 7:
Номер 1
Какие операции над связным списком из класса LINKED_LIST
выполняются за время O(1)
?
Ответ:
 (1) put_right
 
 (2) remove_right
 
 (3) start
 
 (4) finish
 
 (5) forth
 
 (6) back
 
Номер 2
Какие операции над связным списком из класса LINKED_LIST
выполняются в среднем за время O(count)
?
Ответ:
 (1) put_right
 
 (2) remove_right
 
 (3) start
 
 (4) finish
 
 (5) forth
 
 (6) back
 
Номер 3
Какие утверждения справедливы для односвязных и двусвязных списков, реализуемых классами TWO_WAY_LIST и LINKED_LIST
?
Ответ:
 (1) класс TWO_WAY_LIST
восстанавливает симметрию, - теперь каждый элемент списка имеет связь, как с правым, так и с левым соседом, если таковые существуют 
 (2) для двусвязного списка увеличивается расход памяти, поскольку число связей удваивается 
 (3) для двусвязного списка повышается эффективность ряда операций, например, операция перемещения курсора влево - back
выполняется в двусвязном списке за время O(1)
, а не за время O(count)
, как в односвязном списке 
 (4) интерфейс команд и запросов у классов TWO_WAY_LIST
и LINKED_LIST
различен 
 (5) реализации команд и запросов, наследуемых от класса List
, у классов TWO_WAY_LIST
и LINKED_LIST
одинаковы 
Упражнение 8:
Номер 1
Одним из наследников класса LIST
является библиотечный класс ARRAYED_LIST
. Какие утверждения справедливы для этого класса?
Ответ:
 (1) этот класс является частным случаем связного списка, использующего массив как дополнительную промежуточную память 
 (2) этот класс не использует ссылки при организации списка 
 (3) возможности массива как структуры данных достаточны для организации связей между элементами списка 
 (4) класс ARRAYED_LIST
имеет тот же набор запросов и команд, наследуемых от класса LIST
, что и классы LINKED_LIST
и TWO_WAY_LIST
 
 (5) все операции в классе ARRAYED_LIST
реализуются столь же эффективно, как и в классах LINKED_LIST
и TWO_WAY_LIST
 
 (6) некоторые операции в классе ARRAYED_LIST
реализуются эффективнее, некоторые менее эффективно в сравнении с классами LINKED_LIST
и TWO_WAY_LIST
 
Номер 2
Укажите корректные высказывания для мультимассивных списков:
Ответ:
 (1) такие списки могут быть реализованы только на мультиядерных компьютерах 
 (2) реализация такого списка построена на многомерном массиве - мультимассиве 
 (3) реализация такого списка построена на многосвязном списке - мультисписке 
 (4) реализация такого списка построена на двусвязном списке, каждый элемент которого является списком, построенным на массиве 
Номер 3
Укажите корректные высказывания:
Ответ:
 (1) если при работе с контейнером требуются частые операции вставки и удаления элементов, то подходящим видом контейнера в этой ситуации является массив, эффективно реализующий эти операции 
 (2) если при работе с контейнером требуются частые операции вставки и удаления элементов, то подходящим видом контейнера в этой ситуации является список, эффективно реализующий эти операции 
 (3) реализация операций над списком всегда требует использования ссылочных переменных 
 (4) в многосвязном списке каждый элемент списка может быть связан с несколькими элементами того же списка 
 (5) двусвязный список можно рассматривать как последовательность, в которой каждый элемент связан с предыдущим и последующим элементами последовательности