WGU C949 v5 - Data Structures and Algorithms I C949 WGU C949 - Data Structures and Algorithms Pre-Assessment QUESTIONS WITH CORRECT ANSWERS

data structure

A data structure is a way of organizing, storing, and performing operations on data.

record

A record is the data structure that stores subitems, often called fields, with a name associated with each subitem.

array

An array is a data structure that stores an ordered collection of elements, where each element is directly accessible by a positional index.

linked list

A linked list is a data structure that stores an ordered list of items in nodes, where each node stores data and has a reference to the next node.

binary tree

A 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

A hash table is a data structure that stores unordered items by mapping (or hashing) each item to a location in an array.

max-heap

A 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.

min-heap

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

A graph is a data structure for representing connections among items, and consists of vertices connected by edges.

vertex

A vertex represents an item in a graph.

edge

An edge represents a connection between two vertices in a graph.

algorithm

An algorithm describes a sequence of steps to solve a computational problem or perform a calculation.

computational problem

A computational problem specifies an input, a question about the input that can be answered using a computer, and the desired output.

NP-complete

NP-complete problems are a set of problems for which no known efficient algorithm exists.

abstract data type / ADT

An abstract data type (ADT) is a data type described by predefined user operations, such as "insert data at rear," without indicating how each operation is implemented.

list

A list is an ADT for holding ordered data.

dynamic array

A dynamic array is an ADT for holding ordered data and allowing indexed access.

stack

A stack is an ADT in which items are only inserted on or removed from the top of a stack.

queue

A queue is an ADT in which items are inserted at the end of the queue and removed from the front of the queue.

deque

A deque (pronounced "deck" and short for double-ended queue) is an ADT in which items can be inserted and removed at both the front and back.

bag

A bag is an ADT for storing items in which the order does not matter and duplicate items are allowed.

set

A set is an ADT for a collection of distinct items.

priority queue

A priority queue is a queue where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority.

dictionary

A dictionary is an ADT that associates (or maps) keys with values.

abstraction

Abstraction means to have a user interact with an item at a high-level, with lower-level internal details hidden from the user.

compression

Given data represented as some quantity of bits, compression transforms the data to use fewer bits.

Huffman coding

Huffman coding is a common compression technique that assigns fewer bits to frequent items, using a binary tree.

heuristic

Heuristic: A technique that willingly accepts a non-optimal or less accurate solution in order to improve execution speed.

heuristic algorithm

A heuristic algorithm is an algorithm that quickly determines a near optimal or approximate solution.

0-1 knapsack problem

0-1 knapsack problem: The knapsack problem with the quantity of each item limited to 1.

self-adjusting heuristic

A self-adjusting heuristic is an algorithm that modifies a data structure based on how that data structure is used.

greedy algorithm

A greedy algorithm is an algorithm that, when presented with a list of options, chooses the option that is optimal at that point in time.

fractional knapsack problem

The fractional knapsack problem is the knapsack problem with the potential to take each item a fractional number of times, provided the fraction is in the range [0.0, 1.0].

activity selection problem

The activity selection problem is a problem where one or more activities are available, each with a start and finish time, and the goal is to build the largest possible set of activities without time conflicts.

dynamic programming

Dynamic programming is a problem solving technique that splits a problem into smaller subproblems, computes and stores solutions to subproblems in memory, and then uses the stored solutions to solve the larger problem.

longest common substring

The longest common substring algorithm takes 2 strings as input and determines the longest substring that exists in both strings.

list

A list is a common ADT for holding ordered data, having operations like append a data item, remove a data item, check if a data item exists, and print the list.

singly-linked list

A singly-linked list is a data structure for implementing a list ADT, where each node has data and a reference to the next node.

head / tail

A singly-linked list's first node is called the head, and the last node the tail.

positional list

A singly-linked list is a type of positional list: A list where elements contain references to the next and/or previous elements in the list.

append

The singly-linked list append operation inserts a new node after the list's tail node.

prepend

Given a new node, the prepend operation for a singly-linked list inserts the new node before the list's head node.

search

Given a data value, a linked list search operation returns the first node whose data equals that data value, or None if no such node exists.

insert-node-after

Given a new node, the insert-node-after operation for a singly-linked list inserts the new node after a provided existing list node.

remove-node-after

Given a specified existing node in a singly-linked list, the remove-node-after operation removes the node after the specified list node.

doubly-linked list

A doubly-linked list is a data structure for implementing a list ADT, where each node has data, a reference to the next node, and a reference to the previous node.

positional list

A doubly-linked list is a type of positional list: A list where elements contain references to the next and/or previous elements in the list.

append

Given a new node, the append operation for a doubly-linked list inserts the new node after the list's tail node.

prepend

