Free Printable Data Structure - Final Assessment (18-7-2023)

1.

Which sorting algorithm makes one swap per pass (possibly swapping an element with itself)?

a)

Selection Sort

b)

Bubble Sort

c)

Insertion Sort

2.

Which sorting algorithm may make multiple swaps per pass?

a)

Bubble Sort

b)

Selection Sort

c)

Insertion Sort

3.

Which sorting algorithm shifts elements instead of swapping elements if needed in each pass.

a)

Bubble Sort

b)

Selection Sort

c)

Insertion Sort

4.

The following lists represent 3 passes of a sorting algorithm. Which algorithm is being used to sort the list?

4 8 6 2 5 7
4 8 6 2 5 7
4 6 8 2 5 7

a)

Bubble Sort

b)

Selection Sort

c)

Insertion Sort

5.

We are sorting the following list in ascending order:

1 4 2 9 3 8 5

What does the list look like after one pass of the bubble sort algorithm.

a)

1 2 4 3 8 5 9

b)

1 4 2 5 3 8 9

c)

4 2 9 3 8 5 1

6.

Time complexity of bubble sort in best case is

a)

a) θ (n)

b)

b) θ (nlogn)

c)

c) θ (n²)

d)

d) θ (n(logn) ²)

7.

Which of these algorithms sorts items by first splitting the list of items down into smaller and smaller groups?

a)

Bubble sort

b)

Merge sort

c)

Linear search

d)

Binary search

8.

What algorithm does this image represent?

a)

Bubble sort

b)

Merge sort

c)

Linear search

d)

Binary search

9.

Which type of sort algorithm is this?

a)

Insertion

b)

Merge

c)

Bubble

10.

Partition a list A[] into two non-empty parts.

in left part the values should be:

a)

A [ ] <= pivot

b)

A [ ] > pivot

c)

A[] >= pivot

d)

A [ ] < pivot

11.

Partition a list A[] into two non-empty parts.

in right part the values should be:

a)

A [ ] > pivot

b)

A [ ] >= pivot

c)

A [ ] < pivot

d)

A [ ] <= pivot

12.

Which algorithm matches this description: "a sorting algorithm that repeatedly partitions the input into low and high parts (each part unsorted), and then recursively sorts each of those parts."

a)

Selection Sort

b)

Insertion Sort

c)

Shell Sort

d)

Quicksort

13.

Which of the following is a max-heap?

a)

b)

c)

d)

14.

Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?

a)

25,12,16,13,10,8,14

b)

25,12,16,10,13,8,14

c)

25,14,16,13,10,8,12

d)

25,14,12,13,10,8,16

15.

The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a Max Heap. The resultant Max Heap is.

a)

b)

c)

d)

16.

Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

a)

40, 30, 20, 10, 15, 16, 17, 8, 4, 35

b)

40, 35, 20, 10, 30, 16, 17, 8, 4, 15

c)

40, 30, 20, 10, 35, 16, 17, 8, 4, 15

d)

40, 35, 20, 10, 15, 16, 17, 8, 4, 30

17.

Given a binary-max heap. The elements are stored in an arrays as 25, 14, 16, 13, 10, 8, 12. What is the content of the array after two delete operations?

a)

14,13,8,12,10

b)

14,12,13,10,8

c)

14,13,12,8,10

d)

14,13,12,10,8

18.

The 2 properties of a min heap are _____.

a)

Tree must be full.

b)

Tree must be complete.

c)

Node values are always smaller than their children's values.

d)

Node values are always greater than their children's values.

19.

How many swaps are made in the min heap when inserting the value 18?

a)

0

b)

1

c)

2

d)

3

20.

When removing the root from a min heap, what is the first step?

a)

Replace the root with the next smallest value from the tree

b)

Replace the root with the leaf furthest to the left on the bottom level of the tree

c)

Replace the root with the leaf furthest to the right on the bottom level of the tree

d)

Replace the root with the smallest of its children

21.

When adding a value to a min heap, the first step is to ______.

a)

Add the new node at the next open leaf.

b)

Replace the root's value with the new value.

c)

Replace the roots smallest child with the new value.

d)

Add the new node as far right as possible on the bottom level of the tree.

22.

Select the best description to explain what a linear search algorithm is.

a)

Put the elements in order, check each item in turn.

b)

Put the elements in order, compare with the middle value, split the list in order and repeat.

c)

Elements do not need to be in order, check each item in turn.

d)

Elements do not need to be in order, compare to the middle value, split the list in order and repeat

23.

Select the best description to explain what a binary search algorithm is.

a)

Put the elements in order, check each item in turn.

b)

Put the elements in order, compare with the middle value, split the list in order and repeat.

c)

Elements do not need to be in order, check each item in turn.

