Lesson 1 Flashcards
______ are the programmatic way of storing data so that data can be used efficiently.
Data Structures
Systematic way to organize data in order to use it efficiently. Almost every enterprise application uses various types of data structures in one or the other way.
Data Structure
Each data structure has this. ________ represents the set of operations that a data structure supports. It only provides the list of supported operations, type of parameters they can accept and return type of these operations.
Interface
__________ provides the internal representation of a data structure. It also provides the definition of the algorithms used in the operations of the data structure.
Implementation
TRUE OR FALSE:
In general, data structures are used to implement the physical forms of abstract data types. Data structures are a crucial part of designing efficient software. They also play a critical role in algorithm design and how those algorithms are used within computer programs.
TRUE
Some examples of how data structures are used include the following: (7)
Storing Data
Managing resources and services
Data Exchange
Ordering and sorting
Indexing
Searching
Scalability
How data structures are used:
Data structures are used for efficient data persistence, such as specifying the collection of attributes and corresponding structures used to store records in a database management system.
Storing data
How data structures are used:
Core operating system (OS) resources and services are enabled through the use of data structures such as linked lists for memory allocation, file directory management and file structure trees, as well as process scheduling queues.
Managing resources and services.
How data structures are used:
Data structures define the organization of information shared between applications, such as TCP/IP packets
Data exchange.
How data structures are used:
Data structures such as binary search trees – also known as an ordered or sorted binary tree – provide efficient methods of sorting objects, such as character strings used as tags. With data structures such as priority queues, programmers can manage items organized according to a specific priority.
Ordering and sorting.
How data structures are used:
Even more sophisticated data structures such as B-trees are used to index objects, such as those stored in a database.
Indexing.
How data structures are used:
Indexes created using binary search trees, B-trees or hash tables speed the ability to find a specific sought-after item.
Searching.
How data structures are used:
Big data applications use data structures for allocating and managing data storage across distributed storage locations, ensuring scalability and performance. Certain big data programming environments – such as Apache
Spark – provide data structures that mirror the underlying structure of database records to simplify querying.
Scalability.
3 characteristics of data structures:
Linear or non-linear
Homogeneous or heterogeneous
Static or dynamic
Characteristics of data structures:
This characteristic describes whether the data items are arranged in sequential order, such as with an array, or in an unordered sequence, such as with a graph.
Linear or non-linear.
Characteristics of data structures:
This characteristic describes whether all data items in a given repository are of the same type. One example is a collection of elements in an array, or of various types, such as an abstract data type defined as a structure in C or a class specification in Java.
Homogeneous or heterogeneous.
Characteristics of data structures:
This characteristic describes how the data structures are compiled. Static data structures have fixed sizes, structures and memory locations at compile time. Dynamic data structures have sizes, structures and memory locations that can shrink or expand, depending on the use.
Static or dynamic.
3 Need for Data Structure:
Data Search
Processor Speed
Multiple Requests
Need for Data Structure:
Consider an inventory of 1 million(106) items of a store. If the application is to search an item, it has to search an item in 1 million(106) items every time slowing down the search. As data grows, search will become slower.
Data Search
Need for Data Structure:
Processor speed although being very high, falls limited if
the data grows to billion records.
Processor speed
Need for Data Structure:
As thousands of users can search data simultaneously on a web server, even the fast server fails while searching the data.
Multiple requests
Execution Time Cases:
This is the scenario where a particular data structure operation takes maximum time it can take. If an operation’s worst case time is ƒ(n) then this operation will not take more than ƒ(n) time where ƒ(n) represents function of n.
Worst Case
Execution Time Cases:
This is the scenario depicting the average execution time of an
operation of a data structure. If an operation takes ƒ(n) time in execution, then m operations will take mƒ(n) time.
Average Case
Execution Time Cases:
This is the scenario depicting the least possible execution time of an operation of a data structure. If an operation takes ƒ(n) time in execution, then the actual operation may take time as the random number which would be maximum as ƒ(n).
Best Case
_____ are values or set of values.
Data
_________ refers to single unit of values.
Data item
Data items that are divided into sub items are called as __________.
Group Items
Data items that cannot be divided are called as _______.
Elementary Items
An entity is that which contains certain attributes or properties, which may be assigned values.
Attribute and Entity
Entities of similar attributes form ______.
Entity Set
_______ is a single elementary unit of information representing an attribute of an entity.
Field
_______ is a collection of field values of a given entity.
Record
______ is a collection of records of the entities in a given entity set.
File
8 Common Data Structure Concepts:
Arrays
Linked List
Stacks
Queues
Hash Tables
Trees
Heaps
Graphs
Common Data Structure Concept:
An __________ is a structure of fixed-size, which can hold items of the same data type. It can be an array of integers, an array of floating-point numbers, an array of strings or even an array of arrays (such as 2-dimensional arrays). Arrays are indexed, meaning that random access is possible
Array
Common Data Structure Concept:
A __________ is a sequential structure that consists of a sequence of items in linear order which are linked to each other. Hence, you have to access data sequentially and random access is not possible. It provides a simple and flexible representation of dynamic sets.
Linked list
Common Data Structure Concept:
A _______ is a LIFO (Last In First Out — the element placed at last can be accessed at first) structure which can be commonly found in many programming languages. This structure is named as “____” because it resembles a real-world stack — a stack of plates.
Stack
Common Data Structure Concept:
A ______ is a FIFO (First In First Out — the element placed at first can be accessed at first) structure which can be commonly found in many programming languages. This structure is named as “_____” because it resembles a real-world queue — people waiting in a queue.
queue
Common Data Structure Concept:
A ________ is a data structure that stores values which have keys associated with each of them. Furthermore, it supports lookup efficiently if we know the key associated with the value. Hence it is very efficient in inserting and searching, irrespective of the size of the data.
Hash Table
Common Data Structure Concept:
A _______ is a hierarchical structure where data is organized hierarchically and are linked together. This structure is different from a linked list whereas, in a linked list, items are linked in a linear order.
Tree
Common Data Structure Concept:
A ____ is a special case of a binary tree where the parent nodes are compared to their children with their values and are arranged accordingly.
Heap
Common Data Structure Concept:
A ______ consists of a finite set of vertices or nodes and a set of edges connecting these vertices. The order of a graph is the number of vertices in the graph. The size of a graph is the number of edges in the graph.
graph
Applications:
Used as the building blocks to build other data structures such as array lists, heaps, hash tables, vectors and matrices.
Used for different sorting algorithms such as insertion sort, quick sort, bubble sort and merge sort.
Arrays
Applications:
Used for symbol table management in compiler design.
Used in switching between programs using Alt + Tab (implemented using Circular Linked List).
Linked List
Applications:
Used for expression evaluation (e.g.: shunting-yard algorithm for parsing and evaluating mathematical expressions).
Used to implement function calls in recursion programming.
Stacks
Applications:
Used to manage threads in multithreading.
Used to implement queuing systems (e.g.: priority queues).
Queues
Applications:
Used to implement database indexes.
Used to implement associative arrays.
Used to implement the “set” data structure.
Hash Tables
Applications:
Binary Trees: Used to implement expression parsers and expression solvers.
Binary Search Tree: used in many search applications where data are constantly entering and leaving.
Heaps: used by JVM (Java Virtual Machine) to store Java objects.
Treaps: used in wireless networking.
Trees
Applications:
Used in heapsort algorithm.
Used to implement priority queues as the priority values can be ordered according to the heap property where the heap can be implemented using an array.
Queue functions can be implemented using heaps within O(log n) time.
Used to find thekᵗʰsmallest (or largest) value in a given array.
Heaps
Applications:
Used to represent social media networks. Each user is a vertex, and when users connect they create an edge.
Used to represent web pages and links by search engines. Web pages on the
internet are linked to each other by hyperlinks. Each page is a vertex and the hyperlink between two pages is an edge. Used for Page Ranking in Google.
Used to represent locations and routes in GPS. Locations are vertices and the routes connecting locations are edges. Used to calculate the shortest route between two locations.
Graphs
