wayground logo

Free Printable Worksheets

Font size

S
M
L
XL
Worksheets

test

Total questions: 70

Worksheet time: 38mins

Name
Class
Date
1.

1.После операцијата вметнување елемент AVL дрвото се дебалансирало. Која операција треба да се преземе за да стане правилно AVL дрво. 

a)

Единечна ротација - десно

b)

Двојна ротација - лево, десно 

c)

Единечна ротација - лево

d)

Двојна ротација - десно, лево   98

2.

  1. 2.Замислете дека постојат две решенија на еден проблем. Првото решение има два последователни рекурзивни повика кои го користат скоро почетниот број на елементи. Второто решение ги изминува половина од елементите во циклус и потоа втората половина од елементите во обратен циклус Кое од решенијата е поефикасно и зошто?

a)

●       Првото затоа што рекурзија е секогаш поефикасна од циклус

b)

●       Второто затоа што го решава проблемот во линеарно време наместо во експоненцијално

c)

●       Првото затоа што има експоненцијална комплексност за разлика од второто што има двојна линеарна комплексност.

d)

●       Првото, затоа што има логоратимска комплексност за разлика од второто кое има линеарна комплексност.d

3.

3.Која е висината на јазелот 1 на дрвото на сликата?

a)

Нема висина

b)

●       1

c)

●       3

d)

●       2

4.

Со која техника на програмирање може ефикасно да се најде најдолга растечка подниза на дадена низа?

a)

●       Лакоми алгоритми

b)

●       Динамичко програмирање

c)

●       Техники со враќање наназад

d)

●       Груба сила

5.

5.Нека е дадена репрезентацијата на графoт со матрица на соседство А = (0 1 0 0; 1 0 0 1; 1 0 0 1;  0 1 1 0), каде што редоследот на колоните и редиците е 1, 2, 3, 4, соодветно. Ако графот се претстави преку листа на соседство, тогаш што од понуденото е точно?

a)

●       4) — 1 — 2--- 3

b)

●       1 -- 2---3)

c)

●       3) — 1 —> 2---4

d)

●       2) — 1- --4

6.

6.      Динамичкото програмирање како архетип се заснова на

a)

●       комбинација на алчни алгоритми и груба сила

b)

●       Препопување на влезно множество на податоци

c)

●       Паметење на пресметани резултати и генерирање на простор на резултати

d)

●       рекурзија и брзи математички пресметки

7.

7.      Што од наведеното е точно за стек?

a)

●       Имплицитно се имплементира со итерација

b)

●       Користи приоритет

c)

●       Може да се имплантира само со двојно поврзана листа

d)

●       Имплицитно се имплементира со рeкузија

8.

Нека е дадена следната низа од елементи: 20, 47, 15, 8, 9, 4, 40, 30, 12, 17 Ако се примени mеrgе ѕоrt алгоритмот за сортирање на оваа низа, како ќе изгледа низата после второто изминување (second pass) од алгоритмот?

a)

20, 47, 8, 15, 4, 9, 30, 40, 12, 17

b)

8, 15, 20, 47, 4, 9, 30, 40, 12, 17

c)

4, 8, 9, 15, 20, 47, 12, 17, 30, 40

d)

15, 20, 47, 4, 8, 9, 12, 30, 40, 17

9.

За најефикасно решавање на проблемот за проверка на добро поставени загради во аритметичките изрази, се користи:

a)

стек

b)

приоритетна листа

c)

редица

d)

ниту една од понудените апстрактни податочни структури

10.

Која од следниве карактеристики НЕ е недостаток при користење на низи?

a)

Постои можност за неискористеност на мемориски простор ако елементите во низата се помалку отколку алоцираната големина

b)

Додавање на елемент на дадена позиција

c)

Пристап до елементи на специфицирана позиција

d)

Фиксна големина

11.

За бришење на елемент на главата(почетокот) на редицата се користи операцијата:

a)

push

b)

peek

c)

enqueue

d)

dequeue

12.

Ако елементите “А", "В", "С" и "D“ се вметнат во празна редица, кој ќе биде редоследот на вадење на елементите од редицата?

a)

ABCD

b)

DCBA

13.

Стекот (Магацинот) претставува еднодимензионална линеарна секвенца од елементи која работи по принципот:

a)

Последен-внесен-последен-изваден (last-in-last-out)

b)

последе-внесен-прв-изваден

c)

прв-внесен-последен-изваден (first-in-last-out)

d)

прв-внесен-прв-изваден (first-in-first-out)

14.

Додавањето на нови елементи и нивното вадење од Стекот (Магацинот):