d)

Elements do not need to be in order, compare to the middle value, split the list in order and repeat

24.

A linear search is to be performed on the list:
12 6 8 1 3
How many comparisons would it take to find number 1?

a)

1

b)

2

c)

3

d)

4

25.

A binary search is to be performed on the list:
3 5 9 10 23
How many comparisons would it take to find number 9?

a)

0-1

b)

2-3

c)

4-5

d)

I can't find the number 9

26.

A binary search is to be performed on the list:
1 5 10 13 48 68 100 101
How many comparisons would it take to find number 101?

a)

0-1

b)

1-2

c)

3-4

d)

4-5

27.

Describe an advantage of a binary search algorithm

a)

Data does not need to be in order.

b)

Performs well over large ordered lists.

c)

Can only work on an ordered list. If unordered must use a linear search.

d)

Slow with large data sets.

28.

int nums[ ] =

{2, 3, 5, 8, 9, 11};

How would you access the fourth element in nums

a)

nums[8]

b)

nums[3]

c)

nums(4)

d)

nums(3)

29.

Which of the following is NOT a Type of Data Structures?

a)

Arrays

b)

Tables

c)

Stacks

d)

Trees

30.

A FIFO structure implemented as a ring where the front and rear pointers can wrap around the end of the start of the array.

a)

Linear Queue

b)

Circular Queue

c)

Priority Queue

31.

LIFO stands for

a)

List of Outputs

b)

Last in First Out

c)

First in Last Out

d)

None of them

32.

Act of adding values into a stack is called

a)

Popping

b)

Polling

c)

Pushing

d)

None

33.

If the elements “A”, “B”, “C” and “D” are placed in a stack and are deleted one at a time, in what order will they be removed?

a)

ABCD

b)

DCBA

c)

DCAB

d)

ABDC

34.

In some languages, arrays are also called ___

a)

groups or arrows

b)

roots or leaves

c)

lists or vectors

d)

lines or strings

35.

A data type that can be used to group items of possibly different types into a single type is called ___

a)

a root

b)

a struct

c)

a tree

d)

a pointer

36.

A flexible data structure that can store many nodes is called ___

a)

a tree

b)

a linked list

c)

a pointer

d)

a queue

37.

When linked lists are used as stacks, what kind of behaviour is implemented?

a)

First-In First-Out, or FIFO

b)

First-In Last-Out, or FILO

c)

Last-In Last-Out, or LILO

d)

Last-In First-Out, or LIFO

38.

In a tree data structure, the top most node is called ___

a)

the peak

b)

the apex

c)

the crown

d)

the root

39.

In a tree data structure, any nodes that hang from other nodes are called ___

a)

branched nodes

b)

leaf nodes

c)

children nodes

d)

daughter nodes

40.

In a tree data structure, any nodes that have no children (where the tree ends) are called ___

a)

boundary nodes

b)

leaf nodes

c)

orphan nodes

d)

terminal nodes

41.

What is the value of the ROOT node in this Tree?

a)

35

b)

24

c)

42

d)

20

42.

Root

a)

data structure similar to a graph, with no loops.

b)

an object in a graph also known as a vertex

c)

a join of relationship between nodes - also know as an arc

d)

the starting node in a rooted tree structure from which all other nodes branch off./

43.

Tree

a)

data structure similar to a graph, with no loops.

b)

an object in a graph also known as a vertex

c)

a join of relationship between nodes - also know as an arc

d)

the starting node in a rooted tree structure from which all other nodes branch off./

44.

How many leaf are there in the tree?

a)

1

b)

3

c)

4

d)

7

45.

Which Time and Space Complexity uses the O(n²) notation?

a)

Quadratic

b)

Linear

c)

Exponential

d)

Logarithmic

46.

What is the time complexity of this code

int a = 0, i = N;

while (i > 0)

{

a += i;

i /= 2;

}

a)

O(N)

b)

O(Sqrt(N))

c)

O(N / 2)

d)

O(log N)

47.

The complexity of Binary search algorithm is

a)

O(n)

b)

O(log n)

c)

O(n2)

d)

O(n log n)

48.

What is the time complexity of following code:

int a = 0;

for (i = 0; i < N; i++) {

for (j = N; j > i; j--) {

a = a + i + j;

}

a)

O(N)

b)

O(N*log(N))

c)

O(N * Sqrt(N))

d)

O(N*N)

49.

What is the time complexity of following code:

int i, j, k = 0;

for (i = n / 2; i <= n; i++) {

for (j = 2; j <= n; j = j * 2) {

k = k + n / 2;

}

a)

O(n)

b)

O(nLogn)

c)

O(n^2)

d)

O(n^2Logn)

50.

A linear function takes the form

