01H1: Introduction to Data Structures and Algorithms

Data Structures

What are a particular way of organizing data in a computer to be used efficiently?

Data Structures

What is the arrangement of data in memory location to represent values of the carrier set of an abstract data type?

Large databases and internet indexing services

Data structures provides a means to manage large amounts of data for users, such as in what?

Data Structures

What is the key to designing efficient algorithms?

Pointer

Data structures are based on the ability of a computer to fetch and store data at any place in its memory, which is specified by a what?

Pointer

What do you call a bit string representing a memory address that can be stored in memory and manipulated by the program?

1. Array

2. List

3. Linked List

4. Stack

5. Queue

6. Hashing

7. Trees

What are examples of Data Structures?

Array

What is a fixed-length, ordered collection of values of the same type stored in contiguous memory locations?

One-dimensional array or two-dimensional array (matrix)

An array’s collection may be ordered in several dimensions; which are either?

Elements (values or variables)

(1) array index or key

Array consists of collection of what? And each identified by?

Array

What can be considered as the simplest type of data structure?

Lookup tables

Lists

Strings

Array are used to implement tables used by almost every program on a computer such as?

List

What is an abstract data type that represents a sequence of values, where the same value may occur more than once?

Instance = finite sequence

Stream = infinite sequence

What lists are computer representation of mathematical concept of sequences? And what type of sequences they are?

Containers

Lists are a basic example of what, as they contain other values?

1. Expose first element then the rest

2. Random access thru indexer

What are the two families of lists?

Linked List

What does consists of chains of nodes where each node contains information such as data and a pointer to the next node in the chain?

Data and a reference/pointer (a link)

Each node is composed of what in the sequence?

Linked List

What are among the simplest and most common data structures that can be used to implement several other common abstract data types?

Linked List

What does have the principal benefit over a conventional array in that the list elements can easily be inserted or removed?

Linked List

Which is it that can be done without reallocation or reorganization of the entire structure, as the data items need not be stored contiguously in memory or on disk?

Stack

What is the kind of abstract data type or collection in which the principal operations on the collection are the addition;pop of an entity to the collection and the removal;push of an entity?

Last-In-First-Out (LIFO)

What is the principle or order used in Stack data structure?

Last-In-First-Out (LIFO)

Which principle refers to the last element added to the structure must be the first one to be removed?

Top of the stack

The push and pop operations occur only at one end of the structure, referred to as?

Peek or top operation

What can also be implemented, which is about returning the value of the top element without removing it?

Overflow state

What is happening when a stack became full because it does not contain enough space to accept an entity to be pushed?

Stack elements have a natural order

The nature of the pop and push operation also means?

Queue

What is the kind of abstract data type or collection in which the entities in the collection are kept in order, and the principal operations on the collection are the addition of entities to the rear terminal position and the removal of entities from the front terminal position?

First-In-First-Out (FIFO)

Which principle or order does Queue follows?

First-In-First-Out (FIFO)

What principle or order refers to the first element added will be the first one to be removed?

Linear data structure

Queue is also an example of what?

Hashing

Which method allows one to insert, delete, and search for records based on a search key value?

Hash Table (An array)

Where does hash system stores records in?

Hashing

What is it that works in a way that a computation is being performed on a search key K that is intended to identify the position in the hash table that contains the record with key K?

Hash Function

What is the function that performs the calculations in the search key?

Not ordered by value

Since hashing schemes place records on the table in whatever order satisfies the needs of the address calculation, it means that the records are?

Slot

What is the position in the hash table called?

Variable M

What denoted the number of slots in the hash table?

Trees

What is a data structure made up of nodes or vertices and edges without having any cycles?

Null or empty tree

What is a tree with no nodes called?

Root node

(Potentially) many levels of add. nodes

A tree that is not empty consists of what, that in the end it also form a hierarchy?

Tree

What data structure can be defined recursively as a collection of nodes, where each node consists of a value, together with a list of references to (children) nodes?

Root Node

Where does a tree data structure starts?

The children

What is the other term for additional nodes?

No reference is duplicated

None points to the root

What are the constraints of list of references to (children) nodes?

Abstract Data Type

[…] is a mathematical model for a certain class of data structures that have similar behavior, or for certain data types of one or more programming languages that have identical semantics.

certain class of data structure

certain data type of one or more programming languages

Abstract Data Type is a mathematical model for a […] that have similar behavior, or for […] that have identical semantics.

operations and its;

mathematical pre-conditions & constraints

An abstract data type is defined only by the […] that may be performed on it and by […] on the effects (and possibly cost) of those operations.

1. Adding elements

2. Sorting elements

3. Searching elements

4. Re-arranging the elements

5. Performing matrix operations

6. Pre-fix & post-fix operations

Give the Abstract Array Operations:

1. Inserting

2. Searching

3. Deletion

Give the Abstract List Operations:

1. Check whether the list is empty

2. Access a node to modify it/obtain info in it

3. Traverse the list to access all elements (to print them, find specific element)

4. Determine the size of the list (num of elements)

5. Insert or remove specific element

6. Create a list by reading the elements from an input stream

7. Convert list to and from array, string, etc.

Give the Abstract Link Operations:

1. Push (Insert)

2. Pop (Extract)

3. Peek or top (Examine without removal)

Give the Abstract Stack Operations:

1. Enqueue (Join)

2. Dequeue (Remove first element)

3. Front (To access + serve first element)

Give the Abstract Queue Operations:

1. Add (Insert)

2. Delete (Remove)

Give the Abstract Hashing Operations:

1. Searching

2. Insertion

3. Deletion

4. Traversal

5. Sort

Give the Abstract Tree Operations: