SCC121: weeks 6-10

Question 1

Describe a queue data structure

Answer 1

-First in First out data structure.
-Items are added to the tail of the list and removed from the head.

Question 2

What are some key processes associated with queues?

Answer 2

-Queue()- creates a new queue
-enqueue()- adds a new item to the queue
-dequeue()-removes an item from the list
-isEmpty()- checks if the given queue is empty
-size()- returns the size of the list

Question 3

Why are abstract data types “abstract”??

Answer 3

-Abstract data types are theoretical concepts of how data can be stored.
-ADT definitions describe what operations should be performed, not HOW it is implemented/coded.
-when realised/implemented, ADTs become Data Structures.

Question 4

Data Structures vs ADTs

Answer 4

-data structures are a physical representation of how data is stored structurally in memory.
-ADT is a theoretical overview of the data structure and the functions needed to manipulate it.

Question 5

describe the concept of byte addressable memory.

Answer 5

memory can be seen as an array of bytes. each byte/ cell of the array has a unique address.

Question 6

What is word size?

Answer 6

-number of bits the CPU can process at once
-we assume a word is 32 bits in size unless told otherwise
-differs across machines
-memory addresses increase by word size/8 (size of a byte)
-typically ints are word size.

Question 7

What are the 4 pieces of information associated with a variable?

Answer 7

-name
-value
-address
-type

Question 8

Why use pointers?

Answer 8

-Avoids passing copies of variables, memory efficient
-variables are local to the function they are declared in
-pointers allow programmers to pass memory addresses between functions, pass by value, pass by reference

Question 9

what is a heterogenous data structure?

Answer 9

A data structure that can hold data of multiple types.

Question 10

Give an example of a heterogenous data type.

Answer 10

-records
-has components of varying types, called fields
-fields are identified by name, not index.

Question 11

How would a 2D array be created in C?

Answer 11

int 2dArray[x][y];

Question 12

how would a 2D array be created in java?

Answer 12

int [][] rating = new int[x][y];

Question 13

How would you go about populating a 2D array in C?

Answer 13

• a nested loop can be used to traverse every row and cell.

Question 14

Why use an Array?

Answer 14

-one word identifier for a group of variables.
-random access, elements don’t need to be sequentially traversed through

Question 15

What are the problems of an Array?

Answer 15

-fixed size, does not allow dynamic appending
-insertions and deletions are costly

Question 16

define - what is it used for?

Answer 16

-defining constants

Question 17

Why are constants useful?

Answer 17

defined in one place- only need to be changed in one place.

Question 18

describe the difference between passing by reference and passing by value.

Answer 18

-passing by reference:
a pointer to a variable is passed as a parameter to a function
-passing by value:
the variable itself is passed to the function, not the memory location the value is stored at.

Question 19

describe the key features of a stack

Answer 19

-items are inserted and removed from the tail
-a first in last out data structure

Question 20

what are the necessary functions for a stack ADT?

Answer 20

-Stack()
-push()
-pop()

Question 21

what are some errors that can occur when using stacks?

Answer 21

-overflow error when push() used on a full stack
-underflow error when pop() used on an empty stack

Question 22

what are some common uses of stack ADTs?

Answer 22

-program execution: call stack
-syntax applications: evaluating expressions and parentheses matching
-searching/traversal: depth traversal

Question 23

Describe the concept of a doubly linked list

Answer 23

-each value/piece of data in the list is stored along with a pointer to the next and previous item in the list.
-If the value of the previous or next pointer is nil or ‘/’ this suggests the item is the first or last in the list.
-allows dynamic appending the data structure, no set size

Question 24

describe a singly linked list

Answer 24

-no previous pointer stored along with data, only the pointer to the next value
-cannot be traversed in reverse order
-removing values always requires traversal

Question 25

if storage is quick.....

Answer 25

retrieval will be slow.

Question 26

if storage is slow.........

Answer 26

retrieval will be quick.

Question 27

list the order of big O notation complexity classes, small to large

Answer 27

-O(1) -O(logN) -O(n) -O(n(logn)) -O(n^2) -O(n^3) -O(n^a) -O(2^n) -O(a^n)

Question 28

What is the time complexity of a linear search?

Answer 28

linear time complexity- O(n)

Question 29

what is the time complexity of a binary search?

Answer 29

O(logn)

Question 30

What are key attributes of a recursive algorithm?

Answer 30

-A function that calls itself -input size of parameter passed to recursive function grows smaller each time it is called. -consists of a base case and general case. general case contains recursive call and base case returns result. if base case is never met- overflow error as function never ends

Question 31

Describe the concept of hashing

Answer 31

-method of indexing a storage array. -index is determined by an algorithm we run on the data itself

Question 32

what are some characteristics of a hash table?

Answer 32

-to avoid collisions, may store values in an array at an index- called storing in buckets -elements have unique keys -hash function uses key to generate hash code -hash values map to buckets which contain keys

Question 33

how can collisions be reduced?

Answer 33

-increasing the range of indexes -a hashing algorithm should have a wide output range -using more information from the key usually increases the range