Lesson 1

Question 1

______ are the programmatic way of storing data so that data can be used efficiently.

Answer 1

Data Structures

Question 2

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.

Answer 2

Data Structure

Question 3

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.

Answer 3

Interface

Question 4

__________ provides the internal representation of a data structure. It also provides the definition of the algorithms used in the operations of the data structure.

Answer 4

Implementation

Question 5

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.

Answer 5

TRUE

Question 6

Some examples of how data structures are used include the following: (7)

Answer 6

Storing Data
Managing resources and services
Data Exchange
Ordering and sorting
Indexing
Searching
Scalability

Question 7

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.

Answer 7

Storing data

Question 8

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.

Answer 8

Managing resources and services.

Question 9

How data structures are used:
Data structures define the organization of information shared between applications, such as TCP/IP packets

Answer 9

Data exchange.

Question 10

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.

Answer 10

Ordering and sorting.

Question 11

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.

Answer 11

Indexing.

Question 12

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.

Answer 12

Searching.

Question 13

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.

Answer 13

Scalability.

Question 14

3 characteristics of data structures:

Answer 14

Linear or non-linear
Homogeneous or heterogeneous
Static or dynamic

Question 15

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.

Answer 15

Linear or non-linear.

Question 16

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.

Answer 16

Homogeneous or heterogeneous.

Question 17

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.

Answer 17

Static or dynamic.

Question 18

3 Need for Data Structure:

Answer 18

Data Search
Processor Speed
Multiple Requests

Question 19

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.

Answer 19

Data Search

Question 20

Need for Data Structure:
Processor speed although being very high, falls limited if
the data grows to billion records.

Answer 20

Processor speed

Question 21

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.

Answer 21

Multiple requests

Question 22

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.

Answer 22

Worst Case

Question 23

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.

Answer 23

Average Case

Question 24

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).

Answer 24

Best Case

Question 25

_____ are values or set of values.

Answer 25

Data

Question 26

_________ refers to single unit of values.

Answer 26

Data item

Question 27

Data items that are divided into sub items are called as __________.

Answer 27

Group Items

Question 28

Data items that cannot be divided are called as _______.

Answer 28

Elementary Items

Question 29

An entity is that which contains certain attributes or properties, which may be assigned values.

Answer 29

Attribute and Entity

Question 30

Entities of similar attributes form ______.

Answer 30

Entity Set

Question 31

_______ is a single elementary unit of information representing an attribute of an entity.

Answer 31

Field

Question 32

_______ is a collection of field values of a given entity.

Answer 32

Record

Question 33

______ is a collection of records of the entities in a given entity set.

Answer 33

File

Question 34

8 Common Data Structure Concepts:

Answer 34

Arrays
Linked List
Stacks
Queues
Hash Tables
Trees
Heaps
Graphs

Question 35

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

Answer 35

Array

Question 36

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.

Answer 36

Linked list

Question 37

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.

Answer 37

Stack

Question 38

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.

Answer 38

queue

Question 39

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.

Answer 39

Hash Table

Question 40

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.

Answer 40

Tree

Question 41

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.

Answer 41

Heap

Question 42

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.

Answer 42

graph

Question 43

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.

Answer 43

Arrays

Question 44

Applications:
Used for symbol table management in compiler design.

Used in switching between programs using Alt + Tab (implemented using Circular Linked List).

Answer 44

Linked List

Question 45

Applications:
Used for expression evaluation (e.g.: shunting-yard algorithm for parsing and evaluating mathematical expressions).

Used to implement function calls in recursion programming.

Answer 45

Stacks

Question 46

Applications:
Used to manage threads in multithreading.

Used to implement queuing systems (e.g.: priority queues).

Answer 46

Queues

Question 47

Applications:
Used to implement database indexes.

Used to implement associative arrays.

Used to implement the “set” data structure.

Answer 47

Hash Tables

Question 48

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.

Answer 48

Trees

Question 49

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.

Answer 49

Heaps

Question 50

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.

Answer 50

Graphs