Exam (elaborations)
WGU C949 STUDY GUIDE (MOST IMPORTANT QUIZ) QUESTIONS AND ANSWERS 100% CORRECT
- Course
- Institution
WGU C949 STUDY GUIDE (MOST IMPORTANT QUIZ)
[Show more]
Content preview
WGU C949 STUDY GUIDE (MOSTIMPORTANT QUIZ)
Array - answerA data structure that stores an ordered list of items, each item is directly
accessible by a positional index.
Linked List - answerA data structure that stores ordered list of items in nodes, where
each node stores data and has a pointer to the next node.
Binary Search Tree - answerA 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 data structure that stores unordered items by mapping (or
hashing) each item to a location in an array (or vector).
Hashing - answermapping each item to a location in an array (in a hash table).
Chaining - answerhandles hash table collisions by using a list for each bucket, where
each list may store multiple items that map to the same bucket.
Hash key - answervalue used to map an index
bucket - answerEach array element in a hash table
(A 100 elements hash table has 100 buckets)
modulo hash function - answerComputes a bucket index from the items key.
It will map (num_keys / num_buckets) keys to each bucket.
ie... keys range 0 to 49 will have 5 keys per bucket.
= 5
hash table searching - answerHash tables support fast search, insert, and remove.
Requires on average O(1)
Linear search requires O(N)
modulo operator % - answerComputes the integer remainder when dividing two
numbers in a hash table.
Ex: For a 20 element hash table, a hash function of key % 20 will map keys to bucket
indices 0 to 19.
, Max-Heap - answerA binary tree that maintains the simple property that a node's key is
greater than or equal to the node's childrens' keys.
Heap storage - answerHeaps are typically stored using arrays. Given a tree
representation of a heap, the heap's array form is produced by traversing the tree's
levels from left to right and top to bottom. The root node is always the entry at index 0 in
the array, the root's left child is the entry at index 1, the root's right child is the entry at
index 2, and so on.
Max-heap insert - answerAn insert into a max-heap starts by inserting the node in the
tree's last level, and then swapping the node with its parent until no max-heap property
violation occurs.
The upward movement of a node in a max-heap is sometime called percolating.
Complexity O(logN)
Max-heap remove - answerAlways a removal of the root, and is done by replacing the
root with the last level's last node, and swapping that node with its greatest child until no
max-heap property violation occurs.
Complexity O(logN)
Percolating - answerThe upward movement of a node in a max-heap
Min-Heap - answerSimilar to a max-heap, but a node's key is less than or equal to its
children's keys.
Linked list vs Array - answerIf a program requires fast insertion of new data, a linked list
is a better choice than an array.
Abstract Data Type (ADT) - answerA data type described by predefined user
operations, such as "insert data at rear," without indicating how each operation is
implemented.
List - answerAn ADT for holding ordered data.
Data Structure Types: Array, linked list
Tuple - answerArray Type
An immutable(fixed) container with ordered elements.
Stack - answerAn ADT in which items are only inserted on or removed from the top of a
stack.
*Last-in First-Out
Underlying data structures: Linked list
Push(stack, x), pop(stack), peek(stack), IsEmpty(stack), GetLength(stack)
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 $18.99. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
62890 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now