a)

се врши од дното

b)

зависи од имплементацијата на магацинот

c)

се врши од врвот

d)

зависи од пополнетоста на магацинот

15.

Динамички поврзана листа е множество...

a)

подредени елементи (јазли) што содржат вредност и покажувачи кон произволен број јазли

b)

подредени елементи (јазли) што содржат вредност и покажувач кон следен јазел

c)

елементи (јазли) што содржат вредност и покажувач кон следен јазел

d)

подредени елементи (јазли) што содржат вредност и покажувач кон следната вредност

16.

Што е недостаток на податочната структура Низа?

a)

има константно време на пристап до елемент преку неговиот индекс

b)

не може да се промени нејзината големина

c)

не се чуваат други помошни податоци во меморија (пример покажувачи)

d)

времето на изминување на целата низа е брзо

17.

Кој од следните искази НЕ е точен, кога станува збор за еднострано поврзана листа?

a)

Додавањето и бришењето на елементи е поедноставно отколку кај низа

b)

еднострано поврзана листа не овозможува ефикасен пристап до произволен елемент

c)

еднострано поврзаната листа не може да се наполни (освен ако се наполни меморијата)

d)

кај еднострано поврзана листа не е потребна дополнителна меморија за чување на покажувач

18.
Кога се вметнува елемент во редица, истиот се вметнува на ____ на редицата, со операцијата_____.
a)
почетокот (главата), dequeue
b)
почетокот(главата), enqueue
c)
крајот(опашката), dequeue
d)
крајот(опашката), enqueue
19.
Целта на робот за пакување е да смести предмети во пакети, така што вкупната вредност на предметите во пакетот се максимизира. Предметите не може да се делат и мора целосно да ги собира во пакетот. Максималниот волумен на пакетот е 50 литри. Предметите се со волумен {15, 20, 30, 35} и вредности {90, 100, 120, . Која е максималната вкупна вредност на предметите што ги собира во пакетот?
a)
220=120+100
b)
200
c)
215=90+125
d)
190=90+100
20.
Претпоставете дека имате монети од 1, 3 и 4 денари. Користејќи алчен алгоритам кој ќе ја избира најголемата монета која не е поголема од преостанатата сума, одговорете за која од следниве суми, алгоритмот нема да даде оптимален одговор?
a)
6 (треба 3+3 а тој ќе врати 4+1+1)
b)
20 (4+4+4+4+4)
c)
5 (4+1)
d)
12 (4+4+4)
21.
Која од следните техники ја користи Merge sort за имплементација на сортирањето?
a)
Враќање наназад (backtracking)
b)
Динамичко програмирање
c)
Раздели и владеј
d)
Алчен (greedy) алгоритам
22.
Кога алгоритмот Quicksort има најлоши перформанси:
a)
Кога броевите во низата се рамномерно дистрибуирани во одреден опсег
b)
Кога имаме мал број на различни елементи
c)
Кога имаме голем број на различни елементи
d)
Кога низата е скоро сортирана
23.
Која од следниве операции не е O(1) за сортирана низа со елементи. Може да претпоставитедека елементите во низата се различни
a)
Избриши елемент // О(n) е, има после шифтање на др елементи за да се пополни празното место
b)
Најди го і-тиот најголем елемент
c)
Најди го і-тиот најмал елемент
d)
Сите наведени
24.
Во имплементација на редица со еднострано поврзана листа, ако се чува само покажувачот кон front, која од следните операции е со најлошо време на извршување?
a)
И додавање на елемент и бришење на цела редица
b)
Додавање на елемент
c)
Бришење на цела редица
d)
Бришење на елемент
25.
Која е сложеноста на алгоритмот:
a)
O(N * M)
b)
O((N + M)/2)
c)
O((N * M)/(N + M))
d)
O(N + M)
26.
Која е временската сложеност на алгоритмот со техника на груба сила (brute force) што се користи за решавање на проблемот со ранец?
a)
O(n)
b)
O(n^3)
c)
О(2^n)
d)
O(n!)
27.
Кои од следниве тврдења се неточни за двојно поврзани листи?
a)
Потребно е повеќе мемориски простор за нив во споредба од еднострано поврзани листи
b)
Имплементација на двојно поврзана листа е полесно отколку на еднострано поврзана листа
c)
Додавањето и бришењето на јазел е подолго
28.
Да се напише функцијата за бројот на извршени операции за дадениот псевдо код и да се пресмета асимптотската горна граница "големо о“ за истиот код:
a)
f(n)=2n*n+4, O(n*n)
b)
f(n) =5n+8
c)
f(n) =3n+6, O(3n)
d)
f(n)=2n+8. O(n)
e)
6n+4
29.

  1. Кој од следните алгоритми има еднаква најдобра, најлоша и просечна временска комплексност?

