Data Structures

Question 1

What are elementary or primitive data types?

Answer 1

Primitives are predefined data types that are independent of all other kinds and include basic values of particular attributes, like text or numeric values. They are the most fundamental type and are used as the foundation for more complex data types. Most computer languages probably employ some variation of these simple data types.
E.g. real, Boolean, char, integer

Question 2

What are composite data types?

Answer 2

Data types made up of two or more other data types.
E.g. list, array, string (a list of characters)

Question 3

What are abstract data types?

Answer 3

Abstract data types are a logical description of how we view the data and possible operations, independent of the implementation.
E.g. stack, queue
We are only concerned with what the data is representing and not how it’s structured.
We are creating an encapsulation around the data.
Encapsulation is a form of information hiding.

Question 4

What are some examples of queues in real life?

Answer 4

Queueing at a shop or a ticket booth, print job queue, waiting in a line, waiting at the doctor/dentist etc.

Question 5

What is a queue?

Answer 5

A queue is an abstract data type that holds an ordered, linear sequence of items. You can describe it as a first in, first out (FIFO) structure; the first element to be added to the queue will be the first element to be removed from the queue. New elements are added to the back or rear of the queue. When an element is removed, the remaining elements do not move up to take the empty space.

Question 6

How are pointers used in queues?

Answer 6

It’s very wasteful of CPU cycles to refill memory locations with blanks – pointers can be used instead.
Pointers: front and rear.
Front points to the next item to remove and rear points to the last item added.

Question 7

What is a priority queue?

Answer 7

A priority queue is one where each element in the queue has a priority. When new elements are added to the queue, they are inserted ahead of those of lower priority and behind elements of equal priority. A real-world example would be a queue in the school canteen. Students join the queue at the end of the line of other students but prefects can join ahead of students, but behind other prefects.

Question 8

What does the ‘enqueue(data)’ operation do?

Answer 8

Adds an element to the queue (the element is added to the back unless it’s a priority queue).

Question 9

What does the ‘dequeue()’ operation do?

Answer 9

Returns an element from the front of the queue and removes this element from the queue.

Question 10

What does the ‘is_empty()’ operation do?

Answer 10

Checks whether the queue is empty, returns True if it’s empty and False otherwise.

Question 11

What does the ‘is_full()’ operation do?

Answer 11

Checks whether the queue is full, returns True if it’s full and False otherwise.

Question 12

What does the ‘size()’ operation do?

Answer 12

Returns the size of the queue.

Question 13

What are some problems with implementing a queue?

Answer 13

Space in the array cannot be reused. The queue may appear to be full even when there are no items in it.

Question 14

How does a circular queue work?

Answer 14

A circular queue algorithm overcomes the problem of reusing the spaces that have been freed by dequeuing from the front of the array.
The MOD function is used to change the pointers.
E.g. (Current index + 1) MOD 5 for a queue with 5 items.

Question 15

What is a static data structure?

Answer 15

Static data structures are fixed in size.
They cannot grow, shrink, or be freed during execution.
An array is a static data structure.

Question 16

What is a dynamic data structure?

Answer 16

Dynamic data structures can grow and shrink.
They allocates and deallocate memory from the heap (an area of memory specifically used for this purpose).
Excessive allocation of memory, without deallocation, may cause overflow (exceeding the maximum memory limit).
Python – list
Java - arrayList

Question 17

What is a list?

Answer 17

A list is an abstract data type that describes a linear collection of data items in some order, in that each element occupies a specific position in the list. The order could be alphabetic or numeric or it could just be the order in which the list elements have been added. Unlike a set, the elements of a list do not need to be unique.

Question 18

What are some real-life examples of lists?

Answer 18

Lists are used in a wide variety of situations. Many of us use to-do lists to keep ourselves organised. You may use a shopping list to make sure you don’t forget to buy something when you visit the supermarket. If you use a streamed music service, you probably have several playlists.

Question 19

How can you implement a list using a static data structure?

Answer 19

When a list is implemented using a static array the maximum number of elements is fixed. This means that:
When the array structure is full you cannot add any more items to the list
When the array structure is empty, or only partially full, you can be wasting valuable memory space
If you decide to use a static array to store your list, you still have some choices to make about how you organise the data. You could populate the array sequentially, element by element, but this can cause maintenance problems. If items are constantly added and deleted from the list, you will end up with gaps that you will have to locate with a linear search to find space for new items. You could choose to keep moving the items towards the start of the array to fill any gaps. This processing can be avoided if you include an index pointer to the next occupied element in the list; in this way your array will act as a form of linked list.

Question 20

How can you implement a list using a dynamic data structure?

Answer 20

A list can be implemented dynamically using a linked list. A linked list is a dynamic data structure, which means that the size of the list can change at run time.
Each element in a linked list is called a node. Each node stores the data relating to the element and a pointer to the next node.
There is also a separate pointer that indicates the first element in the list (the head of the list). This has a null value when the list is empty. The next node pointer of the last element in the list always points to a null value to mark the end of the list.

Question 21

What does the ‘isEmpty()’ list operation do?

Answer 21

Tests for an empty list, returns True if the list is empty and False otherwise.

Question 22

What does the ‘append(item)’ operation do?

Answer 22

Add a new item to the end of the list.

Question 23

What does the ‘remove(item)’ operation do?

Answer 23

Removes the first occurrence of an item from the list.

Question 24

What does the ‘count(item)’ operation do?

Answer 24

Returns the number of occurrences of an item in a list.

Question 25

What does the ‘len(item)’ operation do?

Answer 25

Returns the number of items in a list.

Question 26

What does the ‘index(item)’ operation do?

Answer 26

Returns the position of an item in a list.