Save
Upgrade to remove ads
Busy. Please wait.
Log in with Clever
or
show password
Forgot Password?
Don't have an account?  Sign up 
Sign up using Clever
or
Username is available taken
show password


Make sure to remember your password. If you forget it there is no way for StudyStack to send you a reset link. You would need to create a new account. Your email address is only used to allow you to reset your password. See our Privacy Policy and Terms of Service.

Already a StudyStack user? Log In

Reset Password
Enter the associated with your account, and we'll email you a link to reset your password.
focusNode
Didn't know it?
click below
 
Knew it?
click below
Don't Know
Remaining cards (0)
Know
0:00
edit
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

DSA TERMS REVIEWER

mag review kayo mga hangal

TermDefinition
representation of the logical relationship existing between individual elements of data Data structure:
Algorithm + Data Structure Program
A step by step procedure to solve a particular function Algorithm:
DATA STRUCTURES ARE DIVIDED INTO TWO BROAD CATEGORIES: Primitive Data Structure Non-Primitive Data Structure
Basic structures and directly operated upon by the machine instructions Primitive Data Structures:
Integer, Floating-point number, Character constants, string constants, pointers Primitive Data Structures:
More sophisticated data structures Derived from the primitive data structures Non-Primitive Data Structures:
Linear List Non-Linear List Non-Primitive Data Structures:
Array Link List Stack Queue Linear List:
in linear data structure, values are arranged in linear fashion. Linear List
Fixed-Size Array:
Variable-Size Linked List:
Add to top and remove from top Stack:
Add to back and remove from front Queue:
Add anywhere, remove the highest priority Priority queue:
the data values in this structure are not arranged in order. Non-Linear List
unordered lists which use a ‘hash function’ to insert and search Hash Tables:
data is organized in branches Tree:
A more general branching structure, with less strict connection conditions than for a tree Graph:
values of the same types of data are stored Example: Array Homogenous
values of different types are grouped and stored Examples: Structures, Classes Non-Homogenous
The choice of particular data model depends on two considerations: Must be rich enough in structure to represent the relationship between data elements Should be simple enough that one can effectively process the data when necessary
Separating design details from usage Abstraction:
Separating the logical properties from the implementation details Abstraction:
Abstraction can also be applied to data True
data type that separates the logical properties from the implementation details Abstract Data Type (ADT):
Support abstraction, encapsulation, and information hiding Abstract Data Type (ADT):
providing only essential information outside the world Abstraction
binding the data, and the functions that use them Encapsulation
Add an item Remove an item Find, retrieve, or access an item Every Collection ADT should provide a way to:
the memory address of a variable Pointer
content is a memory address Pointer Variable
There is no name associated with the pointer data type in C++ True
Declaring Pointer Variables: dataType *identifier; Examples: int *p; char *ch
is called the address of the operator that returns the address of its operand Ampersand &
produces the address of that variable. It produces a pointer that points to the variable. &
simply called the address-of-operator & operator
When used as a unary operator, * is the dereferencing operator or indirection operator DEREFERENCING OPERATOR (*)
Refers to object to which its operand points DEREFERENCING OPERATOR (*)
produces the variable to which it points. * operator
creates a new dynamic variable of a specified type and returns a pointer that points to this new variable The new Operator
special area of memory that is reserved for dynamically allocated variables The heap (freestore)
Any new dynamic variable created by a program consumes some of the memory in the freestore True
If there was insufficient available memory to create the new variable, then new returned a special value named NULL True
eliminates a dynamic variable and returns the memory that the dynamic variable occupied to the freestore manager so that the memory can be reused. The delete Operator
if a pointer variable pointing to the dynamic variable that was destroyed and becomes undefined, they are called dangling pointers. Dangling pointers
you can assign a name definition and use the type name to declare variables using typedef keyword. Type definitions
a series of connected nodes, where each node is a data structure Linked list:
Can grow or shrink in size as the program runs Linked list:
Can easily grow or shrink in size Linked list:
Insertion and deletion of nodes is quicker with linked lists than with vectors Linked list:
Each node in a linked list contains one or more members that represent data Composition of a Linked List:
In addition to the data, each node contains a pointer, which can point to another node. Composition of a Linked List:
A linked list is called “linked” because each node in the series has a pointer that points to the next node in the list True
means to add the node to the end of the list Append a node
the displayList member function traverses the list, displaying the value of each node Traversing a List
Remove the node from the list without breaking the links created by the next pointers Deleting the node from memory Deleting a node: Requires two steps
should release all the memory used by the list. Does so by stepping through the list, deleting each node one-by-one. Destructor
found in the Standard Template Library, is a template version of a doubly linked list. list container
can insert elements, or add elements to their front quicker than vectors can, because lists do not have to shift the other elements STL lists
lists are also efficient at adding elements at their back because they have a built-in pointer to the last element in the list (no traversal required) True
Returns a reference to the last element in the list back: cout << list.back() << endl;
The first example causes the list element pointed to by the iterator iter to be removed. The second example causes all of the list elements from firstIter to lastIter to be removed. erase: list.erase(iter); list.erase(firstIter, lastIter)
The empty member function returns true if the list is empty. If the list has elements, it returns false. empty: If (list.empty())
End returns a bi-directional iterator to the end of the list end: iter = list.end();
Front returns a reference to the first element of the list front: cout << list.front() << endl;
Inserts an element into the list insert: list.insert(iter, x)
Inserts all the items in list2 into list1 is expanded to accommodate new elements plus any elements already stored in list1. merge: list1.merge(list2);
Removes the last element of the list pop_back: list.pop_back();
Removes the first element of the list pop_front: list.pop_front();
Inserts an element with value x at the end of the list push_back: list.push_back(x);
Inserts an element with value x at the beginning of the list push_front: list.push_front(x);
Reverses the order in which the elements appear in the list reverse: list.reverse();
Returns the number of elements in the list size():
The swap member function swaps the elements stored into two lists. swap: list1.swap(List2)
Removes any element that has the same value as the elements before it unique: list.unique();
is a data structure that stores and retrieves items in a last-in-first-out (LIFO) manner Stack
Computer systems use stacks during a program’s execution to store function return addresses, local variables, etc. Applications of Stack:
Some calculators use stacks for performing mathematical operations Applications of Stack:
causes a value to be stored in (pushed 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. Otherwise, it returns false. isFull
boolean operation needed for all stacks. Returns true if the stack is empty. Otherwise, returns false. isEmpty
Fixed size Can be implemented with an array Static Stacks:
Grow in size as needed Can be implemented with a linked list Dynamic Stacks:
a pointer to int. When the constructor is executed, it uses stackArray to dynamically allocate an array for storage *stackArray
an integer that holds the size of the stack stackSize
an integer that is used to mark the top of the stack top
the class constructor accepts an integer argument, which specifies the size of the stack. An integer of this size is dynamically allocated, and assigned to stackArray. Also, the variable top is initialized to -1. stackArray
accepts an integer, which is pushed onto the top of the stack push
uses an integer reference parameter. The value at the top of the stack is removed, and copied into the reference parameter pop
returns true if the stack is full and false otherwise. The stack is full when top is equal to stackSize -1 isFull
returns true if the stack is empty, and false otherwise. The stack is empty when the top is set to -1. isEmpty
built on a linked list instead of an array Dynamic Stack
No need to specify the starting size of the stack A dynamic stack will never be full, as long as the system has enough free memory Linked-List-Based stack offers two advantages over array-based stack.
may be implemented as a vector, a list, or a deque STL stack container
because the stack is used to adapt these other containers, it is often referred to as a container adapter. Container adapter
like a stack, is a data structure that holds a sequence of elements Queue
First-in, First-out (FIFO) a queue provides access to its elements in this order
The elements in a queue are processed like customers standing in a grocery check-out line: the first customer in line is the first one served. True
Dynamic queues offer the same advantages over static queues that dynamic stacks offer over static stacks True
Enqueueing Dequeueing Two primary queue operations:
starts as an empty linked list Dynamic queue
is a double-ended queue. Similar to a vector, but allows efficient access to values at both the front and the rear. deque
The queue ADT is like the stack ADT: it is actually a container adapter. True
The queue container adapter can be built upon vectors, lists, or deques. By default, it uses deque as its base. True
always inserts an element at the rear of the queue queue version of push
always removes an element from the structure’s front queue version of pop
returns the value of the element at the front of the queue top function
Created by: kopeiko
 

 



Voices

Use these flashcards to help memorize information. Look at the large card and try to recall what is on the other side. Then click the card to flip it. If you knew the answer, click the green Know box. Otherwise, click the red Don't know box.

When you've placed seven or more cards in the Don't know box, click "retry" to try those cards again.

If you've accidentally put the card in the wrong box, just click on the card to take it out of the box.

You can also use your keyboard to move the cards as follows:

If you are logged in to your account, this website will remember which cards you know and don't know so that they are in the same box the next time you log in.

When you need a break, try one of the other activities listed below the flashcards like Matching, Snowman, or Hungry Bug. Although it may feel like you're playing a game, your brain is still making more connections with the information to help you out.

To see how well you know the information, try the Quiz or Test activity.

Pass complete!
"Know" box contains:
Time elapsed:
Retries:
restart all cards