Главная / Алгоритмы и дискретные структуры /
Структуры данных и модели вычислений / Тест 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)