Computer Science 101

Question 1

What are the two states in binary due to electricity switches?

Answer 1

0 (off) and 1 (on)

Question 2

What numbering system do humans commonly use?

Answer 2

Decimal system (0-9)

Question 3

How is a number incremented in the binary system?

Answer 3

After a bit reaches 1 in binary, an increment resets it to 0 but also causes an increment of the next bit to the left: 0000, 0001, (rightmost bit starts over, and the next bit is incremented)

Question 4

What is the base of the binary number system?

Answer 4

It uses base 2, so counting like 1, 2, 4, 8 …

Question 5

How do you convert a binary number to a decimal number?

Answer 5

Add the values of the positions with a 1, from right to left, using powers of 2.

Example:
128 64 32 16 8 4 2 1
1 0 1 1 0 0 1 1 = 179

Question 6

How do you convert a decimal number to a binary number?

Answer 6

write out the ^ to the power of numbers, working from the biggest number, subtract the numbers and put a 1 next to them until you’re left with 0

Question 7

What is a logarithmic function?

Answer 7

The opposite of an exponential function; it increases quickly at first and then levels out.

Question 8

What is an exponential function?

Answer 8

A function that increases rapidly - like timesing itself

Question 9

Why is the growth pattern of n-notation important?

Answer 9

It allows comparing the efficiency and scalability of algorithms by understanding how their performance changes with increasing input size.

Question 10

What is the Big O notation used for?

Answer 10

To represent the upper bound of the time complexity of an algorithm, indicating the worst-case scenario.

Question 11

What does O(n) signify in Big O notation?

Answer 11

Linear time complexity

Question 12

What does O(1) signify in Big O notation?

Answer 12

Constant time complexity (the time it takes to complete its task is constant and does not change with the size of the input data)

Question 13

What is a fixed array?

Answer 13

An array with a predefined size. (you’re asking the computer to look through its hard drive, find a slot with room for the array - for example 3 pieces of data.)

Question 14

What is a dynamic array?

Answer 14

An array that can grow in size as needed.

Question 15

What would the run time be (using big O) to insert randomly into a fixed array?

Answer 15

O(n) - inserting randomly requires moving data around in the array, at worst it will need to move every item in the array

Question 16

What is a linked list?

Answer 16

A data structure where each element (node) points to the next, and sometimes the previous, element.

Question 17

What is the difference between a singly and doubly linked list?

Answer 17

A singly linked list has nodes that point only to the next node, while a doubly linked list has nodes that point to both the next and the previous nodes.

Question 18

What is a stack?

Answer 18

A data structure that follows the Last In, First Out (LIFO) principle. (like a stack of trays in a canteen - grab and add from the top)

Question 19

What is a queue?

Answer 19

A data structure that follows the First In, First Out (FIFO) principle.

Question 20

What is a binary search tree (BST)?

Answer 20

A tree structure where each node has at most two children, and the left child is less than the parent node, while the right child is greater.

Question 21

What is a heap?

Answer 21

A tree-based data structure where the parent node is either greater than (max heap) or less than (min heap) its children.

Question 22

What is the purpose of a priority queue?

Answer 22

To manage elements based on their priority, where higher priority elements are served before lower priority ones.

Question 23

What is a graph?

Answer 23

• A collection of nodes (vertices) connected by edges.
• Nodes represent entities such as cities, people, or web pages.
• Edges represent the relationships or connections between nodes, such as roads between cities, friendships, or hyperlinks.
• Graphs can be directed (edges have a direction) or undirected (edges have no direction).
• Common uses include representing networks, social connections, and pathways.

Question 24

What is the difference between directed and undirected graphs?

Answer 24

Directed graphs have edges with a direction, while undirected graphs have edges with no specific direction.

Question 25

What is a weighted graph?

Answer 25

A graph where edges have weights representing the cost or distance between nodes.

Question 26

What is a depth-first search (DFS) in graph traversal?

Answer 26

A graph traversal method that explores as far as possible along each branch before backtracking.

Question 27

What is a breadth-first search (BFS)?

Answer 27

A graph traversal method that explores all nodes at the present depth before moving on to nodes at the next depth level.

Question 28

What is recursion, and how is it used in sorting algorithms?

Answer 28

• Recursion is a function calling itself, similar to a nested loop.
• It ensures the function doesn’t run indefinitely, as each call is pending a return statement.
• Commonly used in divide-and-conquer sorting algorithms like Quick Sort and Merge Sort.