Introduction to Data Structures - Flashcards

Flashcards covering core concepts from the notes: arrays, memory layouts, pointers, dynamic memory, ADT, data objects, and data structures.

What is the relationship between Algorithm and Data Structure in programming?

Algorithm + Data Structure = Program.

Define an Array.

A linear data structure that stores homogeneous data items in contiguous memory locations.

What is a Static array?

An array whose size cannot be changed after compilation.

What are the main types of arrays?

Single Dimensional (1-D) arrays and Multi-Dimensional arrays (2-D and n-D).

How is an array declared in C?

datatype arrayname[array_size]; e.g., int A[10];

How are elements of a 1-D array addressed in memory?

Address of ith element = base address + (i × sizeofelement).

What is the base address in an array?

The address of the first element.

How are 1-D array elements stored in memory?

Continuously in memory; contiguous memory locations.

What is a Two-Dimensional array?

An array with m rows and n columns (A[m][n]).

What is the row-major memory addressing formula for a 2-D array?

arr[i][j] = base address + [(i × noofcols + j) × sizeofdata_type].

What is the column-major memory addressing formula for a 2-D array?

arr[i][j] = base address + [(j × noofrows + i) × sizeofdata_type].

What is row-major representation?

All elements stored row-wise in memory; 2-D array viewed as a 1-D array in row-major order.

What is a self-referential structure?

A structure that contains a member which is a pointer to the same type of structure.

Provide an example of a self-referential structure in C.

struct node { int data1; char data2; struct node* link; };

What is a Pointer in C?

A variable that stores the address of another variable; & gives an address; * dereferences to access the value.

What does the malloc() function do?

Allocates a block of memory of a specified size and returns a pointer to the first byte; returns NULL on failure.

What does calloc() do?

Allocates memory for multiple objects of the same size and initializes all bytes to zero; returns pointer or NULL if insufficient memory.

What does free() do?

Releases previously allocated heap memory; the pointer can be reused; do not free elements individually.

What does realloc() do?

Resizes a previously allocated block; may move to a new location; returns a pointer to the new block or NULL on failure; preserves data when possible.

Where is dynamic memory allocated in a C program?

In the heap, separate from the stack and permanent storage area.

What is Abstract Data Type (ADT)?

A data type defined by a logical model with a set of operations and axioms; emphasizes what operations do, not how implemented.

What are advantages of ADT?

Encapsulation, information hiding, implementation hiding, reusability, and reduced complexity.

What are Derived Data Types?

Data types built from primitive types, such as arrays, pointers, structures, and unions.

What is a Data Object?

A runtime instance of a data structure that holds actual values; can be programmer-defined or system-defined.

What is the difference between Linear and Non-Linear Data Structures?

Linear: elements form a sequence (e.g., arrays, lists, stacks, queues). Non-Linear: hierarchical (e.g., trees, graphs).