Chapter 19. Computational thinking and problem solving Flashcards
(50 cards)
What is a binary search?
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.
What is an insertion sort?
A method of sorting data by placing each item in turn into its correct position in the sorted list.
What is a binary tree?
A hierarchical data structure in which each node has at most two child nodes.
What is a graph in computer science?
A non-linear data structure consisting of nodes and edges.
What is Big O notation?
A mathematical notation used to describe the performance or complexity of an algorithm in the worst-case scenario.
What is recursion?
A process where a function calls itself; defined by a base case and a general case.
What is the base case in recursion?
The terminating condition that stops recursion.
What is the general case in recursion?
The part of a recursive function that calls itself to continue the recursion.
What is winding in recursion?
The phase where recursive calls are made until the base case is reached.
What is unwinding in recursion?
The phase where recursive calls return values back up the call stack.
Give a pseudocode example of a recursive factorial function.
FUNCTION factorial (number: INTEGER) RETURNS INTEGER\nIF number = 0 THEN answer ! 1 ELSE answer ! number * factorial(number - 1)\nRETURN answer ENDFUNCTION
What is an abstract data type (ADT)?
A data structure defined by its behavior (operations), not its implementation.
What is a dictionary data type?
An abstract data type consisting of key-value pairs, where the key is used to find the value.
Name three sorting algorithms discussed in Chapter 19.
Insertion sort, Bubble sort, Recursive sort
Describe the structure of a linked list.
A sequence of nodes where each node contains data and a pointer to the next node.
How can a dictionary be implemented from a linked list?
By storing key-value pairs in nodes and linking them together.
What is the main difference between a linear search and binary search?
Linear search checks each item sequentially; binary search splits the list in halves.
Give the Big O notation of linear search.
O(n)
Give the Big O notation of binary search.
O(log n)
Give the Big O of bubble sort in worst case.
O(n²)
What is the benefit of recursive solutions?
They can solve complex problems with fewer lines of code and greater clarity.
What is the drawback of recursion?
Heavy use of the stack may lead to stack overflow for deep recursions.
What data structure does recursion heavily depend on?
The call stack
What are the key steps to write a recursive function?
Define the base case, define the general case that calls itself.