Data Structures Part 2

Question 1

Array

Answer 1

An ordered group of items, each of the same data type. The number of items is fixed in size. Each item is identified by a subscript.

Question 2

Use Record When

Answer 2

The data is all about one object e.g. a person, a holiday.

The data is of different data types

Question 3

Use array when

Answer 3

The data is about a number of different items.

The data is all of the same data type.

Question 4

Record

Answer 4

A data structure that holds a number of related data values (possibly of different data types) , normally about the object.

Question 5

Linear (sequential) search

Answer 5

A search where each record is examined in turn until required records is found or the end of the list is reached.

Question 6

Binary search

Answer 6

A search on an ordered list where the middle item is inspected, if it is not the correct item, decide which half of the list contains the required value. Search that half of the list. Repeat the process.

half the list is discarded. This process is repeated.

Question 7

Swapping

Answer 7

The process of exchanging the contents of two storage locations.

Question 8

Bubble Sort

Answer 8

Work through the list examining pairs of records.
If a pair is in the wrong order then swap them.
keep passing through the list until no swaps are made.

Question 9

Insertion Sort

Answer 9

Loop for each element in the unsorted part of the list.

Search through the list finding the position of the highest element.

Swap the highest element with the element at the top of the unsorted part of the list.

The top element is in the correct position so is now part of the sorted list.

Repeat until each item has been put in place.

Question 10

Quick sort

Answer 10

Select the first element.

Partition the list so that those items less than the first item come after it and those items greater than the first item come before it.

The first item is then in it’s correct position.

Sort the two separate lists.

Question 11

Quick Sort - Advantage

Answer 11

It is fastest/most efficient type of sort algorithm. It uses recursion

Question 12

Sort choice depends on

Answer 12

The number of elements in the list.
The amount of disorder in the list.
If the data structure is sorted.
The amount of temporary storage available
Computer /processor speed
Data type.

Question 13

Pointer

Answer 13

A reference to a storage location, an address.

Question 14

Class

Answer 14

A class consists of a description of all of the data in a record together with the operations that can be applied to it.

Question 15

Data structure

Answer 15

It’s an organised group of related data items.

Question 16

Static Data Structure

Answer 16

A data structure that is fixed in size, such as an array.

Question 17

A dynamic data structure

Answer 17

It’s one that can grow as data is added and shrink when data is removed.

Question 18

Stack

Answer 18

The stack is a dynamic data structure operating on the principle of Last In First Out. When an item is removed it is always the most recently added item. E.g. Undo function

Question 19

Pull

Answer 19

Removing an item from a stack.

Question 20

Pushing

Answer 20

Adding an item to a stack

Question 21

Stack Errors

Answer 21

Trying to remove (pull) from an empty stack.

Question 22

Stack Usages

Answer 22

• Implement an undo function.

- Implement a back function.

Question 23

Quueue

Answer 23

A queue is a dynamic data structure operating on the principle of First In First Out. When an item is removed it is always the item which has been in the queue the longest.

Question 24

Queue Errors

Answer 24

Trying to remove an item from an empty queue.

Question 25

Queue Usages

Answer 25

• Print queue (spooling)
• Keyboard buffer
• Audio/video streaming buffering.

Question 26

Linked List

Answer 26

A Linked List is a dynamic data structure operating on the principle of each item being linked to the next by a pointer. It is more versatile than a stack or a queue since data may be added or removed in any order.

Question 27

Linked List Errors

Answer 27

Searching for an item that is not present.

Question 28

Linked List Usage

Answer 28

List joining blocks of a file on a disc.

Question 29

Double linked List

Answer 29

It has a link going to previous record as well as the next record. The list may then be searched in either direction.

Question 30

Circular linked list

Answer 30

It has the last element linked back to the first.

Question 31

Binary Tree

Answer 31

A tree is a dynamic data structure organised as a series of layers. Each data item (node) is linked to exactly one element in the layer above and any layers below.

Question 32

Root

Answer 32

A very top of a tree.

Question 33

Branch

Answer 33

A path joining parts of a tree.

Question 34

Terminal Node

Answer 34

A final node which has no branches beneath it.

Question 35

Subtree

Answer 35

From any node the branches beneath it form trees.

Question 36

Parent

Answer 36

A node immediately above a given node.

Question 37

Child

Answer 37

Nodes connected to and immediately below a given node.

Question 38

Level

Answer 38

All nodes, the same number of branches away from the root node, have the same level.

Question 39

Tree errors

Answer 39

Deleting or searching something that doesn’t exist. - Node not found.

Question 40

Tree Usage

Answer 40

• Hierarchical file structure.

- Domain name structure.

Question 41

Binary Sort Tree

Answer 41

A binary tree where all the values in the left subtree of any node are smaller than the values in the node AND all the values in the right subtree of any node are larger than the value in the node.

Question 42

Traverse

Answer 42

The process of visiting in turn each element in a data structure.