a)

Heap sort ( + Merge sort, Radix, Counting)

b)

  • Insertion sort

c)

  • Bubble sort

d)

  • Quick sort 

30.

Колкава е сложеноста на алгоритмот со кој се прави спојување на две сортирани листи со големина m и n во сортирана листа со големина m + n?

a)

O(logm + logn)

b)

O(n)

c)

  • О(m)

d)

  • O(m+n)

31.

Дадени се следните функции:
push(): push (додади) елемент на стекот
pop() : pop (избриши) го елементот од врвот на стекот
top() : врати го елементот кој е на врвот на стекот
Кој ќе биде излезот откако ќе се изврши следната низа на операции:
push(20);
push(4);
top();
pop();
pop():
push(5); 
top();

a)

5

b)

4

c)

  • 20

d)

  • stack underflow

32.

Што значи кога велиме дека алгоритамот Х е асимптотски поефикасен од Ү?

a)

X секогаш ќе биде подобар избор за големи влезови

b)

  • Ү секогаш ќе биде подобар избор за мали влезови

c)

  • Х секогаш ќе биде подобар избор за сите влезови

d)

  • X секогаш ќе биде подобар избор за мали влезови

33.

  1. Која е просторната (мемориската) сложеност за бришење на поврзана листа?

a)

  • O(logn)

b)

  • Или O(1) или O(n)

c)

  • О(1)

d)

  • O(n)

34.

  1. За временската комплексност на пребарување во хеш табела со CВНТ и ОВНТ важи:

a)

  • Комплексноста во најлош случај при пребарување со ОВНТ е поголема

b)

  • Во најлош случај, пребарување со CВНТ и ОВНТ имаат иста комплексност

c)

  • Не може да се спореди комплексноста при пребарување во најлош случај меѓу СВЕТ и ОВНТ

d)

  • Комплексноста во најлош случај при пребарување со CBHT е поголема

35.

  1. Клучевите 12, 18, 13, 2, 3, 23, 5 и 15 се внесуваат во иницијално празна хеш табела со должина 10 која користи ОВНТ со хеш функција h(k) =k mod 10  со ѕtер(k) = k mоd 5. Која е резултантната хеш табела?

a)

А

b)

B

c)

C

d)

D

36.

  1. Еднократната ротација кај AVL дрво може да се изврши врз

a)

  • коренот на дрвото

b)

  • јазелот со најмала вредност од дрвото

c)

  • било кој лист од дрвото

d)

  • било кој јазел од дрвото

37.

За дадениот граф, почнувајќи од темето А, кој е точниот редослед на ребра кои се додаваат во минималното распнувачко стебло со примена на алгоритмот на Прим?

a)

  • (A, G) — (А, В) — (А, С) — (A, D) — (A, D) – (C, F)

b)

  • (A, G) — (G, C) – (С, В) — (C, F) — (F, E) — (E, D) - 

c)

  • (A, G) — (B, C) — (E, F) — (А, В. – (C, F) — (D, E)

d)

  • (A, G) — (А, В) — (B, C) – (A, D) — (C, F) – (F, E) -  

38.

Кај AVL дрво длабочината на дрвото (а со тоа и комплексноста на најчестите операции) е од редот ( + BST, B-tree)

a)

  • O(nlog n)

b)

  • O(log n)

c)

  • О(С)

d)

  • O(n)

39.

Изминување на граф е различно од изминување на дрва, бидејќи:

a)

  • графовите може да имаат циклуси

b)

  • дрвата имаат корен

c)

  • дрвата не се поврзани

d)

  • ниту еден одговор не е точен

40.

  1. Доколку бинарното дрво е пребарувачко, тогаш:

a)

Јазелот со најголем клуч е јазелот до кој се доаѓа доколку од коренот се оди само по левите врски се додека не се дојде до листот на дрвото.

b)

  • Јазелот со најмал клуч е јазелот до кој се доаѓа доколку од коренот се оди само по левите врски се додека не се дојде до листот на дрвото.

c)

Јазелот со единствен клуч е јазелот до кој се доаѓа доколку од коренот се оди само по левите врски се додека не се дојде до листот на дрвото.

d)

  • Јазелот со нулев клуч е јазелот до кој се доаѓа доколку од коренот се оди само по левите врски се додека не се дојде до листот на дрвото.

