Data Structures and Data Manipulation

Question 1

Data Structure

Answer 1

Is a group of related data items.

Question 2

Static Data Structure

Answer 2

Are those where the size is fixed when the structure is created (the size cannot change during processing).

Question 3

Dynamic Data Structure

Answer 3

Are those where the size of the data structure changes as data is added and removed.

Question 4

Static vs Dynamic

Answer 4

Static - amount of storage required known so easier to program. Dynamic - amount of storage not known more complex code.

Question 5

Stack

Answer 5

LIFO. A stack is a list in which insertion and deletion take place at the same end (TOP). One pointer – top.

Question 6

Stack - uses

Answer 6

Storing return addresses (during subroutine calls), Passing parameters, Storing contents of registers while processing interrupt
Reversing the order of a set of data.

Question 7

Stack overflow/underflow

Answer 7

Overflow error when try to push an item onto a full stack and Underflow when try to pop item off empty stack.

Question 8

Stack – insert algorithm

Push item onto stack

Answer 8

If Stack is full Then Error and stop Else Increment StackPointer. Add data item at position StackPointer End if.

Question 9

Stack – retrieve/delete alg

Pop item off stack

Answer 9

If Stack is empty Then Error and stop Else Return the data item at position StackPointer. Decrement StackPointer End if.

Question 10

Queue

Answer 10

FIFO. A queue is a list. Insertion is done at one end, while deletion is performed at the other end. Front and back pointers.

Question 11

Q overflow/underflow

Answer 11

Overflow error when try to enqueue an item onto a full queue and Underflow when try to dequeue item off empty queue.

Question 12

Queue - uses

Answer 12

Jobs waiting for a printer in a spool queue, Job queue batch processing system, Keyboard buffer.

Question 13

Shuffle queue

Answer 13

Front index always fixed (items shuffle up to front when an item is dequeued.

Question 14

Circular queue

Answer 14

When enqueuing next index moves forward. When dequeuing the front index moves forward. Circular as next pointer wraps to beginning once last index is reached.

Question 15

Queue – insert algorithm / add item to circular queue

Answer 15

(Enqueue). If Queue is full Then Error and stop Else Add data item at position NextPointer. Increment NextPointer. If NextPointer > MaxIndex Then Assign the value of 1 to NextPointer End if.

Question 16

Queue – retrieve/delete

from circular queue

Answer 16

(Dequeue). If Queue is empty Then Error and stop Else Return the data item at position FrontPointer. Increment FrontPointer. If FrontPointer > MaxIndex Then Assign the value of 1 to FrontPointer End If End If.

Question 17

Tree

Answer 17

Tree is represents the relationship between data items. (Stack and queue don’t imply relationship between data items).

Question 18

Tree - uses

Answer 18

Binary search tree - storing data in such a way that it makes it easy and fast to search. Representing sorted lists of data.
Most databases use this tree concept as the basis of storing, searching and sorting it’s records.

Question 19

Tree – insert algorithm

add item to a tree

Answer 19

Start at root. REPEAT IF new data

Question 20

Tree – retrieve algorithm

Answer 20

Start at root. WHILE pointer is not Null DO IF current data = required data THEN RETURN current data ELSE IF required data

Question 21

Tree – delete algorithm

Answer 21

Deletion is more tricky as simply deleting a node could detach child nodes from the tree. Deletion could be done in the following ways: Mark the node deleted but leave in tree to maintain structure. OR Re-attach any child nodes to the tree

Question 22

Binary Search

Answer 22

The binary search is more efficient than the linear search, but requires the data to be in order.

Question 23

Binary Search Alg

Answer 23

1) Look at the item at the midpoint of the list (the current item). 2) If the current item is the item sought, then it has been found. 3) If the current item is not the item sought, discard the half of the list that can’t contain the item sought and repeat the same method with the other half of the list. 4) Keep repeating these steps until the item is found or the list contains no items.

Question 24

Binary Search Adv

Answer 24

Usually faster because half of the data is discarded at each step and fewer items checked. This is more efficient for large files.

Question 25

Binary Search Disadv

Answer 25

One disadvantage of a binary search is that items must be in an order to allow appropriate items to be discarded.

Question 26

Serial Search (Linear)

Answer 26

The search starts at the beginning of the list. Each element in turn is compared with the required value until a match is found or the end of the list is reached.

Question 27

Serial Search Alg

Answer 27

ThisElement = 1. Found = False. REPEAT IF List[ThisElement] = ElementSought THEN Found = True ELSE ThisElement = ThisElement + 1 UNTIL Found = True OR ThisElement > Max.

Question 28

Serial Search Adv

Answer 28

A serial search can be used on unordered sets of data.

Question 29

Serial Search Disadv

Answer 29

Generally slower because all data must be checked until the item is found or the end of the list is reached.

Question 30

Merging Data Files

Answer 30

Note when merging data files duplicates are not kept (just one appears in the new file).

Question 31

Merging Data Files Alg

Answer 31

OPEN existing files. CREATE a new file. CHECK existing files are not empty. Use pointers to identify records for comparison. REPEAT compare records indicated by pointers. COPY earlier value record to new file. MOVE correct pointer UNTIL end of one file. COPY the remaining records from the other file. CLOSE the files.

Question 32

Insertion Sort

Answer 32

Insert one number at a time into correct position… so list of sorted numbers is built up.

Question 33

Insertion Sort Adv

Answer 33

simple sorting algorithm and relatively efficient for small sets of data and mostly-sorted lists. It’s relatively fast for adding a small number of new items periodically.

Question 34

Insertion Sort Disadv

Answer 34

Inefficient for large sets of data.

Question 35

Quicksort

Answer 35

If the first pointer is less than the last pointer (if there are elements in the list) then:
1. Select an item at random to act as the ‘pivot’. 2. Create two new lists 3.…one with all items less than pivot 4…other with all items greater than pivot 5. Repeat these four steps until all lists only have one item.

Question 36

Quicksort Adv

Answer 36

Very quick for large sets of data.

Question 37

Quicksort Disadv

Answer 37

Initial arrangement of data affects the time taken. Harder to code.