微信客服：xiaoxionga100
微信客服：ITCS521
Java代写-COMP3506/COMP7505
时间：2021-02-03
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 1 of 13
School of Information Technology and Electrical Engineering
EXAMINATION
Semester Two Def/Supp Examination, 2020
COMP3506/COMP7505 Algorithms and Data Structures
This paper is for all students.
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 2 of 13
Question 1 (9 marks)
a) Use the definition of big-Theta notation to show 7 + n + 5n log n is Θ(n log n).
(2 marks)
The following algorithm takes a non-empty proper binary tree and prints it. You may
wish to recall that a proper binary tree is a binary tree in which each node is either
external or has exactly two children. The expression newIndent ¬ indent + " " creates
a new string that contains the characters in the string indent appended by the single
space character and assigns it to the variable newIndent. The string indent is not
modified by the assignment: the characters from it are copied over to the newly created
string.
Algorithm: print(tree)
return printHelper(tree, tree.root(), "")
Algorithm: printHelper(tree, node, indent)
System.out.println(indent);
System.out.println(node.getElement());
if tree.isInternal(node) then
newIndent ¬ indent + " "
printHelper(tree, tree.leftChild(node), newIndent)
printHelper(tree, tree.rightChild(node), newIndent)
return
b) What is the maximum height of a non-empty proper binary tree containing n nodes
in total? Count the height of a leaf node as being 0.
(2 marks)
c) What is the worst-case time complexity of the above algorithm print, given that
there are n nodes in the parameter tree and that each element in a node is a string
of no more than 30 characters? Express your answer in terms of n in big-O
notation, making the bound as tight as possible and simplifying your answer as
much as possible. Briefly justify your answer and give an example tree of n=7
nodes that would exhibit the worst-case time complexity.
(2 marks)
d) What is the worst-case space complexity of the above algorithm print, given that
there are n nodes in the parameter tree and that each element in a node is a string
of no more than 30 characters? Assume that the parameters in the algorithm and
its helper algorithm are passed by reference. Do not include the space already
consumed by the tree in your calculation. Express your answer in terms of n in
big-O notation, making the bound as tight as possible and simplifying your answer
as much as possible. Briefly justify your answer and give an example tree of n=7
nodes that would exhibit the worst-case space complexity.
(3 marks)
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 3 of 13
Answer Q1 here.
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 4 of 13
Question 2 (7 marks)
a) A bucket sort uses key values as indices into an auxiliary array as part of the
sorting process. Explain how a collection of strings can be sorted using a bucket
sort.
(2 marks)
b) A radix sort is a specialised type of lexicographic sort.
i. Explain how a radix sort can be used to sort a collection of integers.
ii. Compare the performance of using a radix sort versus a bucket sort, to sort a
collection of n integers with values in the range of 0 to N. The comparison
should comment on both run-time complexity and space complexity of both
sorts.
(3 marks)
c) Comparison sorts perform their sorting process by comparing key values to
determine their relative ordering.
i. What is the best-case run-time performance of any comparison sort? Explain
how this can be determined.
ii. Is a bucket sort a comparison sort? Explain why or why not.
(2 marks)
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 5 of 13
Answer Q2 here.
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 6 of 13
Question 3 (6 marks)
a) Construct the min-heap by inserting the keys, 6, 9, 4, 3, 2 and 7, one at a time, in
that order, to an initially empty heap. Draw the heap after each step.
(2 marks)
b) The following tree is a (2,4) tree after inserting the keys 12, 25, 2, 32, 65. Draw
the resulting (2,4) tree after inserting the key 15. Describe what steps were
involved in making the change to the tree’s structure.
(2 marks)
c) Out of the following search trees: AVL trees, Splay trees, (2,4) trees, B-Trees and
red-black trees, which one would be most appropriate for implementing an
Ordered Map that is expected to contain more entries than can be reasonably
expected to fit in main memory? Why?
(2 marks)
12
2 25 32 65
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 7 of 13
Answer Q3 here.
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 8 of 13
Question 4 (3 marks)
Consider character string key consisting of three characters c1, c2, c3 and the
following hash functions for a hash table of size 1250 with linear probing. Which of
the following hash functions are good (less collisions) ones? Describe your answer
briefly. For each hash function, talk about the cases where you get collisions.
a) H1= c1 +5∗c2 mod 1250
b) H2= 10∗c1 +100∗c2 +1000∗c3 mod 1250
c) H3= 11∗c1 +101∗c2 +1001∗c3 mod 1250
Answer Q4 here.
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 9 of 13
Question 5 (6 marks)
a) Represent the last occurrence function for the pattern P="structure", which is used
as part of the Boyer-Moore pattern matching algorithm.
(2 marks)
b) Draw a Standard Trie for the following set of strings: {ab, aa, aab, baa, caab}
(2 mark)
c) Using Huffman’s algorithm, construct a Huffman tree that defines an optimal prefix
code for the string “havaianas”. Show the intermediate states of the priority queue.
(2 marks)
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 10 of 13
Answer Q5 here.
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 11 of 13
Question 6 (9 marks)
A graph is simple if it contains no self-loops (no edges from a vertex to itself) or parallel
edges (i.e. for any pair of vertices v and u, there is at most one edge from v to u).
a) Draw an adjacency matrix representation of the following simple directed graph.
(1 marks)
b) An alternative way to represent a simple undirected graph is to store a list of
vertices in the graph together with a hash table that maps pairs of vertices to
edges. The hash table contains an entry with key (v, u) and value e, if and only if
there is an edge e from vertex v to u in the graph. For instance the directed graph
in part (a) would be represented by the list [v1, v2, v3, v4, v5] of vertices together
with a hash table containing entries ((v1, v4), e1), ((v2, v1), e2), ((v4, v5), e3),
((v5, v3), e4) and ((v1, v5), e5).
Assuming that this alternative representation is well implemented, compare it to
the adjacency matrix representation, taking into consideration the following
aspects:
i. For any two vertices v and u, the time complexity for determining if v and u
are adjacent.
ii. For any vertex v, the time-complexity of creating a list of all of the vertices u
such that there is an edge from vertex v to u.
iii. The space complexity of the different representations.
(6 marks)
c) Decide whether these statements are True or False. You must briefly justify all
your answers to receive full credit.
i. Given an undirected graph, it can be tested to determine whether or not it is
a tree in linear time.
ii. The topological sort of an arbitrary directed acyclic graph G = (V, E) can be
computed in linear time.
(2 marks)
v1 v2
v4 v5
v3
e1
e3
e2
e5 e4
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 12 of 13
Answer Q6 here.
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 13 of 13
Question 7 (0 marks)
Please specify any assumptions you have made in completing this examination and
which questions those assumptions relate to. You may also include queries you may
have made with respect to a particular question, should you have been able to ‘raise
your hand’ in an examination room.
Answer Q7 here.
END OF EXAMINATION
学霸联盟
Page 1 of 13
School of Information Technology and Electrical Engineering
EXAMINATION
Semester Two Def/Supp Examination, 2020
COMP3506/COMP7505 Algorithms and Data Structures
This paper is for all students.
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 2 of 13
Question 1 (9 marks)
a) Use the definition of big-Theta notation to show 7 + n + 5n log n is Θ(n log n).
(2 marks)
The following algorithm takes a non-empty proper binary tree and prints it. You may
wish to recall that a proper binary tree is a binary tree in which each node is either
external or has exactly two children. The expression newIndent ¬ indent + " " creates
a new string that contains the characters in the string indent appended by the single
space character and assigns it to the variable newIndent. The string indent is not
modified by the assignment: the characters from it are copied over to the newly created
string.
Algorithm: print(tree)
return printHelper(tree, tree.root(), "")
Algorithm: printHelper(tree, node, indent)
System.out.println(indent);
System.out.println(node.getElement());
if tree.isInternal(node) then
newIndent ¬ indent + " "
printHelper(tree, tree.leftChild(node), newIndent)
printHelper(tree, tree.rightChild(node), newIndent)
return
b) What is the maximum height of a non-empty proper binary tree containing n nodes
in total? Count the height of a leaf node as being 0.
(2 marks)
c) What is the worst-case time complexity of the above algorithm print, given that
there are n nodes in the parameter tree and that each element in a node is a string
of no more than 30 characters? Express your answer in terms of n in big-O
notation, making the bound as tight as possible and simplifying your answer as
much as possible. Briefly justify your answer and give an example tree of n=7
nodes that would exhibit the worst-case time complexity.
(2 marks)
d) What is the worst-case space complexity of the above algorithm print, given that
there are n nodes in the parameter tree and that each element in a node is a string
of no more than 30 characters? Assume that the parameters in the algorithm and
its helper algorithm are passed by reference. Do not include the space already
consumed by the tree in your calculation. Express your answer in terms of n in
big-O notation, making the bound as tight as possible and simplifying your answer
as much as possible. Briefly justify your answer and give an example tree of n=7
nodes that would exhibit the worst-case space complexity.
(3 marks)
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 3 of 13
Answer Q1 here.
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 4 of 13
Question 2 (7 marks)
a) A bucket sort uses key values as indices into an auxiliary array as part of the
sorting process. Explain how a collection of strings can be sorted using a bucket
sort.
(2 marks)
b) A radix sort is a specialised type of lexicographic sort.
i. Explain how a radix sort can be used to sort a collection of integers.
ii. Compare the performance of using a radix sort versus a bucket sort, to sort a
collection of n integers with values in the range of 0 to N. The comparison
should comment on both run-time complexity and space complexity of both
sorts.
(3 marks)
c) Comparison sorts perform their sorting process by comparing key values to
determine their relative ordering.
i. What is the best-case run-time performance of any comparison sort? Explain
how this can be determined.
ii. Is a bucket sort a comparison sort? Explain why or why not.
(2 marks)
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 5 of 13
Answer Q2 here.
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 6 of 13
Question 3 (6 marks)
a) Construct the min-heap by inserting the keys, 6, 9, 4, 3, 2 and 7, one at a time, in
that order, to an initially empty heap. Draw the heap after each step.
(2 marks)
b) The following tree is a (2,4) tree after inserting the keys 12, 25, 2, 32, 65. Draw
the resulting (2,4) tree after inserting the key 15. Describe what steps were
involved in making the change to the tree’s structure.
(2 marks)
c) Out of the following search trees: AVL trees, Splay trees, (2,4) trees, B-Trees and
red-black trees, which one would be most appropriate for implementing an
Ordered Map that is expected to contain more entries than can be reasonably
expected to fit in main memory? Why?
(2 marks)
12
2 25 32 65
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 7 of 13
Answer Q3 here.
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 8 of 13
Question 4 (3 marks)
Consider character string key consisting of three characters c1, c2, c3 and the
following hash functions for a hash table of size 1250 with linear probing. Which of
the following hash functions are good (less collisions) ones? Describe your answer
briefly. For each hash function, talk about the cases where you get collisions.
a) H1= c1 +5∗c2 mod 1250
b) H2= 10∗c1 +100∗c2 +1000∗c3 mod 1250
c) H3= 11∗c1 +101∗c2 +1001∗c3 mod 1250
Answer Q4 here.
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 9 of 13
Question 5 (6 marks)
a) Represent the last occurrence function for the pattern P="structure", which is used
as part of the Boyer-Moore pattern matching algorithm.
(2 marks)
b) Draw a Standard Trie for the following set of strings: {ab, aa, aab, baa, caab}
(2 mark)
c) Using Huffman’s algorithm, construct a Huffman tree that defines an optimal prefix
code for the string “havaianas”. Show the intermediate states of the priority queue.
(2 marks)
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 10 of 13
Answer Q5 here.
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 11 of 13
Question 6 (9 marks)
A graph is simple if it contains no self-loops (no edges from a vertex to itself) or parallel
edges (i.e. for any pair of vertices v and u, there is at most one edge from v to u).
a) Draw an adjacency matrix representation of the following simple directed graph.
(1 marks)
b) An alternative way to represent a simple undirected graph is to store a list of
vertices in the graph together with a hash table that maps pairs of vertices to
edges. The hash table contains an entry with key (v, u) and value e, if and only if
there is an edge e from vertex v to u in the graph. For instance the directed graph
in part (a) would be represented by the list [v1, v2, v3, v4, v5] of vertices together
with a hash table containing entries ((v1, v4), e1), ((v2, v1), e2), ((v4, v5), e3),
((v5, v3), e4) and ((v1, v5), e5).
Assuming that this alternative representation is well implemented, compare it to
the adjacency matrix representation, taking into consideration the following
aspects:
i. For any two vertices v and u, the time complexity for determining if v and u
are adjacent.
ii. For any vertex v, the time-complexity of creating a list of all of the vertices u
such that there is an edge from vertex v to u.
iii. The space complexity of the different representations.
(6 marks)
c) Decide whether these statements are True or False. You must briefly justify all
your answers to receive full credit.
i. Given an undirected graph, it can be tested to determine whether or not it is
a tree in linear time.
ii. The topological sort of an arbitrary directed acyclic graph G = (V, E) can be
computed in linear time.
(2 marks)
v1 v2
v4 v5
v3
e1
e3
e2
e5 e4
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 12 of 13
Answer Q6 here.
Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures
Page 13 of 13
Question 7 (0 marks)
Please specify any assumptions you have made in completing this examination and
which questions those assumptions relate to. You may also include queries you may
have made with respect to a particular question, should you have been able to ‘raise
your hand’ in an examination room.
Answer Q7 here.
END OF EXAMINATION
学霸联盟