a)

f(n) = an + b

b)

f(n) = an2 +bn + c

c)

f(n) = alog2n

d)

f(n) = a + b

51.

Find the slowest algorithm:

a)

O (n)

b)

O (n^2)

c)

O (n!)

d)

O (2^n)

52.

The number of executions grows extremely quickly as the size of the input increases

a)

Exponential Time

b)

Linear Time

c)

Polynomial Time

d)

Constant Time

53.

What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

a)

X will be a better choice for all inputs

b)

X will be a better choice for all inputs except possibly small inputs

c)

X will be a better choice for all inputs except possibly large inputs

d)

Y will be a better choice for small inputs

54.

Consider this list of numbers: 3 4 6 7 8 9. If the number 9 was to be found using a linear search, how many comparisons need to be made?

a)

6

b)

3

c)

8

d)

4

55.

What is the main disadvantage of a binary search compared to a linear search?

a)

It requires the data to be in order

b)

It requires more memory

c)

It does not execute as quickly with larger data sets

d)

Not all CPUs are capable of executing the algorithm

56.

Consider this list of numbers L: 3 4 5 6 7 8 9. Which number would be checked first in a binary search?

a)

6

b)

3

c)

9

d)

4

57.

What is the worst case running time of the above pseudo code?

a)

O(n)

b)

O(n log n)

c)

O(n²)

d)

O(n³)

58.

What is the worst case running time of the above pseudo code?

a)

O(n)

b)

O(n log n)

c)

O(n²)

d)

O(n³)

59.

asymptotic notations represents

a)

space complexity of algo

b)

time complexity of algo

c)

both a and b

d)

none of the above

60.

Big

\Omega

defines

a)

lower bound

b)

upper bound

c)

middle bound

d)

none of the above

61.

What is the worst case complexity of selection sort?

a)

O(n log n)

b)

O(log n)

c)

O(n)

d)

O(n2)

62.

The stack is also known as?

a)

Last in first out

b)

First in last out

c)

First in first out

d)

.none of these

63.

define the name of the process in which items are added at one end and removed from another side?

a)

stack

b)

Queue

c)

List

d)

Tree

64.

Define the value of r in a circular queue?

a)

r=r+1

b)

r=(r+1)%[QUEUE_SIZE=1]

c)

r=(r+1)% QUEUE_SIZE

d)

r=(r-1)% QUEUE_SIZE

65.

What is the worst case complexity of bubble sort?

a)

O(nlogn)

b)

O(logn)

c)

O(n)

d)

O(n2)

66.

The measure of the longest amount of time possibly taken to complete an algorithm is expressed as __.

a)

Little-O

b)

Little-Omega

c)

Big-Omega

d)

Big-O

67.

___ of an algorithm is the amount of time required for it to execute.

a)

Time complexity

b)

Space complexity

c)

Compiling time

d)

Best case

68.

___ is the maximum amount of time an algorithm takes to execute a specific set of inputs.

a)

Running time

b)

Average case time complexity

c)

Worst case time complexity

d)

Best case time complexity

69.

Which one of the following helps in calculating the longest amount of time taken for the completion of the algorithm?

a)

Theta notation

b)

Big-Oh notation

c)

Omega notation

d)

Time complexity

70.

Which method is practical to perform a single search in an unsorted list of elements?

a)

Sequential search

b)

Bubble sort

c)

Horspool’s method of string matching

d)

Brute force method of string matching

71.

Which of the following best describes the useful criterion for comparing the efficiency of algorithms?

a)

Time

b)

Memory

c)

Both of the above

d)

None of the above

72.

What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

a)

X will always be a better choice for small inputs

b)

X will always be a better choice for large inputs

c)

Y will always be a better choice for small inputs

d)

X will always be a better choice for all inputs

73.

If for an algorithm time complexity is given by O(1) then complexityof it is:

a)

constant

b)

polynomial

c)

exponential

d)

none of the mentioned

74.

If for an algorithm time complexity is given by O(n) then complexityof it is:

a)

constant

b)

linear

c)

exponential

d)

none of the mentioned

75.

What is the time complexity of following code:

int a = 0, i = N;

while (i > 0)

{

a += i;

i /= 2;

}

a)

O(N)

b)

O(Sqrt(N))

c)

O(N / 2)

d)

O(log N)

76.

The asymptotic upper-bound of $f\left(n\right)=20n^2+100n+2$ is $O\left(n^2\right)$

a)

True

b)

False

77.

The asymptotic upper-bound of $f\left(n\right)=2n+2^n$ is $O\left(n^2\right)$

a)

True

b)

False

78.

If for an algorithm time complexity is given by O(1) then complexity of it is

a)

constant

b)

polynomial

c)

exponential

d)

