DSA MIDTERM EXAM QUESTIONS
WITH CORRECT ANSWERS
To define an ADT for your data structure, you should include implementation details on
how the data structure is implemented. - Correct Answers -False.
An ADT is just a specification (or contract) of what operations your data structure should
support. Implementation details will be then included in the class defining the data
structure.
To implement a data structure, the data structure's class should be aware of the type of
items stored. - Correct Answers -False
The Linked implementation of the List ADT is more space efficient than the Array
implementation because of dynamic allocation. - Correct Answers -False
The Array implementation of the List ADT is more space efficient than the Linked
implementation when:
-The Linked List is at least half full
-The Array is at least half full
-The Array implementation is always better
-None of the above - Correct Answers -The Array is at least half full
The Linked list with sentinel nodes is a better implementation than the normal one,
because:
-It has a better time efficiency for insertion and deletion
-It reduces code complexity for insertion and deletion by removing special case checks
-Both are true - Correct Answers -It reduces code complexity for insertion and deletion
by removing special case checks
The space requirement for a SkipList is always 3np, where n is the number of inputs
and p is the size of the pointer - Correct Answers -False
The worst-case running-time analysis of the search operation in SkipList occurs when:
-All nodes are at the same level
-The item we are searching for is located at the end of the list
-Both are true - Correct Answers -All nodes are at the same level
, The SkipList will be have a worse running-time for the search operation than both the
Array and Linked implementations of the list ADT when all SkipList nodes are at the
same level - Correct Answers -False
Having all the SkipList nodes at the same level defines the worst-case of the SkipList's
search operation. However, the efficiency of SkipList in the worst-case is the same as it
in Array and Linked implementations of the List ADT. SkipList will be at least as
efficient.
You can get 100% code coverage without writing meaningful tests to your code -
Correct Answers -True
To have 100% mutation coverage, all mutants in your code should be killed (detected)
by failing of at least one of your test cases - Correct Answers -True
What is the running-time growth rate of the linear (sequential) search algorithm used to
search for a target item with Key K in an unsorted list?
-Linear (n)
-Logarithmic (log n)
-Constant (1)
-None of the above, question is missing some information - Correct Answers -None of
the above, question is missing some information
What is the running-time growth rate of the Find_max algorithm when used to find the
item with the maximum Key in an unsorted list?
-Linear (n)
-Logarithmic (log n)
-Constant (1)
-None, missing info - Correct Answers -Linear (n)
The best case of the linear search algorithm is when we have only one item in the
collection - Correct Answers -False
The upper bound for an algorithm's growth rate is its cost in the worst case. - Correct
Answers -False
A lower bound to the running-time of an algorithm can be defined as any function that is
always equal to or less than the running-time of that algorithm - Correct Answers -True
Theta is the notation used to describe the amount of time required by the algorithm in
the average case. - Correct Answers -False
We use the Big-O, and Big-Omega notations to model the running time of an algorithm
in its worst, and best cases, respectively - Correct Answers -False
WITH CORRECT ANSWERS
To define an ADT for your data structure, you should include implementation details on
how the data structure is implemented. - Correct Answers -False.
An ADT is just a specification (or contract) of what operations your data structure should
support. Implementation details will be then included in the class defining the data
structure.
To implement a data structure, the data structure's class should be aware of the type of
items stored. - Correct Answers -False
The Linked implementation of the List ADT is more space efficient than the Array
implementation because of dynamic allocation. - Correct Answers -False
The Array implementation of the List ADT is more space efficient than the Linked
implementation when:
-The Linked List is at least half full
-The Array is at least half full
-The Array implementation is always better
-None of the above - Correct Answers -The Array is at least half full
The Linked list with sentinel nodes is a better implementation than the normal one,
because:
-It has a better time efficiency for insertion and deletion
-It reduces code complexity for insertion and deletion by removing special case checks
-Both are true - Correct Answers -It reduces code complexity for insertion and deletion
by removing special case checks
The space requirement for a SkipList is always 3np, where n is the number of inputs
and p is the size of the pointer - Correct Answers -False
The worst-case running-time analysis of the search operation in SkipList occurs when:
-All nodes are at the same level
-The item we are searching for is located at the end of the list
-Both are true - Correct Answers -All nodes are at the same level
, The SkipList will be have a worse running-time for the search operation than both the
Array and Linked implementations of the list ADT when all SkipList nodes are at the
same level - Correct Answers -False
Having all the SkipList nodes at the same level defines the worst-case of the SkipList's
search operation. However, the efficiency of SkipList in the worst-case is the same as it
in Array and Linked implementations of the List ADT. SkipList will be at least as
efficient.
You can get 100% code coverage without writing meaningful tests to your code -
Correct Answers -True
To have 100% mutation coverage, all mutants in your code should be killed (detected)
by failing of at least one of your test cases - Correct Answers -True
What is the running-time growth rate of the linear (sequential) search algorithm used to
search for a target item with Key K in an unsorted list?
-Linear (n)
-Logarithmic (log n)
-Constant (1)
-None of the above, question is missing some information - Correct Answers -None of
the above, question is missing some information
What is the running-time growth rate of the Find_max algorithm when used to find the
item with the maximum Key in an unsorted list?
-Linear (n)
-Logarithmic (log n)
-Constant (1)
-None, missing info - Correct Answers -Linear (n)
The best case of the linear search algorithm is when we have only one item in the
collection - Correct Answers -False
The upper bound for an algorithm's growth rate is its cost in the worst case. - Correct
Answers -False
A lower bound to the running-time of an algorithm can be defined as any function that is
always equal to or less than the running-time of that algorithm - Correct Answers -True
Theta is the notation used to describe the amount of time required by the algorithm in
the average case. - Correct Answers -False
We use the Big-O, and Big-Omega notations to model the running time of an algorithm
in its worst, and best cases, respectively - Correct Answers -False
