Exam (elaborations)
WGU C949 Data Structures and Algorithms I Questions and Answers
- Course
- Institution
WGU C949 Data Structures and Algorithms I
[Show more]
Content preview
WGU C949 Data Structures andAlgorithms I
An algorithm with a polynomial runtime is considered efficient? - answerTrue: An
efficient algorithm is generally one whose runtime increases no more than polynomially
with respective to the input size. In contrast, an algorithm with an exponential runtime is
not efficient.
An efficient algorithm exists for all computational problems. - answerFalse: Many
computational problems exist for which an efficient algorithm is unknown. Such
problems are often encountered in real applications.
An efficient algorithm to solve an NP-complete may exist. - answerTrue: Whether or not
an efficient algorithm exists for NP-complete problems is an open research question.
However, the current consensus is that such an algorithm is unlikely.
Record - answerA record is the data structure that stores subitems, often called fields,
with a name associated with each subitem.
Array - answerAn array is a data structure that stores an ordered list of items, where
each item is directly accessible by a positional index.
Linked list - answerA linked list is a data structure that stores an ordered list of items in
nodes, where each node stores data and has a pointer to the next node.
Binary tree - answerA binary tree is a data structure in which each node stores data and
has up to two children, known as a left child and a right child.
Hash table - answerA hash table is a data structure that stores unordered items by
mapping (or hashing) each item to a location in an array
Heap - answerA max-heap is a tree that maintains the simple property that a node's key
is greater than or equal to the node's childrens' keys. A min-heap is a tree that
maintains the simple property that a node's key is less than or equal to the node's
childrens' keys.
Graph - answerA graph is a data structure for representing connections among items,
and consists of vertices connected by edges. A vertex represents an item in a graph. An
edge represents a connection between two vertices in a graph
, A linked list stores items in an unspecified order. - answerFalse: A linked list stores an
ordered list of items. The links in each node define the order in which items are stored.
A node in binary tree can have zero, one, or two children. - answerTrue: A binary tree
node can have no children, a single left or right child, or both a left and right child.
A list node's data can store a record with multiple subitems. - answerTrue: The data
stored in a list node can be a record with multiple subitems. Ex: A linked list storing
employee data might use a record containing the employee's name, title, and salary.
Also, the list node itself can be implemented as a record, having subitems for the data
and the pointer to the next node.
Items stored in an array can be accessed using a positional index. - answerArray
elements are stored in sequential locations, so can be easily accessed using an index.
Inserting an item at the end of a 999-item array requires how many items to be shifted?
- answerZero: Appending an item just places the new item at the end of the array. No
shifting of existing items is necessary.
Inserting an item at the end of a 999-item linked list requires how many items to be
shifted? - answerZero: The new item is simply added to the end.
Inserting an item at the beginning of a 999-item array requires how many items to be
shifted? - answer999: Inserting at the beginning requires making room for the new item.
So every current item must be shifted once.
Inserting an item at the beginning of a 999-item linked list requires how many items to
be shifted? - answerZero: No shifting of other items is required, which is an advantage
of using linked lists.
Algorithm for appending to array - answer
Algorithm for appending to linked-list - answer
Abstract data types (ADTs) - answerA data type described by predefined user
operations, such as "insert data at rear," without indicating how each operation is
implemented. An ADT can be implemented using different underlying data structures.
However, a programmer need not have knowledge of the underlying implementation to
use an ADT.
A list ADT's underlying data structure has no impact on the program's execution. -
answerFalse: Different underlying data structures will require different algorithms to
perform same list ADT operation, which will have different runtimes. Ex: For prepending
an item to a list, a linked list-based implementation is more efficient than an array-based
implementation.
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 $14.49. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
75323 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now