1.4.2 Data structures Flashcards Preview

A Level Computer Science > 1.4.2 Data structures > Flashcards

Flashcards in 1.4.2 Data structures Deck (51)
Loading flashcards...

Describe a primitive data type

A data type which is assigned to a variable used to hold a single piece of data


Describe a composite or compound data type

A data type which is assigned to a variable used to hold multiple related pieces of data


Describe an abstract data type

A conceptual model that describes how data is stored and which operations can be carried out on them


Describe what a data structure is

The implementation of an abstract data type in a program


Explain what a static data structure is

A set amount of memory locations / size to store data


Explain what a dynamic data structure is

Can group data, while also being able to grow in size


What is an array data structure?

A data type that holds data that are usually related. It has a fixed size that cannot be changed during running.


What is a tuple data structure?

A data structure that cannot mutate, which contains multiple constants


Describe a list data structure

A dynamic array


Describe a record data structure

A data structure which allows you to make your own data type consisting of different fields


Describe a linked list data structure

A list data structure which stores data in the next free space, and links them together with pointers


What is a node, for a linked list, and what does it contain?

An individual element of the linked list

Contains the data item and the next address location


What are some advantages of a linked list?

  • Flexible structure - pointers can be changed to shape the ordering system
  • Can easily remove nodes, as very few pointers need to be changed


What are some disadvantages of a linked list?

  • Slow to check through as it must be started at the beginning and then worked through
  • Hard to update with new nodes, as all previous nodes have to be checked and pointers moved to add the new item
  • Hard to find a specific item, as every node has to be gone through to find it
  • More storage space is required since the pointers also have to be stored


Describe a linear queue data structure

FIFO. Pointers point to the start of the queue where items are removed, and to the end where items are added


Describe a circular queue data structure

Functions the same as a linear queue, except it reuses the empty spaces at the front of the queue


What is the advantage of a circular queue over a linear queue?

After elements are removed, the circular queue can reuse the space left behind


Describe a priority queue structure

Each element has a priority value alongside the data, and it is all stored in priority order. This is similar to an ordered linked list.

A new element is added according to its priority value, and the highest priority element is removed first


Describe a stack data structure

LIFO. The last item to be added to the stack is the first item to be removed.


What is the purpose of the peek() operation?

Returns the item at the top of a stack without removing it


What is the purpose of the push() operation?

Adds an element to the top of the stack


What is the purpose of the pop() operation?

Removes an element from the top of a stack


Describe a tree data structure

A hierarchical structure of data, stored as nodes, with parent nodes branching into children nodes.


Define a node in a tree data structure

A unit for data, containing: a sub-tree pointer, the node's data, and pointers to other nodes on the same level


Define a parent and child for a tree data structure

Parent: the predecessor node to branching nodes

Child: a node branching from a predeceasing node


Describe a binary search tree data structure

A dynamic data structure, which can change size during program running. It can have only 0, 1 or 2 branches from each node


What is an advantage of binary search trees over standard root search trees?

Binary trees take a shorter time to search for a particular item than a rooted tree


What are the 3 methods of traversing a binary tree?

Preorder traversal

Inorder traversal

Postorder traversal


What are the features of a preorder traversal?

Is a 'top down' method

Can be used to duplicate the data to create an identical binary tree


Describe a preorder traversal

Pointers are to the left of the node

  • Root visited first
  • Traverses left sub-tree
  • Traverses right sub-tree