Summary Fundamentals of Data Structures: Computer Science AQA A-Level notes
8 views 0 purchase
Course
Unit 2 - Fundamentals of data structures
Institution
AQA
AQA A-Level Computer Science notes on the topic of Data Structures (which appears on paper one!)
Notes are detailed and well laid out and all specific terms and areas are well explained to enhance understanding. There's even a contents page!
Good luck with your exams! Hope this helps!!!
Writ...
4.2 - DATA STRUCTURES
Data Structures: A data structure is a format used to store, organise and manage data in a way that
allows efficient access and modification for the needs of the program.
Contents
Arrays....................................................................................................................................................2
Single-Dimensional Array...................................................................................................................2
Multi-Dimensional Array....................................................................................................................2
Fields, records and files.........................................................................................................................2
Abstract Data types/structures..............................................................................................................2
Queues...............................................................................................................................................2
Linear Queues................................................................................................................................3
Circular Queues.............................................................................................................................3
Priority Queues..............................................................................................................................4
Lists....................................................................................................................................................4
Stacks.................................................................................................................................................5
Overflow and Underflow...............................................................................................................5
Call Stacks......................................................................................................................................5
Hash tables........................................................................................................................................6
Dictionaries........................................................................................................................................7
Graphs...............................................................................................................................................7
Adjacency Matrix...........................................................................................................................8
Adjacency List................................................................................................................................9
Trees..................................................................................................................................................9
Rooted Trees................................................................................................................................10
Binary Trees.................................................................................................................................10
Vectors.............................................................................................................................................11
Visualisation of a Vector..............................................................................................................12
Convex combination of two vectors............................................................................................13
Dot or scalar product...................................................................................................................13
Static and Dynamic data structures.....................................................................................................15
1
, Arrays
Array: A data structure for storing a finite, ordered set of data of the same data type within a single
identifier.
Single-Dimensional Array
Single-Dimensional Array: An array where each data item can be located using a single
index.
Example = {“George”, “Sue”, “Mo”} 0 1 2
It can be visualised with the following table: “George” “Sue” “Mo”
Multi-Dimensional Array
Multi-Dimensional Array: An array where each data item is located using multiple indices.
Example = [{“Rachel”,1,0.5},{“Emma”,4,1.2},{“Bob”,9,0.9}]
0 1 2
It can be visualised with the following table: 0 “Rachel” 1 0.1
E.g., Example(1,2) would return 9 and Example(0,2) would 1 “Emma” 4 1.2
return “Bob” 2 “Bob” 9 0.9
Fields, records and files
Binary File: An organised collection of records where data is stored in binary.
Fields: A single item of data.
Records: A data structure that stores multiple fields, organised based on attributes, within a single
line of a file.
Text file: An organised collection of records where data is stored in human-readable characters.
Basically, information is stored by computers as a series of files. Each file is made up of records
which are composed of a number of fields.
Abstract Data types/structures
Abstract data types can easily be shown in graphical form, and it is not hard to understand
how to perform operations such as adding, deleting or counting elements in each structure.
An abstract data type (ADT) is a logical description of how the data is viewed and the
operations that can be performed on it, but how this is to be done is not necessarily known
to the user.
o This is an example of information hiding – by providing this level of abstraction we
are creating an encapsulation around the data, hiding the details of implementation
from the user.
Examples of this are: Queues, lists, stacks, hash tables, dictionaries, graphs, trees, and vectors.
Queues
A queue is a “First In First Out” (FIFO) data structure.
2
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Rachelexists. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.22. You're not tied to anything after your purchase.
