3/8/2020 Test Canvas: Last year's e-test for practice – CSU22010-...
https://tcd.blackboard.com/webapps/assessment/do/authoring/modifyAssessment?blackboard.platform.security.NonceUtil.nonce=76705a41-3774… 1/9
Edit Mode is: ON•

Test Canvas : Last year's e-test for practice
CSU22010-A-YEAR02-201920 ALGORITHMS AND DATA STRUCTURES Tests, Surveys and Pools
Tests
Test Canvas: Last year's e-test for practice
The Test Canvas lets you add, edit and reorder questions, as well as review a test. More Help
Description
Instructions
Total
Questions
14
Total Points 100
Select: Select by Type: - Question Type -
Points
Please do not start the test until instructed to do so by a demonstrator.
The test is multiple choice, and it consists of 14 questions. You have 45 minutes in
total to complete the test. 
Once you press submit your answers cannot be changed, so please double-check
all of your answers before submitting. 
All None
Delete Update Hide Question Details
1. Multiple Choice: Insertion sort is an example of
which...
Question
Answer
Insertion sort is an example of which algorithm design approach
Greedy
Brute force
Decrease and conquer
?
My Learning Space Student Help Sta Help
Question Settings
Create Question Reuse Question Upload Questions
Module List
Points: 6
IVANA DUSPARIC 2
3/8/2020 Test Canvas: Last year's e-test for practice – CSU22010-...
https://tcd.blackboard.com/webapps/assessment/do/authoring/modifyAssessment?blackboard.platform.security.NonceUtil.nonce=76705a41-3774… 2/9
Divide and conquer
2. Multiple Choice: Which one of the sorting
algorithms l...
Question
Answer
Which one of the sorting algorithms listed below is NOT stable?
Insertion
Selection
Merge sort
All 3 are stable
3. Multiple Choice: What is the worst case input
for stan...
Question
Answer
What is the worst case input for standard quicksort, if the rst element
in the (sub)array is always used as a pivot?
already sorted array
random array
array with a very few unique values
it does not matter - performance of quicksort is the same
regardless of input order
4. Multiple Choice: What is the worst case
complexity for...
Points: 6
Points: 6
Points: 6
3/8/2020 Test Canvas: Last year's e-test for practice – CSU22010-...
https://tcd.blackboard.com/webapps/assessment/do/authoring/modifyAssessment?blackboard.platform.security.NonceUtil.nonce=76705a41-3774… 3/9
Question
Answer
What is the worst case complexity for merge sort algorithm?
O(n^2)
O(n log n)
O(n)
O(log n)
5. Multiple Choice: Which of the following
algorithms,&nb...
Question
Answer
Which of the following algorithms, in its basic implementation, has
space complexity of O(n)?
insertion sort
bubble sort
quick sort
merge sort
6. Multiple Choice: Given an array of 8 almost
sorted int...
Question
Answer
Given an array of 8 almost sorted integers, which of the following
algorithms would be the most suitable to use to sort it?
Insertion sort
Merge sort
Quick sort
Points: 6
Points: 6
3/8/2020 Test Canvas: Last year's e-test for practice – CSU22010-...
https://tcd.blackboard.com/webapps/assessment/do/authoring/modifyAssessment?blackboard.platform.security.NonceUtil.nonce=76705a41-3774… 4/9
Bubble sort
7. Multiple Choice: Which one of the following
sort algor...
Question
Answer
Which one of the following sort algorithms is generally not
implemented using recursion?
Most Signicant Digit Radix Sort
Least Signicant Digit Radix Sort
Merge sort
quick sort
8. Multiple Choice: Which of the following
substring sear...
Question
Answer
Which of the following substring search algorithms does NOT require
backup?
Knuth-Morris-Prath
Brute force approach
Boyer-Moore
all of the above require backup
9. Multiple Choice: Implementation of Knuth-
Morris-Prath&...
Question
Points: 6
Points: 6
Points: 6
3/8/2020 Test Canvas: Last year's e-test for practice – CSU22010-...
https://tcd.blackboard.com/webapps/assessment/do/authoring/modifyAssessment?blackboard.platform.security.NonceUtil.nonce=76705a41-3774… 5/9
Answer
Implementation of Knuth-Morris-Prath (KMP) string search algorithm
requires the following amount of additional space, where M is the
length of the string to be searched for, N is the length of the text in
which we are searching, and R is the radix of the alphabet we are
working with
N
MR
R
M^2
10. Multiple Choice: What is the worst case
performance of...
Question
Answer
What is the worst case performance of Boyer Moore string search
algorithm, if N is the size of the string we are searching for, M is the
size of the text in which we are searching, and R the radix of the algo
MR
M^2
M
MN
11. Multiple Choice: Assume you are searching for
a string...
Question
Answer
Assume you are searching for a string "BANANA" using Boyer-Moore
algorithm. What is the nal content of the "skip array" going to be,
assuming the alphabet consists only of letters A B C D and N
Points: 6
Points: 10
3/8/2020 Test Canvas: Last year's e-test for practice – CSU22010-...
https://tcd.blackboard.com/webapps/assessment/do/authoring/modifyAssessment?blackboard.platform.security.NonceUtil.nonce=76705a41-3774… 6/9
A 1
B 0
C 0
D 0
N 2
A 1
B 0
C -1
D -1
N 2
A 5
B 0
C -1
D -1
N 4
A 5
B 0
C -1
D -1
N -1
12. Multiple Choice: Assume the following DFA
table has be...
Question
Points: 10
3/8/2020 Test Canvas: Last year's e-test for practice – CSU22010-...
https://tcd.blackboard.com/webapps/assessment/do/authoring/modifyAssessment?blackboard.platform.security.NonceUtil.nonce=76705a41-3774… 7/9
Answer
Assume the following DFA table has been constructed to search for a
string "ABABAC" using KMP algorithm.
The string which you are searching in is "ABABABABACAB". 
Which of the answers below shows the correct trace of states of DFA
this search would produce until it nds a full match?
0,1,2,3,4,5,0,1,2,3,4,5,4,5,6
0,1,2,3,4,5,4,5,4,5,6,4,5
0,1,2,3,4,5,4,5,4,5,6
0,1,2,3,4,5,6
13. Multiple Choice: Assume you are required to
sort the f...
Question
Points: 10
3/8/2020 Test Canvas: Last year's e-test for practice – CSU22010-...
https://tcd.blackboard.com/webapps/assessment/do/authoring/modifyAssessment?blackboard.platform.security.NonceUtil.nonce=76705a41-3774… 8/9
Answer
C A T
C A R
A R T
B A R
B O T
C O T
Assume you are required to sort the following array using the LSD
(Least Signicant Digit) radix sort algorithm.
Which of the answers below shows how will array look like after the
FIRST pass (out of the total of 3 passes) of the algorithm through index
key counting?
C A R
B A R
C A T
A R T
B O T
C O T
A R T
B A R
B O T
C O T
C A T
C A R
C A R
B A R
A R T
B O T
C A T
C O T
3/8/2020 Test Canvas: Last year's e-test for practice – CSU22010-...
https://tcd.blackboard.com/webapps/assessment/do/authoring/modifyAssessment?blackboard.platform.security.NonceUtil.nonce=76705a41-3774… 9/9
Select: Select by Type: - Question Type -
Points
A R T
B A R
B O T
C A T
C A R
C O T
14. Multiple Choice: You are required to sort the
followin...
Question
Answer
You are required to sort the following array using merge sort { 2, 11,
7, 8, 3, 19, 13, 5 }. How many calls to the "merge" method will be
made during the top down merge sort execution? 
5
7
8
10
All None
Delete Update Hide Question Details
← OK
Points: 10

欢迎咨询51作业君