1.1 Data Structures

Question 1

Data structure

Answer 1

A data structure is a group / set / collection of related data items / elements

Question 2

Types of data structure

Answer 2

·   queue
·   stack
·   (binary) tree 
·   record
·   Linked lists
·   array

Question 3

Top node of a binary tree

Answer 3

Root (node).

Question 4

Advantage and disadvantage of binary trees

Answer 4

Advantage: faster to add a value / search for a value
Disadvantage: more complex to program / process / May slow processing/traversal if unbalanced.

Question 5

Two dimensional array of:

Narberth, Cardiff, Pontypridd, Wrexham, Rhyl, Bangor, Denbigh

Answer 5

Table

Question 6

Explain what is meant by the term linked list.

Describe one benefit and one drawback of using a linked list compared with using an array.

Answer 6

A linked list is a set of data elements, where each element contains:
· the data itself
· a pointer to the next element
Benefit :
New items can be inserted into a linked list without rearranging all the other elements
· If programmed dynamically uses memory more efficiently
Drawback :
· A linked list is more complex to program / manipulate than an array
· Extra programming is required to access the data in the opposite direction
· Can only be accessed in a linear manner.

Question 7

Write a simple program using the assembly language commands in the table
above to demonstrate how two numbers can be added together and stored in a register

Answer 7

CLR R
LOD R, 0001
LOD S, 0002
ADD R,S
STR R 0003
CLR R

Question 8

Fetch phase of the fetch execute cycle, making clear the role of the :
PC (program counter)
MAR (memory address register)
MDR (memory data register)

Answer 8

· The address of the next instruction is copied from the PC to the MAR
· The instruction is copied to the MDR
· The PC is incremented so that it holds the address of the next instruction.

Question 9

Difference between searching for an item in an ordered list compared with searching an unordered list.

Answer 9

When searching an ordered list the search can be terminated when an item greater than the search value (or less than) is reached

When searching an unordered list the search cannot be terminated until the last item has been reached.

For an ordered list a binary search can be used.

Question 10

Records

Answer 10

A record is a set of data Items all related to a single individual/entity it can contain data of different types.

Question 11

Stacks

Answer 11

A stack is a small register that stores the address of the last program request a stack

Question 12

Describe a computer application that is the most appropriate data structure to use and explain why it is the most appropriate data structure in this case

Answer 12

Example could be subprogram return addresses this is because of the idea of winding back nesting of sub programs

Question 13

Queues

Answer 13

Q pointer is a pointer that points to a part of the queue. A queue will have two pointers front and rear
FIFO

Question 14

Trees

Answer 14

The tree is a data structure that holds a large amount of data for the process of quick searching and producing different ordered lists. The tree needs to be balanced for the accesses to be quick

Question 15

Advantages and disadvantages of a binary tree

Answer 15

And advantage is it is faster to search/add a value

A disadvantage is it is more complex to program/process

Question 16

Balanced binary tree

Answer 16

The above tree is balanced and the maximum number of comparisons to locate an item would be the same as the number of levels

Question 17

Unbalanced binary tree

Answer 17

The above tree is unbalanced and a maximum number of comparisons to locate an item would be the same as the number of items

Question 18

Linked lists

Answer 18

A link to the list is a set of data elements which each element contains the data itself and a pointer to the next element

Question 19

Benefits and drawbacks of linked lists

Answer 19

Benefits:
New items can be inserted into a link list without re-arranging all the other elements
If programmed dynamically uses memory more efficiently

Drawbacks:
A link to the list is more complex to program than an array
Extra programming is required to access the data in the opposite direction
Can only be accessed in linear manner

Question 20

Process of hashing

4 points

Answer 20

A random access file is one where the physical location of the record is calculated from the data in the key field

Sometimes a date a collision a case. In the second stances there needs to be an overflow area where the latest data is stored. A flag is set in the original block and the data is moved into designated overflow area for subsequent linear search

When the file begins to get quite full then maybe many items in the overflow area and access maybe come slow

A solution to this problem is to create a new crashing algorithm and I larger file may be needed