3-Data Structures (Arrays Lists Stacks Queues)

Question 1

Properties of a linear data structure

Answer 1

There is a UNIQUE first element
There is a UNIQUE last element
Every component has a unique predecessor (except the first)
Every component has a unique success (except the last).
If any are false, it’s nonlinear.

Question 2

What are the 2 methods for accessing data stored in a linear structure

Answer 2

Sequential access - by accessing all elements preceding N,

Direct access, any element can be accessed directly.

Question 3

What are homogeneous structures?

Answer 3

All the same type

Direct- array

Question 4

What are heterogeneous structures?

Answer 4

All different types

Direct- record

Question 5

General sequential access structure?

Answer 5

List

Question 6

LIFO sequential access structure?

Answer 6

Stack

Question 7

FIFO sequential access structure?

Answer 7

Queue

Question 8

Example of a non linear strucutre

Answer 8

Set

Question 9

Domain of an array (contents)

Answer 9

A collection of fixed number of components of the same type

A set of indexes used to access the data stored. One to one relationship.

Question 10

Advantages of linked lists

Answer 10

• Fair use of memory
• Size of the structure does not need to be declared in advance
• Insertions and deletions are cheaper

Question 11

Disadvantages of linked lists

Answer 11

Algorithms are more complex, harder to read and harder to debug
Allocation and de-allocation of memory space impose some overhead to the performance of the algorithm

Question 12

What is the SIEVE OF ERATOSTHENES

Answer 12

Gives all prime numbers between 2 and N

Question 13

What are linked lists

Answer 13

It consists of a collection of records called nodes each containing at least one member that gives the location
of the next node in the list.

Question 14

What is a list?

Answer 14

It is a linear structure that provides only sequential access to its elements
• It normally has two “special” named elements called head and tail.
Main advantage over arrays is easy insertion and deletion of nodes
• Mostly when implemented using dynamic allocation

Question 15

When examining a list, what cases do we have to consider?

Answer 15

• When examining a list, we most often have to consider three separate cases
• The node is the first node of the list
• The node is an “interior” node
• The node is the last node of the list
The above is the reason why some programs choose to use sentinels in their
linked lists.

Question 16

What is a sentinel?

Answer 16

Empty node that points to the last and first nodes of a list.

Question 17

What is a multilist

Answer 17

A multilist is a linked list whose nodes contain multiple link fields that form independent linked lists
• For instance a doubly linked list is a multilist with the invariant that x.left.right and x.right.left are both equal to x.

Question 18

Applications of stacks

Answer 18

A few examples include:
• Expression Evaluation
• Runtime Memory Management
• A Call Stack is used to hold information about function calls
• Search problems
• Most solutions require a “memory” to know which part of the search space has not been explored
• Reversing linear orders