PA Weak Areas Flashcards
(32 cards)
Linear search
Linear search is a search algorithm that starts from the beginning of a list, and checks each element until the search key is found or the end of the list is reached.
Binary search
Binary search is a faster algorithm for searching a list if the list’s elements are sorted and directly accessible. Binary search first checks the middle element of the list. If the search key is found, the algorithm returns the matching location. If the search key is not found, the algorithm repeats the search on the remaining left sublist (if the search key was less than the middle element) or the remaining right sublist (if the search key was greater than the middle element).
Merge sort
Merge sort is a sorting algorithm that divides a list into two halves, recursively sorts each half, and then merges the sorted halves to produce a sorted list. The recursive partitioning continues until a list of one element is reached, as a list of one element is already sorted.
recursive function
A function may call other functions, including calling itself. A function that calls itself is known as a recursive function.
What is a list?
A list is an ADT for holding ordered data.
Examples include array and linked list.
Define a dynamic array.
A dynamic array is an ADT for holding ordered data and allowing indexed access.
Example includes array.
What is a stack?
A stack is an ADT in which items are only inserted on or removed from the top of a stack.
Example implementation includes linked list.
Define a 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.
Example implementation includes linked list.
What is a deque?
A deque is an ADT in which items can be inserted and removed at both the front and back.
Pronounced ‘deck’. Example implementation includes linked list.
Define a bag.
A bag is an ADT for storing items in which the order does not matter and duplicate items are allowed.
Example implementations include array and linked list.
What is a set?
A set is an ADT for a collection of distinct items.
Example implementations include binary search tree and hash table.
Define a 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.
Example implementation includes heap.
What is a dictionary (map)?
A dictionary is an ADT that associates (or maps) keys with values.
Example implementations include hash table and binary search tree.
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. 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.
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.
A queue is referred to as a first-in first-out ADT. A queue can be implemented using a linked list or an array.
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. Ex: After the operations “Enqueue 7”, “Enqueue 14”, and “Enqueue 9”, “Dequeue” returns 7. A second “Dequeue” returns 14.
Record
A record is the data structure that stores subitems, often called fields, with a name associated with each subitem.
A list node’s data can store a record with multiple subitems.
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 pointer to the next node.
If a program requires fast insertion of new data, a linked list may be a better choice than an array.
doubly-linked list
A doubly-linked list is a data structure for implementing a list ADT, where each node has data, a pointer to the next node, and a pointer to the previous node. The list structure typically points to the first node and the last node. The doubly-linked list’s first node is called the head, and the last node the tail.
A doubly-linked list is similar to a singly-linked list, but instead of using a single pointer to the next node in the list, each node has a pointer to the next and previous nodes. Such a list is called “doubly-linked” because each node has two pointers, or “links”.
What is a Leaf in the context of a tree?
A tree node with no children
Leaves are the endpoints of a tree structure.
What defines an Internal node?
A node with at least one child
Internal nodes are essential for maintaining the structure of the tree.
Who is considered a Parent in a tree structure?
A node with a child is said to be that child’s parent
The parent-child relationship is crucial for navigating the tree.
What does a node’s ancestors include?
The node’s parent, the parent’s parent, etc., up to the tree’s root
Ancestors trace the lineage from a node back to the root.
