Vai al contenuto

Eduqas A level Computer Science

A-Level · EduqasComputer Science20 appunti in 9 cartelle, 74 KB

20 note di ripasso per Eduqas A-Level Computer Science, create da cookie, in 9 sezioni che seguono gli argomenti del corso.

Notes for Eduqas A level Computer Science, on the 2015 specification for exams in 2027, in folders for each area of the course in the specification's order: data structures and algorithms, programming, computer architecture, communication, data, databases, operating systems, security and society. Delete any folder your course leaves out once the notes are yours.

Contenuto

La prima nota

Data structures and algorithms / Data structures

A data structure is a way of organising data in memory so that it can be stored, found and changed efficiently. The choice of structure decides which operations are cheap and which are expensive, so a programmer picks a structure for the operations the program needs most.

Arrays and records

An array holds a fixed number of elements of one data type. Each element is selected by an index, so a one-dimensional array of five integers uses indexes 0 to 4 in most languages. A two-dimensional array uses a row index and a column index, which suits a grid such as a seating plan or a game board. Arrays of three dimensions add a third index, as in a cube of values. Reading or writing an element takes the same time wherever it sits, because the index gives its position directly.

A record groups fields under one name. A record for a customer might hold a name (text), an account number (integer) and a credit limit (real). Unlike an array, the fields of a record can have different types, and each field is read by its name rather than by a number. Records are often stored in an array, giving a table of customers in which each element is one record.

Stacks and queues

A stack is a last-in, first-out structure. The item added most recently is the first one removed. Two operations define it: push adds an item to the top, and pop removes the top item. Stacks suit tasks that need to undo the most recent step, and they are how a program keeps track of nested subprogram calls.

A queue is a first-in, first-out structure. Items leave in the order they arrived, so a queue suits a print spooler or a list of customers waiting for service. Adding an item is called enqueue and removing one is called dequeue.

Both structures can be built in a one-dimensional array with pointers. A stack needs one pointer, usually called top, that records the position of the most recent item. A queue needs two: a front pointer for removal and a rear pointer for insertion. In a plain array queue the space at the front is wasted once items are removed, so a circular queue lets the rear pointer wrap back to the start of the array and reuse that space.

Linked lists

A linked list is a chain of nodes. Each node holds a data value and a pointer to the next node. The list is entered at a head pointer, and the last node holds a null pointer to show that nothing follows it. Inserting or removing a node means changing a few pointers rather than moving the other items, which is the main advantage over an array. The cost is that the list must be followed from the head to reach a given item.

A linked list can also be stored in arrays. One array holds the data values, a second array holds the position of the next node for each entry, and a separate variable holds the position of the first node.

Trees

A tree is a hierarchical structure. One node is the root, and every other node has exactly one parent. A node may have child nodes, and a node with no children is a leaf. A binary tree allows at most two children per node. In a binary search tree, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger. This ordering lets a search go left or right at each node, discarding about half of the remaining values at each step.

Trees can be represented with pointers, with each node holding its data and pointers to its children, or with arrays in which the children of a node are found by calculation.

Hash tables

A hash table stores items at positions worked out from their keys. A hashing algorithm turns a key into an address. The division method, for example, divides the key by the table size and uses the remainder as the address. With a table of 10 locations, key 23 is stored at address 3, because 23 MOD 10 is 3.

Two keys can produce the same address, which is a collision. A common response is to place the second item in the next free location, or in a separate overflow area. A good hashing algorithm spreads keys evenly so that collisions are rare, and the table then gives direct access to an item with almost no searching.

Choosing a structure

Each structure has a job it does well. Arrays give fast access by position, records group related fields of different types, stacks and queues control the order in which items are handled, linked lists make insertion and removal cheap, trees keep data in a hierarchy that can be searched quickly, and hash tables give direct access from a key. Programmers choose the structure that makes the most common operation in their program the simplest.

E altri 19: aprine uno qualsiasi dall’elenco qui sopra.

Valutazioni

Non ci sono ancora recensioni scritte. Aggiungi queste note alle tue e potrai essere il primo a lasciarne una.