CMSC 341 (Data Structures) Final Exam
Graded A+
Generally, the stack ADT provides "First In First Out" data storage. - ANSWER-False
In a class with memory allocation we do not need to implement an assignment
operator. The one provided by the compiler makes deep copies of objects. -
ANSWER-False
Algorithm A executes an O(log n)-time computation for each entry of an n-element
array. What is the worst-case running time of algorithm A? - ANSWER-The worst
case running time for algorithm A is O(n log n)
In a singly linked list with only a head pointer, inserting a node at its tail is as
efficient as inserting a node at the tail of a doubly linked list with two pointers to
head and tail. Note: efficiency means the number of required node visits. -
ANSWER-False
We are designing an application for the airport control tower which keeps track of
airplanes ready for take off. Airplanes take off in the order they get ready. What
ADT is a proper one to store the list of planes so that the tower can use to issue the
take off permission? - ANSWER-Queue
The circular singly linked list is more efficient than a doubly linked list with regard
to space usage, when implementing the queue ADT. - ANSWER-True
How do we prevent modifications to an object, when we pass the object by
reference to a function? - ANSWER-by passing the object as const
The space required for the stack ADT for n data points, is O(log n). - ANSWER-False
Worst growth rate in running an algorithm - ANSWER-O(n log n)
We want to design an application which its job is to cypher a message. The
algorithm reads the message as a stream of characters, changes some characters
randomly and converts them to another character, at the end it writes the message
in a reversed stream of characters. Then the reversed message will be sent to the
destination. What is the proper ADT to be used in this algorithm? - ANSWER-Stack
In a doubly linked list implementation of the queue ADT, both enqueue and
dequeue operations run in O(1) - ANSWER-True
What is the upper bound for the growth rate of the following function? - ANSWER-
O(n^2)
, What is the upper bound for the growth rate of insertion at the head of an array? -
ANSWER-O(n)
ADT stands for ... - ANSWER-Abstract Data Type
If T(n) is O( f ( n ) ) then there is a constant c > 0 such that T(n) ≤ c f (n) for all
non-negative n. - ANSWER-True
Pre-order traversal can be used to evaluate arithmetic expressions. - ANSWER-
False
What is the upper bound for the growth rate of insertion at an arbitrary location in a
linked list? - ANSWER-O(n)
The function (3n2 + 5n2 log n + n) is O(n^2). - ANSWER-True
If we know the number of data points in advance, using an array is more efficient
than a linked list with regard to space usage. - ANSWER-True
We have used a chaining collision handling scheme with doubly linked lists in a
hash table implementation. What is the worst case running time for search
operations? - ANSWER-O(n)
In a real-time system the search running time is critical. What data structure do
you suggest as a collision handling scheme for a hash table implementation in such
a system? - ANSWER-chaining with a binary search tree
The height of a Heap data structure is ... - ANSWER-O(log n)
What list presents the results of storing (5,28,19,15,20,33,12) in a hash table using
linear probing collision handling. Assume the table has 9 buckets, and the hash
function is h(k) = k % 9. - ANSWER-28,19,20,12,5,15,33
In a hash table using open addressing collision handling, we can store multiple data
items in every bucket - ANSWER-False
The following list is the vector presentation of a heap data structure. No key is
stored in index 0 of the array. Does a preorder traversal of this heap produce the
keys in sorted order? [x, 1, 5, 2, 8, 9, 7, 6] - ANSWER-No
What type of numbers are the best for the table size of a hash table? - ANSWER-
prime numbers
In a priority queue, the items leave the queue in the order that they arrived. -
ANSWER-False
Induction method - ANSWER-step 1: n = 1
Graded A+
Generally, the stack ADT provides "First In First Out" data storage. - ANSWER-False
In a class with memory allocation we do not need to implement an assignment
operator. The one provided by the compiler makes deep copies of objects. -
ANSWER-False
Algorithm A executes an O(log n)-time computation for each entry of an n-element
array. What is the worst-case running time of algorithm A? - ANSWER-The worst
case running time for algorithm A is O(n log n)
In a singly linked list with only a head pointer, inserting a node at its tail is as
efficient as inserting a node at the tail of a doubly linked list with two pointers to
head and tail. Note: efficiency means the number of required node visits. -
ANSWER-False
We are designing an application for the airport control tower which keeps track of
airplanes ready for take off. Airplanes take off in the order they get ready. What
ADT is a proper one to store the list of planes so that the tower can use to issue the
take off permission? - ANSWER-Queue
The circular singly linked list is more efficient than a doubly linked list with regard
to space usage, when implementing the queue ADT. - ANSWER-True
How do we prevent modifications to an object, when we pass the object by
reference to a function? - ANSWER-by passing the object as const
The space required for the stack ADT for n data points, is O(log n). - ANSWER-False
Worst growth rate in running an algorithm - ANSWER-O(n log n)
We want to design an application which its job is to cypher a message. The
algorithm reads the message as a stream of characters, changes some characters
randomly and converts them to another character, at the end it writes the message
in a reversed stream of characters. Then the reversed message will be sent to the
destination. What is the proper ADT to be used in this algorithm? - ANSWER-Stack
In a doubly linked list implementation of the queue ADT, both enqueue and
dequeue operations run in O(1) - ANSWER-True
What is the upper bound for the growth rate of the following function? - ANSWER-
O(n^2)
, What is the upper bound for the growth rate of insertion at the head of an array? -
ANSWER-O(n)
ADT stands for ... - ANSWER-Abstract Data Type
If T(n) is O( f ( n ) ) then there is a constant c > 0 such that T(n) ≤ c f (n) for all
non-negative n. - ANSWER-True
Pre-order traversal can be used to evaluate arithmetic expressions. - ANSWER-
False
What is the upper bound for the growth rate of insertion at an arbitrary location in a
linked list? - ANSWER-O(n)
The function (3n2 + 5n2 log n + n) is O(n^2). - ANSWER-True
If we know the number of data points in advance, using an array is more efficient
than a linked list with regard to space usage. - ANSWER-True
We have used a chaining collision handling scheme with doubly linked lists in a
hash table implementation. What is the worst case running time for search
operations? - ANSWER-O(n)
In a real-time system the search running time is critical. What data structure do
you suggest as a collision handling scheme for a hash table implementation in such
a system? - ANSWER-chaining with a binary search tree
The height of a Heap data structure is ... - ANSWER-O(log n)
What list presents the results of storing (5,28,19,15,20,33,12) in a hash table using
linear probing collision handling. Assume the table has 9 buckets, and the hash
function is h(k) = k % 9. - ANSWER-28,19,20,12,5,15,33
In a hash table using open addressing collision handling, we can store multiple data
items in every bucket - ANSWER-False
The following list is the vector presentation of a heap data structure. No key is
stored in index 0 of the array. Does a preorder traversal of this heap produce the
keys in sorted order? [x, 1, 5, 2, 8, 9, 7, 6] - ANSWER-No
What type of numbers are the best for the table size of a hash table? - ANSWER-
prime numbers
In a priority queue, the items leave the queue in the order that they arrived. -
ANSWER-False
Induction method - ANSWER-step 1: n = 1