none of the mentioned

79.

If for an algorithm time complexity is given by O(n) then complexity of it is

a)

constant

b)

linear

c)

exponential

d)

none of the mentioned

80.

What is the time complexity of following code

int a = 0, i = N;

while (i > 0) {

a + = i;

i / = 2;

}

a)

O(N)

b)

O(Sqrt(N))

c)

O(N / 2)

d)

O(log N)

81.

The linear/sequential search method to search an element in an array has the complexity of BigO(?)

a)

n

b)

n-1

c)

n^2

d)

n logn

82.

Indicate exponential time complexity in terms of big-O notation

a)

O (n)

b)

O (n^2)

c)

O (2^n)

d)

O (log n)

83.

Find the slowest time complexity

a)

O (n)

b)

O (n^2)

c)

O (n!)

d)

O (2^n)

84.

Which notation is consistent for every execution?

a)

O (n)

b)

O (n^2)

c)

O (1)

d)

O (2^n)

85.

Which notation grows in proportion to the size of the input

a)

O (n)

b)

O (n^2)

c)

O (1)

d)

O (2^n)

86.

Which notation would you usually use for a nested loop?

a)

O (n)

b)

O (n^2)

c)

O (1)

d)

O (2^n)

87.

The number of executions grows extremely quickly as the size of the input increases

a)

Exponential Time

b)

Linear Time

c)

Polynomial Time

d)

Constant Time

88.

The number of executions remains the same regardless of the input size

a)

Exponential Time

b)

Linear Time

c)

Polynomial Time

d)

Constant Time

89.

The number of executions grows quickly by the input being multiplied by the input

a)

Exponential Time

b)

Linear Time

c)

Polynomial Time

d)

Constant Time

90.

For every element, you are doing a constant number of operations, such as comparing each element to a known value.

a)

Quadratic

b)

Linear

c)

Logarithmic

d)

Constant

e)

Exponential

91.

What is the correct Big O notation for an algorithm where the number of operations (steps) can be expressed as:

$4n^3\ +3n\ \log_2n\ \ +\ 273$ n is the size of the input.

a)

$O\left(n^2\right)$

b)

$O\left(3n\right)$

c)

$O\left(\log_2n\right)$

d)

$O\left(273\right)$

e)

$O\left(n^3\right)$

92.

What is the big-Oh runtime of A()?

a)

$O\left(n\log_{ }n\right)$

b)

$O\left(n^2\right)$

c)

$O\left(n\right)$

d)

$O\left(10\cdot n\right)$

93.

What is true for $f\left(n\right)=\log_{ }n$ and $g\left(n\right)=n$ ?

a)

$f\left(n\right)=O\left(g\left(n\right)\right)$

b)

$f\left(n\right)=\theta\left(g\left(n\right)\right)$

c)

$f\left(n\right)=\Omega\left(g\left(n\right)\right)$

94.

What is the maximum number of comparisons that a binary search will apply for an array of length 30.

a)

30

b)

15

c)

5

d)

3

e)

2

95.

What is the big-Oh runtime of B()?

a)

$O\left(n^2\right)$

b)

$O\left(n^3\right)$

c)

$O\left(30\cdot n\right)$

d)

$O\left(n\right)$

96.

Which of these is true for $f\left(n\right)=5n^3+7n+13$ and $g\left(n\right)\ =\ n^5$ ?

a)

$f\left(n\right)=\theta\left(g\left(n\right)\right)$

b)

$f\left(n\right)=\Omega\left(g\left(n\right)\right)$

c)

$f\left(n\right)=O\left(g\left(n\right)\right)$

97.

What is the big-Oh runtime of C(n)?

a)

$O\left(10\right)$

b)

$O\left(n\right)$

c)

$O\left(\frac{n}{2}\right)$

d)

$O\left(\log_{ }n\right)$

98.

Which of the following is the time complexity of insertion sort?

a)

$O(n^2)$

b)

$O(\log n)$

c)

$O(n)$

d)

$O(n\log n)$

99.

Which is true for $f\left(n\right)=2^n$ and $g\left(n\right)=n!$ ?

a)

$f\left(n\right)=O\left(g\left(n\right)\right)$

b)

$f\left(n\right)=\theta\left(g\left(n\right)\right)$

c)

$f\left(n\right)=\Omega\left(g\left(n\right)\right)$

100.

What is the big-Oh runtime of D(n)?

a)

$O\left(n\cdot\log_{ }n\right)$

b)

$O\left(n^2\right)$

c)

$O\left(\log_{ }n\right)$

d)

$O\left(2n\right)$

Data Structure - Final Assessment (18-7-2023)

Total questions: 100

Worksheet time: 2hrs 40mins

Similar Resources on Wayground