41.

  1.   При бришење на јазел со две деца од пребарувачко дрво,

a)

  • клучот на јазелот што треба да се избрише се заменува со било кој клуч од неговото лево поддрво

b)

  • клучот на јазелот што треба да се избрише се заменува со најголемиот клуч од неговото лево поддрво

c)

  • Клучот на јазелот што треба да се избрише се заменува со најмалиот клуч од неговото лево поддрво

d)

  • клучот на јазелот што треба да се избрише се заменува со најголемиот клуч од неговото десно поддрво

42.

  1. Кој алгоритам е побрз А или В (за дадените времиња на извршување на сликата)?

a)

  • Алгоритамот А

b)

  • Алгоритамот В

c)

  • Исто се брзи

d)

  • Не може да се спореди

43.

  1. Колку е O() за дадениот код?

a)

O(1)

b)

О(a*n)

c)

O(n)

d)

O(n^2)

44.

  1. Колку е O() за дадениот код? 

a)

  • O(n^3)

b)

  • О(і)

c)

  • O(n) 

d)

  • O(n^2)

45.

  1. Што од наведеното е точно?

a)

  • AVL дрвото има подредено (сортирано) преордер изминување.

b)

  • AVL дрвото има поврзани терминални јазли.

c)

  • AVL дрвото мора да биде балансирано.

d)

  • AVL дрвото има константен степен на своите јазли.

46.

  1. Во кој случај е препорачливо да се користи Insertion sort за сортирање на низа од броеви ?

a)

  • Кога броевите во низата се рамномерно дистрибуирани во одреден опсег

b)

Кога низата е скоро сортирана

c)

  • Кога имаме голем број на различни елементи

d)

  • Кога имаме мал број на различни елементи

47.

Кој е излезот после дадената листа на операции:

  1. push(5)
    push(8)
    pop
    push(2)
    push(5)
    pop
    pop 
    pop
    push(1)
    pop

a)

  • 8 5 5 2 1

b)

  • 8 5 2 5 1

c)

  • 8 2 5 5 1 

d)

  • 8 1 2 5 5

48.

  1. Кај двојно поврзана листа, додавањето на нов елемент после веќе покажан елемент има сложеност:

a)

  • O(n*log(n))

b)

  • O(n)

c)

  • O(n*n)

d)

ниту едно од понудените

49.

  1. Во нетежински ненасочен поврзан граф, најкраткиот пат од јазол S до секој друг јазол, најефикасно може да се пронајде, во смисол на временска комплексност, со:

a)

  • Алгоритмот на Крускал

b)

  • Ширинско изминување на графот (BFS)

c)

  • Длабочинско изминување на графот (DFS)

d)

  • Алгоритмот на Дијкстрa 

50.

  1. Which of the following graphs is isomorphic to: 

a)

b)

c)

d)

51.

  1. Доколку дрвото на сликата се трансформира во бинарно дрво тогаш кој јазол ќе биде десно дете на јазолот 2? 

a)

5

b)

1

c)

  • нема да има такво дете

d)

  • 3

52.

Доколку дрвото на сликата се трансформира во бинарно дрво тогаш кој јазол ќе биде десно дете на јазолот 5?

a)

8

b)

7

c)

6

d)

нема да има такво дете

53.

Податочната структура heap, може да се имплементира со помош на еднодимензионална низа поради фактот што:

a)

  • е комплетно дрво  

b)

  • е бинарно дрво 

c)

  • е слабо подредено бинарно дрво 

d)

  • ги задоволува условите на heap дрво

54.

Земете го предвид следниот граф. Користејќи го алгоритмот на Крускал, кое ребро треба да биде избрано прво?

a)

  • BG

b)

DE

c)

GF

d)

BE

55.

  1. Наоѓање јазол во бинарно пребарувачко дрво вклучува одење од јазол на јазол и прашување:

a)

  • кој јазол-лист сакаме да го достигнеме

b)

  • на кое ниво сме

c)

  • дали јазолот што го бараме е поголем/помал од моменталниот јазол

d)

  • дали јазолот что го бараме е поголем/помал од десното или левото дете

56.

Секое В-дрво од ред п, колку клучеви може да има во внатрешен јазел?

a)

n

b)

  • n-1

c)

2

d)

1

57.

Нацртајте ја хеш табела со затворени кофички со должина 9 по вметнување на елементите 10, 35, 18, 2, 19, 26, 9, 28. Како хеш фчппункција се користи h(x)= x mod 9. Колку елементи ќе има во кофичките со реден број 1 и 2?

a)

  • 2 и 2

