The flashcards below were created by user
on FreezingBlue Flashcards.
Define an array.
An array is an indexed list of values of the same type. An array's members are stored contiguously in memory.
Define a multidimensional array.
A multidimensional array is an indexed table of values of the same type, using more than one dimension. If the array has several rows and columns, the members are still stored contiguously in memory, but the rows may be stored sequentially in memory.
Define a linked list.
A linked list is a list of nodes (the memory for which is allocated dynamically as needed), in which a node contains the data it was created to store and a pointer to where the next node is stored.
What are some advantages of arrays?
- indexing facilitates sorting
- binary search possible if sorted
- straightforward to program
- memory easily cleared after use
What are some disadvantages of arrays?
- require contiguous memory
- require specific size
- potentially waste memory
- potentially run out of memory
- insertion requires rearranging
- deletion requires rearranging
What are some advantages of linked lists?
- dynamically allocate memory
- has flexible size
- uses only allocated space (allocated as needed)
- expands memory as needed
- insertion requires slight relink
- deletion requires slight relink
What are some disadvantages of linked lists?
- one-by-one searching required
- sequential search only
- tougher to conceptualize
- complicated garbage collection
Define a stack.
- A stack is a data structure that manages a list of similar items in such a way that all insertions and deletions take place at one designated end of the list.
- (No real life equivalent.)
What is the terminology used to describe adding an item to a stack or deleting an item from a stack?
- An item is pushed onto the top of the stack.
- An item is popped off the top of the stack.
Name 6 data structures:
- multidimensional array
- linked list
- binary tree
Define a queue.
- A queue is a data structure that manages a list of similar items in such a way that all insertions take place at one end of the list; while all deletions take place at the other end.
- (Like getting in a line)
Define a binary tree.
A binary tree is a hierarchical data structure that manages a collection of similar items in such a way that one item is designated as the root of the tree and every other item is either the left or right offspring of some previously positioned item.
Describe how a new node is inserted into a binary insertion tree.
Starting at the root of the tree, at each node, ask if the node to be inserted is larger or smaller than the new node. If larger -> right. If smaller -> left. If there is not a position open you must continue down the tree.
How does recursive travel of a binary insertion tree work?
- First, there are 6 possible orders. They can be described by the order in which they process the nodes:
- 1) in-order -> left, self, right
- 2) reverse-order -> right, self, left
- 3) pre-order -> self, left, right
- 4) reverse pre-order -> self, right, left
- 5) post-order -> left, right, self
- 6) reverse post-order -> right, left, self