Data Structures Flashcards
Define an interface
A set of procedures that operate on the data structure
Why is an abstract data type ‘abstract’?
Because we are not concerned with the implementation of the data structure but rather what operations we can perform using the data structure
Define strong encapsulation in terms of ADTs
Encapsulation is strong if details of how the data structure is stored is completely hidden from the user because it means the user has no conceptual idea of how the ADT is stored and implemented
Define a queue
An ordered collection of items which are added at the tail and removed from the head
Why are queues beneficial?
They provide FIFO functionality meaning that items can be easily reversed and traced back
How do you use a structure in C to define a queue?
You create a structure which has two properties, one being the data contained in that position in the queue and the second being a pointer to the next item in the queue
How do you add an item to a queue in C?
- Check whether the queue is full
- Check whether the head pointer is NULL
- If the head pointer is NULL then set the head pointer equal to the element you want to add
- If the head pointer is not NULL then determine the position of the tail of the queue and reassign that pointer so it points to the element you want to add
Define homogeneous
Consists of elements with all the same data type
Define heterogeneous
Consists of elements of different data types
Describe byte addressable memory
Memory can be represented as an array of bytes with each cell having a unique address written in hexadecimal
What is a word?
The smallest unit of addressable memory in a computer
What is the size of a word?
The size of a word varies from machine to machine but we assume a word is 32 bits long
How many bits are required to store an integer?
32
What are the 3 aspects of a variable?
- A symbolic name given by the programmer
- The value is contains
- An address where it resides in memory
Define variable scope
The functions of a program in which a variable can be accessed
Why do we have to use pointers in C?
We can only return one variable from a function in C so, in order to change variables in other scopes in a function, we use pointers to the variables
What is indirection?
A method of referring to an item without referring to the item itself .e.g. referring to the memory address in which a variable is stored rather than referring to the variable itself
What does ‘*’ mean?
This is the dereferencing operator because it returns the value stored at the address contained within the operand
What does ‘&’ mean?
This is the address-of operator and it returns the address of its operand
What does it mean if an operator is unary?
It only takes one input
What are the three stages to evaluating an operation?
- Fetch
- Evaluate
- Store
Define record
A heterogeneous compound item
What is the disadvantage of using arrays?
Arrays are homogeneous meaning that you cannot model any entities that consist of values of different data types using arrays
What is a field?
An item which makes up a record
Define a record
A heterogeneous compound item made up of fields
What are the two ways of selecting a field in a record?
- Using a . if it is declared directly
- Using an -> if it declared indirectly as a pointer
What does malloc stand for?
Memory allocation
What does malloc do?
Dynamically assigns memory to an object
What memory section does malloc access?
The heap
What is the heap?
A section of memory which is assigned to a program and made available for use by the programmer
How is malloc implemented?
Malloc assigns an address from the memory in the heap to a pointer in your program which then becomes the base address for the item you are creating in your program, you then access memory for that object using the pointer
What is the difference between a table and a matrix?
A table has a single variable on one axis where as a matrix has two variables on two axis’
How do you define a 2D array?
<data> <array>[<num_rows>][<num_columns>]
</num_columns></num_rows></array></data>
What are the advantages of array?
- We can use a single name to represent multiple data items of the same data type
- They have very fast random access as opposed to sequential access
What are the disadvantages of arrays?
- The size of an array is initialised at runtime and cannot be changed
- Insertions and deletions from an array are costly
Define stack underflow
When you try and pop from an empty stack
Define stack overflow
When you try and push to a full stack
Define an unbounded stack
A stack that has an infinite size
Define a bounded stack
A stack that has a limited size
What are some common uses of stacks?
- Call stacks
- Checking syntax and semantics
- Searching
- Mathematics .e.g. determining the result of postfix equations
What is a call stack?
When a new function is called a stack frame is pushed to the stack which includes information including the return address, arguments, and local variables. This allows the program to return to where it was once the program has been executed and in the same state as before
Programming question: write a program that checks whether there are matching pairs of brackets and braces in a statement
Create a stack and each time you encounter an open parentheses push to the stack and when you encounter a close parentheses pop from the stack.
If you encounter a stack underflow error or the stack is not empty at the end of the statement then there is an unbalanced number of parentheses.
How do you use stacks for searching?
If you’re doing a depth first search you need to retrace your steps and you do this by popping things from the stack