b)

  • 3 и 1 

c)

  • 3 и 0

d)

  • 2 и 0

58.

Како ќе изгледа резултатот од inorder изминувањето на следното дрво: 

a)

  • М В Ш Ќ Г Ј

b)

  • Ј В М Г Ќ Ш

c)

  • В М Ј Г Ќ Ш

d)

  • М В Ј Г Ќ Ш

59.

  1. Нека е дадена репрезентацијата на графот со матрица на соседство А = [0 1 1 0; 0 0 0 1; 0000; 0010, каде што редоследот на колоните и редиците е 1, 2, 3, 4, соодветно. Ако се примени пребарување по длабочина почнувајќи од темето 2 тогаш кој од следните исписи на темињата е можен.

a)

  • 2 4 3 

b)

  • 1 2 4 3

c)

  • 2 1 3 4

d)

2 3 1 4

60.

  1. При пребарување во ОВНТ, алгоритамот застанува кога:

a)

  • Кофичката b е никогаш-зафатена 

b)

  • Кофичката б е зафатена 

c)

  • кофичката b е претходно-зафатена 

d)

  • Кофичката b е никогаш-зафатена или кофичката b е зафатена со еднаков клуч

61.

  1. Најдобри перформанси при користење на ОВНТ се добиваат со:

a)

  • Една хеш функција и степ функција со чекор 1

b)

  • Една хеш функција и една степ функција со произволен чекор

c)

  • Една хеш функција и степ функција со двојно хеширање

d)

  • Една хеш функција

62.

Нека е дадена следната хеш табела која користи отворени кофички. Хеш функцијата е h(x)= x mod 9, а додека пак чекорот е step(k) = 1. По кој редослед биле додавани елементите во хеш табелата? Постојат повеќе точни одговори.

a)

  • 9 14 4 18 12 3 21

b)

  • 9 12 14 3 4 21 18

c)

  • 12 3 14 18 4 9 21

d)

12 9 18 3 14 21 4

63.

  1. При бришење јазел од heap дрво потребно е да се направат следните акции:

a)

  • Бришење на коренот на дрвото; Прилагодување на heap дрвото

b)

  • Бришење на коренот на дрвото и на негово место поставување на најдесниот јазел

c)

  • Бришење на најдесниот јазел-лист

d)

  • Бришење на најмалиот елемент во hеар дрвото

64.

  1. Кога би требало во една хеш табела да Сместиме 1000 податоци кои претставуваат имиња на артикли со соодветен бар код, како ќе ја креираме мапата (клуч, вредност)?

a)

  • (име-артикл, бар-код) 

b)

  • (бар-код, име-артикл)

c)

  • (име-артикл, име-артикл+бар-код) 

d)

  • (бар-код, име-артикл+бар-код)

65.

Која од следните би била најдобар избор за хеш функција?

a)

  • Нема воопшто колизии, а сложеноста е непозната

b)

  • Има многу ретки колизии, а сложеноста е O(logN)

c)

  • Нема воопшто колизии, а сложеноста е O(N)

d)

  • Има ретки колизии, а сложеноста е O(1)

66.

При работа со CBHT вметнување елемент во листата на кофичката со клуч hash(key) се прави со која операција од SLL?

a)

insertFirst

b)

insertLast

c)

insertBefore

d)

insertAfter

67.

Нека е дадено следното BST.

После пришење на ел. 2 дрвото ќе изгледа вака:

a)

  • 6-2-8-1-4-3-5 

b)

  • 6-1-8-4-3-5 

c)

  • 6-5-8-1-4-3 

d)

6-3-8-1-4-5

68.

Бинарно пребарувачко дрво е:

a)

Комплетно бинарно дрво во кое секој јазел што претставува корен на свое поддрво има минимална вредност

b)

  • Полно бинарно дрво во кое елементите во левото поддрво се помали или еднакви на коренот, а елементите во десното поддрво се поголеми од коренот

c)

Бинарно дрво во кое елементите во левото поддрво се строго помали, а оние во десното поддрво строго поголеми од коренот

69.

Да се конструира бинарно пребарувачко дрво, ако при изминување со преордер начин се добива следнава секвенца: 10, 4, 3, 5, 11, 12.

a)

b)

c)

70.

Кој алгоритам може да се искористи за пресметка на рата на кредит?

a)

  • DFS

b)

  • Бинарно пребарување

c)

  • Сортирање со спојување

d)

  • BFS

Similar Resources on Wayground

Итоговая викторина ГД

72 questions

Итоговая викторина ГД

quiz

Worksheet

•

1st - 5th Grade