Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
CCS0015 Flashcards
Data Structures and Algorithms
| Question | Answer |
|---|---|
| representation of the logical relationship existing between individual elements of data | data structure |
| - set of instructions written to carry out certain tasks - step by step procedure to solve a particular function. | algorithm |
| formed from algorithms and associated data structures | program |
| classification of data structures | primitive and non-primitive data structure |
| basic structures, directly operated upon by machine instructions | primitive data structures |
| examples of primitive data structures | integer, float, character, string, pointer |
| more sophisticated data structures; derived from primitive data structures | non-primitive data structures |
| classifications of non-primitive data structures | linear list and non-linear list |
| in this type of list, values are arranged in a linear fashion | linear list |
| examples of linear list | array, linked list, stack, queue, priority queue |
| adds anywhere, remove the highest priority | priority queue |
| data values in this type of list are not arranged in order | non-linear list |
| examples of non-linear list | hash tables, tree, graph |
| unordered lists which use a 'hash function' to insert and search | hash tables |
| data is organized in branches | tree |
| more general branching structure, with less strict connection conditions than of a tree | graph |
| types of data structures | homogenous and non-homogenous |
| values of the same data type are stored | homogenous (e.g. array) |
| data values of different types are grouped and stored | non-homogenous (e.g. structures, classes) |
| separating design details from usage | abstraction |
| - separates logical properties from impelentation details - stores data and allows various operations on the data | abstract data type (ADT) |
| providing only essential information outside the world | abstraction |
| binding the data and the function that use them | encapsulation |
| what do abstract data types support? | abstraction, encapsulation, information hiding |
| the memory address of a variable | pointer |
| variable whose content is a memory address | pointer variable |
| there is __ ____ associated with the pointer data type in C++ | no name |
| syntax of a pointer | dataType *identifier1 *identifier2; |
| a unary operator that returns the address of the operand; produces the address of a variable | address-of operator (&) |
| operator that refers to the object to with its operand points; produces the variable to which it points | dereferencing operator (*) |
| creates a new dynamic variable of a specified type and returns a pointer that points to this new variable | new operator |
| special area of memory reserved for dynamically allocated variables | heap (freestore) |
| if there is insufficient memory to create the new variable, the new returns a special value called... | NULL |
| eliminates a dynamic variable and returns the memory occupied by the dynamic variable to the freestore manager so that the memory can be reused | delete operator |
| pointer variable that points to a destroyed dynamic variable, and whose value becomes undefined | dangling pointers |
| - you can assign a name definition and then use the type name to declare variables using this keyword - is not declared in the main program | typedef |
| array whose size is not specified when you write the program but is determined while the program is running | dynamic array |
| - series of connected nodes, where each node is a data structure - can grow or shrink in size as the program runs | linked list |
| each node in a linked list consists of the following: | - data members - pointer that points to another node |
| displays the member of each node / elements of a linked list | traversal |
| template version of a doubly linked list | standard template library |
| returns a reference to the last element in the list | back |
| returns true if the list is empty; false if the list has elements | empty |
| returns a bi-directional iterator to the end of the list | end |
| returns a reference to the first element of the list | front |
| inserts an element into the list | insert |
| inserts all the items in one list into another | merge |
| removes the last element of the list | pop_back |
| removes the first element of the list | push_front |
| returns the number of elements in the list | size() |
| removes any element that has the same value as the element before it | unique |
| data structure that sotres and retrieves items in a last-in-first-out (LIFO) manner | stack |
| a stack stores and reteives items in this manner | last-in-first-out (LIFO) |
| applications of stack | computer systems and calculators |
| different stack operations | push and pop |
| storing a value onto the stack | push |
| retrieves and removes a value from the stack | pop |
| boolean operation needed for static stacks; returns true if the stack is full | isFull |
| boolean operation needed for all stacks; returns true if the stack is empty | isEmpty |
| stack with a fixed size; implemented with an array | static stack |
| can grow in size as needed; implemented with a linked list | dynamic stack |
| integer that is used to mark the top of the stack; points to most recently added node | top |
| variable top is initialized to | -1 |
| stack that is built on a linked list instead of an array | dynamic stack |
| advantages of a dynamic stack | - no need to specify starting size of the stack - starts as an empty linked list, and then expands by adding one node - will never be full, as long as the system has enough free memory |
| the STL stack contained may be implemented as a | vector, list, deque |
| another term forstack container, which is used to adapt other containers | container adapter |
| declaring a vector stack | stack<int, vector<int> > iStack; |
| declaring a list stack | stack<int, list<int> > iStack; |
| declaring a deque (default) stack | stack<int > iStack; |
| pushes an element with the value x onto the stack | push |
| removes the element at the top of the stack | pop |
| returns a reference to the element at the top of the stack | top |
| returns the number of elements currently in the stack | size |
| What happens to the value of the TOP during a PUSH operation in a STATIC STACK? | increments by 1 |
| data structure that provides access to its element in first-in, first-out (FIFO) order | queue |
| queue provides access to its elements in this order | first-in, first-out (FIFO) |
| applications of queue | print jobs, communications software |
| primary queue operations | enqueuing, dequeuing |
| inserting an element at the rear of a queue | enqueue |
| remove an element from the front of a queue | dequeue |
| similar to dynamic stack, a dynamic queue starts as an | empty linked list |
| what happens as each new item is added to the queue? | - new node is added to rear of the list - rear pointer is updated to point to the new node |
| what happens as each item is dequeued? | - node pointed to by front pointer is deleted - front is made to point to the next node in the list |
| two pointers used in queue ADT | front and rear |
| double-ended queue; although similar to vector, it allows efficient access to values at the front and rear | deque (pronounced "deck") |
| inserts a value into the rear of the queue/deque | push_back |
| removes the first (front) element of the deque | pop_front |
| returns a reference to the first element of the deque | front |
| the queue container adapter can be built upon... | vectors, lists, or deques (default) |
| returns the value of the element at the front of the queue | top |
| - function call in which the function being called is the same as the one making the call - when a function calls itself | recursive call |
| - programming technique in which procedures and functions call themselves - a powerful technique that can be used in the place of iteration (looping) | recursion |
| a function that calls itself | recursive function |
| like a loop, a recursive function must have some algorithm to... | to control the number of times it repeats |
| this holds the number of times the function is to call itself | integer argument |
| this statement heps the function control the repetition | if/else statement |
| the number of cycles of the function repeating itself until 0 is passed to the function | depth of recursion |
| the role of recursive functions in programming is to... | break complex problems down to a solvable problem |
| the solvable problem is known as the... | base case |
| a recursive function is designed to terminate when... | the function reaches its base case |
| a recursive function that directly calls itself | direct recursion |
| occurs when a function A calls function B, which in turn calls function A | indirect recursion |
| a definition in which something is defined in terns of smaller versions of itself | recursive definition |
| the case for which the solution can be stated non-recursively, and which the answer is explicitly known | base case (if statement) |
| the case for which the solution is expressed in a smaller version of itself; also known as recursive case | general / inductive step case (else statement) |
| a recursive function should be designed to stop making recursive calls when it reaches its | base case |
| a tree imposes a ___ structure | hierarchial |
| practical applications of tree | organization charts, family hierarchy, representation of algebraic expression |
| collection of nodes that can be empty | tree |
| the mother node of a tree structure; the first node in an hierarchial arrangement; does not have a parent | root |
| stores data; its role is the same as of linked lists; connected by the means of links with other nodes | node |
| the immediate predecessor of a node | parent |
| successor nodes of a parent (predecessor node) | child |
| connects the two nodes; the line drawn from one node to another | edge |
| pointer to a node in a tree structure | link |
| located at the end of the tree; does not have any child(ren) | leaf |
| rank of tree hierarchy | level |
| the level of the root node is always | level zero |
| the highest number of nodes that is possible in a way starting from the first node to a leaf node | height |
| formula for finding the height of a tree | h = i_max + 1 h - height; i - max level of tree |
| child node of the same parent | sibling |
| maximum number of children that exists for a node | degree of a node |
| node with degree zero | terminal node |
| number of successive edges from source node to destination node | path length |
| maximum level of any leaf of a tree | depth |
| group of disjoint trees; happens when the root node is removed | forest |
| non-linear linked list where each node may point to two other nodes | binary tree |
| pointer that is anchored at the top; similar to the head pointer in a linked list | tree pointer |
| all pointers that do not point to a node (i.e. leaf nodes) are set to... | NULL |
| entire branch of the tree, from one particular node down | subtree |
| uses of binary tree | database applications to organize key values that index database records |
| tree used to facilitate searches | binary search tree |
| all the nodes to the left of a node hold values ___ than the node's value | less |
| all the nodes to the right of a node hold ___ than the node's data | greater |
| three common methods for traversing a binary tree | in-order, pre-order, post-order |
| each of the binary tree traversing methods is best implemented as a... | recursive function |
| left subtree traversed -> data processed -> right subtree traversed | in-order traversal |
| data processed -> left subtree traversed -> right subtree traversed | pre-order traversal |
| left subtree traversed -> right subtree traversed -> data is processed | post-order traversal |
| application of graphs | electronic circuits, transportation networks, computer networks, databases |
| consists of a number of data items called vertexes that can be connected to other vertexes by lines called edges | graph |
| a graph is composed of | vertices and edges |
| edges in a graph have direction | directed graph (digraph) |
| edges in a graph have no direction | undirected graph |
| every edge is assigned to some value which is greater than or equal to zero | weighted graph |
| path in which all vertices are distinct, except possibly the first and last | simple path |
| simple path in which the first and last vertices are the same | cycle |
| when there is an edge from one node to another | adjacent nodes |
| total number of edges included in the path from the source to the destination node | length of a path |
| path such that all its vertices and edges are distinct | simple path |
| graph without a cycle; a good example is a tree | acyclic graph |
| undirected graph that has a path that connects a pair of vertices | connected graph |
| a directed graph is connected if | there is a path between them |
| graph in which all pairs of vertices are adjacent, or in which every vertex is directly connected to every other vertex | complete graph |
| for a complete graph with n vertices, the number of edges is | n(n-1) / 2 |
| total number of edges linked to a node in an undirected graph | degree of a node |
| two degrees for every node in a directed graph | indegree and outdegree |
| total number of edges coming to a node (directed graph) | indegree |
| total number of edges going out forom a node (directed graph) | outdegree |
| a graph can be represented in several ways | adjacency matrices and lists |
| the adjacency matrix of an undirected graph is... | symmetric |
| each node in an adjacency list has two components... | vertex and link |
| operations on graph | create, clear, determine if empty, traverse, print |
| traversing a graph is similar to traversing a binary tree, except that... | - a graph might not have cycles - might not be able to traverse the entire graph from a single vertex |
| most common graph traversal algorithms | depth and breadth first traversal |
| the graph is traversed as much as possible; uses a queue | breadth-first travel |
| the shape of a binary search tree is... | determiend by the order in which values are inserted |
| sequence of vertices, such that consecutive vertices are adjacent | path |
| - process that organizes a collection of data into either ascending or descending order - used to arrange names and numbers in meaningful ways | sorting |
| in sorting, a list is divided into two sub-lists: | sorted and unsorted |
| smallest element is "bubbled" or taken from the unsorted list and moved to the sorted sub-list | bubble sort |
| as the smallest elemetn is moved to the sub-list, it swaps places with the first element on the unsorted sub-list | selection sort |
| first element of the unsorted part is picked up, transferred to the sorted sub-list, and inserted at the appropriate place; appropriate for small inputs | insertion sort |
| sequence of interleaved insertion sorts based on an increment sequence; increment size is reduced after each pass until the increment size is 1 | shell sort |
| two important divide-and-conquer sorting algorithms | merge sort and recursive sort |
| divides the list into halves, sorts each halve separately, and merge the sorted halves into one sorted array | merge sort |
| all the hard work is done before the recursive calls; partitions an array into two parts, sorts the parts independently, and combines the sorted sequences by a simple concatenation | quicksort |
| steps in quicksort algorithm | 1. divide: partition the list by choosing a random element 2. recursion: recursively sort the sublists separately 3. conquer: put the sorted sublists together |
| element chosen in a quicksort, in which half the elements will come before, and the other half after | pivot |
| data structure that stores a collection of objects (with keys) | heap |
| properties of the heap | complete binary tree, heap order |
| the key stored in every node is greater or equal than the key stored in the parent node | heap order property |
| - picks the largest child key and compares it to the parent key - if parent key is larger, then it quits; otherwise, its waps the parent key with the largest child key | heapify |
| - goes through the remaining nodes of the three remaining nodes of the tree and runs 'heapify' on each one - the bottom-up order of processing node guarantees that the subtree rooted at children and heap before 'heapify' is run at their parent | build heap |
| starts by using a procedure to build a heap on the input array | heap sort |
| phases of using heap sort | build a heap from arbitrary array; use the heap to sort the data |
| using this, you can determine whether a particular item is in a list | searching algorithm |
| special member that uniquely identifies the item in the data set | key of the item |
| comparing the key of the search item with the key of an item in the list | key comparison |
| step through array of records one at a time. look for a record with matching key. | sequential search |
| can be applied to sorted lists; uses divide and conquer technique (compares search item to middle element first) | binary search |
| In Binary Search, if search item is less than middle element | restrict the search to the left half of the list |
| a binary search tree doesn't accept the following: | duplicate values |
Created by:
samy__