Data Structures

Question 1

What are data structures

Answer 1

Data structures is a format used to store , organise, modify and access data

Question 2

What are the features of an array

Answer 2

An indexed set of related elements
Must be finite and indexed
An array often start from zero
Must only contain elements with the same data type

Question 3

what are Queues
how can they be used

Answer 3

FIFO ( First item added is the first to be removed )
Used in keyboard buffers and breadth first search algorithm

Question 4

Liner queues

Answer 4

It has two pointers ( front and rear)
IsEmpty , IsFull , Enqueue and Dequeue

Question 5

How can emptiness in a queue be detected

Answer 5

By comparing the front and rear pointers

Question 6

Why is a circular queue better than a linear queue

Answer 6

It is more memory efficient

Question 7

What is a circular queue

Answer 7

A type of queue where the front and rear pointers can move over the two ends of the queue

Question 8

What are priority queues

Answer 8

Items are assigned a priority
High priority items are dequeued first before lower priority items

Question 9

What happens when two or more items have the same priority

Answer 9

Items are removed in first in first out

Question 10

What are the features of stacks

Answer 10

It has a pointer
Push
Pop
Peek
IsFull and IsEmpty

Question 11

What happens when a push command is executed on a full stack

Answer 11

A stack overflow is thrown

Question 12

What happens when you use the pop command on an empty stack

Answer 12

Stack underflow

Question 13

When can a graph be used

Answer 13

Can be used to represent networks such as transport networks, IT networks and the
Internet.

Question 14

What does a graph consist of

Answer 14

Consists of nodes (sometimes called vertices) joined by edges (sometimes called
arcs)

Question 15

What is a weighted graph

Answer 15

A weighted graph is one in which edges are assigned a value

Question 16

What are the ways a graph can be represented as

Answer 16

○ Adjacency matrices
○ Adjacency lists

Question 17

What is a adjacency matrices

Answer 17

● A tabular representation of a graph
● Each of the nodes in the graph is assigned both a row and a column

Question 18

What is a adjacency lists

Answer 18

● Represent a graph using a list
● For each node, a list of adjacent nodes is created
● Only records existing connections in a graph

Question 19

What is the difference adjacency matrix ad an adjacency list

Answer 19

Adjacency matrix

Stores every possible edge between
nodes, even those that don’t exist. Almost half of the matrix is repeated data.
Memory inefficient

Allows a specific edge to be queried very
quickly, as it can be looked up by its row
and column.
Time efficient.

Well suited for dense graphs where there are a large number of edges

Adjacency list

Only stores the edges that exist in the
graph.
Memory efficient.

Slow to query, as each item in a list must
be searched sequentially until the desired
edge is found.
Time inefficient.

Well suited to sparse graphs, where there
are few edges.

Question 20

What are trees

Answer 20

They are connected , undirected with no cycles

Question 21

What are rooted trees

Answer 21

● The root node is the only node with no parent, all other roots stem from them

Question 22

What is a leaf node

Answer 22

child nodes with no children

Question 23

What is a binary node

Answer 23

A rooted tree in which each parent node has no more than two child nodes.

Question 24

What are hash tables

Answer 24

A hashing algorithm takes an input and returns a hash.A hash table stores key-value pairs

Question 25

What is collision

Answer 25

When different inputs produce the same hash key

Question 26

How could you solve collisios

Answer 26

You could do that by rehashing

Question 27

What are dictionaries

Answer 27

A collection of key-value pairs

Question 28

What is applications of dictionaries

Answer 28

Dictionary based compression

Question 29

What is a static structure

Answer 29

Static data structures are ○ fixed in size ○ most frequently declared in memory as a series of sequential, contiguous memory locations

Question 30

What are dyanmic structures

Answer 30

○ change in size to store their content ○ store each item of data alongside a reference to where the next item is stored in memory ○ require more work on the part of the computer to set up and use

Question 31

