{ "@context": "https://schema.org", "@type": "Organization", "name": "Brainscape", "url": "https://www.brainscape.com/", "logo": "https://www.brainscape.com/pks/images/cms/public-views/shared/Brainscape-logo-c4e172b280b4616f7fda.svg", "sameAs": [ "https://www.facebook.com/Brainscape", "https://x.com/brainscape", "https://www.linkedin.com/company/brainscape", "https://www.instagram.com/brainscape/", "https://www.tiktok.com/@brainscapeu", "https://www.pinterest.com/brainscape/", "https://www.youtube.com/@BrainscapeNY" ], "contactPoint": { "@type": "ContactPoint", "telephone": "(929) 334-4005", "contactType": "customer service", "availableLanguage": ["English"] }, "founder": { "@type": "Person", "name": "Andrew Cohen" }, "description": "Brainscape’s spaced repetition system is proven to DOUBLE learning results! Find, make, and study flashcards online or in our mobile app. Serious learners only.", "address": { "@type": "PostalAddress", "streetAddress": "159 W 25th St, Ste 517", "addressLocality": "New York", "addressRegion": "NY", "postalCode": "10001", "addressCountry": "USA" } }

Chapter 19. Computational thinking and problem solving Flashcards

(50 cards)

1
Q

What is a binary search?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is an insertion sort?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is a binary tree?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a graph in computer science?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is Big O notation?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is recursion?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the base case in recursion?

A

The terminating condition that stops recursion.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the general case in recursion?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is winding in recursion?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is unwinding in recursion?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Give a pseudocode example of a recursive factorial function.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is an abstract data type (ADT)?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is a dictionary data type?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Name three sorting algorithms discussed in Chapter 19.

A

Insertion sort, Bubble sort, Recursive sort

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Describe the structure of a linked list.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How can a dictionary be implemented from a linked list?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Give the Big O notation of linear search.

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Give the Big O notation of binary search.

A

O(log n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Give the Big O of bubble sort in worst case.

A

O(n²)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is the benefit of recursive solutions?

A

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

22
Q

What is the drawback of recursion?

A

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

23
Q

What data structure does recursion heavily depend on?

A

The call stack

24
Q

What are the key steps to write a recursive function?

A

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

25
Write a recursive pseudocode function for compound interest.
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
26
What are the first two numbers in the Fibonacci sequence?
0 and 1
27
What is the Fibonacci recurrence relation?
F(n) = F(n-1) + F(n-2)
28
What is an example use of graphs in real life?
Social media networks, where nodes are people and edges are connections
29
Give a recursive pseudocode function to compute Fibonacci numbers.
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
30
What is the purpose of using abstract data types?
To simplify programming by focusing on operations rather than implementation.
31
What are the common operations for a queue ADT?
Create queue, add item, remove item
32
Give a sorting algorithm that uses comparisons and swapping of adjacent elements.
Bubble sort
33
Why does a compiler use the stack in recursive functions?
To store return addresses and local variables for each call
34
Write an iterative pseudocode for bubble sort.
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
35
What is a node in a graph?
A fundamental unit that represents an entity; connected by edges.
36
What is a directed graph?
A graph where edges have a direction from one node to another.
37
What is a weighted edge in a graph?
An edge with a numerical value representing cost, time, or distance.
38
What is a path in a graph?
A sequence of nodes connected by edges.
39
What is a cycle in a graph?
A path that starts and ends at the same node.
40
How do you define a linked list using a record type in pseudocode?
TYPE Node\nDECLARE Name: STRING\nDECLARE Pointer: INTEGER\nENDTYPE
41
What’s an example of an algorithm with O(1) space complexity?
An algorithm that just uses variables, e.g., d = a + b + c
42
What’s an example of an algorithm with O(n) space complexity?
An algorithm using arrays, e.g., summing values in an array
43
What’s the difference between iterative and recursive approaches?
Iterative uses loops, recursive uses function calls
44
What should a recursive function always include to avoid infinite calls?
A base case
45
What is the benefit of decomposition in problem solving?
Breaks down complex problems into manageable parts
46
What is pattern recognition in computational thinking?
Identifying parts of a problem that are similar to reuse solutions
47
Why might recursion be more elegant than iteration?
It simplifies code for problems with repetitive structure, like tree traversal or factorial
48
Give a real-world example of a recursive process.
Directory traversal in file systems
49
Name three languages suitable for algorithm implementation in this chapter.
Python, Java, VB.NET
50
What is stepwise refinement?
Breaking down problems into smaller and smaller tasks until they are easily solvable