CompSci - Data Organisation + Structures

Question 1

Purpose of data structures

Answer 1

MOE

Manipulation
Organisation
Efficiency

Question 2

Operations on data structures

Answer 2

CSS TRIM

Copy
Search
Sort
Traverse
Remove
Insert
Merge

Question 3

Array definition

Answer 3

Collection of elements that are identified by unique indicies and stored in consecutive memory locations

Question 4

Linked list definition

Answer 4

A web of nodes, each with its memory address, its data and a pointer to the next address. Nodes don’t have to be near each other in memory.

Question 5

Stack definition

Answer 5

FILO or LIFO structure

Question 6

Queue definition

Answer 6

FIFO or LILO structure

Question 7

Binary trees definition

Answer 7

Web of nodes connected by branches and two child nodes for each individual node.

Question 8

Hashing table definition

Answer 8

Memory address of the data is calculated by the output of the hashing algorithm that is applied on the data itself.

Question 9

OUTPUT ALL linked list

Answer 9

pointer = 1
linked_list = []
while pointer != -1
node = linked_list(pointer)
output node(data)
pointer = node(pointer)

Question 10

LINEAR SEARCH linked list

Answer 10

flag = False
linked_list = []
input target
address = 1
while address != -1
node = linked_list(address)
if node(data) == target
return “Target is at: “ address
flag = True
address = node(pointer)
if flag == False:
return “Target not found ):”

Question 11

Adding / Removing nodes from linked lists

Answer 11

To add, change the pointer of the previous node to the address of the new node + change the pointer of the new node to the address of the next node

To remove, change the pointer of the previous node to the address of the next node.

Question 12

Simple and doubly linked lists

Answer 12

Simple linked lists only have the pointers to the next node’s address and their data

address + data + pointer>

Doubly linked lists have the previous and next nodes’ addresses and their data

<pointer + address + data + pointer>

Question 13

Stack and queue removing and inserting

Answer 13

For stacks, pushing and popping

For queues, enqueuing and dequeuing

Question 14

Stack and queue advantages and disadv

Answer 14

Fast processing
Efficient memory
Simple implementation

Inflexible applications
Difficult to manipulate elements

Question 15

Stack uses

Answer 15

Store actions in a program
Store function return addresses

Question 16

Queue uses

Answer 16

Data buffer
Printing queue

Question 17

Circular queue

Answer 17

Fixed size queue that has connected front and rear elements

Question 18

Binary tree traversal

Answer 18

Pre-order: Rlr
Copying

In-order: lRr
In order output

Post-order: lrR
Delete

Question 19

Balancing binary trees

Answer 19

If the difference between the heights of the left and right subtrees is > 1, the tree is unbalanced.

Question 20

Hashing tables advantages and disadv

Answer 20

Fast access
Efficient memory

Collisions
Memory redundancy
Complex algorithms

Question 21

Collision operations

Answer 21

Best

Rehashing - reapply algorithm or change
Daisy chaining - creates linked list at collision address
Linear probing - stores data at next free address
Overflow area - creates unsorted serial file to store collisions.

Worst

Question 22

Fixed length

Answer 22

each field/record has a fixed length

Easy to search and calculate memory size
Potential redundant space

Question 23

Variable length

Answer 23

each field has no set length. Elements are separated by delimiters

don’t need to predetermine memory size
no redundant space

difficult to search
potential redundant space if element length is known (delimiter)