Chapter 23 Computational Thinking and Problem-Solving

Question 1

What is an ADT?

Answer 1

Abstract Data Types are a collection of data with associated operations. Data organised according to a certain rule.

Question 2

Types of ADTs (studied in the book)?

Answer 2

Stack
Queue
Circular queue
Linked list
Binary tree
Hash table
Dictionary

Question 3

Which are the pointers in a stack?

Answer 3

Base of stack pointer

Top of stack pointer

Question 4

Which item is accessable in a stack?

Answer 4

The top item

Question 5

The main difference between the stack and queue when an item is removed?

Answer 5

In a stack the top of stack pointer is decreased.

In a queue we need to move all the items one slot forward.

Question 6

Which are the pointers in a queue?

Answer 6

Front of queue pointer

End of queue pointer

Question 7

What is a node in a linked list?

Answer 7

An element of the list

Question 8

What can a node consist of?

Answer 8

Several data items and a pointer

Question 9

What is a pointer in a list?

Answer 9

A variable that stores the address of the node

Question 10

What is a null pointer and a start pointer in a list?

Answer 10

A null pointer is a pointer that doesn’t point to any node and it is represented by ‘Ø’ symbol.
A start pointer is a pointer that points to the first node in the list.

Question 11

What is the difference between linear and linked lists?

Answer 11

1. Reordering:
   
   • linked lists, only the pointer needs to be changed
   • linear lists, all data needs to be moved
2. Linked lists save time, on the other hand linked lists also take up more storage
3. Linked lists can be stored in an array of records. One record consists of the data and a pointer

Question 12

Best practice in a linked list regarding the unused nodes.

Answer 12

Unused nodes are usually linked into another linked list (the free list).

Question 13

What is the pseudocode for initiating a linked list?

Answer 13

Declare the type, the declare an array or list of the new type. 
For example:
TYPE ListNode
	DECLARE Data	: STRING
	DECLARE Pointer	: INTEGER
ENDTYPE

DECLARE List[1 : 7] OF ListNode

Question 14

How are values entered in a binary tree?

Answer 14

If the value that needs to be under a node is greater than the upper node it goes to the right
If the value that needs to be under a node is smaller than the upper node it goes to the left

Question 15

What is the idea behind hash tables?

Answer 15

The idea behind hash tables is to calculate and address (the array index) from the key value of the record and store the record at that address

Question 16

What does hashing mean?

Answer 16

Calculating an address from a key

Question 17

What does collision mean?

Answer 17

If two different key values hash to the same address this is called a ‘collision’

Question 18

How does Chaining work?

Answer 18

Create a linked list for collisions with start pointer at the hashed address

Question 19

How does Using overflow areas work?

Answer 19

All collisions are stored in a separate overflow area, known as ‘closed hashing’

Question 20

How does Using neighbouring slots do?

Answer 20

perform a linear search from the hashed address to find an empty slot, known as ‘open hashing’

Question 21

Which are the ways of handling collisions in a hash table?

Answer 21

Chaining 
Closed Hashing (uses overflow areas)
Open Hashing (uses the same list but adjacent slots)

Question 22

How are dictionaries setup?

Answer 22

Dictionaries are setup as Hash tables.