Sorting Algorithms

Question 1

Which sorting algorithms are stable

Answer 1

Merge Sort, Insertion Sort, Counting Sort (basic forms)

Question 2

Which sort is the best for nearly-sorted data

Answer 2

insertion sort

Question 3

What is the worst-case complexity for Quick sort

Answer 3

O(n²), if the pivot is always the worst element.

Question 4

What does it mean if a sort is stable

Answer 4

it preserves the relative order of equal elements

Question 5

What are the properties for a linear structure

Answer 5

• There is a unique first and last element
• Every component has a unique predecessor and successor except the last or first

Question 6

What are the properties of a non-linear structure

Answer 6

if one linear feature is false

Question 7

In a linear structure what are the two methods for accessing stored data

Answer 7

• sequential structures
• Direct access structures

Question 8

What is a sequential structure

Answer 8

we can only access the nth element if we have accessed all elements preceding n

Question 9

What is direct access structure

Answer 9

any element can be accessed direction, no need to access any others.

Question 10

what are the features of arrays

Answer 10

they are fixed size and provide direct access to elements

Question 11

What are arrays as ADTs

Answer 11

a collection of fixed number of components of the same type

Question 12

What are the operations of Arrays as ADTs and what do they do

Answer 12

• ValueAt(i) - accessed value at position I
• store(I,v) - stores value v at position i

Question 13

Define a list

Answer 13

a linear structure that only provides sequential access to its elements

Question 14

What two special elements does a list have

Answer 14

• head: point to first element of list
• tail: pointer to last element of the list

Question 15

What is the advantage a list

Answer 15

it is not of fixed size

Question 16

What is the difference between delete(v) and deleteAll(v) in a list

Answer 16

delete removes the first instance of v

DeleteAll removes all occurrences of v

Question 17

What are linked listed

Answer 17

a collected of records called nodes each containing one member that gives the location of the next node in the list

Question 18

What do the nodes contain in a linked list

Answer 18

• a data member representing the value
• a link member representing the location of the successor of this node

Question 19

What are the advantages of linked lists

Answer 19

• Fair use of memory
• size of the structure does not need to be declared in advance
• common operations are cheaper

Question 20

What are the disadvantages of linked lists

Answer 20

• Algorithms are more complex, harder to read and debug
• allocation of memory space causes over head

Question 21

How do u insert a node in a linked list

Answer 21

add to the head so its new the first in the list

Question 22

What is the added feature with circular linked lists compared with linked lists

Answer 22

the link member of the last node points to the head(the first node)

Question 23

What is a stack

Answer 23

a collection of values of the same type

Question 24

What rule does stack operations follow

Answer 24

Last in First Out

Question 25

What operation does Push(v) perform in a stack

Answer 25

puts value v on top of the stack

Question 26

what does the operation pop() perform on a stack

Answer 26

removes and returns the value on the top of the stack

Question 27

What does the operation top() perform on a stack

Answer 27

returns the value on top of the stack

Question 28

what is a queue

Answer 28

also a collection of variables of the same type

Question 29

What rule does queue operation follow

Answer 29

first in first out

Question 30

What is the definition of a stable sorting method

Answer 30

a sorting method is said to be stable if it preserves the relative order of the items with duplicated keys on the list

Question 31

How does selection sort work

Answer 31

points start of at last element (last) and largest element (maxPos), keeps switching last with max pos till in order

Question 32

How does insertion sort work

Answer 32

creates order list from right to left while saving variable out of order in viable then placing then moving to the next variable

Question 33

How does bubble sort work

Answer 33

work from left to right swaping pos with pos + 1 if pos 1 is less than pos. keep doing so til in order

Question 34

How does quick sort work

Answer 34

Quick Sort is a divide-and-conquer sorting algorithm that works by partitioning an array around a pivot element, so that: Elements less than the pivot go to the left Elements greater than the pivot go to the right It then recursively sorts the left and right subarrays.

Question 35

How does merge sort work

Answer 35

Merge Sort is a divide-and-conquer algorithm that recursively divides the array into halves, sorts each half, and then merges the sorted halves into a fully sorted array.

Question 36

Why do we avoid direct access structures

Answer 36

we have to allocate its size in advance which could result in an overestimate and waste of space

Question 37

What is the division method for hash functions

Answer 37

k mod m

Question 38

what is the multiplication method to hash functions

Answer 38

m * (kAmod1)

Question 39

What is the best case scenario for bubble sort

Answer 39

omega (n)

Question 40

What is the worst case scenario for bubble sort

Answer 40

O(n^2)

Question 41

What is the best case scenario for selection sort

Answer 41

omega(n^2)

Question 42

What is the worst case scenario for selection sort

Answer 42

O(n^2)

Question 43

What is the best and worst case scenario for insertion sort

Answer 43

Best: omega(n) Worst: O(n^2)

Question 44

What is the best and worst case scenario for merge sort

Answer 44

Best: omega(nlogn) Worst: O(nlogn)

Question 45

What is the best and worst case scenario for quick sort

Answer 45

Best: omega(nlogn) worst: O(n^2)

Question 46

What is the best and worst case scenario for Heap sort

Answer 46

best: omega(nlogn) worst O(nlogn)

Question 47

What is the best and worst case scenario for Radix sort

Answer 47

best: omega(nk) worst: O(nk)

Question 48

Which two pairs of sets have the same time complexity

Answer 48

- Bubble sort - Insertion sort - heap sort - Merge sort

Question 49

What is the the order of the increasing time complexities

Answer 49

O(1) --> O(logn) --> O(n) --> O(nlogn) --> O(n^c) ---> O(n^2)

Question 50

what are the minimum number of fields for a doubly linked list

Answer 50

3 Prev - Pointer to previous node Data Next - pointer to next node

Question 51

Which sorting algorithms have average case performance of O(n^2)

Answer 51

Insertion sort Bubble sort selection sort

Question 52

which sorting algorithm has all performances for time complexity at n^2

Answer 52

selection sort tho bubble and insertion had it for average and worse but their best is O(n)

Question 53

What do merge sort, quick sort, and heap sort have in common with their time complexities

Answer 53

all time complexity the same at O(nlogn) but worst case quick sort is n^2

Question 54

In the context of sorting algorithms, what is the key characteristic of a stable sorting algorithm

Answer 54

it maintains the relative order of equal elements

Question 56

What are the two collision resolutions techniques for hashing

Answer 56

- Separate Chaining - Open Addressing

Question 57

What does separate chaining do

Answer 57

the table points to structures holding the elements that collide

Question 58

Define a tree

Answer 58

A collection of nodes connected by edges

Question 59

define a node

Answer 59

a unit that contains data and pointers to other nodes

Question 60

define an edge

Answer 60

a connected between two nodes

Question 61

define a path

Answer 61

a sequence of nodes connected by edges

Question 62

define a rooted tree

Answer 62

a tree with a single designated root node

Question 63

define a forest

Answer 63

a set of disjoint trees

Question 64

define a leave

Answer 64

a node with no children