Data Structures

Question 1

describe arrays

Answer 1

• stored contiguously in computer memory
• same data type
• insertion at the end of the array = O(1)
• insertion at a new element of index i = O(n)

Question 2

describe linked lists

Answer 2

• node = data + one or more links to other nodes
• last node - next field set to null
• memory NOT allocated contiguously
• size of data field for nodes can be different

Question 3

big O to locate an item in a linked list

Answer 3

n

Question 4

big O to insert an item in a linked list

Answer 4

1

Question 5

big O to delete an item in a linked list

Answer 5

1

Question 6

big O to insert an item into an array

Answer 6

last element - 1
element at i - 1

Question 7

big O to delete an item into an array

Answer 7

last element - 1
element at i - 1

Question 8

big O to locate an item into an array

Answer 8

unsorted - n
sorted - log n

Question 9

describe ADT stack

Answer 9

• LIFO
• push = insert
• pop = delete

Question 10

uses of stacks

Answer 10

• reversing data
• parsing
• backtracking

Question 11

describe ADT queue

Answer 11

• front & rear
• FIFO
• enqueue = inset
• dequeue = delete

Question 12

uses of queues

Answer 12

• scheduling
• simulation

Question 13

define priority queues

Answer 13

• as an item enters the queue it is given a priority
• this determines the order in which the queue is output/read
• higher priorities processed before lower ones even if the entered the queue after them

Question 14

array implementation of stacks

Answer 14

limited size

Question 15

linked list implementation of stacks

Answer 15

‘unlimited’ size
- but extra-memory references

Question 16

applications of priority queues

Answer 16

1. a subroutine in more complex algorithms
2. heapsort algorithms

Question 17

describe heap implementation

Answer 17

• uses a partially ordered binary tree
• allows insertion & deletion with O(log n)
• if operations repeated it is more efficient than linked lists and arrays

Question 18

describe trees

Answer 18

each node in a tree, except the root, has one parent
- parent-child relationship
- nodes without child-nodes = leaves

Question 19

2 conditions of a complete binary tree

Answer 19

1. all internal nodes have 2 children
2. all leaves have the same depth

Question 20

define heap

Answer 20

a complete binary tree down to a depth of d - 1 and the nodes with depth d are as far left as possible

Question 21

2 properties of heaps

Answer 21

1. the root of the heap always contains the largest element
2. depth of heap with n elements is lower bound(log2n)

Question 22

describe a heap as its array implementation

Answer 22

illustration - ordered binary tree
programs - array
- root node = A[0]
- parent node = A[i]
- 2 child nodes = A[2i + 1] and A[2i + 2]

Question 23

heap insert

Answer 23

• attach new node with key K after last leaf
• sift k UP to appropriate place in heap
• O(log n)

Question 24

heap delete

Answer 24

• exchange root’s key with the last K of the heap
• decrease heap size by 1
• sift K down to its appropriate place in the heap
• O(log n)

Question 25

describe a heap sort

Answer 25

- given an array A of n elements, start with initially empty heap and add n elements into heap, one by one - extract the elements from the heap in non-increasing order, putting them back into array A in order