ABSTRACT DATA STRUCTURES | APPLICATION

Topics from the IB Computer Science Specification 2014

ON THIS PAGE
SECTION 1 | THE APPLICATION OF DYNAMIC DATA STRUCTURES

ALSO IN THIS TOPIC
RECURSION
DATA STRUCTURES
LINKED LISTS
​​​TREES
YOU ARE HERE | ​APPLICATION
TOPIC 5 REVISION
KEY TERMINOLOGY
TOPIC 5 ANSWERS

---

Topics from the International Baccalaureate (IB) 2014 Computer Science Guide. 

SECTION 1 | DYNAMIC DATA STRUCTURES

A dynamic data structure is a type of data structure that can grow or shrink in size during runtime, as the program's needs change. Dynamic data structures are implemented using memory allocation techniques that enable the program to allocate and deallocate memory as needed. Unlike static data structures, which are defined with a fixed size at the time of creation and cannot be resized during runtime, dynamic data structures can be resized, which makes them more flexible and adaptable. Examples of dynamic data structures include linked lists, stacks, queues, and trees. Dynamic data structures are useful in situations where the size or complexity of the data is not known in advance or may change over time, as they can adapt to the program's needs and reduce memory waste. However, dynamic data structures also require more complex memory management, as the programmer is responsible for allocating and deallocating memory at the appropriate times to prevent memory leaks and other issues.

When a dynamic data structure is used, it is typically saved in the heap memory area of the program's memory. This is because dynamic data structures are allocated and deallocated during runtime, and the heap memory provides the flexibility to allocate and deallocate memory as needed.

Heap memory uses a region of a computer's RAM (Random Access Memory) that is also known as the heap. The heap is a dynamic memory area that is used for runtime memory allocation and deallocation. The heap memory is typically managed by the operating system or the runtime environment of the program.

The choice of memory area for a particular data structure depends on the specific requirements of the program. Dynamic data structures are typically saved in the heap memory area because they can grow or shrink in size during runtime, and the heap provides the flexibility to allocate and deallocate memory as needed. However, this requires careful and deliberate memory management to avoid memory leaks or other memory-related errors.

A situation suitable for a dynamic structure:
A situation where the number of elements that need to be stored can change during the runtime of the program, and the size of the data structure needs to adapt to the changing requirements. For example, consider a program that reads data from a CSV file, and the number of records in the file can vary. A dynamic data structure such as a linked list, stack, or queue could be used to store the records as they are read, as they can grow or shrink in size as needed, without wasting memory.

A situation suitable for a static structure:
A situation where the number of elements that need to be stored is fixed and known in advance, and the program does not need to modify the data structure during runtime. For example, consider a program that calculates the average of a fixed number of test scores. A static data structure such as an array could be used to store the scores, as the size of the array is known in advance and does not need to be changed during runtime. This can simplify memory management, as the program does not need to allocate or deallocate memory dynamically, and can also provide better performance, as static data structures often use contiguous memory locations, which can be more efficient to access than dynamic data structures.

1: ​What is a dynamic data structure?
a) A data structure whose size is fixed and cannot be changed during runtime
b) A data structure whose size can be changed during runtime

2: Which memory area is typically used to store dynamic data structures?
a) Stack memory
b) Heap memory
c) Cache memory
d) Flash memory

3: Which data structure follows the Last-In-First-Out (LIFO) principle?
a) Queue
b) Stack
c) Heap
d) Binary tree

4: Which data structure follows the First-In-First-Out (FIFO) principle?
a) Queue
b) Stack
c) Heap
​d) Binary tree

5: Which data structure is used to implement a priority queue?
a) Stack
b) Queue
c) Binary tree
d) Heap

6: What is the disadvantage of using a dynamic data structure over a static data structure?
a) Dynamic data structures are more difficult to implement than static data structures
b) Dynamic data structures require more memory and may be slower than static data structures

7: Which data structure can be used to implement a stack?
a) Linked list
b) Queue
c) Heap
d) Array

8: What is the difference between a singly linked list and a doubly linked list?
a) A singly linked list has a pointer to the previous node, while a doubly linked list does not.
b) A singly linked list has a pointer to the next node, while a doubly linked list has pointers to both the previous and next nodes.
c) A singly linked list is faster than a doubly linked list.
d) A doubly linked list is more memory efficient than a singly linked list.

9: Which of the following is a dynamic data structure?
a) Array
b) Stack
c) Linked list
d) Binary tree

10: Which data structure is commonly used to implement a breadth-first search algorithm?
a) Stack
b) Queue
c) Linked list
d) Binary tree

ALSO IN THIS TOPIC

RECURSION
DATA STRUCTURES
LINKED LISTS
TREES
APPLICATION
TOPIC 5 REVISION
KEY TERMINOLOGY
TOPIC 5 ANSWERS