игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Структуры данных и модели вычислений / Тест 2

Структуры данных и модели вычислений - тест 2

Упражнение 1:
Номер 1
Какой класс функций используется для оценки трудоемкости алгоритмов сверху?

Ответ:

 (1) Ο 

 (2) Θ 

 (3) Ω 


Номер 2
Какой класс функций используется для оценки трудоемкости алгоритмов снизу?

Ответ:

 (1) Ο 

 (2) Θ 

 (3) Ω 


Номер 3
Какие классы функций используются для амортизационных оценок трудоемкости алгоритмов?

Ответ:

 (1) Ο 

 (2) Θ 

 (3) Ω 


Упражнение 2:
Номер 1
Какие из перечисленных функций принадлежат классу Ο(n2)?

Ответ:

 (1) 2n 

 (2) 2n2+3n 

 (3) 2n3+3n 

 (4) n logn  

 (5) n2logn 


Номер 2
Какие из перечисленных функций принадлежат классу Ω(n2)?

Ответ:

 (1) 2n 

 (2) 2n2+3n 

 (3) 2n3+3n 

 (4) n logn 

 (5) n2logn 


Номер 3
Какие из перечисленных функций принадлежат классу Θ(n2)?

Ответ:

 (1) 2n 

 (2) 2n2+3n 

 (3) 2n3+3n 

 (4) n logn 

 (5) n2logn 


Упражнение 3:
Номер 1
Какие из следующих операций выполняются за время Ο(1) при представлении списка массивом?

Ответ:

 (1) нахождение позиции элемента в памяти по его номеру в кортеже 

 (2) нахождение позиции элемента, следующего в кортеже за элементом из заданной позиции 

 (3) нахождение позиции элемента, предшествующего в кортеже элементу из заданной позиции 

 (4) удаление элемента, находящегося в заданной позиции 

 (5) вставка в кортеж нового элемента перед элементом, расположенным в заданной позиции 

 (6) определение длины кортежа 


Номер 2
Какие из следующих операций выполняются за время Ο(1) при динамическом представлении списка с односторонними связями?

Ответ:

 (1) нахождение позиции элемента в памяти по его номеру в кортеже 

 (2) нахождение позиции элемента, следующего в кортеже за элементом из заданной позиции.  

 (3) вставка в кортеж нового элемента перед элементом, расположенным в заданной позиции 

 (4) определение длины кортежа 


Номер 3
Какие из следующих операций выполняются за время Ο(1) при динамическом представлении списка с двухсторонними связями?

Ответ:

 (1) нахождение позиции элемента, следующего в кортеже за элементом из заданной позиции 

 (2) нахождение позиции элемента, предшествующего в кортеже элементу из заданной позиции.  

 (3) удаление элемента, находящегося в заданной позиции 

 (4) поиск заданного элемента 


Упражнение 4:
Номер 1
Какова трудоемкость поиска заданного элемента в одностороннем динамическом списке, содержащем n элементов?

Ответ:

 (1) Ο(1) 

 (2) Ο(n) 

 (3) Ο(log n) 


Номер 2
Какой может быть трудоемкость удаления элемента из заданной позиции одностороннего динамического списка, содержащего n элементов?

Ответ:

 (1) Ο(1) 

 (2) Ο(n) 

 (3) Ο(log n) 

 (4) Ο(n2) 


Номер 3
Какова возможна трудоемкость удаления элемента из заданной позиции двустороннего динамического списка, содержащего n элементов?

Ответ:

 (1) Ο(1) 

 (2) Ο(n) 

 (3) Ο(log n) 

 (4) Ο(n2) 


Упражнение 5:
Номер 1
Какой может быть трудоемкость поиска заданного элемента в списке, представленном массивом из n элементов?

Ответ:

 (1) Ο(1) 

 (2) Ο(n) 

 (3) Ο(log n) 

 (4) Ο(n2) 




Главная / Алгоритмы и дискретные структуры / Структуры данных и модели вычислений / Тест 2