Chapter 19. Computational thinking and problem solving

Question 1

What is a binary search?

Answer 1

A method of searching an ordered list by testing the value of the middle item and rejecting the half that does not contain the required value.

Question 2

What is an insertion sort?

Answer 2

A method of sorting data by placing each item in turn into its correct position in the sorted list.

Question 3

What is a binary tree?

Answer 3

A hierarchical data structure in which each node has at most two child nodes.

Question 4

What is a graph in computer science?

Answer 4

A non-linear data structure consisting of nodes and edges.

Question 5

What is Big O notation?

Answer 5

A mathematical notation used to describe the performance or complexity of an algorithm in the worst-case scenario.

Question 6

What is recursion?

Answer 6

A process where a function calls itself; defined by a base case and a general case.

Question 7

What is the base case in recursion?

Answer 7

The terminating condition that stops recursion.

Question 8

What is the general case in recursion?

Answer 8

The part of a recursive function that calls itself to continue the recursion.

Question 9

What is winding in recursion?

Answer 9

The phase where recursive calls are made until the base case is reached.

Question 10

What is unwinding in recursion?

Answer 10

The phase where recursive calls return values back up the call stack.

Question 11

Give a pseudocode example of a recursive factorial function.

Answer 11

FUNCTION factorial (number: INTEGER) RETURNS INTEGER\nIF number = 0 THEN answer ! 1 ELSE answer ! number * factorial(number - 1)\nRETURN answer ENDFUNCTION

Question 12

What is an abstract data type (ADT)?

Answer 12

A data structure defined by its behavior (operations), not its implementation.

Question 13

What is a dictionary data type?

Answer 13

An abstract data type consisting of key-value pairs, where the key is used to find the value.

Question 14

Name three sorting algorithms discussed in Chapter 19.

Answer 14

Insertion sort, Bubble sort, Recursive sort

Question 15

Describe the structure of a linked list.

Answer 15

A sequence of nodes where each node contains data and a pointer to the next node.

Question 16

How can a dictionary be implemented from a linked list?

Answer 16

By storing key-value pairs in nodes and linking them together.

Question 17

What is the main difference between a linear search and binary search?

Answer 17

Linear search checks each item sequentially; binary search splits the list in halves.

Question 18

Give the Big O notation of linear search.

Answer 18

O(n)

Question 19

Give the Big O notation of binary search.

Answer 19

O(log n)

Question 20

Give the Big O of bubble sort in worst case.

Answer 20

O(n²)

Question 21

What is the benefit of recursive solutions?

Answer 21

They can solve complex problems with fewer lines of code and greater clarity.

Question 22

What is the drawback of recursion?

Answer 22

Heavy use of the stack may lead to stack overflow for deep recursions.

Question 23

What data structure does recursion heavily depend on?

Answer 23

The call stack

Question 24

What are the key steps to write a recursive function?

Answer 24

Define the base case, define the general case that calls itself.

Question 25

Write a recursive pseudocode function for compound interest.

Answer 25

FUNCTION compoundInt(principal, rate, years: REAL) RETURNS REAL\nIF years = 0 THEN total ! principal\nELSE total ! compoundInt(principal * rate, rate, years - 1)\nRETURN total ENDFUNCTION

Question 26

What are the first two numbers in the Fibonacci sequence?

Answer 26

0 and 1

Question 27

What is the Fibonacci recurrence relation?

Answer 27

F(n) = F(n-1) + F(n-2)

Question 28

What is an example use of graphs in real life?

Answer 28

Social media networks, where nodes are people and edges are connections

Question 29

Give a recursive pseudocode function to compute Fibonacci numbers.

Answer 29

FUNCTION fib(n: INTEGER) RETURNS INTEGER\nIF n = 0 THEN RETURN 0\nELSE IF n = 1 THEN RETURN 1\nELSE RETURN fib(n-1) + fib(n-2) ENDFUNCTION

Question 30

What is the purpose of using abstract data types?

Answer 30

To simplify programming by focusing on operations rather than implementation.

Question 31

What are the common operations for a queue ADT?

Answer 31

Create queue, add item, remove item

Question 32

Give a sorting algorithm that uses comparisons and swapping of adjacent elements.

Answer 32

Bubble sort

Question 33

Why does a compiler use the stack in recursive functions?

Answer 33

To store return addresses and local variables for each call

Question 34

Write an iterative pseudocode for bubble sort.

Answer 34

FOR ThisPointer ! 1 TO 9\nFOR Pointer ! 1 TO 9\nIF NameList[Pointer] > NameList[Pointer + 1] THEN\nTemp ! NameList[Pointer]\nNameList[Pointer] ! NameList[Pointer + 1]\nNameList[Pointer + 1] ! Temp\nENDIF\nENDFOR\nENDFOR

Question 35

What is a node in a graph?

Answer 35

A fundamental unit that represents an entity; connected by edges.

Question 36

What is a directed graph?

Answer 36

A graph where edges have a direction from one node to another.

Question 37

What is a weighted edge in a graph?

Answer 37

An edge with a numerical value representing cost, time, or distance.

Question 38

What is a path in a graph?

Answer 38

A sequence of nodes connected by edges.

Question 39

What is a cycle in a graph?

Answer 39

A path that starts and ends at the same node.

Question 40

How do you define a linked list using a record type in pseudocode?

Answer 40

TYPE Node\nDECLARE Name: STRING\nDECLARE Pointer: INTEGER\nENDTYPE

Question 41

What’s an example of an algorithm with O(1) space complexity?

Answer 41

An algorithm that just uses variables, e.g., d = a + b + c

Question 42

What’s an example of an algorithm with O(n) space complexity?

Answer 42

An algorithm using arrays, e.g., summing values in an array

Question 43

What’s the difference between iterative and recursive approaches?

Answer 43

Iterative uses loops, recursive uses function calls

Question 44

What should a recursive function always include to avoid infinite calls?

Answer 44

A base case

Question 45

What is the benefit of decomposition in problem solving?

Answer 45

Breaks down complex problems into manageable parts

Question 46

What is pattern recognition in computational thinking?

Answer 46

Identifying parts of a problem that are similar to reuse solutions

Question 47

Why might recursion be more elegant than iteration?

Answer 47

It simplifies code for problems with repetitive structure, like tree traversal or factorial

Question 48

Give a real-world example of a recursive process.

Answer 48

Directory traversal in file systems

Question 49

Name three languages suitable for algorithm implementation in this chapter.

Answer 49

Python, Java, VB.NET

Question 50

What is stepwise refinement?

Answer 50

Breaking down problems into smaller and smaller tasks until they are easily solvable