Draw the classification of algorithm problem

Answer 31

constant , quadratic , logarithm , cubic

Question 32

Describe the process that should be followed to add an item to a circular queue implemented as a static data structure using an array.

Answer 32

1.Check the queue is not already full; 2.   Compare the value of the (rear) pointer with the maximum size of the array; 3.   If equal then (rear) pointer becomes zero; 4.   Otherwise, add one to the (rear) pointer; 5.   Insert new item in position indicated by (rear) pointer;

Question 33

Describe the steps involved when adding an item to a priority queue, implemented as a static data structure using an array, that were not required when adding an item to a linear queue.

Answer 33

Starting with the item at the rear of the queue move each item back one place in the array; Until you (reach the start of the queue or) find an item with the same or higher priority than the item to add;

Question 34

Describe the steps involved in adding an item to a linear queue that has been implemented as a static data structure using an array. Your answer should include a description of how any pointers are used and changed.

Answer 34

Check that the queue is not already full; (if it isn’t) then add 1 to the value of the rear pointer; then add the new item to the position indicated by the rear pointer;

Question 35

Describe the method that would need to be followed to attempt to remove an item from a circular queue implemented as a static data structure using an array. Your method should deal appropriately with any issues which could arise.

Answer 35

1.   Check the queue is (not already) empty; 2.   Compare the value of the front pointer with the maximum size of the array; 3.   If equal then front pointer becomes one; A. index of the first position in the array instead of one 4.   Otherwise, add one to the front pointer;

Question 36

Explain how a single stack can be used in the implementation of the repeat action and the undo action.

Answer 36

2. Each time an action is completed it is pushed/added onto the top of the stack; 3. unless it is an undo (or repeat) action; 4. When repeat action is used the top item from the stack is used to indicate the action to complete When undo action is used the top item is popped/removed from the stack of actions;

Question 37

What is meant by recursively-defined?

Answer 37

It calls itself

Question 38

Why are queues in computer systems usually implemented as circular queues?

Answer 38

In a circular queue, the locations will be re-used; Thus a circular queue has a more efficient use of memory; In a linear queue data is static, so queue ‘moves’ through storage

Question 39

What is the role of the stack when a recursively-defined procedure is executed?

Answer 39

Store return addresses;

Question 40

Describe one example of the use of a stack.

Answer 40

Stack of plates

Question 41

A hash table can be used to implement a dictionary data structure. Explain why a hash table is a suitable choice.

Answer 41

Allows direct access to the value being looked-up

Question 42

Time complexity is one of the two measures that are used to describe the complexity of an algorithm. What is the other measure?

Answer 42

Memory (complexity)

Question 43

Some problems are intractable. What does it mean for a problem to be described as intractable?

Answer 43

The problem can be solved; But not in polynomial time , takes too long for a computer to solve

Question 44

What is the significance of the Halting problem?

Answer 44

Shows that some problems are non-computable, shows that some problems cannot be solved by a computer algorithms

Question 45

Explain what approach(es) a programmer might take if asked to ‘solve’ an intractable problem

Answer 45

Use of heuristic; An algorithm that makes a guess/estimate based on experience;solve simpler version of problem

Question 46

Describe the Halting problem

Answer 46

Determining if a program will halt; without running the program;

Question 47

Some problems are tractable. What does it mean for a problem to be described as tractable?

Answer 47

The problem can be solved;In polynomial time or better

Question 48

Why is it not possible to create a Turing machine that solves the Halting problem?

Answer 48

The Halting problem is non-computable there is no algorithm that solves the Halting problem;

Question 49

Describe the steps involved in adding a record to a hash table.

Answer 49

Hash algorithm applied; to key value; result is location in table where the record should be stored; if location is not empty; then use next free location;

Question 50

State advantages of Reverse Polish Notation over infix nota

Answer 50

Easier for the computer to evaluate No need to backtrack when evaluating;