Linear Data Structures and Algorithms

Question 1

What is an algorithm?

Answer 1

A finite, well-defined sequence of computational steps to solve a specific problem.

Question 2

List the five characteristics of an algorithm.

Answer 2

Finiteness, Definiteness, Input, Output, Effectiveness.

Question 3

What is a computational problem?

Answer 3

A relationship between inputs and outputs, defined by preconditions and postconditions.

Question 4

What is the difference between an algorithm and a program?

Answer 4

An algorithm is conceptual; a program is its implementation in a programming language.

Question 5

What does it mean for an algorithm to be correct?

Answer 5

It is sound (valid results) and complete (guaranteed results for all valid inputs).

Question 6

What is the RAM model?

Answer 6

A theoretical machine that assumes constant-time operations and infinite memory.

Question 7

Why is the RAM model useful?

Answer 7

It simplifies algorithm analysis by abstracting hardware complexities.

Question 8

Define the term “effective” in the context of algorithms.

Answer 8

Each operation is basic and executable in finite time.

Question 9

What is the purpose of pointer arithmetic in arrays?

Answer 9

To enable operations like indirect addressing (A[A[i]]).

Question 10

Describe the difference between zero-based and one-based indexing.

Answer 10

Zero-based indexing starts at 0 (e.g., Java), while one-based indexing starts at 1.

Question 11

What is time complexity?

Answer 11

A measure of the number of operations an algorithm performs relative to input size.

Question 11

What is the best-case complexity of insertion sort?

Answer 11

O(n), when the array is already sorted.

Question 12

What is the worst-case complexity of insertion sort?

Answer 12

O(n^2), when the array is sorted in reverse order

Question 13

What is mathematical induction?

Answer 13

A method of proving statements for all natural numbers by establishing a base case and an inductive step.

Question 14

What is the invariant condition in insertion sort?

Answer 14

At each step, the subarray before the current element is sorted.

Question 15

What does it mean for an algorithm to terminate?

Answer 15

It completes in a finite number of steps.

Question 16

What is the role of preconditions in algorithm analysis?

Answer 16

They define valid input conditions for the algorithm to run correctly.

Question 17

What are the steps of the insertion sort algorithm?

Answer 17

Pick an element, find its correct position, shift larger elements, and insert it.

Question 18

What is the role of postconditions in algorithms?

Answer 18

They specify what must be true after the algorithm completes.

Question 19

How can the runtime of an algorithm be analyzed?

Answer 19

By counting operations or steps in the RAM model.

Question 20

What is an ADT?

Answer 20

Abstract Data Type - A specification of operations on data without detailing implementation.

Question 21

What are creators, observers, and mutators in ADTs?

Answer 21

Creators initialize data, observers query data, and mutators modify data.

Question 22

List the main operations of a stack.

Answer 22

push, pop, and peek.

Question 23

What is a queue, and what are its main operations?

Answer 23

A FIFO data structure with enqueue and dequeue operations.

Question 24

How is a stack implemented using an array?

Answer 24

Using a fixed-size array and a pointer to track the top element.

Question 25

What is a stack overflow?

Answer 25

Adding an element to a full stack.

Question 26

What is a stack underflow?

Answer 26

Removing an element from an empty stack.

Question 27

How are queues implemented using arrays?

Answer 27

Using circular arrays with head and tail pointers.

Question 28

What is the difference between ADTs and data structures?

Answer 28

ADTs define functionality; data structures provide concrete implementations.

Question 29

Why is data abstraction important?

Answer 29

It hides implementation details, allowing flexibility in modifying underlying structures.

Question 30

How does insertion sort work conceptually?

Answer 30

By iteratively inserting elements into their correct positions in a sorted subarray.

Question 31

What is the role of invariants in sorting algorithms?

Answer 31

They ensure the partial correctness of the algorithm at every step.

Question 32

Why is insertion sort inefficient for large datasets?

Answer 32

Its worst-case complexity is quadratic.

Question 33

What is the difference between bubble sort and insertion sort?

Answer 33

Bubble sort repeatedly swaps adjacent elements; insertion sort shifts elements to insert.

Question 34

Why is merge sort preferred for larger datasets?

Answer 34

It has a better time complexity of O(nlogn).

Question 35

What is the divide-and-conquer approach in merge sort?

Answer 35

Divide the array, sort each half recursively, and merge them.

Question 36

Describe a key advantage of merge sort.

Answer 36

It guarantees O(nlogn) performance for all inputs.

Question 37

What is the disadvantage of merge sort compared to quicksort?

Answer 37

Merge sort requires additional memory for merging.

Question 38

What is the stability of a sorting algorithm?

Answer 38

Whether it preserves the relative order of equal elements.

Question 39

What is a static data structure?

Answer 39

A data structure with a fixed size, like arrays.

Question 40

What is a dynamic data structure?

Answer 40

A data structure that can grow or shrink in size, like linked lists.

Question 41

How is a singly linked list implemented?

Answer 41

Using nodes with data and a reference to the next node.

Question 42

What are the advantages of dynamic data structures?

Answer 42

Flexibility and efficient memory usage.

Question 43

What is a circular queue?

Answer 43

A queue where the end wraps around to the front.

Question 44

How is a stack implemented using a linked list?

Answer 44

Using a reference to the top node, where push and pop operate.

Question 45

What is the difference between stacks and queues?

Answer 45

Stacks are LIFO, while queues are FIFO.

Question 46

What is a priority queue?

Answer 46

A queue where elements are dequeued based on priority.

Question 47

How does pointer arithmetic enable efficient data access?

Answer 47

By allowing direct computation of element addresses.

Question 48

What is the key disadvantage of static arrays?

Answer 48

Their size must be known at allocation time.

Question 49

Why do Java developers wear glasses?

Answer 49

Because they can’t C#!... haha