Module 1 Flashcards
These are the programmatic way of storing data so it can be used efficiently
Data structures
It represents the set of operations that a data structure supports
Interface
This provides the internal representation of a data structure, as well as provide the definition of the algorithms used in the operations
Implementation
Data structures are used for specifying the collection of attributes and corresponding structures used to store records in a DBMS
Storing data
_____ resources and services are enabled through the use of data structures
Core operating system
Core operating system resources and services are enabled through the use of data structures
Managing resources and services
Data structures define the organization of information shared between applications, such as TCP/IP packets
Data exchange
These provide efficient methods of sorting objects, such as character strings used as tags; programmers can manage items organized according to a specific priority
Ordering and sorting
Data structures stored in a database such as B-trees are used to index objects
Indexing
Indexes created using binary search trees, B-trees or hash tables speed the ability to find a specific sought-after item
Searching
Big data applications use data structures for allocating and managing data storage across distributed storage locations
Scalability
This characteristic describes whether the data items are arranged in a sequential order, such as with an array, or in an unordered sequence, such as with a graph
Linear or non-linear
This characteristic describes whether all data items in a given repository are of the same type.
Homogenous or heterogenous
This characteristic describes how the data structures are compiled
Static or dynamic
These have fixed sizes, structures and memory locations at compile time
Static data
These have sizes, structures and memory locations that can shrink or expand, depending on the use
Dynamic
Why do we need data structure?
Data search
Processor speed
Multiple requests
True or false: Data can be organized in a data structure in such a way that all items may not be required to be searched, and the required data can be searched almost instantly
True
This is the scenario where a particular data structure operation takes maximum time it can take
Worst case
This is the scenario depicting the average execution time of an operation of a data structure
Average case
This is the scenario depicting the least possible execution time of an operation of a data structure
Best case
These are set of values
Data
These refer to single unit of values
Data item
Data items that are divided into sub items are called
Group items
Data items that cannot be divided are called as
Elementary items
It contains certain attributes or properties, which may be assigned values
Attribute and Entity
These are entities of similar attribtues forming an entity set
Entity set
This is a single elementary unit of information representing an attribute of an entity
Field
This is a collection of field values of a given entity
Record
This is a collection of records of the entities in a given entity set
File
It is a structure of fixed-size, which can hold items of the same data type
Array
What are the different sorting algorithms
Insertion sort, quick sort, bubble sort, merge sort
This is a sequential structure that consists of a sequence of items in linear order which are linked to each other
Linked lists
This is a LIFO (Last In First Out-the element placed at last can be accessed at first)
Stack
This is a FIFO (First In First Out –the element placed at first can be accessed at first); resembles people waiting in a line
Queues
This is a data structure that stores values which have keys associated with each of them
Hash table
This is a hierarchical structure where date is organized hierarchically and are linked together
Tree
What are the different applications of trees
Binary trees
Binary Search Tree
Heaps
Treaps
This is a special case of a binary tree where the parent nodes are compared to their children with their values arranged accordingly
Heap
These are used to find the smallest (or largest) value in a given array
Heaps
These consist of a finite set of vertices or nodes and a set of edges connecting these vertices
Graph
This is the number of vertices in the graph
order
This is the number of edges in the graph
Size
These are used to represent social media networks
Graphs
These are used to represent web pages and links by search engines
Graphs
These are used to represent locations and routes in GPS
Graphs
These are used to implement expression parsers and solvers
Binary Trees
Used in many search applications where data are constantly entering and leaving
Binay Search Trees
Used by Java Virtual Machine to store java objects
Heaps
Data structure used in wireless networking
Treaps
What are the 8 common datatypes?
Arrays
Linked Lists
Stack
Queues
Hash Table
Trees
Heap
Graph
Application of arrays
- For building other data structures
- Array lists
- Heaps
- Hash Tables
- Vectors
- Matrices
- For sorting algorithms:
- Insertion sort
- Quick sort
- Bubble sort
- Merge sort -
Application of Linked Lists
- Symbol Table Management
- Switching between programs using alt + tab (using circular linked list)
Applications of stacks
- Expression evaluation:
- shunting-yard algorithm
- parsing and evaluating mathematical expressions
- implementing function calls in recursion programming
Application of Queues
- Multithreading
- Implementing queuing systems (i.e., priority queues)
Applications of hash tables
- Database indexes
- Associative arrays
- Set data structure
Applications of trees
Binary trees: expression parsers and solvers
Binary Search Tree
Heaps: used by Java Virtual Machine
Treaps: Used in wireless networking
Applications of heaps
- Heapsort algorithm
- Implement priority queues
- Queue functions within O(log n) time
- Used to find the smallest or largest value in an array
Applications of graphs
- represent social media networks: user - vertex; users - edge
- represent web pages and links: each page - vertex; hyperlink: edge
- page ranking in google
- locations and routes in GPS: location - vertices; routes: edges
- calculate the shortest route between two locations
How are data structures used:
Storing Data
Managing resources and services
Data Exchange
Ordering and Sorting
Indexing
Searching
Scalability
