Data Structures

Question 1

Define an interface

Answer 1

A set of procedures that operate on the data structure

Question 2

Why is an abstract data type ‘abstract’?

Answer 2

Because we are not concerned with the implementation of the data structure but rather what operations we can perform using the data structure

Question 3

Define strong encapsulation in terms of ADTs

Answer 3

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

Question 3

Define a queue

Answer 3

An ordered collection of items which are added at the tail and removed from the head

Question 4

Why are queues beneficial?

Answer 4

They provide FIFO functionality meaning that items can be easily reversed and traced back

Question 5

How do you use a structure in C to define a queue?

Answer 5

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

Question 6

How do you add an item to a queue in C?

Answer 6

1. Check whether the queue is full
2. Check whether the head pointer is NULL
3. If the head pointer is NULL then set the head pointer equal to the element you want to add
4. 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

Question 7

Define homogeneous

Answer 7

Consists of elements with all the same data type

Question 8

Define heterogeneous

Answer 8

Consists of elements of different data types

Question 9

Describe byte addressable memory

Answer 9

Memory can be represented as an array of bytes with each cell having a unique address written in hexadecimal

Question 10

What is a word?

Answer 10

The smallest unit of addressable memory in a computer

Question 11

What is the size of a word?

Answer 11

The size of a word varies from machine to machine but we assume a word is 32 bits long

Question 12

How many bits are required to store an integer?

Answer 12

32

Question 13

What are the 3 aspects of a variable?

Answer 13

1. A symbolic name given by the programmer
2. The value is contains
3. An address where it resides in memory

Question 14

Define variable scope

Answer 14

The functions of a program in which a variable can be accessed

Question 15

Why do we have to use pointers in C?

Answer 15

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

Question 16

What is indirection?

Answer 16

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

Question 17

What does ‘*’ mean?

Answer 17

This is the dereferencing operator because it returns the value stored at the address contained within the operand

Question 18

What does ‘&’ mean?

Answer 18

This is the address-of operator and it returns the address of its operand

Question 19

What does it mean if an operator is unary?

Answer 19

It only takes one input

Question 20

What are the three stages to evaluating an operation?

Answer 20

1. Fetch
2. Evaluate
3. Store

Question 21

Define record

Answer 21

A heterogeneous compound item

Question 22

What is the disadvantage of using arrays?

Answer 22

Arrays are homogeneous meaning that you cannot model any entities that consist of values of different data types using arrays

Question 23

What is a field?

Answer 23

An item which makes up a record

Question 24

Define a record

Answer 24

A heterogeneous compound item made up of fields

Question 25

What are the two ways of selecting a field in a record?

Answer 25

1. Using a . if it is declared directly 2. Using an -> if it declared indirectly as a pointer

Question 26

What does malloc stand for?

Answer 26

Memory allocation

Question 27

What does malloc do?

Answer 27

Dynamically assigns memory to an object

Question 28

What memory section does malloc access?

Answer 28

The heap

Question 29

What is the heap?

Answer 29

A section of memory which is assigned to a program and made available for use by the programmer

Question 30

How is malloc implemented?

Answer 30

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

Question 31

What is the difference between a table and a matrix?

Answer 31

A table has a single variable on one axis where as a matrix has two variables on two axis'

Question 32

How do you define a 2D array?

Answer 32

[][]

Question 33

What are the advantages of array?

Answer 33

1. We can use a single name to represent multiple data items of the same data type 2. They have very fast random access as opposed to sequential access

Question 34

What are the disadvantages of arrays?

Answer 34

1. The size of an array is initialised at runtime and cannot be changed 2. Insertions and deletions from an array are costly

Question 35

Define stack underflow

Answer 35

When you try and pop from an empty stack

Question 36

Define stack overflow

Answer 36

When you try and push to a full stack

Question 37

Define an unbounded stack

Answer 37

A stack that has an infinite size

Question 38

Define a bounded stack

Answer 38

A stack that has a limited size

Question 39

What are some common uses of stacks?

Answer 39

1. Call stacks 2. Checking syntax and semantics 3. Searching 4. Mathematics .e.g. determining the result of postfix equations

Question 40

What is a call stack?

Answer 40

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

Question 41

Programming question: write a program that checks whether there are matching pairs of brackets and braces in a statement

Answer 41

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.

Question 42

How do you use stacks for searching?

Answer 42

If you're doing a depth first search you need to retrace your steps and you do this by popping things from the stack