Given a new node, the prepend operation of a doubly-linked list inserts the new node before the list's head node and assigns the head attribute with the new node.

search

Given a data value, a linked list search operation returns the first node whose data equals that data value, or None if no such node exists.

insert-node-after

Given a new node, the insert-node-after operation for a doubly-linked list inserts the new node after a provided existing list node.

remove-node

The remove-node operation for a doubly-linked list removes a provided existing list node.

circular linked list

A circular linked list is a linked list where the tail node's next attribute references the head of the list, instead of None.

list traversal

A list traversal algorithm visits all nodes in the list once and performs an operation on each node.

reverse traversal

A reverse traversal visits all nodes starting with the list's tail node and ending after visiting the list's head node.

dummy node / header node

A linked list implementation may use a dummy node (or header node): A node with an unused data member that always resides at the list head and cannot be removed.

array-based list

An array-based list is a list ADT implemented using an array.

append

Given a new element, the append operation for an array-based list of length X inserts the new element at the end of the list, or at index X.

prepend

The prepend operation for an array-based list inserts a new item at the start of the list.

insert-at

The insert-at operation for an array-based list inserts an item at a specified index.

search

Given an item, the search operation returns the index of the first equal list item, or -1 if not found.

remove-at

Given the index of an item in an array-based list, the remove-at operation removes the item at that index.

stack

A stack is an ADT representing a collection of items in which items are only inserted on or removed from the top.

push

The stack push operation inserts an item on the top of the stack.

pop

The stack pop operation removes and returns the item at the top of the stack.

last-in first-out / LIFO

A stack is referred to as a last-in first-out (LIFO) ADT.

unbounded stack

An unbounded stack is a stack with no upper limit on length.

bounded stack

A bounded stack is a stack with a length that does not exceed a maximum value.

full

A bounded stack with a length equal to the maximum length is said to be full.

queue

A queue is an ADT representing a collection of items in which items are inserted at the end and removed from the front.

enqueue

The queue enqueue operation inserts an item at the end of the queue.

dequeue

The queue dequeue operation removes and returns the item at the front of the queue.

first-in first-out / FIFO

A queue is referred to as a first-in first-out (FIFO) ADT.

bounded queue

A bounded queue is a queue with a length that does not exceed a specified maximum value.

full

A bounded queue with a length equal to the maximum length is said to be full.

unbounded queue

An unbounded queue is a queue with a length that can grow indefinitely.

deque

A deque (pronounced "deck" and short for double-ended queue) is an ADT in which items can be inserted and removed at both the front and back.

peek

A peek operation returns an item in the deque without removing the item.

Queue

A Queue class is defined in the queue module and can be imported with the from queue import Queue statement.

map / dictionary

A map (or dictionary) is an ADT that associates (or maps) keys with values.

insert

The map insert operation takes two parameters, a key and a value. If the key does not exist in the map, the key-value pair is inserted. If the key does exist, the value is updated.

get

The map get operation takes one parameter for the key and returns the associated value, or None if the key does not exist in the map.

hash code

The first problem is addressed with a hash code: a non-negative integer that attempts to uniquely identify a key.

hash function

A hash function is a function that computes a hash code for a given value.

hash table

A hash table is a data structure that stores unordered items by mapping (or hashing) each item to a location in an array.

bucket

Each hash table array element is called a bucket.

hash map

A hash map is an implementation of a map ADT using a hash table.

collision

A hash table collision occurs when two different keys map to the same bucket index.

Chaining

Chaining is a collision resolution technique where each bucket has a list of items (so bucket 6's list could have keys 86 and 16).

Open addressing

Open addressing is a collision resolution technique where collisions are resolved by looking for an empty bucket elsewhere in the table (so key 16 might be stored in bucket 7).

Chaining

Chaining handles hash table collisions by using a list for each bucket, where each list stores the items that map to that bucket.

linear probing

A hash table with linear probing handles a collision by starting at the key's mapped bucket, and then linearly searches subsequent buckets until an empty bucket is found.

empty-since-start

An empty-since-start bucket has been empty since the hash table was created.

empty-after-removal

An empty-after-removal bucket had an item removed that caused the bucket to now be empty.

quadratic probing

A hash table with quadratic probing handles a collision by starting at the key's mapped bucket, and then quadratically searches subsequent buckets until an empty bucket is found.

probing sequence

Iterating through sequential i values to obtain the desired index is called the probing sequence.

Double hashing

Double hashing is an open-addressing collision resolution technique that uses two different hash functions to compute bucket indices.

probing sequence

Iterating through sequential i values to obtain the desired table index is called the probing sequence.

resize

A hash table resize operation increases the number of buckets while preserving all existing items.

load factor

A hash table's load factor is the number of items in the hash table divided by the number of buckets.