Exam (elaborations)
CS DSA QUESTIONS AND ANSWERS
- Course
- Institution
Exam of 5 pages for the course DSA at DSA (CS DSA)
[Show more]
Content preview
CS DSAIn order to do an exact-match search, the key values must define a total order -
answerfalse
One good general-purpose solution to the problem of getting a key from a record is to
define a special method such as ".key()" - answerfalse
{Most programming languages will let us re-define "<" and ">" to handle comparison of
arbitrary objects| We can generally rely on "<" and ">" to let us compare arbitrary record
types} - answerfalse
Defining a record's key field is a property of - answerthe context of the search
In order to be able to sort, the key values must define a total order - answertrue
One good general-purpose solution to the problem of getting a key from a record is to
store Key/Value pairs in the search structure - answertrue
The problem with using a ".key()" method to get the key from a record is that we can't
use this same method to get different fields for different searches - answertrue
n the linked implementation of a queue, a new item would be added to the - answerrear
Which data structure allows insertion only at the back, and removing only from the
front? - answerQueue
Which boolean expression indicates whether the values for the nodes pointed to by p
and q are the same? Assume that neither p nor q is null. - answerp.element() ==
q.element()
Stack A has entries a, b, c (in that order with a on top), while Stack B is initially empty.
When an entry is popped out of stack A, it can be printed immediately or pushed to
stack B. When an entry is popped out of stack B, it can only be printed. Which of the
following permutations of a, b, c is not possible to print? - answerc a b
Which data structure is used for recursion - answerstack
The term "FIFO" is associated with which data structure? - answerqueue
The terms "insert" and "delete" are traditionally associated with which data structure(s)?
- answerList
, Which of the following is not a linear data structure? - answerTree
When is Bubble Sort a good choice for sorting an array? - answerThere is no situation
where Bubble Sort is the best choice over all of the others in this chapter
Bubble Sort (as the code is written in this module) is a stable sorting algorithm. Recall
that a stable sorting algorithm maintains the relative order of records with equal keys. -
answertrue
What is the worst-case time for Bubble Sort (as the algorithm is presented in this
module) to sort an array of nn records? - answerO(n^2)
What is the running time of Bubble Sort when the input is an array where all record
values are equal? - answerO(n^2)
What is the running time of Bubble Sort (as the algorithm is presented in this module)
when the input is an array that has already been sorted? - answerO(n^2)
What is the running time for Bubble Sort when the input array has values that are in
reverse sort order? - answerO(n^2)
In which cases are the time complexities the same for Bubble Sort (as the algorithm is
presented in this module)? - answerWorst, Average and Best
The order of the input records has what impact on the number of comparisons required
by Bubble Sort (as presented in this module)? - answerNone
In the worst case, the total number of swaps done by Selection Sort is closest to: -
answern
The order of the input records has what impact on the number of comparisons required
by Selection Sort (as presented in this module)? - answerNone
What is the average-case time for Selection Sort to sort an array of n records? -
answerO(n^2)
Selection sort is simple, but less efficient than the best sorting algorithms. - answerTrue
Which statement best characterizes Selection Sort (as the code is written in this
module)? Recall that a stable sorting algorithm maintains the relative order of records
with equal keys. - answerSelection Sort is not stable, but with minor modifications it
could be made so
In which cases are the time complexities the same for Selection Sort? - answerWorst,
Average and Best
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Dreamer252. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $13.49. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
84866 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now