1.4.2 Data Structures

Question 1

Array

Answer 1

“A set of data items of the same type grouped together using a single identifier. Each of the data items is addressed by the variable name and a subscript.”

Question 2

Records

Answer 2

“A data structure which consists of a collection of elements, typically in fixed number and sequence and typically indexed by names. The elements of records may also be called fields.”

“The record type is a data type that describes such values and variables. Most modern computer languages allow the programmer to define new record types. The definition includes specifying the data type of each field and an identifier by which it can be accessed.”

Question 3

Lists

Answer 3

“An abstract data type that represents a sequence of values, where the same value may occur more than once. The name list is also used to cover several concrete data structures that can be used to implement abstract lists especially linked lists.”

Question 4

Tuple

Answer 4

“Another name for a record.”

Question 5

Linkedlist

Answer 5

“A list where each item contains the data together with a pointer to the next item. There may be an additional pointer to the previous item. This means the items can be accessed in order even if they are not stored in order; they do not have to be stored in adjacent memory locations.”

Question 6

Directed Graph

Answer 6

“In a directed graph, the order of the vertices in the pairs in the edge set matters.”

Question 7

Undirected Graph

Answer 7

“In an undirected graph, the order of the vertices in the pairs in the Edge set doesn’t matter.”

Question 8

Stack

Answer 8

“A stack is a dynamic data structure of the form Last In First Out (LIFO).”

Question 9

Queue

Answer 9

“A queue is a dynamic data structure of the form First In First Out (FIFO).”

Question 10

Tree

Answer 10

“A tree is a non-linear dynamic data structure where data items can be thought of as occurring at different levels. There are links between items at one level and their descendants at the next. Each data item has data that relates in some way to its unique parent node. The data items are usually called nodes with the links known as branches. The top level nodes is called the root node.”

Question 11

Binary Search Tree

Answer 11

“A data structure very similar to a tree with the following additional restrictions. Each node can have only 0, 1 or 2 leaf nodes. All left nodes and all of its descendants have smaller values that the root node, while all right nodes and all of its descendants have larger values than the root node.”

Question 12

Hash Table

Answer 12

“A data structure where the calculated value is used to mark the position in the table where the data item should be stored, enabling it to be accessed directly, rather than forcing a sequential search.”